最強計算機專業(yè)碩士考研資料：計算機專業(yè)基礎考研

真題(120頁)

一、配套數(shù)據結構考研題庫

一、選擇題

1.已矢口程序如下:

intS<intn.)

{

return(n<=0)?0:s(n-1)-n：

)

voidmain《)

{

cout?S(1);

)

程序運行時使用棧來保^調用過程的信息，自棧尊觸頂保存的信息依次對應的

是()。［2015年聯(lián)考真題］

A.main()->S(1)->S(0)

B.S(0)->S(1)->main()

C.main()->S(0)->S(1)

D.S(l)->S(0)->main()

【答案】A—@

【解析】函數(shù)S(intn)是一個遞歸函數(shù)：①當實際參數(shù)小于等于零時

則返回0,并終止遞歸：②當實際參數(shù)大于零時則遞歸調用S(n-1),并將S

(n-1)的結果加上n作為返回值。程序從main()函數(shù)開始，首先調用main

()函數(shù)；在main()函數(shù)中調用S(l)函數(shù)時，將main()函數(shù)的上下文

儒殍?展中，并進入函數(shù)S(1);由于函數(shù)S(1)的實際參數(shù)大于零，需要調

用s(0),故將S(1)函數(shù)的上下文保格I」棧中，進入S(0);在S(0)中，

實際參數(shù)小于等于零，遞歸終止。

2.算法分析的目的是(1［北京理工大學考研真題］

A.找出數(shù)據結構的合理性

B.研究算法中的輸入和輸出的關系

C.分析算法的效率以求改進

D.分析算法的易懂性和文檔性

【答案】C~~@

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

3.先序序列為a,b,c,d的不同二叉樹的個數(shù)是()。［2015年聯(lián)考真

題］

A.13

B.14

C.15

D.16

【答案】B—@

【解析】二叉樹的先序遍歷定義為：若二叉樹為空，則空操作；否則，

訪問根節(jié)點，然后先序遍歷左子樹，最后先序遍歷右子樹。本題中，結點a為二

叉樹的根節(jié)點，左右子樹的先序遍歷可能存在下面四種情況：①左子樹為空，

bed為右子樹；②b為左子樹，cd為右子樹；③be為左子樹,d為右子樹；④

bed為左子樹，右子樹為空。然后將左右子樹繼續(xù)分解，如第①種情況的右子樹

先序遍歷(bed)可能有：a.左子樹為空，右子樹為cd;b.左子樹為c,右

子樹為d;c.左子樹為cd,右子樹為空。按照這種方法繼續(xù)分解左右子樹，直

到不能再分解為止，可得第①和④種情況各包含5種不同情況，第②和③種情況

各包含2種情況,因此總共有14種不同的二叉樹。

4.下列選項給出的是從根分別到達兩個葉結點路徑上的權值序列，能屬于同一

棵哈夫曼樹的是（）o［2015年聯(lián)考真題］

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~~@

【解析】哈夫曼樹是帝權路徑長度最短的二叉樹。由根結點出發(fā)到兩個

葉子結點路徑中，第二個被訪問的兩個結點的權值要么相等，要么和為根結點的

權值，故B項錯誤。同理，通過第三個被訪問的結點排除A項。C項，由兩條

路徑可推出三個葉子結點的權值分別是：3、10和11,而根據哈夫曼樹的定義

可知，權值為3的結點應該和權值為10的結點結合，故C項錯誤。D項，反推

出有四個葉子結點，權值分別為：5、5、6和8,滿足哈夫曼樹的條件。

5.當輸入非法錯誤時，一個"好”的算法會進行適當處理，而不會產生難以理

解的輸出結果C這稱為算法的（［中山大學考研真題］

A.性

B.健》姆

C.正確性

D.有窮性

【答案】B—@

【解析】健壯性是指當輸入數(shù)據非法時，算法能作適當?shù)奶幚聿⒆鞒龇?/p>

應，而不應死機或輸出異常結果。

6.現(xiàn)在有一顆無重復關鍵字的平衡二叉樹(AVL樹),對其進行中序遍歷可得

到一個降序序列。下列關于該平衡二叉樹的敘述中，正確的是()0［2015

年聯(lián)考真題］

A,根節(jié)點的度f為2

B.樹中最小元素一定是葉節(jié)點

C.最后插入的元素T是葉節(jié)點

D.樹中最大元素一^是無左子樹

【答案】D—@

【解析】二叉樹的中序遍歷定義是“若二叉樹為空，則空操作；否則：

①中序遍歷左子樹；②訪問根節(jié)點；③中序遍歷右子樹"。A項錯誤，當樹中僅

有一個或者兩個結點時，根節(jié)點的度就可能不為2;B項錯誤，樹中最小元素是

中序遍歷時最后訪問的節(jié)結點,當沒有右子樹時，最后訪問的結點是根結點；C

項錯誤，當最后插入的詢破壞樹的平衡后,樹會說弗整，百弱中恒結點；

D項正確，由中序遍歷的特點可知，左子樹的值大于根結點，所以最大元素T

沒有左子樹。

7.設葩圖G=(V,E)/］^V={V0,VI,V2,V3},皿E={<V0,Vl>z

<V0,V2>,<V0,V3>z<V1,V3>},若從頂點VO開始對圖進行深度優(yōu)先遍歷,

則可能得到的不同遍歷序列例是()。［2015年聯(lián)考真題］

A.2

B.3

【答案】D~~@

【解析】根據題意知有向圖的結構如圖所示。深度優(yōu)先遍歷的特點是盡

可能先對縱深方向進行搜索，所以可能得到的不同遍歷序列分別是：①V0-V2

一VLV3；②V0-V2—V3-VL③V0-VLV3-V2；④V0-V3-V2-V1；

⑤VO—V3-V1TV2。

8.程序段

FOR1：=n-lDOWNTO1DO

FORj:=1TO1DO

IFA[J1>ALI-1]

THENMI與ALT]對換J

其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是()。［南京理工

大學考研真題］

A.D(n)

B.0(nlogn)

C.0(na)

D.0(n2)

【答案】D

【解析】這個是冒泡排序，最壞的情況下需要進行l(wèi)+2+...+n-l次交換,

即時間復雜度是0(爪)。

9.下列選項中，不能構兩斤半查找中關鍵字1:徽序列的是(）。[2015年

聯(lián)考真題]

A.500,200,450,180

B.500,450,200,180

C.180,500,200,450

D.180,200,500,450

【答案】A~~@

【解析】折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步

縮小范圍直到找到或找不到該記錄為【匕折半杳找的關鍵字序列滿足：對每一個

巖蜉，麗面的所有蝌宅拓域舒叼才/疑鍵為渚大會節(jié)賤

鍵字。A項錯誤,第三次匕俄的關鍵字為450,說明待查關鍵字位于200~450

間，所以第四次匕徽時不會遇SJ關鍵字180c

10.已知^串S為"abaabaabacacaabaabcc",模式串t為"abaabc",

采用KMP算法進行匹配，第一次出現(xiàn)"失配"(s[i]!=t[i])時，i=j=5,則下

次開始匹配時，i和j的值分別是()o[2015年聯(lián)考真題]

A.i=lJ=0

B.i=5,j=0

C.i=5J=2

D.i=6,j=2

【答案】C~~@

【解析】模式匹配(KMP)算法對普通的暴力匹配的改進在于：每當匹

配過程中匹配失敗時，主串(本題為S)的指針(i)不需要回溯，而是利用日軍

得到的“部分匹配〃的結果將模式串（t）向右"滑動"盡可能遠的一段距離后，

繼續(xù)進行比較。模式串"滑動"的距離是由模式串（t）本身決定的，即t的子

串中前綴串和后綴串相等的最長長度。本題中第一次失配i=5,字串為

"abaab",其相等且最長的前后綴為〃ab",一次下一個j=2。

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

最節(jié)省時間。［江蘇大學考研真題］

A,帶頭結點的雙循環(huán)鏈表

B.單循環(huán)鏈表

C.帶尾指針的單循環(huán)鏈表

D.單鏈表

【答案】A~~@

【解析】要快速地在末尾插入元素，需要能立馬得到末尾元素結點，故

最好是循環(huán)鏈表。要快速地在天尾刪除元素，需要立馬得到末尾元素結點的前繼

結點，故最好是雙向鏈表。綜上可見為雙循環(huán)鏈表。

12.笛腓序命坤元蔚弟動繩斕］瘦字6創(chuàng)始膨坎就冷娓（）。

［2015年聯(lián)考真題］

A.哥施入排序

B.起泡排序

C.基物非序

D.快遴昨

【答案】C—@

【解析】C項，基數(shù)排序是采用分酹口收集實現(xiàn)的，不需要進行關鍵字

的比較0ABD三項都依賴關鍵字的比較，不同的初始排列次序下元素移動的次

數(shù)有很大變化，最好情況元素正序，則不用移動，最壞情況元素反序,則需要移

動n(n-l)/2次(n為元素個數(shù))。

13.已知/」沖艮堆為8,15,10,21,34,16,12,刪除關鍵字8之后需重建

堆，在此過程中，關鍵字之間的匕俄數(shù)是()0［2015年聯(lián)考真題］

A.1

B.2

C.3

D.4

【答案】C~~@

【解析】堆排序中，依次輸出堆頂?shù)淖钚≈?，然后重新調整堆，如此反

復執(zhí)行，便得到一個有序序列。本題中，刪除堆頂元素8后將最后素12

置于堆頂，然后調整堆：首先與15匕俄,12小于15,所以不用交換;然后與

10匕戢，因為10小于12,所以交換10和12的位置;調整后12再與16比

較，12小于16,調整堆過程結束。因此12共與15、10、16進行了三次比較。

14.下面關于線性表穗述中，錯誤的是明f?()［北方交通大學考研真

題］

A.線性表采用JI酹存儲，必須占用一片連續(xù)的存儲單元

B.線性表采用111酹存儲，便于進行插入和刪除操作

C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

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

【答案】B~~@

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

15.希帝F序的組內排序采用的是()o［2015年聯(lián)考真題］

A.直踴內非序

B.折半插入排序

C.快圉非序

D.歸用^序

【答案】A—@

【解析】希爾排序基本思想是：先將整個待排元素序列按某個增量分割

靖產呼，詢揚1內通逾舜閃非序，然粉縮懈*再說亍排序,

待整個序^中的元素基本有序(增量足夠小)時，再對全體元素a行一次直攜g

入排序。

16.下列程常段的時間復雜度是()。［2014年聯(lián)考真題］

count=0;

for(k=l;k<=n;k*2)

for(j=l;j<=n;j+l)

count++;

A.0(log2n)

B.O(n)

C.0(nlog2n)

D.0(n2)

【答案】C—@

【解析】外部循環(huán)的退出條件是k>n,而對于k,每次循環(huán)都執(zhí)行k二

k*2,所以循環(huán)次數(shù)為log2n;內部循環(huán)的退出條件是j>n,對于j,每次循環(huán)都執(zhí)

行j刁+1,所以每知腳熠為n次。所Wt程段的時間蛭江0(nlog2n),

即選C°

17.若某線性表最常用的操作是存取任一指定序號的元薪口在最后進行插入和

刪除運算，則利用()存儲方式最節(jié)省時間。［哈爾濱工業(yè)大學考研真題］

A.怫表

B.雙鏈表

C.帶頭結點的雙循環(huán)鏈表

D.單循環(huán)鏈表

【答案】A—@

【解析】線性表采用順序表，便于進行存取任一指定序號的元素；線性

表采用鏈表，便于進行插入和刪除操作。但該題是在最后進行插入和刪除運算，

所以利用順序表存儲方式最節(jié)省時間。

18.假設棧初始為空，將中綴表達式“白-Cd-°*門/g轉換為等價后

綴表達式的過程中，當掃描到f時，棧中的元素依次是()［2014年聯(lián)考真

題］

A.+I?~

B.+L

c./+(，_*

D./+-率

【答案】B—@

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

(1)遇SJ操作數(shù)，直接輸出；

(2)棧為空時，遇到運算符，入棧；

(3)遇到用舌號，將其入棧；

(4)屢I」右括號,執(zhí)行出棧操作,并將出棧的元素輸出,直到彈出棧的是由舌

號

右舌號不輸出；

(5)遇到其他運算符'+“/*"/'時，彈出所有優(yōu)先級大于或等于該運算符的棧頂

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

(6)最終將棧中的元素依次出棧，輸出。

所以掃描到',入棧‘描到'+',由于'+‘優(yōu)先級比'/'低，所以將‘/'

彈出，'+'入棧；掃描到‘川，優(yōu)先級比'+'高，入棧；掃描到‘(’,入棧；

掃描到‘?‘，將棧中優(yōu)先級更高的'彈出，入棧;掃描到‘,優(yōu)先級比’

-'高，入棧。所以掃描到f的時候，棧中元素為：+(一”

19.循環(huán)兩列放在一維數(shù)組中，endl指向隊頭元素，end2指向隊

尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容

納M-1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是()

[2014年聯(lián)考真題]

A.隊空：endl==end2;隊滿：endl==(end2+l)modM

B.隊空：endl==end2;隊滿:end2==(endl+1)mod(M-1)

C.:end2==(endl+1)modM;隊帶:endl==(end2+l)modM

D.:endl==(end2+l)modM;隊茜:end2==(endl+1)mod

（M-l）

【答案】A—@

【解析】在循環(huán)隊列中，在少用一個元素空間的前提下，可約定入隊前,

測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等，則隊滿。而隊空的條

件還是首尾指針是否相等。

20.對于雙向循環(huán)鏈表，在p指針所指的結點之后插入s指針所指結點的操作

應為（）。［北京工業(yè)大學考研真題］

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的后繼節(jié)點的鏈接，即s->left=p;

s->right=p->right;標建立p的骨節(jié)凝向s的雌，即

p->right->left=s;就WS妾，將p指向s,EPp->right=s?

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

別是（）o［2014年聯(lián)考真題］

A.e,c

B.e,a

C.d,c

D.b,a

【答案】D~~@

【解析】此二叉樹的中序遍歷序列為：debxac,由于節(jié)點x左右孩子都

為空,所有進行中序線索化時,它的左6孩招晶分期旨向它的中序遍歷J朝」的

直接前9降點b和直接后繼結點a,所以選D

22.將森林F粉奐為對應的二叉樹T,F中葉結點的個數(shù)等于()。［2014

年聯(lián)考真題］

A.T中葉結點的介數(shù)

B.T中度為1的結點個數(shù)

C.T中左孩子指針為空的結點個數(shù)

D.T中右孩不旨針為空的結點個數(shù)

【答案】C~~@

【解析】森林轉化為對應的二叉樹是‘孩子-兄弟’存儲的，即左孩子指

針指向當前結點的孩子結點，右孩子指針指向當前結點的兄弟結點，所以在T

中左孩子指針為空則代表它在森林中并沒有孩子即為葉結點。所以選Co

23.線性表的III好存儲結構含-種（）。［北京理工大學考研真題］

A.隨機存取的存儲結構

BJ酹存取的存儲結構

C.索引存取的存儲結構

D.Hash存取的存儲結構

【答案】A—@

【解析】線性表包括順序存儲結構和鏈式存儲結構，順序存儲結構能夠

隨機存取表中的元素，但插入和刪腐果作較麻煩，鏈式存儲S構不能隨機訪問表

中的元素，但是能夠表示元素之間的先后次序，而且插入和刪除操作較容易。

24.5個字符有如下4種編碼方案，不是前綴編碼的是（）o［2014年聯(lián)考

真題］

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’，右分支表示字符T,則可以用從根結

點到葉子結點的路徑上的分支字符串作為該葉子結點字符的編碼。如此得到的編

碼必是前綴編碼。D項中，編碼110是編碼1100的前綴，故不符合前綴編碼

的定義。

25.減口下目標6靖向圖》行描忖非序，僻咱蟠卜筋阿育患()o［2014

年聯(lián)考真題］

A.3,124,5,6

B.3,124,6,5

C.3,1,425,6

D.3,1,426,5

【答案】D—@

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

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

(2)從圖中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊；

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

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

26.向T棧頂指針為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結

點指向第T頭結點之后的結點之前，再將頭結點指向s結點。

27.用哈希（散列）方法處理中突（蒯1）時可能出現(xiàn)堆積（聚集）現(xiàn)象，下

列選項中，會受堆積現(xiàn)象直接影響的是（）。［2014年聯(lián)考真題］

A.存儲效率

B.數(shù)列函數(shù)

C.裝填（裝載）因子

D.平均查找長度

【答案】D~~@

【解析】哈希方法沖突會使在查找沖突的關鍵字時，還要根據沖突處理

辦法多次比較關鍵字，則直接影響了平均查找長度。

28.在海具有15個關鍵字的4階B樹中，含卷字的結微略是（）。

［2014年聯(lián)考真題］

A.5

B.6

C.10

D.15

【答案】D~~@

【解析】階極俳根結點含關鍵字個數(shù)

mBrm/2i-1<=j<=m—L

4階B樹胴賭點含關鍵字1~3個，所以要使關鍵字結點數(shù)量最多，那么每個

結點只有一個關鍵字，一共有15個關鍵翼陷最多有15個含有關鍵字的結點

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

A.abcd*+-

B.abc+*d-

C.abc*+d-

D.-+*abcd

【答案】B—@

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

達式。

30.用希狎脖方法對f麴居序列進行排序時,若第1趟排錠果為

9,1,4,13,7,8,20,23,15,則該題非序采用的增量（間隔）可能是（）［2014

年聯(lián)考真題］

A.2

B.3

C.4

D.5

【答案】B—@

【解析】對于A,t獻g2,刃以9,4,7,20,15含-組，而它H遑無序的，

所以A錯誤

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

對于D,增量為5,那么9,81-組，降序，1,20是一組,而它們是升序,所以

D也錯誤。對于B,分為3組：9,13,20;1723;4,8,15都是升序有序，所以B

正確

31.下列選項中,不可能是快速排序第2腳E序結果的是()［2014年聯(lián)

考真題］

A.2354679

B.2,7,5,6,439

C.3,254,7,6,9

D.4,235,7,6,9

【答案】C~~@

【解析】對于快速排序，每一趟都會使一個元素位于有序時的位置，而

有序序列為2345679,與C進行對比，只有9位于它有序的時僚^位置，顯

然不是第R快潮脖的結果

32.允許對隊列進行的操作有()。［華中科技大學考研真題］

A.對隊列中的元素排序

B.取出最近進隊的元素

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

D.刪除隊頭元素

【答案】D—@

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

33.9曬個長^別為m和n的升序峰，若將它H哈并為f長度為m+n

的降序鏈表，則最壞情況下的時間復雜度是()o［2013年聯(lián)考真題］

A.O(n)

B.0(m*n)

C.O(min(mzn))

D.O(max(m,n))

【答案】D

【解析】m和n是兩個升序鏈表，長度分別為m和n,在合并過程中最

壞的H況是兩個觸中的元素依次進行t檄，的效勺次數(shù)是m和n中的最大值。

34.f棧的入棧序列為123n,其出棧序列是Pi,P2,P3……Pno若,

貝I」P2二3,貝uP3可能取值的個數(shù)是()。［2013年聯(lián)考真題］

A.n-3

B.n-2

C.n-1

D.無法確定

【答案】C

【解析】除了3本身以外，其他的值均可以取m因此可能取值的個數(shù)為

n-lo

35.對于循環(huán)隊列()o［北京理工大學考研真題］

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

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

C.隊列不可能滿

D.處說法者壞是

【答案】D—@

【解析工循環(huán)隊列也會出現(xiàn)隊列滿的情況，并且循環(huán)隊列也可以判斷

是否為空或滿。至少可以通過兩種方法進行判斷：①另設一個布爾變量來區(qū)別隊

列是空還是滿；②隊滿時，（rear+1）=二font。

36.若將關鍵字1,2,3,4,5,6,7依次插入到初始為空的平衡二叉樹T中，

則T中平衡因子為0的分支結點的個數(shù)是（）0[2013年聯(lián)考真題]

A.0

B.1

C.2

D.3

【答案】D

【解析】將圖中給定的關鍵字序列依次插入到平衡樹中，構成的平衡樹

如下圖所示,由圖可知平衡因子為0的分支結點為3個葉子結點,故答案為Do

37.已知三叉樹T中6個葉結點的權分別是2,3,4,5,6,7,T的帶權（外

部）路徑長度最小是（）,[2013年聯(lián)考真題]

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉樹的6個葉子結點的權構建最小帶權生成樹,最小的

帶口SKJt為(2+3)*3+(4+5)*2+(6+7)*1=46

38.循環(huán)隊列A［0..m-1］存放其元素值，用front和「ea「分別表示隊頭和隊

尾,則當前隊列中的元素數(shù)是()。［南京理工大學考研真題］

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

【答案】A

【解析】對于循環(huán)隊列，需要深刻理解隊頭(font)和隊尾(rear)的

概念，在隊頭進行出隊操作，在隊尾進行進隊操作。rear-front可能為正也可能

為負，為正時元素個數(shù)二(rear-front);如果為負則元素的個數(shù)二

(rear-front+m),所以統(tǒng)一的公式就是(rear-front+m)%m。

39.若X是后序線索二叉樹中的葉結點，且X存在左兄弟結點Y,則X的右線

索指向的是()o［2013年聯(lián)考真題］

A.X的父結點

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

C.X的左兄弟結點Y

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

【答案】A

【解析】根據后續(xù)線索二叉樹的定義，X結點為葉子結點且有左兄弟，

那么這個結點為右孩子結點，利用后續(xù)遍歷的方式可知X結點的后繼^父結

點，即其右線索指向的是父結點。

40.在任意一棵非空二叉排序樹T1中,刪除某結點v之后形成二叉排序樹T2,

再將v插入T2形成二叉排序樹T3o下列關于T1與T3的敘述中，正確的是

()o[2013年聯(lián)考真題]

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

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

山.若v不是T1的葉結點，則T1與T3不同

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

A.僅I、m

B.僅I、IV

C.僅II、III

D.僅II、IV

【答案】C

【解析】在一棵二叉排序樹中刪除一個結點后再將此結點插入到二叉排

序樹中，如果刪除的結點是葉子結翩陷在插入結點后，后來的二叉排序樹與刪

除結點之前相同。如果刪除的結點不是葉子結點，那么再插入這個結點后，后來

的二叉樹可能發(fā)生變化，不完全相同。

41.窗口隊的共同點是()。［大連理工大學考研真題］

A.都是先進后出

B.都是后進先出

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

D.沒有共同點

【答案】C~~@

【解析】棧和隊列的區(qū)別是棧是先進后出的數(shù)據結構，隊列是先進先出

的數(shù)據結構，棧和隊列的共同點是都只能在端點處插入和刪除元素。

42.設圖的令吩妾矩陣A如下所示，各頂點的度依次是()o［2013年聯(lián)考真

題］

0101'

0011

0100

1000

A.1,2,1,2

B.2,2,1,1

C.3,4,2,3

D.4,4,2,2

【答案】C

【解析】當圖用鄰接矩陣存儲時，各頂點的度是矩陣中此結點對應的橫

行和縱列非零元素之和。

43.若對如下無向圖進行遍歷,則下列選項中，不是廣度優(yōu)先遍歷序列的是

（）o［2013年聯(lián)考真題］

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

【解析】根據廣度優(yōu)先遍歷的定義，可知ABC三項都為廣度優(yōu)先遍歷,

而D項是深度優(yōu)先遍歷而不是廣度優(yōu)先遍歷,故答案為D。

44.執(zhí)行（）操作時，需要使用隊列做輔助存儲空間。［華中科技大學考研

真題］

A.查找哈希（Hash）表

B.廣度優(yōu)先搜索網

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

D.深度優(yōu)雌索網

【答案】B

【解析】查找哈希表不需要輔助存儲空間，前序遍歷二叉樹和深度優(yōu)先

搜索網需要使用棧做輔助存儲空間，廣度優(yōu)先搜索樹需要隊列做輔助存儲空間。

45.下列AOE網表亦■項包含8個活動的工程。通過同時加快若干進度可以縮

短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（）o

[2013年聯(lián)考真題]

A.c和e

B.d和e

C.f和d

D.f和h

【答案】C

【解汨木郵AOE網的定義可知，同時縮短幾條為徑上的活時間,

可以縮短整個工期。

46.在一株高度為2的5階B樹中，所含關鍵字的個數(shù)最少是（工［2013

年聯(lián)考真題］

A.5

B.7

C.8

D.14

【答案】A

【解析】根據B樹的定義可知,跟結點最少含有max（2,（m?l））個

瀉蜉，高孰）2的階B樹期有（5-1）+1=5^^^,其樹群點含有（5-1）

個關鍵字,第2題點含有1關鍵字。

47.在一棵三元樹中度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1

的結點數(shù)為2個，則度為0的結點數(shù)為（）個。［哈爾濱工業(yè)大學考研真題］

A.4

B.5

C.6

D.7

【答案】C~~@

【解析】設度為0的結點數(shù)為x,則度為3的樹總結點數(shù)n二度為0的

結點數(shù)十度為1的結點數(shù)十度為2的結點數(shù)十度為3的結點數(shù)=x+2+l+2=x+5;

從每個結點所指向的結點數(shù)的和的角度來計算度為3的樹總結點數(shù)n=2x3+lx

2+2x1+1=11。兩種方法所計算出來的n相等,所以x=6。

48.對給定的頰字筋I」110,119,007,911,114,120,122進行基軸F

序,則第2趟分配收集后得到的關鍵字序列是()［2013年聯(lián)考真題］

A.007,110,119,114,911,120z122

B.007,110,119,114,911,122,120

C.007z110,911,114,119,120,122

D.110z120,911,122,114,007,119

【答案】C

【解析】基數(shù)ft序的第1趟排序是按照個位數(shù)字時^序的第2趟排序是

按然十位數(shù)字的大小進行排序的，故答案是C項。

49.求整數(shù)n(n>0)階乘的算法如下，其時間復雜度是()。［2012年聯(lián)

考真題］

int{act(intn)

<if(n<=l)return1；

returnn*fact(n-1九

_____)1_____

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】B—@

【解析】設fact(n)的運行時間函數(shù)是T(n)。

intfact(intn)(

if(nV=l)return1;//語句

returnn*fact(n—1);〃語句

_____________________________________________

該函數(shù)中語句①的運行時間是0(1),語句②的運行時間是T(n-1)+0(1),

其中0(1)為乘法運算的時間。

因此，當nwl時，T(n)-0(l);當n>l時，T(n)=T(n-1)+0(l)o

則，T(n)=0(1)+T(n?l)

=2x0(1)+T(n-2)=(n-1)x0(1)+T(1)=nx0(1)

=0(n)

即fact(n)的時間復雜度為0(n)0

50.設森林F中有三棵樹，第一、第二、第三棵樹的結點個數(shù)分別為Ml、M2

和M3O與森林F對應的二叉樹根^點的右子樹上的結點個數(shù)是(［北方

交通大學考研真題］

A.Ml

B.M1+M2

C.M3

D.M2+M3

【答案】D~~@

【解析】森林轉換成二叉樹的原則：將第一棵樹的根結點作為根結點，

所有結點的第f磁子作為左孩子，下T兄弟結點作為右孩子，其它樹作為

第一棵樹的右孩子。所以森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是除

第一棵樹外其他所有樹的結點總數(shù)。即M2+M3O

51.已知操作符包括中、'，、"、‘/'、‘(‘和‘)’。將中綴

表達式a+?a*((c+d)/af)+g轉換為等價的后綴表達式ab+acd+e/f，-g+

時，用棧來存放暫時還不能確定運算次序的操作符。若棧初始時為空，則轉換過

程中同時保存在棧中的操作符的最大分數(shù)是()o[2012年聯(lián)考真題]

A.5

B.7

C.8

D.11

【答案】A~~@

【解析】基本思想是：采用運算符棧是為了比較運算符的優(yōu)先級，所有

運算符必須進棧。只將大于棧頂元素優(yōu)先級的運算符直接進棧，否則需要退棧棧

頂運算符(先出棧的運算符先計算，同優(yōu)先級的運算符在棧中的先計算)。表達

式a+b-a*((c+d)/e-f)+g產生后綴表達式的過程如下表所列：

當前享存運算存枝內容后始表達式說明

2

?進棧

b一ab

'?/與柱項元素的優(yōu)先級相同，W

,■ab-

出棧，“小進棧

a,abr

*"的優(yōu)先級大于我頂元素“J，貝產■'

.■.abr

理棧

(-?(ab-a對它之前后的運算符起隔離作用

(-?((ab-a"（"對它之前后的運算符起隔離作用

-*((ab-ac

—-?(<*ab-ac進錢

d??<《+ab-acd

與其配對的左任號及其前所有運尊后出

)，（abicd-

枝

/-?(/ab*acd*進柱

e-?(/ab-acdr

“?”的優(yōu)先級小于棧質元素“/”，則

-??(-ab*acd-e/

出校，“?”進餞

fJ(?ab-acd-e^f

與其配對的左話號及其前斫有運算符出

)ab-acd*e/f-

錢

“一”的優(yōu)先級小于柱頂元素"""，則"■’

,ab-acd*e/f-*

出錢

與棧頂元素“」的優(yōu)先級相同，犀

ab-acd-e/f-*-出棧，?進棧

gab-aed-e/f-*-g

ab-acdr/f?"■尸全部出柱

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

52.若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,

d,e,a,則根結點的孩子結點（）o[2012年聯(lián)考真題]

A.只有e

B.有e、b

C.有e、c

D.無法確定

【答案】A—@

【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a,e,b,d,c,

后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹的根結點,接下來，在

前序遍歷的第二個結點為e,而后序遍歷的倒數(shù)第二個結點為e,說明a的孩子

結點只有6o

53.有關二叉樹下列說法正確的是（［南京理工大學考研真題］

A.二叉樹的度為2

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

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

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

【答案】B—@

【解析】樹的度=MAX（結點1的度結點2的度結點3的度，…,結點n

的度）。二叉樹之所以稱為二叉樹，是因為二叉樹中節(jié)點的度最大是2,也可以

小于2。

54.若平衡二叉樹的高度為6,且所有非葉結點的平衡因子均為1,則該平衡二

叉樹的結點總數(shù)為（k［2012年聯(lián)考真題］

A.12

B.20

C.32

D.33

【答案】B~~@

【解析】本題題目的實際問題是，具有6層結點的平衡二叉樹含有最少

的結點數(shù)是多少。Nh表示深度為h的平衡二叉樹中含有的最少結點數(shù)，有No

二0,電=2……Nh=Nh.1+Nh.2+l

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

55.對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷,其算

法時間復雜度是()o[2012年聯(lián)考真題]

A.0(n)

B.0(e)

C.O(n+e)

D.O(nxe)

【答案】C~~@

【解析】遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗

費的時間則取決于所采用的存儲結構。當用二維數(shù)組表示鄰接矩陣圖的存儲結構

時，查找每個頂點的鄰接點所需時間為O(山)，其中n為圖口頂點數(shù)。而當

以鄰接表作圖的存儲結構時，戈令展點所需時間為0(e),其中e為無向圖中

邊的數(shù)或有向圖中弧的數(shù)。由此，當以鄰接表作存儲結構時，深度優(yōu)先搜索遍歷

圖的時間復雜度為o（n+e）o即可得出正確答案。

56.深度為h的滿m叉樹的第k層有（）個結點（lwkwh）。［北京航空

航天大學考研真題］

A.mk-i

B.mk-1

C.mh-i

D.mh-1

【答案】A~~@

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

57.若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該

圖拓撲序列的結論是（）c［2012年聯(lián)考真題］

A.存在，且唯一

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

C.存在，可能不唯一

D.無海角謖否詼

【答案】C~~@

【解析】圖的基本應用——拓撲排序，用鄰接矩陣存儲有向圖，矩陣中主對角

線以下的元素均為零，說明該圖為有向秘圖,所以郵撲序"府在，但不F

o11

000

唯一，如圖的令展矩陣為〔。。小，則存在兩個拓撲序列。

58.有向帶權圖如題58圖所示，若采用迪杰斯特拉(Dijkstra)算法求從源點

a到其他各頂點的最短路徑，則得到的第一級可珞徑的目標頂點是b,第二條

最短路徑的目標頂點是c,后續(xù)得到的其余各最短路徑的目標頂點依次是

)。［2012年聯(lián)考真題］

A.d,e,f

B.e,d,f

C.f,dze

D.f,e,d

【答案】C—@

【解析】本題主要考查Dijkstra算法的思想和解題步驟。題目執(zhí)行算法

過程中各步的狀態(tài)如下表所示,

執(zhí)行Dijkstra算法過程中各步的狀態(tài)表，故后續(xù)目標頂點依次為f,d,e。

點

趟煤、bcdef集合s

25

k=l(a,b)

(a,b)(a,c)

k=2(a,b,c)(a,b,d){a,b,c}

4(a,b,c,

k=3(a,b,d)(a,b,e){a,b,c,f)

f)

k=4(a,b,d)<a,b,c,e){a」b>c>3d)

k=5<a,b,d,e)(a,b,c,f,d,e)

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

高度為（）。［南京理工大學考研真題］

A.4

B.5

C.6

D.7

【答案】C~~@

【解析】若二叉樹中最多只有最下面兩層的結點的度數(shù)可以小于2,并且最下面

一層的逐點都依姑例在該層最左邊的位■上，則這樣的二叉樹稱為完全二叉

樹。具有n個（n>0）結點的完全二叉樹的高度為lbg2（n+1）或IQg2n+JL;

由完全二叉樹類推到完全三叉樹可知，n個結點的完全三叉樹的高度為l（pg3

（n+1）威［log3n>lo

60.下列關于最小生成樹的敘述中，正確的是（）o［2012年聯(lián)考真題］

I.最小生成樹的代價唯一H.所有權值最小的邊一定會出現(xiàn)在所有的最小生

成樹中HI.使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相

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

同

A.僅I

B.僅n

c.僅工、m

D.僅n、iv

【答案】A—@

【解析】當圖中存在相同權值的邊時，其最小生成樹可能是不唯一的，

但最小生成樹的代價一定是相同的，所以說法I正確。從n個頂點的連通圖中

選取n-1條權值最小的邊可能構成回路，所以說法II錯誤。當某個頂點有權值

相同的邊，使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹并不一

定相同，所以說法m錯誤。當最小生成樹不唯一時，使用普里姆算法和克魯斯卡

爾（Kruskal）算法得到的最小生成樹可能相同，也可能不同，所以說法IV錯誤。

由此可得出正確答案。

61.設有一棵3階B樹，如題61圖所示。刪除關鍵字78得至!）一棵新B樹，其

最右葉結點所含的關鍵字是（r[2012年聯(lián)考真題]

題61圖3階B樹圖

A.60

B.60,62

C.62,65

D.65

【答案】D~~@

【解析】本題主要考查B