數(shù)據(jù)結構 ( 第3次 )

《數(shù)據(jù)結構 ( 第3次 )》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

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

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

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

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

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