國開數(shù)據(jù)結(jié)構(gòu)（本）期末復(fù)習(xí)題

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

2017年5月

綜合練習(xí)一

一、單項選擇題

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

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

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

2.在一個單鏈表中p指向結(jié)點a,q指向結(jié)點a的直接后繼結(jié)點b,要刪除結(jié)點b,可執(zhí)

行（）。

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

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

3.以下說法不正確的是

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

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

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

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

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

p->next=s;

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

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

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

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

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

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

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

6.設(shè)有一個長度為23的順序表，要刪除第8個元素需移動元素的個數(shù)為（）。

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

7.鏈表所具備的特點之一是（

A.可以隨機訪問任一結(jié)點B.需要占用連續(xù)的存儲空間

C.插入元素的操作不需要移動元素D.刪除元素的操作需要移動元素

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

個結(jié)點。

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

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

A.一對一B.多對多

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

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

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è)有一個14階的對稱矩陣A（第一個元素為熱力，采用壓縮存儲的方式，將其下三

角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素近3在

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

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

14.元素111,113,1：5,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.在一棵二叉樹中,若編號為8的結(jié)點存在右孩子，則右孩子的順序編號為（

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

16.以下說法不正確的是（）。

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

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

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

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

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

角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素&L2

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

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

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

到的一種頂點序列為（）＜，

A.cibecdfB.acfebdC.&ebcfdD.aedbfc

圖I

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

得到的一種頂點序列為（）。

A.acedbfB.acebfdC.aebcfdD.aedfcb

二、填空題

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

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

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

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

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

三項信息是O

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

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

______次。

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

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

小到大排列)

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

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

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

(根所在結(jié)點為第I層)

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

次元素間的比較。

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

____個結(jié)點。

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

域為空。

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

15.中序遍歷一棵樹可得到一個有序序列。

16.一棵有16個葉結(jié)點的哈夫曼樹，則該樹共有個非葉結(jié)點。

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

18.遍歷二叉排序樹可得到一個有序序列。

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

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

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

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

23.字符串a(chǎn)l:"teijing”,a2=wtefz,,a3="eifang",a4:"tefi”最小的

是o

24.設(shè)有串pl="ABADF"，P2="ABAFD”,P3="ABADFA"P4="ABAF”，四個串中最

小的是o

三、綜合題

1.設(shè)查找表為

序號1234567891011

序列4121819375565778586117

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

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

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

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

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

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

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

3.

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

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

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

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

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

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

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

序號1234567s910

序列23493918256072845559

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

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

四、程序填空題

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

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

typedefstruct

{intkey;

}NODE;

intBinar5_Search(T\iODEa[],intn,intk)

intlow,mid,high;

low=0;

high=n-1;

while(JU)

mid=(⑵)

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

return⑶

elseif((4))

low=mid+l;

else(5)：

}

return-1

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

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

#defineNULL0

voidmain()

{NODE*head,*p;

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

do

{printfCt%d\n,\(1)):

-(21_____；

lwhile(t3)):

)

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

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

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL)(

⑴：

(2):

Inorder(BT—>right);}

)

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

圖3

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

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

空格部分。

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

Inorder(BT->lett);

⑴

(2)

)

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

intsearch(NODEa[1Jntn,intk)

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

敗時返回-1*/

{inti=0;

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

⑵

if((3))

returni;

elsereturn-1;

)

綜合練習(xí)一答案

一、單項選擇題

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

12.A13.A14.1)15.I)16.C17.A18.B19.1)20.B

二、填空題

1.先出

2.11,13,12,14,15,17

3.樹型

4.15

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

6.4次

7.3

8.樹形

9.存儲位置

10.18

11.10

12.21

13.20

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

15.二叉排序樹

16.15

17.葉

18.中序

19.4

20.6

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

22.3

23.a2

24.Pl

三、綜合題

1885

4196586

123777117

⑵3次

(3)平均查找長度=(14-2*2+3*4+4*4)/11=3

2.

(1)

圖5

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

圖6

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

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

⑵(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(4<%cw,BT->data)

(2)Inorder(BT->left)

(3)abdfec

4.

(1)Inorder(BT->right)

(2)printf(,BT->data)

⑴！二k

(2)i++;

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

綜合練習(xí)二

一、單項選擇題

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

為真。

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

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

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

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

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

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

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

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

可執(zhí)行（）。

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

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

5.鏈表所具備的特點之一是（

A.可以隨機訪問任一結(jié)點B.占用連續(xù)的存儲空間

C.插入刪除元素的操作不需要移動元素結(jié)點D.可以通過下標(biāo)對鏈表進(jì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.一對一B.一對多

C.多對多I）,每一個元素都有一個直接前驅(qū)和一個直接后繼

8.以下說法正確的是（）<,

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

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

C.隊列的特點是先逃后出

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

9.在一個單向鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(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è)有一個20階的對稱矩陣A（第一個元素為ar）,采用壓縮存儲的方式，將其下三

角部分以行序為主序存儲到i維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a6,2

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

A.24B.17C.16【）.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個結(jié)點的二叉樹，除葉結(jié)點外每個給點度數(shù)都為2,則該樹共有（）

個葉結(jié)點。

A.nB.n+1C.n+2I）,n-1

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

部分以行序為主序存諸到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素AU在一

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

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

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

得到的一種頂點序列為（）。

A.abecdfB.aecbdfC.aebcfdI）,aedfcb

圖1

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

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

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

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

17.一棵具有38個結(jié)點的完全二叉樹，最后一層有（）個結(jié)點。

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

18.一棵具有38個結(jié)點的完全二叉樹，最后一層有（）個結(jié)點。

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

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

到的一種頂點序列為（

A.abecdfB.acfebdC.aebcfdD.aedfcb

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

()(,

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

C.c=top->data;top=top->ncxt;D.top=top->ncxt;c=data;

二、填空題

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

是o

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

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

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

5.設(shè)有一個長度為22的順序表，要刪除第8個元素需移動元素的個數(shù)為c

6.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，貝J右孩子的順序編號為。

7.在一棵二叉樹中，若編號為i的結(jié)點存在左孩子，貝!左孩子的順序編號為。

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

數(shù)為。

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

________個結(jié)點。

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

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

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

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

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

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

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

個葉結(jié)點。

15.一棵有21個結(jié)點的哈夫曼樹，該樹中有個葉結(jié)點。

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

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

17.遍歷二又排序樹可得到一個有序序列。

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

19.廣義表(a,(a,b),d,e,((i,j),k))的長度是______°

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

21.廣義表的(2,缸口，<1,0,(3)水))深度是o

22.中序遍歷可得到一個有序序列。

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

是O

24.廣義表(年力)評，?,(。/),1<))的長度是o

三、綜合題

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3

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

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

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

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

四、程序填空題

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

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

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

#defineNULL0

voidmain()

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

a.data=6;

b.data=l();

c.data=16;

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

head=(1);

a.ncxt=&b;

b.next=&c;

c.nexl二&d;

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

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

do

{printf^%d\n,\(3));

(4)___________;

)whilef(5));

)

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

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

voidbsort(NODEa[],intn)

{NODEtemp;

inti,j,flag;

for(j=l;(l)；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.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、

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

voidInorder(structBTreeNode*BT)

if(BT!=NULL){

____m__________:

(2)_____________；

Inorder(BT->right);)

)

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

綜合練習(xí)二答案

一、單項選擇題

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

11.C12.B13.B14.B15.I)16.A17.A18.A19.D20.C

二、填空題

1.a2

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

3.物理結(jié)構(gòu)(存儲結(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.二叉排序樹

23.12,14,13,15,16,18

24.4

三、綜合題

圖6

(2)4次

(3)ASL=(I+2*2+3*4+4*4)/11=3

圖7

(2)3,468,5,7

圖8

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

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

(3)abdefcg

4.

(1)

圖10

(2)

2：0000

40001

5001

810

9II

1001

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

四、程序填空題

1.

(1)printf(w%cw,BT->data)

(2)Inorder(BT->right)

(3)dbeafc

2.

(1)

(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)某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán)

4.

(1)Inorder(BT->left)

(2)printf(a%cw,BT->data)

(3)bedafc

綜合練習(xí)三

一、單項選擇題

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

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

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

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

刪除第一個結(jié)點，則可利用下述語句head=head-〉next;和（）。

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

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

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

C.多對多I）.一對多

4.以下說法正確的是（）。

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

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

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

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

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

移動元素的個數(shù)為（）。

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

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

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

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

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

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

A.p=hcad->nextB.head->ncxt=p

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

8.順序表所具備的特點之一是（）。

A.可以隨機訪問任一結(jié)點B.不需要占用連續(xù)的存儲空間

C.插入元素的操作不需要移動元素D.刪除元素的操作不需要移動元素

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

棧出棧可以交替進(jìn)行）。

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

C.117.115.111.113D.113,111.117.I15

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

A.一對一B.一對多

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

11.以下說法正確的是（

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

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

C.隊列的特點是先進(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.棧和隊列的特點都是后進(jìn)后出

13.設(shè)有一個20階的對稱矩陣A（第一個元素為①」），采用壓縮存儲的方式，將其下三

角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a3.2

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

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

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

其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素

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

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

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

大的是（）。

A.p3B.p2C.plD.p4

16.設(shè)有一個長度為22的順序表，要刪除第8個元素需移動元素的個數(shù)為（）。

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

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

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

C.、'h"D.變量h

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

A.12B.9C.11I）.10

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

A.BedB.BCdC.ABCD.Abe

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

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

21.在一棵二叉樹中，若編號為i的結(jié)點存在左孩子，則左孩子的順序編號為（）。

A.2i+lB.2i-lC.2iD.2i+2

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

頂點序列為（）。

A.abcdfgeB.abcedfgC.aebfedgD.abcfgde

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

到的一種頂點序列為（）。

A.abecdfB.aecbdfC.aebefdD.aedfeb

圖2

24.字符串“abcd321ABCD”的子用是（）。

A.”21ABC"B."abcABCD"

C.abcDD."32la”

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

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

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

A.字符nB.字符E

.nD.E

27.一棵具有38個結(jié)點的完全二叉樹，最后一層有（）個結(jié)點。

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

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

到的一種頂點序列為（）。

A.abecdfB.acfebdC.&ebcfdD.aedfcb

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

A.52346

C.56234D.23564

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

A.52346B.52364

二、填空題

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

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

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

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

是。

5.中序遍歷樹可得到一個有序序列。

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

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

(按升序排序)

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

為()。

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

是O

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

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

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

12.遍歷一帙一叉排序樹可得到一個有序序列。

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

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

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

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

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

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

17.一棵有5個葉結(jié)點的哈夫曼樹，該樹中總共有個結(jié)點。

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

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

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

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

為?。

21.設(shè)有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為。

22.線性表用方式存儲可以隨機訪問。

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)過一趟(1,1)歸并后的結(jié)果序列為________。

三、綜合題

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

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

(I)畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹。

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

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

2.設(shè)查找表為

序號1234567891011

序列8162223415969818990121

(I)畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹。

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

(3)說明不成功杳找元素82,依次與哪些元素進(jìn)行了比較，需要經(jīng)過多少次比較？

3.(1)一組記錄的關(guān)鍵字序列為(57,90,67,50,51,56),利用堆排序(堆頂元素是

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

(2)對關(guān)鍵字序列(56,51,71,54,46,106)利用快速排序，以第一個關(guān)鍵字為分割元素,

給出經(jīng)過一次劃分后結(jié)果。

(3)一組記錄的關(guān)鍵字序列為(60,47,80,57,39,41,46,30),利用歸并排序的

方法，分別給出(1,1)歸并、(2,2)歸并、(4,4)歸并的結(jié)果序列。

4.

(1)一組記錄的關(guān)鍵字序列為(36,69,46,28,30,35),給出利用堆排序(堆頂

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

(2)對關(guān)犍字序列(36,69,46,28,30,74)采用快速排序，給出以第一個關(guān)鍵字為分割

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

(3)設(shè)有數(shù)據(jù)集合{30,73,101,4,8,9281},依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。

四、程序填空題

1.設(shè)線性表為(16,20,26,24),以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head,

以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data。

Structnode

{intdata:

structnode*ncxt;

)；

typedefstructnodeNODE:

#defineNULL0

voidmain()

{NODE*head,*p;

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

do

{printf("％d\n”,⑴):

—⑵