期末考試題型:

選擇題(20題，1分/題)、填空題(10空，1分/空)、

算法與應(yīng)用題(7題，10分/題)

數(shù)據(jù)結(jié)構(gòu)試卷(二)

一、選擇題(24分)

1.下面關(guān)于線性表的敘述錯(cuò)誤的是(D)。

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

(B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

(0線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)

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

2.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共

有(B)個(gè)空指針域。

(A)2m-1(B)2m(C)2m+l(D)4m

3.設(shè)順序循環(huán)隊(duì)列Q[0：MT]的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素

的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為(C)。

(A)R-F(B)F-R(C)(R-F+M)(D)(F-R+M)%M

4.設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹

得到序列為(A)。

(A)BADC(B)BCDA(C)CDAB(D)CBDA

5.設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有(A)條邊。

(A)n(n-l)/2(B)n(n-1)(C)n2(D)n2-l

6.設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為(C)。

(A)9(B)10(C)11(D)12

7.設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有(B)個(gè)表頭結(jié)點(diǎn)。

(A)n-1(B)n(C)n+1(D)2n-l

8.設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快

速排序的結(jié)果為(C)?

(A)2,3,5,8,6(B)3,2,5,8,6

(C)3,2,5,6,8(D)2,3,6,5,8

二、填空題(24分)

1.為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個(gè)問題是構(gòu)造?個(gè)好的HA必函數(shù)和確

定解決沖突的辦法。

2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。

typedefstruct{intsllOOJ;inttop;}sqstack;

voidpush(sqstack&stack,intx)

if(stack.top==m-l)printf("overflow’‘)；

else{stack.top++:stack.sfstack.top|=x：)

3.中序遍歷二叉排序樹所得到的序列是有序序列(填有序或無序)。

4.快速排序的最壞時(shí)間復(fù)雜度為”112,平均時(shí)間復(fù)雜度為0(nlog2n)。

5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為N?則該二叉樹中度數(shù)為

2的結(jié)點(diǎn)數(shù)為忙1；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有2N0+\

個(gè)空指針域。

6.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則

7.設(shè)一組初始記錄關(guān)鍵字序列為列5,63,44,38,75,80,31,56),則利用篩選法建立

的初始堆為(31,38,44,56,75,80,55,63)。

8.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是

(1.345.2),BFS遍歷的輸出序列是33245)

圖的鄰接表存緒結(jié)構(gòu)

三、應(yīng)用題(36分)

1.設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇

排序和第4趟直接插入排序后的結(jié)果。

解:(22,40,45,48,80,78),(40,45,48,80,22,78)

2.。

3.設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用

二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長

度。

解：比較次數(shù)：2。ASL=(1*1+2*2+3*4+4*2)/9=25/9

4.設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求

用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。

解：

2

5.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

解:E{(1,3),(1,2)(3,5),(5,6),(6,4)}

6.設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給

出構(gòu)造過程。

1.設(shè)有一組初始記錄關(guān)鍵字序列(K.,及，…，K?),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間

復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于K,右半部分的每

個(gè)關(guān)鍵字均大于等于降。

3

數(shù)據(jù)結(jié)構(gòu)試卷(四)

一、選擇題(每題1分共20分)

1.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為(C)。

2

(A)0(n)(B)0(nlog2n)(C)0(1)(D)0(n)

2.設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有(D)個(gè)結(jié)點(diǎn)。

(A)2k-1(B)2k(C)(D)2-1

3.設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為(D)。

(A)n(B)e(C)2n(D)2e

4.在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為(B)o

2

(A)0(1)⑻0(n)(C)0(log2n)(D)0(n)

5.設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有(C)條有向邊。

(A)n(B)n-1(C)m(D)m-1

6.設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行(A)

趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

(A)3(B)4(C)5(D)8

7.設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作(B)。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(0判別棧元素的類型(D)對(duì)棧不作任何判別

8.下列四種排序中(A)的空間復(fù)雜度最大。

(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

9.設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為N“度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,

則下列等式成立的是(C)。

(A)No=M+l(B)(C)(D)

NO=NI+N2NO=N2+1N0=2NI+1

10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不

超過(A),

(A)logan+l⑻logzn-l(C)log2n(D)log2(n+l)

二、填空題(每空1分共20分)

1.設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為0(/),快速排序的平均

時(shí)間復(fù)雜度為度nlog2n)。

2.設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為

p-〉llink-〉rlink=p-〉rlink;p->rlink->llink=p->rlink(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別

為“ink和rlink).

3.根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為3。

4.深度為k的完全二叉樹中最少有蠹個(gè)結(jié)點(diǎn)。

5.設(shè)初始記錄關(guān)鍵字序列為(L,…，K,,),則用篩選法思想建堆必須從第屋個(gè)元素

開始進(jìn)行篩選。

6.設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有改個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)

構(gòu)，則該樹中有皿個(gè)空指針域。

7.設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)MT個(gè)隊(duì)列元

素；當(dāng)前實(shí)際存儲(chǔ)(R-F+MKM個(gè)隊(duì)列元素(設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置,

尾指針指向當(dāng)前隊(duì)尾元素的位置)。

4

8.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中

i個(gè)數(shù)據(jù)元素;刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中0個(gè)元素。

9.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則以20為中軸的一趟快速

排序結(jié)果為(1948,16.20,30,22)。

10.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列

建成的初始堆為(1618.19,20*32.22)。

11.設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j

互為鄰接點(diǎn)的條件是AlillikL

12.設(shè)無向圖對(duì)應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個(gè)數(shù)笠王第i列上非0元素的

個(gè)數(shù)(填等于，大于或小于)。

13.設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷

該二叉樹的序列為BDCAo

三、計(jì)算題(每題10分，共30分)

1、。

2、下圖所示的森林：

(1)求樹(a)的先根序列和后根序列;

(2)求森林先序序列和中序序列；

解：⑴先根序列：ABCDEF?后根序列:BDEFCA。

(2)森林先序序列:AKCDEFGHIJK中序序列:BDEFCAIJKHG

(3)

3、設(shè)散列表的地址范圍是[0..9],散列函數(shù)為H(key)=(key2+2)MOD9,并采用鏈

表處理沖突，請(qǐng)畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。

解:H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

5

0

1

2

3

4-^n

5

6二疝王EE

7

8

9

四、算法設(shè)計(jì)題（每題io分，共30分）

1.。

2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。

6

數(shù)據(jù)結(jié)構(gòu)試卷(五)

一、選擇題(20分)

1.數(shù)據(jù)的最小單位是(A)o

(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

2.設(shè)一組初始記錄關(guān)鍵字序列為(50,40,95,20,15,70,60,45),則以增量d=4的一

趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為(B)。

(A)40,50,20,95(B)15,40,60,20

(C)15,20,40,45(D)45,40,15,20

3.設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5

個(gè)長度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)

果為(A)o

(A)15,25,35,50,20,40,80,85,36,70

(B)15,25,35,50,80,20,85,40,70,36

(C)15,25,35,50,80,85,20,36,40,70

(D)15,25,35,50,80,20,36,40,70,85

4.函數(shù)substr("DATASTRUCTURE”，5,9)的返回值為(A)。

(A)“STRUCTURE”(B)“DATA”

(C)“ASTRUCTUR”(D)“DATASTRUCTURE”

5.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序,

則該操作的時(shí)間復(fù)雜度為(D)o

2

(A)0(log2n)(B)0(1)(C)0(n)(D)0(n)

6.設(shè)一棵m叉樹中度數(shù)為。的結(jié)點(diǎn)數(shù)為N。，度數(shù)為1的結(jié)點(diǎn)數(shù)為Ni,……,度數(shù)為m的結(jié)

點(diǎn)數(shù)為Nm,則No=(B)。

(A)NiW....+Nm(B)1+N2+2N3+3N4+....+(m-l)Nm

(C)N2+2N3+3N4+...+(m_l)Nm(D)2Ni+3Nz+....+(m+1)Nm

7.設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較(B)次。

(A)25(B)10(C)7(D)1

8.設(shè)連通圖G中的邊集￡={佰，b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從

頂點(diǎn)a出發(fā)不可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為(B)。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb

9.設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n,則輸出

序列中第i個(gè)輸出元素是(C)。

(A)n-i(B)n-l-i(C)n+l-i(D)不能確定

10設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個(gè)記錄關(guān)鍵字45

為基準(zhǔn)而得到一趟快速排序的結(jié)果是(C)。

(A)40,42,45,55,80,83(B)42,40,45,80,85,88

(C)42,40,45,55,80,85(D)42,40,45,85,55,80

二、填空題(共20分)

1.設(shè)有一個(gè)順序共享?xiàng)[0：n-1],其中第一個(gè)棧項(xiàng)指針topi的初值為-1,第二個(gè)棧頂

指針top2的初值為n,則判斷共享?xiàng)M的條件是topl=top2T。

2.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的

簡單鏈表。

7

3.設(shè)有一個(gè)n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對(duì)角線

上元素)存放在n(n+l)個(gè)連續(xù)的存儲(chǔ)單元中，則與A[0][0]之間有

i(i+l)/2+j-l個(gè)數(shù)據(jù)元素。

4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為一

后進(jìn)先出(F1L0)表;隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素

必定先出隊(duì)列，所以又把隊(duì)列稱為先進(jìn)先出(FIFO)表。

5.設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷

序列為ABDECF,中序遍歷序列為DBEAFC,后序遍歷序列為DEBFCA。

6.設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為―,有64個(gè)葉子

結(jié)點(diǎn)。

7.設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等

于頂點(diǎn)i的出度，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的入度。

8.設(shè)一組初始記錄關(guān)鍵字序列(k“k2,……,k.)是堆，則對(duì)i=l,2,…，n/2而言滿足

的條件為K〈=K2i&&KK=K2E。

三、應(yīng)用題(32分)

1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹的

的后序遍歷序列。

2.設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊

上的權(quán)值之和。

最小生成樹的權(quán)值之和W=10

3.設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計(jì)算出成功查找時(shí)

的平均查找長度。

22

口，'口

15*6。

7

8

4.設(shè)散列表的長度為8,散列函數(shù)H(表=kmod7,初始記錄關(guān)鍵字序列為(25,31,8,27,

13,68),要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

答案：H(25)=4H(31)=3H(8)=lH(27)=6H(13)=6H(68)=5

1、線性探測法：

地址0123456

關(guān)鍵/p>

查找次數(shù)211111

ASL=(2+1+1+1+1+1)/6=1.67

2、鏈地址法：1

其中，8,31,25,68,13關(guān)鍵字都比較了1次，27比較了2次

所以ASL=(l+l+l+l+l+2)/6=l.67

四、算法設(shè)計(jì)題(28分)

1.設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。

2.設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。

9

數(shù)據(jù)結(jié)構(gòu)試卷(七)

一、選擇題(30分)

1.設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有(B)個(gè)表頭結(jié)點(diǎn)。

(A)2n(B)n(C)n/2(D)n(n-l)

2.設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有(B)條邊。

(A)n(B)n-1(C)2n(D)2n-l

3.設(shè)一組初始記錄關(guān)鍵字序列為(60,80,55,40,42,85),則以第一個(gè)關(guān)鍵字45為基準(zhǔn)

而得到的一趟快速排序結(jié)果是(C)。

(A)40,42,60,55,80,85(B)42,45,55,60,85,80

(C)42,40,55,60,80,85(D)42,40,60,85,55,80

4.(B)二叉排序樹可以得到一個(gè)從小到大的有序序列。

(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

5.設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)

點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為(B

(A)2i+l(B)2i(C)i/2(D)2iT

6.程序段s=i=0；do{i=i+l；s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為(A)?

23

(A)0(n)(B)0(nlog2n)(C)0(n)(D)0(n/2)

7.設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是(C).,

(A)head==0(B)head->next==0

(C)head->next==head(D)head!=0

8.設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點(diǎn)最多有(C)?

(A)20(B)256(C)512(D)1024

9.設(shè)一組初始記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),則利

用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為(B)。

(A)1(B)2(03(D)4

10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為(D)。

(A)top=top+l;(B)top=top-l;

(C)top->next=top;(D)top=top->next;

二、判斷題(20分)

1.不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。(V)

2.當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。(J)

3.設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為OQown)。(V)

4.完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。(J)

5.哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。(V)

6.對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。(J)

7.先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。(J)

8.由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空.(X)

9.線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。(X)

10.帶權(quán)無向圖的最小生成樹是唯一的。(X)

三、填空題(30分)

10

1.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A

的后面插入結(jié)點(diǎn)X的操作序列為s->left__=p；s->right=p->right；

p->right=s；p->right->left=s；(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right)。

2.設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有n(n+1)條有向條:設(shè)完全無

向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中共有n(n+1)/2條無向邊。

3.設(shè)關(guān)鍵字序列為(Ki,K2,K“)，則用篩選法建初始堆必須從第」一個(gè)元素開始進(jìn)行篩

選。

4.解決散列表沖突的兩種方法是開放定址法和鏈地址法o

5.設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為

3的結(jié)點(diǎn)數(shù)有14個(gè)。

6.高度為h的完全二叉樹中最少有2h'個(gè)結(jié)點(diǎn),最多有2匚1個(gè)結(jié)點(diǎn)。

7.設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后

的結(jié)果的是12,24,27,35,18,26________。

8.設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟簡單選擇排序結(jié)束后

的結(jié)果的是12,18,24,27,35,26。

9.設(shè)一棵二叉樹的前序序列為ABC,則有5種不同的二叉樹可以得到這種序列。

(C67n+1)

10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語句。

structrecord{intkey;datatypeothers;};

voidquickpass(structrecordrl],ints,intt,int&i)

(

intj=t;structrecordx=r[s];i=s;

while(i<j)

(

while(i<j&&r[jJ.key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+l;}

while(i<j&&Hil.keyvx.key)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

)

_r[il=x_____;

四、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。

2.設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。

II

數(shù)據(jù)結(jié)構(gòu)試卷(九)

一、選擇題(30分)

1.下列程序段的時(shí)間復(fù)雜度為(A)o

for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；

for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；

(A)0(m*n*t)(B)0(m+n+t)(C)0(m+n*t)(D)0(m*t+n)

2.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)(A)個(gè)元素。

(A)n-i(B)n+1-i(C)n-l-i(D)i

3.設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B,T1、T2和T3的結(jié)點(diǎn)

數(shù)分別為Nl、N2和N3,則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為(A)?

(A)Nl-1(B)N2-1(C)N2+N3(D)N1+N3

4.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為(C)o

2

(A)0(n)(B)0(nlog2n)(C)0(n)(D)0(log2n)

5.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后

面插入結(jié)點(diǎn)X的操作序列為(D)?

(A)p->right=s；s->left=p；p->right->left=s；s->right=p->right；

(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；

(C)p->right=s；p->righl->left=s；s->left=p；s->right=p->right；

(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；

6.下列各種排序算法中平均時(shí)間復(fù)雜度為0(i?)是(D)?

(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序

7.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n,則輸出序列

中的第i個(gè)輸出元素是(C)。

(A)n-i(B)n-l-i(C)n+1-i(D)不能確定

8.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p,則p最好選擇(B)。

(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)

(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)

9.設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)

為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為。的結(jié)點(diǎn)數(shù)有(C)個(gè)。

(A)4(B)5(06(D)7

10.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有(A)條邊。

(A)n(n-l)/2(B)n(n-l)(C)n(n+l)/2(D)(n-l)/2

11.設(shè)順序表的長度為n,則順序查找的平均比較次數(shù)為(C)。

(A)n(B)n/2(0(n+l)/2(D)(n-l)/2

12.設(shè)有序表中的元素為(13,18,24,35,47,50,62),則在其中利用二分法查找值為24

的元素需要經(jīng)過(C)次比較。

(A)1(B)2(C)3(D)4

13.設(shè)順序線性表的長度為30,分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查

找長度為(D)o

(A)6(B)11(C)5(D)6.5

14.設(shè)有向無環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},則下列屬于

該有向圖G的一種拓?fù)渑判蛐蛄械氖?A)?

(A)1,2,3,4(B)2,3,4,1(C)1,4,2,3(D)1,2,4,3

12

15.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,45,18,26,54,92),則由這組記錄關(guān)鍵字

生成的二叉排序樹的深度為(A)?

(A)4(B)5(C)6(D)7

二、填空題(30分)

1.設(shè)指針p指向單鏈表中結(jié)點(diǎn)A,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的前面插入結(jié)

點(diǎn)X時(shí)的操作序列為：

1)s->next=p->next；2)p->next=s；3)t=p->data；

4)p->data=s->data；5)s->data=t；

2.設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有阻個(gè)葉子結(jié)點(diǎn)。

3.設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)

尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)m-1列元素。

4.對(duì)一組初始關(guān)鍵字序列(40,50,95,20,15,70,60,45,10)進(jìn)行冒泡排序，則

第一趟需要進(jìn)行相鄰記錄的交換的次數(shù)為6,在整個(gè)排序過程中最多需要進(jìn)行工趟排

序才可以完成。

5.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇

快速排序,如果從節(jié)省存儲(chǔ)空間的角度來考慮則最好選擇堆排序。

6.設(shè)一組初始記錄關(guān)鍵字序列為(20,12,42,31,18,14,28),則根據(jù)這些記錄關(guān)鍵

字構(gòu)造的二叉排序樹的平均查找長度是19/7?

7.設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序

列為CBDA。

8.設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、

32、3、21、10,根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為

9.設(shè)一組記錄關(guān)鍵字序列為(80,70,33,65,24,56,48),則廣、4

用篩選法建成的初始堆為(24,65,33,80,70,56,48)。CO2tQ

io.設(shè)無向圖G(如右圖所示)，則其最小生成樹上所有邊的權(quán)值之

和為*14

三、判斷題(20分)—6O

1.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。(X)

2.對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。(V)

3.子串“ABC”在主串“AABCABCD”中的位置為2。(7)

4.若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序

遍歷序列中的最后一個(gè)結(jié)點(diǎn)。(J)

5.希爾排序算法的時(shí)間復(fù)雜度為0(/)?(X)

6.用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊

數(shù)有關(guān)。(X)

7.中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。(J)

8.入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。(J)

9.順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。(X)

10.堆是完全二叉樹，完全二叉樹不一定是堆。(J)

五、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。

2.設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。

3.

某工廠生產(chǎn)一件產(chǎn)品需要經(jīng)過a0,al,a2,a3,a4五道工序，每一道工序所花的時(shí)間和前

13

驅(qū)工序如下表所示，其中“一”表示無先驅(qū)工序。請(qǐng)分析下表并完成以下問題。(10分)

工序代碼a0ala2a3a4

所需時(shí)間43246

先驅(qū)工序--a0al,a2aO

(1)畫出相應(yīng)的AOE網(wǎng)；(3分)

(2)列出各事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間；(3分)

(3)求出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。(4分)

算法設(shè)計(jì)題：

1、使用頭插法創(chuàng)建單鏈表，補(bǔ)充BEGIN-END之間的內(nèi)容。

//單鏈表基本運(yùn)算算法

typedefstructLNode

(

intdata;

structLNode*next;〃指向后繼結(jié)點(diǎn)

}LinkNode;〃聲明單鏈表結(jié)點(diǎn)類型

voidCreateListF(LinkNode*&L,inta[],intn)

〃頭插法建立單鏈表

(

LinkNode*s;

L=(LinkNode*)malloc(sizeof(LinkNode));〃創(chuàng)建頭結(jié)點(diǎn)

L->next=NULL;

/**********BEGIN**********/創(chuàng)建n個(gè)s節(jié)點(diǎn)并為每個(gè)節(jié)點(diǎn)賦值，然后插入頭結(jié)點(diǎn)之后

/**********END**********/

)

2、補(bǔ)充BEGIN-END之間的內(nèi)容，完成先序遞歸遍歷算法

^include<stdio.h>

^include<malloc.h>

typedefstructnode

(

chardata;〃數(shù)據(jù)元素

structnode*lchild;〃指向左孩子節(jié)點(diǎn)

structnodeSchild;〃指向右孩子節(jié)點(diǎn)

}BTNode;

14

voidPreOrder(BTNode*b)〃先序遍歷的遞歸算法

(

/**********BEGIN**********/

〃在b存在的情況下，先訪問根節(jié)點(diǎn)，然后遞歸左子樹，最后遞歸右子樹

/**********END**********/

}

3、補(bǔ)充BEGIN-END之間的內(nèi)容,完成kruskal算法

#include<stdio.h>

ttinclude<malloc.h>

typedefstruct

{intedges[MAXV][MAXV];〃鄰接矩陣數(shù)組

intn,e;〃頂點(diǎn)數(shù)，邊數(shù)

}MatGraph;〃完整的圖鄰接矩陣類型

typedefstruct

intu;〃邊的起始頂點(diǎn)

intv;〃邊的終止頂點(diǎn)

intw;〃邊的權(quán)值

}Edge;

voidKruskal(MatGraphg)

(

inti,j,ul,vl,snl,sn2,k;

intvset[MAXV];

EdgeE[MaxSize];〃存放所有邊

k=0;//E數(shù)組的下標(biāo)從0開始計(jì)

for(i=0;i<g.n;i++)〃由g產(chǎn)生的邊集E

for(j=0;j<=i;j++)

(

if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)

E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];

k++;

}

)

InsertSort(E,g.e);〃采用直接插入排序?qū)數(shù)組按權(quán)值遞增排序

for(i=0;i<g.n;i++)〃初始化輔助數(shù)組

vset[i]=i;

k=l;//k表示當(dāng)前構(gòu)造生成樹的第幾條邊,初值為1

j=0；//E中邊的下標(biāo),初值為0

15

while(k<g.n)〃生成的邊數(shù)小于n時(shí)循環(huán)

(

ul=E[j].u;vl=E[j].v;〃取一條邊的頭尾頂點(diǎn)

snl=vset[ul];sn2=vset[vl];〃分別得到兩個(gè)頂點(diǎn)所屬的集合編

if(snl!=sn2)〃兩頂點(diǎn)屬于不同的集合,該邊是最小生成樹的一條邊

{printf(〃(%d,%d):%d\n”,ul,vl,E[j].w);

/**********BEGIN**********/

〃生成邊數(shù)k增1,兩個(gè)集合統(tǒng)一編號(hào)，將集合編號(hào)為sn2的改為snl

/**********END**********/

)

j++;〃掃描下一條邊

)

}

4、補(bǔ)充BEGIN-END之間的內(nèi)容，完成DFS算法

#include<stdio.h>

Sinclude<malloc.h>

typedefstructANode

{intadjvex;〃該邊的鄰接點(diǎn)編號(hào)

structANode*nextarc;〃指向下一條邊的指針

intweight;〃該邊的相關(guān)信息，如權(quán)值(用整型表示)

}ArcNode;〃邊結(jié)點(diǎn)類型

typedefstructVnode

{InfoTypeinfo;〃頂點(diǎn)其他信息

intcount;〃存放頂點(diǎn)入度,僅僅用于拓?fù)渑判?/p>

ArcNode*firstarc;〃指向第一條邊

}VNode;〃鄰接表頭結(jié)點(diǎn)類型

typedefstruct

{VNodeadjlist[MAXV];〃鄰接表頭結(jié)點(diǎn)數(shù)組

intn,e;〃圖中頂點(diǎn)數(shù)n和邊數(shù)e

}AdjGraph;〃完整的圖鄰接表類型

intvisited[MAXV]={0};

voidDFS(AdjGraph*G,intv)

(

ArcNode*p;

visited[v]=l;〃置已訪問標(biāo)記

printf(z，%d〃，v);〃輸出被訪問頂點(diǎn)的編號(hào)

/**********BEGIN**********/

/*

P指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)，當(dāng)p不為空時(shí):

16

如果p->adjvex