廣東海洋大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷及答案

1、GDOU-B-11-302班級： 姓名： 學(xué)號： 試題共 3 頁 加白紙 5 張 密 封 線廣東海洋大學(xué) 2013 2014 學(xué)年第 1 學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法 課程試題課程號：19232502考試A卷閉卷考查B卷開卷題 號一二三四五六七八九十總分閱卷教師各題分?jǐn)?shù)12151515201211100實得分?jǐn)?shù)一、 選擇題（6小題，每題3分）1. 若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)，則采用( A )存儲方法最節(jié)省時間A 順序表 B單鏈表 C 雙鏈表 D單循環(huán)鏈表2. 一個棧的入棧序列是1,2,3,4,5，則不可能的出棧序列是( C )A 5,4,3,2,1 B 4,5,3,2,

2、1 C 4,3,5,1,2 D 1,2,3,4,53. 深度為k的完全二叉樹至多有（ C ）個結(jié)點A B C D 4. G是一個非連通無向圖，共28條邊，則該圖至少有（ D ）個頂點A 6 B 7 C 8 D 95. 在平衡二叉樹中插入一個結(jié)點后造成不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子平衡因子為0，右孩子平衡因子為1，則應(yīng)該做（ C ）型調(diào)整以使其平衡A LL B LR C RL D RR6. 下述排序方法中，時間性能和待排序記錄的初始狀態(tài)無關(guān)的是（ C ）A 插入排序和快速排序 B 歸并排序和快速排序C 選擇排序和歸并排序 D 插入排序和歸并排序二、填空題1. 數(shù)組Qn用來表示一

3、個循環(huán)隊列，front為隊頭元素的前一個位置，rear為隊尾元素位置，計算隊列中元素個數(shù)的公式為_（rear-front+n）%n_。2. 已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有_12_個葉子結(jié)點。3. 已知無向圖的頂點數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為_O(n+e)_。4. 假定一個數(shù)列25,43,62,31,48,56，采用散列函數(shù)為H(k)=k mod 7，則元素48的同義詞是_62_。5. 利用簡單選擇排序?qū)個記錄進行排序，最壞情況下，記錄交換次數(shù)為_n-1_。三、（15分）已知一棵二叉樹的中序遍歷序列為DBKEHJAFCIG，

4、后序遍歷序列為DKJHEBFIGCA，試畫出該二叉樹并給出其前序遍歷序列四、（15分）設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，它們在電文中出現(xiàn)的頻度分別為0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06，回答下面問題：（1）為這八個字符設(shè)計哈夫曼編碼（2）對這八個字符進行等長編碼需要幾位二進制數(shù)，哈夫曼編碼比等長編碼電文總長壓縮多少？五、（20分）已知一個長度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，試回答下面問題（1）將線性表元素依次插入一個空的平衡二叉樹，畫出所得平衡二叉樹，如果假設(shè)每個元素查找概率相同，則平均查找長度為多少？（2）如果對線性表元素排序后進行折半查找，畫出折半查找判定樹，假設(shè)每個元素查找概率相同，計算平均查找長度。六、（12分）已知數(shù)據(jù)序列為（11,4,8,19,