課程二：《數(shù)據(jù)結(jié)構(gòu)》考試大綱
一、考試總體要求
1．基本理論知識(shí)
（l）什么是數(shù)據(jù)結(jié)構(gòu)、基本概念和基本術(shù)語(yǔ)，算法描述和算法分析。
（2）什么是線性表、在線性表上常進(jìn)行的基本操作以及這些操作分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)及復(fù)雜度分析。
（3）棧和隊(duì)列的定義、表示方法和實(shí)現(xiàn)。
（4）串的定義及其基本操作。
（5）數(shù)組的定義、運(yùn)算和存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)。
（6）樹的定義、基本術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)，二叉樹的定義和性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，哈夫曼樹。
（7）圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其各種操作。
（8）各種查找方式的算法、適用范圍及時(shí)間復(fù)雜度的分析。
（9）多種內(nèi)排序算法的基本思想和算法的時(shí)間復(fù)雜度分析，不同排序方法的比較。
2．基本技能
（1）能閱讀用C語(yǔ)言編寫的算法。
（2）能分析算法所完成的功能、運(yùn)行結(jié)果和時(shí)間復(fù)雜度。
（3）能根據(jù)要求用類C語(yǔ)言編寫算法。
3.工程應(yīng)用
（1）能用工程思維思考問(wèn)題。
（2）能用數(shù)據(jù)結(jié)構(gòu)的理論實(shí)現(xiàn)實(shí)際問(wèn)題求解。
二、考試知識(shí)點(diǎn)
1．緒論
（1）數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、（存儲(chǔ)）物理結(jié)構(gòu)、元素、結(jié)點(diǎn)等基本概念。抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。
（2）算法、算法的特性、如何用類C語(yǔ)言來(lái)描述算法。
（3）算法設(shè)計(jì)的基本要求以及計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。
2．線性表
（1）線性表的定義和操作。
（2）順序存儲(chǔ)線性表的實(shí)現(xiàn)和運(yùn)算。
（3）鏈?zhǔn)酱鎯?chǔ)線性表，帶有附加表頭結(jié)點(diǎn)和不帶附加表頭結(jié)點(diǎn)的單鏈表、循環(huán)鏈表和雙向鏈表的創(chuàng)建以及查找、插入、刪除等基本操作。
（4）利用線性表的設(shè)計(jì)電話本（創(chuàng)建以及查找、插入、刪除等基本操作）。
3．棧和隊(duì)列
（1）棧和隊(duì)列的定義、特點(diǎn)及其存儲(chǔ)結(jié)構(gòu)，棧和循環(huán)隊(duì)列的實(shí)現(xiàn)。
（2）棧和隊(duì)列的主要運(yùn)算。
（3）棧的應(yīng)用舉例，如：數(shù)制轉(zhuǎn)換、表達(dá)式求值等。
4．串和數(shù)組
（1）串的定義、空串、空格串。
（2）串的基本操作（求串的長(zhǎng)度，復(fù)制串，判斷串是否相等，求子串等）。
（3）串的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。
（4）串的模式匹配算法（BF算法）。
（5）一維數(shù)組和二維數(shù)組的實(shí)現(xiàn)機(jī)制
（6）特殊矩陣的壓縮存儲(chǔ)
（7）稀疏矩陣的壓縮存儲(chǔ)
5．樹和二叉樹
（1）樹的定義和術(shù)語(yǔ)。
（2）二叉樹（完全二叉樹、滿二叉樹）的定義和性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)（順序表示法和二叉鏈表表示法）。
（3）二叉樹三種遍歷的遞歸算法。
（4）利用哈夫曼樹實(shí)現(xiàn)字符串的壓縮/解壓處理
6．圖
（1）圖的定義。
（2）圖的基本術(shù)語(yǔ)。
①圖及無(wú)向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖、頂點(diǎn)的度、入度、出度、頂點(diǎn)間路徑、路徑長(zhǎng)度、環(huán)。
（3）圖的存儲(chǔ)結(jié)構(gòu)
①鄰接矩陣
②鄰接表（含逆鄰接表）
（4）遍歷圖
①深度優(yōu)先搜索遍歷圖的思想、算法及其時(shí)間復(fù)雜度。
②廣度優(yōu)先搜索遍歷圖的思想、算法及其時(shí)間復(fù)雜度。
（5）生成樹
①生成樹、最小生成樹的概念。
②最小生成樹的構(gòu)造過(guò)程（Prim算法和Kruskal算法）及其時(shí)間復(fù)雜度。
（6）利用網(wǎng)的遍歷思想尋找最短路徑。
7．排序
（1）排序的目的、分類和排序方法的穩(wěn)定性的定義。
（2）插入排序
①直接插入排序的算法。
②希爾排序的思想。
（3）選擇排序
①簡(jiǎn)單的選擇排序的算法。
②堆的定義、堆排序的思想。
（4）交換排序
①冒泡排序
②快速排序（重點(diǎn)理解）
（5）各種內(nèi)部排序方法的比較。
8．查找
（1）查找、關(guān)鍵字、平均查找長(zhǎng)度等概念。
（2）靜態(tài)查找表的查找算法及其效率（最壞和平均查找長(zhǎng)度）。
①順序查找。
②二分查找（重點(diǎn)理解）。
（3）動(dòng)態(tài)查找表
①二叉排序樹定義、構(gòu)造過(guò)程及其查找算法和效率。
（4）哈希表
①哈希表的特點(diǎn)。
②構(gòu)造哈希函數(shù)的方法（除留余數(shù)法等）。
③處理沖突的方法（開放定址法，重點(diǎn)是線性探測(cè)再散列；拉鏈法）。
三、網(wǎng)絡(luò)工程專業(yè)考試科目《專業(yè)綜合》
（1）C程序設(shè)計(jì)（第五版），譚浩強(qiáng)，清華大學(xué)出版社，2018年08月第5版；
（2）數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第6版，）朱戰(zhàn)立，電子工業(yè)出版社，2020年12月。
四：試卷結(jié)構(gòu)
（數(shù)據(jù)結(jié)構(gòu)部分，50分）
試卷題型比例：
選擇題約50%
填空題約30%
計(jì)算分析算法題約20%