考研复习专业课#2021年上海科技大学<<数据结构与算法>>考研大纲

考研复习>>专业课>>正文2021年上海科技大学<<数据结构与算法>>考研大纲

更新时间：2020/11/179:25:28

上海科技大学硕士研究生入学考试

《数据结构与算法》考试大纲

一 、考试形式

闭卷 ，笔试
，考试时间180分钟，总分150分。在同一套试卷内的每道题目会同时给出中英

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

二
、试卷结构

单项选择、多项选择 、判断
、应用题（计算、画图 、分析、设计）等
。

三
、考试科目

数据结构与算法。数据结构占60~70%
，算法占30~40% 。

四、考试大纲

1 、绪论

（1）数据结构的基本概念，数据的逻辑结构
、存储结构
。

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

2 、线性表

（1）线性表的定义
、基本操作 。

（2）线性表的实现及应用 ，包括顺序存储结构、链式存储结构(单链表 、循环链表和双向链

表)的构造原理，在两种存储结构上对线性表实施的主要的操作(三种链表的建立
、插入和删

除、检索等)的算法设计与实现。

3 、栈与队列

（1）栈与队列的基本概念
、基本操作
。

（2）栈与队列的顺序存储结构、链式存储结构的构造原理。

（3）在不同存储结构的基础上对堆栈 、队列实施基本操作（插入与删除等）对应的算法设

计与实现 。

4、哈希表

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

（2）哈希表的实现方式。

5
、树

（1）树的概念和性质 。

（2）二叉树的概念、性质和实现
。

（3）二叉树的顺序存储结构和链式存储结构。

（4）遍历二叉树 。

（5）树和森林的存储结构 、遍历
。

（6）堆与优先队列。

（6）二叉排序树 。

（7）平衡二叉树
。

（8）哈夫曼(Huffman)树和哈夫曼编码。

6.并查集

（1）并查集的概念与实现 。

7
、图

（1）图的基本概念。

（2）图的存储
，包括邻接矩阵法、邻接表法
。

（3）图的遍历操作，包括深度优先搜索 、广度优先搜索。

（4）最小生成树 ，最短路径
，关键路径
、拓扑排序算法的原理与实现 。

8、排序

（1）排序的基本概念
。

（2）插入排序 、冒泡排序
、快速排序、堆排序 、归并排序
、基数排序算法的原理、复杂度。

9 、算法基础

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

（2）贪心法、分治法
、动态规划的基本概念
。

（3）计算复杂度类别的基本概念，NP-Complete问题。

五、参考书目

ThomasH.Cormen/CharlesE.Leiserson/RonaldL.Rivest/CliffordStein ，算法

导论（第3版）（原版与中译版均可）

编制单位：上海科技大学信息科学与技术学院

编制日期：2017年6月20日