課程考試試卷
一、單選題（每小題 2 分，共10分，本題所給四個答案中只有乙個是正確的）
1．將含有100個結點的完全二叉樹從根結點開始順序編號，根結點為第0號，其他結點自上而下，同一層從左向右連續編號，則編號最小的葉子結點的編號為
（a）47b）48c）49d）50
2．對一顆二叉排序樹進行得到的結點序列是乙個有序序列。
（a）前序周遊 （b）中序周遊 （c）後序周遊 （d）層次周遊
3．設只含根結點的二叉樹的高度為1，則高度為10的二叉樹, 至少有_________個結點。
（a）10b）20c）30d）40
4．如果待排序序列中兩個資料元素具有相同的值，在排序前後它們的相互位置發生顛倒，則稱該排序演算法是不穩定的。下列四種排序方法中是穩定的排序方法。
（a）shell排序b）快速排序
（c）歸併排序d）簡單選擇排序
5．若表r在排序前已按鍵值遞增順序排列，則演算法的比較次數最少。
（a）直接插入排序b）快速排序
（c）歸併排序d）選擇排序
二、填空題（每空 1 分，共5分）
1. 已知完全二叉樹的第5層有8個結點(根結點在第1層), 則其葉結點數是
2. 在有n個葉結點的huffman樹中, 共有_____個結點。
3. 採用____ ____結構來儲存和表示完全二叉樹是最有效的。
4. 當記錄個數比較少且基本有序時，_____是最有效的排序方法。
5. 內部排序問題的時間複雜度的下限是
三、判斷題（若正確，在括號內打「」，否則打「×」；每題1分，共5分）
1．沒有乙個結點的二叉樹稱為空樹
2．一棵二叉樹不能儲存在一維陣列中
3．歸併排序即適合內排序，也適合外排序
4．快速排序在最差情況下的時間複雜度是o（n2），此時它的效能並不比氣泡排序更好
5．刪除二叉排序樹中的乙個結點, 再重新插入進去, 一定能得到原來的二叉排序樹
四、解析題（每題10分，共50分）
1． 根據下面的字母/頻率表構造一棵huffman樹, 並給出各字母的huffman編碼。
2． 已知一棵二叉樹如下，請分別寫出按前序、中序、後序和層次遍歷時得到的結點序列。
3．請證明非空滿二叉樹的葉結點數等於其分支結點數加1。
4．請畫出把如下的完全二叉樹構建成最大值堆的過程。
5．採用直接插入排序演算法, 對關鍵字序列(49, 38, 65, 97, 76, 13, 27 )按從小到大的次序進行排序, 寫出每趟排序的結果。
五、演算法設計題（每題10分，共30分）
1．下面給出了氣泡排序的演算法，請在演算法的空缺處填入適當內容，使之能夠正常工作，得到乙個遞增的序列。
void bubsort(elem a, int n)
} }
2．試設計乙個前序周遊二叉樹的函式。
3．編寫求二叉樹的結點數目的演算法。
湖南大學資料結構考試重點
資料結構 複習提綱 一 基礎知識 1 二 應用 5 三 演算法 5 四 題型及樣題 6 第1章緒論 1 什麼是資料結構，分類 2 抽象資料型別的形式定義 3 邏輯結構 物理結構 儲存結構 4 時間複雜度 第2章線性表 5 線性表的定義和術語 6 線性表的儲存結構 順序表鏈式表 線性鍊錶 單鏈表 迴圈...
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...