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

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

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

+南通大學(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é)費南通大學(xué)研究生獎學(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

考試范圍及要點

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

1.緒論

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

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

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

2.線性表

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

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

①順序表的定義和特性；

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

（3）掌握線性表鏈?zhǔn)酱鎯Φ膶崿F(xiàn)：

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

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

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

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

3.棧

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

（2）掌握順序棧、鏈棧、共享棧的實現(xiàn)。

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

①遞歸算法；

②表達(dá)式求值。

4.隊列

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

（2）掌握隊列的順序存儲和鏈?zhǔn)酱鎯Φ膶崿F(xiàn)。

（3）了解雙端隊列的概念。

5.數(shù)組

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

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

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

6.樹與二叉樹

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

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

方法。

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

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

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

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

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

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

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

7.圖

(1)掌握圖的基本概念。

(2)掌握圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)及其特點。

(3)掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。

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

(5)掌握圖的最短路徑問題求解方法--狄杰斯特拉算法和弗洛伊德算法的原理與過程。

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

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

8.查找

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

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

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

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

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

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

9.排序

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

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

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

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

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

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

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

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

1.是非判斷題：20分

2.簡答題：30分

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

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

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

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

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

南通大學(xué)

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