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

考試科目名稱：數據結構

考試科目代碼：817

考試形式：筆試

考試時間：180分鐘

滿分：150分

參考書目：《數據結構》（C 語言版）， 嚴蔚敏、吳偉民編 著，清華大學出版社，2007 年。及配套題集

一、試卷結構：

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

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

二、考試范圍：

⒈ 緒論

⑴ 考核知識點

數據的邏輯結構與物理結構；抽象數據類型；算法的時間復雜度和空間復雜度

⑵ 考核要求

1) 理解數據結構的基本概念和術語；

2) 掌握抽象數據類型的表示與實現；

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

⑶ 考核重點

1) 數據的邏輯結構與物理結構；

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

⒉ 線性表

⑴ 考核知識點

線性表的抽象數據類型定義；線性表的兩類存儲結構（順序和鏈式）的表示與實現；線性表的兩類存儲結構的比較 

⑵ 考核要求

1) 熟練掌握線性表的兩類存儲結構的表示及其基本操作的實現；

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

3) 熟練掌握在各種鏈表結構上實現線性表操作的基本方法，能在實際應用中選用適當的鏈表結構；

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

⑶ 考核重點

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

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

⒊ 棧和隊列

⑴ 考核知識點

棧和隊列的特性；棧和隊列的表示及實現；棧在函數調用中所起的作用；棧和隊列的典型應用

⑵ 考核要求

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

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

3) 深入理解遞歸算法執行過程中棧的狀態的變化；

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

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

⑶ 考核重點

1) 遞歸算法的設計；

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

⒋ 串

⑴ 考核知識點

串的抽象數據類型；串的表示與實現；串的模式匹配算法

⑵ 考核要求

1) 掌握串的堆存儲結構以及在其上實現串操作的基本方法；

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

3) 串匹配的KMP算法；

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

⑶ 考核重點

串的模式匹配算法。

⒌ 數組

⑴ 考核知識點

數組的抽象數據類型定義和表示；特殊矩陣的壓縮存儲方法；稀疏矩陣的壓縮存儲方法及運算的實現

⑵ 考核要求

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

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

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

⑶ 考核重點

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

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

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

⒍ 樹和二叉樹

⑴ 考核知識點

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

⑵ 考核要求

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

2) 熟悉二叉樹的常用存儲結構的特點及適用范圍；

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

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

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

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

7) 熟悉樹的常用存儲結構及其特點；

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

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

⑶ 考核重點

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

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

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

4) 哈夫曼樹的構建及編碼。

⒎ 圖

⑴ 考核知識點

圖的定義和術語；圖的常用存儲結構；圖的兩種遍歷策略；圖的典型應用：連通分量和最小生成樹，拓撲排序，關鍵路徑，最短路徑

⑵ 考核要求

1) 熟悉圖的常用存儲結構及圖的構造算法；

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

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

⑶ 考核重點

1) 圖的深度優先搜索和廣度優先搜索算法；

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

⒏ 查找

⑴ 考核知識點

順序表和有序表的查找；靜態樹表；索引順序表；二叉排序樹；B+樹和B-樹；哈希表

⑵ 考核要求

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

2) 熟悉靜態查找樹的構造方法和查找算法，理解靜態查找樹和折半查找的關系，掌握次優二叉樹的構造方法；

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

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

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

6) 熟練掌握哈希表的構造方法，深刻理解哈希表與其它結構的表的實質性差別；

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

⑶ 考核重點

1) 折半查找算法；

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

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

4) 哈希表的構造方法及其與其它結構表的實質性差別；

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

⒐ 排序

⑴ 考核知識點

插入排序；交換排序；選擇排序；歸并排序；基數排序

⑵ 考核要求

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

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

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

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

⑶ 考核重點

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

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

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