科目名稱 數(shù)據(jù)結(jié)構(gòu) 科目代碼 808

一、考試范圍

1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)項的概念及其相互間關(guān)系；數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的區(qū)別與聯(lián)系；抽象數(shù)據(jù)類型、算法的時間性能和空間性能分析方法。

2．線性表

線性表的基本概念；線性表的順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)定義，以及順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)的存儲分配特點(diǎn)；線性表順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)的插入、刪除和按關(guān)鍵字查找等基本算法實(shí)現(xiàn)，以及對相應(yīng)算法的時間性能分析和空間性能分析。

3．棧與隊列

棧與隊列的概念與基本操作；鏈隊列、循環(huán)隊列的組織方法與基本操作的實(shí)現(xiàn)；棧的應(yīng)用。

4．串

串的概念與串的表示和實(shí)現(xiàn)；串的基本操作的堆結(jié)構(gòu)實(shí)現(xiàn)；模式匹配算法與算法時間和空間性能分析。

5．?dāng)?shù)組與廣義表

多維數(shù)組的結(jié)構(gòu)特點(diǎn)及其存儲地址計算方法；矩陣的壓縮存儲思想、存儲結(jié)構(gòu)和存儲地址映射關(guān)系；廣義表的邏輯結(jié)構(gòu)及其存儲結(jié)構(gòu)。

6．樹與二叉樹

樹的基本概念；二叉樹的定義與性質(zhì)、順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)；二叉樹的遍歷算法；樹和森林的基本概念；哈夫曼樹與哈夫曼編碼。

7．圖

圖的基本概念、圖的鄰接矩陣和鄰接表的表示方法；圖的遍歷算法；圖的最小生成樹的概念及相關(guān)算法；圖的拓?fù)渑判颉㈥P(guān)鍵路徑與最短路徑算法。

8．查找

查找的基本概念；靜態(tài)查找表的實(shí)現(xiàn)；折半查找的實(shí)現(xiàn)；二叉排序樹的概念及實(shí)現(xiàn)；哈希表的思想，各種查找算法的性能分析。

9．排序

排序的基本概念；插入排序算法與算法性能分析；交換排序算法與算法性能分析；選擇排序算法與算法性能分析；歸并排序算法與算法性能分析；基數(shù)排序算法與算法性能分析；不同算法間性能對比。

二、考試形式及試卷結(jié)構(gòu)

考試形式：閉卷，筆試。

試卷結(jié)構(gòu)：1．單項選擇題； 2．簡答與計算題。

三、參考書目

《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏，吳偉民 編著，清華大學(xué)出版社，2012年。

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》，李春葆 編著，清華大學(xué)出版社，2013年。