《資料結構》複習提綱
一、 基礎知識 1
二、 應用 5
三、 演算法 5
四、 題型及樣題 6
第1章緒論
1． 什麼是資料結構，分類
2． 抽象資料型別的形式定義
3． 邏輯結構、物理結構（儲存結構）
4． 時間複雜度
第2章線性表、
5． 線性表的定義和術語
6． 線性表的儲存結構
順序表鏈式表：線性鍊錶（單鏈表）、迴圈鍊錶、雙向鍊錶
靜態鍊錶
第3章棧和佇列
7． 棧
順序棧鏈式棧8． 佇列
順序佇列：迴圈佇列
鏈式佇列
第5章陣列和廣義表
9． 陣列的特點
10． 陣列的順序表示
11． 二維陣列的兩種儲存方式
以列序為主序
以行序為主序
12． 矩陣的壓縮儲存
特殊矩陣
稀疏矩陣（三元組表）
13． 廣義表的定義
表頭，表尾
表長，深度
第6章樹
14． 樹的定義和術語
15． 二叉樹的定義和術語
16． 滿二叉樹與完全二叉樹
17． 二叉樹的性質
18． 二叉樹的儲存
順序 鏈式：二叉鍊錶
19． 遍歷二叉樹
先序遍歷
中序遍歷
後序遍歷
層次遍歷
20． 線索、線索二叉樹、線索鍊錶
ltag和rtag的作用
21． 樹的儲存結構
雙親表示法
孩子表示法
孩子兄弟表示法
22． 樹與二叉樹之間的轉換
23． 樹的遍歷
先根（對應二叉樹的先序）
後根（對應二叉樹的中序）
層次24． 樹的帶權路徑長度
25． 哈夫曼樹（最優二叉樹）
26． 字首編碼、哈夫曼編碼
第7章圖
27． 圖的定義和術語
28． 圖的儲存結構
鄰接矩陣
鄰接表29． 圖的遍歷
深度優先搜尋（dfs，類似樹的先根遍歷）
廣度優先搜尋（bfs，類似樹的層次遍歷）
30． 最小生成樹：
prim演算法
kruskal演算法
31． 有向無環圖
32． aov網和aoe網
33． 拓撲排序問題
34． 關鍵路徑問題
35． 最短路徑問題
單源最短路徑－dijkstra演算法
多源最短路徑－floyd演算法
第9章查詢
36． 靜態查詢表和動態查詢表
37． 關鍵字、主關鍵字、次關鍵字
38． 平均查詢長度
39． 靜態查詢表
順序表的查詢
有序表的查詢：折半查詢、折半查詢判定樹
40． 動態查詢表
二叉排序樹
平衡二叉樹
b樹和b+樹
41． 雜湊函式、雜湊位址、雜湊表、衝突、同義詞
42． 雜湊函式的構造
43． 位址衝突的處理
44． 裝填因子
第10章內部排序
45． 排序方法的穩定性和時間複雜度
46． 插入排序
直接插入排序
希爾排序
47． 交換排序
氣泡排序
快速排序
48． 選擇排序
簡單選擇排序
堆排序49． 歸併排序
2-路歸併排序
50． 基數排序
1. 分析簡單程式段的時間複雜度
2. 利用棧進行表示式求值
3. 根據下標計算陣列元素的儲存位置
4. 求字串的next值和nextval值。
5. 利用二叉樹的性質求二叉樹的深度、結點數和葉子結點數等。
6. 根據給定的二叉樹寫出其前序、中序和後序遍歷序列
7. 根據二叉樹的前序（或後序）和中序遍歷序列，構造出對應的二叉樹
8. 計算樹的帶權路徑長度
9. 根據給定的字母/頻率表構造哈夫曼樹（或靜態三叉鍊錶），並給出各字母的哈夫曼編碼
10. 二叉樹、樹和森林的相互轉換
11. 根據圖構造鄰接矩陣或鄰接表，或根據鄰接矩陣或鄰接表構造圖
12. 求圖的深度、廣度優先搜尋頂點序列
13. 用prim演算法構造圖的最小生成樹。
14. 用dijkstra演算法求單源最短路徑。
15. 根據給定的圖或鄰接表構造頂點的拓撲序列
16. 折半查詢過程及其判定樹。
17. 二叉排序樹的插入與查詢
18. 平衡二叉樹的建立過程。
19. 雜湊表的插入及查詢
20. 根據關鍵字的查詢概率，求查詢成功時的平均查詢長度
21. 寫出按某種排序演算法進行排序時第一趟的詳細過程和每一趟的結果（希爾排序，快速排序，堆排序，歸併排序，基數排序）
1． 資料型別定義：順序表、鍊錶、二叉鍊錶、圖的鄰接矩陣和鄰接表
2． 順序表：插入，刪除
3． 鏈式表：插入，刪除
4． 二叉樹/樹：遍歷演算法及應用，哈夫曼樹演算法
5． 圖：遍歷演算法及應用，拓撲排序演算法
1． 選擇題（2』*10=20』）
例：對有n個記錄的有序表採用折半查詢，其平均查詢長度的量級為（ ）
2． 填空題（2』*10=20』）
例：在單鏈表中，指標p 所指結點為最後乙個結點的條件是（ ）。
3． 應用題（4~5個，50』）
例：已知二叉樹的前序和中序遍歷序列如下, 畫出該二叉樹。
前序遍歷序列: abcdefghij 中序遍歷序列: cbedaghfji
4． 演算法題（1個，10』）
例：已知二叉樹用二叉鍊錶儲存，請寫出其型別定義，並設計乙個計算二叉樹的葉子結點個數演算法。
湖南大學資料結構期末課程試卷
湖南大學課程考試試卷 課程名稱 數位電路與邏輯設計 試卷編號 考試時間 120分鐘 一 填空題 每空2分，共10分 1 39.75 1016 2 asic可分為和可程式設計asic programmable asic 3 數字系統分為以下六個層次 系統級邏輯單元級 邏輯門級矽片級。二 單選題 在本題...
湖南大學資料結構複習題
課程考試試卷 一 單選題 每小題 2 分，共10分，本題所給四個答案中只有乙個是正確的 1 將含有100個結點的完全二叉樹從根結點開始順序編號，根結點為第0號，其他結點自上而下，同一層從左向右連續編號，則編號最小的葉子結點的編號為 a 47b 48c 49d 50 2 對一顆二叉排序樹進行得到的結點...
資料結構考試重點
資料結構 第一章緒論 1 資料結構的定義 按照某種邏輯關係組織起來的資料集 2 資料主要分為兩大類 數值型資料和非數值型別資料。數值型資料主要包括整數 實數和複數等 非數值型別資料報括字元 字串 文字 聲音 圖形 影象等。3 資料結構的邏輯結構是指資料元素的集合以及定義在該集合上的資料元素之間的一種...