一、考试对象

信息与计算科学专业本科插班生

二、考试目的

使学生掌握计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

本门课程考核要求由低到高共分为“了解”、“掌握”、“熟练掌握”三个层次。其含义：了解，指学生能懂得所学知识，能在有关问题中认识或再现它们；掌握，指学生清楚地理解所学知识；熟练掌握，指学生能较为深刻理解所学知识，在此基础上能够准确、熟练地分析解决较为简单的实际问题。

三、考试方法和考试时间

1、考试方法：闭卷、笔试

2、记分方式：百分制，满分为100分

3、考试时间：120分钟

4、试题总数：26题

5、命题的指导思想和原则

    命题的总的指导思想是：全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。命题的原则是：题目数量多、份量小，范围广，最基本的知识一般要占60%左右，稍微灵活一点的题目要占20%左右，较难的题目要占20%左右。其中绝大多数是中小题目，即使大题目也不应占分太多，应适当压缩大题目在总的考分中所占的比例。客观性的题目应占比较重的份量。

6、题目类型

（1）选择题（在下列各小题的备选答案中，请把你认为正确答案的题号填入题干的括号内。少选、多选不给分。每题1分，共10分）

（2）填空题（每空1.5分，共30分）

（3）简述分析题（每题5--10分，共20分）

（4）算法分析与实现（每题10--15分，共40分）

四、考试内容、要求

第一章 数据结构基本概念

1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。

2、算法的概念和算法的时间复杂度分析

要点： 利用大O规则计算时间复杂性，对于一般算法能分析出时间复杂度。

1、线性表

1．1 线性表的逻辑结构

1．2 线性表的数组实现

1．3 线性表的指针实现——链表

1．4 特殊链表

要点：     掌握数组实现的特点

         掌握链表的实现方法，如单链表的搜索算法与插入、删除算法

第三章 栈与队列

1、栈：栈的特性、栈的基本运算

要点：        栈的数组实现、栈的链表实现

          栈满及栈空条件

2、队列：队列的特性、队列的基本运算

要点：        队列的数组实现：循环队列中队头与队尾指针的表示，队满及

队空条件

    队列的链表实现：链式队列中的队头与队尾指针的表示、

3、算术表达式计算：用后缀表示计算表达式，中缀表示改后缀表示

第四章 树

1、树：树的定义、树的基本运算

要点：        树的分层定义是递归的

            树的一些常用术语，如结点，树根，度，树叶，树的深度等

    树中结点个数与高度的关系

    树的几种存储形式

2、二叉树：二叉树定义、二叉树的基本运算

要点：        二叉树性质、二叉树中结点个数与高度的关系、不同种类的二

叉树棵数

              有序树和二叉树的转化

       二叉树的前序·中序·后序遍历的递归算法

3、二叉排序树：二叉排序树的定义及操作

要点：      二叉排序树的查找算法

4、穿线二叉树：概念，存储形式

要点：        用游标实现穿线二叉排序树

5、哈夫曼树：哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算

要点：        哈夫曼树是带权路径长度最小的扩充二叉树

       构造哈夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树

       在构造过程中，新二叉树按根的权值加入到森林的最后

6、堆：堆的定义

要点：   堆的顺序存储、堆中结点的双亲、子女和兄弟的位置

第五章 图

1、图：图的定义与图的存储表示

要点：        邻接/代价邻接矩阵表示

    邻接表表示

    邻接多重表表示

    边表表示

2、深度优先遍历与广度优先遍历

要点：        深度优先搜索算法和广度优先搜索算法

       深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程

       为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited

3、图的连通性

要点：        深度优先搜索可以遍历一个连通分量上的所有顶点

    对非连通图进行遍历，可以建立一个生成森林

4、最小生成树

要点：        对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树

    会画出用Kruskal算法及Prim算法构造最小生成树的过程

第六章  查找

1、集合

要点：    用位向量实现集合的操作

2、查找表    

要点：    对有序顺序表的顺序搜索算法

       对有序顺序表的折半搜索算法

3、散列技术

要点：        散列的概念

       哈希函数的选择

      两类解决冲突的方法及其优缺点

第七章 排序

1、基本概念：关键字、关键字比较次数、数据移动次数、稳定性

2、熟悉常用排序算法的稳定性、算法的复杂度

3、简单排序方法

3．1 插入排序

要点：        直接插入、折半插入算法的原理和实现方法

3．2 选择排序

要点：        算法的原理和实现方法

3．3 冒泡排序

要点：        算法的原理和实现方法

4、分治法排序

4．1 合并排序

要点：        算法的原理和实现方法

            针对给定的输入实例，写出排序过程

4．2 快速排序

要点：        算法的原理和实现方法

    快速排序是一个递归的排序方法

    当待排序关键码序列已经基本有序时，快速排序显著变慢

            针对给定的输入实例，写出排序过程

5、比较型排序方法

5．1 堆排序

要点：        算法的原理

5．2 希尔排序

要点：        算法的原理

6、各种排序方法的比较（时间复杂性、稳定性方面）

五、试题结构（内容、题型、分数分配）

本课程为闭卷考试，考生不得携带任何纸张、教材、笔记本、作业本、参考资料、电子读物、电子器具和工具书等进入考场。

七、指定参考书

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

《数据库系统原理》考试大纲

    一、考试对象

信息与计算科学专业本科插班生

    二、考试目的

学生应该掌握关系数据库的基本原理，关系数据库的设计理论以及数据库设计的步骤和方法。

三、考试方法和考试时间

1、记分方式：百分制，满分为100分

2、命题的指导思想和原则

    命题的总的指导思想是：全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。命题的原则是：题目数量多、份量小，范围广，最基本的知识一般要占60%左右，稍微灵活一点的题目要占20%左右，较难的题目要占20%左右。

四、  考试内容要求：

（一）数据库系统概述数据管理技术的发展历程（人工管理方式阶段、文件管理方式阶段、数据库管理方式阶段）；数据库与数据库管理系统的基本概念（数据库基本概念、数据库管理系统、数据库语言）；数据模型（数据模型的概念和种类、概念数据模型、结构数据模型）；数据库的体系结构（数据库系统的三级模式结构、数据库的二级映像功能、两级数据性、数据库操作过程）；数据库系统（硬件、软件、数据库、人员）。

（二）关系运算理论

关系的数学定义（关系的基本术语、关系的数学定义、关系数据库、关系模型、关系模式、关系数据语言）；关系代数（传统的集合运算、专门的关系运算、扩充的关系代数运算、关系代数表达式示例）。

 (三)数据库设计和规范化

数据库设计概述（数据库设计的基本概念、数据库设计方法、数据库设计的步骤）；系统规划（系统规划的任务、系统规划的成果）；需求分析（需求分析的任务、需求分析的步骤、需求分析常用的调查方法、数据字典）；概念结构设计（概念模型及其设计方法、采用E-R方法的概念设计步骤）；逻辑结构设计（逻辑结构设计的步骤、E-R图转换为关系模型、关系模式的规范化）；数据库的物理设计（物理设计的任务、物理设计的步骤、物理设计的性能）；数据库的实施和维护（数据库的实施、其他设计、运行与维护）。

（四）数据库基础--SQL语言

SOL概述（sQL发展历程、SQL特点、SOL的数据定义）；基本表的建立、修改、删除；视图的建立和删除；索引的建立和删除；SQL函数（单行函数、聚组函数、函数的嵌套）；SQL的数据查询（单表查询、联结查询、嵌套查询--子查询、集合查询、视图的查询）；SQL的数据操纵（基本表的数据操纵、视图的数据操纵）；SQL数据控制（授权、回收权限）；嵌入式SQL（SQL语言的运行环境、嵌入式SQL的使用规定）。

（五）数据库的保护

数据库的安全性管理（安全性管理的方法和原理、系统的安全措施）；数据库的恢复（数据库恢复的原理、方法和策略、备份与恢复技术）；数据库的并发性控制（并发控制的原理和方法）; 数据库的完整性控制(完整性约束的概念、完整性约束¨)。

（六）数据库的发展方向

分布式数据库系统（分布式数据库系统的定义、分布式数据库系统的特点、分布式数据库系统的结构、分布式数据库管理系统）；并行数据库系统（并行数据库系统概述、并行数据库系统的功能、并行数据库的体系结构、并行数据库的并行处理技术）

五、指定参考书

《数据库系统原理与设计》黄义宏、黄文钰编，清华大学出版社下载本文