為了幫助廣大考生復(fù)習(xí)備考，也應(yīng)廣大考生的要求，現(xiàn)提供我校自命題專業(yè)課的考試大綱供考生下載?？忌趶?fù)習(xí)備考時(shí)，應(yīng)全面復(fù)習(xí)，我校自命題專業(yè)課的考試大綱僅供參考。

    上海電力大學(xué)2021年碩士研究生入學(xué)初試《數(shù)據(jù)結(jié)構(gòu)》課程考試大綱

    課程名稱數(shù)據(jù)結(jié)構(gòu)

    參考書目：嚴(yán)蔚敏,吳偉民《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），清華大學(xué)出版社，2012.5

    復(fù)習(xí)的總體要求

    數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)各專業(yè)的專業(yè)基礎(chǔ)課。本課程包括：算法的基本概念、分析和設(shè)計(jì)方法；軟件設(shè)計(jì)中常用的各類結(jié)構(gòu)即線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)等；查找、排序等各類常用算法。主要考察學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)的理解、是否具備對(duì)現(xiàn)有常用結(jié)構(gòu)和算法的應(yīng)用能力、是否具備針對(duì)具體應(yīng)用設(shè)計(jì)合適數(shù)據(jù)結(jié)構(gòu)的能力?？傮w要求如下：

    1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念；

    2、掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的基本概念和差異，以及各種基本操作的實(shí)現(xiàn)；

    3、熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會(huì)根據(jù)實(shí)際問(wèn)題要求來(lái)選擇數(shù)據(jù)結(jié)構(gòu)；

    4、掌握設(shè)計(jì)算法的步驟和算法分析方法；

    5、掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用；

    6、具備采用類C或C++或JAVA語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

    復(fù)習(xí)內(nèi)容及知識(shí)點(diǎn)

    一、數(shù)據(jù)結(jié)構(gòu)基本概念及算法定義與分析

    1、什么是數(shù)據(jù)結(jié)構(gòu)；

    2、抽象數(shù)據(jù)類型：數(shù)據(jù)類型、數(shù)據(jù)抽象與抽象數(shù)據(jù)類型的概念;用于描述數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言；

    3、數(shù)據(jù)結(jié)構(gòu)的抽象層次；

    4、算法定義及算法效率的度量指標(biāo)：時(shí)間復(fù)雜度與空間復(fù)雜度的計(jì)算方法、常見時(shí)間復(fù)雜度類型與性能優(yōu)劣比較。

    二、線性表

    1、線性表的概念、定義、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；

    2、線性表的順序結(jié)構(gòu)及其各種基本運(yùn)算；

    3、單鏈表、循環(huán)鏈表、雙向鏈表的存儲(chǔ)結(jié)構(gòu)及其各種基本運(yùn)算；

    4、棧：棧的抽象數(shù)據(jù)類型定義、棧的存儲(chǔ)表示及基本操作實(shí)現(xiàn)、棧的應(yīng)用；

    5、隊(duì)列：隊(duì)列的抽象數(shù)據(jù)類型定義、隊(duì)列的存儲(chǔ)表示與基本操作實(shí)現(xiàn)；

    6、鏈表的應(yīng)用：稀疏多項(xiàng)式存儲(chǔ)和運(yùn)算。

    三、串

    1、串類型的定義；

    2、串的定長(zhǎng)順序存儲(chǔ)、塊鏈存儲(chǔ)表示和實(shí)現(xiàn)；

    3、串的模式匹配算法；

    4、串的常見應(yīng)用。

    四、數(shù)組和廣義表

    1、數(shù)組的定義；

    2、二維數(shù)組的兩種存儲(chǔ)方式（以行序?yàn)橹?、以列序?yàn)橹鳎┘捌鋽?shù)組元素存儲(chǔ)位置計(jì)算；

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

    4、廣義表的定義和存儲(chǔ)結(jié)構(gòu)。

    五、樹和二叉樹

    1、樹和森林的概念：樹的定義、樹的術(shù)語(yǔ)、樹的抽象數(shù)據(jù)類型；

    2、二叉樹：二叉樹的定義、二叉樹的性質(zhì)、二叉樹的抽象數(shù)據(jù)類型；

    3、二叉樹的表示：數(shù)組表示、鏈表存儲(chǔ)表示；

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

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

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

    7、樹與森林：樹的存儲(chǔ)表示、森林與二叉樹的轉(zhuǎn)換、樹的遍歷、二叉樹的計(jì)數(shù)；

    8、霍夫曼樹：路徑長(zhǎng)度、霍夫曼樹、霍夫曼編碼。

    六、圖

    1、圖的基本概念：圖的基本概念、圖的抽象數(shù)據(jù)類型；

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

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

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

    5、最短路徑、關(guān)鍵路徑。

    七、查找

    1、順序表的查找；

    2、有序表的查找；

    3、索引順序表的查找；

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

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

    6、哈希表概念；哈希函數(shù)的構(gòu)造方法、處理沖突的方法、哈希表的查找及分析。

    八、內(nèi)部排序

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

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

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

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

    5、各種內(nèi)部排序方法的分析比較（時(shí)間復(fù)雜度和空間占用情況）。

    試卷題型說(shuō)明：（考試題型可能根據(jù)實(shí)際情況進(jìn)行調(diào)整，以下考試題型僅供參考）

    1、單項(xiàng)選擇題：每個(gè)問(wèn)題都只有一個(gè)選擇，根據(jù)題目?jī)?nèi)容選擇正確答案。

    2、填空題：根據(jù)題目要求，填充對(duì)應(yīng)位置的內(nèi)容。

    3、判斷題：根據(jù)題目?jī)?nèi)容判斷其描述問(wèn)題的正確性。

    4、應(yīng)用題：根據(jù)題目?jī)?nèi)容完成相應(yīng)問(wèn)題的求解，要求給出具體求解過(guò)程。

    5、算法設(shè)計(jì)題：根據(jù)題目要求，采用C或C++或Java完成算法的編寫。

添加上海電力大學(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é)考研信息或資源。