《數(shù)據(jù)結(jié)構(gòu)與算法》模擬試卷一

1、數(shù)據(jù)結(jié)構(gòu)與算法模擬試卷一 一、填空題（每空2分，共20分）1. 在一個(gè)長度為n的循環(huán)鏈表中，刪除其元素值為x的結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。2. 如果入棧序列是1，3，5，97，99，且出棧序列的第一個(gè)元素為99，則出棧序列中第30個(gè)元素為_。3. 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：集合、 _、 樹狀結(jié)構(gòu)、_。4. 線性表的鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)包括兩個(gè)域，分別是：_ 和 _ 。5. 一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；6. 在對(duì)一組記錄(54，38，96，72，60，15，60，45，83)進(jìn)行直接插入排序時(shí)，當(dāng)把第5個(gè)記錄60插入到有序表時(shí)，為尋找插入

2、位置需比較_次。7. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的_出度_。二、選擇題（從下列各題四個(gè)備選答案中選出一個(gè)正確答案，并將其代號(hào)寫在答題紙相應(yīng)位置處。每小題2分，共10分。）1. 對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是_。A. 順序表 B.有序的順序表 C.鏈表 D.有序的鏈表 2. 計(jì)算遞歸函數(shù)如不用遞歸過程通常借助的數(shù)據(jù)結(jié)構(gòu)是_。 A.線性表 B.雙向隊(duì)列 C.樹 D.棧 3. 如果T2是由有序樹T轉(zhuǎn)換來的二叉樹，則T中結(jié)點(diǎn)的后序排列是T2結(jié)點(diǎn)的_。 A.先序排列 B.中序排列 C.后序排列 D.層序排列 4. n個(gè)結(jié)點(diǎn)的線索二叉樹中線索的數(shù)目為_。 A.(n-

3、1)個(gè) B.n個(gè) C.（n+1）個(gè) D.(n+2)個(gè) 5. 設(shè)數(shù)組Am為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則判定Q為空隊(duì)列的條件是_。A.(rear-front)%m= =1B.front= =rearC.(rear-front)%m= =m-1D.front= =(rear+1)%m6. 假設(shè)一棵完全二叉樹按層次遍歷的順序依次存放在數(shù)組BTm中，其中根結(jié)點(diǎn)存放在BT0，若BTi中的結(jié)點(diǎn)有左孩子，則左孩子存放在_。A.BTi/2B.BT2*i-1C.BT2*i D.BT2*i+17. 連通圖是指圖中任意兩個(gè)頂點(diǎn)之間_。A.都連通的無向圖B.都不連通的無向圖C.都連

4、通的有向圖D.都不連通的有向圖8. 在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為_。 A. n B. n/2 C. (n+1)/2 D. (n-1)/29. 若一個(gè)棧的輸入序列是1，2，3，4，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是_。A. 不確定 B. n-i C. n-i+1 D. n-i-110. 在單鏈表中插入一個(gè)結(jié)點(diǎn)，要修改_個(gè)結(jié)點(diǎn)的指針域。 A. 1 B. 2 C. 3 D. 4三、簡答題（要求寫出主要操作步驟及結(jié)果。每小題5分,共35分）1. 若進(jìn)棧元素依次為A、B、C、D，寫出

5、至少5種可能的出棧順序。2. 已知一棵二叉樹先序遍歷順序?yàn)?ABDEGHJCFI，中序?yàn)?DBGEHJACIF，試構(gòu)造該二叉樹。3. 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.08, 0.18, 0.02, 0.06, 0.35, 0.10, 0.16, 0.05。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。并計(jì)算其平均編碼長度（即WPL）。 4.將下面森林轉(zhuǎn)換為相應(yīng)的二叉樹。ABCDEFGHIJKLMN5. 給出下圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。6. 使用普里姆算法構(gòu)造如下圖所示的圖G的一棵最小生成樹。（畫出構(gòu)造過程）7. 對(duì)數(shù)據(jù)元素序列15，13，12，8，22，37，4，33，8，6進(jìn)行降序排序，用篩選法構(gòu)造堆排序的初始小頂堆，畫出堆形。四、證明題（要求寫出證明過程。共8分）一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)為