《數(shù)據(jù)結(jié)構(gòu)》第二版嚴(yán)蔚敏課后習(xí)題作業(yè)參考答案(1-7章)

第1章4．答案：（1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類型來(lái)描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言的指針類型來(lái)描述。5.選擇題(1)~(6)：CCBDDA\6．（1）O(1)（2）O(m*n)（3）O(n2)（4）O(log3n)（5）O(n2)（6）O()（第2章1．選擇題（1）~（5）：BABAD（6）~（10）：BCABD（11）~（15）：CDDAC\2．算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。[題目分析]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個(gè)表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無(wú)重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){法設(shè)計(jì)題（1）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫雙棧初始化，判斷棧空、棧滿、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedefstruct]{inttop[2],bot[2]; 第5章，1．選擇題（1）~（5）：ADDCA（6）~（10）：CCBDC（11）~（15）：BCACA2.應(yīng)用題2設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC=1\*GB3①畫出這棵二叉樹。=2\*GB3②畫出這棵二叉樹的后序線索樹。=3\*GB3③將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。答案：`ABABFD~=3\*GB3③CE*HG

-

=1\*GB3①=2\*GB3②3假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為，，，，，，，。=1\*GB3①試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。=2\*GB3②試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。=3\*GB3③對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。答案：~=1\*GB3①先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則得到的哈夫曼編碼為：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10002（00130104011·510061017110.8111=2\*GB3②等長(zhǎng)編碼：字母編號(hào)！對(duì)應(yīng)編碼出現(xiàn)頻率11010200…31000041001511-6100017018"1011(=3\*GB3③方案1的WPL＝2+++4+++5+=++=方案2的WPL＝3+++++++=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼!4已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對(duì)應(yīng)哈夫曼樹HT的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài):

weightparentlchild!rchild13000212|00037000】44000520。00680007）110008

00:09

00010

*00011

000(12

00013

0：00!）

終態(tài)：

weightparent&lchildrchild138002|12120037100？04490052（800681000`7111100859《5199114810~1512361120139{71227132101347《01112|（3．算法題（1）統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)。[題目分析]如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時(shí)為空，返回左子樹中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹中葉子節(jié)點(diǎn)個(gè)數(shù)。[算法描述]intLeafNodeCount(BiTreeT){@ if(T==NULL) return0;擇題(1)~(5)：CBBBC(6)~(10):BABAA(11)~(15)：DCC(DD)B2．應(yīng)用題（2）已知如圖所示的無(wú)向網(wǎng)，請(qǐng)給出：=1\*GB3①鄰接矩陣；=2\*GB3②鄰接表；》=3\*GB3③最小生成樹答案：=1\*GB3①]=2\*GB3②=3\*GB3③）（3）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。、…3.算法設(shè)計(jì)題（2）VoidDFSn(ALGraphG,intv){ata;irsttarc;p!=NULL;p=p->nextarc){ w=p->adjvex;if(!visited[w]&&w!=GetTop(s))Push(s,w);擇題(1)~(5)：CDCAB(6)~(10):CCCDC(11)~(15)：BCADA《2．應(yīng)用題假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：=1\*GB3①畫出描述折半查找過(guò)程的判定樹；=2\*GB3②若查找元素54，需依次與哪些元素比較=3\*GB3③若查找元素90，需依次與哪些元素比較=4\*GB3④假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。答案：}=1\*GB3①先畫出判定樹如下（注：mid=(1+12)/2=6）：30563374287424547295=2\*GB3②查找元素54，需依次與30,63,42,54元素比較；=3\*GB3③查找元素90，需依次與30,63,87,95元素比較；=4\*GB3④求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1＋2×2＋4×3=17次；[但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉排序樹。 答案：12172111621?4913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17,21設(shè)哈希表的地址范圍為0～17，哈希函數(shù)為：H（key）=key%16。用線性探測(cè)法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問(wèn)題：=1\*GB3①畫出哈希表的示意圖；=2\*GB3②若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較=3\*GB3③若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較=4\*GB3④假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。答案：~=1\*GB3①要求寫出計(jì)算過(guò)程哈希表表如下：01234。56789101112…1314151617321763@49244010\30314647=2\*GB3②查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63與31比較,不匹配;然后順移，與46,47,32,17,63相比，一共比較了6次=3\*GB3③查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。=4\*GB3④ASL=（6＋2＋3×3+6）/11＝23/11設(shè)有一組關(guān)鍵字（9，01，23，14，55，20，84，27），采用哈希函數(shù)：H（key）=key%7，表長(zhǎng)為10，用開放地址法的二次探測(cè)法處理沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。限定di=12,22,…k2(k<=m/2)答案：要求寫出計(jì)算過(guò)程散列地址0123456789關(guān)鍵字14192384275520

比較次數(shù)11123412

平均查找長(zhǎng)度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）H2=（6+22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。3．算法設(shè)計(jì)題（1）試寫