辽宁科技大学 2023 年全国硕士研究生入学考试

《专业基础综合 (含数据结构与算法、数据库原理)》考试大纲

科目代码：808

数据结构与算法

参考书目

《数据结构 (C++版)》王红梅，胡明，王涛 清华大学出版社 2011 《计算机算法设计与分析》 王晓东编著 电子工业出版社 (任意版本)

数据库原理

参考书目 《数据库系统概论》(第 5 版) 王珊，萨师煊 高等教育出版社 2014

考试时间：3 小时

考试方式：闭卷 笔试

总 分：150 分

数据结构与算法考试大纲

1. 目的：考察学生能否熟练掌握组织数据、存储数据和处理数据的基本方法，是否具备 一定的分析问题和解决问题的能力。

2.考试内容的基本要求、重点和难点

(一) 一般要求：

掌握数据结构和算法的基本概念方法，并能够熟练运用于解决实际问题。这些概念包括: 数据、数据元素、数据类型、抽象数据类型、数据逻辑结构、数据存储结构、数据结构上的 操作、算法及算法特点等;

了解和掌握算法效率分析的意义和方法;

了解抽象数据类型的概念和表示形式。

(二) 具体要求：

1) 线性结构

一维和多维数组、单链表、双链表、栈、队列、字符串的性质和用途，以及在程序设计 语言中实现相应结构存储和运算。

2) 非线性结构 (树和图)

树和图的存储方法和相关操作 (二叉树的前序、中序、后序遍历，图的深度优先、广度 优先遍历，最小生成树的构造，图的最短路径等)

3) 算法

递归和分治法

回溯法及其与深度优先搜索的关系

各种常见排序算法和查找算法的效率和特点 (插入排序、选择排序、冒泡排序、快速排 序、归并排序、堆排序、线性搜索和二分搜索)

数据库原理考试大纲

( 一) 绪论

内容及基本要求：掌握数据、数据库、数据库管理系统、数据库系统的基本概念，了解 数据管理技术的进展情况、数据库技术产生和发展的背景，掌握数据模型的基本概念、组成 要素和理解主要的数据模型，理解概念模型的基本概念及熟练掌握 E-R 方法，掌握数据库系 统的 3 级模式结构以及数据库系统的组成。

(二) 关系数据库

内容及基本要求：掌握关系模型的三个组成部分及其各部分所包括的主要内容;掌握关 系数据结构及其形式化定义;掌握关系的三类完整性约束的概念。了解关系数据库理论产生 和发展的过程，关系数据库产品的发展及沿革。熟练掌握关系代数的各种运算，包括并、交、 差、选择、投影、连接、除及广义笛卡儿积。

(三) 关系数据库标准语言 SQL

内容及基本要求：了解 SQL 语言发展的过程及特点，掌握 SQL 的数据定义功能，熟练掌 握 SQL 对数据库的查询、插入、删除、更新等操作，掌握 SQL 中视图的操作。

(四) 数据库安全性

内容及基本要求：了解计算机以及信息安全技术标准的进展。理解最重要的存取控制技 术、视图技术和审计技术。熟练掌握存取控制机制中用户权限的授权与回收、合法权限检查、 数据库角色的概念和定义等。了解数据加密和统计数据库的安全性。

(五) 数据库完整性

内容及基本要求：掌握 RDBMS 的数据库完整性实现机制，包括实体完整性、参照完整 性和用户自己定义的完整性约束的定义机制、完整性检查机制和违背完整性约束条件时 RDBMS 采取的预防措施。理解触发器的概念和掌握触发器在数据库完整性检查中的应用。

(六) 关系数据理论

内容及基本要求：掌握数据依赖的基本概念 (包括函数依赖、平凡函数依赖、非平凡的 函数依赖、部分函数依赖、完全函数依赖、传递函数依赖的概念;码、候选码、外码的概念 和定义;多值依赖的概念)，掌握范式的概念、1NF、2NF、3NF、BCNF、4NF 的概念和判定方 法。掌握数据依赖的 Armstrong 公理系统。

了解什么是一个"不好"的数据库模式，什么是模式的插入异常和删除异常。

(七) 数据库设计

内容及基本要求：了解数据库设计的特点，掌握数据库设计的基本步骤，掌握数据库设 计过程中数据字典的内容，掌握数据库设计各个阶段的设计目标、具体设计内容、设计描述、 设计方法等。重点掌握 E-R 图的设计及 E-R 图向关系模型的转换

(八) 数据库编程

内容及基本要求：掌握嵌入式 SQL、游标的概念;掌握 SQL 的过程化扩展 PL/SQL 和存 储过程的基本概念，基本结构，语句语法和用法; 了解使用ODBC 设计开发数据库应用程序 的方法。

(九) 关系查询处理和查询优化

内容及基本要求：理解关系数据库查询优化的重要性和可能性;掌握查询处理步骤;理 解实现查询操作的主要算法，主要是选择操作和连接操作的主要算法思想;了解关系代数表 达式等价变换规则;掌握关系代数表达式的优化;掌握物理优化方法。能够把 SQL 语句转换 成查询树，对查询树进行代数优化，转换成优化的查询树。

(十) 数据库恢复技术

内容及基本要求：熟练掌握事务的基本概念和事务的 ACID 性质。掌握包括数据库运行 中可能发生的故障类型，掌握数据库恢复中最经常使用的技术—数据转储和登录日志文件。 掌握针对事务故障、系统故障和介质故障等不同故障的恢复策略和恢复方法。理解具有检查

点的恢复技术。理解数据库镜像功能。

重点：事务的基本概念和事务的 ACID 性质。数据库故障恢复的策略和方法。

(十一) 并发控制

内容及基本要求：讨论数据库并发控制的基本概念和实现技术。掌握并发操作产生的数 据不一致性 (丢失修改、不可重复读、读“脏数据”) 的确切含义。掌握封锁技术;理解活 锁和死锁的概念;掌握并发调度的可串行性;理解冲突可串行化调度、掌握两段锁协议、理 解封锁的粒度、意向锁。