《數(shù)據(jù)結構》考試大綱

(滿分 100 分，時限 90 分鐘)

一、選用教材

李剛、劉萬輝，數(shù)據(jù)結構(C 語言版)，高等教育出版社，2017 年。

二、考試范圍和內(nèi)容

第一章 緒論及C語言介紹

識記：

(1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的基本概念;

(2)算法的概念、性質和目標。

領會：

(1)數(shù)據(jù)結構的三種邏輯結構和兩種存儲結構表示方法;

(2)數(shù)據(jù)結構和抽象數(shù)據(jù)類型的概念。

運用：

(1)算法的時間復雜度和空間復雜度分析。

第二章 線性表的結構分析與應用

識記：

(1)線性表的定義和抽象數(shù)據(jù)類型。

領會：

(1)順序表的定義和存儲結構;

(2) 單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法;

(3) 順序表、單鏈表的優(yōu)缺點。

運用：

(1)線性表的順序表示和實現(xiàn)。線性表的鏈式表示和實現(xiàn);

(2) 單鏈表、循環(huán)單鏈表、雙向鏈表的存儲結構和操作實現(xiàn);

(3) 順序表上的插入、刪除等操作及其平均時間性能分析。

第三章 棧和隊列的結構分析與應用

識記：

(1)棧的定義和特點。棧頂和棧底相關術語;

(2)隊列的概念和特點。隊首和隊尾相關術語。

領會：

(1)順序堆棧的存儲結構和操作實現(xiàn);

(2) 鏈式棧的存儲結構和操作實現(xiàn);

(3) 順序隊列的存儲結構、順序循環(huán)隊列的表示和實現(xiàn);

(4) 鏈式隊列的存儲結構和實現(xiàn)。

運用：

(1)棧和隊列的應用。

第四章 字符串的結構分析與應用

識記：

(1)串的定義、空串、空格串、子串、主串、串相等。

領會：

(1)串的基本操作。

運用：

(1)模式匹配的原理及其 Brute-Force 算法

第五章 二維數(shù)組及廣義表的結構分析與應用

識記：

(1)數(shù)組的定義;

(2)廣義表的定義。

領會：

(1)特殊矩陣和稀疏矩陣的概念及其壓縮存儲;

(2)廣義表的存儲結構與操作實現(xiàn)。

運用：

(1)數(shù)組的實現(xiàn)機制。計算數(shù)組元素的地址計算公式。

第六章 樹和二叉樹的結構分析與應用

識記：

(1)樹的定義、相關術語、表示方法和存儲結構;

(2)二叉樹的路徑、路徑長度、帶權路徑長度、哈夫曼樹的概念。

領會：

(1)二叉樹的存儲結構——順序表示法和鏈表表示法;

(2)二叉樹的操作實現(xiàn)。

運用：

(1)二叉樹、完全二叉樹、滿二叉樹的定義和性質;

(2) 二叉樹的三種遍歷方法及相應的遞歸算法;

(3) 哈夫曼樹的構造，哈夫曼編碼方法;

(4) 樹與二叉樹的轉換、樹的遍歷。

第七章 圖的結構分析與應用

識記：

(1)圖的定義和常用術語;

(2) 生成樹和最小生成樹的概念;

(3) 最短路徑及相關概念;

(4) AOE 網(wǎng)、關鍵路徑、關鍵活動的概念。

領會：

(1)鄰接矩陣存儲結構下圖操作的實現(xiàn);

(2)圖的深度和廣度優(yōu)先遍歷算法。

運用：

(1)圖的鄰接矩陣存儲結構和鄰接表存儲結構;

(2) 構造最小生成樹的普里姆算法和克魯斯卡爾算法;

(3) 求最短路徑的狄克斯特拉算法。

第八章 查找的分析與應用

識記：

(1)查找的基本概念、分類、平均查找長度。

領會：

(1)順序查找、二分查找、分塊查找的基本思想與實現(xiàn)方法;

(2)二叉排序樹的查找、插入和刪除算法。

運用：

(1)散列表的基本概念、構造方法和沖突解決方法;

(2) 散列表的查找算法;

(3) 各種查找算法的性能分析及比較。

第九章 排序的分析與應用

識記：

(1)排序的概念、分類;

(2)排序算法好壞的評判標準、排序方法的穩(wěn)定性。

領會：

(1)直接選擇排序的基本思想;

(2) 直接插入排序的基本思想;

(3) 冒泡排序的基本思想;

(4) 希爾排序的基本思想;

(5) 快速排序的基本思想。

運用：

(1)直接插入排序、冒泡排序、直接選擇排序算法的實現(xiàn);

(2) 各種內(nèi)部排序方法的比較;

(3) 各種排序算法的性能分析和評價。

三、考核方式

1. 采取筆試，閉卷的形式進行考核。

2. 題型結構：選擇題、填空題、判斷題、程序分析填空題、算法設計題、綜合應用題等。

3. 試題難易度：難度適中?；A題、中等難度題和難題比例分別大致控制在50%、30%、20%。