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

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

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

一、單項選擇題

■針對線性表，在存儲后如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用（D）

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

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表

2.線性表采用鏈式存儲時，其地址（C）。

A.一定是不連續(xù)的B.必須是連續(xù)的

C.可以連續(xù)也可以不連續(xù)D.部分地址必須是連續(xù)的

■數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（D）結(jié)構(gòu)。

A.物理B.存儲C.邏輯與物理D.邏輯

4.帶頭結(jié)點的單向鏈表的頭指針為head,該鏈表為空的判定條件是（C）的值為真。

A.head==NULLB.head->next==head

C.head->next==NULLD.head==head->next

5.以下特征中，（D）不是算法的特性。

A.有窮性B.確定性C.可行性D.有0個或多個輸出

6.設(shè)順序存儲的線性表長度為n,對于插入操作,設(shè)插入位置是等概率的，則插入一個

元素平均移動元素的次數(shù)為（A）。

A.n/2B.nC.n-1D.n-i+1

■設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i

個元素），則移動元素個數(shù)為（A）。

A.n-i+1B.n-iC.n-i-lD.i

8.一個棧的進棧序列是5,6,7,8,則棧的不可能的出棧序列是（A）（進出棧操

作可以交替進行）

A.5,8,6,7B.7,6,8,5

C.7,6,5,8D.8,7,6,5

■棧的插入刪除操作在（D）進行。

A.棧底B.任意位置C.指定位置D.棧頂

10.棧和隊列的相同點是（D）。

A.都是后進先出B.都是后進后出

C.邏輯結(jié)構(gòu)與線性表不同

D.邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表

■以下說法正確的是（C）。

A.棧的特點是先進先出，隊列的特點是先進后出B.棧和隊列的特點都是先進后出

C.棧的特點是先進后出，隊列的特點是先進先出D.棧和隊列的特點都是先進先出

■在C語言中，利用數(shù)組a存放字符串“Hello"，以下語句中正確的是（AD）。

A.chara[10]="Hello”;B.chara[10];a="Hello”；

C.chara[10]='Hello';D.chara[10]={'H','e',T,T,'o'};

■元素2,4,6,8按順序依次進棧，則該棧的不可能輸出序列是（D）（進棧出棧

可以交替進行）。

A.8,6,4,2B.2,4,6,8

C.4,2,8,6D.8,6,2,4

14.設(shè)有一個15階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲

到一維數(shù)組b中。（矩陣A的第一個元素為a,,P數(shù)組b的下標從1開始），則數(shù)組元

素b[13]對應(yīng)A的矩陣元素是（A）。

A.a5.3B.a6.4C.a7,2D.%8

15.設(shè)有一個15階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主序

存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素ai.e在一維數(shù)組B中的下

標是（C

A.42B.13C.27D.32

16?一棵完全二叉樹共有30個結(jié)點，則該樹一共有（D）層（根結(jié)點所在層為第一層）。

A.6B.4C.3D.5

■串函數(shù)StrCmp（"d”，“D”）的值為（B）。

A.0B.1C.-1D.3

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

A.連通圖G的生成樹中不一定包含G的所有頂點

B.連通圖G的生成樹中定要包含G的所有邊

C.連通圖G的生成樹一定是唯一的

D.連通圖G一定存在生成樹

■在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（D

A.2iB.2i-lC.2i+2D.2i+l

20.對二叉排序樹進行（C）遍歷，遍歷所得到的序列是有序序列。

A.按層次B.前序C.中序D.后序

■設(shè)一棵有n個結(jié)點采用鏈式存儲的二叉樹，則該樹共有（D）個指針域為空?

A.2nB.2n+lC.2n+2D.n+1

22.以下排序算法中，在一趟排序過程中，除了其它相關(guān)操作外，只進行一次元素間的

交換的算法是（A

A.直接選擇B.冒泡C.直接插入D.折半插入

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

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

A.abcedfB.abcefdC.aebcfdD.acfdeb

24.對長度為n的線性表進行h找，在等概率情況下，平均查找長度為（B）o

A.nB.（n+1）/2C.2nD.n-1

在有序表｛1,3,8,13,33,42,46,63,76,78,86,97,100｝中，用折半查找

值86時，經(jīng)（D）次比較后查找成功。

A.6B.3C.8D.4

26.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為

(A)。

A.acfgedb

B.aedcbgf

C.acfebdg

D.aecbdgf

■有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功

的平均比較次數(shù)為（A）。

A.29/10B.31/10C.26/10D.29/9

28.一棵哈夫曼樹有12個葉子結(jié)點（終端結(jié)點），該樹總共有（C）個結(jié)點。

A.22B.21C.23D.24

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

鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（A）?

A.31,29,37,47,70,85B.29,31,37,47,70,85

C.31,29,37,70,47,85D.31,29,37,85,47,70

30.隊列的刪除操作在（B）進行。

A.隊頭B.隊尾C.隊頭或隊尾D.在任意指定位置

得分評卷人

二、填空題

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

2.設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next,指針p指向尾結(jié)點，現(xiàn)

要使p指向第一個結(jié)點，可用語句。

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

4.要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)點的單向循

環(huán)鏈表，若結(jié)點的指針域為next,頭指針為head,尾指針為p,,則可執(zhí)行head=head->

next;p->next=head°

■在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向結(jié)點的直接前驅(qū)，另一個指向結(jié)

點的直接后驅(qū)。

6.設(shè)有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x保存出棧結(jié)點的值，

棧結(jié)點的指針域為next,數(shù)據(jù)域為data,則可執(zhí)行x=hsndata；和

hs=hs->next；

7.設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點，且有p?>next==NULL,

通過操作p->next=head,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。

8.循環(huán)隊列的最大存儲空間為MaxSize,隊頭指針為f,隊尾指針為r,當

（q->r+1）%MaxSize=q->f時表明隊列已滿。

■從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用X保存被刪結(jié)點的值，可執(zhí)行

x=h->data;和h=h->next?（結(jié)點的指針域為next）

10.程序段intcount=0;char*s="ABCD";

while（*s!='\0'）{s++;count++;}

執(zhí)行后count=4

■兩個串相等的充分必要條件是串長度相等且對應(yīng)位置的字符相等

12.一棵二叉樹總結(jié)點數(shù)為11,葉結(jié)點數(shù)為5,該樹有__4個雙分支結(jié)點—2.

個單分支結(jié)點。

■對二叉樹的遍歷可分為、中序、后序

層次四種不同的遍歷次序。

14.設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉節(jié)點的雙親結(jié)

點的編號為9,該完全二叉樹一共有—18—個結(jié)點。

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

____2n-l一個結(jié)點。

16.雙向循環(huán)鏈表中，p指向表中某結(jié)點，則通過p可以訪問到p所指結(jié)點的直接后繼結(jié)

點和直接前驅(qū)結(jié)點，這種說法是—正確的（回答正確或不正確）。

17.一棵有14個結(jié)點的完全二叉樹，則它的最高層上有_7個結(jié)點。

18.棧和隊列的操作特點分別是.先進后出（后進先出）和先進先出（后進后出）。

19.如圖2所示的二叉樹，其先序遍歷序列為abdgcefhi。

20.折半查找只適用于順序存儲結(jié)構(gòu)存儲的有序表。

■哈希函數(shù)是記錄關(guān)鍵字值與該記錄一存儲地址之間所構(gòu)造的對應(yīng)關(guān)系。

22.深度為k的二叉樹最多有（24）-1結(jié)點。

23.二叉樹排序中任一棵子樹都是二叉排序樹，這種說法是正確的。（回答正確或

不正確）

串的兩種最基本的存儲方式是順序存儲—和鏈式存儲________

得分評卷人

三、綜合題

1.設(shè)一組記錄的關(guān)鍵字序列為（49,83,59,41,43,47）,采用堆排序算法完成以下

操作：（要求小根堆，并畫出中間過程）

（1）以二叉樹描述6個元素的初始堆

（2）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個元素、4個元素的堆

2.

設(shè)有一個不帶頭結(jié)點的單向鏈表，頭指針為head,結(jié)點類型為NODE,每個結(jié)點包含一

個數(shù)據(jù)域data和一個指針域next,該鏈表有兩個結(jié)點，p指向第二個結(jié)點（尾結(jié)點），按以下

要求寫出相應(yīng)語句（不要求完整程序，（1）＞（2）、（3）、（4）是一個連續(xù)的過程）。

（1）新開辟?個結(jié)點，使指針s指向該結(jié)點，結(jié)點的數(shù)據(jù)成員data賦值為1

（2）把該結(jié)點插入鏈表的尾部，釋放指針s的指向

（3）刪除鏈表的第一個結(jié)點

（4）已知pi指向另一個新結(jié)點，把它插入到p所指結(jié)點和尾結(jié)點之間

3.設(shè)有序表為（13,19,25,36,48,51,63,84,91,116,135,200）,元素的下標

依次為1,2,……』2。

（1）說出有哪幾個元素需要經(jīng)過4次元素間的比較才能成功查到

（2）畫出對上述有序表進行折半查找所對應(yīng)的判定樹（樹結(jié)點用下標表示）

（3）設(shè)查找元素5,需要進行多少次元素間的比較才能確定不能查到

4.

（1）設(shè)有序列｛10,12,15,19,22,25,100,130,150,200｝畫出對上述序列進行折

半查找的判定樹（以序列中的元素作為樹的結(jié)點）

（2）為了成功查找到100需要進行多少次元素間的比較？為了查找9,經(jīng)過多少次元素

間的比較可知道查找失?。?/p>

5.

（1）對給定數(shù)列｛7,16,4,8,20,9,6,18,5｝,依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。

（2）對一個給定的查找值，簡述針對二叉排序樹進行查找的算法步驟，在上述二叉樹中查找

元素20共要進行多少次元素的比較？

6.

（1）設(shè)有查找表｛5,14,2,6,18,7,4,16,3｝,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。

（2）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序

遍歷的結(jié)果。

四、程序填空題

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

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

voidbsort(NODEa[],intn)

{NODEtemp;

inti,j,flag;

for(j=l;⑴;j++);

{flag=0;

for(i=l;⑵i<=n-j;i++)

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

{flag=l;

temp=a[i];

⑶a[i]=a[i+l]__________;

(4)a[i+l]=temp____________;

)

if(flag==0)break;

程序中flag的功能是一(5)當某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán)

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

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

voidPreorder(structBTreeNode*BT)

{if(BT!=NULL){

(])primf("%c”,BT.>data);

(2)Preorder(BT?>left);

(3)PreordeKBrAright);

}

)

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

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

#defineNULL0

voidmain()

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

a.data=6;

b.data=10;

c.data=16;

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

head=(1)&a;

a.next=&b;

b.next=&c;

c.next=&d;

⑵d?>next=NULL;/*以上結(jié)束建表過程*/

p=head;/*p為工作指針，準備輸出鏈表*/

do

{printf("%d\n”,(3)p->data);

(4)p=p->next;

}while((5)p!=NULL);

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

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

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

(1)Inorder(BT~>left);

(2)printf("％c”,BT->data);

(3)InordeKBF>right);

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

一、單項選擇題

1.D2.C3.D4.C5.D6.A7.A8.A9.D10.D11.C12.A

13.D14.A15.C16.D17.B18.D19.D20.C21.D22.A23.B

24、B25.D26.A27.A28.C29.A30.A

二、填空題

1.物理(存儲)

3.線性

5.結(jié)點的直接后繼結(jié)點的直接前驅(qū)

7.p->next=head;

9.h=h->next;

11.串長度相等且對應(yīng)位置的字符相等

13.先序、中序、后序、層次

15.2n-l

17.7

19.abdgcefhi

21.存儲地址

23.正確

2.p=p->next;

4.p->next=head；

6.hs->data;hs->next;

8.(r+1)%MaxSize=f

10.4

12.4；2

14.18

16.正確

18.先進后出（后進先出）先進先出（后進后出）

20.順序存儲結(jié)構(gòu)

22.2k-l

24.順序存儲鏈式存儲

三、綜合題

圖3

圖4

2.

(1)s=(NODE*)malloc(sizeof(NODE));s->data=1;

(2)p->next=s;

s->next=NULL；

free(s)

(3)head=head->next；

(4)pi->next=p->next；

p->next=pi；

3.

(1)19,48,84,116,200

(2)

圖5

(3)3次

(2)4次；3次

圖6

(2)先將給定值與根結(jié)點比較，若相等則查找成功，否則若小于根結(jié)點則在左子樹中繼續(xù)

查找，大于根結(jié)點在右子樹中查找，查找20共進行3次比較。

6.

⑴

3716

圖6

(2)中序遍歷

中序2,3,4,5,6,7,14,16,18

四、程序填空題

L

(1)j<=n-l

(2)i<=n-j

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

(4)a[i+l]=temp

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

(1)printf(,BT->data)

(2)Preorder(BT->1eft)

(3)Preorder(BT->right)

J.

(1)&a

(2)d-next=NULL

(3)p->data

(4)pz:p->next

(5)p!=NULL

(1)Inorder(BT->left)

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

(3)Inorder(BT->right)

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

一、單項選擇題

1.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（C）。

A.只能有一個數(shù)據(jù)項組成B.至少有二個數(shù)據(jù)項組成

C.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成

D.至少有一個數(shù)據(jù)項為指針類型

2.一種邏輯結(jié)構(gòu)（A）存儲結(jié)構(gòu)。

A.可以有不同的B.只能有唯一的

C.的數(shù)據(jù)元素在計算機中的表示稱為D.的數(shù)據(jù)元素之間的關(guān)系稱為

3.線性表的順序結(jié)構(gòu)中，（C）。

A.邏輯上相鄰的元素在物理位置上不一定相鄰

B.數(shù)據(jù)元素是不能隨機訪問的

C.邏輯上相鄰的元素在物理位置上也相鄰

D.進行數(shù)據(jù)元素的插入、刪除效率較高

4.以下說法中不正確的是（B）o

A.雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域

B.已知單向鏈表中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點

C.順序存儲的線性鏈表是可以隨機訪問的

D.單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針

5.以下表中可以隨機訪問的是（D）。

A.單向鏈表B.雙向鏈表

C.單向循環(huán)鏈表D.順序表

6.雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)類型為：

structnode

{intdata;

structnode*next;/*指向直接后繼*/

structnode*prior;

}；

設(shè)p指向表中某一結(jié)點，要顯示p所指結(jié)點的直接前驅(qū)結(jié)點的數(shù)據(jù)元素，可用操作

（B）。

A.printf（<<%d,,,p->next->data）;B.printf（"%d'',p?>prior?>data）;

C.printf（u%d,,,p->prior->next）;D.printf（4<%d,,,p->data）;

7.設(shè)順序存儲的線性表長度為n,對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元

素平均移動元素的次數(shù)為（A）。

A.（n+l）/2B.nC.2nD.n-i

8.一個棧的進棧序列是efgh,則棧的不可能的出棧序列是（D）（進出棧操作可以

交替進行）。

A.hgfeB.gfehC.fgehD.ehfg

9.設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，

設(shè)用x接收棧頂元素，則出棧操作為（A）。

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

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

10.設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,

設(shè)用x接收棧頂元素，則取棧頂元素的操作為（C

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

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

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

A.隊列是后進先出B.棧的特點是后進后出

C.棧的刪除和插入操作都只能在棧頂進行

D.隊列的刪除和插入操作都只能在隊頭進行

■以下說法不正確的是（C）。

A.棧的特點是后進先出B.隊列的特點是先進先出

C.棧的刪除操作在棧底進行，插入操作在棧頂進行

D.隊列的插入操作在隊尾進行，刪除操作在隊頭進行

13.串函數(shù)StrCmp（"abA'’,"aba"）的值為（D）?

A.1B.0C.“abAaba”D.-1

14.char*p;

p=StrCat（"ABD"JABC"）；

Printf（4<%s,\p）;

的顯示結(jié)果為（B）o

A.-1B.ABDABCC.ABD.1

15.設(shè)有一個12階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲

到一維數(shù)組b中（矩陣A的第一個元素為au,數(shù)組b的下標從1開始），則矩陣A

中第4行的元素在數(shù)組b中的下標i一定有（A

A、7WW10B、11W05C、9W04D、6WiW9

16.深度為5的滿二叉樹至多有（B）個結(jié)點（根結(jié)點為第一層）

A.40B.31C.34D.35

17.已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為（A）。

A.2mB.mC.2m+lD.m/2

18.已知一個圖的所有頂點的度數(shù)之和為m,則該圖的邊數(shù)為（D）。

A.2mB.mC.2m+lD,m/2

19.以下說法不正確的是（D）o

A.連通圖G一定存在生成樹

B.連通圖G的生成樹中一定包含G的所有頂點

C.連通圖G的生成樹中不一定包含G的所有邊

D.連通圖G的生成樹可以是不連通的

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

A.連通圖G的生成樹一定是唯一的

B.連通圖G一定存在生成樹

C.連通圖G的生成樹中一定要包含G的所有頂點

D.連通圖G的生成樹一定是連通而且不包含回路

21.散列查找的原理是（A）o

A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系

B.按待查記錄的關(guān)鍵字有序的順序方式存儲

C.按關(guān)鍵字值的比較進行查找

D.基于二分查找的方法

22.有序表為{1,2,4,6,10,18,20,32},用課本中折半查找算法查找值18,經(jīng)（B）

次比較后成功查到。

A.3B.2C.4D.5

23.排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)

排好序的子序列的適當位置，直到全部排好序為止，該排序算法是（A）。

A.直接插入排序B.快速排序

C.冒泡排序D.選擇排序

24.在排序過程中，可以通過某一趟排序的相關(guān)操作所提供的信息，判斷序列是否已經(jīng)排

好序，從而可以提前結(jié)束排序過程的排序算法是（A）。

A.冒泡B.選擇C.直接插入D.折半插入

25.采用順序查找法對長度為n的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的

情況下要進行（B）次元素間的比較。

A.n+2B.nC.n-1D.n/2

26.用折半查找法，對長度為12的有序的線性表進行查找，最壞情況下要進行（A）

次元素間的比較

A.4B.3C.5D.6

27.如圖若從頂點a出發(fā)按索法進行遍歷,

A.acebdfgh

B.aebcghdf

C.aedfbcgh

D.abecdfgh

28.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（B）。

A.acfgedb

B.aedbgfc

C.acfebdg

D.aecbdgf

29.一棵哈夫曼樹總共有23個結(jié)點，該樹共有（D）個葉結(jié)點（終端結(jié)點）

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

30.一棵哈夫曼樹總共有25個結(jié)點，該樹共有（A）個非葉結(jié)點（邪終端結(jié)點）。

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

二、填空題（每小題2分，共24分）

1.通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性.、樹形.、圖狀一四種類型。

2.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)。

3.設(shè)有一個單向鏈表，結(jié)點的指針域為next,頭指針為head,p指向尾結(jié)點，為了使該

單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。

4.設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next,頭指針為head,指針p指向表中某結(jié)

點，若邏輯表達式p~>next==head—的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。

5.設(shè)有一個單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點的指針域為next,p指向尾結(jié)點

的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作一

p->next=head。

■設(shè)有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作s->

next=hs;hs=s。

7.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next,則插入一個

s所指結(jié)點的操作為r->next=s；r=s；

8.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next,s指向一個要

入隊的結(jié)點，則入隊操作為r->next=s:=s:

9.循環(huán)隊列的隊頭指針為f,隊尾指針為r,當r==f時表明隊列為空。

10.循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用一個元素空間以有效地判斷棧空或

棧滿，若隊頭指針front=4,當隊尾指針rean=3時隊滿,隊列中共有

5個元素。

11.'A'在存儲時占_1_____個字節(jié)。

“A”在存儲時占2個字節(jié)。

12.程序段char*s=',aBcD,,;n=0;

while（*s!=,\0,）

{if（*s>='a'&&*s<='z'）n++;

s++;

}執(zhí)行后n=2

13.一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有—11一個結(jié)點。

14.一棵二叉樹中順序編號為5的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中對應(yīng)

位置上結(jié)點的編號相同），若它存在左孩子，則左孩子的編號為-10。

15.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有先序、中序、

后序三種。

■根據(jù)搜索方法的不同，圖的遍歷有深度優(yōu)先—廣度優(yōu)先一兩種方法。

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

18.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為圖狀（網(wǎng)狀狀結(jié)構(gòu)。

■如圖2所示的二叉樹，其后序遍歷序列為gdbeihfcao

圖2

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

2n-l個結(jié)點0

21.二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其

右孩子的值。這種說法是錯誤的。(回答正確或不正確)

■串的兩種最基本的存儲方式分別是一順序存儲和一鏈式存儲o

■根據(jù)搜索方法的不同，圖的遍歷有.深度優(yōu)先、廣度優(yōu)先兩種方

法

■按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字—關(guān)鍵字相等的記錄在排序前和

排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。

三、綜合題

1.(1)已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac,試畫出該二叉樹

(2)若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好

使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系

(3)給出該樹的前序遍歷序列

2.(1)已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是eadcb,試畫出該二叉樹

(2)給出上述二叉樹的后序遍歷序列

(3)若上述二叉樹的各個結(jié)點的字符分別是1,2,3,4,5,并恰好使該樹成為一棵二

叉排序樹，試問a、b、c、d、e的值各為多少？

3.(1)設(shè)有一個整數(shù)序列｛40,28,6,72,100,3,54｝依次取出序列中的數(shù)，構(gòu)造一

棵二叉排序樹

(2)對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度

4.(1)給定數(shù)列｛8,17,5,9,21,10,7,19,6),依次取序列中的數(shù)構(gòu)造一棵二叉

排序樹

(2)對上述二叉樹給出中序遍歷得到的序列

5.(1)利用篩選過程把序列｛42,82,67,102,16,32,57,52｝建成堆(小根堆)，畫

出相應(yīng)的完全二叉樹(不要求中間過程)

(2)寫出對上述堆對應(yīng)的完全二叉樹進行中序遍歷得到的序列

6.(1)以給定權(quán)重值1,2,12,13,20,25為葉結(jié)點，建立一棵哈夫曼樹

(2)若哈夫曼樹有n個非葉子結(jié)點，則樹中共有多少結(jié)點。對給定的一組

權(quán)重值建立的棵哈夫曼樹是否一定唯一

四、程序填空題

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

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

typedefstruct

{intkey;

(NODE;

intBinary_Search(NODEa[],intn,intk)

(

intlow,mid,high;

low=0;

high=n-l;

whi1e(__(1)_low<=high)

(

mid=(low+high)/2;

if(a[mid].key-k)

return__(2)_mid;

elseif(___(3)_a[mid].key<k;)

low=mid+l;

else—(4)_high=mid-l:

)

___(5)_return-1;___;

2.以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返

回值是指向樹結(jié)點的結(jié)構(gòu)指針p(查找成功p指向查到的樹結(jié)點，不成功p指向為NULL)

完成程序中的空格

typedefstructBnode

{intkey;

structBnode*left;

structBnode*right;

}Bnode;

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接收二叉排序樹的根結(jié)點的指針，k用以接收要查找的關(guān)鍵字*/

{Bnode*p;

if(bt==—(1)NULL)

return(bt);

p=bt;

while(p->key!=_(2)_k)

{if(k<p->key)

一(3)_p=p->left___;

else___(4)_p=p->right;

if(p==NULL)break;

)

Return(___(5)_p);

)

3.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是

鏈隊列的隊頭、隊尾指針

structnode

{ElemTypedata;

structnode*next;

)；

structnode*front,*rear;

voidInQueue(ElemTypex)

(

structnode*p;

p=(structnode*)___(1)_malloc(sizeof(structnode))___;

p->data=x;

p->next=NULL;

___(2)rear->next=p;

rear=___(3)_p;

)

4.以下函數(shù)為鏈隊列的出隊操作(鏈隊列帶有頭結(jié)點)，出隊結(jié)點的數(shù)據(jù)域的值由x返

回，front、rear分別是鏈隊列的隊頭、隊尾指針

structnode

{ElemTypedata;

structnode*next;

}；

structnode*front,*rear;

ElemTypeOutQueue()

(

ElemTypex;

if(___(1)___front==rear__){

printf(〃隊列下溢錯誤！\n〃)；

exit(1);

)

else{

structnode*p=front->next;

x=p->data;

front->next=___(2)_p->next___;

if(p->next==NULL)rear=front;

free(p);

一(3)_return(x)

}

)

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

一、單項選擇題

1.C2.A3.C4.B5.D6.B7.A8.D9.A10.C11.C12.C

13.D14.B15.A16.B17,A18.D19.D20.A21.A22.B23.A

24.A25.B26.A27.D28.B29.D30.A

二、填空題

1.集合；線性；樹形；圖狀

2.圖狀

3.p->next=head;

4.p->next==head;

5,p->next=head；

6.hs=s；

7.r->next=s

8.r->next=s；r=s；

9.r==f

10.3；5

11.1；2

12.2

13.11

14.10

15.先序；中序；后序

16.深度優(yōu)先；廣度優(yōu)先

17.物理（存儲）

18.圖狀（網(wǎng)狀）

19.gdbeihfca

20.2n-l

21.錯誤

22.順序存儲鏈式存儲

23.深度優(yōu)先廣度優(yōu)先

24.關(guān)鍵字相等的記錄

三、綜合應(yīng)用題

1.（1）

(2)d<b<e<a<c

(2)edbca

(3)e=1,a=2,d=3,c=4,b=5

(2)5,6,7,8,9,10,17,18,19,21

初始樹堆

(2)102,52,42,82,16,67,32,57

四、程序填空題（每空2分，共16分）

1.(1)low<=high

(2)mid

(3)a[mid].key<k;

(4)high=mid-l

(5)return-1;

2.(1)NULL

(2)k

(3)p=p->left

(4)p=p->right

(5)p

3.(1)malloc(sizeof(structnode))

(2)rear->next=p

(3)p

4.(1)front==rear

(2)p->next

(3)return(x)

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

一、單項選擇題

1.(B)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

A、數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項

2.從n個數(shù)中選取最大元素(C)。

A.基本操作是數(shù)據(jù)元素間的交換B.算法的時間復(fù)雜度是OS?)

C.算法的時間復(fù)雜度是0(n)D.需要進行(n+1)次數(shù)據(jù)元素間的比較

3.設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量，且有NODE*p；為了申請一個新結(jié)點，

并由p指向該結(jié)點，可用以下語句(A)。

A.p=(NODE*)malloc(sizeof(NODE));

B.p=(*NODE)malloc(sizeof(NODE));

C.p=(NODE)malloc(sizeof(p));

D.p=(NODE*)malloc(sizeof(p));

4.設(shè)head為非空的單向循環(huán)鏈表頭指針,p指向鏈表的尾結(jié)點，則滿足邏輯表達式(D)

的值為真。

A.p->next=NULLB.p==NULL

C.p->next=headD.p->next==head

5.設(shè)順序存儲的線性長度為n,要族i個元素之前插入一個新元素，按課本的算法當1=

(D)時，移動元素次數(shù)為2

A.n/2B.nC.1D.n-1

6.設(shè)順序存儲的線性表長度為n,要刪除第i個元素，按課本的算法，當i=(C)時，

移動元素的次數(shù)為3

A.3B.n/2C.n-3D.3

7.一個棧的進棧序列是1,2,3,4,則棧的不可能的出棧序列是(B)(進出棧操

作可.以交替進行)

A.3,2,4,1B.1,4,2,3

C.4,3,2,1D.3,2,1,4

8.一個棧的進棧序列是a,b,c,d,則棧的不可能的出棧序列是(A)。

A.adbcB.bead

C.cbadD.deba

9.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，

front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被

賦值)，則入隊操作為(A)。

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

C.p=rear->next;rear=p;D.rea=p;rear->ne