一、 基礎知識
第1章緒論
1． 什麼是資料結構，分類
2． 抽象資料型別的形式定義
3． 邏輯結構、物理結構（儲存結構）
4． 什麼是演算法
5． 時間複雜度
第2章線性表、
6． 線性表的定義和術語
7． 線性表的儲存結構
順序錶鏈表 線性鍊錶（單鏈表）
迴圈鍊錶
雙向鍊錶
第3章棧和佇列
8． 棧
順序棧鏈式棧9． 佇列
順序佇列
鏈式佇列
第4章串
10． 串的模式匹配演算法
next和nextval陣列的計算
第5章陣列和廣義表
11． 陣列的特點
12． 陣列的順序表示
13． 二維陣列的兩種儲存方式
以列序為主序
以行序為主序
14． 根據下標計算陣列元素的儲存位置
15． 矩陣的壓縮儲存
特殊矩陣
稀疏矩陣（三元組表）
16． 廣義表的定義
表頭，表尾
表長，深度
第6章樹
17． 樹的定義和術語
18． 二叉樹的定義和術語
19． 滿二叉樹與完全二叉樹的定義
20． 二叉樹的性質
21． 二叉樹的儲存
順序 鏈式（二叉鍊錶）
22． 遍歷二叉樹
先序遍歷
中序遍歷
後序遍歷
層次遍歷
23． 線索、線索二叉樹、線索鍊錶
ltag和rtag的作用
24． 樹的儲存結構
雙親表示法
孩子表示法
孩子兄弟表示法
25． 樹與二叉樹之間的轉換
26． 樹的遍歷
先根（對應二叉樹的先序）
後根（對應二叉樹的中序）
層次27． 樹的帶權路徑長度的定義及計算
28． 哈夫曼樹（最優二叉樹）
29． 字首編碼、哈夫曼編碼
第7章圖
30． 圖的定義和術語
31． 圖的儲存結構
鄰接矩陣
鄰接表32． 圖的遍歷
深度優先搜尋（dfs，類似樹的先根遍歷）
廣度優先搜尋（bfs，類似樹的層次遍歷）
33． 最小生成樹
prim演算法
kruskal演算法
34． 有向無環圖
35． aov網和aoe網
36． 什麼是拓撲有序
37． 可進行拓撲排序的條件
38． 拓撲排序的方法
39． 什麼是關鍵路徑
40． 最短路徑問題
單源最短路徑－dijkstra演算法
第9章查詢
41． 靜態查詢表和動態查詢表
42． 關鍵字、主關鍵字、次關鍵字
43． 平均查詢長度的定義及計算
44． 靜態查詢表
順序表的查詢
有序表的查詢
折半查詢、折半查詢判定樹
45． 動態查詢表
二叉排序樹
平衡二叉樹的定義
46． 雜湊函式、雜湊位址、雜湊表、衝突、同義詞
47． 雜湊函式的構造
直接定址法
除留餘數法
48． 位址衝突的處理
線性探測法、二次探測法
再雜湊法
鏈位址法
第10章內部排序
49． 排序方法的穩定性
50． 各種排序的過程及時間複雜度
51． 插入排序
直接插入排序
希爾排序
52． 交換排序
氣泡排序
快速排序
53． 選擇排序
簡單選擇排序
堆排序54． 歸併排序
2-路歸併排序
55． 基數排序
二、 應用（重點複習）
1. 分析簡單程式段的執行時間代價
2. 描述利用棧進行表示式求值的過程。
3. 根據給定的二叉樹寫出其先序、中序和後序遍歷序列
4. 根據二叉樹的先序和中序遍歷序列，構造出對應的二叉樹
5. 根據二叉樹的中序和後序遍歷序列，構造出對應的二叉樹
6. 根據給定的字母/頻率表構造huffman樹，並給出各字母的huffman編碼
7. 根據一棵樹的雙親表構造出該樹
8. 根據一棵樹構造對應的二叉樹
9. 根據圖構造鄰接矩陣或鄰接表
10. 根據鄰接矩陣或鄰接表構造圖
11. 寫出圖的深度、廣度優先搜尋頂點序列
12. 按照prim演算法或kruskal演算法構造圖的最小生成樹
13. 根據給定的圖或鄰接表構造頂點的拓撲序列
14. 用dijkstra演算法求單源最短
15. 根據給出的資料序列構造折半查詢過程的判定樹。
16. 根據給出的關鍵值序列構造二叉排序樹
17. 在雜湊表中插入、查詢記錄
18. 給出一組關鍵字，寫出按某種排序演算法進行排序的第一趟的過程和每一趟的結果
三、 演算法（重點複習）
樹和圖的基本操作，涉及以下內容：
1． 順序表、鍊錶的處理
2． 棧、佇列的應用
3． 迴圈、遞迴的應用
四、 題型及樣題
1． 選擇題（2』*10=20』）
例：對有n個記錄的有序表採用折半查詢，其平均查詢長度的量級為（ ）
2． 填空題（2』*10=20』）
例：在單鏈表中，指標p 所指結點為最後乙個結點的條件是（ ）。
3． 應用題（4~5個，45』）
例：已知二叉樹的前序和中序遍歷序列如下, 畫出該二叉樹。
前序遍歷序列: abcdefghij 中序遍歷序列: cbedaghfji
4． 演算法題（1~2個，15』）
例：已知二叉樹用二叉鍊錶儲存，請寫出其型別定義，並設計乙個計算二叉樹的葉子結點個數演算法。
資料結構 複習提綱
第二章線性表的概念 順序儲存和鏈結儲存的線性表的資料結構 特性 順序儲存的特性 查詢方便，不易擴充 鏈結儲存的特性 插入刪除方便 順序儲存和鏈結儲存的線性表的基本演算法 建立 插入 查詢 刪除等 鍊錶的其他形式 帶表頭 迴圈 雙向 雙向迴圈等 的概念及基本演算法 與一般鍊錶的不同處 帶表頭 便於其後...
資料結構複習提綱
如 以10,15 20,5,1,30,23為權值構造一棵哈夫曼樹並求出wpl，最後確定葉子結點的哈夫曼編碼。5 雜湊表的構造及在雜湊表上查詢的效率分析 6 拆半查詢的效能分析 通過判定樹 7 二叉排序樹的構造及其查詢的效能分析 8 二叉平衡樹的構造及其查詢效能分析 9 寫出各種排序下的資料變化過程 ...
《資料結構》複習提綱2019
江蘇城市職業學院五年制高職 資料結構 課程複習提綱 2008 級計算機應用技術專業 第五學期 用 一 考核說明 本複習提綱依據的教材為 許樂平主編，廣播電視大學出版社出版的 資料結構 c 描述 許樂平主編，廣播電視大學出版社出版的 資料結構實驗指導與測試 考核形式 考試課。考核方法 期末考試以筆試為...