第一部分 目標(biāo)與基本要求

數(shù)據(jù)結(jié)構(gòu)與算法分析考試是為南京信息工程大學(xué)招收人工智能方向碩士研究生而設(shè)置的具有選拔性質(zhì)的全國統(tǒng)一入學(xué)考試科目，其目的是科學(xué)、公平、有效地測試學(xué)生掌握大學(xué)本科階段數(shù)據(jù)結(jié)構(gòu)與算法分析的基本知識、基本理論，以及運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法分析的理論和方法分析和解決問題的能力。評價的標(biāo)準(zhǔn)是高等學(xué)校本科畢業(yè)生能達(dá)到的及格或及格以上水平，以保證被錄取者在開展人工智能方向的研究工作中，具有基本的計算機(jī)程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)與算法分析的理論素質(zhì)，并具有理解和分析工程實(shí)際問題和具有工程實(shí)際應(yīng)用的基本能力。

第二部分具體內(nèi)容

一、數(shù)據(jù)結(jié)構(gòu)及相關(guān)基本概念

1．了解什么是數(shù)據(jù)結(jié)構(gòu)。

2．理解數(shù)據(jù)結(jié)構(gòu)有關(guān)的概念和術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)、集合結(jié)構(gòu)。

3．了解抽象數(shù)據(jù)類型的概念與表示。

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

二、基本數(shù)據(jù)結(jié)構(gòu)

1．掌握線性數(shù)據(jù)結(jié)構(gòu)：線性表的順序表示與實(shí)現(xiàn)、線性表的鏈接表示與實(shí)現(xiàn)。

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

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

 三、樹

1．理解樹的定義及相關(guān)概念。

2．掌握二叉樹定義及性質(zhì)。

3．掌握二叉樹的順序存儲結(jié)構(gòu)合連接存儲結(jié)構(gòu)。

4．掌握二叉樹的遍歷運(yùn)算及其實(shí)現(xiàn)。

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

6. 掌握二叉堆實(shí)現(xiàn)優(yōu)先隊列的方法。

四、圖及其算法

1．理解圖的定義及相關(guān)概念。

2．掌握圖的存儲結(jié)構(gòu)：鄰接矩陣，鄰接表。

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

4. 掌握圖的拓?fù)渑判颉?qiáng)連通分量。

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

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

五、查找和排序 

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

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

3．理解各類內(nèi)部排序方法的特點(diǎn)：時間復(fù)雜度，空間復(fù)雜度，穩(wěn)定性。

六、分治法與動態(tài)規(guī)劃 

1．理解分治法和動態(tài)規(guī)劃方法的主要特點(diǎn)和所適用的不同場景。

2. 掌握常見的適用于分治法的典型問題，例如二分搜索、歸并排序、快速排序、大整數(shù)乘法等等，能夠?qū)Ψ种畏ń鉀Q的問題進(jìn)行算法分析。

3. 掌握常見的適用于動態(tài)規(guī)劃的典型問題，例如圖的最短路徑問題、斐波那契數(shù)列問題、最長公共子序列等，能夠?qū)討B(tài)規(guī)劃解決的問題進(jìn)行算法分析。

第三部分  有關(guān)說明

1、命題說明：無

2、參考書目: 

1）《Python數(shù)據(jù)結(jié)構(gòu)與算法分析》，[美] 布拉德利·米勒（Bradley N.Miller），戴維·拉努姆（David L.Ranum） 著，呂能，刁壽鈞 譯， 人民郵電出版社，2019

2）《數(shù)據(jù)結(jié)構(gòu)與算法分析 C語言描述》，[美] 馬克·艾倫·維斯（Mark，Allen，Weiss） 著，馮舜璽譯 譯，機(jī)械工業(yè)出版社， 2019

3、其他規(guī)定：考試方式為閉卷筆試，總分 150  分（分值在考試科目列表內(nèi)查詢），考試時間為 180 分鐘（初試跟復(fù)試的考試科目考試時間均為180分鐘，同等學(xué)力加試科目的考試時間為120分鐘）。

 

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