數(shù)據(jù)結(jié)構(gòu) ( 第3次 )

《數(shù)據(jù)結(jié)構(gòu) ( 第3次 )》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、第3次作業(yè)一、填空題（本大題共30分，共10小題，每小題3分）1.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為______。不允許插入和刪除運算的一端稱為______。2.二叉樹由，，三個基本單元組成。3.?構(gòu)造連通網(wǎng)最小生成樹的兩個典型算法是______。4.在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的________、________和________三項。5.直接插入排序用監(jiān)視哨的作用是_______。6.AOV網(wǎng)中,結(jié)點表示______,邊表示______。AOE網(wǎng)中,結(jié)點表示______,邊表示______。7.已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)

2、點的語句是________。8.一棵深度為6的滿二叉樹有______個分支結(jié)點和______個葉子。9.已知二叉樹前序為ABDEGCF，中序為DBGEACF，則后序一定是。10.在哈希文件中，處理沖突的方法通常有______、______、______和______四種。二、算法設(shè)計題（本大題共20分，共2小題，每小題10分）1.編寫一個算法將一個頭結(jié)點指針為pa的單鏈表A分解成兩個單鏈表A和B，其頭結(jié)點指針分別為pa和pb，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素，而鏈表B中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序。2.設(shè)稀疏矩陣Mmxn中有t個非零元素，用三元組順序表的

3、方式存儲。請設(shè)計一個算法，計算矩陣M的轉(zhuǎn)置矩陣N，要求轉(zhuǎn)置算法的時間復(fù)雜度為O(n+t)。三、簡答題（本大題共20分，共4小題，每小題5分）1.假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.?(1)為這8個字母設(shè)計哈夫曼編碼。?(2)若用這三位二進制數(shù)(0…7)對這8個字母進行等長編碼，則哈夫曼編碼的平均碼長是等長編碼的百分之幾?它使電文總長平均壓縮多少?2.若二叉樹中各結(jié)點的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列

4、均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。(2)已知一棵二叉樹的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請畫出這兩棵不同的二叉樹。3.?試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。4.給定集合{15,3,14,2,6,9,16,17}(1)（3分）用□表示外部結(jié)點，用○表示內(nèi)部結(jié)點，構(gòu)造相應(yīng)的huffman樹：(2)(2分)計算它的

5、帶權(quán)路徑長度：(3)（2分)寫出它的huffman編碼：(4)（3分)huffman編碼常用來譯碼，請用語言敘述寫出其譯碼的過程。四、程序設(shè)計題（本大題共30分，共2小題，每小題15分）1.以二叉鏈表為存儲結(jié)構(gòu)，寫出求二叉樹葉子總數(shù)的算法2.設(shè)線性表的n個結(jié)點定義為(a0,a1,...an-1)，重寫順序表上實現(xiàn)的插入算法：InsertList答案：一、填空題（30分，共10題，每小題3分）1.參考答案：棧頂，棧底解題方案：評分標(biāo)準(zhǔn)：2.參考答案：根結(jié)點，左子樹，右子樹解題方案：評分標(biāo)準(zhǔn)：3.參考答案：普里姆（prim）算法和克魯斯卡爾（Kruskal）算法解題方案：評分標(biāo)準(zhǔn)：4.參考答

6、案：行號、列號、元素值解題方案：評分標(biāo)準(zhǔn)：5.參考答案：免去查找過程中每一步都要檢測整個表是否查找完畢，提高了查找效率。解題方案：評分標(biāo)準(zhǔn)：6.參考答案：(1)活動（2）活動間的優(yōu)先關(guān)系（3）事件（4）活動邊上的權(quán)代表活動持續(xù)時間解題方案：評分標(biāo)準(zhǔn)：7.參考答案：q=p->next;p->next=q->next;free(q);解題方案：評分標(biāo)準(zhǔn)：8.參考答案：n1+n2=0+n2=n0-1=31，26-1=32解題方案：評分標(biāo)準(zhǔn)：9.參考答案：DGEBFCA解題方案：評分標(biāo)準(zhǔn)：10.參考答案：開放地址法、再哈希法、鏈地址法、建立一個公共溢出區(qū)解題方案：評分標(biāo)準(zhǔn)：二、算法設(shè)計題（20分

7、，共2題，每小題10分）1.參考答案：將單鏈表A中的所有偶數(shù)序號的結(jié)點刪除，并在刪除時把這些結(jié)點鏈接起來構(gòu)成單鏈表B。算法如下：#include#includetypedefintElemType;typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLNode*next;//指針域}LNode,*LinkList;?voiddivide(LinkList&pa,