名校考研真題
2015年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合真題及詳解
一、單項選擇題：1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項符合題目要求。請在答題卡上將所選項的字母塗黑。
1已知程序如下：
intS（intn）
{
return（n<＝0）? 0 : s（n-1）+n;
}
voidmain（）
{
cout<<S（1）;
}
程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息依次對應的是（ ）。
A．main（ ）->S（1）->S（0）
B．S（0）->S（1）->main（ ）
C．main（ ）->S（0）->S（1）
D．S（1）->S（0）->main（ ）
【答案】A查看答案
【解析】函數S（intn）是一個遞歸函數：①當實際參數小於等於零時則返回0，並終止遞歸；②當實際參數大於零時則遞歸調用S（n-1），並將S（n-1）的結果加上n作為返回值。程序從main（ ）函數開始，首先調用main（ ）函數；在main（ ）函數中調用S（1）函數時，將main（ ）函數的上下文保存到棧中，並進入函數S（1）；由於函數S（1）的實際參數大於零，需要調用S（0），故將S（1）函數的上下文保存到棧中，進入S（0）；在S（0）中，實際參數小於等於零，遞歸終止。
2先序序列為a，b，c，d的不同二叉樹的個數是（ ）。
A．13
B．14
C．15
D．16
【答案】B查看答案
【解析】二叉樹的先序遍歷定義為：若二叉樹為空，則空操作；否則，訪問根節點，然後先序遍歷左子樹，最後先序遍歷右子樹。本題中，結點a為二叉樹的根節點，左右子樹的先序遍歷可能存在下面四種情況：①左子樹為空，bcd為右子樹；②b為左子樹，cd為右子樹；③bc為左子樹，d為右子樹；④bcd為左子樹，右子樹為空。然後將左右子樹繼續分解，如第①種情況的右子樹先序遍歷（bcd）可能有：a．左子樹為空，右子樹為cd；b．左子樹為c，右子樹為d；c．左子樹為cd，右子樹為空。按照這種方法繼續分解左右子樹，直到不能再分解為止，可得第①和④種情況各包含5種不同情況，第②和③種情況各包含2種情況，因此總共有14種不同的二叉樹。
3下列選項給出的是從根分別到達兩個葉節點路徑上的權值序列，能屬於同一棵哈夫曼樹的是（ ）。
A．24，10，5和24，10，7
B．24，10，5和24，12，7
C．24，10，10和24，14，11
D．24，10，5和24，14，6
【答案】D查看答案
【解析】哈夫曼樹是帶權路徑長度最短的二叉樹。由根節點出發到兩個葉子節路徑中，第二個被訪問的兩個節點的權值要麼相等，要麼和為根節點的權值，故B項錯誤。同理，通過第三個被訪問的節點排除A項。C項，由兩條路徑可推出三個葉子節點的權值分別是：3、10和11，而根據哈夫曼樹的定義可知，權值為3的節點應該和權值為10的結點結合，故C項錯誤。D項，反推出有四個葉子節點，權值分別為：5、5、6和8，滿足哈夫曼樹的條件。
4現在有一顆無重複關鍵字的平衡二叉樹（AVL樹），對其進行中序遍歷可得到一個降序序列。下列關於該平衡二叉樹的敘述中，正確的是（ ）。
A．根節點的度一定為2
B．樹中最小元素一定是葉節點
C．最後插入的元素一定是葉節點
D．樹中最大元素一定是無左子樹
【答案】D查看答案
【解析】二叉樹的中序遍歷定義是「若二叉樹為空，則空操作；否則：①中序遍歷左子樹；②訪問根節點；③中序遍歷右子樹」。A項錯誤，當樹中僅有一個或者兩個結點時，根節點的度就可能不為2；B項錯誤，樹中最小元素是中序遍歷時最後訪問的節點，當沒有右子樹時，最後訪問的節點是根節點；C項錯誤，當最後插入的元素破壞樹的平衡後，樹會進行調整，使其成為中間節點；D項正確，由中序遍歷的特點可知，左子樹的值大於根節點，所以最大元素一定沒有左子樹。
5設有向圖G＝（V，E），頂點集V＝{V0，V1，V2，V3}，邊集E＝{<V0, V1>，<V0, V2>，<V0, V3>，<V1, V3>}，若從頂點V0開始對圖進行深度優先遍歷，則可能得到的不同遍歷序列個數是（ ）。
A．2
B．3
C．4
D．5
【答案】D查看答案
【解析】根據題意知有向圖的結構如圖所示。深度優先遍歷的特點是儘可能先對縱深方向進行搜索，所以可能得到的不同遍歷序列分別是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。
6暫缺
7下列選項中，不能構成折半查找中關鍵字比較序列的是（ ）。
A．500，200，450，180
B．500，450，200，180
C．180，500，200，450
D．180，200，500，450
【答案】A查看答案
【解析】折半查找的過程是：先確定待查找記錄所在的範圍，然後逐步縮小範圍直到找到或找不到該記錄為止。折半查找的關鍵字序列滿足：對每一個關鍵字，其後面的所有關鍵字序列或者都小於等於該關鍵字或者都大於等於該關鍵字。A項錯誤，第三次比較的關鍵字為450，說明待查關鍵字位於200～450間，所以第四次比較時不會遇到關鍵字180。
考研真題、考資格證、考試題庫就選才聰學習網