《數(shù)據(jù)結構(本)》電大期末試題及其答案

《數(shù)據(jù)結構（本）》期末綜合練習題

一、單選選擇題

1.棧和隊列的共同特點是（C）。

A.都是先進先出B.都是操作受限的線性結構

C.都是先進后出D.元素都可以隨機進出

2.數(shù)據(jù)的存儲結構包括數(shù)據(jù)元素的表示和（C）。

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

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

3.對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結點，則執(zhí)行

p=(structnode*)malloc(sizeof(structnode);p->data=a;和（C）。

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

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

4.樹狀結構中數(shù)據(jù)元素的位置之間存在（B）的關系。

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

C.一對一D.多對多

5.設頭指針為head的非空的單向鏈表，指針p指向尾結點,則通過以下操作（D）可使其成

為單向循環(huán)鏈表。

A.head=p;B.p=head;

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

6.設有一個長度為26的順序表，要插入一個元素，并使它成為新表的第6個元素，需移動

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

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

7.一種邏輯結構（C）。

A.與存儲該邏輯結構的計算機相關B.是指某一種數(shù)據(jù)元素的性質(zhì)

C.可以有不同的存儲結構D.只能有唯一的存儲結構

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

點的單向循環(huán)鏈表，可執(zhí)行head=head->nex;和（A）。

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

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

9.把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結構稱為（D）。

A.給數(shù)據(jù)元素分配存儲空間B.數(shù)據(jù)元素的存儲

C.邏輯結構D.存儲結構

10.元素111，113，115，117按順序依次進棧，則該棧的不可能輸出序列是（D）（進棧出

?？梢越惶孢M行）。

A.111，113，115，117B.113，111，117，115

C.117，115，113，111D.117，115，111，113

11.圖狀結構中數(shù)據(jù)元素的位置之間存在（B）的關系。

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

B.多對多C.一對一D.一對一

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

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

C.棧的特點是先進先出D.棧的特點是先進后出

13.一個單鏈表中，在p所指結點之后插入一個s所指的結點時，可執(zhí)行：s->next=p->next;

和（D）。

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

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

14.設有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角

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

組B中的下標是（B）。

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

15.元素12，14，16，18順序依次進棧，則該棧的不可能輸出序列是（C）。（進棧出?？?/p>

以交替進行）。

A.18，16，14，12B.12，14，16，18

C.18，16，12，14D.14，12，18，16

16.設有串p1="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF"，以下四個串中最大的是（A）。

A.p2B.p3C.p4D.p1

17.設有一個30階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角

部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a9,2在一維

數(shù)組B中的下標是（A）。

A.38B.32C.18D.41

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

A."h"B.字符串的結束符C.變量hD.字符h

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

A.15B.24C.22D.14

20.設主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（B）。

A.ABCB.BcdC.AbcD.BCd

21.在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（C）。

A.2i-1B.2iC.2i+1D.2i+2

22.在一棵二叉樹中，若編號為i的結點存在左孩子，則左孩子的順序編號為（D）。

A.2i+1B.2i-1C.2i+2D.2i

23.一棵具有16個結點的完全二叉樹，共有（B）層。（設根結點在第一層）

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

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

點序列為（A）。

A.aecbdfB.aedfcbC.aebcfdD.abecdf

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

點序列為（C）。

A.aebcfgdB.abecdfgC.aedfcgbD.acfebgd

26.線性表以（B）方式存儲，能進行折半查找。

A.順序B.關鍵字有序的順序C.二叉樹D.鏈接

27.字符串“DABcdabcd321ABC”的子串是（C）。

A.“321a”B.“aBcd”C.“cd32”D.“ABcD”

28.一棵具有38個結點的完全二叉樹，最后一層有（B）個結點。

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

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

列為（C）。

A.acbfedgB.abcdfegC.abcdfgeD.abcfgde

30.下圖的拓撲序列是（）。

A.23645B.56234C.23564D.52346

31.下面關于線性表的敘述錯誤的是（D）。

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

B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間

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

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

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

第一個結點，則可利用下述語句head=head->next;和（D）。

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

33.以下數(shù)據(jù)結構中是非線性結構的是（C）。

A.線性表B.隊列C.二叉樹D.棧

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

A.線性表的鏈式存儲結構必須占用連續(xù)的存儲空間

B.一種邏輯結構可以有不同的存儲結構

C.一種邏輯結構只能有唯一的存儲結構

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

35.設有一個長度為18的順序表，要刪除第7個元素需移動元素的個數(shù)為（B）。

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

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

A.數(shù)據(jù)元素間的邏輯關系B.數(shù)據(jù)的運算

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

37.兩個字符串相等的充要條件是（B）。

A.兩個字符串的長度相等B.同時具備（A）和（C）兩個條件

C.兩個字符串中對應位置上的字符相等D.以上答案都不對

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

A.刪除元素的操作不需要移動元素B.可以隨機訪問任一結點

C.不需要占用連續(xù)的存儲空間D.插入元素的操作不需要移動元素

39.設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，在已知尾指針的條件下，選

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

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

40.圖狀結構中數(shù)據(jù)元素的位置之間存在（A）的關系。

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

C.一對多D.一對一

41.元素13，15，19，20順序依次進棧，則該棧的不可能輸出序列是（A）。（進棧出?？?/p>

以交替進行）

A.19，13，15，20B.15，13，20，19

C.13，15，19，20D.20，19，15，13

42.元素20，14，16，18按順序依次進棧，則該棧的不可能輸出序列是（A）。（進棧出棧

可以交替進行）

A.18，16，20，14B.20，14，16，18

C.14，20，18，16D.18，16，14，20

43.設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，則在表中刪除

結點B的操作為（A）。

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

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

44.設有一個12階的對稱矩陣A（左上角第一個元素為a1,1），采用壓縮存儲的方式，將其

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

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

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

45.棧和隊列的共同特點之一是（A）。

A.只允許在端點處插入和刪除元素B.都是先進先出

C.沒有共同點D.都是先進后出

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

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

47.用鏈接方式存儲的隊列，在進行插入運算時（C）。

A.頭、尾指針都需要修改B.頭、尾指針都不需要修改

C.需修改尾指針D.需修改頭指針

48.在一棵二叉樹中，若編號為5的結點存在右孩子，則右孩子的順序編號為（D）。

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

49.字符串a(chǎn)1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（D）。

A.a2B.a3C.a4D.a1

50.一棵具有5層的完全二叉樹，最后一層有4個結點，則該樹總共有（B）個結點。

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

51.設有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將

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

陣中元素a6,2在一維數(shù)組B中的下標是（C）。

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

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

點序列為（A）。

A.abcedfgB.abcfgdeC.acbfedgD.abcdfge

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

A.二叉樹中任意一個非葉結點的值都大于其左子樹上所有結點的值，小于其右子樹上所有

結點的值，則該樹為二叉排序樹。

B.若二叉樹中左子樹上所有結點的值均小于根結點的值，右子樹上所有結點的值均大于根

結點的值。則該樹為二叉排序樹。

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

D.二叉樹中任意一個結點的值均大于其左孩子的值，小于其右孩子的值。則該樹為二叉排

序樹。

54.字符串"abcd321ABCD"的子串是（B）。

A."321a"B."21ABC"C."abcABCD"D.abcD

55.二叉樹的第k層的結點數(shù)最多為（B）。

A.2K-1B.2k-1C.2K+1D.2k-1

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

A.字符EB."n"C."E"D.字符n

57.如下圖所示，若從頂點6出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序

列為（D）。

A.6，2，8，7，9，3，4B.6，9，2，3，7，8，4

C.6，2，7，9，8，4，3D.6，9，3，2，8，7，4

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

點序列為（A）。

A.aedfcbB.aebcfdC.abecdfD.acfebd

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

列為（A）。

A.abcdfgeB.abcfegdC.abcfgdeD.acbfedg

60.下圖的拓撲序列是（B）。

A.52346B.52364C.23456D.56423

二、填空題

1.對稀疏矩陣進行壓縮存儲，可采用三元組表，一個有10行的稀疏矩陣A共有97個零元素，

其相應的三元組表共有3個元素。該矩陣A有10列。

2.結構中的數(shù)據(jù)元素存在多對多的關系稱為圖狀結構。

3.在單向鏈表中，q指向p所指結點的直接后繼結點，要刪除q所指結點，可以用操作

p->next=q->next;。

4.n個元素進行冒泡法排序，第j趟冒泡要進行n-j次元素間的比較。

5.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行下標、列下

標和數(shù)組元素三項信息。

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

7.隊列的操作特點是后進后出。

8.待排序的序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當進行了兩趟選擇后，

結果序列為1,2,4,8,3,5,9。

9.n個元素進行冒泡法排序，通常需要進行n-1趟冒泡。

10.廣義表（（a，b），d，e（（i，j），k））的長度是4。

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

12.廣義表的（c，a，（a，b），d，e，（（i，j），k））深度是3。

13.廣義表（c，a，（a，b），d，e，（（i，j），k））的長度是6。

14.對稀疏矩陣進行壓縮存儲，可采用三元組表，一個有10行10列的稀疏矩陣A共有95

個零元素，其相應的三元組表共有5個元素。

15.廣義表的（c，a，（a，b），d，e，（（i，j），k））深度是3。

16.在對一組記錄（50，49，97，22，16，73，65，47，88）進行直接插入排序時，當把第

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

17.循環(huán)隊列在規(guī)定少用一個存儲空間的情況下，隊空的判定條件為front==rear。

18.一棵有5個葉結點的哈夫曼樹，該樹中總共有9個結點。

19.c語言中，字符串“E”存儲時占2個字節(jié)。

20.設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有12個結點。（根

所在結點為第1層）。

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

葉結點。

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

23.在對一組記錄（55，39，97，22，16，73，65，47，88）進行直接插入排序時，當把第

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

24.有以下程序段：

chara[]=“English”;

char*p=a;intn=0;

while(*p!=‘\0’){n++;p++;}

結果中，n的值是7。

25.設：chara[]="AEIJING";該字符串在計算機中存儲時占8個字節(jié)。

26.棧的特點之一是：元素進、出棧的次序是：先進后出。

27.結構中的數(shù)據(jù)元素存在多對多的關系稱為圖狀結構。

28.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的三項信息是

行下標，列下標，數(shù)組元素。

29.對稀疏矩陣進行壓縮存儲，可采用三元組表，一個有8行的稀疏矩陣A共有92個零元素，

其相應的三元組表共有4個元素。該矩陣A有12列。

30.在對10個記錄的序列（9，35，19，77，2，10，53，45，27，68）進行直接插入排序時，

當把第6個記錄10插入到有序表時，為尋找插入位置，元素間需比較4次。（按升

序排序）

31.循環(huán)鏈隊列中，設front和rear分別為隊頭和隊尾指針，最大存儲空間元素為MaxSize，

采用少用一個存儲空間的模式，則判斷循環(huán)鏈隊列為空的條件是front==rear為真。

32.字符串a(chǎn)1="beijing"，a2="bef"，a3="beifang"，a4="befi"最小的是a2。

33.n個元素進行冒泡法排序，第j趟冒泡要進行n-j次元素間的比較。

34.10個元素進行冒泡法排序，其中第5趟冒泡共需要進行5次元素間的比較。

35.設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有12個結點。（根

所在結點為第1層）

36.中序遍歷一棵二叉排序樹可得到一個有序序列

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

38.廣義表（c，（a，b，c），（d，e，f），（（i，j），k））的長度是4。

39.待排序的序列為9，4，5，1，2，6，10，采用直接選擇排序算法，當進行了兩趟選擇后，

結果序列為。

40.廣義表的（c，（b，a，b），f，e，（（i，j），k））深度是3。

41.廣義表（（a，b），d，e，（（i，j），k））的長度是4。

42.序列4，2，5，3，8，6，采用冒泡排序算法（升序），經(jīng)一趟冒泡后，結果序列是

2,4,3,5,6,8。

43.廣義表的（c，a，（a，b），d，e，（（i，j），k））深度是3。

44.待排序的序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當進行了兩趟選擇后，

結果序列為1,2,4,8,3,5,9。

45.線性表用順序方式存儲需要占用連續(xù)的存儲空間。

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

47.線性表用關鍵字有序的順序方式存儲，可以用二分法排序。

48.順序表6，5，1，2，4，3，8，7經(jīng)過一趟（1，1）歸并后的結果序列為（5,6），（1,2），

（3,4），（7,8）。

三、綜合題

1.有一個長度為11的有序表（1，2，11，15，24，28，30，56，69，70，80），元素的下

標依次為：1，2，3，……，11，按折半查找對該表進行查找。

（1）畫出對上述查找表進行折半查找所對應的判定樹。

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

（3）說出不成功查找元素72，需要進行元素比較的次數(shù)？

（1）答：

（2）28,69,30,56

（3）4次

2.（1）以3，4，5，8，9，作為葉結點的權，構造一棵哈夫曼樹。

（2）給出相應權重值葉結點的哈夫曼編碼。

（3）n個葉結點的哈夫曼樹，總共有多少個結點？

（1）答：

（2）答：3:0004:0015:018:109:11

（3）2n-1

3.（1）一組記錄的關鍵字序列為（57，90，67，50，51，56），利用堆排序（堆頂元素是

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

（2）對關鍵字序列（56，51，71，54，46，106）利用快速排序，以第一個關鍵字為分割元

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

（3）一組記錄的關鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方

法，分別給出（1，1）歸并、（2，2）歸并、（4，4）歸并的結果序列。

（1）答：

（2）46,51,54,56,71,106

（3）（47,60）（57,80）（39,41）（30,46）

（47,57,60,80）（30,39,41,46）

（30,39,41,46,47,57,60,80）

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

據(jù)構造一棵二叉排序樹。

（2）在上述二叉排序樹上進行查找，給出成功查找到元素92的查找路徑，其中共經(jīng)過了多

少次元素間的的比較。

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

功的平均比較次數(shù)為。

（1）

（2）40,73,101,81,92。共5個元素比較。

（3）29/10

5.（1）以2，3，4，7，8，9作為葉結點的權，構造一棵哈夫曼樹。

（2）給出相應權重值葉結點的哈夫曼編碼。

（3）一組記錄的關鍵字序列為（47，80，57，39，41，46），利用堆排序的方法建立的初

始堆（堆頂元素是最小元素，以樹的形式給出）。

（1）

（2）2：0000

3：0001

4：001

7：10

8：11

9:01

（3）

6.（1）一組記錄的關鍵字序列為（36，69，46，28，30，35），給出利用堆排序（堆頂元

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

（2）對關鍵字序列（36，69，46，28，30，74）采用快速排序，給出以第一個關鍵字為分

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

（3）設有數(shù)據(jù)集合{30，73，101，4，8，9，2，81}，依次取集合中各數(shù)據(jù)構造一棵二叉排

序樹。

答：（1）28,30,35,69,36,46

（2）30,28,36,46,69,74

（3）

7.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹。

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

該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關系。

（3）給出該樹的前序遍歷序列。

（1）

（2）d<b<e<a<c

（3）abdec

8.（1）一組記錄的關鍵字序列為{45，40，65，43，35，95}，寫出利用快速排序的方法，

以第一個記錄為基準得到的一趟劃分的結果（要求給出一趟劃分中每次掃描和交換的結果）。

（2）對序列{45，40，65，43，35，95}利用直接插入排序，寫出逐次插入過程（從第一個

元素一直到第六個元素）。

（1）

（2）404565433595

404345653595

354043456595

9.（1）設head1和p1分別是不帶頭結點的單向鏈表A的頭指針和尾指針，head2和p2分

別是不帶頭結點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個

以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關鍵的賦值語句（不用完整程序，結點的

鏈域為next）。

（2）單向鏈表的鏈域為next，設指針p指向單向鏈表中的某個結點，指針s指向一個要插

入鏈表的新結點，現(xiàn)要把s所指結點插入p所指結點之后，某學生采用以下語句：

p->next=s;s->next=p->next;

這樣做正確嗎？若正確則回答正確，若不正確則說明應如何改寫。

答：（1）p1->next=head2；p2->next=head1；

（2）不對，s->next=p->next；p->next=s；

10.（1）設根為第1層,對給定權值1，3，4，4，5，6，構造深度為5的哈夫曼樹。

提示：構造中當出現(xiàn)被選的結點值有多個相等時，可嘗試不同組合，以得到要求的樹的深度。

（2）求樹的帶權路徑長度。

（3）用鏈接法存儲上述哈夫曼樹，結點中共有多少個指針域為空，說明理由？

（4）給出對上述哈夫曼樹中序遍歷得到的的序列。

（5）一棵哈夫曼樹有n個非葉結點，構造該樹共有多少個權重值？簡述理由？

答：（1）

（2）WPL=1*4+3*4+4*3+6*2+4*2+5*2=58

（3）有12個空指針域，因為共11個結點，22個指針域，除根結點外，每個結點對應一個

指針域，共10個指域非空，故有22-10=12個空指針域。（針對哈夫曼樹還可有其它理由）

（4）1，4，3，8，4，14，6，23，4，9，5

（5）n+1，因為葉結點比非葉結點多1。

四、程序填空

1.以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域

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

voidInorder(structBTreeNode*BT)

{

if(BT!=NULL)

（1）Inorder(BT->left)；

（2）printf("%c",BT->data)；

Inorder(BT->right);

}

利用上述程序?qū)ο聢D進行遍歷，結果是（3）dbfeac。

2.設線性表為（16，20，26，24），以不帶頭結點的單向鏈表存儲，鏈表頭指針為head，

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

structnode

{

intdata;

structnode*next;

};

typedefstructnodeNODE;

#defineNULL0

voidmain()

{

NODE*head,*p;

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

do

{

printf("%d\n",（1）);

（2）;

}while(（3）);

}

答：（1）p->data

（2）p=p->next

（3）p!=NULL

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

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

voidbsort(NODEa[],intn)

{

NODEtemp;

inti,j,flag;

for(j=1;（1）;j++)

{

flag=0;

for(i=1;（2）;i++)

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

{

flag=1;

temp=a[i];

（3）;

（4）;

}

if(flag==0)break;

}

}

設有序列6，4，5，8，2，1，給出由該程序經(jīng)過兩趟冒泡后的結果序列（5）。

答：（1）j<=n-1

（2）i<=n-j

（3）a[i]=a[i+1]

（4）a[i+1]=temp

（5）4，5，2，1，6，8

4.以下函數(shù)為直接選擇排序算法，對a[1]，a[2]，……，a[n]中的記錄進行直接選擇排序，

完成程序中的空格：

typedefstruct

{

intkey;

……

}NODE;

voidselsort(NODEa[],intn)

{

inti,j,k;

NODEtemp;

for(i=1;i<=（1）;i++)

{

k=i;

for(j=i+1;j<=（2）;j++)

if(a[j].key<a[k].key)（3）;

if(i!=k)

{

temp=a[i];

（4）;

（5）;

}

}

}

答：（1）n-1

（2）n

（3）k=j

（4）a[i]=a[k]

（5）a[k]=temp

5.設線性表為（1，3，7，5），以下程序用說明結構變量的方法建立單向鏈表，并輸出鏈表

中各結點中的數(shù)據(jù)。

structnode

{

intdata;

structnode*next;

}

typedefstructnodeNODE;

#defineNULL0

Voidmain()

{

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

a.data=6;

b.data=10;

c.data=16;

c.data=4;/*d是尾結點*/

head=（1）;

a.next=&b;

b.next=&c;

c.next=&d;

（2）；/*以上結束建表過程*/

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

do

{

printf("%d\n",（3）);

（4）;

}while(p!=NULL);

}

畫出按該程序建立的單向鏈表的示意圖，說明程序運行結束后p的指向。（5）

答：（1）&a

（2）d->next=NULL

（3）p->data

（4）p=p->next

（5）P指向NULL

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

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

typedefstruct

{

intkey;

……

}NODE;

intBinary_Search(NODEa[],intn,intk)

{

intlow,mid,high;

low=0;

high=n-1;

while(（1）)

{

mid=(low+high)/2;

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

return（2）;

elseif(（3）)

low=mid+1;

else（4）;

}

return-1;

}

設數(shù)組元素：a[0]=2；a[1]=5；a[2]=3；a[3]=4；a[4]=9；a[5]=6；a[6]=1；a[7]=10；按

上述程序查找元素5，能否成功查到，說明理由（5）。

答：（1）low<=high

（2）mid

（3）a[mid].key<k

（4）high=mid-1

（5）不能，因為不是有序序列，不能用折半查找。

7.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指

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

voidInorder(structBTreeNode*BT)

{

if(BT!=NULL)

{

（1）;

Inorder(BT->right);

（2）;

}

}

利用上述程序?qū)ο聢D進行遍歷，結果是（3）。

答：（1）Inorder(BT->left)

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

（3）f,d,e,b,c,a

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

隊列的隊頭、隊尾指針

structnode

{

ElemTypedata;

structnode*next;

};

structnode*front,*rear;

voidInQueue(ElemTypex)

{

structnode*p;

p=(structnode*)（1）;

p->data=x;

p->next=NULL;

（2）;

rear=（3）;

}

答：（1）malloc(sizeof(structnode))

（2）rear->next=p

（3）p

9.設有一個頭指針為head的不帶頭結點單向鏈表，p、q是指向鏈表中結點類型的指針變量，

p指向鏈表中某結點a（設鏈表中沒有結點的數(shù)據(jù)域與結點a的數(shù)據(jù)域相同），寫出相關語

句：（1）使該單向鏈表成為單向循環(huán)鏈表；（2）刪去a結點

q=p;x=p->data;

while(q->next!=NULL)q=q->next;

（1）;

q=p;p=p->next;

while(p->data!=x)

{

q=p;

（2）;

}

（3）;

答：（1）q->next=head

（2）p=p->next

（3）q->next=p->next

模擬練習題（一）

一、單項選擇題（每小題2分，共30分）

1、單向鏈表所具備的特點是（C）。

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

C.插入刪除不需要移動元素D.可以通過某結點的指針域訪問其前驅(qū)結點

2、設有一個長度為18的順序表，要在第6個元素之前插入一個元素（也就是插入元素作為

新表的第6個元素），則移動元素個數(shù)為（A）。

A.13B.5C.12D.6

3、棧和隊列的共同特點是（C）。

A.都是先進后出B.都是先進先出C.都是線性結構D.元素都可以隨機進出

4、元素1，3，5，7按順序依次入隊列，按該隊列的出隊序列進棧，該棧的可能輸出序列是

（B）（進棧出?？梢越惶孢M行）。

A.5，1，3，7B.7，5，3，1C.7，5，1，3D.7，3，1，5

5、在一個不帶頭結點的鏈隊中，假設f和r分別為隊頭和隊尾指針，則對該隊列進行出隊

操作中并把結點的值保存在變量e中,其運算為e=f→data；和（C）。

A.f→next=f;B.r=r→next;C.f=f→next;D.r→next=r;

6、設有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維

數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有45個元素，則該矩陣是（B）階的

對稱矩陣。

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

7、下列是C語言中"abcd321ABCD"的子串的選項是（B）。

A.abcDB."21ABC"C."abcABCD"D."321a"

8、字符串a(chǎn)1="BEIJING"，a2="BEF"，a3="BEFANG"，a4="BEFI"最小的是（D）。

A.a1B.a3C.a4D.a2

9、一棵有20個結點采用鏈式存儲的二叉樹中，共有（D）個指針域為空。

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

10、設一棵哈夫曼樹共有18個葉結點，則該樹有（C）個非葉結點。

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

11、如下圖所示的一個圖，若從頂點g出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一

種頂點序列為（C）。

A.gaebcfdB.gabecdfC.gaedfcbD.gacfebd

12、線性表以（C）方式存儲，能進行折半查找。

A.順序B.鏈接C.關鍵字有序的順序D.關鍵字有序的

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

均比較次數(shù)為（D）。

A.22/8B.20/8C.23/8D.21/8

14、排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行

比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（C）。

A.歸并排序B.選擇排序C.折半插入排序D.直接插入排序

15、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一

端的方法，稱為（B）排序。

A.快速B.選擇C.冒泡D.堆

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

16、廣義表(a，(a，b)，d，e，((i，j)，k))的長度是5。

17、廣義表的(c，a，(a，b)，d，e，((i，j)，k))深度是3。

18、設順序隊列的類型為

typedefstruct

{

ElemTypedata[MaxSise];

intfront,rear;

}Squeue;

Squeue*sq;

sq為指向順序隊列的指針變量，要進行新元素x的入隊操作，按教課書約定，可用語句

sq->data[sq->rear]=x;和sq->rear++。

19、序列4，2，5，3，8，6，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結果是2,4,3,5,6,8

。（按由小到大順序）

20、在對一組記錄（50，34，92，19，11，68，56，41，79）進行直接插入排序（由小到大

排序)，當把第7個記錄56插入到有序表時，為尋找插入位置需比較3次。

21、數(shù)據(jù)結構中，數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項組成。

22、循環(huán)隊列中，設front和rear分別為隊頭和隊尾指針，（最多元素為MaxSize，采用

少用一個元素的模式），判斷循環(huán)隊列為滿的條件為front==(rear+1)%MaxSize為

真。

23、排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素依次

進行比較，然后將其放入已排序序列的正確位置的方法是直接插入排序。

24、對稀疏矩陣進行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A共有34個零

元素，其相應的三元組表共有8個元素。

25、在雙向鏈表中，要刪除p所指的結點，可以先用語句（p->prior）->next=p->next；然

后再用語句（p->next）->prior=p->prior;。

26、在雙向鏈表中，每個結點有兩個指針域，一個指向結點的直接后繼，另一個指向結點

的直接前驅(qū)。

27、把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結構稱為存儲結構。

三、綜合題（每小題15分，共30分）

28、設數(shù)據(jù)集合a={1，12，5，8，3，10，7，13，9}

（1）依次取a中各數(shù)據(jù)，構造一棵二叉排序樹。

（2）說明如何依據(jù)此二叉樹得到a的有序序列。

（3）對該二叉樹進行查找，成功查找到7要進行多少次元素間的比較？

（4）給出對該二叉樹后序遍歷的序列。

（5）畫出在二叉樹中刪除12后的樹結構（要求結點13的位置不變）。

答：（1）

（2）中序遍歷1，3，5，7，8，9，10，12，13

（3）5次

（4）3，7，9，10，8，5，13，12，1

（5）

29、設有序表為（2，5，11，12，30，48，58，70，78，79，90），元素的序號依次為1，

2，3，……，11。

（1）畫出對上述查找表進行折半查找所對應的判定樹（樹中結點用序號表示）

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

（3）說明不成功查找元素75需要經(jīng)過多少次比較？

（4）給出后序遍歷該折半查找判定樹的序列

（5）給出中序遍歷該折半查找判定樹的序列

答：（1）

（2）3次

（3）4次

（4）2，1，5，4，3，8，7，11，10，9，6（序號）

（5）1，2，3，4，5，6，7，8，9，10，11（序號）

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

30、設有一個不帶頭結點的單向鏈表，頭指針為head，p、prep是指向結點類型的指針，該

鏈表在輸入信息時不慎把相鄰兩個結點的信息重復輸入，以下程序段是在該單向鏈表中查找

這相鄰兩個結點，把該結點的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程

序中的空格。

prep=head;

p=prep->next;

while(p->data!=prep->data)

{

prep=p;

（1）

}

printf(“min=%d”,（2）);

prep->next=（3）;

答：（1）p=p->next;

（2）p->data或prep->data

（3）p->next

31、以下程序是折半插入排序的算法（按記錄中關鍵字key排序）設待排序的記錄序列存放

在a[1]，…，a[n]中，以a[0]作為輔助工作單元，以下程序是要把a[i]插入到已經(jīng)有序

的序列a[1]，…，a[i-1]中。

voidbinsort(NODEa[],intn)

{

intx,i,j,s,k,m;

for（i=2；i<=（1）;i++）

{

a[0]=a[i];

x=a[i].key;

s=1;

j=i-1;

while(s<=j)

{

m=（2）;

if(x<a[m].key)

（3）;

else

（4）

}

for(k=i-1;k>=j+1;k--)

（5）=a[k];

a[j+1]=a[0];

}

}

答：（1）n

（2）(s+j)/2

（3）j=m-1

（4）s=m+1

（5）a[k+1]

模擬練習題（二）

一、單項選擇題（每小題2分，共30分）

1、頭指針為head的帶頭結點的單向鏈表為空的判定條件是（C）為真。

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

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

2、設有一個長度為32的順序表，要刪除第8個元素需移動元素的個數(shù)為（B）。

A.9B.24C.25D.8

3、一個棧的進棧序列是2，4，6，8，10，則棧的不可能輸出序列是（A）（進棧出?？?/p>

以交替進行）。

A.8，6，10，2，4B.8，10，6，4，2

C.10，8，6，4，2D.2，4，6，8，10

4、一個隊列的入隊序列是a，b，c，d，按該隊列的可能輸出序列使各元素依次入棧，該棧

的可能輸出序列是（C）。（進棧出?？梢越惶孢M行）。

A.d，a，b，cB.c，a，b，dC.d，c，b，aD.d，b，a，c

5、在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，p指向一個已生成的結點，現(xiàn)要為

該結點的數(shù)據(jù)域賦值e，并使結點入隊的運算為p->data=e;p->next=NULL;和（D）。

A.f->next=p;f=p;B.p->next=f;f=p;C.p->next=r;r=p;D.r->next=p;r=p;

6、設有一個24階的對稱矩陣A，采用壓縮存儲的方式（矩陣的第一個元素為a），將其

1,1

下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則數(shù)組中第30號元

素對應于矩陣中的元素是（C）。

A.aB.aC.aD.a

10,88,58,29,2

7、字符串a(chǎn)1="BEIJING"，a2="BEI"，a3="BEFANG"，a4="BEFI"中最大的是（C）。

A.a3B.a4C.a1D.a2

8、程序段chara[]=“English”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}

結果中，n的值是（D）。

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

9、在一棵二叉樹中，若編號為5的結點存在左孩子，則左孩子的順序編號為（D）。

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

10、設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2，該樹結點中共有20

個指針域為空。則該樹有（A）個葉結點。

A.10B.9C.22D.21

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

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

A.abcefdgB.acfdebgC.abcedfgD.aebcfdg

12、在有序表{10，23，32，36，53，66，68，76，87，90，101，120}中，用折半查找值

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

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

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

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

A.26/11B.29/11C.33/11D.30/11

14、設已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的

交換就使第m+1個元素排序到位，該方法是（D）。

A.歸并排序B.快速排序C.堆排序D.簡單選擇排序

15、一組記錄的關鍵字序列為（32，65，42，24，26，80），利用快速排序，以第一個關鍵

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

A.26，24，32，42，65，80B.26，24，32，65，42，80

C.24，26，32，42，65，80D.26，24，32，80，42，65

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

16、結構中的數(shù)據(jù)元素存在一對多的關系稱為樹型結構。

17、棧的操作特點是后進先出。

18、廣義表的(a，(a，b)，d，e，((i，j)，k))深度是3。

19、廣義表((a，b)，d，e，((i，j)，k))的長度是4。

20、設順序隊列的類型為

typedefstruct

{

ElemTypedata[MaxSise];

intfront,rear;

}Squeue;

Squeue*sq;

sq為指向順序隊列的指針變量，要進行元素的出隊操作，并把元素賦給邊量x，按教科書約

定，可用語句x=sq->data[sq->front];和sq->fronf++;。

21、設順序隊列的類型為

typede