計(jì)算機(jī)專業(yè)基礎(chǔ)考研真題

最強(qiáng)計(jì)算機(jī)專業(yè)碩士考研資料：計(jì)算機(jī)專業(yè)基礎(chǔ)考研

真題(120頁(yè))

一、配套數(shù)據(jù)結(jié)構(gòu)考研題庫(kù)

一、選擇題

1.已矢口程序如下:

intS<intn.)

{

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

)

voidmain《)

{

cout?S(1);

)

程序運(yùn)行時(shí)使用棧來(lái)保^調(diào)用過(guò)程的信息，自棧尊觸頂保存的信息依次對(duì)應(yīng)的

是()。［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)是一個(gè)遞歸函數(shù)：①當(dāng)實(shí)際參數(shù)小于等于零時(shí)

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

(n-1)的結(jié)果加上n作為返回值。程序從main()函數(shù)開(kāi)始，首先調(diào)用main

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

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

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

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

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

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)

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

【答案】C~~@

【解析】分析算法為的就是能對(duì)算法有更多、更好的改進(jìn)。

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

題］

A.13

B.14

C.15

D.16

【答案】B—@

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

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

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

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

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

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

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

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

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

4.下列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉結(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一

棵哈夫曼樹(shù)的是（）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~~@

【解析】哈夫曼樹(shù)是帝權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。由根結(jié)點(diǎn)出發(fā)到兩個(gè)

葉子結(jié)點(diǎn)路徑中，第二個(gè)被訪問(wèn)的兩個(gè)結(jié)點(diǎn)的權(quán)值要么相等，要么和為根結(jié)點(diǎn)的

權(quán)值，故B項(xiàng)錯(cuò)誤。同理，通過(guò)第三個(gè)被訪問(wèn)的結(jié)點(diǎn)排除A項(xiàng)。C項(xiàng)，由兩條

路徑可推出三個(gè)葉子結(jié)點(diǎn)的權(quán)值分別是：3、10和11,而根據(jù)哈夫曼樹(shù)的定義

可知，權(quán)值為3的結(jié)點(diǎn)應(yīng)該和權(quán)值為10的結(jié)點(diǎn)結(jié)合，故C項(xiàng)錯(cuò)誤。D項(xiàng)，反推

出有四個(gè)葉子結(jié)點(diǎn)，權(quán)值分別為：5、5、6和8,滿足哈夫曼樹(shù)的條件。

5.當(dāng)輸入非法錯(cuò)誤時(shí)，一個(gè)"好”的算法會(huì)進(jìn)行適當(dāng)處理，而不會(huì)產(chǎn)生難以理

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

A.性

B.健》姆

C.正確性

D.有窮性

【答案】B—@

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

應(yīng)，而不應(yīng)死機(jī)或輸出異常結(jié)果。

6.現(xiàn)在有一顆無(wú)重復(fù)關(guān)鍵字的平衡二叉樹(shù)(AVL樹(shù)),對(duì)其進(jìn)行中序遍歷可得

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

年聯(lián)考真題］

A,根節(jié)點(diǎn)的度f(wàn)為2

B.樹(shù)中最小元素一定是葉節(jié)點(diǎn)

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

D.樹(shù)中最大元素一^是無(wú)左子樹(shù)

【答案】D—@

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

①中序遍歷左子樹(shù)；②訪問(wèn)根節(jié)點(diǎn)；③中序遍歷右子樹(shù)"。A項(xiàng)錯(cuò)誤，當(dāng)樹(shù)中僅

有一個(gè)或者兩個(gè)結(jié)點(diǎn)時(shí)，根節(jié)點(diǎn)的度就可能不為2;B項(xiàng)錯(cuò)誤，樹(shù)中最小元素是

中序遍歷時(shí)最后訪問(wèn)的節(jié)結(jié)點(diǎn),當(dāng)沒(méi)有右子樹(shù)時(shí)，最后訪問(wèn)的結(jié)點(diǎn)是根結(jié)點(diǎn)；C

項(xiàng)錯(cuò)誤，當(dāng)最后插入的詢破壞樹(shù)的平衡后,樹(shù)會(huì)說(shuō)弗整，百弱中恒結(jié)點(diǎn)；

D項(xiàng)正確，由中序遍歷的特點(diǎn)可知，左子樹(shù)的值大于根結(jié)點(diǎn)，所以最大元素T

沒(méi)有左子樹(shù)。

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

<V0,V2>,<V0,V3>z<V1,V3>},若從頂點(diǎn)VO開(kāi)始對(duì)圖進(jìn)行深度優(yōu)先遍歷,

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

A.2

B.3

【答案】D~~@

【解析】根據(jù)題意知有向圖的結(jié)構(gòu)如圖所示。深度優(yōu)先遍歷的特點(diǎn)是盡

可能先對(duì)縱深方向進(jìn)行搜索，所以可能得到的不同遍歷序列分別是：①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]對(duì)換J

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

大學(xué)考研真題］

A.D(n)

B.0(nlogn)

C.0(na)

D.0(n2)

【答案】D

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

即時(shí)間復(fù)雜度是0(爪)。

9.下列選項(xiàng)中，不能構(gòu)兩斤半查找中關(guān)鍵字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~~@

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

縮小范圍直到找到或找不到該記錄為【匕折半杳找的關(guān)鍵字序列滿足：對(duì)每一個(gè)

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

鍵字。A項(xiàng)錯(cuò)誤,第三次匕俄的關(guān)鍵字為450,說(shuō)明待查關(guān)鍵字位于200~450

間，所以第四次匕徽時(shí)不會(huì)遇SJ關(guān)鍵字180c

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

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

次開(kāi)始匹配時(shí)，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)算法對(duì)普通的暴力匹配的改進(jìn)在于：每當(dāng)匹

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

得到的“部分匹配〃的結(jié)果將模式串（t）向右"滑動(dòng)"盡可能遠(yuǎn)的一段距離后，

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

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

"abaab",其相等且最長(zhǎng)的前后綴為〃ab",一次下一個(gè)j=2。

11.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）

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

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

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

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

D.單鏈表

【答案】A~~@

【解析】要快速地在末尾插入元素，需要能立馬得到末尾元素結(jié)點(diǎn)，故

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

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

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

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

A.哥施入排序

B.起泡排序

C.基物非序

D.快遴昨

【答案】C—@

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

的比較0ABD三項(xiàng)都依賴關(guān)鍵字的比較，不同的初始排列次序下元素移動(dòng)的次

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

動(dòng)n(n-l)/2次(n為元素個(gè)數(shù))。

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

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

A.1

B.2

C.3

D.4

【答案】C~~@

【解析】堆排序中，依次輸出堆頂?shù)淖钚≈担缓笾匦抡{(diào)整堆，如此反

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

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

10匕戢，因?yàn)?0小于12,所以交換10和12的位置;調(diào)整后12再與16比

較，12小于16,調(diào)整堆過(guò)程結(jié)束。因此12共與15、10、16進(jìn)行了三次比較。

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

題］

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

B.線性表采用111酹存儲(chǔ)，便于進(jìn)行插入和刪除操作

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

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

【答案】B~~@

【解析】順序存儲(chǔ)，插入刪除時(shí)會(huì)移動(dòng)大量的元素，效率相對(duì)較低。

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

A.直踴內(nèi)非序

B.折半插入排序

C.快圉非序

D.歸用^序

【答案】A—@

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

靖產(chǎn)呼，詢揚(yáng)1內(nèi)通逾舜閃非序，然粉縮懈*再說(shuō)亍排序,

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

入排序。

16.下列程常段的時(shí)間復(fù)雜度是()。［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,而對(duì)于k,每次循環(huán)都執(zhí)行k二

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

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

即選C°

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

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

A.怫表

B.雙鏈表

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

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

【答案】A—@

【解析】線性表采用順序表，便于進(jìn)行存取任一指定序號(hào)的元素；線性

表采用鏈表，便于進(jìn)行插入和刪除操作。但該題是在最后進(jìn)行插入和刪除運(yùn)算，

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

18.假設(shè)棧初始為空，將中綴表達(dá)式“白-Cd-°*門(mén)/g轉(zhuǎn)換為等價(jià)后

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

題］

A.+I?~

B.+L

c./+(，_*

D./+-率

【答案】B—@

【解析】中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式遵循以下原則：

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

(2)棧為空時(shí)，遇到運(yùn)算符，入棧；

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

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

號(hào)

右舌號(hào)不輸出；

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

元素，然后將該運(yùn)算符入棧；

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

所以掃描到',入?！璧?+',由于'+‘優(yōu)先級(jí)比'/'低，所以將‘/'

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

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

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

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

尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容

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

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

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

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

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

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

（M-l）

【答案】A—@

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

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

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

20.對(duì)于雙向循環(huán)鏈表，在p指針?biāo)傅慕Y(jié)點(diǎn)之后插入s指針?biāo)附Y(jié)點(diǎn)的操作

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

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é)點(diǎn)的鏈接，即s->left=p;

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

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

21.若對(duì)如下的二叉樹(shù)進(jìn)行中序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分

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

A.e,c

B.e,a

C.d,c

D.b,a

【答案】D~~@

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

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

直接前9降點(diǎn)b和直接后繼結(jié)點(diǎn)a,所以選D

22.將森林F粉奐為對(duì)應(yīng)的二叉樹(shù)T,F中葉結(jié)點(diǎn)的個(gè)數(shù)等于()。［2014

年聯(lián)考真題］

A.T中葉結(jié)點(diǎn)的介數(shù)

B.T中度為1的結(jié)點(diǎn)個(gè)數(shù)

C.T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)

D.T中右孩不旨針為空的結(jié)點(diǎn)個(gè)數(shù)

【答案】C~~@

【解析】森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)是‘孩子-兄弟’存儲(chǔ)的，即左孩子指

針指向當(dāng)前結(jié)點(diǎn)的孩子結(jié)點(diǎn)，右孩子指針指向當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，所以在T

中左孩子指針為空則代表它在森林中并沒(méi)有孩子即為葉結(jié)點(diǎn)。所以選Co

23.線性表的III好存儲(chǔ)結(jié)構(gòu)含-種（）。［北京理工大學(xué)考研真題］

A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)

BJ酹存取的存儲(chǔ)結(jié)構(gòu)

C.索引存取的存儲(chǔ)結(jié)構(gòu)

D.Hash存取的存儲(chǔ)結(jié)構(gòu)

【答案】A—@

【解析】線性表包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)能夠

隨機(jī)存取表中的元素，但插入和刪腐果作較麻煩，鏈?zhǔn)酱鎯?chǔ)S構(gòu)不能隨機(jī)訪問(wèn)表

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

24.5個(gè)字符有如下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—@

【解析】在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼

的前綴。約定左分支表示字符‘0’，右分支表示字符T,則可以用從根結(jié)

點(diǎn)到葉子結(jié)點(diǎn)的路徑上的分支字符串作為該葉子結(jié)點(diǎn)字符的編碼。如此得到的編

碼必是前綴編碼。D項(xiàng)中，編碼110是編碼1100的前綴，故不符合前綴編碼

的定義。

25.減口下目標(biāo)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—@

【解析】拓?fù)渑判蚍椒ㄈ缦拢?/p>

(1)從有向圖中選擇一個(gè)沒(méi)有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它；

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

(3)重復(fù)上述兩步，直到剩余的網(wǎng)中不再存在沒(méi)有前趨的頂點(diǎn)為止。

對(duì)于此有向圖進(jìn)行拓?fù)渑判蛩行蛄袨椋?,14625和3,142,6,5。所以選D

26.向T棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針S所指的結(jié)點(diǎn)時(shí)，曲

行(］［北京理工大學(xué)考研真題］

A.h->next=s;

B.s->next=h;

C.s->next=h;h->next=s;

D.s->next=h-next;h->next=s;

【答案】D—@

【解析】本題是向一個(gè)鏈棧中插入結(jié)點(diǎn)，可從頭結(jié)點(diǎn)后插入。先將s結(jié)

點(diǎn)指向第T頭結(jié)點(diǎn)之后的結(jié)點(diǎn)之前，再將頭結(jié)點(diǎn)指向s結(jié)點(diǎn)。

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

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

A.存儲(chǔ)效率

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

C.裝填（裝載）因子

D.平均查找長(zhǎng)度

【答案】D~~@

【解析】哈希方法沖突會(huì)使在查找沖突的關(guān)鍵字時(shí)，還要根據(jù)沖突處理

辦法多次比較關(guān)鍵字，則直接影響了平均查找長(zhǎng)度。

28.在海具有15個(gè)關(guān)鍵字的4階B樹(shù)中，含卷字的結(jié)微略是（）。

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

A.5

B.6

C.10

D.15

【答案】D~~@

【解析】階極俳根結(jié)點(diǎn)含關(guān)鍵字個(gè)數(shù)

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

4階B樹(shù)胴賭點(diǎn)含關(guān)鍵字1~3個(gè)，所以要使關(guān)鍵字結(jié)點(diǎn)數(shù)量最多，那么每個(gè)

結(jié)點(diǎn)只有一個(gè)關(guān)鍵字，一共有15個(gè)關(guān)鍵翼陷最多有15個(gè)含有關(guān)鍵字的結(jié)點(diǎn)

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

A.abcd*+-

B.abc+*d-

C.abc*+d-

D.-+*abcd

【答案】B—@

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

達(dá)式。

30.用希狎脖方法對(duì)f麴居序列進(jìn)行排序時(shí),若第1趟排錠果為

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

年聯(lián)考真題］

A.2

B.3

C.4

D.5

【答案】B—@

【解析】對(duì)于A,t獻(xiàn)g2,刃以9,4,7,20,15含-組，而它H遑?zé)o序的，

所以A錯(cuò)誤

對(duì)于C,增量為4,那么9,7,15是一組，而它們是無(wú)序的，所以C錯(cuò)誤

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

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

正確

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

考真題］

A.2354679

B.2,7,5,6,439

C.3,254,7,6,9

D.4,235,7,6,9

【答案】C~~@

【解析】對(duì)于快速排序，每一趟都會(huì)使一個(gè)元素位于有序時(shí)的位置，而

有序序列為2345679,與C進(jìn)行對(duì)比，只有9位于它有序的時(shí)僚^位置，顯

然不是第R快潮脖的結(jié)果

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

A.對(duì)隊(duì)列中的元素排序

B.取出最近進(jìn)隊(duì)的元素

C.在隊(duì)頭元素之前插入元素

D.刪除隊(duì)頭元素

【答案】D—@

【解析】隊(duì)列的原則是先進(jìn)先出，出隊(duì)操作應(yīng)該刪除隊(duì)頭元素。

33.9曬個(gè)長(zhǎng)^別為m和n的升序峰，若將它H哈并為f長(zhǎng)度為m+n

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

A.O(n)

B.0(m*n)

C.O(min(mzn))

D.O(max(m,n))

【答案】D

【解析】m和n是兩個(gè)升序鏈表，長(zhǎng)度分別為m和n,在合并過(guò)程中最

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

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

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

A.n-3

B.n-2

C.n-1

D.無(wú)法確定

【答案】C

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

n-lo

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

A.無(wú)法判斷隊(duì)列是否為空

B.無(wú)法判斷隊(duì)列是否為滿

C.隊(duì)列不可能滿

D.處說(shuō)法者壞是

【答案】D—@

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

是否為空或滿。至少可以通過(guò)兩種方法進(jìn)行判斷：①另設(shè)一個(gè)布爾變量來(lái)區(qū)別隊(duì)

列是空還是滿；②隊(duì)滿時(shí)，（rear+1）=二font。

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

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

A.0

B.1

C.2

D.3

【答案】D

【解析】將圖中給定的關(guān)鍵字序列依次插入到平衡樹(shù)中，構(gòu)成的平衡樹(shù)

如下圖所示,由圖可知平衡因子為0的分支結(jié)點(diǎn)為3個(gè)葉子結(jié)點(diǎn),故答案為Do

37.已知三叉樹(shù)T中6個(gè)葉結(jié)點(diǎn)的權(quán)分別是2,3,4,5,6,7,T的帶權(quán)（外

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

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉樹(shù)的6個(gè)葉子結(jié)點(diǎn)的權(quán)構(gòu)建最小帶權(quán)生成樹(shù),最小的

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

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

尾,則當(dāng)前隊(duì)列中的元素?cái)?shù)是()。［南京理工大學(xué)考研真題］

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

【答案】A

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

概念，在隊(duì)頭進(jìn)行出隊(duì)操作，在隊(duì)尾進(jìn)行進(jìn)隊(duì)操作。rear-front可能為正也可能

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

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

39.若X是后序線索二叉樹(shù)中的葉結(jié)點(diǎn)，且X存在左兄弟結(jié)點(diǎn)Y,則X的右線

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

A.X的父結(jié)點(diǎn)

B.以Y為根的子樹(shù)的最左下結(jié)點(diǎn)

C.X的左兄弟結(jié)點(diǎn)Y

D.以Y為根的子樹(shù)的最右下結(jié)點(diǎn)

【答案】A

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

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

點(diǎn)，即其右線索指向的是父結(jié)點(diǎn)。

40.在任意一棵非空二叉排序樹(shù)T1中,刪除某結(jié)點(diǎn)v之后形成二叉排序樹(shù)T2,

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

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

I.若v是T1的葉結(jié)點(diǎn)，則T1與T3不同

II.若v是T1的葉結(jié)點(diǎn)，則T1與T3相同

山.若v不是T1的葉結(jié)點(diǎn)，則T1與T3不同

IV.若v不是T1的葉結(jié)點(diǎn)，則T1與T3相同

A.僅I、m

B.僅I、IV

C.僅II、III

D.僅II、IV

【答案】C

【解析】在一棵二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)后再將此結(jié)點(diǎn)插入到二叉排

序樹(shù)中，如果刪除的結(jié)點(diǎn)是葉子結(jié)翩陷在插入結(jié)點(diǎn)后，后來(lái)的二叉排序樹(shù)與刪

除結(jié)點(diǎn)之前相同。如果刪除的結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，那么再插入這個(gè)結(jié)點(diǎn)后，后來(lái)

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

41.窗口隊(duì)的共同點(diǎn)是()。［大連理工大學(xué)考研真題］

A.都是先進(jìn)后出

B.都是后進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素

D.沒(méi)有共同點(diǎn)

【答案】C~~@

【解析】棧和隊(duì)列的區(qū)別是棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列是先進(jìn)先出

的數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列的共同點(diǎn)是都只能在端點(diǎn)處插入和刪除元素。

42.設(shè)圖的令吩妾矩陣A如下所示，各頂點(diǎn)的度依次是()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

【解析】當(dāng)圖用鄰接矩陣存儲(chǔ)時(shí)，各頂點(diǎn)的度是矩陣中此結(jié)點(diǎn)對(duì)應(yīng)的橫

行和縱列非零元素之和。

43.若對(duì)如下無(wú)向圖進(jìn)行遍歷,則下列選項(xiàng)中，不是廣度優(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

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

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

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

真題］

A.查找哈希（Hash）表

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

C.前序（根）遍歷二叉樹(shù)

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

【答案】B

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

搜索網(wǎng)需要使用棧做輔助存儲(chǔ)空間，廣度優(yōu)先搜索樹(shù)需要隊(duì)列做輔助存儲(chǔ)空間。

45.下列AOE網(wǎng)表亦■項(xiàng)包含8個(gè)活動(dòng)的工程。通過(guò)同時(shí)加快若干進(jìn)度可以縮

短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是（）o

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

A.c和e

B.d和e

C.f和d

D.f和h

【答案】C

【解汨木郵AOE網(wǎng)的定義可知，同時(shí)縮短幾條為徑上的活時(shí)間,

可以縮短整個(gè)工期。

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

年聯(lián)考真題］

A.5

B.7

C.8

D.14

【答案】A

【解析】根據(jù)B樹(shù)的定義可知,跟結(jié)點(diǎn)最少含有max（2,（m?l））個(gè)

瀉蜉，高孰）2的階B樹(shù)期有（5-1）+1=5^^^,其樹(shù)群點(diǎn)含有（5-1）

個(gè)關(guān)鍵字,第2題點(diǎn)含有1關(guān)鍵字。

47.在一棵三元樹(shù)中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1

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

A.4

B.5

C.6

D.7

【答案】C~~@

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

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

從每個(gè)結(jié)點(diǎn)所指向的結(jié)點(diǎn)數(shù)的和的角度來(lái)計(jì)算度為3的樹(shù)總結(jié)點(diǎn)數(shù)n=2x3+lx

2+2x1+1=11。兩種方法所計(jì)算出來(lái)的n相等,所以x=6。

48.對(duì)給定的頰字筋I(lǐng)」110,119,007,911,114,120,122進(jìn)行基軸F

序,則第2趟分配收集后得到的關(guān)鍵字序列是()［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趟排序是按照個(gè)位數(shù)字時(shí)^序的第2趟排序是

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

49.求整數(shù)n(n>0)階乘的算法如下，其時(shí)間復(fù)雜度是()。［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—@

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

intfact(intn)(

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

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

_____________________________________________

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

其中0(1)為乘法運(yùn)算的時(shí)間。

因此，當(dāng)nwl時(shí)，T(n)-0(l);當(dāng)n>l時(shí)，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)的時(shí)間復(fù)雜度為0(n)0

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

和M3O與森林F對(duì)應(yīng)的二叉樹(shù)根^點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是(［北方

交通大學(xué)考研真題］

A.Ml

B.M1+M2

C.M3

D.M2+M3

【答案】D~~@

【解析】森林轉(zhuǎn)換成二叉樹(shù)的原則：將第一棵樹(shù)的根結(jié)點(diǎn)作為根結(jié)點(diǎn)，

所有結(jié)點(diǎn)的第f磁子作為左孩子，下T兄弟結(jié)點(diǎn)作為右孩子，其它樹(shù)作為

第一棵樹(shù)的右孩子。所以森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是除

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

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

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

時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)

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

A.5

B.7

C.8

D.11

【答案】A~~@

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

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

頂運(yùn)算符(先出棧的運(yùn)算符先計(jì)算，同優(yōu)先級(jí)的運(yùn)算符在棧中的先計(jì)算)。表達(dá)

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

當(dāng)前享存運(yùn)算存枝內(nèi)容后始表達(dá)式說(shuō)明

2

?進(jìn)棧

b一ab

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

,■ab-

出棧，“小進(jìn)棧

a,abr

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

.■.abr

理?xiàng)?/p>

(-?(ab-a對(duì)它之前后的運(yùn)算符起隔離作用

(-?((ab-a"（"對(duì)它之前后的運(yùn)算符起隔離作用

-*((ab-ac

—-?(<*ab-ac進(jìn)錢(qián)

d??<《+ab-acd

與其配對(duì)的左任號(hào)及其前所有運(yùn)尊后出

)，（abicd-

枝

/-?(/ab*acd*進(jìn)柱

e-?(/ab-acdr

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

-??(-ab*acd-e/

出校，“?”進(jìn)餞

fJ(?ab-acd-e^f

與其配對(duì)的左話號(hào)及其前斫有運(yùn)算符出

)ab-acd*e/f-

錢(qián)

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

,ab-acd*e/f-*

出錢(qián)

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

ab-acd-e/f-*-出棧，?進(jìn)棧

gab-aed-e/f-*-g

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

通過(guò)上表可以看出，顯然轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大例是5。

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

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

A.只有e

B.有e、b

C.有e、c

D.無(wú)法確定

【答案】A—@

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

后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹(shù)的根結(jié)點(diǎn),接下來(lái)，在

前序遍歷的第二個(gè)結(jié)點(diǎn)為e,而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為e,說(shuō)明a的孩子

結(jié)點(diǎn)只有6o

53.有關(guān)二叉樹(shù)下列說(shuō)法正確的是（［南京理工大學(xué)考研真題］

A.二叉樹(shù)的度為2

B.一棵二叉樹(shù)的度可以小于2

C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2

D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2

【答案】B—@

【解析】樹(shù)的度=MAX（結(jié)點(diǎn)1的度結(jié)點(diǎn)2的度結(jié)點(diǎn)3的度，…,結(jié)點(diǎn)n

的度）。二叉樹(shù)之所以稱為二叉樹(shù)，是因?yàn)槎鏄?shù)中節(jié)點(diǎn)的度最大是2,也可以

小于2。

54.若平衡二叉樹(shù)的高度為6,且所有非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二

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

A.12

B.20

C.32

D.33

【答案】B~~@

【解析】本題題目的實(shí)際問(wèn)題是，具有6層結(jié)點(diǎn)的平衡二叉樹(shù)含有最少

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

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

由此可得電=20。對(duì)應(yīng)的平衡二叉樹(shù)如下圖所示。

55.對(duì)有2個(gè)頂點(diǎn)e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷,其算

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

A.0(n)

B.0(e)

C.O(n+e)

D.O(nxe)

【答案】C~~@

【解析】遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。其耗

費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲(chǔ)結(jié)構(gòu)

時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(山)，其中n為圖口頂點(diǎn)數(shù)。而當(dāng)

以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，戈令展點(diǎn)所需時(shí)間為0(e),其中e為無(wú)向圖中

邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷

圖的時(shí)間復(fù)雜度為o（n+e）o即可得出正確答案。

56.深度為h的滿m叉樹(shù)的第k層有（）個(gè)結(jié)點(diǎn)（lwkwh）。［北京航空

航天大學(xué)考研真題］

A.mk-i

B.mk-1

C.mh-i

D.mh-1

【答案】A~~@

【解析】滿m叉樹(shù)第k層必有mk-i個(gè)結(jié)點(diǎn)。

57.若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該

圖拓?fù)湫蛄械慕Y(jié)論是（）c［2012年聯(lián)考真題］

A.存在，且唯一

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

C.存在，可能不唯一

D.無(wú)海角謖否詼

【答案】C~~@

【解析】圖的基本應(yīng)用——拓?fù)渑判?，用鄰接矩陣存?chǔ)有向圖，矩陣中主對(duì)角

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

o11

000

唯一，如圖的令展矩陣為〔。。小，則存在兩個(gè)拓?fù)湫蛄小?/p>

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

a到其他各頂點(diǎn)的最短路徑，則得到的第一級(jí)可珞徑的目標(biāo)頂點(diǎn)是b,第二條

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

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

A.d,e,f

B.e,d,f

C.f,dze

D.f,e,d

【答案】C—@

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

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

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

點(diǎn)

趟煤、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.將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的

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

A.4

B.5

C.6

D.7

【答案】C~~@

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

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

樹(shù)。具有n個(gè)（n>0）結(jié)點(diǎn)的完全二叉樹(shù)的高度為lbg2（n+1）或IQg2n+JL;

由完全二叉樹(shù)類推到完全三叉樹(shù)可知，n個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度為l（pg3

（n+1）威［log3n>lo

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

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

成樹(shù)中HI.使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相

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

同

A.僅I

B.僅n

c.僅工、m

D.僅n、iv

【答案】A—@

【解析】當(dāng)圖中存在相同權(quán)值的邊時(shí)，其最小生成樹(shù)可能是不唯一的，

但最小生成樹(shù)的代價(jià)一定是相同的，所以說(shuō)法I正確。從n個(gè)頂點(diǎn)的連通圖中

選取n-1條權(quán)值最小的邊可能構(gòu)成回路，所以說(shuō)法II錯(cuò)誤。當(dāng)某個(gè)頂點(diǎn)有權(quán)值

相同的邊，使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)并不一

定相同，所以說(shuō)法m錯(cuò)誤。當(dāng)最小生成樹(shù)不唯一時(shí)，使用普里姆算法和克魯斯卡

爾（Kruskal）算法得到的最小生成樹(shù)可能相同，也可能不同，所以說(shuō)法IV錯(cuò)誤。

由此可得出正確答案。

61.設(shè)有一棵3階B樹(shù)，如題61圖所示。刪除關(guān)鍵字78得至!）一棵新B樹(shù)，其

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

題61圖3階B樹(shù)圖

A.60

B.60,62

C.62,65

D.65

【答案】D~~@

【解析】本題主要考查B