02級期末考試試題答案(草稿)

1、?數(shù)據(jù)結構?試題(開卷)(電信系本科 2002級 2003 年12月)姓名班級、答復以下問題(每題4分，共32分)題號-一-二二三總分題分323830100得分1. 對于一個有10000個結點的二叉樹，樹葉最多有多少個？最少有多少個？答： 最多是完全二叉樹的形態(tài)，即5000個葉子；最少是單支樹的形態(tài)，即 1個葉子。2. 一棵二叉樹的中序序列和后序序列分別為：DBGEACHF 和DGEBHFCA，那么該二叉樹的前序序列是什么？答：是：ABDEGCFH3. 設有1000個無序的元素，需排出前10個最大(小)的元素，你認為采用哪種排序方法最快？為什么? 答：用錦標賽排序或堆排序很適宜，因為不必等全部

2、元素排完就能得到所需結果，時間效率為 O(nlog2n)； 即 O (1000log 21000)=0(10000)錦標賽排序的準確比擬次數(shù)為：堆排序的準確比擬次數(shù)為：假設用冒泡排序也較快，最多消耗比擬次數(shù)為(n-1+ n-2+ n-10) =10 n-55=10000-55=9945 (次)4. 在KMP算法中，模式串為 ADABCADADA，請寫出模式串的 nextj函數(shù)值。答：01121123435. 中序遍歷的遞歸算法平均空間復雜度為多少？答：要考慮遞歸時占用了?？臻g，但遞歸次數(shù)最多不超過樹的高度，所以空間復雜度為O(log2 n)6. 欲將無序序列(24, 79,13, 36,70,

3、 96,12,10, 36*,49,100, 27)中的關鍵碼按升序重新排列，請寫出快速排序第一趟排序的結果序列。另外請畫出堆排序小根堆的初始堆。答：快速排序第一趟排序的結果序列為：|10, 12， 13 ， 24 ， 70, 96, 36, 79, 36*, 49, 100, 27注意要按振蕩式逼近算法實現(xiàn) 堆排序的初始堆如下，注意要從排無序堆開始，從最后一個非終端結點開始，自下而上調(diào)整，而且要排2479 .1312/ / 3入為1036*49100 27成小根堆！初始堆序列為：10，24，12，79，49，27，13，36，36*, 70, 100, 96無序堆有序初始堆7.一組關鍵字為1

4、0,H key = key MOD/10、24 1279.49.271336*70100 9647,4063，/3646,一47,一4063函數(shù)13。請寫出用線性探測法處理沖突構造所得的哈希表。24，32，17，31，30,答:494017313230464710246301234567891011128.算法復雜度O 1 的含義是什么？答：它表示與輸入的元素規(guī)模無關，是一個常數(shù)但不一定是1 ?；颍核硎驹撍惴▓?zhí)行時消耗時間的長短或占用輔助空間的多少與元素個數(shù)效率或空間效率，將是最理想的算法。n無關，假設能到達這樣的時間二、綜合題4小題，共38 分1.以下圖為某無向圖的鄰接表，按教材算法7.5

5、和7.6分別寫出深度優(yōu)先搜索和廣度優(yōu)先搜索的結果，并畫出邏輯結構圖。10分BCDAEFGHIJ321A3A298A8A答：深度優(yōu)先搜索|7h|3|A10jDFS )結果為：AEBCFGDHIJ廣度優(yōu)先搜索BFS 結果為：AEBCGFDHIJ這是有著4個連通分量的非連通圖。7A2.設AH8個字符出現(xiàn)的概率為：=0.10, 0.16, 0.01,0.02,0.29, 0.10,0.07,0.25,設計最優(yōu)二進制碼并計算平均碼長。如果設計最優(yōu)三進制編碼即可用0,1,2三種符號進行編碼，畫出最優(yōu)三叉樹并計算平均碼長。(10分答:最優(yōu)二進制編碼不惟一，但WPL惟-。1.00.10A0.100.020.2

6、5 0.260.290.070.160.01假設按教材算法，合并規(guī)律應當如下:A : 001B: 101C: 00000D:00001E: 11F: 100G:0001H: 01平均碼長為：工 PiWi=3 X (0.1 + 0.16+ 0.1)+ 5X( 0.01+0.02)+2 X( 0.29+0.25)+4 X 0.07=2.59對三進制編碼，由于總共有8個字符，8%3=2,故第一次構建最優(yōu)樹只有 2個結點，那么最優(yōu)三叉樹為0.010/ 0 0.03 / 、 0.01 0.021.000.550.45A : 100平均碼長為：工 PiWi=1 >°#69+2 X (

7、76;1+0.16+ci200+(0；07+0.25)+ 0.10 0.163 X (0.01+0.02)=0.29+1.36+0.09=1.740.030.070.100.100.02編碼為:A : 02B: 21C: 000D: 001E: 1B: 001C:00000D: 0E: 0001F: 101F: 20G: 01平均碼長仍為:H: 22 工 PiWVi=2.59G:0001H: 11n個元素中的最大值和最小8分3.給定一個由n個關鍵字不同的記錄構成的序列，你能否用2n-3次比擬找出值？如果有，請描述你的方法。最快需多少次比擬？無需寫算法 答：可以實現(xiàn)。選用錦標賽算法。兩兩元素比擬

8、，淘汰較小的，形如一棵二叉樹。樹根為最大值此時用掉n-1次比擬？。而最小者一定位于首次被淘汰之列。故只有n/2個。一共需n-1+n/2次比擬。4.分析下面算法中I和h變量表示什么含義？初始調(diào)用時，I和h應取什么值？其中p為指 向二叉樹的根結點，如果去掉形參中的“ &符號，會得到什么結果？10分Void ABC(Bitree p, int l, int & h) if p 豐 NIL then1=1+1;if l>h then h=l;ABC( p->Lchild, l,h);ABC( p->Rchild, l,h);此題含義是：求樹的深度h 但求解方法是從根開

9、始計算層次。 反而比從葉子往上計算要簡單。解：依分析，I、h表示二叉樹的層次數(shù)和深度。開始調(diào)用時，應為 ABC p, 0, 0 去掉形參中的“ &號，那么上次計算的結果不能正確返回。故h不變，得不到正確結果。這里的int &h應當理解為push形參，每次返回就要 return實參。所以I和h其實是每一層當前的狀態(tài)。L代表當前結點所在的層數(shù)從根結點計算起；而h代表當前結點所在的深度。附：教材求深度的函數(shù)如下:int BTreeDepth(Btree *BT)*BT為二叉樹某結點的指針int leftdep, rightdep;設左右兩個深度/ 層次計數(shù)器if(BT=NULL) r

10、eturn(0);當前結點指針為空那么立即返回else leftdep= BTreeDepth(BT->left);/ 遍歷當前結點左子樹/遍歷當前結點右子樹從葉子計數(shù)rightdep=BTreeDepth(BT->right);if( leftdep>rightdep)retur n(leftdep+1);else retur n( rightdep+1); /BTreeDepth算法設計題每題10分，共30分1. 試用C或類C語言編寫一高效算法，將一順序存儲的線性表設元素均為整型量中所有零元素向表尾集中，其他元素那么順序向表頭方向集中。解：void SortA(sqlis

11、t &L) inti=0, zerosum =0;if(L.le ngth=0) return(0);/ 空表else for( i=1; i<=Len gth; i+)if (L.vi<>0) L.v i- zerosum= L.vi;非空表時特別浪費!zerosum+;while( zerosum!=0)L.vi = =0; zerosum-/ 表的后部補 0 return(ok)以上算法在非空表時特別浪費！解：void SortA(sqlist &L) int i=0,zerosum =0;if(L.length= =0) return(0); / 空表

12、那么不執(zhí)行while(i<=L.length&&( L.vi <>0) i+; / 非空表那么不移動 if(i>L.length) return(ok); elsei+; zerosum+;/ 假設有零元素那么統(tǒng)計和移動 for( i; i<=L.length; i+)if ( L.vi = =0) zerosum+;else L.vi- zerosum = L.vi; ; / 非零元素順序前移 while( zerosum!=0 )L.vi = =0; zerosum- / 表的后部補 0 return(ok)解 2 ： void SortA(s

13、qlist &L) int i=0,zerosum =0;if(L.length= =0) return(0); / 空表那么不執(zhí)行while(i<=L.length&&( L.vi <>0) i+; / 非空表那么不移動 if(i>L.length) return(ok); if(i>L.length) return(ok);i+; zerosum+; / 一定有零元素for( i; i<=L.length; i+)if (L.vi<>0) L.vi- zerosum= L.vi;zerosum+;while( zero

14、sum!=0 )L.vi = =0; zerosum- / 表的后部補 0 return(ok)2. 試編寫一個算法， 判斷一給定的整型數(shù)組 an 是不是一個堆 解： void SortA(sqlist &A, int n) if(n=0) return(0); / 空表if (a1<a2) for( i=1; i<=n/2; i+) if (ai>a2*i| ai>a2*i+1)return(-1); return(minleap);else for( i=1; i<=n/2; i+) if (ai<a2*i| ai<a2*i+1)retur

15、n(-1);return( “ maxleap );3. 一棵二叉樹的繁茂度定義為各層結點數(shù)的最大值與樹的高度的乘積。試寫一高效算法， 求二叉樹的繁茂度。, 再從法一：要用層次遍歷以及隊列來處理，可以增設一個寬度計數(shù)器，在統(tǒng)計完每一層的結點個數(shù)之后 計數(shù)器中挑出最大值。typedef struct BTNode node; int layer;/layer 是結點所在層數(shù) BTNRecord, r ;int Width(Bitree T )/ 求樹寬int count ;/增開 count 向量，存放各層對應的結點數(shù)InitQueue(Q);/ 隊列初始化， Q 的元素為 BTNRecord

16、類型EnQueue(Q,T, 0);/根結點入隊 , 0 表示 count0 ，下標值 while(!QueueEmpty(Q) DeQueue(Q, r);/ 結點出隊countr.layer+; / 出隊時再把結點對應層的計數(shù)器加if(r.node->lchild) EnQueue(Q,r.node->lchild, r.layer+1);if(r.node->rchild) EnQueue(Q,r.node->rchild, r.layer+1); / 按層序入隊時要隨時標注結點所在層號h=r.layer; / 最后一個隊列元素所在層就是樹的高度for(maxn=

17、count0, i=1; h;i+)if(counti>maxn) maxn=counti; / 求出哪一層結點數(shù)最多return ( h* maxn) / Width法二：假設不用輔助數(shù)組，不用層數(shù)分量也可以，關鍵在于如何區(qū)別層與層。有兩種方法：一、通過比擬指針判斷是否到達新的一層的開始；二、通過比擬指針判斷是否到達當前層的末尾.由于方法一對新的一層的開始點不易確定，比擬次數(shù)要多于第二種，因此推薦第二種。對任意種類的樹都適用，二叉樹類似可得。算法如下：/TreeWidth 求樹的寬度/不用輔助數(shù)組，不用層數(shù)分量/思路：/1.以兩個整型變量存寬度，一個表示當前層的節(jié)點數(shù)，一個表示當前最大

18、寬度，當遍歷完一層后立即判斷兩者大小，保存大者。/2.通過比擬指針判斷是否到達本層的末尾，以確定層與層間的關系。/int TreeWidth (T reeNode * T)int iMaxCount=0,iRecCount=0;/iRecCount 當前層的節(jié)點數(shù)，iMaxCount 當前最大寬度TreeNode * pP=T,* pLastChild=T;/pP 指向當前節(jié)點，pFirstChild 指向本層最末節(jié)點InitQueue(Q);/隊列初始化，Q的元素為TreeNode*類型EnQueue(Q,T);根結點入隊while(!QueueEmpty(Q)DeQueue(Q,pP); 結點出隊iRecCount+;出隊時再把結點所在層的計數(shù)器加1if(hasChild(pP)EnQueue(Q,pP->Child); 有孩子那么孩子入隊if(pP=pLastChild)假設到達本層的末尾/先決定iMaxCount，再重置iRecCount /求繁茂度不能清零此變量。iMaxCount=max(iMaxCount,iRecCount);iRecCount=0;QueueTail(Q,pLastChild);