江蘇城市職業學院五年制高職
《資料結構》課程複習提綱
2008 級計算機應用技術專業（第五學期）用
一、考核說明
本複習提綱依據的教材為：許樂平主編，**廣播電視大學出版社出版的《資料結構——c++描述》，許樂平主編，**廣播電視大學出版社出版的《資料結構實驗指導與測試》。
考核形式：考試課。
考核方法：期末考試以筆試為主，試卷由省校統一命題，閉卷考試，時間120分鐘。題型和分數分配：
填空題（20分），選擇題（30分），分析填充題（10分），判斷題（10分），問答題（30分）。
複習方法：依平時的教學為主，結合教學要求和複習大綱，結合指定的教材，掌握基本知識。
二、基本知識點
第一章緒論
1、基本概念的掌握（資料、資料元素、資料物件、資料邏輯結構、資料物理結構、資料結構、資料型別）。
2、演算法的時間複雜度計算（書中例題）。
習題：書後p21 一，二（1、2、3）
第二章線性表
1、線性表的定義。
2、線性表的順序儲存結構及基本操作（重點掌握插入元素和刪除元素）。
3、線性表的單鏈表儲存結構及基本操作（重點掌握表頭、表尾插入結點操作）。
4、了解迴圈鍊錶的結構。
5、線性表的兩種儲存結構的比較。
習題：p62-63 一，二（1-4，
第三章棧和佇列
1、棧的定義。
2、棧的順序儲存表示及基本操作（重點掌握入棧、出棧）。
3、棧的鏈結儲存表示及基本操作（重點掌握入鏈棧，出鏈棧）。
4、掌握逆波蘭式。
5、佇列的定義。
6、佇列的鏈結儲存表示及基本操作（重點掌握入隊、出隊）。
習題：p107-109 一（1-7），二（1-6），三（1-3）
第四章陣列與廣義表
1、陣列的概念（一維和二維陣列）。
2、陣列的順序儲存結構（一維和二維陣列元素位址的計算）。
3、稀疏矩陣的定義。
4、稀疏矩陣的儲存結構（掌握三元組線性表和三元組順序表表示方法）。
5、廣義表的定義和應用（求廣義表的廣度和深度，取表頭、表尾的操作）。
習題：p130 一，二，三（1，2）
第五章樹與二叉樹
1、樹的定義、邏輯結構和儲存結構。
2、二叉樹的儲存結構。
3、遍歷二叉樹的三種遍歷方法。
4、樹和森林與二叉樹的轉換。
5、二叉排序樹的定義。
6、哈夫曼樹中的基本概念和應用。
習題：p174 一（1，2，4-7），二（1-6），三（1，4，5，6，8，9）
第六章圖
1、圖的定義、基本概念。
2、圖的鄰接矩陣表示法。
3、圖的深度優先遍歷和廣度優先遍歷。
4、最小生成樹的概念和構造（兩種演算法）。
習題：p216 一（1-6），二（1-4）。
第七章查詢
1、掌握順序查詢、折半查詢的方法和操作。
2、雜湊查詢的概念，雜湊函式的構造，解決衝突的方法。
習題：p238 一，二，三，四（2中平均查詢長度不要求）。
第九章排序
1、掌握插入排序、氣泡排序、選擇排序、堆排序、歸併排序的方法。
2、掌握直接選擇排序和氣泡排序的演算法。
習題:p267 一、二、三
注：《資料結構實驗指導與測試》中的模擬試題要求學生完成。
責任教師： 許小媛
2023年11月
資料結構 複習提綱
第二章線性表的概念 順序儲存和鏈結儲存的線性表的資料結構 特性 順序儲存的特性 查詢方便，不易擴充 鏈結儲存的特性 插入刪除方便 順序儲存和鏈結儲存的線性表的基本演算法 建立 插入 查詢 刪除等 鍊錶的其他形式 帶表頭 迴圈 雙向 雙向迴圈等 的概念及基本演算法 與一般鍊錶的不同處 帶表頭 便於其後...
資料結構複習提綱
如 以10,15 20,5,1,30,23為權值構造一棵哈夫曼樹並求出wpl，最後確定葉子結點的哈夫曼編碼。5 雜湊表的構造及在雜湊表上查詢的效率分析 6 拆半查詢的效能分析 通過判定樹 7 二叉排序樹的構造及其查詢的效能分析 8 二叉平衡樹的構造及其查詢效能分析 9 寫出各種排序下的資料變化過程 ...
資料結構複習提綱考試重點
一 基礎知識 第1章緒論 1 什麼是資料結構，分類 2 抽象資料型別的形式定義 3 邏輯結構 物理結構 儲存結構 4 什麼是演算法 5 時間複雜度 第2章線性表 6 線性表的定義和術語 7 線性表的儲存結構 順序錶鏈表 線性鍊錶 單鏈表 迴圈鍊錶 雙向鍊錶 第3章棧和佇列 8 棧 順序棧鏈式棧9 佇...