《數(shù)據(jù)結(jié)構(gòu)》考試大綱
(滿分 100 分，時(shí)限 90 分鐘)
一、選用教材
李剛、劉萬(wàn)輝，數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版)，高等教育出版社，2017 年。
二、考試范圍和內(nèi)容
第一章 緒論及C語(yǔ)言介紹
識(shí)記：
(1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的基本概念;
(2)算法的概念、性質(zhì)和目標(biāo)。
領(lǐng)會(huì)：
(1)數(shù)據(jù)結(jié)構(gòu)的三種邏輯結(jié)構(gòu)和兩種存儲(chǔ)結(jié)構(gòu)表示方法;
(2)數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的概念。
運(yùn)用：
(1)算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。
第二章 線性表的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)線性表的定義和抽象數(shù)據(jù)類(lèi)型。
領(lǐng)會(huì)：
(1)順序表的定義和存儲(chǔ)結(jié)構(gòu);
(2) 單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法;
(3) 順序表、單鏈表的優(yōu)缺點(diǎn)。
運(yùn)用：
(1)線性表的順序表示和實(shí)現(xiàn)。線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn);
(2) 單鏈表、循環(huán)單鏈表、雙向鏈表的存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn);
(3) 順序表上的插入、刪除等操作及其平均時(shí)間性能分析。
第三章 棧和隊(duì)列的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)棧的定義和特點(diǎn)。棧頂和棧底相關(guān)術(shù)語(yǔ);
(2)隊(duì)列的概念和特點(diǎn)。隊(duì)首和隊(duì)尾相關(guān)術(shù)語(yǔ)。
領(lǐng)會(huì)：
(1)順序堆棧的存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn);
(2) 鏈?zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn);
(3) 順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)、順序循環(huán)隊(duì)列的表示和實(shí)現(xiàn);
(4) 鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)。
運(yùn)用：
(1)棧和隊(duì)列的應(yīng)用。
第四章 字符串的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)串的定義、空串、空格串、子串、主串、串相等。
領(lǐng)會(huì)：
(1)串的基本操作。
運(yùn)用：
(1)模式匹配的原理及其 Brute-Force 算法
第五章 二維數(shù)組及廣義表的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)數(shù)組的定義;
(2)廣義表的定義。
領(lǐng)會(huì)：
(1)特殊矩陣和稀疏矩陣的概念及其壓縮存儲(chǔ);
(2)廣義表的存儲(chǔ)結(jié)構(gòu)與操作實(shí)現(xiàn)。
運(yùn)用：
(1)數(shù)組的實(shí)現(xiàn)機(jī)制。計(jì)算數(shù)組元素的地址計(jì)算公式。
第六章 樹(shù)和二叉樹(shù)的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)樹(shù)的定義、相關(guān)術(shù)語(yǔ)、表示方法和存儲(chǔ)結(jié)構(gòu);
(2)二叉樹(shù)的路徑、路徑長(zhǎng)度、帶權(quán)路徑長(zhǎng)度、哈夫曼樹(shù)的概念。
領(lǐng)會(huì)：
(1)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)——順序表示法和鏈表表示法;
(2)二叉樹(shù)的操作實(shí)現(xiàn)。
運(yùn)用：
(1)二叉樹(shù)、完全二叉樹(shù)、滿二叉樹(shù)的定義和性質(zhì);
(2) 二叉樹(shù)的三種遍歷方法及相應(yīng)的遞歸算法;
(3) 哈夫曼樹(shù)的構(gòu)造，哈夫曼編碼方法;
(4) 樹(shù)與二叉樹(shù)的轉(zhuǎn)換、樹(shù)的遍歷。
第七章 圖的結(jié)構(gòu)分析與應(yīng)用
識(shí)記：
(1)圖的定義和常用術(shù)語(yǔ);
(2) 生成樹(shù)和最小生成樹(shù)的概念;
(3) 最短路徑及相關(guān)概念;
(4) AOE 網(wǎng)、關(guān)鍵路徑、關(guān)鍵活動(dòng)的概念。
領(lǐng)會(huì)：
(1)鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖操作的實(shí)現(xiàn);
(2)圖的深度和廣度優(yōu)先遍歷算法。
運(yùn)用：
(1)圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ)結(jié)構(gòu);
(2) 構(gòu)造最小生成樹(shù)的普里姆算法和克魯斯卡爾算法;
(3) 求最短路徑的狄克斯特拉算法。
第八章 查找的分析與應(yīng)用
識(shí)記：
(1)查找的基本概念、分類(lèi)、平均查找長(zhǎng)度。
領(lǐng)會(huì)：
(1)順序查找、二分查找、分塊查找的基本思想與實(shí)現(xiàn)方法;
(2)二叉排序樹(shù)的查找、插入和刪除算法。
運(yùn)用：
(1)散列表的基本概念、構(gòu)造方法和沖突解決方法;
(2) 散列表的查找算法;
(3) 各種查找算法的性能分析及比較。
第九章 排序的分析與應(yīng)用
識(shí)記：
(1)排序的概念、分類(lèi);
(2)排序算法好壞的評(píng)判標(biāo)準(zhǔn)、排序方法的穩(wěn)定性。
領(lǐng)會(huì)：
(1)直接選擇排序的基本思想;
(2) 直接插入排序的基本思想;
(3) 冒泡排序的基本思想;
(4) 希爾排序的基本思想;
(5) 快速排序的基本思想。
運(yùn)用：
(1)直接插入排序、冒泡排序、直接選擇排序算法的實(shí)現(xiàn);
(2) 各種內(nèi)部排序方法的比較;
(3) 各種排序算法的性能分析和評(píng)價(jià)。
三、考核方式
1. 采取筆試，閉卷的形式進(jìn)行考核。
2. 題型結(jié)構(gòu)：選擇題、填空題、判斷題、程序分析填空題、算法設(shè)計(jì)題、綜合應(yīng)用題等。
3. 試題難易度：難度適中。基礎(chǔ)題、中等難度題和難題比例分別大致控制在50%、30%、20%。
