數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

超越高度

一.單選題（共23題,36.8分）

1堆排序?qū)儆谙铝心囊环N排序算法？（）

A插入排序

B交換排序

C選擇排序

D快速排序

正確答案：C

2下面有向圖所表示的拓?fù)渑判虻慕Y(jié)果序列是（）

B125634C516234D123456E521643

正確答案：B

3無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中（）。

A通過(guò)該頂點(diǎn)的簡(jiǎn)單路徑數(shù)

B與該頂點(diǎn)連通的頂點(diǎn)數(shù)

C通過(guò)該頂點(diǎn)的回路數(shù)

D與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)

正確答案：D

4樹最適合表示（）

A有序數(shù)據(jù)元素

B無(wú)序數(shù)據(jù)元素

C元素之間具有層次關(guān)系

D元素之間關(guān)系任意

正確答案：C

5對(duì)n（n22）個(gè)權(quán)值均不同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的

是（）。

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

B該樹中一定沒(méi)有度為1的結(jié)點(diǎn)

C樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D樹中任一非葉子結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值

正確答案：A

6已知一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，根據(jù)深度優(yōu)先遍歷算法，從

頂點(diǎn)VI出發(fā)，所得到的頂點(diǎn)序列是（）

BV1,V2,V3,V5,V4CV1,V2,V3,V4,V5DV1,V3,V4,V5,V2EV1,V4,V3,V5,V2正

確答案：C

7非空循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（）。

Ap->next==NULL

Bp->next==head

Cp==NULL

Dp==head

正確答案：B

8假定一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)位15,度為1的結(jié)點(diǎn)數(shù)為30,則葉子結(jié)

點(diǎn)有（）個(gè)。

A15B16C17D47

正確答案：B

9抽象數(shù)據(jù)類型的三個(gè)組成部分分別為（）。

A數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作

B數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

C數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型

D數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

正確答案：A

10如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則

該圖一定是（）

A完全圖

B連通圖

C有回路

D一棵樹

正確答案：B

11下面（）可以判斷出一個(gè)有向圖是否有回路。

A廣度優(yōu)先遍歷

B拓?fù)渑判?/p>

C最短路徑

D關(guān)鍵路徑

正確答案：B

12下面（）算法適合用于構(gòu)造一個(gè)稠密圖的最小生成樹。

ADijkstra算法

BPrim算法

CFIoyd算法

DKruskal算法

正確答案：B

13按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

A3B4C5D6

正確答案：C

14將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開(kāi)始，每一層上從左到右依次

對(duì)結(jié)

A行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）。

B98C99D50E48

正確答案：A

15一個(gè)遞增表為采用折半查找方法，在某次成功查找到指定的記錄

時(shí)，以下（）是可能的記錄比較序列。

AR[0]、R[5]、R[2]

BR[0]>R⑹、R[9]

CR[5]>R[8]、R[10]

DR[5]、R⑵、R[4]

正確答案：C

16循環(huán)鏈表的主要優(yōu)點(diǎn)是（）

A在進(jìn)行插入、刪除操作運(yùn)算時(shí)能保證鏈表不斷開(kāi)

B在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表

C不再需要頭指針

D已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)

正確答案：B

17在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是（）。

A單鏈表

B雙鏈表

C循環(huán)鏈表

D順序表

正確答案：D

18在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接這該頂點(diǎn)所有（）鄰接點(diǎn)。

A入邊

B出邊

C入邊和出邊

D不是出邊

正確答案：A

19串是（）。

A不少于一個(gè)字母的序列

B任意個(gè)字母的序列

C不少于一個(gè)字符的任意序列

D有限個(gè)字符的序列

正確答案：D

20若某鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一

個(gè)

A,則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

B單鏈表

C雙鏈表

D單循環(huán)鏈表

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

正確答案：D

21設(shè)圖的鄰接矩陣為，則該圖為（）。

A有向圖

B無(wú)向圖

C強(qiáng)連通圖

D完全圖

正確答案：A

22棧的插入和刪除操作在（）。

A棧底

B棧頂

C任意位置

D指定位置

正確答案：B

23一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是10,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)

元素的地址是（）。

A14B16C18D20

正確答案：C

二.多選題（共13題,20.8分）

1下列說(shuō)法正確的是（）

A從邏輯關(guān)系上，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)

B所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系

C數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)

D數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體

正確答案：ABC

2完全二叉樹（）

A適合于順序結(jié)構(gòu)存儲(chǔ)

B不一定適合順序結(jié)構(gòu)存儲(chǔ)

C葉子結(jié)點(diǎn)可在任一層出現(xiàn)

D某些結(jié)點(diǎn)有右子樹，必然有左子樹

正確答案：AD

3下面屬于常用的表示樹的鏈?zhǔn)浇Y(jié)構(gòu)的有（）

A雙親表示法

B孩子表示法

C孩子兄弟表示法

D父子表示法

正確答案：ABC

4數(shù)的表示方法有以下哪幾種？（）

A直觀表示法

B嵌套集合表示法

C凹入表示法

D廣義表表示法

正確答案：ABCD

5以下說(shuō)法正確的是（）

A數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象

C數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象數(shù)據(jù)元素之間關(guān)系的集合

D數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的

正確答案：CD

6（）二叉排序樹不可以得到一個(gè)從小到大的有序序列

A先序遍歷

B中序遍歷

C后序遍歷

D層次遍歷

正確答案：ACD

7下列說(shuō)法正確的是（）

A當(dāng)隊(duì)列中無(wú)數(shù)據(jù)元素時(shí)，稱為空隊(duì)列

B隊(duì)列的特點(diǎn)是“先進(jìn)后出”

C隊(duì)列是一種操作不受限的線性表

D隊(duì)列是一種只允許在一端進(jìn)行插入和刪除數(shù)據(jù)的線性表

正確答案：AD

8下列說(shuō)法正確的是（）

A圖結(jié)構(gòu)中，各結(jié)點(diǎn)之間的關(guān)系可以是任意的

B樹結(jié)構(gòu)構(gòu)中，各元素之間有明顯的層次關(guān)系

C樹結(jié)構(gòu)中，數(shù)據(jù)元素之間僅有線性關(guān)系

D線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系

正確答案：ABD

9下列和圖結(jié)構(gòu)有關(guān)的算法是（）

A克魯斯卡爾算法

B哈夫曼算法

C迪杰斯特拉算法

D拓?fù)渑判蛩惴?/p>

正確答案：ACD

10以下說(shuō)法中正確的是（）

A無(wú)向圖中的極大連通子圖稱為連通分量

B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)

C圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)

D有向圖的遍歷不可采用廣度優(yōu)先搜索方法

正確答案：ABC

11下列哪一種數(shù)據(jù)結(jié)構(gòu)適合于插入和刪除操作？（）

A單鏈表

B順序表

C雙鏈表

D循環(huán)鏈表

正確答案：ACD

12數(shù)據(jù)元素之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。根

據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，下面的選項(xiàng)中（）屬于其基本結(jié)構(gòu)。

A集合

B線性結(jié)構(gòu)

C樹結(jié)構(gòu)

D圖結(jié)構(gòu)

正確答案：ABCD

13以下說(shuō)法正確的是（）

A二叉樹meige結(jié)點(diǎn)至多只有兩棵子樹

B二叉樹的子樹有左右之分

C二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)

D樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。

正確答案：ABD

三.填空題（共13題,20.8分）

1在一個(gè)圖中，所有頂點(diǎn)的度之和等于邊數(shù)的倍。

正確答案：2；

2具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為o

正確答案：7；

3數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和兩種方法衡量其效

率。

正確答案：空間復(fù)雜度；

4n個(gè)元素進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)是次。

正確答案：n-1；

5一棵二叉樹中，度為零的結(jié)點(diǎn)個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n0和

n2之間的關(guān)系為o

正確答案：n0=n2+l；

6帶有頭結(jié)點(diǎn)的單鏈表head為空的條件是。

正確答案：

head->

next=NULL；

7已知完全二叉樹的第八層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是o

正確答案：68；

8分別采用堆排序、快速排序、插入排序和歸并排序算法對(duì)初始狀態(tài)為遞增序

列的表按遞增順序排序，最省時(shí)間的是算法。

正確答案：插入排序；

9已知一棵度為4的樹中，度為i（i>l）的結(jié)點(diǎn)個(gè)數(shù)有i個(gè)，則該樹中有

_______________個(gè)葉子結(jié)點(diǎn)。

正確答案：21；

10在無(wú)向圖G的鄰接矩陣A中，若等于1,則等于。

正確答案：1;

11樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的相同。

正確答案：中序遍歷序列；

12若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為定點(diǎn)

Vi的O

正確答案：出度；

13在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素。

正確答案：n-1；

四.簡(jiǎn)答題（共1題,1.6分）

1已知指針p指向雙向鏈表中的一個(gè)結(jié)點(diǎn)（非首、非尾結(jié)點(diǎn)），則將指針s指向

結(jié)點(diǎn)插在p指向結(jié)點(diǎn)前的語(yǔ)句序列是：

正確答案：

p->prior->next；s

五.論述題（共6題,9.6分）

1將整數(shù)序列（4,5,7,2,1,3,6）中的元素依次插入，給出構(gòu)造二叉查找

樹的過(guò)程。

正確答案：

4

2設(shè)字符a,b,c,d,e的使用頻度分別是0.25,0.3,0.12,0.08,0.25。試構(gòu)造一課

Huffman樹，求出其帶權(quán)路徑長(zhǎng)度并給出a,b,c,d,e的Huffman(哈夫曼)編碼。

正確答案：

解：Huffman樹：

WPL=0.25*2+0.3*2+0.12*3+0.08*3+0.25*2=2.2編碼分別為：a:10b:

01c:000d:001e:11

【評(píng)分說(shuō)明】哈夫曼樹建立正確5分，WPL正確2分，哈夫曼編碼正確3分

3給定權(quán)集亞=(2,3,4,7,8,9),試構(gòu)造關(guān)于W的一棵哈夫曼樹，并求

其加權(quán)路徑長(zhǎng)度WPL及相應(yīng)哈夫曼編碼。

正確答案：

解：Huffman樹：

33

其加權(quán)路徑長(zhǎng)度為：

WPL==7*2+8*2+*9*2+4*3+2*4+3*4=80哈夫曼編碼：

2:00003:00014:0019:017:108:11【評(píng)分說(shuō)明】哈夫曼樹建立正確5

分，WPL正確2分，哈夫曼編碼正確3分

4已知圖G的頂點(diǎn)數(shù)組和鄰接矩陣如下：

A|B|C|D|E

[01101I

10100

11011

00101

[10110]

（1）畫出該圖；

（2）根據(jù)鄰接矩陣寫出該圖的一種鄰接表表示；

（3）根據(jù)鄰接表表示給出從頂點(diǎn)A出發(fā)的深度優(yōu)先和廣度優(yōu)先搜索遍歷序

列。

正確答案：

解：（1）（1分）

（2）（5分）此問(wèn)答案不唯一，每個(gè)鏈表后的結(jié)點(diǎn)順序可以調(diào)換，比如A結(jié)點(diǎn)

后的1、2、4的順序可以互換。

0

1

2

3

4

（3）深度優(yōu)先搜索遍歷序列為：ABCDE（2分）

廣度優(yōu)先搜索遍歷序列為：ABCED（2分）

5已知圖G如下，圖示用克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程。

正確答案：

構(gòu)造最小生成樹的過(guò)程如下:

6畫出如下圖所示無(wú)向圖G對(duì)應(yīng)的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。

正確答案:

解答：

i110

1i101

A=1i111

10111

Lo111V

(a)(b)

【評(píng)分說(shuō)明】(a)鄰接矩陣5分,(b)鄰接表5分。

六.其它(共4題,10.4分)

1設(shè)二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法，求一棵給定二叉樹的葉子結(jié)點(diǎn)

數(shù)目。

正確答案:

intleafNodes(BTNode*b)//I分

{if(b==NULL)return0;//2分

elseif(b->lchild==NULL&&b->rchild==NULL)return1;〃3分

elsereturnleatNodes(b->lchild)+leafNodes(b->rchild);//4分

}

2設(shè)二叉樹T以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試編寫算法shendu(bitreeT),求二叉

樹T的深度。

正確答案：

解：

intshendu(bitreeT)1分

{if(!T)return0;2分

ld=shendu(T->lchild)1分

rd=shendu(T->rchild)；1分

if(ld>rd)d=ld+1;2分

elsed=rd+1;2分

returnd;1分

)

3已知某個(gè)帶頭結(jié)點(diǎn)單鏈表L,其結(jié)點(diǎn)數(shù)據(jù)遞增有序，試編寫算法：

voidinsert(LinkNode*&L,ElemTypex)

在鏈表L中插入值為x的結(jié)點(diǎn)，并保持鏈表有序性。

正確答案：

解：

voidListInsert(LinkNode*&L,ElemTypex)

{LinkNode*pre=L,*p;//2分

while(pre->next!=NULL&&pre->next->data<x)

pre=pre->next;//4分

p=(LinkNode*)malloc(sizeof(LinkNode));//I分

p->data=x;//1分

p->next=pre->next;

pre->next=p;//2分

}

4設(shè)線性表L中的數(shù)據(jù)元素遞增有序，并以帶頭單鏈表作存儲(chǔ)結(jié)構(gòu)，試寫一算

法Del_anx(Linklist&L,ElemTypex)刪除表中所有值等于x的元素。

正確答案：

解：

StatusDel_allx(Linklist&L,ElemTypex)1分

p=L->next;q=L;2分

while(p)2分

{if(p->data==x){q->next=p->next;free(p);}3分

elseq=p;1分

p=q->next;1分

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

一.單選題（共27題,43.2分）

1對(duì)n（n22）個(gè)權(quán)值均不同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的

是（）。

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

B該樹中一定沒(méi)有度為1的結(jié)點(diǎn)

C樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D樹中任一非葉子結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值

正確答案：A

2若某鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一

個(gè)

A,則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

B單鏈表

C雙鏈表

D單循環(huán)鏈表

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

正確答案：D

3設(shè)G1=（V1,E1）和G2=（V2,E2）為兩個(gè)圖，如果，則稱（）。

AG1是G2的子圖

BG2是G1的子圖

CG1是G2的連通分量

DG2是G1的連通分量

正確答案：A

4已知一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，根據(jù)深度優(yōu)先遍歷算法，從

頂點(diǎn)VI出發(fā)，所得到的頂點(diǎn)序列是（）

BV1,V2,V3,V5,V4CV1,V2,V3,V4,V5DV1,V3,V4,V5,V2EV1,V4,V3,V5,V2正

確答案：C

5抽象數(shù)據(jù)類型的三個(gè)組成部分分別為（）。

A數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作

B數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

C數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型

D數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

正確答案：A

6隊(duì)列的刪除操作是在（）。

A隊(duì)頭

B隊(duì)尾

C隊(duì)中

D隊(duì)列任意位置

正確答案：A

7樹最適合表示（）

A有序數(shù)據(jù)元素

B無(wú)序數(shù)據(jù)元素

C元素之間具有層次關(guān)系

D元素之間關(guān)系任意

正確答案：C

8以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的敘述中正確的是（）。

A鄰接矩陣占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

B鄰接矩陣占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)

C鄰接表占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

D鄰接表占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)

正確答案：A

9設(shè)圖的鄰接矩陣為，則該圖為（）。

A有向圖

B無(wú)向圖

C強(qiáng)連通圖

D完全圖

正確答案：A

10鏈表不具有的特點(diǎn)是（）。

A隨機(jī)訪問(wèn)

B不必事先估計(jì)存儲(chǔ)空間

C插人刪除時(shí)不需移動(dòng)元素

D所需的空間與線性表成正比

正確答案：A

11假定一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)位15,度為1的結(jié)點(diǎn)數(shù)為30,則葉子結(jié)

點(diǎn)有（）個(gè)。

A15B16C17D47

正確答案：B

12二分查找法要求查找表中各元素的鍵值必須是（）排列。

A遞增或遞減

B遞增

C遞減

D無(wú)序

正確答案：A

13下面有向圖所表示的拓?fù)渑判虻慕Y(jié)果序列是（）

B125634C516234D123456E521643

正確答案：B

14棧的插入和刪除操作在（）。

A棧底

B棧頂

C任意位置

D指定位置

正確答案：B

15一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是10,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)

元素的地址是（）。

A14B16C18D20

正確答案：C

16一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是（）。

A4,3,2,lBl,2,3,4Cl,4,3,2D3,2,4,1

正確答案：B

17在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接這該頂點(diǎn)所有（）鄰接點(diǎn)。

A入邊

B出邊

C入邊和出邊

D不是出邊

正確答案：A

18若某線性表最常用的操作是存取指定序號(hào)的元素和在最后位置進(jìn)行插入和刪

除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A順序表

B雙鏈表

C帶頭結(jié)點(diǎn)的單鏈表

D不帶頭結(jié)點(diǎn)的循環(huán)單鏈表

正確答案：A

19按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

A3B4C5D6

正確答案：C

20數(shù)據(jù)結(jié)構(gòu)是（）。

A一種數(shù)據(jù)類型

B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

C一組性質(zhì)相同的數(shù)據(jù)元素的集合

D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

正確答案：D

21某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的先序遍歷序

列是（）o

Adecab

Bdeabc

Ccedba

Dacbed

正確答案：c

22任何一個(gè)無(wú)向連通圖的最小生成樹（）。

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在

正確答案：B

23有6個(gè)元素6,5,4,3,2,1按順序入棧，則下列哪一個(gè)是合法的出棧序

列？（）

A543621B346521C453216D234156

正確答案：B

24循環(huán)鏈表的主要優(yōu)點(diǎn)是（）

A在進(jìn)行插入、刪除操作運(yùn)算時(shí)能保證鏈表不斷開(kāi)

B在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表

C不再需要頭指針

D已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)

正確答案：B

25鄰接表是圖的一種（）。

A順序存儲(chǔ)結(jié)構(gòu)

B鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

D散列存儲(chǔ)結(jié)構(gòu)

正確答案：B

26下面（）算法適合用于構(gòu)造一個(gè)稠密圖的最小生成樹。

ADijkstra算法

BPrim算法

CFloyd算法

DKruskal算法

正確答案：B

27下面（）可以判斷出一個(gè)有向圖是否有回路。

A廣度優(yōu)先遍歷

B拓?fù)渑判?/p>

C最短路徑

D關(guān)鍵路徑

正確答案：B

二.多選題（共13題,20.8分）

1下列說(shuō)法正確的是（）

A當(dāng)隊(duì)列中無(wú)數(shù)據(jù)元素時(shí)，稱為空隊(duì)列

B隊(duì)列的特點(diǎn)是“先進(jìn)后出”

C隊(duì)列是一種操作不受限的線性表

D隊(duì)列是一種只允許在一端進(jìn)行插入和刪除數(shù)據(jù)的線性表

正確答案：AD

2下列關(guān)于線性表的描述正確的是（）

A線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

B線性表采用順序存儲(chǔ)必須占用一段連續(xù)的存儲(chǔ)空間

C線性表采用鏈?zhǔn)酱鎯?chǔ)可以分配不連續(xù)的存儲(chǔ)空間

D線性表采用鏈?zhǔn)讲拍艹霰阌诓迦牒蛣h除操作的實(shí)現(xiàn)

正確答案：BCD

3根據(jù)所喲數(shù)據(jù)成員之間的邏輯關(guān)系的不同個(gè)，數(shù)據(jù)結(jié)構(gòu)分為（）

A非線性結(jié)構(gòu)

B邏輯結(jié)構(gòu)

C物理結(jié)構(gòu)

D線性結(jié)構(gòu)

正確答案：AD

4下列關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，哪一項(xiàng)是正確的？（）

A結(jié)點(diǎn)除自身外，還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)

B邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

C可以通過(guò)計(jì)算直接得到第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

D插入、刪除操作方便，不必移動(dòng)結(jié)點(diǎn)

正確答案：ABD

5下面敘述正確的是（）

A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i值無(wú)關(guān)

B線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i值成正比

C線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i值無(wú)關(guān)

D線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i值程增比

正確答案：BC

6下列哪些是圖的遍歷算法？（）

A深度優(yōu)先遍歷

B廣度優(yōu)先遍歷

C先根遍歷

D后根遍歷

正確答案：AB

7數(shù)的表示方法有以下哪幾種？（）

A直觀表示法

B嵌套集合表示法

C凹入表示法

D廣義表表示法

正確答案：ABCD

8下列說(shuō)法正確的是（）

A圖結(jié)構(gòu)中，各結(jié)點(diǎn)之間的關(guān)系可以是任意的

B樹結(jié)構(gòu)構(gòu)中，各元素之間有明顯的層次關(guān)系

C樹結(jié)構(gòu)中，數(shù)據(jù)元素之間僅有線性關(guān)系

D線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系

正確答案：ABD

9完全二叉樹（）

A適合于順序結(jié)構(gòu)存儲(chǔ)

B不一定適合順序結(jié)構(gòu)存儲(chǔ)

C葉子結(jié)點(diǎn)可在任一層出現(xiàn)

D某些結(jié)點(diǎn)有右子樹，必然有左子樹

正確答案：AD

10以下說(shuō)法正確的是（）

A二叉樹meige結(jié)點(diǎn)至多只有兩棵子樹

B二叉樹的子樹有左右之分

C二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)

D樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。

正確答案：ABD

11以下說(shuō)法中正確的是（）

A無(wú)向圖中的極大連通子圖稱為連通分量

B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)

C圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)

D有向圖的遍歷不可采用廣度優(yōu)先搜索方法

正確答案：ABC

12線性結(jié)構(gòu)的特點(diǎn)是（）

A集合中必存在唯一的一個(gè)“第一元素”

B集中中必存在唯一的一個(gè)“最后元素”

C除最后元素外，具有唯一的后繼

D除第一元素外，均有唯一的前驅(qū)

正確答案：ABCD

13下列哪一種數(shù)據(jù)結(jié)構(gòu)適合于插入和刪除操作？（）

A單鏈表

B順序表

C雙鏈表

D循環(huán)鏈表

正確答案：ACD

三.填空題（共11題,17.6分）

1已知完全二叉樹的第八層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是。

正確答案：68；

2哈希查找性能主要與3個(gè)因素有關(guān)，分別是：裝填因子、所采用的哈希函

數(shù)、o

正確答案：解決沖突的方法；

3在有序表A［21］中，數(shù)據(jù)元素存儲(chǔ)在A［l］到A［20］單元，采用二分查找算法

查找元素值等于AE12］的元素，所比較過(guò)的元素的下標(biāo)依次為—、15、

120

正確答案：10;

4在無(wú)向圖G的鄰接矩陣A中，若等于1,則等于。

正確答案：1;

5在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素。

正確答案：n-1；

6已知一棵度為4的樹中，度為i(i>l)的結(jié)點(diǎn)個(gè)數(shù)有i個(gè)，則該樹中有

_______________個(gè)葉子結(jié)點(diǎn)。

正確答案：21；

7帶有頭結(jié)點(diǎn)的單鏈表head為空的條件是o

正確答案：

head->

next=NULL；

8分別采用堆排序、快速排序、插入排序和歸并排序算法對(duì)初始狀態(tài)為遞增序

列的表按遞增順序排序，最省時(shí)間的是算法。

正確答案：插入排序；

9一棵二叉樹中，度為零的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則nO和

n2之間的關(guān)系為o

正確答案：n0=n2+l；

10具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為0

正確答案：7；

11在循環(huán)隊(duì)列hq中(最多n個(gè)元素)，判斷隊(duì)列滿的條件是o

正確答案：

hq->

front==（hq?>

rear+l）%n；

四.簡(jiǎn)答題（共1題,1.6分）

1已知指針p指向雙向鏈表中的一個(gè)結(jié)點(diǎn)（非首、非尾結(jié)點(diǎn)），則將指針s指向

結(jié)點(diǎn)插在p指向結(jié)點(diǎn)前的語(yǔ)句序列是：

正確答案：p->prior->next；s

五.論述題（共6題,9.6分）

1給定權(quán)集亞=（2,3,4,7,8,9）,試構(gòu)造關(guān)于W的一棵哈夫曼樹，并求

其加權(quán)路徑長(zhǎng)度WPL及相應(yīng)哈夫曼編碼。

正確答案：

解：Huffman樹：

其加權(quán)路徑長(zhǎng)度為:

WPL==7*2+8*2+*9*2+4*3+2*4+3*4=80哈夫曼編碼：

2:00003:00014:0019:017:108:11【評(píng)分說(shuō)明】哈夫曼樹建立正確5

分，WPL正確2分，哈夫曼編碼正確3分

2已知圖G的頂點(diǎn)數(shù)組和鄰接矩陣如下：

ABCL)E

01101

10100

11011

0010

0110

(1)畫出該圖;

(2)根據(jù)鄰接矩陣寫出該圖的一種鄰接表表示;

(3)根據(jù)鄰接表表示給出從頂點(diǎn)A出發(fā)的深度優(yōu)先和廣度優(yōu)先搜索遍歷序

列。

正確答案:

解:

(2)(5分)此問(wèn)答案不唯一，每個(gè)鏈表后的結(jié)點(diǎn)順序可以調(diào)換，比如A結(jié)點(diǎn)

后的1、2、4的