《數據結構與算法》模擬試卷一

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

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

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

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

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