2015年中国矿业大学085212■软件工程考研大纲（官方）

科目代码

科目名称

参考书目

考试大纲

874

数据结构

《数据结构（C  语言版）》，严蔚敏主 编，清华大学出版社,2007年；
《数据结构》（用面向对象语言和C++
描述），殷人昆主编，清华大学出版社，
2012年；
《数据结构精讲与习题详解》（考研辅 导与答疑解惑），殷人昆主编，清华大 学出版社，2012 年。

一、     考试目的与要求

目的：通过本科目的考试，考察计算机专业人员对《数据结构》 课程内容的理解和掌握程度以及算法编写能力。 要求：掌握各种基本概念和术语，掌握算法描述和分析的方法。 重点是掌握数据结构的逻辑结构、存储结构及数据操作三方面的 概念及相互关系，并掌握算法复杂度的分析及分析方法。
二、     考试范围

1.数据结构相关概念
2.算法时间复杂度分析
3.线性表的顺序存储结构和链式存储结构以及相关操作、应用。
4.栈和队列的顺序存储结构和链式存储结构以及相关操作、应用。
5.字符串定义、顺序存储结构、相关操作。模式匹配算法。
6.数组定义和相关操作（主要考察多维数组）。
7.广义表定义和相关操作。
8.树，二叉树定义，链式存储结构，主要性质，基于遍历的相关递 归和非递归操作，线索化，哈夫曼树。
9.图，图的基本概念，图的邻接表和邻接矩阵的存储结构，深度优 先和广度优先遍历，最优树，最短路径，关键路径，AOV，AOE， 拓扑排序等。
10.查找，主要查找算法和时间复杂度分析。
11.排序，主要排序算法和时间复杂度分析。
三、     试题结构（包括考试时间，试题类型等）

满分  150，考试时间3  小时，试题类型主要为： 选择、填空、简答、算法编写。

875

数据库原理

《数据库系统概论》（第四版）， 王珊、萨师煊著，高等教育出版社，
2006年；
《数据库原理与应用》，孟凡荣，
清华大学出版社，2010年。

一、     考试目的与要求

考试目的：检查考生数据库原理和技术的掌握情况。 要求：掌握数据库的基本概念、基础理论以及数据库设计的方法。 重点掌握关系数据库概念，关系代数，结构化查询语言，关系规 范化理论及数据库设计的基本能力，数据库保护技术。
二、     考试范围

（1）数据库基本概念，数据库系统特点，数据库系统体系结构。
（2）关系数据库基本概念、关系运算及查询优化；关系系统定义 及分类。
（3）结构化查询语言SQL  的数据定义、操纵、查询以及控制的语 法规则及应用；
（4）关系数据理论的函数依赖、范式、Armstrong  公理及模式分 解算法。
（5）数据库设计理论和方法，设计关系数据库应用系统的原则和 步骤。
（6）数据库完整性、安全性、并发控制和数据库恢复技术。
三、     试题结构（包括考试时间，试题类型等）

考试时间：3  个小时 考试类型：
（1）选择题或判断或填空
（2）简答
（3）关系代数和SQL
（4）数据库设计
（5）规范化理论