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

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

一、考試形式

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

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

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

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

三、考試科目

數(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)、存儲(chǔ)結(jié)構(gòu)。

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

2、線性表

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

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

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

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

3、棧與隊(duì)列

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

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

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

計(jì)與實(shí)現(xiàn)。

4、哈希表

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

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

5、樹

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

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

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

（4）遍歷二叉樹。

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

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

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

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

6. 并查集

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

7、圖

（1）圖的基本概念。

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

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

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

8、排序

（1）排序的基本概念。

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

9、算法基礎(chǔ)

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

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

（3）計(jì)算復(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 日

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