考试科目代码：840 考试科目名称: 数据结构与面向对象程序设计

第一部分 数据结构

一、考试要求

数据结构是计算机相关专业的专业基础课。本门课程要求考生能够比较系统地理解数据结构的基本概念、基本原理和方法，掌握数据的逻辑结构、存储结构以及各种基本操作的实现;要求考生能够运用所学的基本原理和基本方法分析、判断和解决相关的理论问题和实际问题;要求考生能够对算法进行设计与分析并选择适当的数据结构和方法进行问题求解。

二、考试内容范围

1. 数据结构中的基本定义

(1) 数据结构的基本概念，数据的逻辑结构、存储结构。

(2) 抽象数据类型的定义、表示和实现。

(3) 算法定义及算法的基本特性，算法分析的基本概念。

2. 线性结构

(1) 线性表的定义，线性表的基本操作，线性表的顺序存储结构和基本运算的实现，线性表的链式存储结构 ( 包括单链表、循环链表和双向链表 ) 和基本运算的实现，从时间和空间复杂度的角度综合比较线性表两种存储结构的特点及其适用场合。

(2) 串的定义、存储表示和基本操作，在定长顺序存储结构上实现串的基本操作算法。

(3) 数组的定义、顺序存储表示和基本运算的实现。

3. 树与二叉树

(1) 树与二叉树的基本概念，包括基本特征、基本操作。

(2) 二叉树的基本性质、二叉树的二叉链表存储结构、二叉树的三种基本遍历算法 ( 前序、中序和后序 ) ;由二叉树的遍历序列恢复二叉树;二叉树遍历的应用。

4. 图

(1) 图的定义，基本概念，图的分类。

(2) 图的邻接矩阵存储方法、邻接表存储方法。

(3) 图的深度优先和广度优先遍历算法。

(4) 最小生成树 (Prim 算法和 Kruskal 算法 ) ，最短路径， AOV 网与拓扑排序。

5. 查找

(1) 顺序表和有序表的查找方法。

(2) 二叉排序树的基本概念、建立和查找。

(3) 平衡二叉树的维护平衡的方法 。

(4) 哈希查找和哈希表。

6. 内排序

(1) 排序的基本概念，排序方法的分类。

(2) 插入排序 ( 含折半插入排序 ) 、希尔排序、选择排序、归并排序、快速排序、堆排序。

(3) 各种排序方法排序的特点及比较，各种排序算法的时空复杂度简单分析。

第二部分 面向对象程序设计(JAVA语言)

一、考试要求

面向对象程序设计指采用JAVA语言，要求考生掌握Java程序设计基本步骤与过程;熟悉Java各种基本数据类型及其操作，学会根据实际问题要求来选择数据类型;掌握Java语言基本程序设计技术;掌握Java面向对象程序设计的抽象性、封装性、继承性和多态性;熟悉如何使用面向对象程序设计方法进行程序设计。

二、考试内容范围

1. JAVA语言基础

(1) 使用标识符命名变量、常量、方法和类。

(2) Java的基本数值类型。

2. 选择结构

(1) 使用单分支if语句实现选择控制。

(2) 使用双分支if-else语句实现选择控制。

(3) 使用嵌套的if语句和多分支if语句实现选择控制。

(4) 使用switch语句实现选择控制。

3. 数学函数、字符和字符串

(1) 使用Math类中的方法解决数学问题。

(2) 使用char类型表示字符。

(3) 使用string对象表示字符串。

(4) 使用length()方法来返回字符串长度。

(5) 使用charAt(i)方法来返回字符串中的字符。

(6) 使用indexOf方法定位一个字符串中的字符或子字符串。

4. 循环结构

(1) 使用while循环编写重复执行语句的程序。

(2) 使用do-while语句编写循环。

(3) 使用for语句编写循环。

(4) 使用break和continue来实现程序的控制。

5. 方法

(1) 使用形参定义方法。

(2) 使用实参调用方法。

(3) 定义带返回值的方法。

(4) 定义无返回值的方法。

6. 一维数组与多维数组

(1) 声明数组引用变量以及创建数组。

(2) 使用下标访问数组元素。

(3) 使用线性查找算法和二分查找算法查找数组中的元素。

(4) 使用选择排序法对数组排序。

7. 对象和类

(1) 描述对象和类，并使用类来建模对象。

(2) 使用UML图形符号来描述类和对象。

(3) 使用构造方法创建对象。

(4) 通过对象引用变量访问对象。

(5) 使用引用类型定义引用变量。

(6) 使用对象成员访问操作符来访问对象的数据和方法。

(7) 封装数据域使得类易于维护。

7. 继承与多态

(1) 通过继承由父类定义子类。

(2) 使用关键字super调用父类的构造方法和方法。

(3) 在子类中重写实例方法。

(4) 区分重写和重载的不同。

8. 抽象类和接口

(1) 设计和使用抽象类。

(2) 使用接口指定对象共同的行为。

(3) 定义接口以及实现接口的类。

考试总分：150分 考试时间：3小时 考试方式：闭卷，笔试

考试题型： 选择题、填空题、简答题、程序分析题及综合应用题

参考书目：

[1] 严蔚敏等. 数据结构(C语言版).清华大学出版社, 2014

[2] 沈泽刚等.Java语言程序设计，清华大学出版社,2018