一、       考试的总体要求

本考试内容由两部分组成，数据结构和程序设计，各占总分的50％。

数据结构是计算机科学与技术专业基础课,要求学生掌握基本的数据结构及相关的存储方式、基本运算、算法和应用,并能运用盒图、结构化语言、类C、高级语言（C或C++）等方法之一编写算法。

程序设计指采用C++语言，应用数据结构的知识进行面向对象程序设计。要求学生掌握面向对象的程序设计方法，掌握C＋＋语言的基本概念，语法及编程方法。

二、       考试的内容及比例

数据结构考试的内容包括：（ 占总分50%）

1、  线性表、顺序表、链表的定义、特点、存储结构及相关的基本算法

2、  栈的定义、特点、顺序与链式存储表示、基本算法；栈的应用；队列的定义、特点；链队列、循环队列相关的定义、特点、基本算法；栈与递归的实现

3、  广义表的定义及存储结构

4、  二叉树的定义、性质及存储结构；遍历二叉树定义、过程及其算法；二叉树的应用；树、森林与二叉数之间的转换；哈夫曼树及其应用；与二叉树应用相关的递归算法

5、  图的定义、存储结构；图的遍历过程及算法；最小生成树构造过程及算法；拓扑排序过程及算法；关键路径相关内容；最短路径相关内容；与图的应用相关的递归算法

6、  静态表查找过程及算法、动态表查找过程及算法；哈希表的构造及处理冲突方法

7、  插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点、过程及算法

程序设计考试的内容包括：（ 占总分50％）

1、  基本语法与常用语句，面向对象的基本概念

2、  函数的调用，函数参数，函数的重载及函数作用域

3、  类的概念，类的定义与说明，类的成员函数，作用域

4、  对象的概念，对象的初始化，对象的特殊生成方法，对象的生存期

5、  对象指针和对象引用，对象数组

6、  类的继承性和派生类

7、  虚基类与虚函数

8、  重载及其应用

9、  模版及其应用

10、基本数据结构和算法的程序设计

三、       试卷类型及比例

考试题型：

数据结构部分：

包括实做题与算法设计题两大类：其中实做题有简述题、举例说明题、图示题、图表题、过程描述题、论述题等。算法设计题应当根据要求，运用允许使用的适当的方法编写算法。

比例：    实做题（60%）

算法设计题（40%）

程序设计部分：

包括2类题型：写程序结果和程序设计。      

写程序结果题：本题型给出C++程序，并已经调试通过，考生需要根据C++的语法与语义给出正常运行后应该输出的结果。需要按照程序运行的顺序给出正确结果，不需要对程序的正确性进行判断。

本题型为42分，6-7个题。

程序设计： 按照题中的要求，写出完整的C++程序，并符合程序设计规范。

本题型为33分，2个题。

四、       考试形式及时间

考试形式均为笔试，考试时间为三小时（满分150分）。

五、       参考书目

数据结构：

1、  《数据结构》C语言版，严为敏吴伟民编，清华大学出版社，2009.

2、  《数据结构》 (用面向对象方法与C++描述)，殷人昆等，清华大学出版社，2007.

程序设计：

1、  《C++程序设计》，Y. Daniel Liang著，王刚 刘晓光 刘璟译，机械工业出版社

2、  《C++编程思想(两卷合订本) 》埃克尔(Bruce Eckel)、Chuck Allison、刘宗田、 袁兆山 机械工业出版社

3、  《C++程序设计语言(特别版o十周年中文纪念版)》斯特朗斯特鲁普(Bjarne Stroustrup)、裘宗燕 机械工业出版社