《计算机综合》考试大纲

一、考试内容：

数据结构100分+数据库50分

（一）数据结构部分

1.数据结构基本概念

(1)数据结构的基本概念：数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。

(2)算法时间复杂度和空间复杂度的分析方法。

2.线性表

(1)线性表的定义。

(2)线性表的顺序存储结构和主要算法实现，如查找、插入和删除算法。

(3)线性表的链式存储结构和主要算法实现，如查找、插入和删除算法。

(4)循环链表、双向链表的特点。

(5)从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。

(6)线性表的应用，如线性表的合并算法。

3.栈和队列

(1)栈的定义及特点，栈的顺序存储和链接存储结构，进栈出栈算法，顺序栈栈满和栈空的条件。

(2)栈的应用，如表达式求值算法，借助栈深入理解递归算法。

(3)队列的定义及特点，队列的顺序存储(循环队)和链接存储结构，进队出队算法，循环队列中队满及队空的条件。

4.串和数组

(1)串的定义。

(2)串的古典模式匹配算法。

(3)数组地址的计算方法。

(4)特殊矩阵的压缩存储方法。

5.树和二叉树

(1)二叉树的定义和性质。

(2)二叉树的两种存储结构：顺序存储和链式存储。

(3)二叉树的创建和三种不同遍历算法，利用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等算法。

(4)线索二叉树的特性及构造方法。

(5)树和森林的定义、存储结构与二叉树的转换方法。

(6)树的应用，哈夫曼树及哈夫曼编码的构造算法、带权路径长度的计算。

6.图

(1)图的定义和性质。

(2)图的两种存储结构：邻接矩阵和邻接表。

(3)图的两种遍历策略：深度优先搜索算法和广度优先搜索算法。

(4)图的基本应用，包括拓扑排序算法、求解最短路径的迪杰斯特拉算法、构造最小生成树的两种算法（普里姆算法和克鲁斯卡尔算法）。

7.查找

(1)线性表的查找：顺序查找和折半查找算法。

(2)树表的查找：二叉排序树的定义，二叉排序树的创建、插入、删除和查找算法。

(3)散列表的查找：两种处理冲突的方法包括开放地址法（线性探测法、二次探测法）和链地址法。

(4)上述三种不同查找算法的分析，平均查找长度ASL的计算方法及时间复杂度分析，不同查找算法的适用场合。

8.排序

(1)排序的基本概念。

(2)插入排序：直接插入排序、折半插入排序和希尔排序。

(3)交换排序：冒泡排序和快速排序。

(4)选择排序：简单选择排序和堆排序。

(5)归并排序：2-路归并排序。

(6)上述各种排序方法的特点和排序过程，时间和空间复杂度的分析，排序方法“稳定”或“不稳定”的含义。排序算法的实现及适用场合。

（二）数据库部分

1.数据库系统概述

(1)数据库系统概论：数据，数据库，数据库管理系统，数据库系统，数据管理技术的产生和发展，数据库系统的特点。

(2)数据模型：数据模型的组成要素，概念模型，层次模型，网状模型，关系模型，对象模型。

(3)数据库系统结构：数据库系统模式的概念，数据库系统的三级模式结构，数据库的二级映像功能与数据独立性，数据库系统的组成。

(4)数据库技术的研究领域。

2.关系数据库

(1)关系模型概述。

(2)关系数据结构及形式化定义：关系，关系模式，关系数据库。

(3)关系的完整性：实体完整性，参照完整性，用户自定义完整性。

(4)关系代数：集合运算，关系运算。

3.关系数据库标准语言——SQL

(1)SQL概述。

(2)SQL数据定义。

(3)SQL查询：单表查询，连接查询，嵌套查询，集合查询。

(4)SQL数据更新：插入数据，修改数据，删除数据。

(5)视图：SQL创建视图，查询视图，更新视图，视图意义。

(6)数据控制：SQL授权，收回授权。

(7)嵌入式SQL。

4.关系数据库理论

(1)关系模式的冗余和异常问题。

(2)规范化：函数依赖，码，范式，2NF，3NF，BCNF，多值依赖，4NF。

(3)模式的分解。

5.数据库安全保护

(1)数据库安全性控制。

(2)数据库完整性控制。

(3)数据库并发控制。

(4)数据恢复。

6.数据库设计

(1)数据库设计的概述。

(2)需求分析。

(3)概念结构设计。

(4)逻辑结构设计。

(5)数据库物理设计。

(6)数据库实施。

(7)数据库运行维护。

7.SQL Server2000数据库管理系统

(1)Transact-SQL程序设计：变量，流程控制命令，其他命令，常用函数。

(2)存储过程和触发器。

(3)备份和还原。

二、参考书目：

严蔚敏，李冬梅，吴伟民.数据结构（C语言版）.北京：人民邮电出版社.

陈志泊，王春玲.数据库原理及应用教程（第二版）.北京：人民邮电出版社.