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

《數(shù)據(jù)結構與算法》考試大綱

一、考試形式

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

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

二、試卷結構

單項選擇、多項選擇、判斷、應用題（計算、畫圖、分析、設計）等。

三、考試科目

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

四、考試大綱

1、緒論

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

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

2、線性表

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

（2）線性表的實現(xiàn)及應用，包括順序存儲結構、鏈式存儲結構(單鏈表、循環(huán)鏈表和雙向鏈

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

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

3、棧與隊列

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

（2）棧與隊列的順序存儲結構、鏈式存儲結構的構造原理。

（3）在不同存儲結構的基礎上對堆棧、隊列實施基本操作（插入與刪除等）對應的算法設

計與實現(xiàn)。

4、哈希表

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

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

5、樹

（1）樹的概念和性質。

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

（3）二叉樹的順序存儲結構和鏈式存儲結構。

（4）遍歷二叉樹。

（5）樹和森林的存儲結構、遍歷。

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

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

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

6. 并查集

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

7、圖

（1）圖的基本概念。

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

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

（4）最小生成樹，最短路徑，關鍵路徑、拓撲排序算法的原理與實現(xiàn)。

8、排序

（1）排序的基本概念。

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

9、算法基礎

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

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

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

五、參考書目

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

導論（第 3 版）（原版與中譯版均可）

編制單位：上?？萍即髮W信息科學與技術學院

編制日期：2017 年 6 月 20 日

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