北林數(shù)據(jù)結構期末考試應用題

1、數(shù)據(jù)結構應用題天涯古巷出品第三章題型一：表達式求值按照四則運算加(+)、減(-)、乘(*)、除(/)和幕運算)優(yōu)先關系的慣例，畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程：A-BXC/D+EF解:BC=GG/D=HA-H=IEF=JI+J=K步驟OPTR棧OPND棧輸入字符主要操作1#A-B*C/D+EF#PUSH(OPND,A)2#A-B*C/D+EF#PUSH(OPTR,-)3#-AB*C/D+EF#PUSH(OPND,B)4#-AB*C/D+EF#PUSH(OPTR,*)5#-*ABC/D+EF#PUSH(OPND,C)6#-*ABC/D+EF#Operate(B,*,C)7#

2、-AG/D+EF#PUSH(OPTR,/)8#-/AGD+EF#PUSH(OPND,D)9#-/AGD+EF#Operate(G,/,D)10#-AH+EF#Operate(A,-,H)11#I+EF#PUSH(OPTR,+)12#+IEF#PUSH(OPND,E)13#+IEF#PUSH(OPTR,)14#+IEF#PUSH(OPND,F)15#+IEF#Operate(E,F)16#+IJ#Operate(I,+,J)17#K#RETURN題型二：漢諾塔時間復雜度的分析及證明漢諾塔問題的遞歸算法的時間復雜度是什么？請給出答案并且給予證明解：時間復雜度T(n)=0(2n),證明如下已知：f(

3、l)=l,f(n)=2f(n-1)+1所以：f(n)+1=2(f(n-1)+1)f(n)=2n-1(2n-1為至少執(zhí)行移動操作的次數(shù))T(n)=O(2n)故：得證第四章題型一：數(shù)組地址的計算設有二維數(shù)組A(6x8),每個元素占6字節(jié)存儲，順序存放，A的起地址為1000,計算:數(shù)組A的體積(即存儲量)；數(shù)組的最后一個元素A57的起始地址；按行優(yōu)先存放時，元素A14的起始地址；按列優(yōu)先存放時，元素A47的起始地址。第五章題型一：由二叉樹的中序遍歷和前(后)序遍歷，畫出該二叉樹1、給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：ABDFCEGH；中序遍歷序列：BFDAGEHC試畫出二叉樹B，并簡述由

4、任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。答案：2、試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。題型二：哈夫曼樹的構造(畫樹、計算WPL、初態(tài)和終態(tài)表)，設計哈夫曼編碼1、假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32,0.03，0.21，0.10。試為這8個字母設計赫夫曼編碼。試設計另一種由二進制表示的等長編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【(2,3

5、)，6,(7,10)】，19,21,32字母編號對應編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案比較：字母編號對應編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10(100)(40)(60)192132(28)(17)(11)7106(5)23方案1WPL=2*(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方

6、案2WPL=3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結論：哈夫曼編碼優(yōu)于等長二進制編碼2、已知下列字符A、B、C、D、E、F、G的權值分別為3、12、7、4、2、8,11,試填寫出其對應哈夫曼樹HT的存儲結構的初態(tài)和終態(tài)。答案：終態(tài):初態(tài):weightparentlchildrchildweightparentlchildrchild13000138002120002121200370003710004400044900520005280068000681000711000711110080008595190009911481000010151

7、23611000112013971200012271321013000134701112題型三：利用二叉樹的性質對某些問題進行證明對于那些所有非葉子結點均含有左右子數(shù)的二叉樹：試問：有n個葉子結點的樹中共有多少個結點？試證明：2-1)=1,其中n為葉子結點的個數(shù)，1表示第i個葉子結點所在的層次ii=1(設根節(jié)點所在層次為1)。解：(1)總結點數(shù)為1+2件，其中件為非葉子結點數(shù)，則葉子結點數(shù)為n=nl+1,所以總結點數(shù)為2n一1。(2)用歸納法證明。i=1，說明二叉樹只有一個葉子結點，則整棵樹只有一個根結點，*=1,2-(l1-1)=1，結論成立。設有n個葉子結點時也成立，即2-(/-i.+2-

8、(-L+.+2-(p+.+2-(/”+i.=1，現(xiàn)假設增加一個葉子結點，這意味著在某葉子結點p上新生兩個葉子結點，而結點p則成為非葉子結點，可見，總結點數(shù)增2，葉子結點數(shù)增1。此時，所有葉子結點是原結點除去p，然后加上兩個深度為l+1的新葉子結點，由此，p2-(l1-1)+2-(l2-1)+.+2-(lp-1-1)+2-(lp+1-1)+.+2-(ln+1)+2-(lp+1-1)+2-(lp+1-1)=2-(l1-1)+2-(l2-1)+.+2-(lp-1)+.+2-(ln+1)=1則當i=n+1時，也成立，由此即得到證明。AA-第六章2、已知如圖6.33所示的無向網(wǎng)，請給出：鄰接矩陣；鄰接表

9、最小生成樹答案：叩43DDDDD4D559DDD35D5DDD5D55D7654D9D7D3DDDDD63D2DDDD5D2D6DD54DD6D題型二：根據(jù)圖的邏輯結構或存儲結構，寫出深度、廣度優(yōu)先搜索遍歷結果（根據(jù)邏輯結構寫是唯一的，根據(jù)存儲結構寫不唯一）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先題型三：根據(jù)圖的邏輯結構填寫最短路徑求解過程表，畫出最小生成樹（計算權值和），寫出拓撲排序結果有向網(wǎng)如圖所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成下表XyTi23456b1515151515158b8b8b8b8b(ab)2(ac)

10、121211118888f3(a,c,，d)eoo101088e(a,c,e)foo(a,c,)goooo161688f3g88f8g(a,c,d,g)S終點集888188f8e88f8i88f8e88g88f8e88g8b第七章題型一：折半查找過程，畫判定樹，計算ASL假定對有序表：(3，4，5，7，24，30，42，54，63，72，87，95)進行折半查找，試回答下列問題：畫出描述折半查找過程的判定樹；若查找元素54，需依次與哪些元素比較？若查找元素90，需依次與哪些元素比較？假定每個元素的查找概率相等，求查找成功時的平均查找長度。答案：先畫出判定樹如下(注：mid=(1+12)/2=6

11、)：30563374287424547295查找元素54，需依次與30,63,42,54元素比較；查找元素90，需依次與30,63,87,95元素比較；求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前3層共查找1+2X2+4X3=17次；但最后一層未滿，不能用8X4，只能用5X4=20次，所以ASL=1/12(17+20)=37/123.08題型二：二叉排序樹的創(chuàng)建，查找，計算ASL已知如下所示長度為12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹

12、，并求其在等概率的情況下查找成功的平均查找長度。若對表中元素先進行排序構成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。答案：三(1X1+2XCD求得的二叉排序樹如下圖所示，在等概率情況下查2+3X3+4X3+!題型三：已知哈希表長度和哈希函數(shù)，利用線性探測法和鏈地址法解決沖突，構造哈希表，計算ASL1、(線性探測)設哈希表的地址范圍為017,哈希函數(shù)為：H(key)=key%16。用線性探測法處理沖突，輸入關鍵字序列：(10，24，32，17，31，30，46，47，40，63，49)，構造哈希表，試回答下列問題：畫出哈希表的示意圖；若查找關鍵字63,需要依次與哪

13、些關鍵字進行比較？若查找關鍵字60,需要依次與哪些關鍵字比較？假定每個關鍵字的查找概率相等,求查找成功時的平均查找長度。答案：畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內容比較，即63與31比較，不匹配；然后順移,與46,47,32,17,63相比,一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內容比較，但因為12號單元為空(應當有空標記)，所以應當只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)?！?3”需要6

14、次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11(6+2+3X3+6)=23/112、（鏈地址法）設哈希函數(shù)H（K）=3Kmod11,哈希地址空間為010,對關鍵字序列（32,13，49，24，38，21，4，12），按下述兩種解決沖突的方法構造哈希表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。線性探測法；鏈地址法。答案：散列地址012345678910關鍵字412493813243221比較次數(shù)11121212ASLsucc=(1+1+1+2+1+2+1+2)/8=11/8ASLunsucc=(1

15、+2+1+8+7+6+5+4+3+2+1)/11=40/11ASLsucc=(1*5+2*3)/8=11/8ASLunsucc=(1+2+1+2+3+1+3+1+3+1+1)/11=19/110123456789oTIlAlk|38|A|13|h-k|24|A|13Ihl1Ia|第八章題型一：已知整數(shù)序列，寫出直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、歸并排序的排序過程（考兩到三種），并會分析時空復雜度、穩(wěn)定性及適用情況1、設待排序的關鍵字序列為12，2，16，30，28，10，16*，20，6，18，試分別寫出使用以下排序方法，每趟排序結束后關鍵字序列的狀態(tài)。折

16、半插入排序直接插入排序希爾排序（增量選取5，3，1）冒泡排序快速排序簡單選擇排序二路歸并排序答案：直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折半插入排序排序過程同希爾排序（增量選取5，3，1）102166181216*203028（增量選取5）621210181616*203028（增量

17、選取3）2610121616*18202830（增量選取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列遞歸深度為1，右