2021年南通大學碩士研究生入學考試復習大綱

    培養單位:信息科學技術學院2020年6月

    科目名稱數據結構科目代碼905

    考試范圍及要點

    數據結構研究生考試大綱

    1.緒論

    （1）掌握數據結構的基本概念，包括數據、數據項、數據元素、數據的邏輯結構和存儲結構；掌握典型的邏輯結構、存儲結構。

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

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

    2.線性表

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

    （2）掌握線性表順序存儲的實現：

    ①順序表的定義和特性；

    ②基本操作的實現及算法復雜度分析；

    （3）掌握線性表鏈式存儲的實現：

    ①各種形式鏈表的定義和特性，包括有或無頭結點的單向或雙向鏈表、循環鏈表、靜態鏈表；

    ②各種鏈表形式的基本操作的實現及算法復雜度分析。

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

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

    3.棧

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

    （2）掌握順序棧、鏈棧、共享棧的實現。

    （3）掌握棧的典型應用：

    ①遞歸算法；

    ②表達式求值。

    4.隊列

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

    （2）掌握隊列的順序存儲和鏈式存儲的實現。

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

    5.數組

    （1）掌握數組的定義，理解它們是線性表的擴展。

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

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

    6.樹與二叉樹

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

    （2）掌握樹的各種邏輯結構表示、樹的各種存儲結構表示、樹的性質、樹的遍歷

    方法。

    （3）掌握二叉樹的定義、術語、遞歸特性、5種基本形態和性質。

    （4）掌握二叉樹的兩種存儲結構：順序存儲和二叉鏈表存儲，掌握它們各自優缺點和適用場合。

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

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

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

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

    （9）掌握哈夫曼樹的定義、性質、構造過程和產生哈夫曼編碼的方法與過程。

    7.圖

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

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

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

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

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

    (6)掌握拓撲排序的概念和求解拓撲序列算法。

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

    8.查找

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

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

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

    （4）掌握平衡二叉樹的定義和調整過程。

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

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

    9.排序

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

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

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

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

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

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

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

    試題結構

    1.是非判斷題：20分

    2.簡答題：30分

    3.綜合應用題：70分

    4.算法分析與設計：30分

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

    數據結構（C語言）嚴蔚敏清華大學出版社第二版2011

    數據結構管致錦清華大學出版社第一版2010

添加南通大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[南通大學考研分數線、南通大學報錄比、南通大學考研群、南通大學學姐微信、南通大學考研真題、南通大學專業目錄、南通大學排名、南通大學保研、南通大學公眾號、南通大學研究生招生）]即可在手機上查看相對應南通大學考研信息或資源。