考試科目：數(shù)據(jù)結(jié)構(gòu)
科目代碼：831
一、參考書目：
《數(shù)據(jù)結(jié)構(gòu)——用C語言描述.》(第二版)，耿國華 編，高等教育出版社，2015年
二、考試內(nèi)容范圍：
(一)數(shù)據(jù)結(jié)構(gòu)基本概念
1、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念。
2、數(shù)據(jù)結(jié)構(gòu)的發(fā)展和地位。
3、算法描述方法和算法設(shè)計的基本要求。
4、算法的評價標(biāo)準(zhǔn)和算法效率的度量方法。
(二)線性表
1、線性表的概念、定義、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。
2、線性表的順序結(jié)構(gòu)及其各種基本操作。
3、單鏈表、循環(huán)鏈表、雙向鏈表的存儲結(jié)構(gòu)及其各種基本操作。
(三)棧和隊列
1、棧的定義、表示、實現(xiàn)和應(yīng)用。
2、遞歸的概念和遞歸的實現(xiàn)過程。
3、隊列的定義以及其順序(循環(huán)隊列)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)。
(四)串
1、串的基本概念及其順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
2、串的各種基本操作。
3、串模式匹配算法。
(五)數(shù)組和廣義表
1、數(shù)組的順序存儲結(jié)構(gòu)。
2、稀疏數(shù)組的概念和壓縮存儲方法。
3、稀疏矩陣的三元組存儲結(jié)構(gòu)和基本操作。
4、疏矩陣的十字鏈表存儲結(jié)構(gòu)。
5、廣義表的基本概念及其存儲結(jié)構(gòu)。
(六)樹
1、樹的基本概念及其存儲結(jié)構(gòu)。
2、二叉樹的定義、性質(zhì)以及各種存儲結(jié)構(gòu)和遍歷算法。
3、線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法。
4、樹、森林與二叉樹間的轉(zhuǎn)換，樹和森林的遍歷算法。
5、哈夫曼樹的概念、存儲結(jié)構(gòu)和應(yīng)用
(七)圖
1、圖的基本概念及其鄰接矩陣、鄰接表存儲結(jié)構(gòu)的實現(xiàn)。
2、圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。
3、圖的連通性、最小生成樹、求最小生成樹算法。
4、有向無環(huán)圖的概念，拓?fù)渑判蚝完P(guān)鍵路徑算法。
5、帶權(quán)最短路徑的概念，最短路徑的算法
(八)查找
1、查找的概念及其效率的評價方法。
2、靜態(tài)查找表的概念，順序、折半和分塊查找算法。
3、動態(tài)查找表和二叉排序樹。
4、哈希表的含義，哈希函數(shù)的構(gòu)造和處理沖突的基本方法。
(九)內(nèi)部排序
1、插入類排序的算法：直接插入排序、希爾排序。
2、交換類排序的算法：冒泡排序、快速排序。
3、選擇類排序的算法：簡單選擇排序、堆排序。
4、歸并排序、基數(shù)排序的思想，外排序的概念。
三、試卷結(jié)構(gòu)及題型比例：
試卷結(jié)構(gòu)為：填空題、選擇題、判斷題、應(yīng)用題等。