《數(shù)據(jù)結構》考試大綱
(滿分 100 分，時限 90 分鐘)
一、選用教材
李剛、劉萬輝，數(shù)據(jù)結構(C 語言版)，高等教育出版社，2017 年。
二、考試范圍和內容
第一章 緒論及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) 各種內部排序方法的比較;
(3) 各種排序算法的性能分析和評價。
三、考核方式
1. 采取筆試，閉卷的形式進行考核。
2. 題型結構：選擇題、填空題、判斷題、程序分析填空題、算法設計題、綜合應用題等。
3. 試題難易度：難度適中?；A題、中等難度題和難題比例分別大致控制在50%、30%、20%。
