數(shù)據(jù)結(jié)構(gòu)原理
102
數(shù)據(jù)結(jié)構(gòu)原理
1. 具有n個(gè)結(jié)點(diǎn)的二叉樹采用鏈接結(jié)構(gòu)存儲(chǔ)，鏈表中存放NULL指針域的個(gè)數(shù)為（n+1）。
2．串是（任意有限個(gè)字符構(gòu)成的序列）。
3．在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2 ）。
4．某二叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹(高度等于其結(jié)點(diǎn)數(shù))。
5. 對(duì)于棧操作數(shù)據(jù)的原則是（后進(jìn)先出 ）。
6．若長度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，首先需要移動(dòng)表中數(shù)據(jù)元素的個(gè)數(shù)是（n-i）。
7. 在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該(只有左子樹上的所有結(jié)點(diǎn) )。
8. 排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為( 插入排序 )。
9. 若一棵二叉樹具有45個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（46 ）。
10.某二叉樹的前序和后序序列正好相同，則該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。
11. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有邊數(shù)（ 4 ）倍。
12．串是（任意有限個(gè)字符構(gòu)成的序列 ）。
13．對(duì)于棧操作數(shù)據(jù)的原則是（后進(jìn)先出 ）
14. 設(shè)輸入序列為A,B,C,D,借助一個(gè)棧不可以得到的輸出序列是(D,A,B,C )。
15. 結(jié)點(diǎn)前序?yàn)閤yz的不同二叉樹，所具有的不同形態(tài)為(5 )。
16. 一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的起始地址為100，則該數(shù)組的首地址是（70）。
17．在一棵高度為h(假定樹根結(jié)點(diǎn)的層號(hào)為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h )。
18. 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ 2 ）倍。
19.因此在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是 (d ).
20. 一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（堆棧）。
21. 對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,則(n=2h＋1-1 )。
22. 線性表的長度是指（表中的元素個(gè)數(shù)）。
23. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常用來實(shí)現(xiàn)算法的輔助結(jié)構(gòu)是(棧 )。
24. 堆的形狀是一棵(完全二叉樹 )。
25. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（ cabdef）。
26. 若長度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該
是（ C. 1≤i≤n）。
27．在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2 ）。
28. 若某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，則采用什么存儲(chǔ)方
式最節(jié)省時(shí)間（順序表）。
29．一組記錄的關(guān)鍵字為{45, 80, 55, 40, 42, 85}，則利用堆排序的方法建立的初始堆為（85, 80, 55, 40, 42, 45 ）。
30. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的先根序列就是T2中結(jié)點(diǎn)的（先根序列）。
31. 對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,則(n=2h＋1-1 )。
32.具有n個(gè)頂點(diǎn)的有向圖最多可包含的有向邊的條數(shù)是(n(n-1) )。
33．設(shè)有6000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元
素,最好選用(堆排序)法。
34.任何一個(gè)無向連通圖的最小生成樹(有一棵或多棵 )。
35. 排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(選擇排序)。
36. 對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為（R6，R2，R4，R3 ）。
37. 因此在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是 (d )。
38.深度為h且有多少個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹(2h+1-1 )。
39．某二叉樹的前序和后序序列正好相反，則該二叉樹一定是的二叉樹為(高度等于其結(jié)點(diǎn)數(shù))。
40. 帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是(head->next==NULL)。
41．棧和隊(duì)列的主要區(qū)別在于（插入刪除運(yùn)算的限定不一樣）
42. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為(2h-1 )。
43．在一個(gè)單鏈表中，若刪除(*p)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行(p->next=p->next->next)。
44.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（n+1 ）
45.若一棵二叉樹有11個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是（12 ）。
46. 對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉查找樹，在這種情況下，其平均查找長度的量級(jí)為（O(n) ）。
47. 有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱為頂點(diǎn)v的（入度）。
48. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(通常不會(huì)出現(xiàn)棧滿的情況)。
49. 若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用的存儲(chǔ)結(jié)構(gòu)是（鏈?zhǔn)剑?/p>
50. 設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（3 2 1 5 4）。
51.設(shè)森林F中有三棵樹，第一、第二和第三棵的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和m3,則森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)上的右子樹上結(jié)點(diǎn)個(gè)數(shù)是 ( m2+m3 )。
52. 有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉查找樹，若希望高度最小，則應(yīng)選擇下面輸入序列是（ 37,24,12,30,53,45,96）。
53．若要在O（1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向(各自的尾結(jié)點(diǎn) )。
54. 二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（2I ）。
55.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ 2h-1 ）。
56.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的先根序列就是T2中結(jié)點(diǎn)的（先根序列 ）。
57. 用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)
行的時(shí)間雜度為(O(n2))。
58. 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（2n-1 ）。
59. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法為(三元組表)。
60. 若二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1 的結(jié)點(diǎn)有10個(gè)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為（16 ）。
61. 若某完全二叉樹的深度為h，則該完全二叉樹中具有的結(jié)點(diǎn)數(shù)至少是(2h－1 )。
62. 任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后根遍歷序列中的相對(duì)位置(肯定不發(fā)生變化)。
63.初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為( n-1)。
64. 對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長度的量級(jí)為(O(log2n))。
65用冒泡排序法對(duì)序列{18,16,14,12,10,8}從小到大進(jìn)行排序，需要進(jìn)行的比較次數(shù)是(15 )。
66在一個(gè)有向圖中，所有頂點(diǎn)的出度之和等于所有邊數(shù)的倍數(shù)是（ 1 ）。
67.有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n ）。
68.6個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（5 ）。
69. 對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為（R6，R4，R2，R3）。
70. 串是（任意有限個(gè)字符構(gòu)成的序列）。
71.個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（1 ）倍。
72.單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的什么位置（鏈頭 ）。
73. 一組記錄的關(guān)鍵字為{45, 80, 55, 40, 42, 85}，則利用堆排序的方法建立的初始堆為（85, 80, 55, 40, 42, 45 ）。
74. 對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,則(n=2h＋1-1)
75.某二叉樹的前序和后序序列正好相同，則該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。
76.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（n+1 ）。
77. 若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，需要移動(dòng)表中元素的個(gè)數(shù)是（n-i+1）。
78. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（-1 ）。
79.設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵高度為h 的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是(2h+1-1 )。
80. 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(有左孩子，無右孩子)。
81. 設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5，8的存儲(chǔ)首地址為( BA+180 )。
82.在一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為 (n(n-1)/2 )。
83．設(shè)森林F中有三棵樹，第一、第二和第三棵的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和m3,則森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)上的右子樹上結(jié)點(diǎn)個(gè)數(shù)是 (m2+m3 )。
84.對(duì)于鍵值序列{72,73,71,23,94,16,5,68,76,103}用篩選法建堆，開始結(jié)點(diǎn)的鍵值必須為(94 )。
85. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有(任意多個(gè) )。
86.對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長度的量級(jí)為(O(log2n) )。
87. 用孩子兄弟鏈表表示一棵樹，若要找到結(jié)點(diǎn)x的第5個(gè)孩子，只要先找到x的第一個(gè)孩子，然后(從兄弟域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可)。
88．有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功的比較次數(shù)是（4 ）。.
89. 當(dāng)初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為(n-1 )。
90.深度為h的滿二叉樹具有的結(jié)點(diǎn)個(gè)數(shù)為（2h+1-1 ）。
91. 二維數(shù)組A56的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址為3000的連續(xù)的內(nèi)存單元中，則元素A45的存儲(chǔ)地址為（3145）。
92.一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖中，采用鄰接表表示，則所有頂點(diǎn)的鄰接表的結(jié)點(diǎn)總數(shù)為（2e ）。
93. 一個(gè)具有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n）。
94. 一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖中，采用鄰接表表示，則所有頂點(diǎn)的鄰接表的結(jié)點(diǎn)總數(shù)為（ 2e ）。
95. 若要在O（1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向( 各自的尾結(jié)點(diǎn))。
96．在一棵高度為h(假定樹根結(jié)點(diǎn)的層號(hào)為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h )。
97. 若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用比較次數(shù)最少的方法是（直接插入排序）。
98. 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（2n-1 ）。
99.二分查找法要求查找表中各元素的鍵值必須是(遞增或遞減 )。
100. 在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，最好情況下的時(shí)間復(fù)雜性為（
）。
101.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(通常不會(huì)出現(xiàn)棧滿的情況 )。
102. 將長度為m的單鏈表連接在長度為n的單鏈表之后的算法的時(shí)間復(fù)雜度為(O(n) )。
103.若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用（直接插入排序）方法比較次數(shù)最少。
104. 若字符串“1234567”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)，則該字符串的存儲(chǔ)密度為（33.3﹪）。
105.用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)
行的時(shí)間雜度為(O(n2) )。
106. 若在一棵非空樹中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)（包括A自身），B是A的雙親結(jié)點(diǎn)，則B的度為（3）。
107. 單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（方便運(yùn)算的實(shí)現(xiàn)）。
108. 深度為h的滿二叉樹所具有的結(jié)點(diǎn)個(gè)數(shù)是（2h+1-1 ）。
109．按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有多少種(5 )。
110. 設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為(O(n) )。
111．樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（-1 ）。
112. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ -1 ）
113. 設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是(ZXY )。
114. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用的輔助存儲(chǔ)結(jié)構(gòu)是(棧)。
115. 對(duì)有18個(gè)元素的有序表作二分（折半）查找，則查找A 3的比較序列的下標(biāo)為（9、4、2、3）。
116. 在含n個(gè)頂點(diǎn)e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ n2-2e）。
117. 樹形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有 ( 多個(gè)直接后繼)。
118. 使具有30個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（29）。
119. 按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹具有的種類為(5 )。
120. 使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（8 ）。
121. 在順序表（n足夠大）中進(jìn)行順序查找，其查找不成功的平均長度是（n+1 ）。
122. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ 8 ）。
123. 棧的插入和刪除操作進(jìn)行的位置在（棧頂）。
124. 某二叉樹的前序和后序序列正好相同，則該二叉樹一定是的二叉樹為(空或只有一個(gè)結(jié)點(diǎn))。
125. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(通常不會(huì)出現(xiàn)棧滿的情況)。
126. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（節(jié)省存儲(chǔ)空間）。
127. 結(jié)點(diǎn)前序?yàn)閤yz的不同二叉樹，所具有的不同形態(tài)為(5 )。
128. 若一棵二叉樹具有20個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（21 ）。
129. 一棵線索二叉樹的線索個(gè)數(shù)比鏈接個(gè)數(shù)多（ 2 ）個(gè)。
1. 若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為9。
2．在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為2。
3.對(duì)于一棵二叉樹，設(shè)葉子結(jié)點(diǎn)數(shù)為n0,次數(shù)為2的結(jié)點(diǎn)數(shù)為n2,則n0和n2的關(guān)系是n0= n2＋1。
4. 在循環(huán) 鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。
5. 普里姆(Prim)算法適用于邊稠密圖。
6.深度為h且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點(diǎn)處在第1層)。
7.圖的深度優(yōu)先搜索方法類似于二叉樹的先序遍歷 。
8.哈夫曼樹是帶權(quán)路徑長度最小的二叉樹。
9. 二叉樹的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
10. 哈夫曼樹是帶權(quán)路徑長度最小 的二叉樹。
11.一般樹的存儲(chǔ)結(jié)構(gòu)有雙親表示法、孩子兄弟表示法和孩子鏈表表示法。
12. 將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存于一個(gè)一維數(shù)組中，然后采用折半查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為5，7，6 。。
13. 圖的深度優(yōu)先遍歷序列不是唯一的。
14. 下面程序段的時(shí)間復(fù)雜度是 O（mn） 。
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
aij=0;
16. 圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪問圖中全部頂點(diǎn)且使每一頂點(diǎn)僅被 訪問一次。
17. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的2倍 。
18. 由一棵二叉樹的后序序列和中序序列可唯一確定這棵二叉樹 。
19. 在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為2。
20. 若二叉樹的一個(gè)葉子結(jié)點(diǎn)是某子樹的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹的后跟遍歷中的第一 個(gè)結(jié)點(diǎn)。
21.在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩(wěn)定的排序方法有直接插入排序。
22.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為50。
23.普里姆(Prim)算法適用于邊稠密圖。
24. 在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng) n/2 個(gè)結(jié)點(diǎn)。
25.將一棵樹轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點(diǎn)沒有右子樹。
26循環(huán)隊(duì)列的引入，目的是為了克服 假溢出 。
27.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1棵 。
28．在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為2 。
29.棧和隊(duì)列的共同特點(diǎn)是插入和刪除均在端點(diǎn)處進(jìn)行。
30. 二叉樹的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。
31. 若連通圖的頂點(diǎn)個(gè)數(shù)為n，則該圖的生成樹的邊數(shù)為n-1。
32.圖的存儲(chǔ)結(jié)構(gòu)最常用的有鄰接矩陣和鄰接表。
33. 若一棵二叉樹有15個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為14。
34．隊(duì)列中允許進(jìn)行插入的一端稱為隊(duì)尾。
35.拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在環(huán)。
36.在有序表(15,23,24,45,48,62,85)中二分查找關(guān)鍵詞23時(shí)所需進(jìn)行的關(guān)鍵詞比較次數(shù)為2。
37. 則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為k，最多為2k-1。
38. 若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1棵 。
39. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是3 1 2。
40. 設(shè)有一個(gè)順序棧S，元素S1，S2，S3，S4，S5，S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2，S3，S4，S6，S5，S1，則順序棧的容量至少應(yīng)為 3 。
41. 對(duì)于一棵二叉樹，設(shè)葉子結(jié)點(diǎn)數(shù)為n0,次數(shù)為2的結(jié)點(diǎn)數(shù)為n2,則n0和n2的關(guān)系是 n0= n2＋1 。
42. 設(shè)某二叉樹的后序遍歷序列為ABKCBPM，則可知該二叉樹的根為 M 。
43. 數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)的 邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、 運(yùn)算。
44. 每個(gè)結(jié)點(diǎn)只有 一個(gè) 鏈接域的鏈表叫做單鏈表。
45. 設(shè)無向圖G的頂點(diǎn)數(shù)為n，則要使G連通最少有 n-1條邊。
46. 組成串的數(shù)據(jù)元素只能是字符。
47．圖的存儲(chǔ)結(jié)構(gòu)最常用的有鄰接表 和鄰接矩陣。
48. 由一棵二叉樹的后序序列和中序序列 可唯一確定這棵二叉樹。
49. 隊(duì)列中允許進(jìn)行插入的一端稱為隊(duì)尾。
1.對(duì)于一個(gè)隊(duì)列，如果輸入項(xiàng)序列由1,2,3,4所組成，試給出全部可能的輸出序列。
答：1,2,3,4。
2. 已知一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。
中序序列：c，b，d，e，a，g，i，h，j，f
前序序列：a，b，c，d，e，f，g，h，i，j
答：該二叉樹的后序序列為：c,e,d,b,i,j,h,g,f,a
3. 為什么說樹是一種非線性結(jié)構(gòu)？
答：樹中的每個(gè)結(jié)點(diǎn)除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)，但有多個(gè)直接后繼，所以說樹是一種非線性結(jié)構(gòu)。
4．將算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式。
答： B．a(chǎn)bcde/+*+
5. 找出所有這樣的二叉樹形，其結(jié)點(diǎn)在先根次序遍歷和中根次序遍歷下的排列是一樣的。
答： 為空樹，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。
8.有個(gè)頂點(diǎn)的無向連通圖至少有多少條邊？有個(gè)頂點(diǎn)的有向連通圖至少有多少條邊？
答：有個(gè)頂點(diǎn)的無向連通圖至少有n-1條邊，有個(gè)頂點(diǎn)的有向連通圖至少有n條邊。
9．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？
答：起泡排序, 直接插入排序，歸并排序是穩(wěn)定的。
10. 完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最合適，為什么？
答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最合適。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒有空洞，不存在空間浪費(fèi)問題；另外，順序存儲(chǔ)方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即已知父（或子）結(jié)點(diǎn)尋找子（或父）結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問結(jié)點(diǎn)方便。但采用鏈表存儲(chǔ)時(shí)就存在空間浪費(fèi)問題，因?yàn)槊總€(gè)結(jié)點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。
11．線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：如果有 n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？
答：選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O（1）。
12．試述順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別及各自的優(yōu)缺點(diǎn)。
答：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點(diǎn)的空間連續(xù)。
1）插入與刪除操作：由于數(shù)組在插入與刪除數(shù)據(jù)時(shí)需移動(dòng)大量的數(shù)據(jù)元素，而鏈表只需要改變一些指針的鏈接，因此，鏈表比數(shù)組易于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作。
2）內(nèi)存空間的占用情況：因鏈表多了一個(gè)指針域，故較浪費(fèi)空間，因此，在空間占用方面，數(shù)組優(yōu)于鏈表。
3）數(shù)據(jù)的存取操作：訪問鏈表中的結(jié)點(diǎn)必須從表頭開始，是順序的存取方式，而數(shù)組元素的訪問是通過數(shù)組下標(biāo)來實(shí)現(xiàn)的，是隨機(jī)存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。
數(shù)據(jù)的合并與分離：鏈表優(yōu)于數(shù)組，因?yàn)橹恍枰淖冎羔樀闹赶?/p>
13. 將表達(dá)式((a+b)-c*(d+e)-f)*(g+h)改寫成后綴表達(dá)式。
答：后綴表達(dá)式為：ab+cde+*-f-gh+*
19.寫出中綴表達(dá)式A-(B+C/D)*E的后綴形式。
答：中綴表達(dá)式A-(B+C/D)*E的后綴形式是：ABCD/+E*-。
20． 為什么用二叉樹表示一般樹？
答：樹的最直觀表示是為樹中結(jié)點(diǎn)設(shè)置指向子結(jié)點(diǎn)的指針域，對(duì)k叉樹而言，每個(gè)結(jié)點(diǎn)除data域外，還有k個(gè)鏈接域。這樣，對(duì)一個(gè)有n個(gè)結(jié)點(diǎn)的k叉樹來說，共有n*k個(gè)指針域，其中n-1個(gè)不空，另外n(k-1)+1個(gè)指針域?yàn)榭?，因此，空鏈接域的比例約為（k-1）/k ，于是導(dǎo)致大量的空間浪費(fèi)。然而，如果采用二叉樹表示一棵n個(gè)結(jié)點(diǎn)的樹，則樹中共有2n個(gè)鏈接域，其中未用到的有n+1個(gè)，占所有指針域的比例約為1/2，空間浪費(fèi)少很多。
另外，因?yàn)槿魏螛湫徒Y(jié)構(gòu)都可以轉(zhuǎn)換成二叉樹，因此，通常用二叉樹表示樹型結(jié)構(gòu)。
21．已知數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出冒泡排序每趟的結(jié)果。
答： 初始鍵值序列12 5 9 20 6 31 24
第一趟排序 5 9 12 6 20 24 31
第二趟排序 5 9 6 12 20 24 31
第三趟排序 5 9 6 12 20 24 31
第四趟排序 5 6 9 12 20 24 31
22．試找出前序序列和中序序列相同的所有二叉樹。
解答：空樹或缺左子樹的單支樹。
23．完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最合適，為什么？
答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最合適。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒有空洞，不存在空間浪費(fèi)問題；另外，順序存儲(chǔ)方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即已知父（或子）結(jié)點(diǎn)尋找子（或父）結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問結(jié)點(diǎn)方便。但采用鏈表存儲(chǔ)時(shí)就存在空間浪費(fèi)問題，因?yàn)槊總€(gè)結(jié)點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。
26．我們已經(jīng)知道，樹的先根序列與其對(duì)應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對(duì)應(yīng)的二叉樹的中根序列相同。那么利用樹的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹？請(qǐng)說明理由。
答：能。因?yàn)闃涞南雀蛄信c其對(duì)應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對(duì)應(yīng)的二叉樹的中根序列相同，而二叉樹的先根序列與二叉樹的中根序列能唯一確定一棵二叉樹，所以利用樹的先根遍歷次序與后根遍歷次序，能唯一確定一棵樹。
28．已知一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。
中序序列：c，b，d，e，a，g，i，h，j，f
前序序列：a，b，c，d，e，f，g，h，i，j
答：該二叉樹的后序序列為：c,e,d,b,i,j,h,g,f,a
29． 對(duì)半查找是否適合于以鏈接結(jié)構(gòu)組織的表？
答：對(duì)半查找不適合于以鏈接結(jié)構(gòu)組織的表。。
30. 請(qǐng)指出中序遍歷二叉查找樹的結(jié)點(diǎn)可以得到什么樣的結(jié)點(diǎn)序列。
答：中序遍歷二叉查找樹的結(jié)點(diǎn)就可以得到從小到大排序的結(jié)點(diǎn)序列。
31．已知數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出歸并排序每趟的結(jié)果。
解答：
初始鍵值序列12 5 9 20 6 31 24
第一趟排序 5 12 9 20 6 31 24
第二趟排序 5 9 12 20 6 24 31
第三趟排序 5 6 9 12 20 24 31（）
37.一組記錄的關(guān)鍵字為(52, 56, 26, 12, 69, 85, 33, 48, 70)，給出快速排序的過程。
解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70
第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70
第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85
第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
38．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？
起泡排序, 直接插入排序，歸并排序是穩(wěn)定的。
39．已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。
前序序列：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
48. 設(shè)記錄的關(guān)鍵字集合key={51,28,38,86,70,90,7,30,40,25}，試寫出對(duì)key進(jìn)行漸減增量排序（增量d = 5，3，1）時(shí)，各趟排序結(jié)束后的結(jié)果。
解答：各趟排序結(jié)束后的結(jié)果。
初始狀態(tài)：51 28 38 86 70 90 7 30 40 25
第一趟排序(d=5): 51 7 30 40 25 90 28 38 86 70
第二趟排序(d=3): 28 7 30 40 25 86 51 38 90 70
第三趟排序(d=1): 7 25 28 30 38 40 51 70 86 90）
1.寫出計(jì)算單鏈表head（head為單鏈表的表頭）中數(shù)據(jù)域data值為m的結(jié)點(diǎn)個(gè)數(shù)的算法。
int count (Node *head)
//計(jì)算單鏈表head中數(shù)據(jù)域data值為m的結(jié)點(diǎn)個(gè)數(shù)
{ Node *p=head->next;
int n=0;
while (p!=NULL)
{if (p->data==m)
n++；
p=p->next;
}
return n;
}// count
2.已知非空單鏈表head，試設(shè)計(jì)一個(gè)算法，交換p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置。
解答：
int revers(listnode *head, listnode *p)
/*交換p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置*/
{ if (p->next==NULL) return 0 ;
listnode *q=head;
while (q->next!=p) q=q->next;
{r=p->next；q->next=r;
p->next =r ->next ; r->next=p;
return 1;
}// revers
3.線性表用帶頭結(jié)點(diǎn)的單向鏈表示，試寫出刪除表中所有data域?yàn)榱愕脑氐乃惴ā?/p>
解答：
解： int DeleteItem(Node * head)
{ Node *p=head;
//聲明指針p，并令其指向鏈表頭結(jié)點(diǎn)
while (p->nextNode()!=NULL)
{
if (p->nextNode()->data==0)
p->next=p->nextNode()->next.
else p=p->nextNode(); //指針下移
}
}
4．試設(shè)計(jì)一算法，計(jì)算帶頭結(jié)點(diǎn)的單鏈表head(head指向表頭)的結(jié)點(diǎn)個(gè)數(shù)。
解答：
int Length( )
//計(jì)算帶表頭結(jié)點(diǎn)的單鏈表head的長度
{
Node *p=head->next;
int count=1;
while (p->next!=NULL)
{p=p->next; count ++;}
return count;
}
5．判斷單鏈表head(head指向表頭)是否是遞增的。
解答：
int order(Node *head)
{
Node *p=head;
while(p->next!=NULL)
if(p->data<p->next->data)
p=p->next;
else
break;
if(p->next==NULL)
return 1;
else
return 0;
}
6. 設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表head中找出值最小的元素。
解答：int Min(Node * head )
//在單鏈表head中找出值最小的元素
{
Node *p=head;
int min=p->data;
while (p->next!=NULL)
阿 { if(p->next->data<min) min=p->next->data;
p=p->next;
}
return min; }
7設(shè)有兩個(gè)單鏈表L和L1,其結(jié)點(diǎn)結(jié)構(gòu)為 ,試 編寫算法判斷鏈表L1中的各元素是否都是單鏈表L中的元素。
解答：
int SubLnk(Node *L, Node *L1){
Node *p1=L1;
while(p1!=NULL)
{
Node *p=L;
while((p!=NULL)&&(p1->data!=p->data))
{
p=p->next;
if (p==NULL) return 0;
else p1=p1->next;
}
return 1;
}
}
8.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法交換二叉樹中每個(gè)結(jié)點(diǎn)的左子女和右子女。（12分）
解答：
void exchange(BinTreeNode * t)
{
if (t!=NULL)
BinTreeNode * temp;
if((t->lchild!=NULL)||(t->rchild!=NULL))
{temp= t->lchild;
t->lchild= t->rchild;
t->rchild= temp;
exchange(t->lchild);
exchange(t->rchild);
}
}
9.設(shè)有一個(gè)正整數(shù)序列組成帶頭結(jié)點(diǎn)的單鏈表head，試編寫算法確定在序列中比正整數(shù)x 大的數(shù)有幾個(gè)。（8分）
解答：
int count（Node * head，int x）
∥在帶頭結(jié)點(diǎn)的單鏈表head中，確定序列中比正整數(shù)x大的數(shù)有幾個(gè)
{
Node *p=head->next;
int count=0;
while (p!=NULL)
{ if (p->data>x) count ++;
p=p->next;
}
return count;
}∥算法count結(jié)束
10.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法計(jì)算二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。
（12分）
解答：void countleaf(BinTreeNode * t,int &count)
{
if(t!=NULL)
{if((t->lchild= =NULL)&&(t->rchild= =NULL))
count++;（2分）
countleaf(t->lchild,count);
countleaf(t->rchild ,count);
}
}
11. 設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試寫一算法求該二叉樹上度為2的結(jié)點(diǎn)個(gè)數(shù)。
（12分）
解答：
void count2(bitreptr t，int count)
{if (t!=NULL)
{if ((t-> lchild != NULL) && (t-> rchild != NULL))
count++;
count2 (t->lchild,count)；
count2 (t->rchild,count)；
}
}// count2
12.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試寫一算法求該二叉樹中最大值（元）。（12分）
解答：
void maxnode(bitreptr t，int max)
{if (t!=NULL) （2分）
{if (t-> data>max) max=t->data; （4分）
max= maxnode (t->lchild,max)；（2分）
max= maxnode (t->rchild,max)；（2分）
}
return max; （2分）
}// maxnode
......詳細(xì)資料請(qǐng)下載
上一篇： 多媒體