科目代码：852 科目名称：数据结构与数据库
一. 考试要求
数据结构主要考查学生对数据结构的基本概念、基本原理和基本方法的掌握；对数据的逻辑结构、存储结构及基本操作的掌握；运用数据结构基本原理和方法进行问题的分析与求
解，设计与实现算法的能力。数据库主要考查学生对数据库技术基本概念、关系代数与关系模型、查询语言SQL、数据库设计理论、数据库事务与并发控制技术的理解与掌握；运用
数据库技术进行数据库设计、管理的能力。
二、考试内容
数据结构部分
1．数据结构概述
数据结构的基本概念（逻辑结构、存储结构），抽象数据类型的概念以及算法时空复杂性的分析和度量方法。
2．线性表
线性表的概念，顺序表、单链表、静态链表和循环链表的数据结构以及相应算法。
3．栈和队列
栈和队列的定义、实现、基本运算，栈和队列的应用，递归的方法。
4．串、数组和广义表
串、数组、广义表的定义，字符串的存储结构和相应算法，字符串的模式匹配算法，矩阵的压缩存储方法和广义表的递归算法。
5．树与二叉树
树、二叉树和森林的概念及常用表示法，树、二叉树以及森林的遍历，线索二叉树，森林与二叉树的转换，赫夫曼树和赫夫曼编码。
6．图
图的基本概念和图的存储表示，图的深度、广度优先搜索，图的连通性问题，有向无环图，图的应用（最小生成树、拓扑排序、关键路径、最短路径）。
7．查找
查找的基本概念，顺序查找、折半查找、索引表查找的方法，二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，平衡二叉树的构造、性能分析方法，B-树、B+树的搜
索和构造方法；散列法，包括散列函数的构造、解决冲突的方法。
8．排序
排序的基本概念，插入排序、交换排序、选择排序、归并排序、基数排序等排序方法及其性能分析方法。
数据库部分
1．数据库技术的基本概念
数据描述，数据模型，数据库体系结构，数据库管理系统，数据库系统。数据管理技术的历史与发展前景。
2．关系模型和关系代数
关系模型的基本概念，关系代数的各种运算（并、交、差、笛卡儿积、投影、选择、联接、自然联接、除）。
3．SQL语言
SQL概念，SQL数据查询，SQL数据更新，SQL数据定义，视图定义和视图操作。
4．关系数据理论
关系模式的设计问题，函数依赖，多值依赖，关系模式的范式（1NF、2NF、3NF、BCNF、4NF），关系模式的分解。
5．数据库设计
设计方法概述，设计基本步骤及各阶段的主要工作，概念结构设计（E-R图），E-R图向关系模型转换。
6．事务与并发控制
事务的基本概念、ACID性质，数据库并发操作与并发控制机制（封锁和时标技术）。
三、考试形式
考试形式为闭卷、笔试，考试时间为3小时，满分150分。
题型包括：选择题、简答题、编写算法题、综合题等。
四、参考书目
1．《数据结构》（c语言版）．严蔚敏等编．清华大学出版社．2011
2．《数据库系统教程》．施伯乐等编．高等教育出版社．2008
