2021南通大學(xué)905數(shù)據(jù)結(jié)構(gòu)研究生考試大綱

發(fā)布時(shí)間：2020-12-04 編輯：考研派小莉推薦訪問(wèn)：

2021南通大學(xué)905數(shù)據(jù)結(jié)構(gòu)研究生考試大綱內(nèi)容如下，更多考研資訊請(qǐng)關(guān)注我們網(wǎng)站的更新！敬請(qǐng)收藏本站，或下載我們的考研派APP和考研派微信公眾號(hào)（里面有非常多的免費(fèi)考研資源可以領(lǐng)取，有各種考研問(wèn)題，也可直接加我們網(wǎng)站上的研究生學(xué)姐微信，全程免費(fèi)答疑，助各位考研一臂之力，爭(zhēng)取早日考上理想中的研究生院校。）

+南通大學(xué) 研究生
微信,為你答疑,送資源

2021南通大學(xué)911學(xué)前教育學(xué)研究生考試大綱 2021南通大學(xué)910發(fā)展心理學(xué)研究生考試大綱 2021南通大學(xué)907小學(xué)課程與教學(xué)研究生考試大綱 2021南通大學(xué)708心理學(xué)綜合研究生考試大綱 2021南通大學(xué)708心理學(xué)綜合研究生考試大綱 2021南通大學(xué)706教育學(xué)科綜合研究生考試大綱 95%的同學(xué)還閱讀了： 南通大學(xué)研究生招生目錄南通大學(xué)研究生分?jǐn)?shù)線南通大學(xué)王牌專業(yè)排名南通大學(xué)考研難嗎南通大學(xué)考研調(diào)劑信息南通大學(xué)研究生導(dǎo)師名單南通大學(xué)研究生學(xué)費(fèi)南通大學(xué)研究生獎(jiǎng)學(xué)金

2021南通大學(xué)905數(shù)據(jù)結(jié)構(gòu)研究生考試大綱正文

2021年南通大學(xué)碩士研究生入學(xué)考試復(fù)習(xí)大綱

培養(yǎng)單位:信息科學(xué)技術(shù)學(xué)院2020年6月

科目名稱數(shù)據(jù)結(jié)構(gòu)科目代碼905

考試范圍及要點(diǎn)

數(shù)據(jù)結(jié)構(gòu)研究生考試大綱

1.緒論

（1）掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，包括數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；掌握典型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。

（2）理解算法特性，掌握算法的描述方法，包括偽碼、類語(yǔ)言描述方法。

（3）掌握算法時(shí)間和空間復(fù)雜度概念及分析方法。

2.線性表

（1）掌握線性表的相關(guān)概念、特點(diǎn)和基本操作（包括：創(chuàng)建、銷毀、插入、刪除、查找等）定義。

（2）掌握線性表順序存儲(chǔ)的實(shí)現(xiàn)：

①順序表的定義和特性；

②基本操作的實(shí)現(xiàn)及算法復(fù)雜度分析；

（3）掌握線性表鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)：

①各種形式鏈表的定義和特性，包括有或無(wú)頭結(jié)點(diǎn)的單向或雙向鏈表、循環(huán)鏈表、靜態(tài)鏈表；

②各種鏈表形式的基本操作的實(shí)現(xiàn)及算法復(fù)雜度分析。

（4）能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)，了解各自適宜場(chǎng)景，能夠針對(duì)具體問(wèn)題選擇合適的結(jié)構(gòu)。

（5）掌握有序表的定義、特點(diǎn)和高效算法設(shè)計(jì)方法。

3.棧

（1）掌握棧的相關(guān)概念、特點(diǎn)和基本操作（入棧、出棧等）定義。

（2）掌握順序棧、鏈棧、共享?xiàng)５膶?shí)現(xiàn)。

（3）掌握棧的典型應(yīng)用：

①遞歸算法；

②表達(dá)式求值。

4.隊(duì)列

（1）掌握隊(duì)列的相關(guān)概念、特點(diǎn)和基本操作（入隊(duì)、出隊(duì)等）定義。

（2）掌握隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)。

（3）了解雙端隊(duì)列的概念。

5.數(shù)組

（1）掌握數(shù)組的定義，理解它們是線性表的擴(kuò)展。

（2）掌握多維數(shù)組到一維存儲(chǔ)的映射方法。

（3）掌握特殊矩陣（包括：稀疏矩陣、對(duì)稱矩陣、上（下）三角矩陣、對(duì)角矩陣等）的壓縮存儲(chǔ)方法。

6.樹(shù)與二叉樹(shù)

（1）掌握樹(shù)的定義和術(shù)語(yǔ)，包括：樹(shù)根、孩子、雙親、祖先、子孫、兄弟、堂兄、路徑、路徑長(zhǎng)度等。

（2）掌握樹(shù)的各種邏輯結(jié)構(gòu)表示、樹(shù)的各種存儲(chǔ)結(jié)構(gòu)表示、樹(shù)的性質(zhì)、樹(shù)的遍歷

方法。

（3）掌握二叉樹(shù)的定義、術(shù)語(yǔ)、遞歸特性、5種基本形態(tài)和性質(zhì)。

（4）掌握二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和二叉鏈表存儲(chǔ)，掌握它們各自優(yōu)缺點(diǎn)和適用場(chǎng)合。

（5）掌握二叉樹(shù)的四種遍歷方法：先序、中序、后序和層次遍歷；理解遞歸遍歷和非遞歸遍歷算法的執(zhí)行過(guò)程；重點(diǎn)掌握各種遍歷算法在求解實(shí)際問(wèn)題中的應(yīng)用，例如：求結(jié)點(diǎn)個(gè)數(shù)、復(fù)制二叉樹(shù)、結(jié)點(diǎn)查找等。

（6）掌握基于兩種遍歷序列構(gòu)造二叉樹(shù)的過(guò)程。

（7）掌握樹(shù)或森林與二叉樹(shù)之間的相互轉(zhuǎn)換過(guò)程。

（8）掌握線索二叉樹(shù)的實(shí)質(zhì)、二叉樹(shù)線索化過(guò)程、線索二叉樹(shù)的遍歷算法。

（9）掌握哈夫曼樹(shù)的定義、性質(zhì)、構(gòu)造過(guò)程和產(chǎn)生哈夫曼編碼的方法與過(guò)程。

7.圖

(1)掌握?qǐng)D的基本概念。

(2)掌握?qǐng)D的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。

(3)掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。

(4)掌握?qǐng)D的生成樹(shù)和最小生成樹(shù)的概念、采用普里姆算法和克魯斯卡爾算法構(gòu)造圖的最小生成樹(shù)的過(guò)程。

(5)掌握?qǐng)D的最短路徑問(wèn)題求解方法--狄杰斯特拉算法和弗洛伊德算法的原理與過(guò)程。

(6)掌握拓?fù)渑判虻母拍詈颓蠼馔負(fù)湫蛄兴惴ā?/div>

(7)掌握關(guān)鍵路徑的概念以及求解關(guān)鍵路徑的過(guò)程。

8.查找

(1)掌握靜態(tài)查找和動(dòng)態(tài)查找的含義及區(qū)別；成功情況下和不成功情況下平均查找長(zhǎng)度ASL的概念。

(2)掌握線性表上的順序查找、折半查找算法，了解分塊查找原理，能夠分析些算法的特點(diǎn)和計(jì)算平均查找長(zhǎng)度ASL。

（3）掌握二叉排序樹(shù)的定義、特點(diǎn)、存儲(chǔ)方法、創(chuàng)建、結(jié)點(diǎn)刪除和插入、查找等操作過(guò)程，并能針對(duì)具體的二叉排序樹(shù)分析其成功和不成功的平均查找長(zhǎng)度ASL。

（4）掌握平衡二叉樹(shù)的定義和調(diào)整過(guò)程。

(5)了解B-、B+樹(shù)概念。

(6)掌握哈希表的概念、解決沖突的方法及構(gòu)造，能夠計(jì)算哈希查找的ASL。

9.排序

(1)掌握排序的基本概念。

(2)掌握插入排序的思路和各種插入排序算法進(jìn)行排序的過(guò)程，包括直接插入排序、二分插入排序和希爾排序等。

(3)掌握交換排序的思路和各種交換排序算法進(jìn)行排序的過(guò)程，包括冒泡排序、快速排序等。

(4)掌握選擇排序的思路和各種選擇排序算法進(jìn)行排序的過(guò)程，包括簡(jiǎn)單選擇排序、樹(shù)型選擇排序和堆排序等。

(5)掌握歸并排序的思路和二路歸并排序算法進(jìn)行排序的過(guò)程。

(6)掌握基數(shù)排序的思路以及排序過(guò)程。

(7)掌握各種排序算法的優(yōu)缺點(diǎn)和性能，特別是各種排序方法的時(shí)間復(fù)雜度和空間復(fù)雜度的比較。

試題結(jié)構(gòu)

1.是非判斷題：20分

2.簡(jiǎn)答題：30分

3.綜合應(yīng)用題：70分

4.算法分析與設(shè)計(jì)：30分

參考書目名稱編者出版單位版次年份

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）嚴(yán)蔚敏清華大學(xué)出版社第二版2011

數(shù)據(jù)結(jié)構(gòu)管致錦清華大學(xué)出版社第一版2010

南通大學(xué)

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