西大成人教育數(shù)據(jù)結構期末考試復習題及參考答案

數(shù)據(jù)結構

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

1對n（n22）個權值均不同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（）。

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

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

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

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

正確答案：A

2若某鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個

A,則采用（）存儲方式最節(jié)省運算時間。

B單鏈表

C雙鏈表

D單循環(huán)鏈表

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

正確答案：D

3設G1=（V1,E1）和G2=（V2,E2）為兩個圖,如果，則稱（）?

AG1是G2的子圖

BG2是G1的子圖

CG1是G2的連通分量

DG2是G1的連通分量

正確答案：A

4已知一個有向圖的鄰接表存儲結構如下圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點VI出發(fā),

所得到的頂點序列是（）

A

BV1,V2,V3,V5,V4

CV1,V2,V3,V4,V5

DV1,V3,V4,V5,V2EV1,V4,V3,V5,V2

正確答案：C

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

A數(shù)據(jù)對象、數(shù)據(jù)關系和基本操作

B數(shù)據(jù)元素、邏輯結構和存儲結構

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

D數(shù)據(jù)元素、數(shù)據(jù)結構和數(shù)據(jù)類型

正確答案：A

6隊列的刪除操作是在（）。

A隊頭

B隊尾

C隊中

D隊列任意位置

正確答案：A

7樹最適合表示（）

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

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

C元素之間具有層次關系

D元素之間關系任意

正確答案：C

8以下關于圖的存儲結構的敘述中正確的是（）。

A鄰接矩陣占用的存儲空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關

B鄰接矩陣占用的存儲空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關

C鄰接表占用的存儲空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關

D鄰接表占用的存儲空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關

正確答案：A

9設圖的鄰接矩陣為，則該圖為（）。

A有向圖

B無向圖

C強連通圖

D完全圖

正確答案：A

10鏈表不具有的特點是（）。

A隨機訪問

B不必事先估計存儲空間

C插人刪除時不需移動元素

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

正確答案：A

11假定一棵二叉樹中，度為2的結點數(shù)位15,度為1的結點數(shù)為30,則葉子結點有（）

個。

A15B16C17D47

正確答案：B

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

A遞增或遞減

B遞增

C遞減

D無序

正確答案：A

13下面有向圖所表示的拓撲排序的結果序列是（）

A

B125634

C516234

D123456

E521643

正確答案：B

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

A棧底

B棧頂

C任意位置

D指定位置

正確答案：B

15一個順序表的第一個元素的存儲地址是10,每個元素的長度為2,則第5個元素的地址

是（）。

A14B16C18D20

正確答案：C

16一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是（）。

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

正確答案：B

17在有向圖的逆鄰接表中，每個頂點鄰接表鏈接這該頂點所有（）鄰接點。

A入邊

B出邊

C入邊和出邊

D不是出邊

正確答案：A

18若某線性表最常用的操作是存取指定序號的元素和在最后位置進行插入和刪除運算，則

利用（）存儲方式最節(jié)省時間。

A順序表

B雙鏈表

C帶頭結點的單鏈表

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

正確答案：A

19按照二叉樹的定義，具有3個結點的二叉樹有（）種。

A3B4C5D6

正確答案：C

20數(shù)據(jù)結構是（）。

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

B數(shù)據(jù)的存儲結構

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

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

正確答案：D

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

Adecab

Bdeabc

Ccedba

Dacbed

正確答案：c

22任何一個無向連通圖的最小生成樹（）。

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在

正確答案：B

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

A543621B346521C453216D234156

正確答案：B

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

A在進行插入、刪除操作運算時能保證鏈表不斷開

B在表中任一結點出發(fā)都能掃描整個鏈表

C不再需要頭指針

D已知某結點位置后能容易找到其直接前驅

正確答案：B

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

A順序存儲結構

B鏈式存儲結構

C索引存儲結構

D散列存儲結構

正確答案：B

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

ADijkstra算法

BPrim算法

CFIoyd算法

DKruskal算法

正確答案：B

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

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

B拓撲排序

C最短路徑

D關鍵路徑

正確答案：B

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

1下列說法正確的是（）

A當隊列中無數(shù)據(jù)元素時，稱為空隊列

B隊列的特點是“先進后出”

C隊列是一種操作不受限的線性表

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

正確答案：AD

2下列關于線性表的描述正確的是（）

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

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

C線性表采用鏈式存儲可以分配不連續(xù)的存儲空間

D線性表采用鏈式才能出便于插入和刪除操作的實現(xiàn)

正確答案：BCD

3根據(jù)所喲數(shù)據(jù)成員之間的邏輯關系的不同個，數(shù)據(jù)結構分為（）

A非線性結構

B邏輯結構

C物理結構

D線性結構

正確答案：AD

4下列關于鏈式存儲結構，哪一項是正確的？（）

A結點除自身外，還包括指針域，因此存儲密度小于順序存儲結構

B邏輯上相鄰的結點物理上不必鄰接

C可以通過計算直接得到第i個結點的存儲地址

D插入、刪除操作方便,不必移動結點

正確答案：ABD

5下面敘述正確的是（）

A線性表在鏈式存儲時,查找第i個元素的時間同i值無關

B線性表在鏈式存儲時,查找第i個元素的時間同i值成正比

C線性表在順序存儲時,查找第i個元素的時間同i值無關

D線性表在順序存儲時,查找第i個元素的時間同i值程增比

正確答案：BC

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

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

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

C先根遍歷

D后根遍歷

正確答案：AB

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

A直觀表示法

B嵌套集合表示法

C凹入表示法

D廣義表表示法

正確答案：ABCD

8下列說法正確的是（）

A圖結構中，各結點之間的關系可以是任意的

B樹結構構中，各元素之間有明顯的層次關系

C樹結構中，數(shù)據(jù)元素之間僅有線性關系

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

正確答案：ABD

9完全二叉樹（）

A適合于順序結構存儲

B不一定適合順序結構存儲

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

D某些結點有右子樹，必然有左子樹

正確答案：AD

10以下說法正確的是（）

A二叉樹meige結點至多只有兩棵子樹

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

C二叉樹只能采用鏈式存儲

D樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支.

正確答案：ABD

11以下說法中正確的是（）

A無向圖中的極大連通子圖稱為連通分量

B連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點

C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點

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

正確答案：ABC

12線性結構的特點是（）

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

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

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

D除第一元素外，均有唯一的前驅

正確答案：ABCD

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

A單鏈表

B順序表

C雙鏈表

D循環(huán)鏈表

正確答案：ACD

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

1已知完全二叉樹的第八層有8個結點，則其葉子結點數(shù)是?

正確答案：第一空：68；

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

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

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

于A［12］的元素，所比較過的元素的下標依次為一、15、12o

正確答案：第一空：10；

4在無向圖G的鄰接矩陣A中，若A皿j］等于1,則A皿i］等于?

正確答案：第一空：1;

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

正確答案：第一空：n-1；

6已知一棵度為4的樹中，度為i（i>l）的結點個數(shù)有i個，則該樹中有個

葉子結點。

正確答案：第一空：21；

7帶有頭結點的單鏈表head為空的條件是o

第一空：正確答案：第一空：head->

第二空：next=NULL；

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

順序排序，最省時間的是算法。

正確答案：第一空：插入排序；

9一棵二叉樹中，度為零的結點個數(shù)為n0,度為2的結點個數(shù)為n2,則n0和n2之間的關

系為?

正確答案：第一空：n0=n2+l；

10具有100個結點的完全二叉樹的深度為。

正確答案：第一空：7；

11在循環(huán)隊列hq中（最多n個元素），判斷隊列滿的條件是。

正確答案：第一空：hq->

第二空:front==（hq->

第三空：rear+l）%n；

四.簡答題（共1題,1.6分）

1已知指針p指向雙向鏈表中的一個結點（非首、非尾結點），則將指針s指向結點插在p

指向結點前的語句序列是：

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

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

1給定權集W=（2,3,4,7,8,9）,試構造關于W的一棵哈夫曼樹，并求其加權路徑

長度WPL及相應哈夫曼編碼。

正確答案：解：Huffman樹：

其加權路徑長度為：

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

2:00003:00014:0019:017:108:11【評分說明】哈夫曼樹建立正確5分，WPL正

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

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

ABCI)E

FOllOl'

10100

11011

00101

[10110]

（1）畫出該圖；

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

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

正確答案：解：（1）（1分）

（2）（5分）此問答案不唯一，每個鏈表后的結點順序可以調換，比如A結點后的1、2、

4的順序可以互換。

0A

1B

2C

3D

4E

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

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

3畫出如下圖所示無向圖G對應的鄰接矩陣和鄰接表兩種存儲結構。

正確答案：解答:

「1111

1110

A=l1111

1.011

0111

(a)(b)

【評分說明】(a)鄰接矩陣5分，(b)鄰接表5分。

4已知圖G如下，圖示用克魯斯卡爾算法構造最小生成樹的過程。

正確答案：構造最小生成樹的過程如下:

⑥

/

0①

(a)(b)0

)

/

(c)(d)~

(e)(f)~

5依次輸入關鍵字:{17,26,35,10,8,15,18,20,12),給出構造二叉查找樹的過程.

XX

正確答案：J(127)(20)

6設字符a,b,c,d,e的使用頻度分別是0.25,0.3,0.12,0.08,0.25。試構造一課Huffman樹,

求出其帶權路徑長度并給出a,b,c,d,e的Huffman(哈夫曼)編碼。

正確答案：解：Huffman樹：

NA-i

cA

WPL=0.25*2+0.3*2+0.12*3+0.08*3+0.25*2=2.2編碼分別為：a:10b:01c:000d:001e:11

【評分說明】哈夫曼樹建立正確5分，WPL正確2分，哈夫曼編碼正確3分

六.其它(共2題,7.2分)

1已知某個帶頭結點單鏈表L,其結點數(shù)據(jù)遞增有序，試編寫算法：

voidinsert(LinkNode*&L,ElemTypex)

在鏈表L中插入值為x的結點，并保持鏈表有序性。

正確答案：解：

voidListlnsert(LinkNode*&L,ElemTypex)

{UnkNode*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分

)

2設線性表L中的數(shù)據(jù)元素遞增有序，并以帶頭單鏈表作存儲結構，試寫一算法

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

正確答案：解：

StatusDel_allx(Linklist&L,日emTypex)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ù)結構

一.單選題(共24題,38.4分)

1堆排序屬于下列哪一種排序算法？()

A插入排序

B交換排序

C選擇排序

D快速排序

正確答案：C

2以下關于圖的存儲結構的敘述中正確的是（）。

A鄰接矩陣占用的存儲空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關

B鄰接矩陣占用的存儲空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關

C鄰接表占用的存儲空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關

D鄰接表占用的存儲空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關

正確答案：A

3任何一個無向連通圖的最小生成樹（）。

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在

正確答案：B

4在線性表的下列存儲結構中，讀取元素花費的時間最少的是（）。

A單鏈表

B雙鏈表

C循環(huán)鏈表

D順序表

正確答案：D

5鏈表不具有的特點是（）。

A隨機訪問

B不必事先估計存儲空間

C插人刪除時不需移動元素

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

正確答案：A

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

A在進行插入、刪除操作運算時能保證鏈表不斷開

B在表中任一結點出發(fā)都能掃描整個鏈表

C不再需要頭指針

D已知某結點位置后能容易找到其直接前驅

正確答案：B

7若某線性表最常用的操作是存取指定序號的元素和在最后位置進行插入和刪除運算，則利

用（）存儲方式最節(jié)省時間。

A順序表

B雙鏈表

C帶頭結點的單鏈表

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

正確答案：A

8一個順序表的第一個元素的存儲地址是10,每個元素的長度為2,則第5個元素的地址是

（）。

A14B16C18D20

正確答案：C

9按照二叉樹的定義，具有3個結點的二叉樹有（）種。

A3B4C5D6

正確答案：C

10數(shù)據(jù)結構是（）。

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

B數(shù)據(jù)的存儲結構

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

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

正確答案：D

11有6個元素6,5,4,3,2,1按順序入棧，則下列哪一個是合法的出棧序列？（）

A543621B346521C453216D234156

正確答案：B

12若某鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個

A,則采用（）存儲方式最節(jié)省運算時間。

B單鏈表

C雙鏈表

D單循環(huán)鏈表

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

正確答案：D

13一棵高度為h（h2l）的完全二叉樹至少有（）個結點。

A2h-1B2h

C2h+1D2h-1+1

正確答案：A

14如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是

（）

A完全圖

B連通圖

C有回路

D一棵樹

正確答案：B

15用順序存儲的方法，將完全二叉樹種所有結點按層次逐個從左到右的順序存放在一維數(shù)

組R[1..N]中，若結點R[i]有右孩子，則其右孩子是（）。

AR[2i-l]

BR[2i]

CR[2i+l]

DR[i/2]

正確答案：C

16鏈表不具備的特點是（）。

A插入和刪除操作不需要移動元素

B不必事先估計存儲空間

C可隨機訪問任一元素

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

正確答案：c

17下面（）可以判斷出一個有向圖是否有回路。

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

B拓撲排序

C最短路徑

D關鍵路徑

正確答案：B

18假定一棵二叉樹中，度為2的結點數(shù)位15,度為1的結點數(shù)為30,則葉子結點有（）

個。

A15B16C17D47

正確答案：B

19非空循環(huán)單鏈表head的尾結點p滿足（）。

Ap->next==NULL

Bp->next==head

Cp==NULL

Dp==head

正確答案：B

20一個遞增表為RO.11],采用折半查找方法，在某次成功查找到指定的記錄時，以下（）

是可能的記錄比較序列。

AR[0],R[5]>R[2]

BR⑼、R⑹、R[9]

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

DR[5hR[2]、R[4]

正確答案：C

21棧的插入和刪除操作在（）.

A棧底

B棧頂

C任意位置

D指定位置

正確答案：B

22隊列的刪除操作是在（）。

A隊頭

B隊尾

C隊中

D隊列任意位置

正確答案：A

23一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是（）。

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

正確答案：B

24串是（）。

A不少于一個字母的序列

B任意個字母的序列

C不少于一個字符的任意序列

D有限個字符的序列

正確答案：D

二.多選題（共14題,22.4分）

1以下說法正確的是（）

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

B數(shù)據(jù)結構是具有結構的數(shù)據(jù)對象

C數(shù)據(jù)結構是數(shù)據(jù)對象與對象數(shù)據(jù)元素之間關系的集合

D數(shù)據(jù)的邏輯結構是指各數(shù)據(jù)元素之間的邏輯關系，是用戶按使用需要建立的

正確答案：CD

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

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

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

C先根遍歷

D后根遍歷

正確答案：AB

3下列和圖結構有關的算法是（）

A克魯斯卡爾算法

B哈夫曼算法

C迪杰斯特拉算法

D拓撲排序算法

正確答案：ACD

4下面屬于常用的表示樹的鏈式結構的有（）

A雙親表示法

B孩子表示法

C孩子兄弟表示法

D父子表示法

正確答案：ABC

5下列關于鏈式存儲結構，哪一項是正確的？（）

A結點除自身外，還包括指針域，因此存儲密度小于順序存儲結構

B邏輯上相鄰的結點物理上不必鄰接

C可以通過計算直接得到第i個結點的存儲地址

D插入、刪除操作方便，不必移動結點

正確答案：ABD

6數(shù)據(jù)元素之間存在著某種關系，這種數(shù)據(jù)元素相互之間的關系稱為結構。根據(jù)數(shù)據(jù)元素之

間關系的不同特性，下面的選項中（）屬于其基本結構。

A集合

B線性結構

C樹結構

D圖結構

正確答案：ABCD

7根據(jù)所喲數(shù)據(jù)成員之間的邏輯關系的不同個，數(shù)據(jù)結構分為（）

A非線性結構

B邏輯結構

C物理結構

D線性結構

正確答案：AD

8下列說法正確的是（）

A圖結構中，各結點之間的關系可以是任意的

B樹結構構中，各元素之間有明顯的層次關系

C樹結構中，數(shù)據(jù)元素之間僅有線性關系

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

正確答案：ABD

9下列哪一種數(shù)據(jù)結構適合于插入和刪除操作？（）

A單鏈表

B順序表

C雙鏈表

D循環(huán)鏈表

正確答案：ACD

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

A直觀表示法

B嵌套集合表示法

C凹入表示法

D廣義表表示法

正確答案：ABCD

11以下說法正確的是（）

A二叉樹meige結點至多只有兩棵子樹

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

C二叉樹只能采用鏈式存儲

D樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支.

正確答案：ABD

12線性結構的特點是（）

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

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

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

D除第一元素外，均有唯一的前驅

正確答案：ABCD

13以下說法中正確的是（）

A無向圖中的極大連通子圖稱為連通分量

B連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點

C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點

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

正確答案：ABC

14下列說法正確的是（）

A當隊列中無數(shù)據(jù)元素時，稱為空隊列

B隊列的特點是“先進后出”

C隊列是一種操作不受限的線性表

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

正確答案：AD

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

1在具有n個單元的循環(huán)隊列中，隊滿時共有個元素。

正確答案：第一空：n-1：

2一棵二叉樹中，度為零的結點個數(shù)為nO,度為2的結點個數(shù)為n2,則nO和n2之間的關

系為。

正確答案：第一空：n0=n2+l；

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

正確答案：第一空：出度；

4在循環(huán)隊列hq中（最多n個元素），判斷隊列滿的條件是。

正確答案：第一空：hq->

第二空:front==（hq->

第三空：rear+l）%n；

5一棵有n個葉子結點的哈夫曼樹共有個結點。

正確答案：第一空：2n-l：

6已知一棵度為4的樹中，度為i（i>l）的結點個數(shù)有i個，則該樹中有個

葉子結點。

正確答案：第一空：21；

7具有100個結點的完全二叉樹的深度為。

正確答案：第一空：7；

8在有序表A[21]中，數(shù)據(jù)元素存儲在A⑴到A[20]單元，采用二分查找算法查找元素值等

于A[12]的元素，所比較過的元素的下標依次為一、15、12。

正確答案：第一空：10；

9在一個圖中，所有頂點的度之和等于邊數(shù)的倍。

正確答案：第一空：2；

10在一個長度為n的順序表中第i個元素（l<=i<=n）之前插入一個元素時，需向后移動

個元素。

正確答案：第一空：n-i+1；

11在單鏈表中，刪除指針P所指結點的后繼結點的語句是o

正確答案：第一空：P->

第二空：next=P->

第三空：next->

第四空：next；

12帶有頭結點的單鏈表head為空的條件是。

正確答案：第一空：head->

第二空：next=NULL；

13在無向圖G的鄰接矩陣A中，若A「皿等于1,則等于。

正確答案：第一空：1;

四.簡答題（共1題,1.6分）

1已知指針p指向雙向鏈表中的一個結點（非首、非尾結點），則將指針s指向結點插在p

指向結點前的語句序列是：

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

五.論述題（共5題,8.0分）

1已知圖G如下，圖示用克魯斯卡爾算法構造最小生成樹的過程。

正確答案：構造最小生成樹的過程如下:

2依次輸入關鍵字：｛17,26,35,10,8,15,18,20,12),給出構造二叉查找樹的過程。

正確答案:

3畫出如下圖所示無向圖G對應的鄰接矩陣和鄰接表兩種存儲結構。

正確答案：解答:

riiii

1110

A=i1111

1.01