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

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

2、前序?yàn)锳BDEGCF，中序?yàn)镈BGEACF，則后序一定是 。10. 在哈希文件中，處理沖突的方法通常有_、_ 、_和_四種。二、算法設(shè)計(jì)題（本大題共20分，共 2 小題，每小題 10 分）1. 編寫一個(gè)算法將一個(gè)頭結(jié)點(diǎn)指針為pa的單鏈表A分解成兩個(gè)單鏈表A和B，其頭結(jié)點(diǎn)指針?lè)謩e為pa和pb，使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素，而鏈表B中含有原鏈表A中序號(hào)為偶數(shù)的元素，且保持原來(lái)的相對(duì)順序。2. 設(shè)稀疏矩陣Mmxn中有t個(gè)非零元素，用三元組順序表的方式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算矩陣M的轉(zhuǎn)置矩陣N，要求轉(zhuǎn)置算法的時(shí)間復(fù)雜度為O(n+t)。三、簡(jiǎn)答題（本大題共20分，共 4 小題，每小題 5

3、 分）1. 假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.  (1)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。  (2)若用這三位二進(jìn)制數(shù)(07)對(duì)這8個(gè)字母進(jìn)行等長(zhǎng)編碼，則哈夫曼編碼的平均碼長(zhǎng)是等長(zhǎng)編碼的百分之幾?它使電文總長(zhǎng)平均壓縮多少?2. 若二叉樹(shù)中各結(jié)點(diǎn)的值均不相同，則由二叉樹(shù)的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹(shù)，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹(shù)。 (1)已知一棵二叉樹(shù)的前序序列和中序序列

4、分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫出此二叉樹(shù)。 (2)已知一棵二叉樹(shù)的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫出此二叉樹(shù)。 (3)已知一棵二叉樹(shù)的前序序列和后序序列分別為AB和BA，請(qǐng)畫出這兩棵不同的二叉樹(shù)。3.   試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。 4. 給定集合15,3,14,2,6,9,16,17(1)（3分）用表示外部結(jié)點(diǎn)，用表示內(nèi)部結(jié)點(diǎn)，構(gòu)造相應(yīng)的huffman樹(shù)：(2) (2分)計(jì)算它的帶權(quán)路徑長(zhǎng)度：(3)（2分)寫出它的huffman編碼：(4)（3分)huffman編碼常用來(lái)譯碼，請(qǐng)用語(yǔ)言敘

5、述寫出其譯碼的過(guò)程。四、程序設(shè)計(jì)題（本大題共30分，共 2 小題，每小題 15 分）1. 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出求二叉樹(shù)葉子總數(shù)的算法 2. 設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,a1,.an-1)，重寫順序表上實(shí)現(xiàn)的插入算法：InsertList 答案：一、填空題（30分，共 10 題，每小題 3 分）1. 參考答案：棧頂，棧底解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：根結(jié)點(diǎn)，左子樹(shù)，右子樹(shù)解題方案：評(píng)分標(biāo)準(zhǔn)：3. 參考答案：普里姆（prim）算法和克魯斯卡爾（Kruskal）算法解題方案：評(píng)分標(biāo)準(zhǔn)：4. 參考答案：行號(hào)、列號(hào)、元素值解題方案：評(píng)分標(biāo)準(zhǔn)：5. 參考答案：免去查找過(guò)程中每一步都要檢測(cè)整

6、個(gè)表是否查找完畢，提高了查找效率。解題方案：評(píng)分標(biāo)準(zhǔn)：6. 參考答案：(1)活動(dòng)（2）活動(dòng)間的優(yōu)先關(guān)系（3）事件（4）活動(dòng)邊上的權(quán)代表活動(dòng)持續(xù)時(shí)間解題方案：評(píng)分標(biāo)準(zhǔn)：7. 參考答案：q=p->next; p->next=q->next; free(q);解題方案：評(píng)分標(biāo)準(zhǔn)：8. 參考答案：n1+n2=0+ n2= n0-1=31，26-1 =32解題方案：評(píng)分標(biāo)準(zhǔn)：9. 參考答案：DGEBFCA解題方案：評(píng)分標(biāo)準(zhǔn)：10. 參考答案：開(kāi)放地址法、再哈希法、鏈地址法、建立一個(gè)公共溢出區(qū)解題方案：評(píng)分標(biāo)準(zhǔn)：二、算法設(shè)計(jì)題（20分，共 2 題，每小題 10 分）1. 參考答案：將單鏈

7、表A中的所有偶數(shù)序號(hào)的結(jié)點(diǎn)刪除，并在刪除時(shí)把這些結(jié)點(diǎn)鏈接起來(lái)構(gòu)成單鏈表B。算法如下： #include<stdio.h>#include<malloc.h>typedef int ElemType;typedef struct LNodeElemType data; /數(shù)據(jù)域struct LNode *next; /指針域 LNode,*LinkList; void divide(LinkList&pa, LinkList&pb) pb=(LNode *)malloc(sizeof(LNode *); pb->next=NULL; r=p

8、b; p=pa->next; while(p!=NULL && p->next!=NULL) q=p->next; if(q!=NULL) p->next=q->next; r->next=q; r=q; p=p->next; r->next=NULL; 解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：轉(zhuǎn)置可按轉(zhuǎn)置矩陣的三元組表中的元素順序進(jìn)行，即按稀疏矩陣的列序。這種方法時(shí)間復(fù)雜度是O(n*t)，當(dāng)t和m*n同量級(jí)時(shí)，時(shí)間復(fù)雜度為O(n3)。另一種轉(zhuǎn)置方法稱作快速轉(zhuǎn)置，使時(shí)間復(fù)雜度降為O(m*n)。需要求出每列非零元素個(gè)數(shù)和每列第一個(gè)非零元

9、素在轉(zhuǎn)置矩陣三元組表中的位置，因此設(shè)置了兩個(gè)附加向量。下面分別給出兩個(gè)算法。TSMatrixTransMatrix(TSMatrixM,TSMatrix N)采用三元組表方式存儲(chǔ)，按列序?qū)崿F(xiàn)矩陣的轉(zhuǎn)置N.m=M.n; N.n=M.m; N.len=M.len; 行數(shù)、列數(shù)和非零元素個(gè)數(shù) if(N.len)ql; 設(shè)置N中第一個(gè)非零元素從下標(biāo)1開(kāi)始存儲(chǔ)for(j1;jM.n;j+) 按列，共M.n列 for(p1;pM.len; +p) 在M.len個(gè)元素中查找 if(M.datap.col=j) 轉(zhuǎn)置N.dataq.row=M.datap.col;N.dataq.col=M.datap.row

10、;N.dataq.e=M.datap.e; q+; return N;TransMatrixTSMatrixFastTransMatrix(TSMatrix M, TSMatrix N)三元組表上實(shí)現(xiàn)矩陣的快速轉(zhuǎn)置的算法N.m=M.n; N.n=M.m; N.len=M.len;if(M.len) for(j=1;j<=M.n;j+) numbj=0; 矩陣M每一列非零元初始化為零 for(t=1;t<=M.len;t+)numbM.datat.col+;求矩陣M每一列得非零元個(gè)數(shù)pos1=1; 第1列第一個(gè)非零元在轉(zhuǎn)置后的三元組中下標(biāo)是1 for(j=2;j<=M.n;j+

11、) 求M.data第j列第一個(gè)非零元在N.data中的序號(hào)poscol=poscol-1+numcol-1; for(p=1;p<=M.len;p+)求轉(zhuǎn)置矩陣N的三元組表 j=M.datap.col; q=posj;N.dataq.row=M.datap.col; N.dataq.col=M.datap.row;N.dataq.e=M.datap.e; posj+; 同列下一非零元素位置 return N;解題方案：評(píng)分標(biāo)準(zhǔn)：三、簡(jiǎn)答題（20分，共 4 題，每小題 5 分）1. 參考答案：（1）哈夫曼編碼  P_47E42CBBE4BEF0B3804EEA501687A04A

12、    根據(jù)上圖可得編碼表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000（2）用三位二進(jìn)行數(shù)進(jìn)行的等長(zhǎng)編碼平均長(zhǎng)度為3，而根據(jù)哈夫曼樹(shù)編碼的平均碼長(zhǎng)為：       4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61       2.61/3=0.87=87%其平均碼長(zhǎng)是等長(zhǎng)碼的87%，所以平均壓縮率為13%。解題方案：評(píng)分標(biāo)準(zhǔn)：2.

13、 參考答案：(1)已知二叉樹(shù)的前序序列為ABDGHCEFI和中序序列GDHBAECIF，則可以根據(jù)前序序列找到根結(jié)點(diǎn)為A，由此，通過(guò)中序序列可知它的兩棵子樹(shù)包分別含有GDHB和ECIF結(jié)點(diǎn)，又由前序序列可知B和C分別為兩棵子樹(shù)的根結(jié)點(diǎn).以此類推可畫出所有結(jié)點(diǎn)： A / B C / / D EF / /G H I  (2)以同樣的方法可畫出該二叉樹(shù)： A / B F C G / D E H  (3)這兩棵不同的二叉樹(shù)為： A A / B B 解題方案：評(píng)分標(biāo)準(zhǔn)：3. 參考答案：例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)生的身高、體重等各項(xiàng)體檢

14、信息。這張登記表中，每個(gè)學(xué)生的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，身高和體重等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。這個(gè)表中的數(shù)據(jù)如何存儲(chǔ)到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢? 即用一片連續(xù)的內(nèi)存單元來(lái)存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢? 這就是存儲(chǔ)結(jié)構(gòu)的問(wèn)題。在這個(gè)表的某種存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對(duì)這張表中的記錄進(jìn)行查詢，

15、修改，刪除等操作。對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問(wèn)題了。解題方案：評(píng)分標(biāo)準(zhǔn)：4. 參考答案：（1）P_F438585CD9EAD09DED967D20E23446F3（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229（3）編碼為：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01(4) 常用哈夫曼樹(shù)為通訊用的字符編碼，本題中集合的數(shù)值解釋為字符發(fā)生的頻率（次數(shù)）。由哈夫曼樹(shù)構(gòu)造出哈夫曼編碼。譯碼時(shí)，進(jìn)行編碼的“匹配”，即從左往右掃描對(duì)方發(fā)來(lái)的“編碼串”，用字

16、符編碼去匹配，得到原來(lái)的元素（本題中的數(shù)）。解題方案：評(píng)分標(biāo)準(zhǔn)：四、程序設(shè)計(jì)題（30分，共 2 題，每小題 15 分）1. 參考答案：typedef char DataType;/定義DataType類型typedefstruct node DataType data; struct node *lchild, *rchild;/左右孩子子樹(shù)BinTNode; /結(jié)點(diǎn)類型typedefBinTNode *BinTree ;/二叉樹(shù)類型 int Leaf(BinTree T) /算葉子數(shù)if(T) if (T->lchild=NULL)&&(T->rchild=NUL

17、L) return 1; else return Leaf(T->lchild)+Node(T->rchild); else return 0; 解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：#define ListSize 100 / 假定表空間大小為100typedef int DataType;/假定DataType的類型為int型typedef struct    DataType dataListSize;/ 向量data用于存放表結(jié)點(diǎn)    int length; / 當(dāng)前的表長(zhǎng)度  Seqlist;  /以上為定義表結(jié)構(gòu)void InsertList ( Seqlist *L, Datatype x, int i)/將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上，即插入的合法位置為：0<=i<=L->lengthint j;if ( i < 0 | i > L -> length )&#