?

第一部分名校考研真題

一、選擇題1已知程序如下：

程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息依次對應的是（）。[2015年聯考真題]

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．分析算法的易懂性和文檔性

【答案】C查看答案

【解析】分析算法為的就是能對算法有更多、更好的改進。

3先序序列為a，b，c，d的不同二叉樹的個數是（）。[2015年聯考真題]

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種不同的二叉樹。

4下列選項給出的是從根分別到達兩個葉結點路徑上的權值序列，能屬于同一棵哈夫曼樹的是（）。[2015年聯考真題]

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，滿足哈夫曼樹的條件。

5當輸入非法錯誤時，一個“好”的算法會進行適當處理，而不會產生難以理解的輸出結果。這稱為算法的（）。[中山大學考研真題]

A．可讀性

B．健壯性

C．正確性

D．有窮性

【答案】B查看答案

【解析】健壯性是指當輸入數據非法時，算法能作適當的處理并作出反應，而不應死機或輸出異常結果。

6現在有一顆無重復關鍵字的平衡二叉樹（AVL樹），對其進行中序遍歷可得到一個降序序列。下列關于該平衡二叉樹的敘述中，正確的是（）。[2015年聯考真題]

A．根節點的度一定為2

B．樹中最小元素一定是葉節點

C．最后插入的元素一定是葉節點

D．樹中最大元素一定是無左子樹

【答案】D查看答案

【解析】二叉樹的中序遍歷定義是“若二叉樹為空，則空操作；否則：①中序遍歷左子樹；②訪問根節點；③中序遍歷右子樹”。A項錯誤，當樹中僅有一個或者兩個結點時，根節點的度就可能不為2；B項錯誤，樹中最小元素是中序遍歷時最后訪問的節結點，當沒有右子樹時，最后訪問的結點是根結點；C項錯誤，當最后插入的元素破壞樹的平衡后，樹會進行調整，使其成為中間結點；D項正確，由中序遍歷的特點可知，左子樹的值大于根結點，所以最大元素一定沒有左子樹。

7設有向圖G＝（V，E），頂點集V＝{V0，V1，V2，V3}，邊集E＝{<V0,V1>，<V0,V2>，<V0,V3>，<V1,V3>}，若從頂點V0開始對圖進行深度優先遍歷，則可能得到的不同遍歷序列個數是（ 

）。[2015年聯考真題]

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。

8程序段

其中n為正整數，則最后一行的語句頻度在最壞情況下是（）。[南京理工大學考研真題]

A．D（n）

B．O（nlogn）

C．O（n3）

D．O（n2）

【答案】D查看答案

【解析】這個是冒泡排序，最壞的情況下需要進行1+2+...+n-1次交換，即時間復雜度是O（n2）。

9下列選項中，不能構成折半查找中關鍵字比較序列的是（ 

）。[2015年聯考真題]

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。

10已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進行匹配，第一次出現“失配”（s[i]!＝t[i]）時，i＝j＝5，則下次開始匹配時，i和j的值分別是（）。[2015年聯考真題]

A．i＝1，j＝0

B．i＝5，j＝0

C．i＝5，j＝2

D．i＝6，j＝2

【答案】C查看答案

【解析】模式匹配（KMP）算法對普通的暴力匹配的改進在于：每當匹配過程中匹配失敗時，主串（本題為S）的指針（i）不需要回溯，而是利用已經得到的“部分匹配”的結果將模式串（t）向右“滑動”盡可能遠的一段距離后，繼續進行比較。模式串“滑動”的距離是由模式串（t）本身決定的，即t的子串t[0…j-1]中前綴串和后綴串相等的最長長度。本題中第一次失配i＝5，字串為“abaab”，其相等且最長的前后綴為“ab”，一次下一個j＝2。

11設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用（ 

）最節省時間。[江蘇大學考研真題]

A．帶頭結點的雙循環鏈表

B．單循環鏈表

C．帶尾指針的單循環鏈表

D．單鏈表

【答案】A查看答案

【解析】要快速地在末尾插入元素，需要能立馬得到末尾元素結點，故最好是循環鏈表。要快速地在末尾刪除元素，需要立馬得到末尾元素結點的前繼結點，故最好是雙向鏈表。綜上可見為雙循環鏈表。

12下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是（ 

）。[2015年聯考真題]

A．直接插入排序

B．起泡排序

C．基數排序

D．快速排序

【答案】C查看答案

【解析】C項，基數排序是采用分配和收集實現的，不需要進行關鍵字的比較。ABD三項都依賴關鍵字的比較，不同的初始排列次序下元素移動的次數有很大變化，最好情況元素正序，則不用移動，最壞情況元素反序，則需要移動n（n-1）/2次（n為元素個數）。

13已知小根堆為8，15，10，21，34，16，12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字之間的比較數是（ 

）。[2015年聯考真題]

A．1

B．2

C．3

D．4

【答案】C查看答案

【解析】堆排序中，依次輸出堆頂的最小值，然后重新調整堆，如此反復執行，便得到一個有序序列。本題中，刪除堆頂元素8后將最后一個元素12置于堆頂，然后調整堆：首先與15比較，12小于15，所以不用交換；然后與10比較，因為10小于12，所以交換10和12的位置；調整后12再與16比較，12小于16，調整堆過程結束。因此12共與15、10、16進行了三次比較。

14下面關于線性表的敘述中，錯誤的是哪一個?（）[北方交通大學考研真題]

A．線性表采用順序存儲，必須占用一片連續的存儲單元

B．線性表采用順序存儲，便于進行插入和刪除操作

C．線性表采用鏈接存儲，不必占用一片連續的存儲單元

D．線性表采用鏈接存儲，便于插入和刪除操作

【答案】B查看答案

【解析】順序存儲，插入刪除時會移動大量的元素，效率相對較低。

15希爾排序的組內排序采用的是（ 

）。[2015年聯考真題]

A．直接插入排序

B．折半插入排序

C．快速排序

D．歸并排序

【答案】A查看答案

【解析】希爾排序基本思想是：先將整個待排元素序列按某個增量分割成若干個子序列，在子序列內進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。

16下列程常段的時間復雜度是（）。[2014年聯考真題]

count＝0;

for（k＝1;k<＝n;k*2）

for（j＝1;j<＝n;j+1）

count++;

A．O（log2n）

B．O（n）

C．O（nlog2n）

D．O（n2）

【答案】C查看答案

【解析】外部循環的退出條件是k>n，而對于k，每次循環都執行k＝k*2,所以循環次數為log2n；內部循環的退出條件是j>n,對于j，每次循環都執行j＝j+1，所以每次循環次數為n次。所以此程序段的時間復雜度為O（nlog2n），即選C。

17．若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節省時間。[哈爾濱工業大學考研真題]

A．順序表

B．雙鏈表

C．帶頭結點的雙循環鏈表

D．單循環鏈表

【答案】A查看答案

【解析】線性表采用順序表，便于進行存取任一指定序號的元素；線性表采用鏈表，便于進行插入和刪除操作。但該題是在最后進行插入和刪除運算，所以利用順序表存儲方式最節省時間。

18假設棧初始為空，將中綴表達式轉換為等價后綴表達式的過程中，當掃描到f時，棧中的元素依次是（）[2014年聯考真題]

A．

B． 

C． 

D．

【答案】B查看答案

【解析】中綴表達式轉后綴表達式遵循以下原則：

（1）遇到操作數，直接輸出；

（2）棧為空時，遇到運算符，入棧；

（3）遇到左括號，將其入棧；

（4）遇到右括號，執行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，

左括號不輸出；

（5）遇到其他運算符'+''-''*''/'時，彈出所有優先級大于或等于該運算符的棧頂

元素，然后將該運算符入棧；

（6）最終將棧中的元素依次出棧，輸出。

所以掃描到’/’，入棧‘描到’+’,由于’+’優先級比’/’低，所以將’/’彈出，’+’入棧；掃描到’*’,優先級比’+’高，入棧；掃描到’（‘,入棧;掃描到’-‘,將棧中優先級更高的’*’彈出，‘-’入棧;掃描到’*’,優先級比’-‘高，入棧。所以掃描到f的時候，棧中元素為：

19循環兩列放在一維數組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M-1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（）[2014年聯考真題]

A．隊空：end1＝＝end2；隊滿：end1＝＝（end2+1）modM

B．隊空：end1＝＝end2;隊滿：end2＝＝（end1+1）mod（M-1）

C．隊空：end2＝＝（end1+1）modM;隊滿：end1＝＝（end2+1）modM

D．隊空：end1＝＝（end2+1）modM;隊滿：end2＝＝（end1+1）mod（M-1）

【答案】A查看答案

【解析】在循環隊列中，在少用一個元素空間的前提下，可約定入隊前，測試尾指針在循環意義下加1后是否等于頭指針，若相等，則隊滿。而隊空的條件還是首尾指針是否相等。

20對于雙向循環鏈表，在p指針所指的結點之后插入s指針所指結點的操作應為（）。[北京工業大學考研真題]

A．p->right=s；s->left=p；p->right->left=s；s->right=p->right；

B．p->right=s；p->right->left=s；s->left=p；s->right=p->right；

C．s->left=p；s->right=p->right；p->right=s；P->right->left=s；

D．s->left=p；s->right=p->right；P->right->left=s；P->right=s；

【答案】D查看答案

【解析】先建立好s指向p和p的后繼節點的鏈接，即s->left=p；s->right=p->right；然后建立p的后繼節點指向s的鏈接，即p->right->left=s；最后，斷開p與后繼節點的鏈接，將p指向s，即p->right=s。

21若對如下的二叉樹進行中序線索化，則結點x的左、右線索指向的結點分別是（ 

）。[2014年聯考真題]

A．e,c

B．e,a 

C．d,c

D．b,a

【答案】D查看答案

【解析】此二叉樹的中序遍歷序列為：debxac,由于節點x左右孩子都為空，所有進行中序線索化時，它的左右孩子指針分別指向它的中序遍歷序列的直接前驅結點b和直接后繼結點a，所以選D

22將森林F轉換為對應的二叉樹T，F中葉結點的個數等于（）。[2014年聯考真題]

A．T中葉結點的個數  

B．T中度為1的結點個數

C．T中左孩子指針為空的結點個數

D．T中右孩子指針為空的結點個數

【答案】C查看答案

【解析】森林轉化為對應的二叉樹是‘孩子-兄弟’存儲的，即左孩子指針指向當前結點的孩子結點，右孩子指針指向當前結點的兄弟結點，所以在T中左孩子指針為空則代表它在森林中并沒有孩子即為葉結點。所以選C。

23線性表的順序存儲結構是一種（ 

）。[北京理工大學考研真題]

A．隨機存取的存儲結構

B．順序存取的存儲結構

C．索引存取的存儲結構

D．Hash存取的存儲結構

【答案】A查看答案

【解析】線性表包括順序存儲結構和鏈式存儲結構，順序存儲結構能夠隨機存取表中的元素，但插入和刪除操作較麻煩，鏈式存儲結構不能隨機訪問表中的元素，但是能夠表示元素之間的先后次序，而且插入和刪除操作較容易。

245個字符有如下4種編碼方案，不是前綴編碼的是（）。[2014年聯考真題]

A．01,0000,0001,001,1 

B．011,000,001,010,1

C．000,001,010,011,100 

D．0,100,110,1110,1100

【答案】D查看答案

【解析】在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴。約定左分支表示字符‘0’，右分支表示字符‘1’，則可以用從根結點到葉子結點的路徑上的分支字符串作為該葉子結點字符的編碼。如此得到的編碼必是前綴編碼。D項中，編碼110是編碼1100的前綴，故不符合前綴編碼的定義。

25對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是（ 

）。[2014年聯考真題]

A．3,1,2,4,5,6

 

B．3,1,2,4,6,5

C．3,1,4,2,5,6 

 

D．3,1,4,2,6,5

【答案】D查看答案

【解析】拓撲排序方法如下:

（1）從有向圖中選擇一個沒有前驅（即入度為0）的頂點并且輸出它；

（2）從圖中刪去該頂點,并且刪去從該頂點發出的全部有向邊；

（3）重復上述兩步,直到剩余的網中不再存在沒有前趨的頂點為止。

對于此有向圖進行拓撲排序所有序列為：3,1,4,6,2,5和3,1,4,2,6,5。所以選D

26向一個棧頂指針為h的帶頭結點的鏈棧中插入指針S所指的結點時，應執行（）。[北京理工大學考研真題]

A．h->next=s；

B．s->next=h；

C．s->next=h；h->next=s；

D．s->next=h-next；h->next=s；

【答案】D查看答案

【解析】本題是向一個鏈棧中插入結點，可從頭結點后插入。先將s結點指向第一個頭結點之后的結點之前，再將頭結點指向s結點。

27用哈希（散列）方法處理沖突（碰撞）時可能出現堆積（聚集）現象，下列選項中，會受堆積現象直接影響的是（）。[2014年聯考真題]

A．存儲效率 

B．數列函數

C．裝填（裝載）因子

D．平均查找長度

【答案】D查看答案

【解析】哈希方法沖突會使在查找沖突的關鍵字時，還要根據沖突處理辦法多次比較關鍵字，則直接影響了平均查找長度。

28在一棵具有15個關鍵字的4階B樹中，含關鍵字的結點數最多是（）。[2014年聯考真題]

A．5

B．6 

C．10 

D．15

【答案】D查看答案

【解析】m階B樹非根結點含關鍵字個數┌m/2┐-1<＝j<＝m–1。

4階B樹非根結點含關鍵字1～3個，所以要使關鍵字結點數量最多，那么每個結點只有一個關鍵字，一共有15個關鍵字那么最多有15個含有關鍵字的結點

29表達式a*（b+c）-d的后綴表達式是（）。[南京理工大學考研真題]

A．abcd*+-

B．abc+*d-

C．abc*+d-

D．-+*abcd

【答案】B查看答案

【解析】后綴表達式：在程序語言中，運算符位于兩個操作數后面的表達式。

30用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是（ 

）[2014年聯考真題]

A．2 

B．3

C．4

D．5

【答案】B查看答案

【解析】對于A，增量為2，那么9,4,7,20,15是一組，而它們是無序的，所以A錯誤

對于C，增量為4，那么9,7,15是一組，而它們是無序的，所以C錯誤

對于D，增量為5，那么9,8是一組，降序，1,20是一組，而它們是升序，所以D也錯誤。對于B，分為3組：9,13,20；1,7,23；4,8,15都是升序有序，所以B正確

31下列選項中，不可能是快速排序第2趟排序結果的是（）[2014年聯考真題]

A．2,3,5,4,6,7,9 

B．2,7,5,6,4,3,9 

C．3,2,5,4,7,6,9 

D．4,2,3,5,7,6,9

【答案】C查看答案

【解析】對于快速排序，每一趟都會使一個元素位于有序時的位置，而有序序列為2,3,4,5,6,7,9，與C進行對比，只有9位于它有序的時候的位置，顯然不是第二趟快速排序的結果

32允許對隊列進行的操作有（）。[華中科技大學考研真題]

A．對隊列中的元素排序

B．取出最近進隊的元素

C．在隊頭元素之前插入元素

D．刪除隊頭元素

【答案】D查看答案

【解析】隊列的原則是先進先出，出隊操作應該刪除隊頭元素。

33．已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是（）。[2013年聯考真題]

A．O（n）

B．O（m*n）

C．O（min（m,n））

D．O（max（m,n））

【答案】D查看答案

【解析】m和n是兩個升序鏈表，長度分別為m和n，在合并過程中最壞的情況是兩個鏈表中的元素依次進行比較，比較的次數是m和n中的最大值。

 

34．一個棧的入棧序列為1,2,3,……,n，其出棧序列是P1，P2，P3……Pn。若，則P2＝3，則P3可能取值的個數是（ 

）。[2013年聯考真題]

A．n-3

B．n-2

C．n-1

D．無法確定

【答案】C查看答案

【解析】除了3本身以外,其他的值均可以取到,因此可能取值的個數為n-1。

 

35．對于循環隊列（）。[北京理工大學考研真題]

A．無法判斷隊列是否為空

B．無法判斷隊列是否為滿

C．隊列不可能滿

D．以上說法都不是

【答案】D查看答案

【解析】，循環隊列也會出現隊列滿的情況，并且循環隊列也可以判斷是否為空或滿。至少可以通過兩種方法進行判斷：①另設一個布爾變量來區別隊列是空還是滿；②隊滿時，（rear+1）==font。

 

36．若將關鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結點的個數是（）。[2013年聯考真題]

A．0

B．1

C．2

D．3

【答案】D查看答案

【解析】將圖中給定的關鍵字序列依次插入到平衡樹中，構成的平衡樹如下圖所示,由圖可知平衡因子為0的分支結點為3個葉子結點，故答案為D。

 

37．已知三叉樹T中6個葉結點的權分別是2，3，4，5，6，7，T的帶權（外部）路徑長度最小是（）。[2013年聯考真題]

A．27

B．46

C．54

D．56

【答案】B查看答案

【解析】利用三叉樹的6個葉子結點的權構建最小帶權生成樹，最小的帶權路徑長度為（2+3）*3+（4+5）*2+（6+7）*1＝46

 

38．循環隊列A[0．．m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是（）。[南京理工大學考研真題]

A．（rear-front+m）％m

B．rear-front+1

C．rear-front-1

D．rear-front

【答案】A查看答案

【解析】對于循環隊列，需要深刻理解隊頭（font）和隊尾（rear）的概念，在隊頭進行出隊操作，在隊尾進行進隊操作。rear-front可能為正也可能為負，為正時元素個數=（rear-front）；如果為負則元素的個數=（rear-front+m），所以統一的公式就是（rear-front+m）％m。

 

39．若X是后序線索二叉樹中的葉結點，且X存在左兄弟結點Y，則X的右線索指向的是（）。[2013年聯考真題]

A．X的父結點

B．以Y為根的子樹的最左下結點

C．X的左兄弟結點Y

D．以Y為根的子樹的最右下結點

【答案】A查看答案

【解析】根據后續線索二叉樹的定義，X結點為葉子結點且有左兄弟，那么這個結點為右孩子結點，利用后續遍歷的方式可知X結點的后繼是其父結點，即其右線索指向的是父結點。

 

40．在任意一棵非空二叉排序樹T1中，刪除某結點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關于T1與T3的敘述中，正確的是（）。[2013年聯考真題]

I．若v是T1的葉結點，則T1與T3不同

II．若v是T1的葉結點，則T1與T3相同

III．若v不是T1的葉結點，則T1與T3不同

IV．若v不是T1的葉結點，則T1與T3相同

A．僅I、III

B．僅I、IV

C．僅II、III

D．僅II、IV

【答案】C查看答案

【解析】在一棵二叉排序樹中刪除一個結點后再將此結點插入到二叉排序樹中，如果刪除的結點是葉子結點那么在插入結點后，后來的二叉排序樹與刪除結點之前相同。如果刪除的結點不是葉子結點，那么再插入這個結點后，后來的二叉樹可能發生變化，不完全相同。

 

41．棧和隊的共同點是（）。[大連理工大學考研真題]

A．都是先進后出

B．都是后進先出

C．只允許在端點處插入和刪除元素

D．沒有共同點

【答案】C查看答案

【解析】棧和隊列的區別是棧是先進后出的數據結構，隊列是先進先出的數據結構，棧和隊列的共同點是都只能在端點處插入和刪除元素。

 

42．設圖的鄰接矩陣A如下所示,各頂點的度依次是（）。[2013年聯考真題]

A．1，2，1，2

B．2，2，1，1

C．3，4，2，3

D．4，4，2，2

【答案】C查看答案

【解析】當圖用鄰接矩陣存儲時，各頂點的度是矩陣中此結點對應的橫行和縱列非零元素之和。

 

43．若對如下無向圖進行遍歷，則下列選項中，不是廣度優先遍歷序列的是（）。[2013年聯考真題]

A．h，c，a，b，d，e，g，f

B．e，a，f，g，b，h，c，d

C．d，b，c，a，h，e，f，g

D．a，b，c，d，h，e，f，g

【答案】D查看答案

【解析】根據廣度優先遍歷的定義，可知ABC三項都為廣度優先遍歷，而D項是深度優先遍歷而不是廣度優先遍歷，故答案為D。

 

44．執行（）操作時，需要使用隊列做輔助存儲空間。[華中科技大學考研真題]

A．查找哈希（Hash）表

B．廣度優先搜索網

C．前序（根）遍歷二叉樹

D．深度優先搜索網

【答案】B查看答案

【解析】查找哈希表不需要輔助存儲空間，前序遍歷二叉樹和深度優先搜索網需要使用棧做輔助存儲空間，廣度優先搜索樹需要隊列做輔助存儲空間。

 

45．下列AOE網表示一項包含8個活動的工程。通過同時加快若干進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（ ）。[2013年聯考真題]

A．c和e

B．d和e

C．f和d

D．f和h

【答案】C查看答案

【解析】根據AOE網的定義可知，同時縮短幾條關鍵路徑上的活動時間，可以縮短整個工期。

 

46．在一株高度為2的5階B樹中，所含關鍵字的個數最少是（）。[2013年聯考真題]

A．5

B．7

C．8

D．14

【答案】A查看答案

【解析】根據B樹的定義可知，跟結點最少含有max（2,（m-1））個關鍵字，高度為2的階B樹最少有（5-1）+1＝5個關鍵字，其中根節點含有（5-1）個關鍵字，第2層結點含有1關鍵字。

 

47．在一棵三元樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（）個。[哈爾濱工業大學考研真題]

A．4

B．5

C．6

D．7

【答案】C查看答案

【解析】設度為0的結點數為x，則度為3的樹總結點數n=度為0的結點數+度為1的結點數+度為2的結點數+度為3的結點數=x+2+1+2=x+5；從每個結點所指向的結點數的和的角度來計算度為3的樹總結點數n=2×3+1×2+2×1+1=11。兩種方法所計算出來的n相等，所以x=6。

 

48．對給定的關鍵字序列110，119，007，911，114，120，122進行基數排序，則第2趟分配收集后得到的關鍵字序列是（）[2013年聯考真題]

A．007，110，119，114，911，120，122

B．007，110，119，114，911，122，120

C．007，110，911，114，119，120，122

D．110，120，911，122，114，007，119

【答案】C查看答案

【解析】基數排序的第1趟排序是按照個位數字來排序的,第2趟排序是按然十位數字的大小進行排序的,故答案是C項。

49求整數n（n≥0）階乘的算法如下，其時間復雜度是（ 

）。[2012年聯考真題]

A．O（log2n）

B．O（n）

C．O（nlog2n）

D．O（n2）

【答案】B查看答案

【解析】設fact（n）的運行時間函數是T（n）。

該函數中語句①的運行時間是0（1），語句②的運行時間是T（n-1）+O（1），其中O（1）為乘法運算的時間。

因此，當n≤1時，T（n）-0（1）；當n>1時，T（n）＝T（n-1）+O（1）。則，T（n）＝O（1）+T（n-1）

＝2×O（1）+T（n-2）＝（n-1）×O（1）+T（1）＝n×O（1）

＝O（n）

即fact（n）的時間復雜度為O（n）。

50設森林F中有三棵樹，第一、第二、第三棵樹的結點個數分別為M1、M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是（ 

）。[北方交通大學考研真題]

A．M1

B．M1+M2

C．M3

D．M2+M3

【答案】D查看答案

【解析】森林轉換成二叉樹的原則：將第一棵樹的根結點作為根結點，所有結點的第一個左孩子作為左孩子，下一個兄弟結點作為右孩子，其它樹作為第一棵樹的右孩子。所以森林F對應的二叉樹根結點的右子樹上的結點個數是除第一棵樹外其他所有樹的結點總數。即M2+M3。

51已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。將中綴表達式a+b-a*（（c+d）／e-f）+g轉換為等價的后綴表達式ab+acd+e／f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符。若棧初始時為空，則轉換過程中同時保存在棧中的操作符的最大個數是（）。[2012年聯考真題]

A．5

B．7

C．8

D．11

【答案】A查看答案

【解析】基本思想是：采用運算符棧是為了比較運算符的優先級，所有運算符必須進棧。只將大于棧頂元素優先級的運算符直接進棧，否則需要退棧棧頂運算符（先出棧的運算符先計算，同優先級的運算符在棧中的先計算）。表達式a+b-a*（（c+d）／e-f）+g產生后綴表達式的過程如下表所列：

通過上表可以看出，顯然轉換過程中同時保存在棧中的操作符的最大個數是5。

52若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結點的孩子結點（）。[2012年聯考真題]

A．只有e

B．有e、b

C．有e、c

D．無法確定

【答案】A查看答案

【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，其中a為這棵二叉樹的根結點，接下來，在前序遍歷的第二個結點為e，而后序遍歷的倒數第二個結點為e，說明a的孩子結點只有e。

53有關二叉樹下列說法正確的是（ 

）。[南京理工大學考研真題]

A．二叉樹的度為2

B．一棵二叉樹的度可以小于2

C．二叉樹中至少有一個結點的度為2

D．二叉樹中任何一個結點的度都為2

【答案】B查看答案

【解析】樹的度=MAX（結點1的度,結點2的度,結點3的度,...,結點n的度）。二叉樹之所以稱為二叉樹，是因為二叉樹中節點的度最大是2，也可以小于2。

54若平衡二叉樹的高度為6，且所有非葉結點的平衡因子均為1，則該平衡二叉樹的結點總數為（）。[2012年聯考真題]

A．12

B．20

C．32

D．33

【答案】B查看答案

【解析】本題題目的實際問題是，具有6層結點的平衡二叉樹含有最少的結點數是多少。Nh表示深度為h的平衡二叉樹中含有的最少結點數，有N0＝0，N1＝1，N2＝2……Nh＝Nh-1+Nh-2+1

由此可得N5＝20。對應的平衡二叉樹如下圖所示。

55．對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優先遍歷，其算法時間復雜度是（）。[2012年聯考真題]

A．0（n）

B．0（e）

C．O（n+e）

D．O（n×e）

【答案】C查看答案

【解析】遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。當用二維數組表示鄰接矩陣圖的存儲結構時，查找每個頂點的鄰接點所需時間為O（n2），其中n為圖中頂點數。而當以鄰接表作圖的存儲結構時，找鄰接點所需時間為0（e），其中e為無向圖中邊的數或有向圖中弧的數。由此，當以鄰接表作存儲結構時，深度優先搜索遍歷圖的時間復雜度為O（n+e）。即可得出正確答案。

56深度為h的滿m叉樹的第k層有（）個結點（1≤k≤h）。[北京航空航天大學考研真題]

A．mk-1

B．mk-1

C．mh-1

D．mh-1

【答案】A查看答案

【解析】滿m叉樹第k層必有mk-1個結點。

57若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結論是（）。[2012年聯考真題]

A．存在，且唯一

B．存在，且不唯一不唯一

C．存在，可能不唯一

D．無法確定是否存在

【答案】C查看答案

【解析】圖的基本應用——拓撲排序，用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，說明該圖為有向無環圖，所以其拓撲序列存在，但不一定唯一，如圖的鄰接矩陣為，則存在兩個拓撲序列。

58有向帶權圖如題58圖所示，若采用迪杰斯特拉（Dijkstra）算法求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，后續得到的其余各最短路徑的目標頂點依次是（）。[2012年聯考真題]

題58圖有向帶權圖

A．d,e,f

B．e，d，f

C．f，d，e

D．f，e，d

【答案】C查看答案

【解析】本題主要考查Dijkstra算法的思想和解題步驟。題目執行算法過程中各步的狀態如下表所示。

執行Dijkstra算法過程中各步的狀態表，故后續目標頂點依次為f,d,e。

59．將有關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度為（ 

）。[南京理工大學考研真題]

A．4

B．5

C．6

D．7

【答案】C查看答案

【解析】若二叉樹中最多只有最下面兩層的結點的度數可以小于2，并且最下面一層的葉結點都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。具有n個（n>0）結點的完全二叉樹的高度為log2（n+1）或log2n+1；由完全二叉樹類推到完全三叉樹可知，n個結點的完全三叉樹的高度為log3（n+1）或log3n+1。

60下列關于最小生成樹的敘述中，正確的是（）。[2012年聯考真題]

Ⅰ．最小生成樹的代價唯一 Ⅱ．所有權值最小的邊一定會出現在所有的最小生成樹中 Ⅲ．使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同 

Ⅳ．使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

【答案】A查看答案

【解析】當圖中存在相同權值的邊時，其最小生成樹可能是不唯一的，但最小生成樹的代價一定是相同的，所以說法Ⅰ正確。從n個頂點的連通圖中選取n-1條權值最小的邊可能構成回路，所以說法Ⅱ錯誤。當某個頂點有權值相同的邊，使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹并不一定相同，所以說法Ⅲ錯誤。當最小生成樹不唯一時，使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹可能相同，也可能不同，所以說法Ⅳ錯誤。由此可得出正確答案。

61設有一棵3階B樹，如題61圖所示。刪除關鍵字78得到一棵新B樹，其最右葉結點所含的關鍵字是（）。[2012年聯考真題]

題61圖3階B樹圖

A．60

B．60，62

C．62，65

D．65

【答案】D查看答案

【解析】本題主要考查B樹刪除操作。即被刪關鍵字所在的結點中的關鍵字個數等于［m/2］-1，而與該結點相鄰的右兄弟（或左兄弟）結點中的關鍵字數目大于［m/2］-1，則需將其兄弟結點中最小（或最大）的關鍵字上移至雙親結點中，而將雙親結點中小于（或大于）且緊靠該上移關鍵字的關鍵字下移至被刪關鍵字所在結點中。題目中刪除關鍵字78得到一棵新B樹如下，其最右葉結點所含的關鍵字是65。

62排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結束時都至少能夠確定一個元素最終位置的方法是（）。[2012年聯考真題]

Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排V．二路歸并排序A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

【答案】A查看答案

【解析】其中簡單選擇排序、堆排序屬于選擇類排序，每一趟排序結束時將確定最大（或最小）關鍵字所在的位置。快速排序每一趟排序結束時將確定基準關鍵字所在的位置。希爾排序、二路歸并排序每一趟排序結束時不一定能確定一個元素的最終位置。

63對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左、右孩子的編號，在同一結點的左、右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）次序的遍歷實現編號。[北京理工大學考研真題]

A．前序

B．中序

C．后序

D．從根開始按層次遍歷

【答案】C查看答案

【解析】為了滿足條件：每個結點的編號大于其左、右孩子的編號，同一結點的左孩子的編號小于其右孩子的編號，訪問結點的次序必須是左一右一根，所以采用后序遍歷。

64某二叉樹中序序列為A，B，C，D，E，F，G，后序序列為B，D，C，A，F，G，E則前序序列是（）。[南京理工大學考研真題]

A．E，G，F，A，C，D，B

B．E，A，C，B，D，G，F

C．E，A，G，C，F，B，D

D．上面的都不對

【答案】B查看答案

【解析】由后序序列可知E為根結點，再由中序遍歷結果知A，B，C，D，為E的左孩子，且A為B，C，D的父結點，到此可排除A項，按照這種邏輯依次推理，便可得出結果。

65對同一待排序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）。[2012年聯考真題]

A．排序的總趟數

B．元素的移動次數

C．使用輔助空間的數量

D．元素之間的比較次數

【答案】D查看答案

【解析】折半插入排序所需附加存儲空間和直接插入排序相同，從時間上比較，折半插入排序僅減少了關鍵字間的比較次數，而記錄的移動次數不變。折半插入排序的時間復雜度仍為O（n2）,所以兩者之間的不同只可能是元素之間的比較次數。

66設n是描述問題規模的非負整數，下面程序片段的時間復雜度是（）。[2011年聯考真題]

x＝2：

while（x<n/2）

x＝2×x；

A．O（log2n）

B．O（n）

C．O（nlog2n）

D．O（n2） 

【答案】A查看答案

【解析】其中，以基本的原操作重復執行的次數作為算法的時間度量。題目中的基本運算是語句x＝2×x，設其執行時間為T（n），則有2T（n）<n/2即T（n）<log2（n/2）＝O（log2n）。

67在二叉樹結點的前序序列、中序序列和后序序列中，所有葉結點的先后順序（）。[北方交通大學考研真題]

A．都不相同

B．完全相同

C．前序和中序相同，而與后序不同

D．中序和后序相同，而與前序不同

【答案】B查看答案

【解析】前序遍歷形式為：根左右。中序遍歷形式為：左根右。后序遍歷形式為：左右根。可知左右相對順序不變，葉結點都是在左右位置上，因此，他們的相對位置不變。

68元素a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是（）。[2011年聯考真題]

A．3

B．4

C．5

D．6

【答案】B查看答案

【解析】d首先出棧后的狀態如下圖所示。

此時可有以下4種操作：

（1）e進棧后出棧，出棧序列為decba。

（2）c出棧，e進棧后出棧，出棧序列為dceba。

（3）cb出棧，e進棧后出棧，出棧序列為dcbea。

（4）cba出棧，e進棧后出棧，出棧序列為dcbae。

69已知循環隊列存儲在一維數組A[0…n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（ 

）。[2011年聯考真題]

A．0，0

B．0，n-1

C．n-1，0

D．n-1，n-1

【答案】B查看答案

【解析】題目要求隊列非空時front和rear分別指向隊頭元素和隊尾元素，若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則此時front和rear的值都為0。由于進隊操作要執行（rear+1）%n，則初始時front的值為0、rear的值為n-1。

70設F是一個森林，B是由F變換得到的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（）個。[西安電子科技大學考研真題]

A．n-1

B．n

C．n+1

D．n+2

【答案】C查看答案

【解析】B中右指針為空的點，就是森林中的每棵樹中的每個非終端結點最右邊那個子樹的根結點，也可以說是每棵樹的每一棵子樹的每一層的最后一個結點。每個非終端結點都有一個最右邊的結點（X），轉化成二叉樹的時候，X就是那個右指針為空的點，所以F中N個非終端結點就對應著N個B中右指針為空的結點。

還有一個結點，就是森林中最右邊那個樹的根結點（T），如果這個森林只有一棵樹，這個結點就是這棵樹的根結點，這個結點不是任何結點的最右邊的孩子，但是轉化成二叉樹B的時候，他的右指針可以是為空。所以答案的n+1。

71若一棵完全二叉樹有768個結點，則該二叉樹中葉結點的個數是（ 

）。[2011年聯考真題]

A．257

B．258

C．384

D．385

【答案】C查看答案

【解析】由n＝n0+n1+n2和n0＝n2+1可知，n＝2n0-1+n1，即2n0-1+n1＝768，顯然n1＝1，2n0＝768，則n0＝384，所以二叉樹的葉結點個數是384。還可以根據完全二叉樹的另一個性質：最后一個分支結點的序號為[768/2]，故非葉子結點數為384，而葉子結點的個數為768-384＝384。（［x］表示不大于x的最大整數，比如［3.14］＝3）。

72若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為l，2，3，4和4，3，2，1，則該二叉樹的中序遍歷序列不會是（）。[2011年聯考真題]

A．1，2，3，4

B．2，3，4，1

C．3，2，4，1

D．4，3，2，1

【答案】C查看答案

【解析】題目中的二叉樹的先序序列和后序序列正好相反，這樣的二叉樹每層只有一個結點。該二叉樹的形態如下圖所示。

從左至右，這8棵二叉樹的中序序列分別為：

（1）4，3，2，1，

（2）3，4，2，1

（3）2，4，3，1

（4）2，3，4，1

（5）1，4，3，2

（6）1，3，4，2

（7）1，2，4，3

（8）1，2，3，4

顯然選項C的中序序列不會出現。

73一個有n個結點的圖，最少有（）個連通分量，最多有（）個連通分量。[北京郵電大學考研真題]

A．0

B．1

C．n-l

D．n

【答案】1B 2D查看答案

【解析】若圖G中任意兩個頂點都是連通的，則稱圖G為連通圖。無向圖中的極大連通子圖稱為圖的連通分量。圖的連通分量的個數小于或等于圖的結點數。當圖的各個結點彼此都沒有邊相連時，連通分量數最大為n。當圖的各個結點彼此都與邊相連時，連通分量數最小為1。

74已知一棵有2011個結點的樹，其葉結點個數為ll6，該樹對應的二叉樹中無右孩子的結點個數是（）。[2011年聯考真題]

A．115

B．116

C．1895

D．1896

【答案】D查看答案

【解析】每個非終端結點轉換成二叉樹后都對應一個無右孩子的結點（因為一個非終端結點至少有一個孩子結點，其最右邊的孩子結點轉換成二叉樹后一定沒有右孩子），另外，樹根結點轉換成二叉樹后也沒有右孩子。題目中樹的總結點數是2011，葉結點個數是116，則非終端結點個數是2011-116＝1895，則該樹對應的二叉樹中無右孩子的結點個數是1895+1＝1896。

75對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列是（）。[2011年聯考真題]

A．95，22，91，24，94，71

B．92，20，91，34，88，35

C．21，89，77，29，36，38

D．12，25，71，68，33，34

【答案】A查看答案

【解析】各選項對應的查找過程如下圖所示，從中看到BCD三項對應的查找樹都是二叉排序樹，只有A項對應的查找樹不是一棵二叉排序樹，因為在以91為根的左子樹中出現了比91大的結點94。

76用鄰接表存儲圖所用的空間大小＿＿。[北京交通大學考研真題]

A．與圖的頂點數和邊數都有關

B．只與圖的邊數有關

C．只與圖的頂點數有關

D．與邊數的平方有關

【答案】A查看答案

【解析】所謂鄰接表就是對圖G中的每個頂點vi建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊，這個單鏈表就稱為頂點vi的邊表。因此鄰接表既存儲圖的所有頂點，也存儲頂點之間的邊的信息。

77下列關于圖的敘述中，正確的是（）。[2011年聯考真題]

Ⅰ．回路是簡單路徑

Ⅱ．存儲稀疏圖，用鄰接矩陣比鄰接表更省空間

Ⅲ．若有向圖中存在拓撲序列，則該圖不存在回路

A．僅Ⅱ

B．僅Ⅰ、Ⅱ

C．僅Ⅲ

D．僅Ⅰ、Ⅲ

【答案】C查看答案

【解析】第一個頂點和最后一個頂點相同的路徑稱為回路；序列中頂點不重復出現的路徑稱為簡單路徑；回路顯然不是簡單路徑，所以選項Ⅰ錯誤。稀疏圖用鄰接表表示比鄰接矩陣節省存儲空間，稠密圖適合用鄰接矩陣的存儲表示，所以選項Ⅱ錯誤。利用拓撲排序算法可以判斷圖中是否存在回路，即在拓撲排序輸出結束后所余下的頂點都有前驅，則說明了只得到了部分頂點的拓撲有序序列，圖中存在回路。所以選項Ⅲ正確。

78為提高散列（Hash）表的查找效率，可以采用的正確措施是（ 

）。[2011年聯考真題]

Ⅰ．增大裝填（載）因子

Ⅱ．設計沖突（碰撞）少的散列函數

Ⅲ．處理沖突（碰撞）時避免產生聚集（堆積）現象

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅱ

D．僅Ⅱ、Ⅲ

【答案】D查看答案

【解析】散列表的查找效率（比較次數）取決于：散列函數、處理沖突的方法和散列表的裝填因子α。α標志著散列表的裝滿程度，通常情況下，α越小，發生沖突的可能性越小；反之，α越大，表示已填入的記錄越多，再填入記錄時，發生沖突的可能性越大。因此選項Ⅰ錯誤，越是增大裝填因子，發生沖突的可能性就越大，查找效率也越低。選項Ⅱ正確。選項Ⅲ正確。采用合適的處理沖突的方法避免產生聚集現象，也將提高查找效率。例如，用拉鏈法解決沖突時不存在聚集現象，用線性探測法解決沖突時易引起聚集現象。

79無向圖G=（V，E），其中：V={a，b，c，d，e，f）}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f,d）,（e，d），對該圖進行深度優先遍歷，得到的頂點序列正確的是（）。[南京理工大學考研真題]

A．a，b，e，c，d，f

B．a，c，f,e，b，d

C．a，e，b，c，f,d 

D．a，e，d，f，c，b

【答案】D查看答案

【解析】圖的深度優先遍歷過程是：從圖中某個初始頇點v出發，首先訪問初始頂點v，然后選擇一個與頂點v相鄰且沒被訪問過的頂點u為初始頂點。再從u出發進行深度優先搜索，直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。

根據E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}可知各頂點之間的鄰接關系。依據上面的原則遍歷，得出遍歷順序a，e，d，f，c，b。

80為實現快速排序算法，待排序序列宜采用的存儲方式是（）。[2011年聯考真題]

A．順序存儲

B．散列存儲

C．鏈式存儲

D．索引存儲

【答案】A查看答案

【解析】對絕大部分內部排序而言，只適用于順序存儲結構，快速排序在排序過程中，既要從后向前查找，也要從前向后查找，因此宜采用順序存儲。

81已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，將其再調整為大根堆，調整過程中元素之間進行的比較次數是（）。[2011年聯考真題]

A．1

B．2

C．4

D．5

【答案】B查看答案

【解析】對堆插入或刪除一個元素，有可能不滿足堆的性質，堆被破壞，需要調整為新堆。

（1）為原堆，

（2）為插入18后，

（3）比較10與18，交換后，

（4）比較25與18，不交換，即為調整后的新的大根堆。

因此調整過程中元素之間進行的比較次數為2。

82在有向圖的鄰接表存儲結構中，頂點v在鏈表中出現的次數是（）。[北京理工大學考研真題]

A．頂點v的度

B．頂點v的出度

C．頂點v的入度

D．依附于頂點v的邊數

【答案】B查看答案

【解析】在有向圖中，第j個鏈表中的結點個數只是頂點vi的出度，為求入度，必須遍歷整個鄰接表。因此頂點v在鏈表中出現的次數是頂點v的入度。

83若元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續三次進行退棧操作，則不可能得到的出棧序列是（）。[2010年聯考真題]

A．d，c，e，b，f，a

B．c，b，d，a，e，f

C．b，c，a，e，f，d

D．a，f，e，d，c，b

【答案】D查看答案

【解析】4個選項所給序列的進、出棧操作序列分別為：

選項A．Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

選項B．Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

選項C．Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

選項D．Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

按照題目要求，不允許連續三次進行退棧操作，所以D項所給序列為不可能得到的出棧順序。

84某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，元素a，b，c，d，e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是（）。[2010年聯考真題]

A．b，a，c，d，e

B．d，b，a，c，e

C．d，b，c，a，e

D．e，c，b，a，d

【答案】C查看答案

【解析】根據題意，隊列兩端都可以輸入數據元素，但是只能在一端輸出數據元素，這種隊列為輸出受限的雙端隊列。本題解題方法分別判斷每個選項如何入隊和出隊，從而得出不可能的情況。

假設L代表從左端入隊，R代表從右端入隊，出隊都是從左端L出。四個選項所給序列的進隊操作序列分別為：

選項A．aL（或aR），bL，cR，dR，eR

選項B．aL（或aR），bL，cR，dL，eR

選項C．不可能出現

選項D．aL（或aR），bL，cL，dR，eL

85已知有向圖G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓撲序列是（）。[北京航空航天大學考研真題]

A．V1，V3，V4，V6，V2，V5，V7

B．V1，V3，V2，V6，V4，V5，V7

C．V1，V3，V5，V2，V6，V7

D．V1、V2，V5，V3，V4，V6，V7

【答案】A查看答案

【解析】設G=（V，E）是一個具有n個頂點的有向圖，V中頂點序列v1，v2，…，vn，能被稱為拓撲序列的條件：若<vi，vj>是圖中的邊（即從頂點vi到vj有一條路徑），則在序列中頂點vi必須排在頂點vj之前。根據上面拓撲序列的定義，就可以得出G的拓撲序列是V1，V3，V4，V5，V2，V5．V7。

86下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）。[2010年聯考真題]

【答案】D查看答案

【解析】線索二叉樹利用二叉鏈表的空鏈域來存放結點的前驅和后繼信息，解題思路較簡單。題中所給二叉樹的后序序列為dbca。結點d無前驅和左子樹，左鏈域空，無右子樹，右鏈域指向其后繼結點b；結點b無左子樹，左鏈域指向其前驅結點d；結點c無左子樹，左鏈域指向其前驅結點b，無右子樹，右鏈域指向其后繼結點a。所以正確選項為D。

87在下圖所示的平衡二叉樹中，插入關鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是（）。[2010年聯考真題]

A．13、48

B．24、48

C．24、53

D．24、90

【答案】C查看答案

【解析】題目中，插入48以后，樹根結點的平衡因子由-1變為-2，失去平衡。這屬于RL（先右后左）型平衡旋轉，需做兩次（先右旋后左旋轉）旋轉操作。過程如下圖所示：

顯然，在調整后的新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是24，53。

88在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是（）。[南京理工大學考研真題]

A．G中有弧<Vi，Vj> 

 

B．G中有一條從Vi到Vj的路徑

C．G中沒有弧<Vi，Vj）

D．G中有一條從Vj到Vi的路徑

【答案】D查看答案

【解析】若想實現圖的一個拓撲排序，需要滿足的一個條件為：若頂點A在序列中排在頂點B的前面，則在圖中不存在從頂點B到頂點A的路徑。又因為若G中有一條從Vj到Vi的路徑，則在拓撲序列中Vi不可能在Vj前。

89在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點個數是（）。[2010年聯考真題]

A．41

B．82

C．113

D．122

【答案】B查看答案

【解析】根據二叉樹的性質3的推廣公式：N0＝l+N2+2N3+…+（m-1）Nm可直接在將數據帶入公式，即N0＝l+N2+2N3+3N4＝l+1×1+2×10+3×20＝82。樹T的葉子結點的個數是82。如果考生不能熟練掌握二叉樹的性質3的推廣公式，得到本題的正確答案將費時費力。因此，需要熟練掌握二叉樹的性質及推廣。

90對n（n≥2）個權值均不相同的字符構成哈夫曼樹。下列關于該哈夫曼樹的敘述中，錯誤的是（）。[2010年聯考真題]

A．該樹一定是一棵完全二叉樹

B．樹中一定沒有度為1的結點

C．樹中兩個權值最小的結點一定是兄弟結點

D．樹中任一非葉結點的權值一定不小于下一層任一結點的權值

【答案】A查看答案

【解析】哈夫曼樹為帶權路徑長度最小的二叉樹，但不一定是完全二叉樹，A項錯誤；哈夫曼樹中沒有度為1的結點，B項正確；構造哈夫曼樹時，最先選取兩個權值最小的結點作為左右子樹構造一棵新的二叉樹，C項正確；哈夫曼樹中任一非葉結點P的權值為其左右子樹根結點權值之和，其權值不小于其左右子樹根結點的權值，在與結點P的左右子樹根結點處于同一層的結點中，若存在權值大于結點P權值的結點Q，那么結點Q與其兄弟結點中權值較小的一個應該與結點P作為左右子樹構造新的二叉樹，由此可知，哈夫曼樹中任一非葉結點的權值一定不小于下一層任一結點的權值。

91在下述幾種樹中，（）可以表示靜態查找表。[中國科學技術大學考研真題]

A．次優查找樹

B．二叉排序樹

C．B-樹

D．平衡二叉樹

【答案】A查看答案

【解析】在有序序列的查找中，如果各個元素的查找概率都是一樣的，那么二分查找是最快的查找算法，但是如果查找元素的查找概率是不一樣的，那么用二分查找就不一定是最快的查找方法。基于這種查找元素概率不想等的有序序列，可以通過構造最優二叉樹的方法，使得該二叉樹的帶權路徑長度最小，這樣的二叉樹的構造代價是非常大的，所以用一種近似的算法，構造次優查找樹，該樹的帶權路徑長度近似達到最小

92若無向圖G＝（V，E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數最少是（）。[2010年聯考真題]

A．6

B．15

C．16

D．21

【答案】C查看答案

【解析】要保證無向圖G在任何情況下都是連通的，即任意變動圖G中的邊，G始終保持連通。首先需要圖G的任意6個結點構成完全連通子圖G1，需n（n-l）／2＝6×（6—1）／2＝15條邊，然后再添加一條邊將第7個結點與G1連接起來，共需l6條邊。本題非常容易錯誤地選擇選項A，主要原因是對“保證圖G在任何情況下都是連通的”的理解，分析選項A，在圖G中，具有7個頂點6條邊并不能保證其一定是連通圖，即有n-1條邊的圖不一定是連通圖。分析選項D，圖G有7個頂點21條邊，那么圖G一定是無向完全圖，無向完全圖能保證其在任何情況下都是連通的，但是這不符合題目中所需邊數最少的要求。

93對下圖進行拓撲排序，可以得到不同的拓撲序列的個數是（）。[2010年聯考真題]

A．4

B．3

C．2

D．1

【答案】B查看答案

【解析】拓撲排序的步驟為：

（1）在有向圖中選一個沒有前驅的頂點并且輸出它；

（2）從圖中刪除該頂點和以它為尾的弧。重復上述兩步，直至全部頂點均已輸出。由于沒有前驅的頂點可能不唯一，所以拓撲排序的結果也不唯一。題中所給圖有三個不同的拓撲排序序列，分別為abced，abecd，aebcd。

94如果要求一個線性表既能較快地查找，又能適應動態變化的要求，可以采用下列哪一種查找方法。[北京交通大學考研真題]

A．分塊

B．順序

C．折半

D．哈希

【答案】A查看答案

【解析】分塊查找，把線形表分成若干塊，塊間是順序存儲的，所以查找速度較快。在每一塊中的數據元素的存儲順序是任意的，所以便于線性表的動態變化。

95．已知一個長度為l6的順序表L，其元素按關鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關鍵字的比較次數最多是（）。[2010年聯考真題]

A．4

B．5

C．6

D．7

【答案】B查看答案

【解析】折半查找法在查找不成功時和給定值進行比較的關