福建師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》期末練習(xí)題(有答案)

1、福建師范大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院計算機(jī)科學(xué)與技術(shù) 數(shù)據(jù)結(jié)構(gòu)與算法期末練習(xí) 一 選擇題1以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ D ）。A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧2. 算法的時間復(fù)雜度取決于（ A ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 計算機(jī)cpu3. 一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 24. 有關(guān)靜態(tài)鏈表的敘述：(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。

2、(2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ B ） A（1），（2） B（1） C（1），（2）,(3) D.（2）5對于有n 個結(jié)點的二叉樹, 其高度為（ D ）Anlog2n Blog2n Cëlog2nû|+1 D不確定6從下列有關(guān)樹的敘述中,選出正確的敘述（ C ）A二叉樹中每個結(jié)點有兩個子結(jié)點,而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1時高度為K的二叉樹至多有2k-1個結(jié)點。C哈夫曼樹是帶權(quán)路徑最短的樹,路徑上權(quán)值較大的結(jié)點離根較近。D在二叉

3、樹中插入結(jié)點,該二叉樹便不再是二叉樹。7設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（ B ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En28已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>,G的拓?fù)湫蛄惺牵?A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6

4、,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V79下列排序算法中，其中（ D ）是穩(wěn)定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 希爾排序，歸并排序 D. 歸并排序，冒泡排序10對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 11. 則采用的排序是 ( A )。 A. 選擇 B. 冒泡 C. 快速 D. 插入12以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線

5、性結(jié)構(gòu)（ D ）？ A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串13下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。14. 設(shè)一個棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ D ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 415. 設(shè)n為正整數(shù).下列程序段中前置以的語句的頻度為（ ）。i = 1; k = 0;

6、do k+= 10*i; i+;While(i <= n-1); A. n 1 B. n C. n + 1 D. n - 216. 一棵具有 n個結(jié)點的完全二叉樹的樹高度（深度）是（ A ）Aëlognû+1 Blogn+1 Cëlognû Dlogn-117一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（ B ）。A. 不確定 B. n-i+1 C. i D. n-i18n個結(jié)點的完全有向圖含有邊的數(shù)目（D）。An*n n（n） Cn2 Dn*（nl）19穩(wěn)定的排序方法是（ B ） A直接插

7、入排序和快速排序 B折半插入排序和起泡排序C希爾排序和四路歸并排序 D樹形選擇排序和shell排序20有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4） 用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序為 ( A )（按遞增序）。 A下面的B，C，D都不對。 B9，7，8，4，-1，7，15，20C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，2021以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ A ）A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表22下面關(guān)于串的的敘述中，哪一個是不正確的？（ B ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算

8、 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?3. 某堆棧的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b24. 關(guān)于二叉樹的敘述：只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。正確的是（ D ）A B C D25高度為 K的二叉樹最大的結(jié)點數(shù)為（ C ）。A2k B2k-1 C2k -1 D2k-1-126從下列有關(guān)樹的敘述中,選出正確的敘述（ C ）A二叉樹中每個結(jié)點

9、有兩個子結(jié)點,而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1時高度為K的二叉樹至多有2k-1個結(jié)點。C用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。D哈夫曼樹是帶權(quán)路徑最長的樹,路徑上權(quán)值較大的結(jié)點離根較近。27. 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。A從源點到匯點的最長路徑 B從源點到匯點的最短路徑C最長回路 D最短回路28用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點序列是( A )。A逆拓?fù)溆行?B拓?fù)溆行?C無序的29一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ C ）。A(

10、38,40,46,56,79,84) B. (40,38,46,79,56,84)C(40,38,46,56,79,84) D. (40,38,46,84,56,79)30. 一個向量的第一個元素的地址是begin，每個元素的長度是k ，則第i個元素的地址是( D )A. begin+(k-1)i B. begin+(k-2)i C. begin+ki D. begin+(i-1)k31. 有一個有序表為 1，3，9，12，32，41，45，62，77，88，92，100，用折半查找法，若要找63，要經(jīng)過( C )次與63比較。A. 12 B. 6 C. 4 D. 5 32. 一個序列的初始狀

11、態(tài)為（46，77，82，53，31，70），今對其進(jìn)行冒泡排序，當(dāng)進(jìn)行兩趟冒泡后，序列中的元素排列為( D )。A.（31，46，70，53，77，82）B.（46，77，53，31，70，82）C.（46，31, 82，53，77，70）D. (46 ，53，31，70，77，82) 33. 將一個長度為n的向量的第i 個元素刪除時，需要前移( B )個元素。A. i B. n-i C. n+1 D. n-i+1 34. 不帶表頭的單鏈表，頭指針為head ，判斷其是否為空的條件是( A ) A. head=0 B. head->next=null C. head=head D. he

12、ad->next=head35. 在一個單鏈表中，已知*q是（*q表示指針q所指的結(jié)點，以下同）*p的前驅(qū)結(jié)點，在*q之后插入結(jié)點*s，正確的操作步驟序列是( A )。 A) q->next=s; s->next =p B) s->next=p->next; q->next=s;C) p->nexr=s; s->next=p ; D) p->next=s; s->next=q;36. 非空循環(huán)鏈表head 的尾結(jié)點 *p 滿足下列( C )條件A) head->next=p; B) head=p; C) p->next=h

13、ead; D) p->next=037. 一個棧的輸入序列是a,b,c,d,e ，則可能的出棧序列是( D )。A. ecdab B) cebda C) daecb D) abcde38. 設(shè)棧s的類型為sqstack ，判定?？盏臈l件是( C )。A. s=NULL B) s->top=0 C) s.top=0 D) s.top=NULL 39. 深度為5 的二叉樹至多有個( B )結(jié)點。A. 12 B. 31 C. 14 D. 1540. 已知二叉樹的后、中根序列分別是bedfca 和 badecf，則該二叉樹的前根遍歷序列是( C )。 A) defbca B) fedbca

14、 C) abcdef D) fedcba 41. 一個有n個頂點的有向圖最多有( B )弧 。 A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/242. 具有n個頂點的無向圖至少要有( B )條邊才有可能是一個連通圖。A) n(n+1) B) n-1 C) n+1 D) n(n-1)43. 已知有向圖的正鄰接鏈表的存儲結(jié)構(gòu)如下，從頂點1出發(fā)的按深度優(yōu)先遍歷序列是( B )。 A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 24 2 3 3 4 2 4 123444. 一個向量的第一個元素的地址是100，每個元素的長度是2

15、，則第五個元素的地址是( C )A) 102 B) 110 C) 108 D) 12045. 一個循環(huán)順序隊列 ,隊頭、尾指針的值分別為front,rear ，則隊列中元素個數(shù)為( A )。（maxlen為循環(huán)順序表的長度）A. (rear-front+maxlen) % maxlen B. (rear-front) % maxlenC. rear-front+1 D. front-rear+146. 一個有n個頂點的圖最少有( D )條邊。A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 047. 具有5個頂點的無向圖至少要有( A )條邊才能確保是一個連通圖。A) 4

16、B) 5 C) 6 D) 748. 設(shè)棧s的類型為sqstack ，最多可容納maxlen個元素，則判定棧滿的條件是( B )。A. s=maxlen-1 B) s.top=maxlen-1 C) s->top=maxlen-1 D) s.top=049. 一個順序隊列q的類型為sqqueue,隊頭、尾指針分別為front,rear，最多可容納maxlen個元素，則隊空的條件是( C )。A) front=rear B) rear=0 C) q.front=q.rear D) rear=maxlen-150. 在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復(fù)雜度是( B

17、 )A.O(1) B.O(n)C.O(nlogn) D.O(n*n)51. 鏈棧與順序棧相比，比較明顯的優(yōu)點是( D )A.插入操作更加方便 B.刪除操作更加方便C.不會出現(xiàn)下溢的情況 D.不會出現(xiàn)上溢的情況52. 二叉樹中第5層上的結(jié)點個數(shù)最多為( C )A.8 B.15C.16 D.3253. 下列編碼中屬前綴碼的是( A )A.1,01,000,001 B.1,01,011,010C.0,10,110,11 D.0,1,00,1154. 如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應(yīng)采用（B）A深度優(yōu)先搜索算法B廣度優(yōu)先搜索算法C求最小生成樹的prim算法D拓?fù)渑判蛩惴?5. 對

18、n個關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為( B )A.O(1) B.O(logn)C.O(n) D.O(n logn)56. 對表長為n的順序表進(jìn)行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為( C )A. (n-1)/2 B. n/2C. (n+1)/2 D. n57. 對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是( D )A.35和41 B.23和39C.15和44 D.25和5158. 關(guān)于線性表的說法,下面選項正確的是（ B ） A 線性表的特點是每個元素都有一個前驅(qū)和一個后繼 B 線性表是具有n(n>=0)個元素的一個有限序列 C

19、線性表就是順序存儲的表 D 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)59. 表長為n的順序存儲的線性表，當(dāng)在任何一個位置上插入或者刪除一個元素的概率相等時，刪除一個元素需要移動元素的平均個數(shù)為（ A ） A (n-1)/2 B n/2 C n D n-160. 設(shè)雙向循環(huán)鏈表中節(jié)點的結(jié)構(gòu)為(data,LLink,RLink)，且不帶頭節(jié)點。若想在指針p所指節(jié)點之后插入指針s所指節(jié)點，則應(yīng)執(zhí)行下列哪一個操作？（ D ） A p->RLink=s; s->LLink=p; p->RLink->LLink=s; s->RLink=p->RLink; B p->RLink

20、=s; p->RLink->LLink=s;s->LLink=p; s->RLink=p->RLink; C s->LLink=p; s->RLink=p->RLink; p->RLink=s; p->RLink->LLink=s; D s->LLink=p; s->RLink=p->RLink; p->RLink->LLink=s; p->RLink=s;61. 棧和隊列都是（ A ） A 限制存取位置的線性結(jié)構(gòu) B 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu) C 順序存儲的線性結(jié)構(gòu) D 限制存取位置的非線性結(jié)構(gòu)

21、62. 單循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則入隊的時間復(fù)雜度為（ A ） A O(n) B O(1) C O(n*n) D O(n*logn)63. 一棵含有n個節(jié)點的k叉樹，可能達(dá)到的最小深度為多少？（ C ） A n-k B n-k+1 C |logkn|+1 D |logkn| 其中|k|表示下取整 64. 下列序列中( B )不是堆。A. 12 36 53 68 48 60 75 B. 12 48 53 68 36 60 75C. 12 48 36 60 75 68 53 D. 12 36 60 53 48 68 7565. 在下列內(nèi)排序方法中，( C )的平均時間復(fù)雜性是O

22、(nlogn)。A. 直接插入排序 B. 簡單選擇排序C. 快速排序 D. 希爾排序66. 設(shè)順序棧s非空，則語句段( C )可實現(xiàn)棧s的出棧操作，其中s.top為棧頂指針，s.elem為?？臻g，出棧的元素存放在x中。 A. s.top:=s.top+1; B. x:=s.elems.top; x:=s.elems.top; s.top:=s.top+1; C. s.top:=s.top-1; D. x:=s.elems.top; x:=s.elems.top; s.top:=s.top-1;67. 已知L是帶頭結(jié)點的單鏈表，p指向表中某結(jié)點，則要刪除p結(jié)點的后繼結(jié)點應(yīng)執(zhí)行操作( A )；要在

23、p結(jié)點后插入s結(jié)點應(yīng)執(zhí)行操作( D )。 A. pànext:=pànextànext; B. pànextànext:= à.next; C. pànext:=s; sànext:=pànext; D. sànext:=pànext; pànext:=s;68. 下述二叉樹中,哪一種滿足性質(zhì):從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序（ D ）。 A二叉排序樹 B哈夫曼樹 CAVL樹 D堆69. 下面給出的四種排序法中( D )排序法是不穩(wěn)定性排序法。 A.

24、插入 B. 冒泡 C. 二路歸并 D. 快速排序70. 若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 歸并排序 D. 直接插入排序二 填空題1、在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是： p->next!=null2、表達(dá)式23+(12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是： (請在表達(dá)式中用點(.)將數(shù)隔開)23.12.3*2-4/34.5*7/+108.9/+3、有一個100*90的稀疏矩陣，非0元素有9個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是

25、 604、深度為9的完全二叉樹至少具有的 個結(jié)點2565、已知二叉樹后序為DGEBFCA，中序為DBGEACF，則前序一定是 ABDEGCF6、先根遍歷樹林正好等同于按_ _遍歷對應(yīng)的二叉樹.先序7、構(gòu)造n個結(jié)點的強連通圖，至少有_條弧。n8、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比較的元素下標(biāo)依次為 6,9,11,12 9、在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點的操作是： s->next=p->next;p->next=s;10、有N個頂點的有向圖，至少需要量_條弧才能保證是連通的。N-111、在順序表（8,11,15,19,25,26,30,3

26、3,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值12，需做的關(guān)鍵碼比較次數(shù)為 413、下面是一個無向圖的鄰接矩陣，試將有關(guān)數(shù)據(jù)填入本題的空白處（頂點號由1開始） 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 該圖的頂點數(shù)為 該圖的邊數(shù)為 頂點3的度為 。5 6 214、后根遍歷樹林正好等同于按_(6) _遍歷對應(yīng)的二叉樹。中序15、n個結(jié)點的完全有向圖含有邊的數(shù)目_(7) n*（nl）16、當(dāng)問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的_。時間復(fù)雜度17、假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到

27、輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為_。 SXSSXXSSXSSXXX18、在一棵度為3的樹中，度為2的結(jié)點個數(shù)是1，度為0的結(jié)點個數(shù)是6，則度為3的結(jié)點個數(shù)是_。 （注：沒有包含度為1的結(jié)點）219、如圖所示的有向無環(huán)圖可以排出_種不同的拓?fù)湫蛄小?220、利用篩選法將關(guān)鍵字序列(37，66，48，29，31，75)建成的大根堆為(_ _)。75, 66, 48, 29, 31, 3721、對長度為20的有序表進(jìn)行二分查找的判定樹的高度為_。522、n個頂點的連通無向圖，其邊的條數(shù)至少為_。n-123、排序(sorting)有哪

28、幾種方法_，_，_，_，_。直接插入排序，冒泡排序，快速排序，希爾排序，歸并排序，基數(shù)排序，堆排序等24、下面程序段的時間復(fù)雜度為_。（用O估計） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j;O（n*n）25、非線性結(jié)構(gòu)包括_和_。樹，圖26、在線性表的_存儲結(jié)構(gòu)上進(jìn)行插入或刪除操作要移動元素。順序存儲結(jié)構(gòu)27、用一維數(shù)組r0. .m-1表示順序存儲的循環(huán)隊列，設(shè)隊頭和隊尾指針分別是front和rear，且隊頭指針?biāo)傅膯卧e置，則隊滿的條件是_，隊空的條件是_。Front=rear, rear+1=front28、下面表達(dá)式樹所對應(yīng)的表達(dá)式的前綴表達(dá)式是_

29、，后綴表達(dá)式是_。+*a-bc/de , abc-*de/+29、在AOE-網(wǎng)中，設(shè)e(i)和l(i)分別表示活動的最早開始時間和最晚開始時間，則當(dāng)且僅當(dāng)_時，為關(guān)鍵活動。e(i)=l(i)30對有向圖進(jìn)行拓?fù)渑判?，若拓?fù)渑判虿怀晒?，則說明該圖_。下面有向圖的一個拓?fù)溆行蛐蛄惺莀。存在回路，123456798 31、二叉排序樹的特點是其 序列是有序的。 中序遍歷三 簡答題1、名詞解釋：（1）抽象數(shù)據(jù)類型；（2）算法的時間復(fù)雜性；（3）散列法(hashing)；（4）索引文件。（1）抽象數(shù)據(jù)類型：（課本P7）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。（2）算法的時間復(fù)雜性；（課本P15）一般

30、情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f（n），算法的時間量度記作T(n)=O(f(n)，它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。（3）散列法(hashing)：（課本P253）散列法（Hashing）或哈希法是一種將字符組成的字符串轉(zhuǎn)換為固定長度（一般是更短長度）的數(shù)值或索引值的方法。根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映像到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映像過程稱為哈希造表或散列。（4）索引文件： 

31、（課本P311）  除了文件本身（稱作數(shù)據(jù)區(qū)）之外，另建立一張指示邏輯記錄和物理記錄之間一一對應(yīng)關(guān)系的表-索引表。這類包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件稱作索引文件。索引表中的每一項稱作索引項，一般索引項都是由主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址組成的。顯然，索引表必須按主關(guān)鍵字有序，而主文件本身則可以按主關(guān)鍵字有序或無序，前者稱為索引順序文件（Indexed Sequential File），后者稱為索引非順序文件（Indexed NonSequential File）。2、堆與二元查找樹的區(qū)別?（課本P280）堆的定義如下：n個元素的序列Kl，K2，Kn當(dāng)且僅當(dāng)滿足如下關(guān)系時，

32、稱之為堆： (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i) 若將和此序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于(或不小于)其左右孩子結(jié)點的值。 由此，若序列Kl，K2，Kn是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。（課本P227）二叉排序樹又稱二元查找樹（Binary Search Tree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： （1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值； （2）若它的右子樹不空，則右子樹上所

33、有結(jié)點的值均大于它的根結(jié)點的值； （3）它的左、右子樹也分別為二叉排序樹。3、快速分類法的基本思想是什么?（課本P273）快速排序是對起泡排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。4、如下所示的是一個帶權(quán)無向圖，帶框的數(shù)字表示相應(yīng)邊的權(quán)，不帶框的數(shù)字表示頂點號。用prime 算法求最小生成樹時，如果已確定的邊為(5,4),則，下一條邊應(yīng)在哪幾條邊中選取？選取哪一條？1234565723415438下一條邊應(yīng)在（5，1），（5，6），（4，6），（4，3）中

34、選取，根據(jù)MST性質(zhì)應(yīng)該選取（4，6）。5、二叉樹的后根遍歷的序列中，任何一個非葉子結(jié)點均處在其孩子結(jié)點后面。該論斷是否正確？ 正確6、有一棵哈夫曼樹共有5 個葉子結(jié)點其權(quán)值分別為0.1,0.25,0.08,0.21,0.9,試畫出該哈夫曼樹。假設(shè)該葉子分別表示a,b,c,d,e，分別給出五個葉子對應(yīng)的哈夫曼編碼。0000，0001，001，01，17、對于一個隊列，若入隊的順序為a,b,c, 則所有可能的出隊序列是什么？a,b,c8、已知一個圖如下，試畫出其逆鄰接鏈表。 2134注意：課本P164，逆鄰接表是為了便于確定頂點的入度。9、若一個棧的輸入序列是1,2,3，n, 其輸出序列為p1,

35、p2,pn,若 p1=n，則pi為多少？Pi= n-i+110、非空的二叉樹的中根遍歷序列中，根的右子樹的所有結(jié)點都在根結(jié)點的后邊，這說法對嗎？正確11、已知二叉樹的中根遍歷序列為abc，試畫出該二叉樹的所有可能的形態(tài)。5種12、已知一個圖如圖所示，如從頂點a出發(fā)進(jìn)行按深度優(yōu)先遍歷，可否得到序列acebdf ?為什么？若按廣度優(yōu)先遍歷，能否得到序列abedfc?為什么？ dabcef不行，不行根據(jù)深度優(yōu)先和廣度優(yōu)先遍歷的規(guī)則13、棧的存儲方式有哪兩種？順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)14、對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將p所指結(jié)點的數(shù)據(jù)元素與其確實存

36、在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。其中：datenext單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為priordatenext雙向鏈表的結(jié)點結(jié)構(gòu)為 1.單鏈表不行，因為單鏈表沒有辦法得到其前驅(qū)；2. 單循環(huán)鏈表可以，假設(shè)鏈表的元素大于等于2：struct Node Node * next; int data;循環(huán)鏈表 Node * list;Node *pnode = p;while(pnode->next != p) pnode = pnode->next;/找到其前驅(qū)了int tmp = pnode->data;pnode->data =

37、 p->data;p->data->tmp;3.雙向鏈表可以，假設(shè)鏈表的元素大于等于2，且p不為鏈表頭。struct NodeNode * next;Node * pre;int data;雙向鏈表list;Node *pnode = p;if(p->pre != NULL) int tmp = p->data; p->data = p->pre->data; p->pre->data = tmp;15、假設(shè)通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010

38、。(1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標(biāo)注相應(yīng)字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權(quán)路徑長度。（1）根據(jù)哈夫曼編碼的規(guī)則畫樹。（課本P146）（2）（具體計算方法見課本P146）該哈夫曼樹的帶權(quán)路徑長度：25316、對于線性表的兩種存儲結(jié)構(gòu)（順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)），如果線性表基本穩(wěn)定，并且很少進(jìn)行插入和刪除操作，但是要求以最快速度存取線性表中的元素，則應(yīng)選擇哪種存儲結(jié)構(gòu)？試說明理由。（期中試題）順序存儲17、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個棧s1和s2使用，怎樣分配這部分存儲空間，使得對任一棧

39、，僅當(dāng)這部分空間全滿時才發(fā)生上溢。如何判斷棧滿，?？?，并對兩個棧的容量進(jìn)行分析。（期中試題）18、設(shè)某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹；（2）畫出該二叉樹后序線索化圖。（3）試畫出該二叉樹對應(yīng)的森林。（期中試題）19、 一棵二叉排序樹結(jié)構(gòu)如下,各結(jié)點的值從小到大依次為1-9，請標(biāo)出各結(jié)點的值。從上到下，從左到右依次為：5，1，9，4，6，2，7，3，820、 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj&l

40、t;Pk<Pi。如果i<j，則對于pi<pj情況，說明pi在pj入棧前先出棧。而對于pi>pj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于i<j<k，不可能出現(xiàn)pj<pk<pi的輸出序列。換句話說，對于輸入序列1，2，3，不可能出現(xiàn)3，1，2的輸出序列。【詳細(xì)參考】 因為借助棧由輸入序列1, 2, 3, , n,可得到輸出序列p1, p2, p3, , pn ,如果存在下標(biāo)i, j, k,滿足i < j < k,那么在輸出序列中,可能出現(xiàn)如下5種情況:i進(jìn)棧,i出棧,j進(jìn)棧,j出棧,k進(jìn)棧,k出

41、棧.此時具有最小值的排在最前面pi位置,具有中間值的排在其后pj位置,具有最大值的排在pk位置,有pi < pj < pk, 不可能出現(xiàn)pj < pk < pi的情形;i進(jìn)棧,i出棧,j進(jìn)棧,k進(jìn)棧,k出棧,j出棧.此時具有最小值的排在最前面pi位置,具有最大值的排在pj位置,具有中間值的排在最后pk位置,有pi < pk < pj , 不可能出現(xiàn)pj< pk < pi的情形;i進(jìn)棧,j進(jìn)棧,j出棧,i出棧,k進(jìn)棧,k出棧.此時具有中間值的排在最前面pi位置,具有最小值的排在其后pj位置,有pj < pi < pk, 不可能出現(xiàn)pj

42、< pk < pi的情形;i進(jìn)棧,j進(jìn)棧,j出棧,k進(jìn)棧,k出棧,i出棧.此時具有中間值的排在最前面pi 位置,具有最大值的排在其后pj位置,具有最小值的排在pk位置,有pk < pi < pj, 也不可能出現(xiàn)pj < pk < pi的情形;i進(jìn)棧,j進(jìn)棧,k進(jìn)棧,k出棧,j出棧,i出棧.此時具有最大值的排在最前面pi 位置,具有中間值的排在其后pj位置,具有最小值的排在pk位置,有pk < pj < pi, 也不可能出現(xiàn)pj < pk < pi的情形.四 算法閱讀1、void AE(Stack& S) InitStack(S

43、); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;i<5;i+) Push(S,2*ai); while(!StackEmpty(S) print(Pop(S); 該算法被調(diào)用后得到的輸出結(jié)果為：（期中試題）2、 void ABC (BTNode *BT,int &c1,int &c2) if (BT !=NULL ) ABC(BT->left,c1,c2); c1+; if (BT->left=NULL&&BT-&g

44、t;right=NULL) c2+; ABC(BT->right,c1,c2); /if 該函數(shù)執(zhí)行的功能是什么？（期中試題）3、在下面的每個程序段中，假定線性表La的類型為List，e的類型為ElemType,元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(zhí)行后所得到的線性表La。（1）InitList(La); Int a=100,26,57,34,79; For (i=0;i<5;i+) ListInsert(La,1,ai);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3

45、）ClearList(La); For (i=0;i<5;i+) ListInsert(La,i+1,ai);（期中試題）4、int Prime(int n) int i=1; int x=(int) sqrt(n); while (+i<=x) if (n%i=0) break; if (i>x) return 1; else return 0; (1)指出該算法的功能；(2)該算法的時間復(fù)雜度是多少？（期中試題）5. 寫出下述算法A的功能： 其中BiTree定義如下: Typedef struct BiTNode TElemType data; struct BiTNod

46、e *LChild, *RChild;BiTNode, *BiTree;Status A(BiTree T) Queue Q; InitQueue(Q); ENQueue(Q,T); While(not QueueEmpty(Q) DeQueue(Q,e); If(e=NULL) break; Else Print(e.data);ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); （期中試題）6.閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；(2)簡

47、述算法algo的功能。void algo(Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);（1）q=(8,7,5,4,2)（2）算法利用棧S輔助實現(xiàn)隊列Q的逆置。五 算法填空1、下面是在帶表頭結(jié)點的循環(huán)鏈表表示的隊列上，進(jìn)行出隊操作，并將出隊元素的值保留在x中的函數(shù)，其中rear是指向隊尾結(jié)點的指針。請在橫線空白處填上適當(dāng)?shù)恼Z句。typedef struct node int data; struct node *next; lklist;void del( lklist rear, int &x); lklist p,q; q=rear-> next; if (_q = = rear_) printf( “it is empty!n” ); else p=q->next; x=p->data; _q->next=p->next_ ; if (_rear= =p_) rear=q; free(p) ; ;2、堆分配存儲方式下，串連接函數(shù)。（期中試題）