上?？萍即髮W(xué)碩士研究生入學(xué)考試

《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

一、考試形式

閉卷，筆試，考試時間 180 分鐘，總分 150 分。在同一套試卷內(nèi)的每道題目會同時給出中英

文表述，考生自行決定中文或英文作答。

二、試卷結(jié)構(gòu)

單項選擇、多項選擇、判斷、應(yīng)用題（計算、畫圖、分析、設(shè)計）等。

三、考試科目

數(shù)據(jù)結(jié)構(gòu)與算法。數(shù)據(jù)結(jié)構(gòu)占 60~70%，算法占 30~40%。

四、考試大綱

1、緒論

（1）數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。

（2）算法的定義、算法的基本特性以及算法分析的基本概念。

2、線性表

（1）線性表的定義、基本操作。

（2）線性表的實現(xiàn)及應(yīng)用，包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)(單鏈表、循環(huán)鏈表和雙向鏈

表)的構(gòu)造原理，在兩種存儲結(jié)構(gòu)上對線性表實施的主要的操作(三種鏈表的建立、插入和刪

除、檢索等)的算法設(shè)計與實現(xiàn)。

3、棧與隊列

（1）棧與隊列的基本概念、基本操作。

（2）棧與隊列的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的構(gòu)造原理。

（3）在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧、隊列實施基本操作（插入與刪除等）對應(yīng)的算法設(shè)

計與實現(xiàn)。

4、哈希表

（1）哈希表的基本概念。

（2）哈希表的實現(xiàn)方式。

5、樹

（1）樹的概念和性質(zhì)。

（2）二叉樹的概念、性質(zhì)和實現(xiàn)。

（3）二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

（4）遍歷二叉樹。

（5）樹和森林的存儲結(jié)構(gòu)、遍歷。

（6）堆與優(yōu)先隊列。

（6）二叉排序樹。（7）平衡二叉樹。

（8）哈夫曼(Huffman)樹和哈夫曼編碼。

6. 并查集

（1）并查集的概念與實現(xiàn)。

7、圖

（1）圖的基本概念。

（2）圖的存儲，包括鄰接矩陣法、鄰接表法。

（3）圖的遍歷操作，包括深度優(yōu)先搜索、廣度優(yōu)先搜索。

（4）最小生成樹，最短路徑，關(guān)鍵路徑、拓?fù)渑判蛩惴ǖ脑砼c實現(xiàn)。

8、排序

（1）排序的基本概念。

（2）插入排序、冒泡排序、快速排序、堆排序、歸并排序、基數(shù)排序算法的原理、復(fù)雜度。

9、算法基礎(chǔ)

（1）字符串模式匹配算法。

（2）貪心法、分治法、動態(tài)規(guī)劃的基本概念。

（3）計算復(fù)雜度類別的基本概念，NP-Complete 問題。

五、參考書目

Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein，算法

導(dǎo)論（第 3 版）（原版與中譯版均可）

編制單位：上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院

編制日期：2017 年 6 月 20 日

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