题号： 880

数据库、数据结构与程序设计

考试内容：

1. 数据库技术 2. 程序设计与数据结构（ C 语言版）

数据库技术：

1、数据库系统概述（了解）：包括数据库系统的产生和发展，数据、数据库、数据库管理系统、数据库系统的基本概念，常用的数据模型，E-R图，数据库系统的主要功能及特点。

2、关系模型的概念（熟悉）（关系，属性，域，元组，码，分量，主码，外码）,关系模式的三类完整性约束（实体完整性、参照完整性、用户定义完整性）。

3、关系代数（掌握）：传统的集合运算（并、差、交、笛卡尔积）和专门的关系运算（选择、投影、连接、除）。要求熟悉相关概念并能运用关系代数完成查询。

4、SQL语言（掌握）：SQL概念，基本表的概念，基本表的定义、删除与修改，索引的建立与删除，数据查询（简单查询、连接查询、嵌套查询、集合查询），数据插入、删除、修改，视图的概念，视图定义、删除、查询、更新。要求能熟练运用SQL语言解决实际问题。

5、关系数据理论（掌握）：范式（1NF，2NF，3NF，BCNF，4NF），函数依赖，多值依赖，规范化过程，模式分解的基本原则。

6、数据库设计（掌握）：设计方法概述，设计基本步骤及各阶段的主要工作，概念结构设计（E-R图），E-R图向关系模型转换。

7、数据库恢复技术（熟悉）：事务的概念，故障种类，转储，日志，镜像。

8、并发控制（掌握）：数据不一致性，共享锁和排它锁，活锁和死锁，可串行化，两段锁协议，并发事务的调度。

9、数据库新技术（了解）：了解分布式数据库的特点，数据库技术与其他相关技术的结合。

程序设计与数据结构（ C 语言版）：

1、数据结构（逻辑结构、存储结构）概念，抽象数据类型定义及实现，算法描述，时间复杂性及空间复杂性的评价。（熟悉）

2、线性表的概念，顺序表、单链表、双链表、循环链表的物理实现、基本运算、效率分析。（掌握）

3、栈和队列的定义、实现、基本运算，栈和队列的应用，递归的方法。（掌握）

4、串、数组和广义表的概念，实现及基本运算。（掌握）

5、树和二叉树的基本概念及常用表示法，树、森林与二叉树的相互转换，二叉树的遍历与线索二叉树，哈夫曼树及其应用。（掌握）

6、图的基本概念，图的实现（邻接矩阵、邻接表、十字链表），图的遍历，图的应用（最小生成树、拓扑排序、关键路径、最短路径）。（掌握）

7、查找的基本概念，顺序查找和折半查找算法，二叉排序树、二叉平衡树、哈希表的构造方法及查找过程、算法、效率分析。（掌握）

8、排序的基本概念，插入排序、快速排序、堆排序、归并排序、基数排序的过程、算法及效益评估。（掌握）

9、文件的基本概念，顺序文件和索引文件的概念，组织方法和存储结构及基本操作。（了解）

参考书目：

1. 王珊、萨师煊：《数据库系统概论（第四版）》，高等教育出版社， 2006

2. 谭浩强：《 C 语言程序设计（第三版）》，清华大学出版社

3 ． 严蔚敏、吴伟民：《数据结构（ C 语言版）》，清华大学出版社