2017年西北工业大学880数据库、数据结构与程序设计考研大纲

西北工业大学 题号：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 语言版）》，清华大学出版社