考试科目：数据结构与数据库技术

代码：938

本考试科目包括《数据结构》和《数据库应用》两门课程，其中《数据结构》内容占90分(60%)，《数据库技术》占60分(40%)。

《数据结构》考试大纲

指定教材：《数据结构》(C语言版)，严蔚敏主编，清华大学出版社。

考试重点：1. 线性表的链表存储结构、基本运算及其算法应用;

2. 二叉树的各种遍历算法;二叉排序树和哈夫曼树;

3. HASH函数(表)及其查找算法;

4. 各种排序算法及其算法复杂度分析。

第一章、绪论

掌握算法的时间复杂度和空间复杂度分析方法。

第二章、线性表

2.1 掌握线性表的顺序存储结构

2.2 熟练掌握线性表的链表存储结构、单链表的基本运算算法及其应用

2.3 了解循环链表和双向链表

第三章、栈和队列

3.1 掌握栈的基本概念

3.2 熟练掌握栈的顺序与链表存储结构、栈的基本运算算法

3.3 掌握队列的基本概念

3.4 掌握队列的顺序与链表存储结构、队列的基本运算算法

3.5 掌握栈和队列的应用

第四章、串

了解串的基本概念及其存储结构

第五章、数组和广义表

了解稀疏矩阵的概念

第六章、树

6.1 了解树的基本概念与定义

6.2 掌握二叉树的基本概念与定义

6.3 熟练掌握二叉树的前序、中序和后序遍历算法

6.4 了解线索二叉树

6.5 掌握二叉树、树和森林的转换方法

6.6 熟练掌握二叉排序树和哈夫曼树

第七章、图

7.1 掌握图的基本概念和术语

7.2 掌握图的存储结构

7.3 了解图的遍历方法

7.4 掌握图的拓扑排序算法

第八章、查找

8.1 熟练掌握顺序表的查找算法及其算法复杂度分析

8.2 熟练掌握有序表(折半查找)的查找算法及其算法复杂度分析

8.3 掌握索引表的查找算法及其算法复杂度分析

8.4 熟练掌握二叉排序树查找算法及其算法复杂度分析

8.5 熟练掌握HASH表及其查找算法

第九章、排序

9.1 熟练掌握直接插入排序算法及其算法复杂度分析

9.2 熟练掌握折半插入排序算法及其算法复杂度分析

9.3 熟练掌握希尔排序算法及其算法复杂度分析

9.4 熟练掌握冒泡排序算法及其算法复杂度分析

9.5 了解快速排序算法及其算法复杂度分析

9.6 熟练掌握简单选择排序算法及其算法复杂度分析

9.7 了解堆排序算法及其算法复杂度分析

9.8 了解归并排序算法及其算法复杂度分析

9.9 了解基数排序算法及其算法复杂度分析

考试题型：

程序设计题 90分

《数据库技术》考试大纲

指定教材：1)《数据库：原理、技术与应用》、祝锡永主编，机械工业出版社。

1. 掌握数据库的基本概念;了解常用的关系型数据库管理系统，如SQL SERVER、ORACLE等;

2. 熟练掌握数据表的定义，记录(行)的插入、修改及删除等操作命令;

3. 熟练掌握SELECT查询语言，包括带WHERE、GROUP BY、JOIN子句和子查询的使用;熟练掌握集合(聚合)函数的使用方法。

4. 熟练掌握存储过程的使用

5. 熟练掌握关系代数的各种运算

6. 掌握E-R图，并能根据E-R导出关系模式

考试题型：

解答题(编写SQL语句或关系代数表达式、画E-R图并导出关系模式)60分