為了幫助廣大考生復習備考，也應廣大考生的要求，現提供我校自命題專業課的考試大綱供考生下載。考生在復習備考時，應全面復習，我校自命題專業課的考試大綱僅供參考。

    上海電力大學2021年碩士研究生入學初試《數據結構》課程考試大綱

    課程名稱數據結構

    參考書目：嚴蔚敏,吳偉民《數據結構》（C語言版），清華大學出版社，2012.5

    復習的總體要求

    數據結構是計算機各專業的專業基礎課。本課程包括：算法的基本概念、分析和設計方法；軟件設計中常用的各類結構即線性結構、樹結構、圖結構等；查找、排序等各類常用算法。主要考察學生對數據結構基礎知識的理解、是否具備對現有常用結構和算法的應用能力、是否具備針對具體應用設計合適數據結構的能力。總體要求如下：

    1、理解數據結構的基本概念；

    2、掌握數據結構中邏輯結構、存儲結構的基本概念和差異，以及各種基本操作的實現；

    3、熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構；

    4、掌握設計算法的步驟和算法分析方法；

    5、掌握數據結構在排序和查找等常用算法中的應用；

    6、具備采用類C或C++或JAVA語言設計與實現算法的能力。

    復習內容及知識點

    一、數據結構基本概念及算法定義與分析

    1、什么是數據結構；

    2、抽象數據類型：數據類型、數據抽象與抽象數據類型的概念;用于描述數據結構的語言；

    3、數據結構的抽象層次；

    4、算法定義及算法效率的度量指標：時間復雜度與空間復雜度的計算方法、常見時間復雜度類型與性能優劣比較。

    二、線性表

    1、線性表的概念、定義、邏輯結構和存儲結構；

    2、線性表的順序結構及其各種基本運算；

    3、單鏈表、循環鏈表、雙向鏈表的存儲結構及其各種基本運算；

    4、棧：棧的抽象數據類型定義、棧的存儲表示及基本操作實現、棧的應用；

    5、隊列：隊列的抽象數據類型定義、隊列的存儲表示與基本操作實現；

    6、鏈表的應用：稀疏多項式存儲和運算。

    三、串

    1、串類型的定義；

    2、串的定長順序存儲、塊鏈存儲表示和實現；

    3、串的模式匹配算法；

    4、串的常見應用。

    四、數組和廣義表

    1、數組的定義；

    2、二維數組的兩種存儲方式（以行序為主、以列序為主）及其數組元素存儲位置計算；

    3、特殊矩陣與稀疏矩陣的壓縮存儲方式；

    4、廣義表的定義和存儲結構。

    五、樹和二叉樹

    1、樹和森林的概念：樹的定義、樹的術語、樹的抽象數據類型；

    2、二叉樹：二叉樹的定義、二叉樹的性質、二叉樹的抽象數據類型；

    3、二叉樹的表示：數組表示、鏈表存儲表示；

    4、二叉樹遍歷：中序、前序、后序遍歷、不用棧的二叉樹中序遍歷算法；

    5、線索化二叉樹：中序線索化二叉樹、前序與后序的線索化；

    6、堆：堆的定義、堆的建立；

    7、樹與森林：樹的存儲表示、森林與二叉樹的轉換、樹的遍歷、二叉樹的計數；

    8、霍夫曼樹：路徑長度、霍夫曼樹、霍夫曼編碼。

    六、圖

    1、圖的基本概念：圖的基本概念、圖的抽象數據類型；

    2、圖的存儲表示：鄰接矩陣、鄰接表、鄰接多重表；

    3、圖的遍歷與連通性：深度優先搜索、廣度優先搜索、連通分量；

    4、最小生成樹：克魯斯卡爾算法、普里姆算法；

    5、最短路徑、關鍵路徑。

    七、查找

    1、順序表的查找；

    2、有序表的查找；

    3、索引順序表的查找；

    4、二叉排序樹和平衡二叉樹；

    5、B-樹和B＋樹概念；

    6、哈希表概念；哈希函數的構造方法、處理沖突的方法、哈希表的查找及分析。

    八、內部排序

    1、插入排序：直接插入排序、希爾排序；

    2、交換排序：起泡排序、快速排序；

    3、選擇排序：直接選擇排序、堆排序；

    4、歸并排序：歸并;迭代的歸并排序算法、遞歸的表歸并排序；

    5、各種內部排序方法的分析比較（時間復雜度和空間占用情況）。

    試卷題型說明：（考試題型可能根據實際情況進行調整，以下考試題型僅供參考）

    1、單項選擇題：每個問題都只有一個選擇，根據題目內容選擇正確答案。

    2、填空題：根據題目要求，填充對應位置的內容。

    3、判斷題：根據題目內容判斷其描述問題的正確性。

    4、應用題：根據題目內容完成相應問題的求解，要求給出具體求解過程。

    5、算法設計題：根據題目要求，采用C或C++或Java完成算法的編寫。

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