南昌航空大學(xué)2020年研究生入學(xué)考試初試大綱

1、南昌航空大學(xué)2020年研究生入學(xué)考試初試大綱考試科目名稱：數(shù)據(jù)結(jié)構(gòu)考試科目代碼：817考試形式：筆試考試時(shí)間：180分鐘滿分：150分參考書目：數(shù)據(jù)結(jié)構(gòu)（C 語言版）， 嚴(yán)蔚敏、吳偉民編 著，清華大學(xué)出版社，2007 年。及配套題集一、試卷結(jié)構(gòu)：解答題(包括證明題)6小題，每題10分，共60分算法設(shè)計(jì)題6小題，每題15分，共90分二、考試范圍： 緒論 考核知識(shí)點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；抽象數(shù)據(jù)類型；算法的時(shí)間復(fù)雜度和空間復(fù)雜度 考核要求1) 理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語；2) 掌握抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；3) 掌握算法的基本概念和算法的性能分析方法。 考核重點(diǎn)1) 數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

2、；2) 算法的時(shí)間復(fù)雜度分析。 線性表 考核知識(shí)點(diǎn)線性表的抽象數(shù)據(jù)類型定義；線性表的兩類存儲(chǔ)結(jié)構(gòu)（順序和鏈?zhǔn)剑┑谋硎九c實(shí)現(xiàn)；線性表的兩類存儲(chǔ)結(jié)構(gòu)的比較 考核要求1) 熟練掌握線性表的兩類存儲(chǔ)結(jié)構(gòu)的表示及其基本操作的實(shí)現(xiàn)；2) 能對(duì)上述操作的時(shí)間和空間復(fù)雜度進(jìn)行分析；3) 熟練掌握在各種鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)；4) 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。 考核重點(diǎn)1) 要求滿足一定時(shí)間性能和空間性能的線性表的算法設(shè)計(jì)；2) 設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。例如：實(shí)現(xiàn)兩張線性表的按條件合并，或一張表的有條

3、件拆分、逆置、刪除指定位置或指定條件的元素，或集合的相關(guān)運(yùn)算（并集、交集、差集），或約瑟夫環(huán)問題，或一元稀疏多項(xiàng)式計(jì)算器，等等。 棧和隊(duì)列 考核知識(shí)點(diǎn)棧和隊(duì)列的特性；棧和隊(duì)列的表示及實(shí)現(xiàn)；棧在函數(shù)調(diào)用中所起的作用；棧和隊(duì)列的典型應(yīng)用 考核要求1) 熟練掌握棧和隊(duì)列兩種抽象數(shù)據(jù)類型的特點(diǎn)；2) 熟練掌握棧和隊(duì)列的實(shí)現(xiàn)方法；3) 深入理解遞歸算法執(zhí)行過程中棧的狀態(tài)的變化；4) 熟練掌握遞歸算法的設(shè)計(jì)；5) 深入了解棧和隊(duì)列的特點(diǎn)，以便在實(shí)際問題背景下靈活運(yùn)用棧和隊(duì)列。 考核重點(diǎn)1) 遞歸算法的設(shè)計(jì)；2) 利用棧或隊(duì)列解決相關(guān)的應(yīng)用問題。例如：括號(hào)匹配的檢驗(yàn)，算術(shù)表達(dá)式求值，皇后問題，背包問題，迷宮

4、問題，等等。 串 考核知識(shí)點(diǎn)串的抽象數(shù)據(jù)類型；串的表示與實(shí)現(xiàn)；串的模式匹配算法 考核要求1) 掌握串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法；2) 熟練掌握串的模式匹配算法；3) 串匹配的KMP算法；4) 了解串操作的應(yīng)用方法和特點(diǎn)。 考核重點(diǎn)串的模式匹配算法。 數(shù)組 考核知識(shí)點(diǎn)數(shù)組的抽象數(shù)據(jù)類型定義和表示；特殊矩陣的壓縮存儲(chǔ)方法；稀疏矩陣的壓縮存儲(chǔ)方法及運(yùn)算的實(shí)現(xiàn) 考核要求1) 熟練掌握數(shù)組的兩種存儲(chǔ)表示方法，掌握數(shù)組在以行或列為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；2) 掌握特殊矩陣壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；3) 熟練掌握稀疏矩陣的表示方法及其運(yùn)算。 考核重點(diǎn)1) 數(shù)組、特殊矩陣（對(duì)稱矩陣、上/

5、下三角矩陣）的地址計(jì)算方法；2) 稀疏矩陣的三元組順序表表示方法及其快速轉(zhuǎn)置算法。 3) 能夠從空間復(fù)雜度的角度分析稀疏矩陣的壓縮存儲(chǔ)的優(yōu)點(diǎn)及其適用場(chǎng)合。 樹和二叉樹 考核知識(shí)點(diǎn)二叉樹的性質(zhì)；二叉樹的存儲(chǔ)表示；各種二叉樹遍歷策略的遞歸和（先序、中序）非遞歸算法；二叉樹遍歷算法的應(yīng)用；線索二叉樹；哈夫曼樹及應(yīng)用 考核要求1) 熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；2) 熟悉二叉樹的常用存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；3) 熟練掌握各種二叉樹遍歷策略的遞歸和（先序、中序、層次）非遞歸算法；4) 能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；5) 了解遞歸遍歷過程中棧的作用和狀態(tài)；6) 了解遞歸算法轉(zhuǎn)化為非

6、遞歸算法的常用方法；7) 熟悉樹的常用存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)；8) 熟練掌握樹、森林與二叉樹的轉(zhuǎn)換方法；9) 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。 考核重點(diǎn)1) 二叉樹的性質(zhì)及其證明方法；2) 二叉樹的遞歸遍歷算法及其應(yīng)用；3) 二叉樹的非遞歸算法及其應(yīng)用；4) 哈夫曼樹的構(gòu)建及編碼。 圖 考核知識(shí)點(diǎn)圖的定義和術(shù)語；圖的常用存儲(chǔ)結(jié)構(gòu)；圖的兩種遍歷策略；圖的典型應(yīng)用：連通分量和最小生成樹，拓?fù)渑判?，關(guān)鍵路徑，最短路徑 考核要求1) 熟悉圖的常用存儲(chǔ)結(jié)構(gòu)及圖的構(gòu)造算法；2) 熟練掌握?qǐng)D的兩種遍歷策略；3) 能應(yīng)用圖的遍歷算法求解以下問題：最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑和最短路徑問題。 考

7、核重點(diǎn)1) 圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法；2) 應(yīng)用圖的上述遍歷算法求解以下問題：最小生成樹、拓?fù)渑判?、關(guān)鍵路徑和最短路徑。 查找 考核知識(shí)點(diǎn)順序表和有序表的查找；靜態(tài)樹表；索引順序表；二叉排序樹；B+樹和B-樹；哈希表 考核要求1) 熟練掌握順序表和有序表的查找算法；2) 熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系，掌握次優(yōu)二叉樹的構(gòu)造方法；3) 熟練掌握二叉排序樹的構(gòu)造、查找和刪除算法；4) 了解二叉平衡樹的維護(hù)平衡方法；5) 理解B+樹、B-樹和鍵樹的特點(diǎn)以及建樹過程；6) 熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性差別；7) 了解各種查

8、找方法所適應(yīng)的不同場(chǎng)合及等概率情況下查找成功的平均查找長(zhǎng)度。 考核重點(diǎn)1) 折半查找算法；2) 二叉排序樹的構(gòu)造、查找和刪除算法；3) B+樹、B-樹和鍵樹的建樹過程；4) 哈希表的構(gòu)造方法及其與其它結(jié)構(gòu)表的實(shí)質(zhì)性差別；5) 各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。 排序 考核知識(shí)點(diǎn)插入排序；交換排序；選擇排序；歸并排序；基數(shù)排序 考核要求1) 深刻理解內(nèi)部排序的定義和各種排序方法的特點(diǎn)、所適應(yīng)的不同場(chǎng)合，并能加以靈活應(yīng)用；2) 了解各種方法的排序過程及其依據(jù)的原則；3) 掌握各種排序方法的時(shí)間、空間復(fù)雜度和穩(wěn)定性分析方法；4) 能從“運(yùn)行時(shí)長(zhǎng)”、“關(guān)鍵字的比較次數(shù)”、“數(shù)據(jù)元素的移動(dòng)次數(shù)”三方面分析各種方法的時(shí)間性能。 考核重點(diǎn)1) 分析各種內(nèi)部