第一部分 目標與基本要求
數據結構與算法分析考試是為南京信息工程大學(xué)招收人工智能方向碩士研究生而設置的具有選拔性質(zhì)的全國統一入學(xué)考試科目，其目的是科學(xué)、公平、有效地測試學(xué)生掌握大學(xué)本科階段數據結構與算法分析的基本知識、基本理論，以及運用數據結構與算法分析的理論和方法分析和解決問(wèn)題的能力。評價(jià)的標準是高等學(xué)校本科畢業(yè)生能達到的及格或及格以上水平，以保證被錄取者在開(kāi)展人工智能方向的研究工作中，具有基本的計算機程序設計、數據結構與算法分析的理論素質(zhì)，并具有理解和分析工程實(shí)際問(wèn)題和具有工程實(shí)際應用的基本能力。
第二部分 具體內容
一、數據結構及相關(guān)基本概念
1．了解什么是數據結構。
2．理解數據結構有關(guān)的概念和術(shù)語(yǔ)：數據、數據元素、數據對象、數據結構、線(xiàn)性結構、樹(shù)形結構、圖結構、集合結構。
3．了解抽象數據類(lèi)型的概念與表示。
4. 掌握算法及其分析：算法的定義，特性，時(shí)間復雜度，空間復雜度。
二、基本數據結構
1．掌握線(xiàn)性數據結構：線(xiàn)性表的順序表示與實(shí)現、線(xiàn)性表的鏈接表示與實(shí)現。
2．理解棧的性質(zhì)與特點(diǎn)，能夠用棧解決常見(jiàn)的問(wèn)題，例如括號匹配等。
3．理解隊列的性質(zhì)與特點(diǎn)，掌握常見(jiàn)的隊列表示方法，例如順序表示和鏈接表示。
三、樹(shù)
1．理解樹(shù)的定義及相關(guān)概念。
2．掌握二叉樹(shù)定義及性質(zhì)。
3．掌握二叉樹(shù)的順序存儲結構合連接存儲結構。
4．掌握二叉樹(shù)的遍歷運算及其實(shí)現。
5．掌握二叉搜索樹(shù)以及平衡二叉搜索樹(shù)（AVL）。
6. 掌握二叉堆實(shí)現優(yōu)先隊列的方法。
四、圖及其算法
1．理解圖的定義及相關(guān)概念。
2．掌握圖的存儲結構：鄰接矩陣，鄰接表。
3．掌握圖的寬度優(yōu)先搜索與深度優(yōu)先搜索，能夠用深度優(yōu)先搜索分析和解決騎士游歷問(wèn)題。
4. 掌握圖的拓撲排序、強連通分量。
5．掌握圖的最短路徑問(wèn)題的求解方案，理解并能夠分析Dijistra算法。
6．掌握圖的最小生成樹(shù)問(wèn)題的解決方法。
五、查找和排序
1．掌握順序查找、二分查找、哈希查找方法，并能夠進(jìn)行分析。
2．掌握常用的排序方法：直接插入排序，直接選擇排序，冒泡排序，希爾排序，快速排序，堆排序，歸并排序，基數排序等。
3．理解各類(lèi)內部排序方法的特點(diǎn)：時(shí)間復雜度，空間復雜度，穩定性。
六、分治法與動(dòng)態(tài)規劃
1．理解分治法和動(dòng)態(tài)規劃方法的主要特點(diǎn)和所適用的不同場(chǎng)景。
2. 掌握常見(jiàn)的適用于分治法的典型問(wèn)題，例如二分搜索、歸并排序、快速排序、大整數乘法等等，能夠對分治法解決的問(wèn)題進(jìn)行算法分析。
3. 掌握常見(jiàn)的適用于動(dòng)態(tài)規劃的典型問(wèn)題，例如圖的最短路徑問(wèn)題、斐波那契數列問(wèn)題、最長(cháng)公共子序列等，能夠對動(dòng)態(tài)規劃解決的問(wèn)題進(jìn)行算法分析。
第三部分 有關(guān)說(shuō)明
1、命題說(shuō)明：無(wú)
2、參考書(shū)目:
1）《Python數據結構與算法分析》，[美] 布拉德利·米勒（Bradley N.Miller），戴維·拉努姆（David L.Ranum） 著(zhù)，呂能，刁壽鈞 譯， 人民郵電出版社，2019
2）《數據結構與算法分析 C語(yǔ)言描述》，[美] 馬克·艾倫·維斯（Mark，Allen，Weiss） 著(zhù)，馮舜璽譯 譯，機械工業(yè)出版社， 2019
3、其他規定：考試方式為閉卷筆試，總分 150 分（分值在考試科目列表內查詢(xún)），考試時(shí)間為 180 分鐘（初試跟復試的考試科目考試時(shí)間均為180分鐘，加試科目的考試時(shí)間為120分鐘）。
