資源描述：
《清華大學(xué)模擬試題二》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、清華大學(xué)模擬試題二一．單項選擇題（2分/題）1．一棵左右子樹均不空的二叉樹在先序前驅(qū)和后序后繼線索化后，其空鏈域數(shù)為（）。A.0B.1C.2D.不確定2．設(shè)圖G采用鄰接表存儲，則拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是（）。A.O(n)B.O(n+e)C.O(n2)D.O(n*e)3．下列排序算法中，時間復(fù)雜度為O(nlog2n)且占用額外空間最少的是（）。A.堆排序B.冒泡排序C.快速排序D.SHELL排序4．已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，則采用（）排序算法最節(jié)省時間。A.堆排序B.插入排序C.快速排序D.直接選擇排
2、序5．串是（）。A.不少于一個字母的序列B.任意個字母的序列C.不少于一個字符的序列D.有限個字符的序列二．判斷題（1分/題）1.（?）若一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1。(i=1,2,...,n)2.（′）二叉樹中的葉子結(jié)點(diǎn)就是二叉樹中沒有左右子樹的結(jié)點(diǎn)。3.（′）一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。4.（′）刪除二叉排序樹中的一個結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。5.（′）線性表就是順序表。6.（
3、?）若一棵樹中某結(jié)點(diǎn)的度為1，則該結(jié)點(diǎn)僅有一棵子樹。7.（′）所謂平衡二叉樹是指左右子樹的高度差的絕對值不大于1的二叉樹。8.（′）AOE網(wǎng)所表示的工程至少所需的時間等于從源點(diǎn)到匯點(diǎn)的最短路徑的長度。9.（?）若某二叉樹的葉子結(jié)點(diǎn)數(shù)為1，則其先序序列和后序序列一定相反。10.（′）在采用線性探測法處理沖突的散列表中，所有的同義詞在表中相鄰。11.（?）對B-樹中任一非葉子結(jié)點(diǎn)中的某關(guān)鍵字K，比K小的最大關(guān)鍵字和比K大的最小關(guān)鍵字一定都在非葉結(jié)點(diǎn)的最下層。12.（?）若一個連通無向圖的以頂點(diǎn)1為起點(diǎn)的深度遍歷序列唯一
4、，則可唯一確定該圖。13.（′）若一個有向圖的以頂點(diǎn)1為起點(diǎn)的深度遍歷序列唯一，則可唯一確定該圖。14.（′）在數(shù)據(jù)表基本有序時，冒泡排序算法的時間復(fù)雜度一定接近O(n)。15.（′）設(shè)指針p指向單鏈表中的一個結(jié)點(diǎn)，則語句序列u:=p^.next;u:=u^.next將刪除一個結(jié)點(diǎn)。一．填空題（2分/題）1．已知二叉樹中葉子數(shù)為50，僅有一個孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)是（129）。2．已知棧的輸入序列為1,2,3,...,n，輸出序列為a1,a2,a3,...,an，符合a2=n的輸出序列共有（n-1）種。3．
5、已知數(shù)組A[1..10,1..10]為對稱矩陣，其中每個元素占5個單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)內(nèi)存單元中，則元素A[5，6]對應(yīng)的地址為（1095）。4．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點(diǎn)處在同一層的條件是（?log2i?=?log2j?）。5．在按關(guān)鍵字遞增的數(shù)組A[1..20]中，按折半查找方法進(jìn)行查找時，查找長度為5的元素個數(shù)是（5）。二．應(yīng)用題（5分/題）1．一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來，試求出空格處的內(nèi)容，并畫出該二叉樹。先
6、序序列：BFICEHG；中序序列：DKFIAEJC；后序序列：KFBHJGA先序序列：ABDFKICEHJG；中序序列：DBKFIAHEJCG；后序序列：DKIFBHJEGCAABCDFEGKIHJ1．已知哈希表地址空間為0..14，哈希函數(shù)為H(k)=kmod13，采用線性探測法處理沖突。將下面各數(shù)依次存入該散列表中，并求出在等概率下的平均查找長度和失敗的查找長度。240,29,345,189,100,20,21,35,3,208,78,99,45,35001234567891011121314012345678
7、91011121314208783502932403451891002021359945001233677978986ASLs=43/14ASLf=105/132．對下面的遞歸算法，寫出調(diào)用p(4)的執(zhí)行結(jié)果。PROCp(w:integer);ifw>0then[write(w);p(w-1);p(w-1)]ENDP;{p}4321121132112113．一棵排序二叉樹結(jié)構(gòu)如下，各結(jié)點(diǎn)的值從小到大依次為1~8，請標(biāo)出各結(jié)點(diǎn)的值。68175342601．求出下圖中頂點(diǎn)1到其余各頂點(diǎn)的最短路徑。30201543214
8、3211036310153166368765876578107810一．算法設(shè)計題（10分/題）1．已知T為一棵二叉排序樹。（1）設(shè)計算法按遞減次序打印各結(jié)點(diǎn)的值。（2）設(shè)計算法以產(chǎn)生一個序列，要求該序列滿足：依次將這些元素插入到初值為空的二叉排序樹中所得的結(jié)果與原二叉排序樹相同。算法思想：（1）按“右根左”遍歷（2）先序遍歷2．已知一棵二叉樹按順序方式存儲
