(完整word版)2017《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(2)

1、2017數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案12.試題 1 答案 7.數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案29.試題 2 答案 1.4.數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案31.6試題 3 答案 2.1.第 3 頁(yè) 共 23 頁(yè)數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案 1單選題（每題 2 分，共 20 分）1. 棧和隊(duì)列的共同特點(diǎn)是 （）。A. 只允許在端點(diǎn)處插入和刪除元素B. 都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒(méi)有共同點(diǎn)2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí) （）.A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針D .頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？ （）A.

2、 隊(duì)列B. 棧C. 線性表D. 二叉樹(shù)4. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644（io）, A22存放位置在 676（10），每個(gè)元素占一個(gè)空間，表示用 10 進(jìn)制表示。問(wèn) A33 （10）存放在什么位置？腳注 （10）5.A688B678C692D 696樹(shù)最適合用來(lái)表示 （）。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素6.C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D .元素之間無(wú)聯(lián)系的數(shù)據(jù)二叉樹(shù)的第 k 層的結(jié)點(diǎn)數(shù)最多為 （ ）.A2k-1B.2K+1C.2K-1D. 2k-17.若有18個(gè)元素的有序表存放在一維數(shù)組 A19中，第一個(gè)元素放A1中,現(xiàn)進(jìn)行二分查找，則查找 A 3的比較序列的下標(biāo)

3、依次為（A. 1 ，2，3B. 9，5，2， 3C. 9，5，3D. 9，4，2， 38. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為A. O（1）B. O（n）C. O（ 1 og2n）D. O（n2）9. 對(duì)于線性表（ 7， 34， 55， 25， 64， 46， 20， 10）進(jìn)行散列存儲(chǔ)時(shí)，若選 用 H（K）=K %9 作為散列函數(shù)，則散列地址為 1 的元素有（ ）個(gè)，A1B2C3D410. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有 ()條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.8二、填空題(每空 1 分，共 26 分)1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： 、 、

4、和2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2,其數(shù)量級(jí)表示為。3. 假定一棵樹(shù)的廣義表表示為 A (C, D (E, F, G), H (I, J),則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為 樹(shù)的度為 。4. 后綴算式9 2 3 +- 10 2 / -的值為 中綴算式(3+4X)-2Y/3對(duì)應(yīng)的后綴算式為 。_5. 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)， 每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外， 還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 指針域，其中有個(gè)指針域是存放了地址，有 個(gè)指針是空指針。6. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所

5、含邊結(jié)點(diǎn)分別有 個(gè)和 個(gè)。7. AOV 網(wǎng)是一種 的圖。8. 在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有 條邊，在一個(gè)具有 n個(gè)頂點(diǎn)的有向完全圖中，包含有 條邊。9. 假定一個(gè)線性表為 (12,23,74,55,63,40)，若按 Key % 4 條件進(jìn)行劃分， 使得同一 余 數(shù) 的 元 素 成 為 一 個(gè) 子 表 ， 則 得 到 的 四 個(gè) 子 表 分 別 為和。10. 向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，貝慚樹(shù)比原樹(shù)的高度。11. 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為 。12. 在快速排序、堆排序、歸并排序中， 卡序是

6、穩(wěn)定的。三、運(yùn)算題(每題6分，共24分)1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A 0.next，試寫(xiě)出該線性表。605078903440357204101234567Adatan ext2. 請(qǐng)畫(huà)出圖10的鄰接矩陣和鄰接表3. 已知一個(gè)圖的頂點(diǎn)集 V和邊集E分別為： V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。4. 畫(huà)出向小根堆中加入數(shù)據(jù)4,

7、 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化第4頁(yè)共23頁(yè)四、閱讀算法(每題 7 分，共 14分)1. LinkList mynote(LinkList L)/L 是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L ；L=L >next； p=L ；S1：while(p >next) p=p >next；S2：p>next=q； q >next=NULL ；return L ；請(qǐng)回答下列問(wèn)題：(1) 說(shuō)明語(yǔ)句 S1 的功能；(2) 說(shuō)明語(yǔ)句組 S2 的功能；(3) 設(shè)鏈表表示的線性表為(ai,a2,an),寫(xiě)出算法執(zhí)行后的返

8、回值所表 示的線性表。2. void ABC(BTNode * BT) if BT ABC (BT->left);ABC (BT->right); cout<<BT->data<<' ' 該算法的功能是：第 # 頁(yè) 共 23 頁(yè)五、算法填空（共 8 分）二叉搜索樹(shù)的查找 遞歸算法 :bool Find(BTreeNode* BST,ElemType& item)if (BST=NULL)return false; /查找失敗else if (item=BST->data) item=BST->data;/查找成功 r

9、eturn ;else if(item<BST->data)return Find(,item);else return Find(,item);/if六、 編寫(xiě)算法(共 8 分) 統(tǒng)計(jì)出單鏈表 HL 中結(jié)點(diǎn)的值等于給定值 X 的結(jié)點(diǎn)數(shù)。int CountX(LNode* HL,ElemType x)第 7 頁(yè) 共 23 頁(yè)試題1答案5.2nn-1n+16.2e7.有向無(wú)回路8.n(n-1)/2n(n_1)9.(12, 40)(74)(23,55, 63)10.增加111.O(log2 n)0(nlog 2n)12.歸并1.線性表為:(78,50：,40,60, 34, 90)01

10、1 10101 01110 11101 012.鄰接矩陣:011 10鄰接表如圖11所示：運(yùn)算題（每題6分，共24分）4A圖11、1.A單選題（每題2分，共20分）2.D3.D4.C5.C6.D7.D8.C、填空題（每空1分，共26分）1.正確性易讀性強(qiáng)壯性咼效率2.O(n)3.933-13 4 X * + 2 Y * 3 / -4.9.D10.A四、3.用克魯斯卡爾算法得到的最小生成樹(shù)為:(1,2)3,(4,6)4,(1,3)5,(1,4)8,1.2.(2,5)10,(4,7)20圖12閱讀算法(每題7分，共14分)(1)查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3

11、)返回的線性表為(a2,a3,an,a1)遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。五、算法填空(每空2分，共8分)true BST->leftBST->right六、編寫(xiě)算法(8分)int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器while(p!=NULL) if (P->data=x) i+;p=p->n ext;/while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i;/Cou ntX第9頁(yè)共23頁(yè)數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案2一、 單選題（每小題2分，共8分）1、在一個(gè)長(zhǎng)度為n的順序線性表中順序查

12、找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為（）。AnB n/2C（n+1）/2D（n-1）/22、在一個(gè)單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入 一個(gè)s所指的結(jié)點(diǎn)，則執(zhí)行（）。As link=p f link;plink=s ；Bp lin k=s;s lin k=q;Cplin k=slink;s lin k=p;Dq lin k=s;s link =p;3、棧的插入和刪除操作在（）進(jìn)行。A棧頂B棧底C任意位置D指定位置4、由權(quán)值分別為11, 8, 6,2, 5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（

13、）A 24B 71C 48D53填空題（每空1分，共32分）1、 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、和四種。2、 一種抽象數(shù)據(jù)類型包括和個(gè)部分。3、 在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為ao.next，則該線性表為。605642387425437620廠data n ext0123456784、 在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為和。5、用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的，該循環(huán)隊(duì)列的最大長(zhǎng)度為 。6、當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用 表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用 表示。7、一

14、棵高度為 5 的二叉樹(shù)中最少含有 個(gè)結(jié)點(diǎn)，最多含有 個(gè)結(jié)點(diǎn)；一棵高度為 5 的理想平衡樹(shù)中，最少含有 個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為 ，通常它包含三個(gè)域：.曰曰-曰一是 ；二是 ；三是 。9、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的 和兩項(xiàng)數(shù)據(jù)。10、假定一棵樹(shù)的廣義表表示為 A（B（C，D（ E，F(xiàn)，G），H（I，J）， 則樹(shù) 中所 含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為 ,樹(shù)的度為, 結(jié)點(diǎn) H 的雙親結(jié)點(diǎn)為 ,孩子結(jié)點(diǎn)為 。11、在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 ,整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為 。12、在對(duì)m階的B_樹(shù)插入元素的過(guò)程中，每

15、向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉 子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于 個(gè)，則必須把它分裂為 個(gè)結(jié)點(diǎn)。運(yùn)算題（每小題 6 分，共 24 分）1、已知一組記錄的排序碼為（ 46， 79， 56， 38， 40， 80, 95， 24），寫(xiě)出對(duì) 其進(jìn)行快速排序的每一次劃分結(jié)果。第13頁(yè)共23頁(yè)2、一個(gè)線性表為 B= （12, 23, 45, 57, 20, 03, 78, 31, 15, 36）,設(shè)散列表為HT0.12，散列函數(shù)為H （key） = key % 13并用線性探查法解決沖 突，請(qǐng)畫(huà)出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。3、已知一棵二叉樹(shù)的前序遍歷的結(jié)

16、果序列是ABECKFGHIJ，中序遍歷的結(jié)果是 EBCDAFHIGJ，試寫(xiě)出這棵二叉樹(shù)的后序遍歷結(jié)果。4、已知一個(gè)圖的頂點(diǎn)集 V各邊集G如下：V = 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9；E = （0 , 1）,（0 , 4）,（ 1, 2）,（ 1 , 7）,（2 , 8）,（3 , 4）,（3 , 8）,（5 , 6）,（5 , 8）,（5 , 9）,（6 , 7）,（7 , 8）,（8 , 9）當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫(xiě)出從頂點(diǎn)V。出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次

17、序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí)四、閱讀算法，回答問(wèn)題（每小題 8分，共16分）1、假定從鍵盤(pán)上輸入一批整數(shù),依次為：78 63 45 30 91 34 - 1，請(qǐng) 寫(xiě)出輸出結(jié)果。# in elude < iostream.h># in elude < stdlib.h >const int staekmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;# include void“stack.h”main ( ) stack

18、a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” cout <<end1;該算法的輸出結(jié)果為：2、閱讀以下二叉樹(shù)操作算法，指出該算法的功能。Template <calss type > void BinTree <Type> ： unknown (BinTreeNode<Type>*t) BinTreeNode< Typ

19、e> *p =t, *temp;if (p!=NULL) temp = p leftchild; pf leftchild = p f rightchild; pfrightchild = temp; unknown(pfleftchild); undnown(pfrightchild); 該算法的功能是： 五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容(10 分)對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法 。int Binsch( ElemType A ,int low ,int high,KeyType K )if (low <= high)int mid = 1 if ( K=

20、= A mid .key ) return mid;else if ( K < Amid.key) return 2else return 3elsereturn 4六、編寫(xiě)算法( 10 分)即若原單鏈表中,a1 o編寫(xiě)算法， 將一個(gè)結(jié)點(diǎn)類型為 Lnode 的單鏈表按逆序鏈接， 存儲(chǔ)元素的次序?yàn)閍i,a-i, an,則逆序鏈接后變?yōu)?an, eVoid contrary (Lnode * & H L)第 i3 頁(yè) 共 23 頁(yè)試題2答案、單選題（每小題 2分，共8分）題號(hào)1234答案CDAB二、填空題（每空1分，共32分）1:集合、線性、樹(shù)、圖；2:數(shù)據(jù)描述、操作聲名；3：（38

21、, 56， 25， 60， 42， 74）;4： HLt next =NULL ; HL=HL 宀 next;5: 前一個(gè)位置；n-1;6: S.stack S.top;HSt data;7：531& 邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；9:索引值域、開(kāi)始位置域；10:10、3、3、B、I 和 J;11: O （log2n）、0（nlog2n）;12: m、 m - 1三、運(yùn)算題（每小題 6分，共24分）1、劃分次序劃分結(jié)果第一次3824 40 465680 9579第二次243840 4656809579第三次2438 40465680 9579第四次2438 404656809579第五

22、次2438 404656798095第六次2438 40465679 80952、012345678910111278150357452031233612查找成功的平均查找長(zhǎng)度：ASL succ=14/10= 1.44、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)0, 1 , 2, 8, 3, 4, 5, 6, 7, 90, 1 , 4 , 2 , 7 , 3 , 8 , 6 , 5 , 9鄰接表表示時(shí)0, 4, 3, 8, 9, 5, 6, 7, 1 , 20 , 4 , 1 , 3 , 7 , 2 , 8 , 6 , 9 , 5四、閱讀算法，回答問(wèn)題（每小題8分，共16分）3、此二叉樹(shù)的后序遍

23、歷結(jié)果是:EDCBIHJGFA1、 該算法的輸入結(jié)果是：34 91 30 45 63 782、該算法的功能是：交換二叉樹(shù)的左右子樹(shù)的遞歸算法。10 分)五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容(1 是：(low + high)/2;2 是： Binsch(A,low,mid - 1,K);3 是：Binsch(A,mid+1,high,K);4 是：-1;六、編寫(xiě)算法(10分)根據(jù)編程情況，酌情給分。Lnode *P=HL;HL=NULL;While (p!=null)Lno de*q=p;P=p t n ext;qf n ext=HL;HL=q;數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案3一、單項(xiàng)選擇題

24、1對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為()。(A)、正確性 (B).可行性 (C).健壯性 (D).輸入性2. 設(shè)S為C語(yǔ)言的語(yǔ)句,計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為()。for(i=n-1 ; i>=0 ; i-)for(j=0 ; j<i ; j+) S;(A)、n2(B). O(nlgn)(C). O(n)(D). O(n2)3折半查找法適用于()。(A)、有序順序表 (B)、有序單鏈表(C)、有序順序表和有序單鏈表都可以(D)、無(wú)限制4. 順序存儲(chǔ)結(jié)構(gòu)的優(yōu)勢(shì)是()。(A)、利于插入操作(B)、利于刪除操作(C)、利于順序訪問(wèn)(D)、利于隨

25、機(jī)訪問(wèn)5深度為k的完全二叉樹(shù)，其葉子結(jié)點(diǎn)必在第()層上。(A)、k-1(B)、k (C)、k-1 和 k ( D)、1 至 k6. 具有60個(gè)結(jié)點(diǎn)的二叉樹(shù)，其葉子結(jié)點(diǎn)有12個(gè)，則度過(guò)1的結(jié)點(diǎn)數(shù)為()(A )、11(B)、13( C)、48( D)、37、遍歷方法的推廣。7. 圖的 Depth-First Search(DFS)遍歷思想實(shí)際上是二叉樹(shù)(A)、先序 (B)、中序(C)、后序 (D)、層序&在下列鏈隊(duì)列 Q中，元素a出隊(duì)的操作序列為()Q(A)、p=Q.front->next; p->next= Q.front->next;第25頁(yè)共23頁(yè)(B )、p=Q.

26、front->next; Q.front->next=p->next;(C) 、p=Q.rear->next; p->next= Q.rear->next;(D) 、p=Q->next; Q->next=p->next;9. Huffman樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL等于()(A)、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和(B)、所有結(jié)點(diǎn)權(quán)值之和(C)、各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和(D)、根結(jié)點(diǎn)的值10. 線索二叉鏈表是利用()域存儲(chǔ)后繼結(jié)點(diǎn)的地址。(A)、Ichild( B)、data(C)、rchild( D)、root二、填空題1. 邏輯結(jié)構(gòu)決定了

27、算法的 ，而存儲(chǔ)結(jié)構(gòu)決定了算法的 。2棧和隊(duì)列都是一種 的線性表，棧的插入和刪除只能在 進(jìn)行。3. 線性表(ai,a 2,an)的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)單元的長(zhǎng)度為 L,元素a的存儲(chǔ)地址LOC(a)為4. 已知一雙向鏈表如下(指針域名為next和prior):p .e現(xiàn)將p所指的結(jié)點(diǎn)插入到 x和y結(jié)點(diǎn)之間，其操作步驟為： ; ; ;5. n個(gè)結(jié)點(diǎn)無(wú)向完全圖的的邊數(shù)為 ,n 個(gè)結(jié)點(diǎn)的生成樹(shù)的邊數(shù)為 。6. 已知一有向無(wú)環(huán)圖如下：7. 已知二叉樹(shù)的中序遍歷序列為BCA后序遍歷序列為 CBA則該二叉樹(shù)的先序遍歷序列為，層序遍歷序列為。三、應(yīng)用題1. 設(shè)散列函數(shù) H(k)=k % 13,設(shè)關(guān)鍵字系列為

28、22,12,24,6,45,7,8,13,21, 要求用線性探測(cè) 法處理沖突。(6分)(1) 構(gòu)造HASH表。(2) 分別求查找成功和不成功時(shí)的平均查找長(zhǎng)度。2. 給定表(19,14,22,15,20,21,56,10) . (8 分)(1) 按元素在表中的次序，建立一棵二叉排序樹(shù)(2) 對(duì)(1)中所建立的二叉排序樹(shù)進(jìn)行中序遍歷，寫(xiě)出遍歷序列。(3) 畫(huà)出對(duì)(2)中的遍歷序列進(jìn)行折半查找過(guò)程的判定樹(shù)。3.已知二個(gè)稀疏矩陣 A和B的壓縮存儲(chǔ)三元組表如下:ijV13-524625242-1529ABijV25233741352-9558寫(xiě)出A-B壓縮存儲(chǔ)的三兀組表。(5分)4.已知一維數(shù)組中的數(shù)據(jù)

29、為(18,12,25,53,18_),試寫(xiě)出插入排序(升序)過(guò)程。并指出A開(kāi)始的最小生成樹(shù)。(8分，要有過(guò)程)具有n個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？(5分)ABCDEFA651B653C572D15764E366F246(1 )求從頂點(diǎn)A開(kāi)始的最小生成樹(shù)。5.已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)（2）分別畫(huà)出以 A為起點(diǎn)的DFS生成樹(shù)和BFS生成樹(shù)。6.已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表:ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作（7分，要有過(guò)程）。（1）畫(huà)出對(duì)應(yīng)的Huffman樹(shù)。（2）計(jì)算帶權(quán)路徑長(zhǎng)度 WPL（3）求 A、B

30、 C、D、E、F 的 Huffman 編碼。7. 已知有如下的有向網(wǎng):求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用 Dijkstra算法，要有過(guò)程）。（6分）四、 設(shè)計(jì)題（30分，每題10分,用C語(yǔ)言寫(xiě)出算法，做在答題紙上）1. 已知線性表（a1,a 2, - ,a n）以順序存儲(chǔ)結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)，其類型定義如下：#define LIST_INIT_SIZEtypedef struct Elemtype *elem;int len gth;SqList;設(shè)計(jì)一個(gè)算法，刪除其元素值為x的結(jié)點(diǎn)雜度。其算法函數(shù)頭部如下：100/順序表初始分配容量/順序存儲(chǔ)空間基址/當(dāng)前長(zhǎng)度（存儲(chǔ)元素個(gè)數(shù)）（假若x是唯一的）。

31、并求出其算法的平均時(shí)間復(fù)S tatus ListDelete(Sqlist &L,Elemtype x) base2 設(shè)順序棧如左圖所示。 其中結(jié)點(diǎn)定義如下：typedef struct Elemtype *base; / 棧底指針Elemtype *top; / 棧頂指針 Stack;設(shè)計(jì)算法，將棧頂元素出棧并存入e中.3. 設(shè)二叉鏈樹(shù)的類型定義如下：typedef int Elemtype;typedef struct no deElemtype data; struct node *lchild, *rchild;Bi nN ode, *B in Tree;試寫(xiě)出求該二叉樹(shù)葉子結(jié)

32、點(diǎn)數(shù)的算法：S tatus Coun tLeaves(B in Tree &root, int &n)/n is the nu mber of leaves試題3答案一、選擇題(每題 1分)1. C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C二、填空題1 設(shè)計(jì)、實(shí)現(xiàn)2. 特殊、棧頂3. LOC(a1) +(i-1)*L4. p_>next=q_>next;q_>next->prior=p; q_>next=p;p_>prior=q;5. n(n-1)/2、n-16. ADCBFEG 、 ABCDEFFG7. ABC、ABC三、應(yīng)用題1.(1