數(shù)據(jù)結(jié)構(gòu)應(yīng)用題練習(xí).doc

1、假設(shè)一棵二叉樹的層序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,請畫出該樹。21、有一個(gè)完全二叉樹按層次順序存放在一維數(shù)組中，如下所示： 請指出結(jié)點(diǎn)P的父結(jié)點(diǎn)，左子女，右子女。3、給出下列二叉樹的先序序列。4、已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài) （2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。 ABMFD(3)CEMHG (1) (2)1、已知一棵二叉樹的前序序列為：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。i. 寫出該二叉樹的后序序列；ii. 畫出該二叉樹；iii. 求該二叉樹的高度(假定空樹的高度為1)和度為2、度為1、及度為0的結(jié)點(diǎn)個(gè)數(shù)。該二叉樹的后序序列為：J,G,D,H,E,B,K,L,I,F,C,A。該二叉樹的形式如圖所示：ABJKIFCGEDLH該二叉樹高度為：5。度為2的結(jié)點(diǎn)的個(gè)數(shù)為：3。度為1的結(jié)點(diǎn)的個(gè)數(shù)為：5。度為0的結(jié)點(diǎn)個(gè)數(shù)為：4。5、試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹，并計(jì)算哈夫曼樹的帶權(quán)路徑長度。答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=696、已知權(quán)值集合為5,7,2,3,6,9，要求給出哈夫曼樹，并計(jì)算帶權(quán)路徑長度WPL。答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79（3） 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。 試設(shè)計(jì)另一種由二進(jìn)制表示的等長編碼方案。 對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼2應(yīng)用題（1）已知如圖6.27所示的有向圖，請給出： 每個(gè)頂點(diǎn)的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 圖6.27 有向圖 2 AOE網(wǎng)G如下所示，求關(guān)鍵路徑。（要求標(biāo)明每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，并畫出關(guān)鍵路徑）答案：(1)最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間： (2)關(guān)鍵路徑： （2）已知如圖6.28所示的無向網(wǎng)，請給出： 鄰接矩陣； 鄰接表； 最小生成樹圖6.28 無向網(wǎng) ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6（3）已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖6.29 鄰接矩陣（2）根據(jù)prim算法，求圖G從頂點(diǎn)1出發(fā)的最小生成樹，要求表示出其每一步生成過程。（用圖或者表的方式均可）。答案：(1)廣度優(yōu)先遍歷序列：1; 2, 3, 4; 5; 6 (2)最小生成樹（prim算法）V1V5V4V6V761V2V8V561. 對下面的有向圖，從頂點(diǎn)V1開始進(jìn)行遍歷，試畫出遍歷得到的DFS生成森林和BFS生成森林。遍歷得到的DFS生成森林和BFS生成森林如下圖：V1V5V4V6V761V2V8V56DFS生成森林V1V5V4V6V761V2V8V56BFS生成森林（5）設(shè)哈希表的地址范圍為017，哈希函數(shù)為：H（key）=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問題： 畫出哈希表的示意圖； 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？ 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？ 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因?yàn)?2號單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6233+6）23/11設(shè)散列表的長度為m=13，散列函數(shù)為H(k)=k MOD m，給定的關(guān)鍵碼序列為19，14，23，1，68，20，84，27，55，11，13，7，試寫出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。答案：表形態(tài)：（2）在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。 127 17 2 11 16 21 4 9 13驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，21（3）已知如下所示長度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。 若對表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長度。 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。解： 堆排序第一步,形成初始大根堆（詳細(xì)過程略），第二步做堆排序。1221620103016*28618302816102016*182126初始排序 不是大根堆 形成初始大根堆1228162102016*18630282016101216*182306交換1與10對象 從1到9重新形成堆620162101216*182830201816101216*623028交換1與9對象 從1到8重新形成堆2181620101216*6283018121610216*12203028交換1與8對象 從1到7重新形成堆16*121620102186283016*1216102186203028交換1與7對象 從1到6重新形成堆1012162016*2186283016121016*2186203028交換1與6對象 從1到5重新形成堆612102016*2181628301261016*21816203028交換1與5對象 從1到4重新形成堆126102016*1218162830106216*121816203028交換1與4對象 從1到3重新形成堆26102016*1218162830621016*121816203028交換1與3對象 從1到2重新形成堆26102016*1218162830261016*121816203028交換1與2對象 得到結(jié)果90、請畫出下圖中的極大連通子圖。14563291、對于如下圖請畫出其用prim和kruskal兩種不同算法生成最小生成樹的各條邊的并入順序。畫出最小生成樹。并寫出廣度優(yōu)先和深度優(yōu)先的結(jié)點(diǎn)遍歷順序。20143256121233106578492、什么是靜態(tài)查找，什么時(shí)動(dòng)態(tài)查找，什么叫平均查找長度。93、用序列（46，88，45，39，70，58，101，10，66，34）建立一個(gè)二叉排序樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。94、已知一個(gè)線性表（38，25，74，63，52，48），假定采用h(k)=k%7計(jì)算散列地址進(jìn)行散列存儲，若引用線性探測的開放地址法解決沖突，則在該散列表上進(jìn)行檢索的平均檢索長度為多少，若利用連地址法處理沖突，則在該散列表上進(jìn)行檢索的平均查找長度為多少？設(shè)地址空間為9。請畫出算列表。96、已知長度為12的表：（Jan , Fed , Mar , Apr , May , Jun , Aug , Sep , Oct , Nov , Dec）按表中元素的順序，依次插入一棵初始為空的二叉排序樹，畫出插完之后的二叉排序樹，并求其在等概率情況下，查找成功的平均查找長度。98、有散