必看數據結構期末復習題及部分答案解析

1、0一是非題1. 數據結構(應該是抽象數據類型)可用三元式表示（D，S，P）。其中：D是數據對象，S是D上的關系，P是對 D的基本操作集。(f)2 簡單地說,數據結構是帶有結構的數據元素的集合。(t)3 判斷帶頭結點的非空循環(huán)單鏈表（頭指針為L）中指針p所指結點是最后一個元素結點 的條件是：p->next=L。(t)4 線性表的鏈式存儲結構具有可直接存取?表中任一元素的優(yōu)點。(f) 5 線性表的順序存儲結構優(yōu)于鏈式存儲結構。(f)6. 在單鏈表P指針所指結點之后插入S結點的操作是： P->next= S ; S-> next = P->next;。(順序弄反了)(f)7

2、對于插入、刪除而言，線性表的鏈式存儲優(yōu)于順序存儲。(t)8. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。(f)9. 棧和隊列是操作上受限制的線性表。(t)10. 隊列是與線性表完全不同的一種數據結構。棧和隊列是操作上受限制的線性表(f)11. 隊列是一種操作受限的線性表，凡對數據元素的操作僅限一端進行。對列不是(f)12. 棧和隊列也是線性表。如果需要，可對它們中的任一元素進行操作。(f)13. 棧是限定僅在表頭進行插入和表尾進行刪除運算的線性表。(f)14. 二叉樹中每個結點有兩個子結點，而對一般的樹，則無此限制，所 以，二叉樹是樹的 特殊情形。(f)15 二叉樹是一棵結點的度

3、最大為二的樹二叉樹和樹相互獨立。(f) 16 赫夫曼樹中結點個數一定是奇數。(t)17 在二叉樹的中序遍歷序列中，任意一個結點均處在其左孩子結點的后面。(t)18 假設B是一棵樹，B是對應的二叉樹。則B的后根遍歷相當于B的后序遍歷 后根遍歷相當于中序遍歷。(f)19. 通常，二叉樹的第i層上有2i-1個結點。應該為12i-1個(f)20. 中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅結點和直接后繼結點。(t)21 二叉樹的先序遍歷序列中，任意一個結點均處在其孩子結點的前面。(t)22 由樹結點的先根序列和后根序列可以唯一地確定一棵樹。 (t)23 鄰接多重表可以用以表示無向圖，也可用以表示有

4、向圖。只能表示無向圖，有向圖用十字鏈表(f)24 可從任意有向圖中得到關于所有頂點的拓撲次序帶環(huán)圖沒有。(f)25 有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)26 關鍵路徑是AOE網中源點到匯點的最短路徑。(f)27 連通圖G的生成樹是一個包含G的所有n個頂點和n-1條邊的子圖。(f)28 一個無向圖的連通分量是其極大的連通子圖。(t)29 十字鏈表可以表示無向圖，也可用以表示有向圖。(f)30 鄰接表可以表示有向圖，也可以表示無向圖。（ t ）31. 二叉排序樹的平均查找長度為O(log)。(t)32. 二叉排序樹的最大查找長度與（LOG2N）同階。(f)33 選用好

5、的HASH函數可避免沖突。哈希函數有幾種處理沖突的方法(f)34 折半查找不適用于有序鏈表的查找。(t)35. 對于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 對于任何待排序序列來說，快速排序均快于冒泡排序。(f)37 在最壞情況下，堆排序的時間性能是O(nlogn),比快速排序好(t)38 快速排序具有最好的平均時間性能，它在任何時候的時間復雜度都是O（n log n）。(f)39. 字符串是數據對象特定的線性表。(t)40. 空串與空格串是相同的。(f)41. 對于一棵m階的B-樹.樹中每個結點至多有m 個關鍵字.除根之外的所有非終端結點至 少有m/2個關鍵字。(f)42.

6、 當二叉排序樹是一棵平衡二叉樹時，其平均查找長度為O(log2n)。(t)43. 廣義表的表頭和表尾都是廣義表。(f)44 二維數組是其數據元素為線性表的線性表。(t)選擇題。1 從邏輯上可以把數據結構分成( c )。 A. 動態(tài)結構和靜態(tài)結構 B. 順序組織和鏈接組織 C. 線性結構和非線性結構 D. 基本類型和組合類型2 線性表L在( b )情況下適于使用鏈表結構實現。 A. 不需修改L的結構 B. 需不斷對L進行刪除、插入 C. 需經常修改L中結點值 D. L中含有大量結點3 帶頭結點的單鏈表L為空的判斷條件是 b 。 帶頭結點的循環(huán)鏈表L為空的判斷條件是 c 。 A. L=null B

7、. L->next=null C. L->next=L D. L!=null4 若順序表中各結點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定 的結點，將該結點與其后繼（若存在）結點交換位置，使得經常被查找的結點逐漸移至 表尾。以下為據此策略編寫的算法，請選擇適當的內容，完成此功能。 順序表的存儲結構為：typedef struct ElemType *elem; /數據元素存儲空間，0號單元作監(jiān)視哨 int length; /表長度 SSTable;int search_seq(SSTable ST,KeyType key) /在順序表ST中順序查找關鍵字等于key

8、的數據元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key) f ;if( G ) ST.elemiST.elemi+1； e ；return i;A. i>0 B. i>=0 C. i<ST.length D. i<=ST.lengthE. i+ F. i- G. A和C同時滿足 H. B和D同時滿足5 若入棧順序為A、B、C、D、E，則下列( d )出棧序列是不可能的。 AA、B、C、D、E BB、C、D、A、E CC、D、B、E、A DD

9、、E、C、A、B6 遞歸程序可借助于( c )轉化為非遞歸程序。 a.線性表 b.隊列 c: 棧 d.數組 7 在下列數據結構中( c )具有先進先出（FIFO）特性， ( b )具有先進后出(FILO）特性。 a線性表 b棧 c隊列 d廣義表8 若對編號為1，2，3的列車車廂依次通過扳道棧進行調度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,19 在計算遞歸函數時，如不用遞歸過程，應借助于( b ) 這種數據結構。 A. 線性表 B. 棧 C. 隊列 D. 雙向隊列10 若帶頭結點的鏈表只設尾結點指針。下列選擇中

10、（ c ）最適用于隊列。 A）單鏈表 B）雙向鏈表 C循環(huán)單鏈表 D）雙向循環(huán)鏈表11 棧和隊列的一個共同點是( c )。 A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點12 循環(huán)隊列用數組A0.m-1存放其元素值，設頭尾指針分別為front和rear，則當前隊列中 的元素個數是( c )。 A. rear-front-1 B. Rear-front+1 C. (rear-front+m)%m D. Rear-front13 如下關于串的陳述中，正確的是( a, c )。 A. 串是數據元素類型特殊的線性表 B. 串中的元素是字母 C. 串中若干個

11、元素構成的子序列稱為子串 D. 空串即為空格串14 對字符串s=data-structure 執(zhí)行操作replace(s,substring(s,6,8),bas) 的結果是 ( b ) 。 a: database b: data-base c: bas d: data-basucture 1 5 設有二維數組A 5 x 7 ,每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址. 已知A的起始地址為100。則按行存儲時，元素A06的第一個字節(jié)的地址是（d ） 按列存儲時，元素A06的第一個字節(jié)的地址是（ a ） a: 220 b: 200 c: 140 d: 12416對廣義表 A=（a,(b)）

12、,(c,(),d）執(zhí)行操作gettail(gethead(gettail(A) 的結果是：（ b ） 。 a:（） b: （） c: d d: (d)17 假設用于通訊的電文僅由6個字符組成，字母在電文中出現的頻率分別為7, 19, 22, 6, 32, 14。 若為這6個字母設計哈夫曼編碼（設生成新的二叉樹的規(guī)則是按給出的次序從左至 右的結合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（ g ），頻率 為32的字符編碼是（ c ）。 a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:111118 對二叉排序樹（ c ）可得到有序序列。

13、 a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷19 設一棵二叉樹BT的存儲結構如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B C D E F G H rchild 0 5 4 0 8 7 0 0 其中l(wèi)child，rchild分別為結點的左、右孩子指針域，data為結點的數據域。則 該二叉樹的高度為( d )； 第3層有( a )個結點（根結點為第1層）。 A2 B. 3 C. 4 D. 520 先序遍歷圖示二叉樹可得到（ a ）的序列。 (A) (B) (C) (H) (D) (G) (E) (F) (I) a)A B H D

14、 E F I C G b)H B E D F I A C G c) H E I F D B G C A 21 在有n個結點的二叉樹的二叉鏈表表示中，空指針數為 n+1;非空指針樹為 n-1; （ b ）。 a.不定 b.n+1 c.n d.n-122 若某二叉樹有20個葉子結點，有20個結點僅有一個孩子，則該二叉樹的總結點數是 ( c )。度為2的節(jié)點n2 = n0 1;其中no表示度為0的節(jié)點 A40 B. 55 C. 59 D. 6123 已知某二叉樹的先序遍歷次序為abcdefg中序遍歷次序為badcgfe， 則該二叉樹的后序遍歷次序為（ c ）。層次遍歷次序為（ a ）。 a: abc

15、defg b: cdebgfa c: bdgfeca d: edcgfba.24 圖示的三棵二叉樹中( c)為最優(yōu)二叉樹。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 425 已知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。則其先序遍歷次序為（ b ），層次遍歷次序為（ a ）。 a: abcdefg b: abdcefg c: abcdfeg d: abcdegf26 已知某樹的先根遍歷次序為abcdefg后根遍歷次序為cdebgfa。 若將該樹轉換為二叉樹,其后序遍歷次序為（ d ）。a: abcd

16、efg b: cdebgfa c: cdegbfa d: edcgfba27 設x和y是二叉樹中的任意兩個結點，若在先根序列中x在y之前，而在后根序列中x 在y之后，則x和y的關系是( c )。 A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的子孫28 用三叉鏈表作二叉樹的存儲結構，當二叉樹中有n個結點時，有( d )個空指針。 A. n-1 B. n C. n+1 D. n+229 對一棵完全二叉樹進行層序編號。則編號為n的結點若存在右孩子,其位序是( d )。 編號為n的結點若存在雙親,其位置是( a )。 a: n/2 b: 2n c:2n-1 d:2n+1

17、 e:n f: 2(n+1)30 設森林F中有三棵樹，第一、第二和第三棵樹的結點個數分別為m1、m2和m3，則與 森林F對應的二叉樹根結點的右子樹上的結點個數是( d )。 A. m1 B. m1+m2 C. m3 D. m2+m331 下列二叉樹中，( a )可用于實現符號不等長高效編碼。 a:最優(yōu)二叉樹 b:次優(yōu)查找樹 c:二叉平衡樹 d:二叉排序樹32 鄰接表存儲結構下圖的深度優(yōu)先遍歷算法類似于二叉樹的(a )遍歷。 A. 先根 B. 中根 C. 后根 D. 層次33 設無向圖G = (V,E)和G= (V,E)，若G是G的生成樹，則下面不正確的說法是( b )。 A. G是G的子圖&#

18、160;        B. G是G的連通分量（極大連通子圖稱為連通分量） C. G是G的無環(huán)子圖      D. G是G的極小連通子圖且V= V34 任何一個連通圖的最小生成樹( b )。最小生成樹其實是最小權重生成樹的簡稱 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 e f e f35 深度優(yōu)先遍歷圖使用了數據結構（b ），而廣度優(yōu)先遍歷圖使用了數據結構（ c ）。A）數組 B）棧 C）隊列 D）線性表36 已知某有向圖的鄰接表存儲結構如圖所示。 0 E 2

19、 1 1 D 0 3 4 2 C 43 B 1 2 0 4 A 2 根據存儲結構依教材中的算法其深度優(yōu)先遍歷次序為（ d ）。 廣度優(yōu)先遍歷此序為（ c ）。各強連通分量的頂點集為（ h ）。有向圖的極大強連通子圖，稱為強連通分量 a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc與ed f: bc與aed g: ab與ced h: ac與bed37 下列查找方法中（ a ）適用于查找單鏈表。 A）順序查找 B）折半查找 C）分塊查找 D）hash查找38 下列算法中（c 普利姆算法）適用于求圖的最小代價生成樹。（ b ）能對圖作廣度優(yōu)先遍歷。 A）D

20、FS算法 B）BFS算法 C）Prim算法 D）Dijkstra算法39 關鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網中源點至匯點（ c ）的路徑。 a:弧的數目最多 b:弧的數目最少 c:權值之和最大 d:權值之和最小40 希表的查找效率取決于（ d ）。 a: 哈希函數 b:處理沖突的方法。 c:哈希表的裝填因子。 d:以上都是41 在Hash函數H(k)=k MOD m中，一般來說，m應取( c )。 A. 奇數 B. 偶數 C. 素數 D. 充分大的數42 在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢， 可采用 a 方法。 A.設置監(jiān)視哨 B.鏈表存貯 C.二分查

21、找 D.快速查找43 靜態(tài)查找表和動態(tài)查找表的區(qū)別在于( b )。 A. 前者是順序存儲，而后者是鏈式存儲 B. 前者只能進行查找操作，而后者可進行查找、插入和刪除操作 C. 前者只能順序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序44 在一個含有n個元素的有序表上進行折半查找，找到一個元素最多要進行( b )次元素 比較。 Aëlog2(n)û B. ëlog2(n)û+1 C. ëlog2(n+1)û D. ëlog2(n+1)û+145 設輸入序列為20, 45, 30, 89, 70, 3

22、8, 62，19依次插入到一棵2-3樹中(初始狀態(tài)為空)， 該B-樹為（ b ）。再刪除38，該B-樹為（ f ）。 （ 30 62 ） （ 45 ） （19，20）（ 38 45 ） （ 70，89 ） （ 30 ） （ 70 ） （19 20） （38 ）（ 62 ） （ 89 ） a: b: （ 45 70 ） （ 45 ） （20） （ 62 ） （ 89 ） （ 20 ） （ 70 ）（19）（ 30 ） （ 19 ） ( 30,38 ）（ 62 ） （ 89 ） c: d: （ 30 70 ） （ 45 ） （19，20） （ 45 62） （ 89 ） （ 20 ） （ 70 ）

23、 （19 ） （30 ）（ 62 ） （ 89 ） e: f:46根據插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。 圖（ a ）是最終變化的結果。若仍以該插入次序建立平衡二叉樹。圖（ c ）是最 終變化的結果。 80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d:47 若有序表中關鍵字序列為：14，20，25，32，34，45，57，69，77，83，92

24、。畫出二叉判定樹計算，關鍵字在第幾層，就經過幾次比較對其進行 折半查找，則在等概率情況下，查找成功時的平均查找長度是( c )。查找32時需進 行( c )次比較。A. 1 B. 2 C. 3 D. 4 48 已知哈希表地址空間為A9，哈希函數為H(k)=k mod 7，采用線性探測再散列處理沖突指加數為1。 若依次將數據序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲的下標為( h )； 在等概率情況下查找成功的平均查找長度為( c )。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 749 若從二叉樹的根結點到其它任一結點的路徑上所

25、經過的結點序列按其關鍵字遞增有序， 則該二叉樹是( c )。 A. 二叉排序樹 B. 赫夫曼樹 C. 堆 D. 平衡二叉樹50 當待排序序列的關鍵字次序為倒序時，若需為之進行正序排序，下列方案中( d )為佳。 A. 起泡排序 B. 快速排序 C. 直接插入排序 D. 簡單選擇排序51 下列排序算法中，( d)算法可能會出現：初始數據有序時，花費的時間反而最多。 A. 堆排序 B. 起泡排序 C. 歸并排序 D. 快速排序52 在下列排序方法中，（ c 快速排序）方法平均時間復雜度為0(nlogn)， 最壞情況下時間復雜度為0(n2)；（ d ）方法所有情況下時間復雜度均為0(nlogn)。

26、a. 插入排序 b. 希爾排序 c. 快速排序 d. 堆排序 53 已知一組待排序的記錄關鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42下列選擇中（ d ）是快速排序一趟排序的結果。（ c ）是希爾排序（初始步長為3）一趟排序的結果。（ a ）是初始堆（大堆頂）。 A）86,75,77,58,42,19,56,35,48,26. B）26,56,35,75,19,77,58,48,42,86. C）35,26,19,42,58,48,56,75,86,77. D）42,26,48,35,19,56,77,58,75,86.三填空題1 數據結構通常有下列4類基本結構

27、：集合、 線性結構 、樹型結構、圖型結構。2 設單鏈表中結點形式為 data next ，若單鏈表長度大于等于2，指針p指向表中某個結點且p->next非空，此時若要刪除指針p所指的結點，可以通過如下方法進行：將p所指結點的后繼的元素值復制到該結點，然后刪除其后繼結點。相應的語句序列為：p->data = p->next->data; p->next = p->next->next; free(p ->next)換指針的同時還要交換數據3 線性表的順序存儲結構是以 數組下標 來表示數據元素之間的邏輯關系的。4 已知P是單鏈表中某一結點的指針，P既

28、不是首元結點也不是尾元結點，Q是P 的 前驅 結點指針。當刪除P結點時，鏈表的鏈接可用語句（ q->netx = p->next ）實現。5 已知某樹的先根遍歷次序為abcdefg后根遍歷次序為cdebgfa。 若將該樹轉換為二叉樹,其后序遍歷次序為（ ）。層次遍歷次序為（ ）。6 已知某二叉樹的先序遍歷次序為afbcdeg后序遍歷次序為cedbgfa。 其后序遍歷次序為（ ）。層次遍歷次序為（ ）。7 在二叉樹的第i層上至少有_1_個結點, 至多有_2_個結點 , 深度為k的二叉樹至多有_2_-1_個結點.8 對樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲結構, 則樹

29、的先序遍歷可借用二叉樹的 遍歷算法來實現, 而樹的后序遍歷可借用二叉樹的 中序遍歷 遍歷算法來實現。9 設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少 是 2*h - 1 ，至多是 滿樹 。10 對任何一棵二叉樹T,若其終端結點數為n0.度為2的結點為n2,則n0與n2的關系為 ( n0 = n2 +1 )。11 如果對完全二叉樹中結點從1開始按層進行編號，設最大編號為n；那么，可以斷定編 號為i (i>1)的結點的父結點編號為( i/2向下取整 )；所有編號（ i>n/2）的結點為葉子結點。 12 n個頂點的連通圖至少有 條邊，至多有 n*(n-1

30、)/2條邊，此時即是完全圖 條邊。13 對于圖的存儲結構有（ 數組表示法 ）、（ 鄰接表法 ）( 十字鏈表法 ) ( 鄰接多重表法 )等方法。14 在一個無向圖的鄰接表中，若表結點的個數是m，則圖中邊的條數是_m/2_條。15 若有序表中關鍵字序列為：12，22，33，44，55，66，77，88，99對其進行折半查找， 則在等概率情況下，查找成功時的平均查找長度是（ ）。查找99時需進行（ ）次比 較。16 在哈希表中，處理沖突的方法有開放定址法， 再哈希表法 ， 鏈地址法 等。17 在二叉樹的第i層上至少有_個結點, 至多有_個結點 ,深度為k的二叉樹至多有 個結點.18 對于一棵高度為K

31、的二叉排序樹，結點數最少可有 個，最多可有 個。19 用 中序遍歷 遍歷對二叉排序樹進行訪問可得到有序序列。20 已知Hash函數為 H（K）=K mod 13 ，散列地址為0 -14，用二次探測再散列 處理沖突，關鍵字（23，34，56，24，75，12，49, 52，36，92） 的分布如圖，則平均成功的查找長度為（ ）、平均失敗的查找長度為（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634 232475124921 一棵階的-樹，第一層至少有一個結點；第二層至少有2個結點， 除根之外的所有非終端結點至少有（ ）棵子樹， 樹中每個結點至多有

32、（ ）棵子樹。22 在哈希表中，處理沖突的方法有開放定址法， ， ,23 哈希表的查找效率取決于（ 哈希函數是否均勻； 處理沖突的方法； 哈希表的裝填因子 ）。24高度為4 (包含不帶關鍵字的葉子結點層)的7階B樹最少有 個關鍵字，最多 有_個關鍵字；如果其中的某結點正好有2個兒子，那么，該結點必定是 結點。25 對n個元素的序列進行內部排序，若用起泡排序法，最少的比較次數是 n-1 ，最多的比較次數是 n(n-1)/2 。25 (算法填空)Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) /先序非遞歸遍歷二叉樹。Init

33、stack ( S ); Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )&& _p_ ) if (!Visit (p->data ) ) return ERROR; _push(s,p->lchild)_ ; Pop ( S , p ); if ( _(!stackempty(s) _ ) _ pop(S, p); push( S, p->rchild ); return ok;26 (算法填空)下列算法試圖完成在數組A中搜索有無關鍵字key，若有，返回數組下標,若無，返回-1。在“

34、 ”處填上合適的內容,完成該算法。int BinarySearch (keytype A , int low,int high, keytype key )while ( low <= high) middle = (low+high) /2;if ( Amiddle = key ) return middle; if (key < Amiddle) high = middle -1 ; else low = middle + 1 ;return -1; /end of BinarySearch27 (算法填空)下列函數為堆排序中的堆調整過程（調整H.rs的關鍵字，使H.rs.m成

35、為一小頂堆）。請在“ ”處填上合適的內容,完成該算法。Void heapadjust( heaptype H , int s , int m ) rc=H.rs;for (j=2*s;j<=m;j*=2) if (j<m && rj+1>rj ) +j;if ( rc > H.rj ) break;H.rs=H.rj; s=j; H.Rs = rc ;/heapadjust圖示結構題1 已知在電文中只出現頻率為 ( 5,26,7,23,20,19 )的個字符， 畫出你建的哈夫曼樹，并給出其哈夫曼編碼。2.已知某二叉樹的后序遍歷和中序遍歷次序分別為DBFG

36、ECA和BDACFEG 請畫出該二叉樹，并為之建立先序線索沒有左子樹，則建立該節(jié)點的前驅，若沒有右子樹，這指向該節(jié)點的后繼。3 已知某二叉樹的先序遍歷次序為：a,b,c,d,e,f,g.中序遍歷次序為：b,a,d,f,e,g,c 畫出該二叉樹，并在該二叉樹上建立中序線索。4 某二叉樹的中序遍歷次序為BEGFDAC， 先序遍歷次序為ABDEFGC。 試畫出該二叉樹，并為之建立中序線索（圖示之）。5 已知某二叉樹的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG， 請構造并畫出該二叉樹。6 設某一電文只出現a,b,c,d,e,f,g 7個字母；出現頻率分別為30%,10%,05%,04%

37、,13%,18% 與20%，請給出各字母的哈夫曼編碼。7 將圖示森林轉換為二叉樹，并對該二叉樹先序全序線索化。hda jibfec mlkg 8 將圖示森林轉換為二叉樹，并對該二叉樹中序全序線索化。561 97832 4 9 某二叉樹的結點數據采用順序存儲表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19ABC D E  F   GH    I（1）試畫出此二叉樹的圖形表示。（2）將此二叉樹看作森林的二叉樹表示，試將它還原為森

38、林。10 已知某有向圖如圖所示：a 1）給出其十字鏈表存儲結構 2）給出其深度優(yōu)先遍歷次序。 3）給出其廣度優(yōu)先遍歷次序。cb 4）給出各強連通分量。ed11 設輸入序列為20,45,30,89,70,38,62,19，依次插入到一棵2-3樹中(初始狀態(tài)為空)，請畫出該B-樹。12 右圖為一棵3階B樹。 （20，25）1)畫出在該樹上插入元素15 后的B樹。 (10，14)（21）（35） 2)接著，再刪除元素35，畫出刪除后的B樹。13 已知Hash函數為 H（K）=K mod 13 ，散列地址為0 -14，用線性探測再散列處理 沖突，給出關鍵字（56，34，68，23，16，70，48，3

39、5，83，12，14，57） 在散列地址的分布。并指出平均成功的查找長度是多少? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 根據插入次序（20，30，70，60，10，100，110，90，80。）建立平衡的二叉排序樹。15 設哈希表長為16，哈希函數為H(key)=key mod 13，用開放定址法的二次探測再散列處理沖突（di=12，-12，22，-22，32，-32）。依次存入12個元素：56，82，17,24,36,21,83,96,13,34,57,50。請畫出它們在表中的分布情形。16 已知待排序序列為：25,12,9,20,7,31,24,35,

40、17,10，試寫出： (1). 堆排序初始建堆(大頂堆)的結果； (2). 以第一個元素為樞軸的快速排序一趟掃描的結果； (3). 希爾排序第一趟(增量為5)的結果。算法設計題1 設有一個帶頭結點、元素按值遞增有序的單鏈表，結點的類型定義如下：typedef struct LNode int data; struct LNode *next; LNode, *LinkList;編寫算法，刪除其中所有值相同的多余元素結點2 某線性表中元素以降序排列，現要插入一個元素X，插入后該線性元素仍保持降序。線性表采用帶頭結點單鏈表方式存貯。請編寫該插入算法。3 編寫在一有序順序表中插入數據元素X的算法 INSERT（