自命题科目考试大纲

科目代码及名称：808 数据结构与程序设计

适用专业：计算机科学与技术  计算机技术

一、考试目的及要求

“数据结构与程序设计”入学考试是为招收计算机科学与技术类硕士生而实施的选拔性考试，主要涉及数据结构、C/C++程序设计课程的内容。主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。要求考生具有较全面的数据结构表示与实现的基础知识；具有较高的分析问题和解决问题的能力；具有较强的综合知识运用能力。

二、考试内容

1．绪论

1.1 数据结构的基本概念；

1.2 抽象数据类型；

1.3 算法和算法的时间复杂度。

2. 线性表

2.1 线性表概述；

2.2 线性表的顺序表示和实现；

2.3 线性表的链式表示和实现；

2.4 静态链表；

2.5 线性表的基本运算。

3. 堆栈和队列

3.1 堆栈；

3.2 堆栈应用；

3.3 队列；

3.4 优先级队列。

4. 串

4.1 串概述；

4.2 串的存储结构；

4.3 串基本操作的实现算法；

4.4 串的模式匹配算法-BF和KMP算法。

5. 数组

5.1 数组概述；

5.2 动态数组；

5.3 特殊矩阵的压缩存储；

5.4 稀疏矩阵的压缩存储。

6. 递归算法

6.1 递归的概念；

6.2 递归算法的执行过程；

6.3 递归算法的设计方法；

6.4 递归过程和运行时栈；

6.5 递归算法的时间效率分析。

7. 树和二叉树

7.1 树；

7.2 二叉树；

7.3 二叉树的设计和实现；

7.4 二叉树遍历；

7.5 线索二叉树；

7.6 哈夫曼树；

7.7 等价问题；

7.8 树与二叉树的转换；

7.9 树的遍历。

8. 图

8.1 图概述；

8.2 图的存储结构；

8.3 图的实现；

8.4 图的遍历；

8.5 最小生成树；

8.6 最短路径；

8.7 拓扑排序；

8.8 关键路径。

9. 排序

9.1 排序的基本概念；

9.2 插入排序；

9.3 选择排序；

9.4 交换排序；

9.5 归并排序；

9.6 基数排序；

9.7 排序算法性能比较。

10. 查找

10.1 查找的基本概念；

10.2 静态查找； 

10.3 动态查找；

10.4 哈希查找；

三、考试的题型及比例

单项选择题（20%）

填空题（13%）

简答题（20%）

算法理解与设计题（47%）

四、考试形式及时间

考试形式为闭卷笔试。考试时间为3小时。

五、主要参考书目（可以多本）

1. 严蔚敏，《数据结构（ C语言版）》（第二版），人民邮电出版社，2016 年

2．朱战立，《数据结构（使用 C语言）》 (第五版 )，电子工业出版社，2014 年

3．M.A.韦斯，《数据结构与算法分析 --- C++ 语言描述》， (第四版 )，电子工业出版社，2016 年