2021廈門大學845數據結構課程研究生參考書目 正文

845數據結構課程考試內容范圍：
在考查基本概念、基本知識、基本方法的基礎上，注重考查學生運用基本知識來分析和解決實際問題的能力，注重考查算法和程序設計的能力。
考查要點：
1.數據結構和算法：數據結構、存儲結構的概念；數據類型與抽象數據類型；算法的概念，用C/C++描述算法和程序設計，算法分析初步
2.線性表：線性表的定義和基本操作；線性表的抽象數據類型；線性表的順序存儲結構，應用舉例；線性表的鏈式存儲結構（單鏈表，雙鏈表，循環鏈表），應用舉例。
3.棧：棧的定義和基本操作；棧的抽象數據類型；順序棧，鏈式棧；棧和遞歸算法，算術表達式求值，其它應用。
4.隊列：隊列的定義和基本操作；隊列的抽象數據類型；順序隊列，鏈式隊列；雙端隊列的定義和基本操作；應用舉例。
5.數組和廣義表
（1）數組：數組的定義和基本操作；數組的順序存儲結構，應用舉例；特殊矩陣和稀疏，矩陣的壓縮存儲
（2）廣義表：廣義表的定義和基本操作，廣義表的抽象數據類型，廣義表的存儲結構。*廣義表運算的實現舉例
6.字符串：字符串的定義和基本操作，字符串的存儲結構，字符串操作的實現舉例，字符串和模式匹配
7.樹和二叉樹：樹的基本概念和基本操作，樹的抽象數據類型；二叉樹的概念和性質，特殊二叉樹；二叉樹的存儲結構；二叉樹的生成與建立；遍歷二叉樹：前序遍歷，中序遍歷，后序遍歷，層次遍歷；二叉樹其它操作實現舉例；線索二叉樹的概念和存儲結構，二叉樹的線索化，線索二叉樹的遍歷；樹的存儲結構，樹與二叉樹之間的轉換，森林與二叉樹之間的轉換，樹和森林的遍歷；樹的路徑長度和帶權路徑長度，哈夫曼樹（Huffman）的概念，哈夫曼算法，哈夫曼編碼樹；二叉排序樹的的概念和基本操作，二叉排序樹的建立，二叉排序樹其它操作實現舉例
8.圖：圖的基本概念和基本操作，圖的抽象數據類型；圖的存儲結構：數組表示法（鄰接矩陣）；鄰接表，逆鄰接表，十字鏈表；鄰接多重表；圖的遍歷：深度優先搜索法，寬度優先搜索法，求圖的連通分量；生成樹、最小生成樹的概念；克魯斯卡爾（Kruskal）算法，普里姆（Prim）算法。*從一個頂點到其余各頂點的最短路徑，每對頂點之間的最短路徑。*拓撲排序和關鍵路徑
9.查找：查找的概念，關鍵字比較次數，平均查找長度；順序表的查找：順序查找，折半查找，分塊查找；樹表的查找：二叉排序樹，平衡二叉樹；*哈希（Hash）表的查找：哈希表的概念，哈希函數構造方法，哈希表的建立和查找，沖突處理方法
10.排序：排序的概念；排序的穩定性；比較關鍵字次數，移動記錄次數；順序表的排序，鏈接表（單鏈表）的排序；內排序方法與算法；交換排序：冒泡排序，快速排序；插入排序：直接插入排序，2路插入排序，折半插入排序，希爾排序；選擇排序：直接選擇排序，錦標賽排序，堆排序；歸并排序；基數排序；各種排序算法的評價和應用
11.文件：文件的基本概念，文件的基本操作；文件的物理結構：順序文件，索引文件與索引順序文件，直接存取文件，鏈接文件和多重鏈表文件，倒排文件。
說明：帶“*”號的章節為一般考查內容，其余為重點考查內容。

廈門大學

本文來源：http://m.btfokj.cn/xiamendaxue/cankaoshumu_402992.html