北林?jǐn)?shù)據(jù)結(jié)構(gòu)期末考試(四)應(yīng)用題

1、數(shù)據(jù)結(jié)構(gòu)應(yīng)用題天涯古巷 出品第三章題型一：表達式求值按照四則運算加(+)、減(-)、乘(* )、除(/ )和冪運算(勺優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A-BX C/D+EAF解：BC=G G/D=H A-H=l EAF=J l+J=K步驟OPTR 棧OPND 棧輸入字符主要操作1#A-B*C/D+EAF#PUSH(OPND,A)2#A-B*C/D+EAF#PUSH(OPTR,-)3#-AB*C/D+EAF#PUSH(OPND,B)4#-A B*C/D+EAF#PUSH(OPTR,*)5#-*A BC/D+EAF#PUSH(OPND,C)6#-*A B C

2、/D+EAF#Operate(B,*,C)7#-A G/D+EAF#PUSH(OPTR,/)8#-/A GD+EAF#PUSH(OPND,D)9#-/A G D+EAF#Operate(G,/,D)10#-A H+EAF#Operate(A,-,H)11#I+EAF#PUSH(OPTR,+)12#+IEAF#PUSH(OPND,E)13#+I EAF#PUSH(OPTR,a)14#+aI EF#PUSH(OPND,F)15#+aI E F#Operate(E,A,F)16#+I J#Operate(I,+,J)17#K#RETURN題型二：漢諾塔時間復(fù)雜度的分析及證明漢諾塔問題的遞歸算法的時間

3、復(fù)雜度是什么？請給岀答案并且給予證明 解：時間復(fù)雜度T(n)=0(2 )，證明如下已知：f(1)=1 , f(n)=2f(n-1)+1所以：f(n)+1=2(f(n-1)+1)f(n)= 2 n -1(2 n -1為至少執(zhí)行移動操作的次數(shù))nT(n)=O(2)故：得證第四章題型一：數(shù)組地址的計算設(shè)有二維數(shù)組 A(6 8)，每個元素占6字節(jié)存儲，順序存放，A 的起地址為1000,計算:(1) 數(shù)組 A的體積(即存儲量)(2) 數(shù)組的最后一個元素(3) 按行優(yōu)先存放時，元素(4) 按列優(yōu)先存放時，元素A57的起始地址；A14的起始地址;A47的起始地址。第五章題型一：由二叉樹的中序遍歷和前(后)序

4、遍歷，畫岀該二叉樹1、給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：A B D F C E G H ; 中序遍歷序列：B F D A G E H CB的前序遍歷序列和中序遍歷序列求二叉樹2、試寫岀如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的 結(jié)點序列。KB的思想方法。題型二：哈夫曼樹的構(gòu)造（畫樹、計算WPL初態(tài)和終態(tài)表），設(shè)計哈夫曼編碼1、假設(shè)用于通信的電文僅由8個字母組成， 字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這 8個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方

5、案的優(yōu)缺點。答案：方案1;哈夫曼編碼先將概率放大 100倍，以方便構(gòu)造哈夫曼樹。w=7,19,2,6,32,3,21,10 ，按哈夫曼規(guī)則:【(2,3)，6, (7,10)】,19, 21,3223字母編號對應(yīng)編碼出現(xiàn)頻率j111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案比較:字母編號對應(yīng)編碼出現(xiàn)頻率110000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06

6、+0.10)+5*(0.02+0.03)=1.44+0.92+0.25=2.61方案2WPIl3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼2、已知下列字符 A B C DE、F、G的權(quán)值分別為3、12、7、4、2、8,11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：終態(tài):初態(tài):weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000weightparentIchildrchild1

7、3800212120037100044900528006810007111100859519911481015123611201397122713210134701112題型三：利用二叉樹的性質(zhì)對某些問題進行證明 對于那些所有非葉子結(jié)點均含有左右子數(shù)的二叉樹：(1) 試問：有 n個葉子結(jié)點的樹中共有多少個結(jié)點？n(2) 試證明：2-(li-1) = 1，其中n為葉子結(jié)點的個數(shù)，|i表示第i個葉子結(jié)點所在的層次(設(shè)根節(jié)點所在層次為1) o解：(1)總結(jié)點數(shù)為1+2口，其中ni為非葉子結(jié)點數(shù)，則葉子結(jié)點數(shù)為n = ni +1，所以總結(jié)點數(shù)為2n - 1 o(2)用歸納法證明。i=1，說明二叉樹只有

8、一個葉子結(jié)點，則整棵樹只有一個根結(jié)點，|1 = 1,2-(l1-1) =1,結(jié)論成立。設(shè)有 n 個葉子結(jié)點時也成立，即2-(l1-1)+2-(l2-1)+. + 2-(lp-1)+.+ 2-(ln+1) =1,現(xiàn)假設(shè)增加一個葉子結(jié)點，這意味著在某葉子結(jié)點p上新生兩個葉子結(jié)點，而結(jié)點p則成為非葉子結(jié)點，可見，總結(jié)點數(shù)增2,葉子結(jié)點數(shù)增1。此時，所有葉子結(jié)點是原結(jié)點除去p,然后加上兩個深度為lp +1的新葉子結(jié)點，由此，-(l1-1)- (l2- 1)-(lp-1-1)-(lp + 1-1)- (ln +1)-(lp + 1-1)-dp1)2 + 2 +. + 2 + 2 +. + 2 + 2 +

9、2-(l1-1)-(l2-1)-山-1)-(ln+1)=2 +2 +. + 2 +.+ 2 =1則當(dāng)i=n+1時，也成立，由此即得到證明。0）連犧13 4 5(.2、已知如圖 6.33所示的無向網(wǎng)，請給出: 鄰接矩陣； 鄰接表； 最小生成樹答案:第六章題型一：給定圖的邏輯結(jié)構(gòu)，畫岀鄰接矩陣和鄰接表（或反過來考）1已知圖所示的有向圖，請給出: 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。?43COCOCOCOCO?,?4CO559COCOCO ?35CO5COCOCO5?s55CO7654?s9CO7CO3COCO?COCO63CO2CO?OOCOCO5CO2CO6?OCO54COC

10、O6CO?答案：b4a4a3b5b9d6d5TTTTTTTTTTTTc3c5b5c5d7e3f2TTTTTTd5d5e7f3g2h6TTTZd5丄Tg5h4題型二：根據(jù)圖的邏輯結(jié)構(gòu)或存儲結(jié)構(gòu)，寫岀深度、廣度優(yōu)先搜索遍歷結(jié)果（根據(jù)邏輯結(jié)構(gòu)寫是唯一的，根據(jù)存儲結(jié)構(gòu)寫不唯一）已知圖的鄰接矩陣如圖所示。試分別畫岀自頂點 1岀發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。lj()tt10 0 0(j(I(III (.110()0 0(1fl00 (t 0答案：深度優(yōu)先生成樹廣度優(yōu)先生成樹題型三：根據(jù)圖的邏輯結(jié)構(gòu)填寫最短路徑求解過程表，畫岀最小生成樹（計算權(quán)值和），寫岀拓?fù)渑判蚪Y(jié)果有向網(wǎng)如圖所示，試用迪

11、杰斯特拉算法求岀從頂點a到其他各頂點間的最短路徑，完成下表答案: 終點i=1i=2i=3i=4i=5i=6b1515151515(a,b)(a,b)(a,b)(a,b)b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)eoo1010.(a,c,e)(a,c,e)foo6gcooo161614(a,c,f,g)(a,c,f,g)(a,c,f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第七章題型一：折半查找過程，畫判定樹，計算ASL假定對有序表：(3, 4,5,7,24, 30

12、, 42,54,63,72,87,95)進行折半查找，試回答下列問題: 畫出描述折半查找過程的判定樹； 若查找元素 54,需依次與哪些元素比較？ 若查找元素 90,需依次與哪些元素比較？ 假定每個元素的查找概率相等，求查找成功時的平均查找長度答案： 先畫出判定樹如下(注：mid= ?(1+12)/2?=6):305374242454 72 查找元素 54,需依次與30, 63, 42, 54元素比較； 查找元素 90,需依次與30, 63,87, 95元素比較;3 層共查找 1 + 2X2+4X3=17 求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前次；但最后一層未滿，不能用8X4,只能

13、用 5X4=20次,所以 ASL=1/12 (17+20)= 37/12 3.08題型二：二叉排序樹的創(chuàng)建，查找，計算ASL已知如下所示長度為12 的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov,De 試按表中元素的順序依次插入一棵初始為空的二叉排序樹,樹，并求其在等概率的情況下查找成功的平均查找長度。畫岀插入完成之后的二叉排序 若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度答案:(1)求得的二更排序樹如下圖所示,在尊槪率情況下查找成功的平均查找長度為ASL = 1(1

14、X1 + 2X2 + 3X3 + 4 X 3 + 5 X 2 + 6 X 1) = 7I丄也12 =題型三：已知哈希表長度和哈希函數(shù)，利用線性探測法和鏈地址法解決沖突，構(gòu)造哈希表，計算ASL1、(線性探測)設(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)鍵字進行比較？ 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？ 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。答案：畫

15、表如下:012345678910111213141516173217634924401030314647 查找 63,首先要與 H(63)=63%16=15號單元內(nèi)容比較，即63與31比較，不匹配；然后順移，與 46,47,32,17,63 相比，一共比較了 6次！ 查找60,首先要與 H(60)=60%16=12號單元內(nèi)容比較，但因為 12號單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以應(yīng)當(dāng)只比較這一次即可。 對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)?！?3”需要 6次，“49”需要 3次，“40”需要 2次，“46”需要 3次，“47”需要 3次，所以 ASL=1/11

16、 (6+2+ 3X3+6= 23/112、(鏈地址法)設(shè)哈希函數(shù)H(K)=3 K mod 11，哈希地址空間為010，對關(guān)鍵字序列(32,13, 49, 24, 38, 21, 4, 12)，按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查ASLsucc 和 ASLunsuco找成功時和查找失敗時的平均查找長度 線性探測法； 鏈地址法。答案:散列地址012345678910關(guān)鍵字412493813243221比較次數(shù)11121212ASLsucc = (1+1+1+2+1+2+1+2 /8=11/8ASLunsucc=( 1+2+1+8+7+6+5+4+3+2+)/11=40/11AS

17、Lsucc =(1*5+2*3)/8=11/8ASLunsucc= ( 1+2+1+2+3+1+3+1+3+1+1/11=19/1110第八章題型一：已知整數(shù)序列，寫岀直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、簡 單選擇排序、歸并排序的排序過程（考兩到三種），并會分析時空復(fù)雜度、穩(wěn)定性及適用情況1、設(shè)待排序的關(guān)鍵字序列為12，2, 16, 30, 28, 10, 16*，20, 6, 18，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。直接插入排序折半插入排序 希爾排序（增量選取5, 3, 1） 冒泡排序簡單選擇排序 快速排序二路歸并排序2121630281016

18、*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*2028306182610121616*20 :28 3018261012 -16 16*18 :20 28 30折半插入排序排序過程同希爾排序（增量選取5, 3, 1)102166181216*20 3028621210181616*20 30282610121616*18202830冒泡排序21216281016“ 2061830212161016* 206182830212101616* 6182028302101216616*182028302101261616*182028302106121616*182028302610121616*18202830答案：直接插入排序26 1012 16 16*18 20 28 30（增量選取5）（增量選取3）（增量選取1）快速排序12621012283016*20 16186261012283016*20 1618 28261012181616*20 2830 1826101216*161820 283016*26 10 12 16* 1618 20 28 30左子序列遞歸深度為1右子序列遞