南昌航空大學2021年研究生入學考試初試大綱

    考試科目名稱：數(shù)據(jù)結(jié)構(gòu)（C語言版）

    考試科目代碼：961

    考試形式：筆試

    考試時間：180分鐘

    滿分：150分

    參考書目：

    1.嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：清華大學出版社，2017

    2.嚴蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)[M].北京：清華大學出版社，2017

    一、試卷結(jié)構(gòu)：

    解答題(包括證明題)6小題，每題10分，共60分

    算法設計題6小題，每題15分，共90分

    二、考試范圍：

    ⒈緒論

    ⑴考核知識點

    數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；抽象數(shù)據(jù)類型；算法的時間復雜度和空間復雜度

    ⑵考核要求

    1)理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語；

    2)掌握抽象數(shù)據(jù)類型的表示與實現(xiàn)；

    3)掌握算法的基本概念和算法的性能分析方法。

    ⑶考核重點

    1)數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；

    2)算法的時間復雜度分析。

    ⒉線性表

    ⑴考核知識點

    線性表的抽象數(shù)據(jù)類型定義；線性表的兩類存儲結(jié)構(gòu)（順序和鏈式）的表示與實現(xiàn)；線性表的兩類存儲結(jié)構(gòu)的比較

    ⑵考核要求

    1)熟練掌握線性表的兩類存儲結(jié)構(gòu)的表示及其基本操作的實現(xiàn)；

    2)能對上述操作的時間和空間復雜度進行分析；

    3)熟練掌握在各種鏈表結(jié)構(gòu)上實現(xiàn)線性表操作的基本方法，能在實際應用中選用適當?shù)逆湵斫Y(jié)構(gòu)；

    4)能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。

    ⑶考核重點

    1)要求滿足一定時間性能和空間性能的線性表的算法設計；

    2)設計有效算法解決與線性表相關(guān)的應用問題。例如：實現(xiàn)兩張線性表的按條件合并，或一張表的有條件拆分、逆置、刪除指定位置或指定條件的元素，或集合的相關(guān)運算（并集、交集、差集），或約瑟夫環(huán)問題，或一元稀疏多項式計算器，等等。

    ⒊棧和隊列

    ⑴考核知識點

    棧和隊列的特性；棧和隊列的表示及實現(xiàn)；棧在函數(shù)調(diào)用中所起的作用；棧和隊列的典型應用

    ⑵考核要求

    1)熟練掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點；

    2)熟練掌握棧和隊列的實現(xiàn)方法；

    3)深入理解遞歸算法執(zhí)行過程中棧的狀態(tài)的變化；

    4)熟練掌握遞歸算法的設計；

    5)深入了解棧和隊列的特點，以便在實際問題背景下靈活運用棧和隊列。

    ⑶考核重點

    1)遞歸算法的設計；

    2)利用?；蜿犃薪鉀Q相關(guān)的應用問題。例如：括號匹配的檢驗、算術(shù)表達式求值、皇后問題、背包問題、迷宮問題，等等。

    ⒋串

    ⑴考核知識點

    串的抽象數(shù)據(jù)類型；串的表示與實現(xiàn)；串的模式匹配算法

    ⑵考核要求

    1)掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法；

    2)熟練掌握串的模式匹配算法；

    3)串匹配的KMP算法；

    4)了解串操作的應用方法和特點。

    ⑶考核重點

    串的模式匹配算法。

    ⒌數(shù)組

    ⑴考核知識點

    數(shù)組的抽象數(shù)據(jù)類型定義和表示；特殊矩陣的壓縮存儲方法；稀疏矩陣的壓縮存儲方法及運算的實現(xiàn)

    ⑵考核要求

    1)熟練掌握數(shù)組的兩種存儲表示方法，掌握數(shù)組在以行或列為主的存儲結(jié)構(gòu)中的地址計算方法；

    2)掌握特殊矩陣壓縮存儲時的下標變換公式；

    3)熟練掌握稀疏矩陣的表示方法及其運算。

    ⑶考核重點

    1)數(shù)組、特殊矩陣（對稱矩陣、上/下三角矩陣）的地址計算方法；

    2)稀疏矩陣的三元組順序表表示方法及其快速轉(zhuǎn)置算法。

    3)能夠從空間復雜度的角度分析稀疏矩陣的壓縮存儲的優(yōu)點及其適用場合。

    ⒍樹和二叉樹

    ⑴考核知識點

    二叉樹的性質(zhì)；二叉樹的存儲表示；各種二叉樹遍歷策略的遞歸和（先序、中序）非遞歸算法；二叉樹遍歷算法的應用；線索二叉樹；哈夫曼樹及應用

    ⑵考核要求

    1)熟練掌握二叉樹的性質(zhì)，了解相應的證明方法；

    2)熟悉二叉樹的常用存儲結(jié)構(gòu)的特點及適用范圍；

    3)熟練掌握各種二叉樹遍歷策略的遞歸和（先序、中序、層次）非遞歸算法；

    4)能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作；

    5)了解遞歸遍歷過程中棧的作用和狀態(tài)；

    6)了解遞歸算法轉(zhuǎn)化為非遞歸算法的常用方法；

    7)熟悉樹的常用存儲結(jié)構(gòu)及其特點；

    8)熟練掌握樹、森林與二叉樹的轉(zhuǎn)換方法；

    9)了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。

    ⑶考核重點

    1)二叉樹的性質(zhì)及其證明方法；

    2)二叉樹的遞歸遍歷算法及其應用；

    3)二叉樹的非遞歸算法及其應用；

    4)哈夫曼樹的構(gòu)建及編碼。

    ⒎圖

    ⑴考核知識點

    圖的定義和術(shù)語；圖的常用存儲結(jié)構(gòu)；圖的兩種遍歷策略；圖的典型應用：連通分量和最小生成樹、拓撲排序、關(guān)鍵路徑、最短路徑

    ⑵考核要求

    1)熟悉圖的常用存儲結(jié)構(gòu)及圖的構(gòu)造算法；

    2)熟練掌握圖的兩種遍歷策略；

    3)能應用圖的遍歷算法求解以下問題：最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑問題。

    ⑶考核重點

    1)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法；

    2)應用圖的上述遍歷算法求解以下問題：最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑。

    ⒏查找

    ⑴考核知識點

    順序表和有序表的查找；靜態(tài)樹表、索引順序表、二叉排序樹、B+樹和B-樹、哈希表

    ⑵考核要求

    1)熟練掌握順序表和有序表的查找算法；

    2)熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系，掌握次優(yōu)二叉樹的構(gòu)造方法；

    3)熟練掌握二叉排序樹的構(gòu)造、查找和刪除算法；

    4)了解二叉平衡樹的維護平衡方法；

    5)理解B+樹、B-樹和鍵樹的特點以及建樹過程；

    6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性差別；

    7)了解各種查找方法所適應的不同場合及等概率情況下查找成功的平均查找長度。

    ⑶考核重點

    1)折半查找算法；

    2)二叉排序樹的構(gòu)造、查找和刪除算法；

    3)B+樹、B-樹和鍵樹的建樹過程；

    4)哈希表的構(gòu)造方法及其與其它結(jié)構(gòu)表的實質(zhì)性差別；

    5)各種查找方法在等概率情況下查找成功時的平均查找長度。

    ⒐排序

    ⑴考核知識點

    插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序

    ⑵考核要求

    1)深刻理解內(nèi)部排序的定義和各種排序方法的特點、所適應的不同場合，并能加以靈活應用；

    2)了解各種方法的排序過程及其依據(jù)的原則；

    3)掌握各種排序方法的時間、空間復雜度和穩(wěn)定性分析方法；

    4)能從“運行時長”、“關(guān)鍵字的比較次數(shù)”、“數(shù)據(jù)元素的移動次數(shù)”三方面分析各種方法的時間性能。

    ⑶考核重點

    1)分析各種內(nèi)部排序算法的時間、空間復雜度和穩(wěn)定性；

    2)從“運行時長”、“關(guān)鍵字的比較次數(shù)”、“數(shù)據(jù)元素的移動次數(shù)”三方面分析各種內(nèi)部排序算法的時間性能；

    3)典型內(nèi)部排序算法的特點、算法實現(xiàn)、所適應的不同場合及應用：希爾排序、快速排序、堆排序、歸并排序、鏈式基數(shù)排序。

添加南昌航空大學學姐微信，或微信搜索公眾號“考研派小站”，關(guān)注[考研派小站]微信公眾號，在考研派小站微信號輸入[南昌航空大學考研分數(shù)線、南昌航空大學報錄比、南昌航空大學考研群、南昌航空大學學姐微信、南昌航空大學考研真題、南昌航空大學專業(yè)目錄、南昌航空大學排名、南昌航空大學保研、南昌航空大學公眾號、南昌航空大學研究生招生）]即可在手機上查看相對應南昌航空大學考研信息或資源。