2021廈門大學(xué)845數(shù)據(jù)結(jié)構(gòu)課程研究生參考書目 正文

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

廈門大學(xué)

本文來源：http://www.qiang-kai.com/xiamendaxue/cankaoshumu_402992.html