數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)

2017年5月

綜合練習(xí)一

一、單項(xiàng)選擇題

1.設(shè)有頭指針為head的帶有頭結(jié)點(diǎn)的非空單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要?jiǎng)h除

頭結(jié)點(diǎn)，并使其仍為單向循環(huán)鏈表，則可利用下述語(yǔ)句head=head->next;（）,,

A.p=head;B.p=NULL;C.p->next=head;D.head=p;

2.在一個(gè)單鏈表中p指向結(jié)點(diǎn)a,q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b,要?jiǎng)h除結(jié)點(diǎn)b,可執(zhí)

行（）。

A.p->next=q->next;B.p=q->next;

C.p->next=q;D.p->next=q;

3.以下說(shuō)法不正確的是

A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間

B.一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)

C.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)

D.線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間

4.在一個(gè)單向鏈表中，在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）；和

p->next=s;

A.p=s;B.p->next=s->next;

C.p=s->next;D.s->next=p->next;

5.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)（）稱為物理結(jié)構(gòu)。

A.數(shù)據(jù)元素間的邏輯關(guān)系

B.數(shù)據(jù)的處理方法

C.數(shù)據(jù)的性質(zhì)

D.數(shù)據(jù)的運(yùn)算

6.設(shè)有一個(gè)長(zhǎng)度為23的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。

A.16B.14C.15D.13

7.鏈表所具備的特點(diǎn)之一是（）。

A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.需要占用連續(xù)的存儲(chǔ)空間

C.插入元素的操作不需要移動(dòng)元素D.刪除元素的操作需要移動(dòng)元素

8.設(shè)一棵有8個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，度數(shù)為1的結(jié)點(diǎn)有3個(gè)，則該樹(shù)共有（）

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

A.20B.18C.17D.16

9.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.一對(duì)一B.多對(duì)多

C.一對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

10.一棵具有5層的完全二叉樹(shù)，最后一層有4個(gè)結(jié)點(diǎn)，則該樹(shù)總共有（）個(gè)結(jié)點(diǎn)。

A.14B.15C.19D.18

11.元素15,9,11,13按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）

（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.13,11,9,15B.15,9,11,13

C.13,11,15,9D.9,15,13,11

12.設(shè)主串為“FABcCDABcdEFaBc"，以下模式串能與主串成功匹配的是（)o

A.EFaBcB.ABCdE

C.DABCCD.FAbcC

13.設(shè)有一個(gè)14階的對(duì)稱矩陣A（第一個(gè)元素為采用壓縮存儲(chǔ)的方式，將其下三

角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a.g在

一維數(shù)組B中的下標(biāo)是（)o

A.9B.10C.11D.8

14.元素111,113,115,117按順序依次進(jìn)棧,則該棧的不可能輸出序列是（）（進(jìn)

棧出?？梢越惶孢M(jìn)行）。

A.117,115,113,111B.111,113,115,117

C.113,111,117,115D.117,115,111,113

15.在一棵二叉樹(shù)中,若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（

A.18B.16C.15D.17

16.以下說(shuō)法不正確的是（）o

A.棧和隊(duì)列都是線性結(jié)構(gòu)B.棧的特點(diǎn)是后進(jìn)先出

C.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出D.隊(duì)列的特點(diǎn)是先進(jìn)先出

17.設(shè)一棵哈夫曼樹(shù)共有14個(gè)非葉結(jié)點(diǎn)，則該樹(shù)總共有（）個(gè)結(jié)點(diǎn)。

A.29B.27C.30D.28

18.設(shè)有一個(gè)15階的對(duì)稱矩陣A（第一個(gè)元素為采用壓縮存儲(chǔ)的方式，將其下三

角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a」,2

在一維數(shù)組B中的下標(biāo)是（）。

A.9B.8C.7D.10

19.如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得

到的一種頂點(diǎn)序列為（）o

A.abecdfB.acfebdC.aebcfdD.aedbfc

圖1

20.如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能

得到的一種頂點(diǎn)序列為（）o

A.acedbfB.acebfdC.aebcfdD.aedfcb

二、填空題

1.隊(duì)列的特點(diǎn)之一是：元素進(jìn)、出隊(duì)的次序是:先進(jìn)。

2.序列13』1,14,12,17,15,采用冒泡排序算法，經(jīng)一趟冒泡后,序列的結(jié)果是o

3.結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。

4.對(duì)16個(gè)元素的序列用冒泡排法進(jìn)行排序，通常需要進(jìn)行_____趟冒泡。

5.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的

三項(xiàng)信息是o

6.對(duì)9個(gè)元素的一組記錄(58,35,93,20,12,78,56,41,79)進(jìn)行直接插入排

序(由小到大排序)，當(dāng)把第7個(gè)記錄56插入有序表，為尋找插入位置需比較

______次。

7.在對(duì)11個(gè)記錄的序列(12,35,9,7,2,11,56,95,37,58,60)進(jìn)行直接插入排序時(shí)，當(dāng)把

第6個(gè)記錄11插入到有序表時(shí)，為尋找插入位置，元素間需比較次。(由

小到大排列)

8.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為結(jié)構(gòu)。

9.哈希函數(shù)是記錄關(guān)鍵字的值與該記錄之間所構(gòu)造的對(duì)應(yīng)關(guān)系。

10.設(shè)有一棵深度為5的完全二叉樹(shù)，第5層上有3個(gè)結(jié)點(diǎn)，該樹(shù)共有個(gè)結(jié)點(diǎn)。

(根所在結(jié)點(diǎn)為第1層)

11.20個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行19趟冒泡，其中第10趟冒泡共需要進(jìn)行

次元素間的比較.

12.一棵二叉樹(shù)中每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,共有10個(gè)非葉結(jié)點(diǎn)，則該樹(shù)共有

____個(gè)結(jié)點(diǎn)。

13.一棵有19個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹(shù)結(jié)構(gòu)中有個(gè)指針

域?yàn)榭铡?/p>

14.序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為。

15.中序遍歷一棵樹(shù)可得到一個(gè)有序序列。

16.一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有個(gè)非葉結(jié)點(diǎn)。

17.二叉排序樹(shù)插入操作中，新插入的結(jié)點(diǎn)總是以樹(shù)的結(jié)點(diǎn)被插入的

18.遍歷二叉排序樹(shù)可得到一個(gè)有序序列。

19.廣義表的(a,(d,a,b),h,(e,((i,j),k)))深度是。

20.廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長(zhǎng)度是。

21.序列4,2,5,3,8,6,7,9,采用歸并排序算法(升序),經(jīng)一趟歸并后，序列的結(jié)果

22.廣義表的(h,c,g,a,(a,b),d,e,((i,j),k))深度是。

23.字符串a(chǎn)l="teijing",a2="tef",a3="teifang",a4="tefi"最小的

是o

24.設(shè)有串pl="ABADF"，P2="ABAFD"，P3="ABADFA”P(pán)4="ABAF”，四個(gè)串中最

小的是?

三、綜合題

1.設(shè)查找表為

序號(hào)1234567891011

序列4121819375565778586117

(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)(樹(shù)中結(jié)點(diǎn)用下標(biāo)表示)

(2)說(shuō)明成功查找到元素86需要經(jīng)過(guò)多少次比較？

(3)求在等概率條件下，成功查找的平均比較次數(shù)？

2.(1)設(shè)有數(shù)據(jù)集合{50,39,17,83,111,14,65,13,91,102,49},依次取

集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。

(2)一組記錄的關(guān)鍵字序列為(6,9,7,4,5,8),利用堆排序(堆頂元素

是最小元素)的方法建立初始堆。(要求用完全二叉樹(shù)表示)

3.

(1)一組記錄的關(guān)鍵字序列為(26,59,36,18,20,25),給出利用堆排序(堆頂

元素是最小元素)的方法建立的初始堆(要求以完全二叉樹(shù)描述)。

(2)對(duì)關(guān)鍵字序列(26,59,36,18,20,64)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割

元素，經(jīng)過(guò)一次劃分后的結(jié)果。

4.(1)如下表為一個(gè)長(zhǎng)度為10的有序表，給出按折半查找對(duì)該表進(jìn)行查找的判定樹(shù)

(2)按折半查找對(duì)該表進(jìn)行查找，求在等概率情況下查找成功的平均比較次數(shù)。

為了成功查找72，給出元素的比較次數(shù)。

序號(hào)12345678910

序列23493918256072845559

5.(1)以1,2,3,6,7,8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)

(2)給出具有相應(yīng)權(quán)重值的葉結(jié)點(diǎn)的哈夫曼編碼。

四、程序填空題

1.以下函數(shù)在a[0]到a[n-l]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回

該記錄的下標(biāo)，失敗時(shí)返回-1,完成程序中的空格

typcdcfstruct

{intkey;

}NODE;

intBinaty_Search(NODEa[],intn,intk)

intlow,mid,high;

low=O;

high=n-1;

while((1))

mid二(⑵)

if(a[mid].key==k)

return⑶

elseif((4))

low=mid+1;

else(5)；

return-1

2.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功能是

輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/

do

{printfC%d\n,\⑴):

⑵二

}whilef(3));

3.以下程序是前序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)構(gòu)中左、

右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

⑴；

⑵；

Inorder(BT->right);}

)

利用上述程序?qū)τ覉D進(jìn)行前序遍歷，結(jié)果是⑶；

4.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)構(gòu)中左、

右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。完成程序中

空格部分。

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

Inorder(BT->left);

⑴

⑵

5.順序查找算法如下，完成程序中空格部分。

intsearch(NODEa[],intn,intk)

/*在a[0],a[l]…中查找關(guān)鍵字等于k的記錄,查找成功返回記錄的下標(biāo)，失

敗時(shí)返回-1*/

{inti=0;

while(i<n&&a[i].key(1))

⑵

if(⑶)

returni;

elsereturn-1;

綜合練習(xí)一答案

一、單項(xiàng)選擇題

1.C2,A3.B4.D5.A6.C7.C8.B9.B10.C11.C

12.A13.A14.D15.D16.C17.A18.B19.D20.B

二、填空題

1.先出

2.11,13,12,14,15,17

3.樹(shù)型

4.15

5.行下標(biāo)列下標(biāo)數(shù)組元素

6.4次

7.3

8.樹(shù)形

9.存儲(chǔ)位置

10.18

11.10

12.21

13.20

14.1,3,7,18,6,9,12,13

15.二叉排序樹(shù)

16.15

17.葉

18.中序

19.4

20.6

21.2,4,3,5,6,8,7,9

22.3

23.a2

24.Pl

三、綜合題

1.

(1)55

1885

4196586

123777117

(2)3次

(3)平均查找長(zhǎng)度=(1+2*2+3*4+4*4)/11=3

圖5

⑵4,5,7,9,6,8

圖6

(1)18,20,25,59,26,36

圖7

(2)20,18,26,36,59,64

圖8

⑵(1+2*2+3*4+4*3)/10=29/104次

5.(1)

圖9

(2)

10000

20001

3001

601

710

811

四、程序填空題

1.(1)low<=high

(2)(low+high)/2

(3)mid;

(4)a[mid].key<k

(5)high=mid-l;

2.

(1)p->data

(2)p=p->next

(3)p!=NULL

3.

(1)printf(,BT->data)

(2)Inorder(BT->left)

(3)abdfec

4.

(1)Inorder(BT->right)

(2)printf(“枇”，BT->data)

(1)!=k

⑵i++；

(3)a[i].key==k

綜合練習(xí)二

一、單項(xiàng)選擇題

1.設(shè)頭指針為head的非空的單向循環(huán)鏈表，指針p指向尾結(jié)點(diǎn)，則滿足表達(dá)式（）

為真。

A.p->next==NULLB.p==NULLC.p->next==headD.p==head

2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。

A.數(shù)據(jù)處理的方法C.相關(guān)算法

D.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示

3.一種邏輯結(jié)構(gòu)（）。

A.可以有不同的存儲(chǔ)結(jié)構(gòu)B.只能有唯一的存儲(chǔ)結(jié)構(gòu)

C.是指某一種數(shù)據(jù)元素之間的存儲(chǔ)關(guān)系D.是指某一種數(shù)據(jù)元素的性質(zhì)

4.在一個(gè)頭指針為head的單向鏈表中，p指向尾結(jié)點(diǎn)，要使該鏈表成為單向循環(huán)鏈表

可執(zhí)行（

A.p=head->next;B.head->next=p;

C.head->next=p->next;D.p->next=head;

5.鏈表所具備的特點(diǎn)之一是（

A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間

C.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)

6.元素111,113,115,117按順序依次進(jìn)棧,則該棧的不可能輸出序列是（）（進(jìn)

棧出?？梢越惶孢M(jìn)行）。

A.117,115,113,111B.111,113,115,117

C.117,115,111,113D.113,111,117,115

7.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.一對(duì)一B.一對(duì)多

C.多對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

8.以下說(shuō)法正確的是（）。

A.棧的特點(diǎn)是先進(jìn)后出

B.棧的特點(diǎn)是先進(jìn)先出

C.隊(duì)列的特點(diǎn)是先進(jìn)后出

D.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出

9.在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）。

A.p->next=s;s->next=p->nextB.p->next=s->next;

C.p=s->nextD.s->next=p->next;p->next=s;

10.設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為ai,i）,采用壓縮存儲(chǔ)的方式，將其下三

角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素S6.2

在一維數(shù)組B中的下標(biāo)是（）。

A.24B.17C.16D.23

11.元素11,13,15,17按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）

（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.17,15,13,11B.11,13,15,17

C.17,15,11,13D.13,11,17,15

12.設(shè)一棵有2n+l個(gè)結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,則該樹(shù)共有（）

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

A.nB.n+1C.n+2D.n-1

13.設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為ai,D,采用壓縮存儲(chǔ)的方式，將其下三角

部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a.%2在一

維數(shù)組B中的下標(biāo)是（）。

A.11B.12C.13D.10

14.已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能

得到的一種頂點(diǎn)序列為（）。

A.abecdfB.aecbdfC.aebcfdD.aedfcb

15.設(shè)一棵哈夫曼樹(shù)共有11個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有（）個(gè)葉結(jié)點(diǎn)。

A.22B.10C.11D.12

16.線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。

A.關(guān)鍵字有序的順序B.順序C.鏈接D.二叉樹(shù)

17.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。

A.7B.5C.6D.8

18.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。

A.7B.5C.6D.8

19.已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得

到的一種頂點(diǎn)序列為（）.

A.abecdfB.acfebdC.aebcfdD.aedfcb

20.對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行

()。

A.e=top->next;top->data=e;B.top=top->next;e=top->data;

C.e=top->data;top=top->next;D.top=top->next;e=data;

二、填空題

1.字符串a(chǎn)l="BEIJING",a2="BEF",a3="BEFANG",a4="BEI”最小的

是。

2.數(shù)組a經(jīng)初始化chara[]="English”;a[7]中存放的是。

3.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為。

4.設(shè)有串pl="ABADF"，P2="ABAFD"，P3="ABADFA"P4="ABAF”，四個(gè)串中最大的是

5.設(shè)有一個(gè)長(zhǎng)度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為。

6.在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為。

7.在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為。

8.設(shè)有一個(gè)長(zhǎng)度為20的順序表，要插入一個(gè)元素，并作為第8個(gè)元素，需移動(dòng)元素的個(gè)

數(shù)為。

9.設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,則該樹(shù)共有

________個(gè)結(jié)點(diǎn)。

10.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為結(jié)構(gòu)。

11.在對(duì)一組序列(45,29,87/2,6,63,55,37,78)進(jìn)行直接插入排序時(shí)，當(dāng)把第8個(gè)記錄37插

入到有序表時(shí)，為尋找插入位置需比較次。(由小到大排序)

12.設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有個(gè)結(jié)點(diǎn)。

(根所在結(jié)點(diǎn)為第1層)

13.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_______趟冒泡。

14.一棵二叉樹(shù)中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,則該樹(shù)共有

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

15.一棵有21個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)，該樹(shù)中有個(gè)葉結(jié)點(diǎn)。

16.在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插

入到有序表時(shí)，為尋找插入位置需比較次。(由小到大排序

17.遍歷二叉排序樹(shù)可得到一個(gè)有序序列。

18.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行次元素間的比較。

19.廣義表(a,(a,b),d,e,((i,j),k))的長(zhǎng)度是。

20.一棵有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有個(gè)結(jié)點(diǎn)。

21.廣義表的(a,(a,b),d,e,((i,j),k))深度是。

22.中序遍歷可得到一個(gè)有序序列。

23.序列14,12,15,13,18,16,采用冒泡排序算法(升序),經(jīng)一趟冒泡后，序列的結(jié)果

是。

24.廣義表((a,b),d,e,((i,j),k))的長(zhǎng)度是。

三、綜合題

1.設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120),元素的下標(biāo)依次為1,2,3,……-11.

(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)(樹(shù)中結(jié)點(diǎn)用下標(biāo)表示)

(2)說(shuō)明成功查找到元素40需要經(jīng)過(guò)多少次比較？

(3)求在等概率條件下，成功查找的平均比較次數(shù)？

2.(1)設(shè)有數(shù)據(jù)集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合

中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。

(2)一組記錄的關(guān)鍵字序列為(5,8,6,3,4,7),利用堆排序(堆頂元素是最

小元素)的方法建立初始堆。(要求用完全二叉樹(shù)表示)

3.(1)一組記錄的關(guān)鍵字序列為(47,80,57,39,41,46),給出利用堆排序(堆頂

元素是最小元素)的方法建立的初始堆(要求以完全二叉樹(shù)描述

(2)對(duì)關(guān)鍵字序列(47,80,57,39,41,85)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割

元素，經(jīng)過(guò)一次劃分后的結(jié)果。

(3)如圖3所示的二叉樹(shù)，給出其前序遍歷序列。

圖3

4.(1)以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)

(2)給出上述哈夫曼樹(shù)葉結(jié)點(diǎn)的哈夫曼編碼。

(3)一組記錄的關(guān)鍵字序列為(37,70,47,29,31,85),利用快速排序，以第一

個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。(由小到大排序)

四、程序填空題

1.以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)構(gòu)中左、

右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。

voidInorder(structBTreeNode*BT)乙

if(BT!=NULL){<7)^(

Inorder(BT->left);}1

——；0O亡

利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是(3)__________________:圖4

2.設(shè)線性表為(6,10,16,4),以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出

鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。

#defineNULL0

voidmain()

{NODEa,b,c,d,*head,*p;

a.data=6;

b.data=10;

c.data=16;

d.data=4;/*d是尾結(jié)點(diǎn)*/

head=(1);

a.next=&b;

b.next=&c;

c.next=&d;

(2);/*以上結(jié)束建表過(guò)程*/

p=head;/*p為工作指針，準(zhǔn)備輸出鏈表*/

do

Srintfr%d\n”,(3))：

}while((5));

)

3.以下冒泡法程序?qū)Υ娣旁赼[l],a[2],……，a[n]中的序列進(jìn)行排序，完成程序中

的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。

voidbsort(NODEa[],intn)

{NODEtemp;

inti,j,flag;

for(j=l;(1)；j++)；

{flag=O;

for(i=l;(2);i++)

if(a[i].key>a[i+l].key)

{flag=l;

temp=a[i];

(3);

(4);

)

if(flag==0)break;

)

)

程序中flag的功能是(5)_______________________

4.以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、

右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）.

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

___LU_______;

(2)_____________;

Inorder(BT->right);}

)

利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是(3):

綜合練習(xí)二答案

一、單項(xiàng)選擇題

1.C2.D3.A4.D5.C6.C7.A8.A9.D10.B

11.C12.B13.B14.B15.D16.A17.A18.A19.D20.C

二、填空題

1.a2

2.字符串的結(jié)束符

3.物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

4.p2

5.14

6.2i+l

7.2i

8.13

9.2n-l

10.圖狀

11.5

12.12

13.n-1

14.n+1

15.11

16.3

17.中序

18.n-j

19.5

20.2n-l

21.3

22.二叉排序樹(shù)

23.12,14,13,15,16,18

24.4

三、綜合題

圖6

Q)4次

(3)ASL=(1+2*2+3*4+4*4)711=3

圖7

(2)3,4,6,8,5,7

3(1)39,41,46,80,47,57

(2)41,39,47,57,80,85

(3)abdefcg

圖10

(2)

2：0000

40001

5001

810

911

1001

(3)31,29,37,47,70,85

四、程序填空題

1.

(1)printf(“枇”，BT->data)

(2)Inorder(BT->right)

(3)dbeafc

2.

(1)&a

(2)d->next=NULL

(3)p->data

(4)p=p->next

(5)p!=NULL

(1)j<=n-l

(2)i<=n-j

(3)a[i]=a[i+l]

(4)a[i+l]=temp

(5)當(dāng)某趟冒泡中沒(méi)有出現(xiàn)交換則已排好序，結(jié)束循環(huán)

(1)Inorder(BT->left)

(2)printf("%c”，BT->data)

(3)bedafc

綜合練習(xí)三

一、單項(xiàng)選擇題

1.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和()?

A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素的類型

C.相關(guān)算法D.數(shù)據(jù)元素間的關(guān)系的表示

2.設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要

刪除第一個(gè)結(jié)點(diǎn)，則可利用下述語(yǔ)句head=head->next;和()。

A.p=head;B.p=NULL;C.p->next=head;D.head=p;

3.樹(shù)狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.一對(duì)一

C.多對(duì)多D.一對(duì)多

4.以下說(shuō)法正確的是（）?

A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間

B.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)

C.一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)

D.線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間

5.設(shè)有一個(gè)長(zhǎng)度為26的順序表，要插入一個(gè)元素,并使它成為新表的第6個(gè)元素，需

移動(dòng)元素的個(gè)數(shù)為（）。

A.21B.22C.20D.19

6.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)（）稱為物理結(jié)構(gòu)。

A.數(shù)據(jù)的處理方法B.數(shù)據(jù)的性質(zhì)

C.數(shù)據(jù)的運(yùn)算D.數(shù)據(jù)元素間的邏輯關(guān)系

7.頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p所指向尾結(jié)點(diǎn)，要使該鏈表成為

不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，可執(zhí)行head=head->nex;和（）。

A.p=head->nextB.head->next=p

C.head->next=p->nextD.p->next=head;

8.順序表所具備的特點(diǎn)之一是（）o

A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.不需要占用連續(xù)的存儲(chǔ)空間

C.插入元素的操作不需要移動(dòng)元素D.刪除元素的操作不需要移動(dòng)元素

9.元素111,113,115,117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)

棧出?？梢越惶孢M(jìn)行）。

A.117,115,113,111B.111,113,115,117

C.117,115,111,113D.113,111,117,115

10.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.一對(duì)一B.一對(duì)多

C.多對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

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

A.棧的特點(diǎn)是先進(jìn)先出

B.棧的特點(diǎn)是先進(jìn)后出

C.隊(duì)列的特點(diǎn)是先進(jìn)后出

12.元素20,14,16,18按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）

（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.18,16,14,20

B.20,14,16,18

C.18,16,20,14

D.14,20,18,16

D.棧和隊(duì)列的特點(diǎn)都是后進(jìn)后出

13.設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為aiQ,采用壓縮存儲(chǔ)的方式，將其下三

角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣元素a612

在一維數(shù)組B中的下標(biāo)是（

A.21B.17C.28D.23

14.設(shè)有一個(gè)12階的對(duì)稱矩陣A（左上角第一個(gè)元素為ai,】），采用壓縮存儲(chǔ)的方式，將

其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素

a5.4在一維數(shù)組B中的下標(biāo)是（）。

A.14B.12C.13D.11

15.設(shè)有串pl="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF"，以下四個(gè)串中最

大的是（）.

A.p3B.p2C.plD.p4

16.設(shè)有一個(gè)長(zhǎng)度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。

A.25B.14C.15D.23

17.數(shù)組a經(jīng)初始化chara[]="English”;a[7]中存放的是（）。

A.字符串的結(jié)束符B.字符h

C.、'h"D.變量h

18.在一棵二叉樹(shù)中，若編號(hào)為5的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。

A.12B.9C.11D.10

19.設(shè)主串為“ABcCDABcdEFaBc"，以下模式串能與主串成功匹配的是（）。

A.BedB.BCdC.ABCD.Abe

20.一棵具有5層的完全二叉樹(shù)，最后一層有4個(gè)結(jié)點(diǎn)，則該樹(shù)總共有（）個(gè)結(jié)點(diǎn)。

A.14B.15C.19D.18

21.在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為（）.

A.2i+lB.21-1C.2iD.2i+2

22.如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種

頂點(diǎn)序列為（）。

A.abcdfgeB.abcedfgC.aebfedgD.abcfgde

圖1

23.如圖2所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得

到的一種頂點(diǎn)序列為（）。

A.abecdfB.aecbdfC.aebefdD.aedfeb

圖2

24.字符串''abcd321ABCDz/的子串是（）。

A."21ABC"B."abcABCD"

C.abcDD.、'321a"

25.線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。

A.鏈接B.順序C.關(guān)鍵字有序的順序D.二叉樹(shù)

26.數(shù)組a經(jīng)初始化chara[]="English"；a[l]中存放的是（）。

A.字符nB.字符E

C.、'n"D."E"

27.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。

A.7B.5C.6D.8

28.如圖3所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得

到的一種頂點(diǎn)序列為（）。

A.abecdfB.acfebdC.aebcfdD.aedfcb

29.下圖的拓?fù)湫蛄惺牵ǎ?/p>

A.52346

C.56234

30.下圖的拓?fù)湫蛄惺牵ǎ?

A.52346B.52364

C.56423D.23456

二、填空題

1.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為結(jié)構(gòu)。

2.棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是:先進(jìn)。

3.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行次元素間的比較。

4.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的三項(xiàng)信息

是o

5.中序遍歷樹(shù)可得到一個(gè)有序序列。

6.在對(duì)10個(gè)記錄的序列(9,35,19,77,2,10,53,45,27,68)進(jìn)行直接插入排序時(shí)，當(dāng)把第

6個(gè)記錄10插入到有序表時(shí)，為尋找插入位置，元素間需比較次。

(按升序排序)

7.待排序的序列為8,341,2,5,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列

為()。

8.字符串a(chǎn)l="beijing",a2="bef",a3="beifang",a4="befi"最小的

是o

9.廣義表(包5),(1,6,(。/),1;))的長(zhǎng)度是。

10.10個(gè)元素進(jìn)行冒泡法排序，，其中第5趟冒泡共需要進(jìn)行次元素間的比較。

11.廣義表的(c,a,(a,b),d,e,((i,j),k))深度是。

12.遍歷一棵二叉排序樹(shù)可得到一個(gè)有序序列。

13.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10行10列的稀疏矩陣A共有

95個(gè)零元素，其相應(yīng)的三元組表共有個(gè)元素。

14.廣義表(c,(a,b,c),(d,e,f),((i,j),k))的長(zhǎng)度是.

15.在對(duì)一組記錄(50,49,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記

錄65插入到有序表時(shí)，為尋找插入位置需比較次。

16.廣義表的(c,(b,a,b),f,e,((i,j),k))深度是.

17.一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，該樹(shù)中總共有個(gè)結(jié)點(diǎn)。

18.序列4,2,5,3,8,6,采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是。

19.設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有個(gè)結(jié)點(diǎn)。

(根所在結(jié)點(diǎn)為第1層)。

20.待排序的序列為8,3,4,125,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列

為

21.設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為。

22.線性表用方式存儲(chǔ)可以隨機(jī)訪問(wèn)。

23.有以下程序段

chara[]="English";

char*p=a;intn=0;

while(*p!=’\0'){n++;p++;}結(jié)果中，n的值是。

24.順序表,,6,5,1,2,4,3,8,7經(jīng)過(guò)一趟(1,1)歸并后的結(jié)果序列為_(kāi)_______。

三、綜合題

1.有一個(gè)長(zhǎng)度為11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下標(biāo)依次為

1,2,3,……,11,按折半查找對(duì)該表進(jìn)行查找。

(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)。

(2)說(shuō)出成功查找到元素56”需要依次經(jīng)過(guò)與哪些元素的比較？

(3)說(shuō)出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)？

2.設(shè)查