廣東海洋大學(xué)2013—2014數(shù)據(jù)結(jié)構(gòu)期末考試試題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上GDOU-B-11-302廣東海洋大學(xué) 2013 2014 學(xué)年第 1 學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法 課程試題課程號(hào)：考試A卷閉卷考查B卷開(kāi)卷題 號(hào)一二三四五六七八九十總分閱卷教師各題分?jǐn)?shù)12151515201211100實(shí)得分?jǐn)?shù)一、 選擇題（6小題，每題3分）1. 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，則采用( )存儲(chǔ)方法最節(jié)省時(shí)間A 順序表 B單鏈表 C 雙鏈表 D單循環(huán)鏈表2. 一個(gè)棧的入棧序列是1,2,3,4,5，則不可能的出棧序列是( )A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,53. 深度為k

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

3、元素個(gè)數(shù)的公式為_(kāi)。2. 已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹(shù)中有_個(gè)葉子結(jié)點(diǎn)。3. 已知無(wú)向圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為_(kāi)。4. 假定一個(gè)數(shù)列25,43,62,31,48,56，采用散列函數(shù)為H(k)=k mod 7，則元素48的同義詞是_。5. 利用簡(jiǎn)單選擇排序?qū)個(gè)記錄進(jìn)行排序，最壞情況下，記錄交換次數(shù)為_(kāi)。三、（15分）已知一棵二叉樹(shù)的中序遍歷序列為DBKEHJAFCIG，后序遍歷序列為DKJHEBFIGCA，試畫(huà)出該二叉樹(shù)并給出其前序遍歷序列四、（15分）設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母

4、構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06，回答下面問(wèn)題：（1）為這八個(gè)字符設(shè)計(jì)哈夫曼編碼（2）對(duì)這八個(gè)字符進(jìn)行等長(zhǎng)編碼需要幾位二進(jìn)制數(shù)，哈夫曼編碼比等長(zhǎng)編碼電文總長(zhǎng)壓縮多少？五、（20分）已知一個(gè)長(zhǎng)度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，試回答下面問(wèn)題（1）將線性表元素依次插入一個(gè)空的平衡二叉樹(shù)，畫(huà)出所得平衡二叉樹(shù)，如果假設(shè)每個(gè)元素查找概率相同，則平均查找長(zhǎng)度為多少？（2）如果對(duì)線性表元素排序后進(jìn)行折半查找，畫(huà)出折半查找判定樹(shù)，假設(shè)每個(gè)元素查找概率相同，計(jì)算平均查找長(zhǎng)度。六、（12分）已知數(shù)據(jù)序列為（11,4,8,19,6,31,23），寫(xiě)