《數據結構》第二版嚴蔚敏課后習題作業(yè)參考答案(1-7章)

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

-

=1\*GB3①=2\*GB3②3假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為，，，，，，，。=1\*GB3①試為這8個字母設計赫夫曼編碼。=2\*GB3②試設計另一種由二進制表示的等長編碼方案。=3\*GB3③對于上述實例，比較兩種方案的優(yōu)缺點。答案：~=1\*GB3①先將概率放大100倍，以方便構造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則得到的哈夫曼編碼為：字母編號對應編碼出現頻率10002（00130104011·510061017110.8111=2\*GB3②等長編碼：字母編號！對應編碼出現頻率11010200…31000041001511-6100017018"1011(=3\*GB3③方案1的WPL＝2+++4+++5+=++=方案2的WPL＝3+++++++=3結論：哈夫曼編碼優(yōu)于等長二進制編碼!4已知下列字符A、B、C、D、E、F、G的權值分別為3、12、7、4、2、8，11，試填寫出其對應哈夫曼樹HT的存儲結構的初態(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）統計二叉樹的葉結點個數。[題目分析]如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點個數加上右子樹中葉子節(jié)點個數。[算法描述]intLeafNodeCount(BiTreeT){@ if(T==NULL) return0;擇題(1)~(5)：CBBBC(6)~(10):BABAA(11)~(15)：DCC(DD)B2．應用題（2）已知如圖所示的無向網，請給出：=1\*GB3①鄰接矩陣；=2\*GB3②鄰接表；》=3\*GB3③最小生成樹答案：=1\*GB3①]=2\*GB3②=3\*GB3③）（3）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。、…3.算法設計題（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．應用題假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題：=1\*GB3①畫出描述折半查找過程的判定樹；=2\*GB3②若查找元素54，需依次與哪些元素比較=3\*GB3③若查找元素90，需依次與哪些元素比較=4\*GB3④假定每個元素的查找概率相等，求查找成功時的平均查找長度。答案：}=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之前，需要統計每個元素的查找次數。判定樹的前3層共查找1＋2×2＋4×3=17次；[但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈在一棵空的二叉排序樹中依次插入關鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。 答案：12172111621?4913驗算方法：用中序遍歷應得到排序結果：2,4,7,9,11,12,13,16,17,21設哈希表的地址范圍為0～17，哈希函數為：H（key）=key%16。用線性探測法處理沖突，輸入關鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構造哈希表，試回答下列問題：=1\*GB3①畫出哈希表的示意圖；=2\*GB3②若查找關鍵字63，需要依次與哪些關鍵字進行比較=3\*GB3③若查找關鍵字60，需要依次與哪些關鍵字比較=4\*GB3④假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。答案：~=1\*GB3①要求寫出計算過程哈希表表如下：01234。56789101112…1314151617321763@49244010\30314647=2\*GB3②查找63,首先要與H(63)=63%16=15號單元內容比較，即63與31比較,不匹配;然后順移，與46,47,32,17,63相比，一共比較了6次=3\*GB3③查找60,首先要與H(60)=60%16=12號單元內容比較，但因為12號單元為空（應當有空標記），所以應當只比較這一次即可。=4\*GB3④ASL=（6＋2＋3×3+6）/11＝23/11設有一組關鍵字（9，01，23，14，55，20，84，27），采用哈希函數：H（key）=key%7，表長為10，用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。限定di=12,22,…k2(k<=m/2)答案：要求寫出計算過程散列地址0123456789關鍵字14192384275520

比較次數11123412

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