清華模擬試題二答案

1、模擬試題二一 單項選擇題（2 分/題）1一棵左右不空的二叉樹在先序前驅(qū)和后序后繼線索化后，其空鏈域數(shù)為（）。A.0B.1C.2D.不確定，則拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是（）。2設(shè)圖G 采用鄰接表A.O(n)B.O(n+e)C.O(n2)D.O(n*e)3下列排序算法中，時間復(fù)雜度為 O(nlog2n)且占用額外空間最少的是（）。A.堆排序B.冒泡排序C.快速排序D.S排序4已知數(shù)據(jù)表 A 中每個元素距其最終位置不遠(yuǎn)，則采用（）排序算法最節(jié)省時間。A.堆排序 5串是（）。B.C.快速排序D.直接選擇排序排序A.不少于一個字母的序列 C.不少于一個字符的序列B. 任意個字母的序列D.有限個字符的序列

2、二 判斷題（1 分/題）1.（）若一個棧的輸入序列為 123n，其輸出序列的第一個元素為 n，則其輸出序列的每個元素 ai 一定滿足 ai =n-i+1。(i=1,2,.,n)2.（）二叉樹中的葉子結(jié)點就是二叉樹中沒有左右的結(jié)點。3.（）一棵樹中的葉子結(jié)點數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點數(shù)。4.（）刪除二叉排序樹中的一個結(jié)點，再重新原來的二叉排序樹。5.（）線性表就是順序表。6.（）若一棵樹中某結(jié)點的度為 1，則該結(jié)點僅有一棵上去，一定能得到。7.（）所謂平衡二叉樹是指左右叉樹。8.（）AOE 網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最短路徑的長度。9.（）若某二叉樹的葉子結(jié)點數(shù)為

3、 1，則其先序序列和后序序列一定相反。的高度差的絕對值不大于 1 的二10.（）在采用線性探測法處理相鄰。11.（）對B-樹中任一非葉子結(jié)點中的某關(guān)鍵字 K，比 K 小的最大關(guān)鍵字和比 K 大的最小關(guān)鍵字一定都在非葉結(jié)點的最下層。的散列表中，所有的同義詞在表中12.（）若通無向圖的以頂點 1 為起點的深度遍歷序列唯一，則可唯一確定該圖。13.（）若一個有向圖的以頂點 1 為起點的深度遍歷序列唯一，則可唯一確定該圖。14.（）在數(shù)據(jù)表基本有序時，冒泡排序算法的時間復(fù)雜度一定接近 O(n)。15.（）設(shè)指針p 指向單鏈表中的一個結(jié)點，則語句序列 u:=p.next; u:=u.next 將刪除一個

4、結(jié)點。三 填空題（2 分/題）已知二叉樹中葉子數(shù)為 50，僅有一個孩子的結(jié)點數(shù)為 30，則總結(jié)點數(shù)是（129）。已知棧的輸入序列為 1,2,3,.,n，輸出序列為 a1, a2, a3,., an，符合 a2=n 的輸出序列共有（n-1）種。已知數(shù)組 A1.10,1.10為對稱矩陣，其中每個元素占 5 個單元?，F(xiàn)在起始地址為 1000 的連續(xù)內(nèi)存單元將其下三角部分按行優(yōu)先次序中，則元素 A5，6對應(yīng)的地址為（1095）。4在順序為 i 和j 的兩個結(jié)點處在同一層的條的二叉樹中，件是（log2i=log2j）。5在按關(guān)鍵字遞增的數(shù)組 A1.20中，按折半查找方法進(jìn)行查找時，查找長度為 5 的元素

5、個數(shù)是（5）。四 應(yīng)用題（5 分/題）1一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來，試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： B F ICEH G；中序序列：D KFIA EJC ；后序序列： K FBHJ G A先序序列：ABDFKICEHJG；中序序列：DBKFIAHEJCG；后序序列：DKIFBHJEGCAABCDFEGKIHJ2已知哈希表地址空間為 0.14，哈希函數(shù)為H(k)=k mod 13，采用線性探測法處理。將下面各數(shù)依次存入該散列表中，并求出在等概率下的平均查找長度和失敗的查找長度。240,29,345,189,100,20,21,35,3,208

6、,78,99,45,350012345678910111278910 11 12 13 14001233677978986ASLs=43/14ASLf=105/133對下面的遞歸算法，寫出調(diào)用 p(4)的執(zhí)行結(jié)果。PROC p(w:eger);if w0 then write(w);p(w-1);p(w-1)ENDP; p4 3 2 1 1 2 1 1 3 2 1 1 2 1 14一棵排序二叉樹結(jié)構(gòu)如下，各結(jié)點的值從小到大依次為 18，請標(biāo)出各結(jié)點的值。61857324208 78 350 29 3240 345 189 100 20 21 35 99 455求出下圖中頂點 1 到其余各頂點的

7、最短路徑。1341063578810五 算法設(shè)計題（10 分/題）已知T 為一棵二叉排序樹。設(shè)計算法按遞減次序打印各結(jié)點的值。設(shè)計算法以產(chǎn)生一個序列，要求該序列滿足：依次將這些元素到初值為空的二叉排序樹中所得的結(jié)果與原二叉排序樹相同。：（1）按“右根左”遍歷（2）先序遍歷算法2已知一棵二叉樹按順序方式在數(shù)組 A1.n中，設(shè)計算法求出下標(biāo)分別為 i 和j 的兩個結(jié)點的最近公共祖先結(jié)點。：沿 i、j 分別上溯查找公共結(jié)點。算法3已知數(shù)組 A1.n的元素類型為整型，設(shè)計算法將其調(diào)整為左右兩部分，使得左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為 O(n)。算法：利用快速排序的。4設(shè)計算法判斷有向圖 G 是否是一棵以 v 為根的有向樹?？梢允褂靡韵聨讉€函數(shù)調(diào)用：adj(G,v)返回圖G 中頂點v 的第一個鄰接點，若不存在返回 0 ne