數(shù)據(jù)結構與算法期末練習題含答案

1、數(shù)據(jù)結構與算法期末練習 一 選擇題1以下與數(shù)據(jù)的存儲結構無關的術語是（ D ）。A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧2. 算法的時間復雜度取決于（ A ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 計算機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. 有關靜態(tài)鏈表的敘述：(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。(2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表

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

3、圖的頂點個數(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的拓撲序列是（ A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V

4、2,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ù)結構中，哪一個是線性結構（ D ）？ A廣義表 B. 二叉樹 C

5、. 稀疏矩陣 D. 串13下面關于線性表的敘述中，錯誤的是哪一個？（ B ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。14. 設一個棧的輸入序列是 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. 設n為正整數(shù).下列程序段中前置以的語句的頻度為（ B ）。i = 1; k = 0; do k+= 10*i; i+;While

6、(i <= n-1); A. n 1 B. n C. n + 1 D. n - 216. 一棵具有 n個結點的完全二叉樹的樹高度（深度）是（ 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個結點的完全有向圖含有邊的數(shù)目（D）。An*n n（n） Cn2 Dn*（nl）19穩(wěn)定的排序方法是（ B ） A直接插入排序和快速排序 B折半插入排序和起泡排序

7、C希爾排序和四路歸并排序 D樹形選擇排序和shell排序20有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4） 用快速排序的劃分方法進行一趟劃分后數(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ù)據(jù)的存儲結構無關？（ A ）A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表22下面關于串的的敘述中，哪一個是不正確的？（ B ）A串是字符的有限序列 B空串是由空格構成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存

8、儲23. 某堆棧的輸入序列為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. 關于二叉樹的敘述：只有一個結點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹。正確的是（ D ）A B C D25高度為 K的二叉樹最大的結點數(shù)為（ C ）。A2k B2k-1 C2k -1 D2k-1-126從下列有關樹的敘述中,選出正確的敘述（ C ）A二叉樹中每個結點有兩個子結點,而樹無此限制,因此二叉樹是樹

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

10、 (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. 一個序列的初始狀態(tài)為（46，77，82，53，31，70）

11、，今對其進行冒泡排序，當進行兩趟冒泡后，序列中的元素排列為( 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. head->next=head35. 在

12、一個單鏈表中，已知*q是（*q表示指針q所指的結點，以下同）*p的前驅(qū)結點，在*q之后插入結點*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 的尾結點 *p 滿足下列( C )條件A) head->next=p; B) head=p; C) p->next=head; D) p->next=03

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

14、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. 已知有向圖的正鄰接鏈表的存儲結構如下，從頂點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 ，則第五個元素的地址是( C )A) 10

15、2 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 B) 5 C) 6 D) 748. 設棧s

16、的類型為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個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是( B )A.O(1) B.O(n)C.O(nl

17、ogn) D.O(n*n)51. 鏈棧與順序棧相比，比較明顯的優(yōu)點是( D )A.插入操作更加方便 B.刪除操作更加方便C.不會出現(xiàn)下溢的情況 D.不會出現(xiàn)上溢的情況52. 二叉樹中第5層上的結點個數(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. 如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用（B）A深度優(yōu)先搜索算法B廣度優(yōu)先搜索算法C求最小生成樹的prim算法D拓撲排序算法55. 對n個關鍵字的序列進行快速排序，平均情況下的

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

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

20、Link=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 限制存取位置的線性結構 B 鏈式存儲的非線性結構 C 順序存儲的線性結構 D 限制存取位置的非線性結構62. 單循環(huán)鏈表表示的隊列長度為n，若只

21、設頭指針，則入隊的時間復雜度為（ A ） A O(n) B O(1) C O(n*n) D O(n*logn)63. 一棵含有n個節(jié)點的k叉樹，可能達到的最小深度為多少？（ 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 )的平均時間復雜性是O(nlogn)。A. 直接插入排序 B.

22、簡單選擇排序C. 快速排序 D. 希爾排序66. 設順序棧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是帶頭結點的單鏈表，p指向表中某結點，則要刪除p結點的后繼結點應執(zhí)行操作( A )；要在p結點后插入s結點應執(zhí)行操作( D )。

23、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ì):從任一結點出發(fā)到根的路徑上所經(jīng)過的結點序列按其關鍵字有序（ D ）。 A二叉排序樹 B哈夫曼樹 CAVL樹 D堆69. 下面給出的四種排序法中( D )排序法是不穩(wěn)定性排序法。 A. 插入 B. 冒泡 C. 二路歸并 D. 快

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

25、知二叉樹后序為DGEBFCA，中序為DBGEACF，則前序一定是 ABDEGCF6、先根遍歷樹林正好等同于按_ _遍歷對應的二叉樹.先序7、構造n個結點的強連通圖，至少有_條弧。n8、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比較的元素下標依次為 6,9,11,12 9、在單鏈表指針為p的結點之后插入指針為s的結點的操作是： s->next=p->next;p->next=s;10、有N個頂點的有向圖，至少需要量_條弧才能保證是連通的。N-111、在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值12，

26、需做的關鍵碼比較次數(shù)為 413、下面是一個無向圖的鄰接矩陣，試將有關數(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) _遍歷對應的二叉樹。中序15、n個結點的完全有向圖含有邊的數(shù)目_(7) n*（nl）16、當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的_。時間復雜度17、假設S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c

27、/d”得到“ab*cd/+”的操作序列為_。 SXSSXXSSXSSXXX18、在一棵度為3的樹中，度為2的結點個數(shù)是1，度為0的結點個數(shù)是6，則度為3的結點個數(shù)是_。219、如圖所示的有向無環(huán)圖可以排出_種不同的拓撲序列。1220、利用篩選法將關鍵字序列(37，66，48，29，31，75)建成的大根堆為(_ _)。75, 66, 48, 29, 31, 3721、對長度為20的有序表進行二分查找的判定樹的高度為_。522、n個頂點的連通無向圖，其邊的條數(shù)至少為_。n-123、排序(sorting)有哪幾種方法_，_，_，_，_。直接插入排序，冒泡排序，快速排序，希爾排序，歸并排序，基數(shù)排序

28、，堆排序等24、下面程序段的時間復雜度為_。（用O估計） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j;O（n*n）25、非線性結構包括_和_。樹，圖26、在線性表的_存儲結構上進行插入或刪除操作要移動元素。順序存儲結構27、用一維數(shù)組r0. .m-1表示順序存儲的循環(huán)隊列，設隊頭和隊尾指針分別是front和rear，且隊頭指針所指的單元閑置，則隊滿的條件是_，隊空的條件是_。Front=rear, rear+1=front28、下面表達式樹所對應的表達式的前綴表達式是_，后綴表達式是_。+*a-bc/de , abc-*de/+29、在AOE-網(wǎng)中，設e(i

29、)和l(i)分別表示活動的最早開始時間和最晚開始時間，則當且僅當_時，為關鍵活動。e(i)=l(i)30對有向圖進行拓撲排序，若拓撲排序不成功，則說明該圖_。下面有向圖的一個拓撲有序序列是_。存在回路，123456798 31、二叉排序樹的特點是其 序列是有序的。 中序遍歷三 簡答題1、名詞解釋：（1）抽象數(shù)據(jù)類型；（2）算法的時間復雜性；（3）散列法(hashing)；（4）索引文件。2、堆與二元查找樹的區(qū)別?3、快速分類法的基本思想是什么?4、如下所示的是一個帶權無向圖，帶框的數(shù)字表示相應邊的權，不帶框的數(shù)字表示頂點號。用prime 算法求最小生成樹時，如果已確定的邊為(5,4),則，下一

30、條邊應在哪幾條邊中選??？選取哪一條？12345657234154385、二叉樹的后根遍歷的序列中，任何一個非葉子結點均處在其孩子結點后面。該論斷是否正確？ 6、有一棵哈夫曼樹共有5 個葉子結點其權值分別為0.1,0.25,0.08,0.21,0.9,試畫出該哈夫曼樹。假設該葉子分別表示a,b,c,d,e，分別給出五個葉子對應的哈夫曼編碼。7、對于一個隊列，若入隊的順序為a,b,c, 則所有可能的出隊序列是什么？8、已知一個圖如下，試畫出其逆鄰接鏈表。 21349、若一個棧的輸入序列是1,2,3，n, 其輸出序列為p1,p2,pn,若 p1=n，則pi為多少？10、非空的二叉樹的中根遍歷序列中，

31、根的右子樹的所有結點都在根結點的后邊，這說法對嗎？11、已知二叉樹的中根遍歷序列為abc，試畫出該二叉樹的所有可能的形態(tài)。12、已知一個圖如圖所示，如從頂點a出發(fā)進行按深度優(yōu)先遍歷，可否得到序列acebdf ?為什么？若按廣度優(yōu)先遍歷，能否得到序列abedfc?為什么？ dabcef 13、棧的存儲方式有哪兩種？14、對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結點的指針p，能否將p所指結點的數(shù)據(jù)元素與其確實存在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。其中：datenext單鏈表和單循環(huán)鏈表的結點結構為priordatenext雙向鏈表的結點

32、結構為 15、假設通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。(1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結點中標注相應字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權路徑長度。16、對于線性表的兩種存儲結構（順序存儲和鏈式存儲結構），如果線性表基本穩(wěn)定，并且很少進行插入和刪除操作，但是要求以最快速度存取線性表中的元素，則應選擇哪種存儲結構？試說明理由。17、內(nèi)存中一片連續(xù)空間（不妨假設地址從1到m）提供給兩個棧s1和s2使用，怎樣分配這部分存儲空間，使

33、得對任一棧，僅當這部分空間全滿時才發(fā)生上溢。如何判斷棧滿，?？?，并對兩個棧的容量進行分析。18、設某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹；（2）畫出該二叉樹后序線索化圖。（3）試畫出該二叉樹對應的森林。19、 一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。20、 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。四 算法閱讀1、void AE(Stack&

34、 S) InitStack(S); 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)用后得到的輸出結果為：2、 void ABC (BTNode *BT,int &c1,int &c2) if (BT !=NULL ) ABC(BT->left,c1,c2); c1+; if (BT->left=NULL&&

35、amp;BT->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)

36、;（3）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)該算法的時間復雜度是多少？5. 寫出下述算法A的功能： 其中BiTree定義如下: Typedef struct BiTNode TElemType data; struct BiTNode *LChild

37、, *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)假設隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；(2)簡述算法algo的功能。void

38、 algo(Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);五 算法填空1、下面是在帶表頭結點的循環(huán)鏈表表示的隊列上，進行出隊操作，并將出隊元素的值保留在x中的函數(shù)，其中rear是指向隊尾結點的指針。請在橫線空白處填上適當?shù)恼Z句。typedef struct node int data; struct node *next; lklist;void del( lklist re

39、ar, int &x); lklist p,q; q=rear-> next; if (_) printf( “it is empty!n” ); else p=q->next; x=p->data; _ ; if (_) rear=q; ; ;2、堆分配存儲方式下，串連接函數(shù)。typedef struct char * ch； int len； HString； HString *s， t; Status StrCat(s， t) /* 將串t連接在串s的后面 */ int i; char *temp; f if (temp=NULL) return(0); for

40、 (i=0; ;i+) tempi=s->chi; for ( ;i<s->len + t.len;i+) tempi=t.chi-s->len; s->len+=t.len; fr s->ch=temp; return(1); 3、向單鏈表的末尾添加一個元素的算法。 LNode是一個包含（data，Next）的結構體Void InsertRear(LNode*& HL,const ElemType& item)LNode* newptr;newptr=new LNode;If (_)cerr<<"Memory allo

41、cation failare!"<<endl;exit(1);_=item;newptr->next=NULL;if (HL=NULL) HL=_;elseLNode* P=HL;While (P->next!=NULL) _;p->next=newptr; 4、L為一個帶頭結點的循環(huán)鏈表。函數(shù)f30的功能是刪除L中數(shù)據(jù)域data的值大于c的所有結點，并由這些結點組建成一個新的帶頭結點的循環(huán)鏈表，其頭指針作為函數(shù)的返回值。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。LinkList f30(LinkList L, int c) LinkList L

42、c,p,pre; pre=L; p= (1) ; Lc=(LinkList) malloc(sizeof(ListNode); Lc->next=Lc; while(p!=L) if(p->data>c) pre->next=p->next; (2) ; Lc->next=p; p=pre->next; else pre=p; (3) ; return Lc; vertexfirstedge5、已知圖的鄰接鏈表的頂點表結點結構為 adjvexnext邊表結點EdgeNode的結構為下列算法計算有向圖G中頂點vi的入度。請在空缺處填入合適的內(nèi)容，使其成為

43、一個完整的算法。int FindDegree(ALGraph *G,int i)/ALGraph為圖的鄰接表類型 int dgree, j; EdgeNode *p; degree= (1) ; for(j=0;j<G->n;j+) p=G->adjlistj. firstedge; while ( (2) ) if( (3) ) degree+; break; p=p->next; return degree;六 簡單應用題1、已知一個非空二元樹，其按中根和后根遍歷的結果分別為：中根：C G B A H E D J F I后根：G B C H E J I F D A試

44、將這樣二元樹構造出來;若已知先根和后根的遍歷結果，能否構造這棵二元樹，為什么?2、對于下圖，畫出按Kruskal（克魯斯卡爾）算法和Prim（普里姆）算法構造最小生成樹的過程。3、畫出由下面的二叉樹轉換成的森林。4、用Floyed（弗洛伊徳）算法求下圖每一對頂點之間的最短路徑及其長度，將計算過程的中間和最后結果填入下表： A A(0) A(1) A(2) A(3) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3PATH PATH(0) PATH(1) PATH(2) PATH(3) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 35、哈夫曼樹在構造時，首先進行初始化存儲空

45、間，結果如左下圖，當構造完成后，請?zhí)顚懽詈鬆顟B(tài)表，如右下圖。weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000-000-000-000-000-000-000-0001234567891011121314156、考慮右圖：(1)從頂點A出發(fā)，求它的深度優(yōu)先生成樹(4分)(2)從頂點E出發(fā)，求它的廣度優(yōu)先生成樹(4分)(3）根據(jù)普利姆(Prim) 算法，求它的最小生成樹(請畫出過程)(設該圖用鄰接表存儲結構存儲，頂點的鄰接點按頂點編號升序排列)(6分)答案如下：七 編寫算法題1、設計函數(shù)，求一個單鏈表中值為x的結點個數(shù)。并將結果放在頭結點的data 域中。void count1(lklist head,int x)2、設計遞歸函數(shù)，求一棵二叉樹的深度。int depth (bitreptr ro