1、2014年春季北大數據結構與算法 B期末考試模擬試卷(本試卷只是給同學們看看考題形式和范圍，難度與真實考卷稍有差別)學號 姓名 教師/教室(注：如米標明，本試卷題中的下標、位 .胃.都從o開始計數)一、填空題(共32分)1 .設有字符串變量String A = This,C= just,D= ajest, ”請計算下列表達式：(1) A+B+D= Thisisajest ; (2) D.IndexOf( t )(=_2_皆在字符串中的第一個位置)(3) B.StrlengthQ = 2(4) D.SubStr(U2)=(注：1為起始下標，2為子串長度)【4分】2 .順序查找n個元素的順序表，若

2、查找成功，則比較關鍵字的次數S多為n次;若查找失敗，則比較關鍵字的次數最多為_n_，最少力_次?！?分】3 .在散列函數H (key) =key%p中，p值最好取 質數(或素數)。【1分】4 .對于下圖鄰接表所對應的有向圖，試寫出：【2分】(1)從頂點出發進行深度優先遍歷結果 _1, 2, 3, 4, 5_(2)從頂點出發進行廣度優先遍歷結果 _1, 2, 3, 4, 55 .當圖中各條邊上的權值_都相等時，寬度優先搜索算法可用來解決單源最短路徑問題？【2分】6 .一棵有n個結點的滿二叉樹有i個度為1的結點、有(n-1)/2個分支非終端)結點；該滿二 叉樹的深度最大為_(n-l)/2_,最小為

3、int(log2n)gcLlog2nJo (獨根樹深度為0)【4分】7 .對于給定的n個元素，可以構造出的邏輯結構有線性結構，樹形結構,閣形結構,集合四種?！?分】8 .下面程序段的時間復雜度力_O(n)_。( n I)大。表示法【2分】sum=l;for (i=0;sum、 /D E F.、2 .設一組數據為1, 14,27,29,55,68, 10,11, 23,現采用的散列函數是 H (key) =key % 13, 沖突用鏈地址法解決，設散列表的大小為13 (下標為0? 12),試畫出插入上述數據后的散列表。 答：3 .設T是一棵二叉樹，除葉子結點外，其它結點的度數皆為2,若T中有6個

4、葉結點，試 問：(1) T樹的最大深度Kmax=?最小可能深度Kmin=?(假定獨根二叉樹深度為0)(2) T樹中共有多少非葉結點？(3)若葉結點的權值分別為1,2,3,4,5,6。請畫出一棵哈曼夫樹，并計算該哈曼夫樹的帶 權 路徑長度wpl。答：1) T樹的最大深度Kmax=5 (除根外，每層均是兩個結點)T樹的最小深度Kmin=3 (具有6個葉子的完全二叉樹是其中的一種形態)(2) 非葉子結點數是5。(n2=n0-l)(3) 哈夫曼樹見下圖，其帶權路徑長度 wpl=51四、算法填空題(20分，第一題10分，第2題10分)1 .下回是求二叉樹高度(獨根樹高度是 1)的遞歸算法，試補充完整二叉

5、樹的兩指針域為lchild與rchild ,算法中p力二叉樹的根，lh和rh分別為以p為根的二 叉 樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最后返回。int height(BinTree *p) int hi, Ih, rh;if (pj/ p!二 NULL 也對 if (p-lchild=null)lh= 0else lh= height(p-Ichii (l): if(p-rchild=null) rh= 0:else rh= height(p-rchild); if(lh rh)hi=_lh+1 ;else hi=rh+1; else hi= 0:return hi;)/

6、題目中結構已經給定，就應該按照題目要求來/如果根據給定的題目結構填入其他內容也正確的話，那么就是正確的。 2 .對單鏈表(帶頭結點)中元素按插入方法實現非遞增序列的排序的C語言描述算法如下，其中L為鏈表頭結點指針。請填充算法中標出的空白處，完成其功能。typedef struct node int data;struct node *next; linknode , *link;void Insertsort(link L) link p , q, r, u;p=L- ncxt; L-ncxt = NULL :/L-next = NULL這？句是需要的，因為p指向待插入結點，L G來一直指向排好序的鏈表。 第二層while循環實際上是在L所指向的有序表中查找p應該插入的位置。while( -p !=NULL_) r=L; q=L-next; whilc(q != NULL & q-data data) r=q; q=q-next;u=p-next; p- ne