南京信息工程大學碩士研究生招生入學考試

考試大綱

科目代碼：853

科目名稱：數據結構與算法分析

第一部分  目標與基本要求

數據結構與算法分析考試是為南京信息工程大學招收電子信息類（人工智能方向）專業學位碩士研究生而設置的具有選拔性質的全國統一入學考試科目，其目的是科學、公平、有效地測試學生掌握大學本科階段數據結構與算法分析的基本知識、基本理論，以及運用數據結構與算法分析的理論和方法分析和解決問題的能力。評價的標準是高等學校本科畢業生能達到的及格或及格以上水平，以保證被錄取者在開展人工智能方向的研究工作中，具有基本的計算機程序設計、數據結構與算法分析的理論素質，并具有理解和分析工程實際問題和具有工程實際應用的基本能力。

第二部分 內容與考核目標

一、數據結構及相關基本概念

1．了解什么是數據結構。

2．理解數據結構有關的概念和術語：數據、數據元素、數據對象、數據結構、線性結構、樹形結構、圖結構、集合結構。

3．了解抽象數據類型的概念與表示。

4. 掌握算法及其分析：算法的定義，特性，時間復雜度，空間復雜度。

二、基本數據結構

1．掌握線性數據結構：線性表的順序表示與實現、線性表的鏈接表示與實現。

2．理解棧的性質與特點，能夠用棧解決常見的問題，例如括號匹配等。

3．理解隊列的性質與特點，掌握常見的隊列表示方法，例如順序表示和鏈接表示。

 三、樹

1．理解樹的定義及相關概念。

2．掌握二叉樹定義及性質。

3．掌握二叉樹的順序存儲結構合連接存儲結構。

4．掌握二叉樹的遍歷運算及其實現。

5．掌握二叉搜索樹以及平衡二叉搜索樹（AVL）。

6. 掌握二叉堆實現優先隊列的方法。

四、圖及其算法

1．理解圖的定義及相關概念。

2．掌握圖的存儲結構：鄰接矩陣，鄰接表。

3．掌握圖的寬度優先搜索與深度優先搜索，能夠用深度優先搜索分析和解決騎士游歷問題。

4. 掌握圖的拓撲排序、強連通分量。

5．掌握圖的最短路徑問題的求解方案，理解并能夠分析Dijistra算法。

6．掌握圖的最小生成樹問題的解決方法。

五、查找和排序 

1．掌握順序查找、二分查找、哈希查找方法，并能夠進行分析。

2．掌握常用的排序方法：直接插入排序，直接選擇排序，冒泡排序，希爾排序，快速排序，堆排序，歸并排序，基數排序等。

3．理解各類內部排序方法的特點：時間復雜度，空間復雜度，穩定性。

六、分治法與動態規劃 

1．理解分治法和動態規劃方法的主要特點和所適用的不同場景。

2. 掌握常見的適用于分治法的典型問題，例如二分搜索、歸并排序、快速排序、大整數乘法、快速傅立葉變換等等，能夠對分治法解決的問題進行算法分析。

3. 掌握常見的適用于動態規劃的典型問題，例如圖的最短路徑問題、斐波那契數列問題、最長公共子序列等，能夠對動態規劃解決的問題進行算法分析。

第三部分  有關說明與實施要求

1、命題說明：無

2、參考書目: 《Python數據結構與算法分析》（第2版），布拉德利·米勒（Bradley N.Miller），戴維·拉努姆（David L.Ranum）著，人民郵電出版社，2019年

3、其他規定：考試方式為閉卷筆試，總分 150分，考試時間為 180 分鐘。