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

發(fā)布時(shí)間：2020-12-04 編輯：考研派小莉 推薦訪問：
2021南通大學(xué)905數(shù)據(jù)結(jié)構(gòu)研究生考試大綱

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

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)和存儲結(jié)構(gòu)；掌握典型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。
    （2）理解算法特性，掌握算法的描述方法，包括偽碼、類語言描述方法。
    （3）掌握算法時(shí)間和空間復(fù)雜度概念及分析方法。
    2.線性表
    （1）掌握線性表的相關(guān)概念、特點(diǎn)和基本操作（包括：創(chuàng)建、銷毀、插入、刪除、查找等）定義。
    （2）掌握線性表順序存儲的實(shí)現(xiàn)：
    ①順序表的定義和特性；
    ②基本操作的實(shí)現(xiàn)及算法復(fù)雜度分析；
    （3）掌握線性表鏈?zhǔn)酱鎯Φ膶?shí)現(xiàn)：
    ①各種形式鏈表的定義和特性，包括有或無頭結(jié)點(diǎn)的單向或雙向鏈表、循環(huán)鏈表、靜態(tài)鏈表；
    ②各種鏈表形式的基本操作的實(shí)現(xiàn)及算法復(fù)雜度分析。
    （4）能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點(diǎ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ì)列的順序存儲和鏈?zhǔn)酱鎯Φ膶?shí)現(xiàn)。
    （3）了解雙端隊(duì)列的概念。
    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)缺點(diǎn)和適用場合。
    （5）掌握二叉樹的四種遍歷方法：先序、中序、后序和層次遍歷；理解遞歸遍歷和非遞歸遍歷算法的執(zhí)行過程；重點(diǎn)掌握各種遍歷算法在求解實(shí)際問題中的應(yīng)用，例如：求結(jié)點(diǎn)個(gè)數(shù)、復(fù)制二叉樹、結(jié)點(diǎn)查找等。
    （6）掌握基于兩種遍歷序列構(gòu)造二叉樹的過程。
    （7）掌握樹或森林與二叉樹之間的相互轉(zhuǎn)換過程。
    （8）掌握線索二叉樹的實(shí)質(zhì)、二叉樹線索化過程、線索二叉樹的遍歷算法。
    （9）掌握哈夫曼樹的定義、性質(zhì)、構(gòu)造過程和產(chǎn)生哈夫曼編碼的方法與過程。
    7.圖
    (1)掌握圖的基本概念。
    (2)掌握圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)及其特點(diǎn)。
    (3)掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。
    (4)掌握圖的生成樹和最小生成樹的概念、采用普里姆算法和克魯斯卡爾算法構(gòu)造圖的最小生成樹的過程。
    (5)掌握圖的最短路徑問題求解方法--狄杰斯特拉算法和弗洛伊德算法的原理與過程。
    (6)掌握拓?fù)渑判虻母拍詈颓蠼馔負(fù)湫蛄兴惴ā?/div>
    (7)掌握關(guān)鍵路徑的概念以及求解關(guān)鍵路徑的過程。
    8.查找
    (1)掌握靜態(tài)查找和動(dòng)態(tài)查找的含義及區(qū)別；成功情況下和不成功情況下平均查找長度ASL的概念。
    (2)掌握線性表上的順序查找、折半查找算法，了解分塊查找原理，能夠分析些算法的特點(diǎn)和計(jì)算平均查找長度ASL。
    （3）掌握二叉排序樹的定義、特點(diǎn)、存儲方法、創(chuàng)建、結(jié)點(diǎn)刪除和插入、查找等操作過程，并能針對具體的二叉排序樹分析其成功和不成功的平均查找長度ASL。
    （4）掌握平衡二叉樹的定義和調(diào)整過程。
    (5)了解B-、B+樹概念。
    (6)掌握哈希表的概念、解決沖突的方法及構(gòu)造，能夠計(jì)算哈希查找的ASL。
    9.排序
    (1)掌握排序的基本概念。
    (2)掌握插入排序的思路和各種插入排序算法進(jìn)行排序的過程，包括直接插入排序、二分插入排序和希爾排序等。
    (3)掌握交換排序的思路和各種交換排序算法進(jìn)行排序的過程，包括冒泡排序、快速排序等。
    (4)掌握選擇排序的思路和各種選擇排序算法進(jìn)行排序的過程，包括簡單選擇排序、樹型選擇排序和堆排序等。
    (5)掌握歸并排序的思路和二路歸并排序算法進(jìn)行排序的過程。
    (6)掌握基數(shù)排序的思路以及排序過程。
    (7)掌握各種排序算法的優(yōu)缺點(diǎn)和性能，特別是各種排序方法的時(shí)間復(fù)雜度和空間復(fù)雜度的比較。
    試題結(jié)構(gòu)
    1.是非判斷題：20分
    2.簡答題：30分
    3.綜合應(yīng)用題：70分
    4.算法分析與設(shè)計(jì)：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é)報(bào)錄比、南通大學(xué)考研群、南通大學(xué)學(xué)姐微信、南通大學(xué)考研真題、南通大學(xué)專業(yè)目錄、南通大學(xué)排名、南通大學(xué)保研、南通大學(xué)公眾號、南通大學(xué)研究生招生）]即可在手機(jī)上查看相對應(yīng)南通大學(xué)考研信息或資源。

南通大學(xué)考研公眾號 考研派小站公眾號

本文來源：http://www.scstrans.com/nantongdaxue/cankaoshumu_387696.html

推薦閱讀