考试科目：数据结构与程序设计（一） 适用专业：计算机软件与理论
计算机应用技术
一、 复习要求：
要求考生熟悉面向对象的程序设计和各种数据结构的基本概念，掌握数据结构的有关算法和程序设计的方法，能运用程序设计语言C++编写算法或程序。
二、主要复习内容：
1． 数据结构的基本概念和C++语言基础
数据结构的基本概念；相关的术语；C++语言基础；算法性能与复杂度（算法的定义、算法的性能标准、算法复杂度）。
重点：数据结构的基本概念、C++语言基础、算法的定义和复杂度
2．抽象数据类型和C++类
抽象数据类型（数据抽象、封装和信息隐藏、抽象数据类型描述）；类与对象（消息与合作、多态性）；面向对象的程序设计方法；C++类与对象；构造函数和析构函数；工具函数；继承；虚函数及动态联编；模板类
重点：抽象数据类型；C++类与对象；继承；模板类
3．线性表
线性表的定义；线性表的顺序表示（顺序表的类定义、顺序表插入、删除算法）；线性表的链表表示（单链表、单循环链表、双向循环链表、静态链表）；多项式抽象数据类型
重点：线性表的定义；线性表的顺序表示；线性表的链表表示
4．栈、队列和递归
栈（顺序栈、链式栈、表达式的计算）；队列（循环队列、链队列）；递归（递归的概念、 递归过程与递归工作栈、消除递归）；迷宫问题
重点：栈与队列的顺序表示和链式表示的类定义及相关的操作；递归的概念和算法
5．串、数组和广义表
字符串(字符串的定义、存储结构和操作、串的操作、常用的C++字符串函数、串类及其实现、模式匹配算法)；数组（C++中数组的定义、数组的抽象数据类型表示、数组的顺序存储结构）；稀疏矩阵（三元组顺序表、十字链表）；广义表（广义表的定义、广义表的存储结构、n元多项式的表示、广义表的递归算法）
重点：字符串；数组的顺序存储结构；稀疏矩阵；广义表的定义、广义表的存储结构及其递归算法
6．树和森林
树的概念（树的定义、树的术语、树的表示形式、树的基本操作和抽象数据类型）；二叉树（二叉树的定义、二叉树的性质、二叉树的基本操作和抽象数据类型）；二叉树的存储结构（数组表示法、链表表示法、二叉树的二叉链表类声明）；遍历二叉树；线索二叉树（线索二叉树的定义、线索二叉树的类定义、中序线索二叉树）；二叉树的应用（堆、哈夫曼树）； 树和森林（树的存储结构、树、森林和二叉树的转化、树的遍历和森林的遍历）；等价类及其表示；并查集
重点：树的概念；二叉树；二叉树的存储结构；遍历二叉树；线索二叉树；堆；哈夫曼树；树、森林和二叉树的转化；树的遍历和森林的遍历
7．图
图的基本概念（图的定义、术语、基本操作和抽象数据类型）；图的存储结构（邻接矩阵、 邻接表、邻接多重表、十字链表）；图的遍历与连通性（深度优先遍历、广度优先遍历、连通分量）；最小生成树（克鲁斯卡尔算法和普里姆算法）；最短路径问题；活动网络（用顶点表示活动的网络、用边表示活动的网络(AOE网络))
重点：图的基本概念；图的存储结构；图的遍历与连通性；最小生成树；最短路径问题；活动网络
8．查找
查找的基本概念；顺序表（顺序表的查找、有序表的折半查找）；索引顺序表；倒排表；二叉排序树（二叉排序树定义；二叉排序树上的查找、插入和删除；二叉排序树查找的性能分析）；平衡二叉树（平衡二叉树的定义、平衡旋转、平衡二叉树的插入和删除）；B—树（动态的m路查找树、B—树、B—树的插入和删除、B+树）；散列表查找（散列表的基本概念、 散列函数、处理溢出的闭散列方法、处理溢出的开散列方法—链地址法、散列表分析）
重点：查找的基本概念；；顺序表的查找；有序表的折半查找；索引顺序表；二叉排序树；平衡二叉树；B—树；散列表查找；散列函数、处理溢出的闭散列方法、处理溢出的开散列方法—链地址法
9．排序
排序的基本概念；排序表的抽象数据类型描述和类定义；交换排序（冒泡排序、快速排序）；插入排序（直接插入排序、折半插入排序）；希尔排序；选择排序（直接选择排序、锦标赛排序、堆排序）；归并排序（归并、两路归并排序、递归的归并排序）；基数排序(多关键字排序、链式基数排序；各种排序方法的选择和使用
重点：排序的基本概念；排序表的抽象数据类型描述和类定义；各种排序算法
三、参考书目：
1．《数据结构——C++实现》，缪淮扣等 编著，科学出版社 2004年7月第二次印刷
2．《C++程序设计教程》，钱能主编，清华大学出版社，1999
计算机应用技术
一、 复习要求：
要求考生熟悉面向对象的程序设计和各种数据结构的基本概念，掌握数据结构的有关算法和程序设计的方法，能运用程序设计语言C++编写算法或程序。
二、主要复习内容：
1． 数据结构的基本概念和C++语言基础
数据结构的基本概念；相关的术语；C++语言基础；算法性能与复杂度（算法的定义、算法的性能标准、算法复杂度）。
重点：数据结构的基本概念、C++语言基础、算法的定义和复杂度
2．抽象数据类型和C++类
抽象数据类型（数据抽象、封装和信息隐藏、抽象数据类型描述）；类与对象（消息与合作、多态性）；面向对象的程序设计方法；C++类与对象；构造函数和析构函数；工具函数；继承；虚函数及动态联编；模板类
重点：抽象数据类型；C++类与对象；继承；模板类
3．线性表
线性表的定义；线性表的顺序表示（顺序表的类定义、顺序表插入、删除算法）；线性表的链表表示（单链表、单循环链表、双向循环链表、静态链表）；多项式抽象数据类型
重点：线性表的定义；线性表的顺序表示；线性表的链表表示
4．栈、队列和递归
栈（顺序栈、链式栈、表达式的计算）；队列（循环队列、链队列）；递归（递归的概念、 递归过程与递归工作栈、消除递归）；迷宫问题
重点：栈与队列的顺序表示和链式表示的类定义及相关的操作；递归的概念和算法
5．串、数组和广义表
字符串(字符串的定义、存储结构和操作、串的操作、常用的C++字符串函数、串类及其实现、模式匹配算法)；数组（C++中数组的定义、数组的抽象数据类型表示、数组的顺序存储结构）；稀疏矩阵（三元组顺序表、十字链表）；广义表（广义表的定义、广义表的存储结构、n元多项式的表示、广义表的递归算法）
重点：字符串；数组的顺序存储结构；稀疏矩阵；广义表的定义、广义表的存储结构及其递归算法
6．树和森林
树的概念（树的定义、树的术语、树的表示形式、树的基本操作和抽象数据类型）；二叉树（二叉树的定义、二叉树的性质、二叉树的基本操作和抽象数据类型）；二叉树的存储结构（数组表示法、链表表示法、二叉树的二叉链表类声明）；遍历二叉树；线索二叉树（线索二叉树的定义、线索二叉树的类定义、中序线索二叉树）；二叉树的应用（堆、哈夫曼树）； 树和森林（树的存储结构、树、森林和二叉树的转化、树的遍历和森林的遍历）；等价类及其表示；并查集
重点：树的概念；二叉树；二叉树的存储结构；遍历二叉树；线索二叉树；堆；哈夫曼树；树、森林和二叉树的转化；树的遍历和森林的遍历
7．图
图的基本概念（图的定义、术语、基本操作和抽象数据类型）；图的存储结构（邻接矩阵、 邻接表、邻接多重表、十字链表）；图的遍历与连通性（深度优先遍历、广度优先遍历、连通分量）；最小生成树（克鲁斯卡尔算法和普里姆算法）；最短路径问题；活动网络（用顶点表示活动的网络、用边表示活动的网络(AOE网络))
重点：图的基本概念；图的存储结构；图的遍历与连通性；最小生成树；最短路径问题；活动网络
8．查找
查找的基本概念；顺序表（顺序表的查找、有序表的折半查找）；索引顺序表；倒排表；二叉排序树（二叉排序树定义；二叉排序树上的查找、插入和删除；二叉排序树查找的性能分析）；平衡二叉树（平衡二叉树的定义、平衡旋转、平衡二叉树的插入和删除）；B—树（动态的m路查找树、B—树、B—树的插入和删除、B+树）；散列表查找（散列表的基本概念、 散列函数、处理溢出的闭散列方法、处理溢出的开散列方法—链地址法、散列表分析）
重点：查找的基本概念；；顺序表的查找；有序表的折半查找；索引顺序表；二叉排序树；平衡二叉树；B—树；散列表查找；散列函数、处理溢出的闭散列方法、处理溢出的开散列方法—链地址法
9．排序
排序的基本概念；排序表的抽象数据类型描述和类定义；交换排序（冒泡排序、快速排序）；插入排序（直接插入排序、折半插入排序）；希尔排序；选择排序（直接选择排序、锦标赛排序、堆排序）；归并排序（归并、两路归并排序、递归的归并排序）；基数排序(多关键字排序、链式基数排序；各种排序方法的选择和使用
重点：排序的基本概念；排序表的抽象数据类型描述和类定义；各种排序算法
三、参考书目：
1．《数据结构——C++实现》，缪淮扣等 编著，科学出版社 2004年7月第二次印刷
2．《C++程序设计教程》，钱能主编，清华大学出版社，1999