數(shù)據(jù)結(jié)構(gòu)原理與分析

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)原理與分析

數(shù)據(jù)結(jié)構(gòu)原理與分析-01343-18日下-復(fù)習(xí)資料一、填空

1.線性表是具有n個什么的有限序列（數(shù)據(jù)元素）。

2.鄰接表的存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹的(先序遍歷)。

3.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2）。4.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹(高度等于其結(jié)點數(shù))。

5.對于棧操作數(shù)據(jù)的原則是（后進先31.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（11）

32.在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（n+1）

33.若一棵二叉樹有11個度為2的結(jié)點，則該二叉樹的葉結(jié)點的個數(shù)是（12）。34.對有n個記錄的表按記錄鍵值有序建立二叉查找樹，在這種狀況下，其平均查找長度的量級為（O(n)）。35.設(shè)森林F中有三棵樹，第一、其次和第三棵的結(jié)點個數(shù)分別為m1,m2和m3,則森林F對應(yīng)的二叉樹根結(jié)點上的右子樹上結(jié)點個數(shù)是(m2+m3)。

36.對有18個元素的有序表作二分（折半）查找，則查找A[3]的比較序列的下標為（9、弟結(jié)點（包括A自身），B是A的雙親結(jié)點，

則B的度為（4）。

60.深度為h的滿二叉樹具有的結(jié)點個數(shù)為（2h+1-1）。

61.用二叉鏈表存儲樹，則根結(jié)點的右指針是（空）。62.個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（1）倍。

63.單鏈表表示的鏈式隊列的隊頭在鏈表的什么位置（鏈頭）。

64.線性表的長度是指（表中的元素個數(shù)）

65.某二叉樹的前序和后序序列正好一致，則該二叉樹一定是什么樣的二叉樹(空或只有一個結(jié)點)。

66.在一棵具有n個結(jié)點的二叉樹中，所有91.設(shè)根結(jié)點的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點的層數(shù)加1，則高度為k的二叉樹具有的結(jié)點數(shù)目，最少為k，最多為2k-1。

92.在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩(wěn)定的排序方法有直接插入排序。

93.具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為50。

94.普里姆(Prim)算法適用于邊稠密圖。95.在有n個葉子結(jié)點的哈夫曼樹中,其結(jié)點總數(shù)為2n-1。

96.將一棵樹轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點沒有右子樹。

97.矩陣采用壓縮存儲是為了節(jié)省空間98.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不一致，則出）。

6.結(jié)點前序為xyz的不同二叉樹，所具有的不同形態(tài)為(5)。

7.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊操作的時間繁雜度為(O(n))。

8.在一棵高度為h(假定樹根結(jié)點的層號為0)的完全二叉樹中，所含結(jié)點個數(shù)不小于(2h)。

9.具有n個頂點的有向無環(huán)圖最多可包含有向邊的條數(shù)是(n(n-1)/2)。

10.因此在初始為空的隊列中插入元素

a,b,c,d以后，緊接著作了兩次刪除操作，此時的隊尾元素是(d).

11.若二叉樹中度為2的結(jié)點有15個，度為1的結(jié)點有10個，則葉結(jié)點的個數(shù)（16）。12.對于一棵滿二叉樹，m個樹葉，n個結(jié)點，深度為h,則(n=2h＋1-1)。13.在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（n+1）

14.用鄰接表表示圖進行深度優(yōu)先遍歷時，尋常用來實現(xiàn)算法的輔助結(jié)構(gòu)是(棧)。15.堆的形狀是一棵(完全二叉樹)。16.若在一棵非空樹中，某結(jié)點A有3個兄弟結(jié)點（包括A自身），B是A的雙親結(jié)點，則B的度為(4)。

17.任何一個無向連通圖的最小生成樹(有一棵或多棵)

18.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點的左邊應(yīng)當(只有左子樹上的所有結(jié)點)。

19.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。

20.對于一棵滿二叉樹，m個樹葉，n個結(jié)點，深度為h,則(n=2h＋1-1)。21.具有n個頂點的有向圖最多可包含的有向邊的條數(shù)是(n(n-1))。

22.某二叉樹的前序和后序序列正好一致，則該二叉樹一定是什么樣的二叉樹(空或只有一個結(jié)點)。

23.棧和隊列的主要區(qū)別在于(插入刪除運算的限定不一樣)。24.串是（任意有限個字符構(gòu)成的序列）。25.對有14個數(shù)據(jù)元素的有序表R[14]進行折半探尋，探尋到R[3]的關(guān)鍵碼等于給定值，此時元素比較順序依次為（R[6]，R[2]，R[4]，R[3]）。26.深度為h且有多少個結(jié)點的二叉樹稱為滿二叉樹(2h+1-1)。

27.在含n個頂點e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（n2-2e）。28.在一個有向圖中，所有頂點的入度之和與所有頂點出度之和的倍數(shù)為(1)。29.鄰接表的存儲結(jié)構(gòu)下圖的廣度優(yōu)先遍歷類似于二叉樹的(按層遍歷)。

30.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為(2h-1)。

4、2、3）。

37.若要在O（1）的時間繁雜度上實現(xiàn)兩個循環(huán)鏈表頭尾相接，則應(yīng)對兩個循環(huán)鏈表各設(shè)置一個指針，分別指向(各自的尾結(jié)點)。

38.深度為h的滿二叉樹所具有的結(jié)點個數(shù)是（2h+1-1）。

39.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（2h-1）。

40.假使T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的先根序列就是T2中結(jié)點的（先根序列）。

41.有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（2n-1）。

42.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊操作的時間繁雜度為(O(n))。

43.若二叉樹中度為2的結(jié)點有15個，度為1的結(jié)點有10個，則葉子結(jié)點的個數(shù)為（16）。

44.若某完全二叉樹的深度為h，則該完全二叉樹中具有的結(jié)點數(shù)至少是(2h－1)。45.叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹(度等于其結(jié)點數(shù))。

46.初始序列已經(jīng)按鍵值有序時，用直接插入算法進行排序，需要比較的次數(shù)為(n-1)。

47.接表表示圖進行廣度優(yōu)先遍歷時，為實現(xiàn)算法尋常采用的輔助結(jié)構(gòu)是(隊列)。48.用冒泡排序法對序列

{18,16,14,12,10,8}從小到大進行排序，需要進行的比較次數(shù)是(15)。

49.有n個頂點的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n）。

50.6個頂點的無向圖成為一個連通圖至少應(yīng)有邊的條數(shù)是（5）。51.單鏈表中，增加頭結(jié)點的目的是為了（便利運算的實現(xiàn)）。

52.在線索二叉樹中,結(jié)點(*t)沒有左子樹的充要條件是(t->ltag==1)。

53.依照二叉樹的定義,具有3個結(jié)點的二叉樹有多少種(5)。

54.對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是（快速排序）

55.二分查找法要求查找表中各元素的鍵值必需是(遞增或遞減)。

56.線性表的長度是指（表中的元素個數(shù)）57.將長度為m的單鏈表連接在長度為n的單鏈表之后的算法的時間繁雜度為(O(n))。

58.有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結(jié)點時，查找成功的比較次數(shù)是（4）。.59.若在一棵非空樹中，某結(jié)點A有3個兄

結(jié)點的空子樹個數(shù)等于（n+1）。

67.一個具有n個頂點e條邊的無向圖中，采用鄰接表表示，則所有頂點的鄰接表的結(jié)點總數(shù)為（2e）。68.鏈棧和順序棧相比，有一個較明顯的優(yōu)點是(尋常不會出現(xiàn)棧滿的狀況)。69.對于鍵值序列

{72,73,71,23,94,16,5,68,76,103}用篩選法建堆，開始結(jié)點的鍵值必需為(94)。70.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以有(任意多個)。71.對有n個記錄的有序表采用二分查找，其平均查找長度的量級為(O(log2n))。72.在一棵高度為h(假定樹根結(jié)點的層號為0)的完全二叉樹中，所含結(jié)點個數(shù)不小于(2h)。

73.若一棵二叉樹有10個葉結(jié)點，則該二叉樹中度為2的結(jié)點個數(shù)為9。

74.設(shè)有一個順序棧S，元素S1，S2，S3，S4，S5，S6依次進棧，假使6個元素的出棧順序為S2，S3，S4，S6，S5，S1，則順序棧的容量至少應(yīng)為3。

75.對于一棵二叉樹，設(shè)葉子結(jié)點數(shù)為n0,次數(shù)為2的結(jié)點數(shù)為n2,則n0和n2的關(guān)系是n0=n2＋1。

76.若一棵二叉樹有12個葉結(jié)點，則該二叉樹中度為2的結(jié)點個數(shù)為11。

77.二叉樹的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。

78.深度為h且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點處在第1層)。79.圖的深度優(yōu)先探尋方法類似于二叉樹的先序遍歷。

80.哈夫曼樹是帶權(quán)路徑長度最小的二叉樹。

81.在線索二叉樹中，線索是指向結(jié)點在某遍歷次序下的前驅(qū)或后繼結(jié)點的指針。82.?？梢宰鳛閷崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

83.一般樹的存儲結(jié)構(gòu)有雙親表示法、孩子兄弟表示法和孩子鏈表表示法。

84.將數(shù)據(jù)元素

2,4,6,8,10,12,14,16,18,20依次存于一個一維數(shù)組中，然后采用折半查找元素12，被比較過的數(shù)組元素的下標依次為5，7，6。。

85.圖的深度優(yōu)先遍歷序列不是唯一的。86.若二叉樹的一個葉子結(jié)點是某子樹的中根遍歷序列中的第一個結(jié)點，則它必是該子樹的后跟遍歷中的第一個結(jié)點。87.圖的遍歷是指從圖中某一頂點出發(fā)訪問圖中全部頂點且使每一頂點僅被_訪問一次。

88.在一個圖中，所有頂點的度數(shù)之和等于所有邊的數(shù)目的2倍。

89.由一棵二叉樹的后序序列和中序序列可唯一確定這棵二叉樹。

90.在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為2。

該圖的最小生成樹有1棵。

99.設(shè)無向圖G的頂點數(shù)為n，則要使G連通最少有n-1條邊。

100.棧和隊列的共同特點是插入和刪除均在端點處進行。

101.克魯斯卡爾(Kruskar)算法適用于邊稀疏圖。

102.若連通圖的頂點個數(shù)為n，則該圖的生成樹的邊數(shù)為n-1。

103.圖的存儲結(jié)構(gòu)最常用的有鄰接矩陣和鄰接表。

104.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。

105.隊列中允許進行插入的一端稱為隊尾。

106.拓撲排序輸出的頂點數(shù)小于有向圖的頂點數(shù)，則該圖一定存在環(huán)。

107.在有序表(15,23,24,45,48,62,85)中二分查找關(guān)鍵詞23時所需進行的關(guān)鍵詞比較次數(shù)為2。

108.樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（-1）。

109.在一個具有n個頂點的完全無向圖的邊數(shù)為(n(n-1)/2)。

110.用分劃交換排序方法對包含有n個關(guān)鍵的序列進行排序，最壞狀況下執(zhí)行的時間雜度為(O(n2))

111.一棵高度為h(假定樹根結(jié)點的層號為0)的完全二叉樹中，所含結(jié)點個數(shù)不小于(2h)。

112.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個數(shù)據(jù)元素，首先需要移動表中數(shù)據(jù)元素的個數(shù)是（n-i）。113.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點的左邊應(yīng)當(只有左子樹上的所有結(jié)點)。

114.若一棵二叉樹具有45個度為2的結(jié)點，6個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（46）。

115.在一個有向圖中，所有頂點的入度之和等于所有邊數(shù)（4）倍。

116.設(shè)輸入序列為A,B,C,D,借助一個棧不可以得到的輸出序列是(D,A,B,C)。117.一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6個字節(jié)，第6個元素的起始地址為100，則該數(shù)組的首地址是（70）。118.設(shè)abcdef以所給的次序進棧，若在進棧操作時，允許退棧操作,則下面得不到的序列為（cbdef）。

119.一般狀況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)當設(shè)置（堆棧）。

120.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個數(shù)據(jù)元素，i的合法值應(yīng)當

121.是（C.1≤i≤n）。

122.若某線性表中最常用的操作是取第i個元素和刪除最終一個元素，則采用什么存儲方

123.式最節(jié)省時間（順序表）。124.一組記錄的關(guān)鍵字為{45,80,55,40,

42,85}，則利用堆排序的方法建立的初始堆為（85,80,55,40,42,45）。

125.設(shè)有6000個無序的元素,希望用最快的速度挑揀出其中前5個最大的元素,最好選用(堆排序)法。

126.排序方法中，從未排序序列中挑揀元素，將其放入已排序序列的一端的方法，找，其查找不成功的平均長度是（n+1）。148.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（8）。

149.棧的插入和刪除操作進行的位置在（棧頂）。150.若一棵二叉樹具有20個度為2的結(jié)A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}

D.{05,23,16,68,73,71,72,94}

4.以下排序算法中,某一趟終止后未必能選出一個元素放其最終位置上的是(D)。A.堆排序B.冒泡排序C.快速排序D.則稱該排序是不穩(wěn)定的。不穩(wěn)定的排序方

法是（D）。A．起泡排序B．歸并排序C．直接插入法排序D．簡單項選擇擇排序18.將一棵有50個結(jié)點的完全二叉樹按層編號，則對編號為25的結(jié)點x，該結(jié)點(B)。A.無左、右孩子B.有左孩子，無右孩子C.有右孩子，無左孩子D.有左、右孩子稱為(選擇排序)。

點，6個度為1的結(jié)點，則度為0的結(jié)點直接插入排序

127.帶頭結(jié)點的單鏈表head為空的判斷個數(shù)是（21）。5.用孩子兄弟鏈表表示一棵樹，若要找到條件是(head->next==NULL)。

151.一棵線索二叉樹的線索個數(shù)比鏈接個結(jié)點x的第5個孩子，只要先找到x的第128.在一個單鏈表中，若刪除(*p)結(jié)點的數(shù)多（2）個。

一個孩子，然后(D)。

后繼結(jié)點，則執(zhí)行

152.在循環(huán)鏈表中，從任何一結(jié)點出發(fā)都A.從孩子域指針連續(xù)掃描5個結(jié)點即可B.(p->next=p->next->next)。

能訪問到表中的所有結(jié)點。

從孩子域指針連續(xù)掃描4個結(jié)點即可129.在一棵具有n個結(jié)點的二叉樹中，所153.在n個結(jié)點的順序表中插入一個結(jié)點C.從兄弟域指針連續(xù)掃描5個結(jié)點即可D.有結(jié)點的空子樹個數(shù)等于（n+1）需平均移動n/2個結(jié)點。

從兄弟域指針連續(xù)掃描4個結(jié)點即可130.有向圖中，以頂點v為終點的邊的數(shù)154.循環(huán)隊列的引入，目的是為了戰(zhàn)勝假6.鏈棧和順序棧相比，有一個較明顯的優(yōu)目，稱為頂點v的（入度）。

溢出。

點是(A)。

131.若頻繁地對線性表進行插入和刪除操155.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不一致，A.尋常不會出現(xiàn)棧滿的狀況B.尋常不會作，該線性表應(yīng)當采用的存儲結(jié)構(gòu)是（鏈則該圖的最小生成樹有1棵。出現(xiàn)?？盏臓顩r

式）。

156.二叉樹的遍歷方式有三種：先序遍歷、C插入操作更加便利D.刪除操作更加方132.設(shè)一個棧的輸入序列是1，2，3，4，中序遍歷、后序遍歷。

便

5,則以下序列中，是棧的合法輸出序列的157.若一棵二叉樹有15個葉結(jié)點，則該二7.任何一棵二叉樹的葉結(jié)點在其先根、中是（32154）。叉樹中度為2的結(jié)的點個數(shù)為14。根、后根遍歷序列中的相對位置(C)。133.有數(shù)據(jù){53，30，37，12，45，24，96}，158.設(shè)某二叉樹的后序遍歷序列為A.確定發(fā)生變化B.有時發(fā)生變化C.從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉ABKCBPM，則可知該二叉樹的根為M。確定不發(fā)生變化D.無法確定查找樹，若希望高度最小，則應(yīng)選擇下面159.數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)的規(guī)律結(jié)8.排序方法中，從未排序序列中挑揀元素，輸入序列是（37,24,12,30,53,45,96）。構(gòu)、物理結(jié)構(gòu)、運算。

將其放入已排序序列的一端的方法，稱為134.二叉樹的第I層上最多含有結(jié)點數(shù)為160.每個結(jié)點只有一個鏈接域的鏈表叫做(D)。

（2I）。

單鏈表。

A.希爾排序B.冒泡排序C.插入排序135.稀疏矩陣一般采用的壓縮存儲方法為161.組成串的數(shù)據(jù)元素只能是字符。D.選擇排序

(三元組表)。

162.具有n個結(jié)點的二叉樹采用鏈接結(jié)構(gòu)9.堆是一種什么排序（B）。A.插入B.選136.某二叉樹的前序和后序序列正好相存儲，鏈表中存放NULL指針域的個數(shù)為擇C.交換D.歸并

同，則該二叉樹一定是什么樣的二叉樹(空（n+1）。10.以下排序方法中不穩(wěn)定的排序是(C)?；蛑挥幸粋€結(jié)點)。

163.在一個無向圖中，所有頂點的度數(shù)之A.直接插入排序B.冒泡排序C.堆排序137.若長度為n的線性表采用順序存儲結(jié)和等于所有邊數(shù)（2）倍。

D.歸并排序

構(gòu)，在表的第i個位置插入一個數(shù)據(jù)元素，164設(shè)二叉樹根結(jié)點的層次為0，一棵高度11.一個無向連通圖的生成樹是含有該連需要移動表中元素的個數(shù)是（n-i+1）。為h的滿二叉樹中的結(jié)點個數(shù)是通圖的全部頂點的(A)。

138.設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長(2h+1-1)。

A.微小連通子圖B.極大連通子圖C.極度為3字節(jié)，i的值為1到8，j的值為165.將一棵有50個結(jié)點的完全二叉樹按小子圖D.極大子圖

1到10，數(shù)組從內(nèi)存首地址BA開始順序?qū)泳幪?，則對編號為25的結(jié)點x，該結(jié)點12.如下陳述中正確的是(A)。

存放，當用以列為主存放時，元素A[5，(有左孩子，無右孩子)。

A.串是一種特別的線性表B.串的長度必需8]的存儲首地址為(BA+180)。

166.樹（或樹形）的定義是什么？答：一大于零

139.二維數(shù)組A[5][6]的每個元素占5個個樹（或樹形）就是一個有限非空的結(jié)點B.串中元素只能是字母D.空串就是空白串單元，將其按行優(yōu)先順序存儲在起始地址集合T，其中有一個特別標出的稱為該樹13.快速排序不利于發(fā)揮其優(yōu)點的狀況是為3000的連續(xù)的內(nèi)存單元中，則元素之根A[4][5]的存儲地址為（3145）。

140.一個具有n個頂點的圖采用鄰接矩陣Troot（T）的結(jié)點；其余（除根外）（C）。的結(jié)點劃分成1,?m,?T0個不相交集合

m[A]待排序數(shù)據(jù)量太大[B]待排序數(shù)據(jù),而且這些集合的

一致值過多

表示，則該矩陣的大小為（n*n）。每一個又都是樹。

[C]待排序數(shù)據(jù)已基本有序[D]待排序數(shù)141.若字符串“1234567〞采用鏈式存儲，167在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點據(jù)值差過大

假設(shè)每個字符占用1個字節(jié)，每個指針占數(shù)和后續(xù)結(jié)點數(shù)可以有(任意多個)。14.性表中采用折半查找法查找元素，該線用2個字節(jié)，則該字符串的存儲密度為168.什么是樹的路徑長度？答：樹的路徑性表必需滿足（C）。（33.3﹪）。

長度是指從根結(jié)點到樹中每個葉結(jié)點的路[A]元素按值有序142.若在一棵非空樹中，某結(jié)點A有3個徑長度之和。[B]采用順序存儲結(jié)構(gòu)

兄弟結(jié)點（包括A自身），B是A的雙親結(jié)二、選擇

[C]元素按值有序，且采用順序存儲結(jié)構(gòu)點，則B的度為（3）。

1.若某線性表中最常用的操作是取第i個[D]元素按值有序，且采用鏈式存儲結(jié)構(gòu)143.設(shè)有三個元素X，Y，Z順序進棧（進元素和刪除最終一個元素，則采用什么存15.r在排序前已按元素鍵值遞增順序排的過程中允許出棧），以下得不到的出棧排儲方式最節(jié)省時間（A）。A.順序表B.單列，則比較次數(shù)較少的排序方法是(A)。列是(ZXY)。

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

A.直接插入排序B.快速排序C.歸并排144.樹形結(jié)構(gòu)的特點是：一個結(jié)點可以有2.在下述的排序方法中，不屬于內(nèi)排序方序D.選擇排序

(多個直接后繼)。

法的是（C）。16.一個遞歸的定義可以用遞歸過程求解，145.使具有30個頂點的無向圖成為一個A.插入排序法B.選擇排序法C.拓撲排序也可以用非遞歸過程求解，但單從運行時連通圖至少應(yīng)有邊的條數(shù)是（29）。

法D.歸并排序法

間來看，尋常遞歸過程比非遞歸過程（B）146.使具有9個頂點的無向圖成為一個連3.以下四個關(guān)鍵詞序列中,不是堆的序列A．較快B．較慢C．一致D.不確定通圖至少應(yīng)有邊的條數(shù)是（8）。

為(C)。

17.假使待排序序列中兩個數(shù)據(jù)元素具有147.在順序表（n足夠大）中進行順序查

一致的值，在排序后它們的位置發(fā)生顛倒，

三、簡答

1.對于一個隊列，假使輸入項序列由1,2,3,4所組成，試給出全部可能的輸出序列。答：1,2,3,4。

2.將表達式(a+b)*c+d-(e+g)*h改寫成后綴表達式。答：后綴表達式為：ab+c*d+eg+h*-

3.對于一個棧，給出輸入序列A，B，C，試給出全部可能的輸出序列。答：解：輸出序列為：ABC，CBA,ACB,BAC,BCA。

19.若某鏈表最常用的操作是在最終一個結(jié)點之后插入一個結(jié)點和刪除最終一個結(jié)點，則采用那種存儲方式最節(jié)省時間(C)。A.單鏈表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表

20.以下排序算法中,第一趟排序完畢后,其最大或最小元素一定在其最終位置上的算法是(D)。

A.歸并排序B.直接插入排序C.快速排序D.冒泡排序

21.樹形結(jié)構(gòu)最適合用來描述（C）。[A]有序的數(shù)據(jù)元素[B]無序的數(shù)據(jù)元素

[C]數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)[D]數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)22.設(shè)有7000個無序的元素,希望用最快的速度挑揀出其中前5個最大的元素,最好選用方法是(C)。

A.冒泡排序B.快速排序C.堆排序D.基數(shù)排序

23.鏈表不具有的特點是(A)。A.可隨機訪問任一元素B.插入刪除不需要移動元素

C.不必事先估計存儲空間D.所需空間與線性表長度成正比

24.若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則比較次數(shù)最少的方法排序是（A）。

A．直接插入排序B．快速排序C．歸并排序D．直接選擇排序

25.以下關(guān)鍵字序列中是堆的序列為(D)。A.16,72,31,23,94,53B.94,23,31,72,16,53

B.16,53,23,94,31,72D.16,23,53,31,94,72

26.以下四個關(guān)鍵字序列中,那個序列不是堆(C)。

A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}

C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}27.下面4個序列中，滿足堆的定義是（D）。A.13,27,49,76,76,38,85,97B.76,38,27,49,76,85,13,97

C.13,76,49,76,27,38,85,97D.13,27,38,76,49,85,76,97

28.采用線性探查法處理沖突所構(gòu)成的散列表上進行查找，可能要探測到多個位置，在查找成功狀況下，所探測的這些位置上的鍵值（D）。

A.一定都是同義詞B.一定都不是同義詞C.都一致D.不一定都是同義詞29.性表中采用折半查找法查找元素，該線性表必需滿足（C）。[A]元素按值有序[B]采用順序存儲結(jié)構(gòu)

[C]元素按值有序，且采用順序存儲結(jié)構(gòu)[D]元素按值有序，且采用鏈式存儲結(jié)構(gòu)

4．將算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式。答：B．a(chǎn)bcde/+*+

5.由權(quán)值為12，6，5，9,10的五個葉子結(jié)點構(gòu)造一棵哈夫曼樹，請問該樹的帶權(quán)路徑長度是多少？答：權(quán)值為95。

6.由二叉樹的前序和后序遍歷序列能否唯一確定一棵二叉樹。若不能請舉出反例。答：不能唯一確定一棵二叉樹。如下圖。

123

2

1

3

7.求出下圖所示有向圖的鄰接矩陣。2VV731VV54

V

答：有向圖的鄰接矩陣為：

01234

027∞10∞0∞∞∞1∞∞05∞2∞∞∞0∞33∞∞404

8.有n個頂點的無向連通圖至少有多少條邊？有n個頂點的有向連通圖至少有多少條邊？答：有n個頂點的無向連通圖至少有n-1條邊，有n個頂點的有向連通圖至少有n條邊。

9．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？

答：起泡排序,直接插入排序，歸并排序是穩(wěn)定的。10.為什么說樹是一種非線性結(jié)構(gòu)？

樹中的每個結(jié)點除了根結(jié)點外，其余每個結(jié)點有一個直接前驅(qū)，但有多個直接后繼，所以說樹是一種非線性結(jié)構(gòu)。11．已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。

前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列為：C,B,F,E,I,J,H,G,D,A

12．試述順序存儲和鏈式存儲的區(qū)別及各自的優(yōu)缺點。

答：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點的空間連續(xù)。

1）插入與刪除操作：由于數(shù)組在插入與刪除數(shù)據(jù)時需移動大量的數(shù)據(jù)元素，而鏈表只需要改變一些指針的鏈接，因此，鏈表比數(shù)組易于實現(xiàn)數(shù)據(jù)的插入和刪除操作。

2）內(nèi)存空間的占用狀況：因鏈表多了一個指針域，故較浪費空間，因此，在空間占用方面，數(shù)組優(yōu)于鏈表。

3）數(shù)據(jù)的存取操作：訪問鏈表中的結(jié)點必需從表頭開始，是順序的存取方式，而數(shù)組元素的訪問是通過數(shù)組下標來實現(xiàn)的，是隨機存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。4）數(shù)據(jù)的合并與分開：鏈表優(yōu)于數(shù)組，由于只需要改變指針的指向13.將表達式((a+b)-c*(d+e)-f)*(g+h)改寫成后綴表達式。

答：后綴表達式為：ab+cde+*-f-gh+*

14．將算術(shù)表達式a*(b+c)-d轉(zhuǎn)為后綴表達式。答：abc+*d-

15.求出下圖所示有向圖的鄰接表。

2VV

73

1

VV

54

V

答：有向圖的鄰接表為：

122741∧V0V1∧∧35

V2V3∧34∧03VHead

16．試找出中序序列和后序序列一致的所有二叉樹。答：空樹或缺右子樹的單支樹。

17.用鄰接矩陣存儲一個包含1000個頂點和1000條邊的圖，則該圖的鄰接矩陣中有多少元素？有多少非零元素？答：該圖的鄰接矩陣中有1000*1000個元素。該圖的鄰接矩陣中有2000個非零元素。18.畫出下圖中二叉樹的順序存儲結(jié)構(gòu)示意圖。

1

3715

答：二叉樹的順序存儲結(jié)構(gòu)示意圖為：13715A[0]A[2]A[6]A[14]19.寫出中綴表達式A-(B+C/D)*E的后綴形式。

答：中綴表達式A-(B+C/D)*E的后綴形式是：ABCD/+E*-。20．為什么用二叉樹表示一般樹？

答：樹的最直觀表示是為樹中結(jié)點設(shè)置指向子結(jié)點的指針域，對k叉樹而言，每個結(jié)點除data域外，還有k個鏈接域。這樣，對一個有n個結(jié)點的k叉樹來說，共有n*k個指針域，其中n-1個