算法分析与设计考试大纲

《算法分析与设计考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》考试大纲一、考试大纲的性质为帮助考生明确考试复习范围和有关要求，特制定本考试大纲。二、考试范围和内容 第一章数据结构基本概念1．算法的概念和算法的时间复杂度分析要点：Ø利用大O规则计算时间复杂性，对于一般算法能分析出时间复杂度。第二章线性表和数组1、线性表1．1线性表的逻辑结构1．2线性表的数组实现1．3线性表的指针实现——链表1．4特殊链表要点：Ø掌握数组实现的特点Ø掌握链表的实现方法，包括单链表，双向链表、循环链表2、数组2．1作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储2．2矩阵的压缩存储要点：Ø确定数组元素的三要素：行号、列号、

2、元素值Ø数组元素的存放地址计算Ø稀疏矩阵的存储方法第三章栈与队列1、栈：栈的特性、栈的基本运算要点：Ø栈的数组实现、栈的链表实现Ø栈满及栈空条件2、队列：队列的特性、队列的基本运算要点：Ø队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件Ø队列的链表实现：链式队列中的队头与队尾指针的表示、3、算术表达式计算：用后缀表示计算表达式，中缀表示改后缀表示第四章树1、树：树的定义、树的基本运算要点：Ø树的分层定义是递归的Ø树的一些常用术语，如结点，树根，度，树叶，树的深度等Ø树中结点个数与高度的关系Ø树的几种存储形式2、二叉树：二叉树定义、二叉树的基本运算要点：Ø二叉树性质

3、、二叉树中结点个数与高度的关系、不同种类的二叉树棵数Ø      有序树和二叉树的转化Ø      二叉树的前序·中序·后序遍历的递归算法3、二叉排序树：二叉排序树的定义及操作要点：Ø二叉排序树的查找算法4、穿线二叉树：概念，存储形式要点：Ø用游标实现穿线二叉排序树5、哈夫曼树：哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算要点：Ø哈夫曼树是带权路径长度最小的扩充二叉树Ø      构造哈夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树Ø      在构造过程中，新二叉树按根的权值加入到森林的最后第五章无向图1、图：图的定义与图的存储

4、表示要点：Ø邻接/代价邻接矩阵表示Ø邻接表表示Ø邻接多重表表示Ø边表表示2、深度优先遍历与广度优先遍历要点：Ø深度优先搜索算法和广度优先搜索算法Ø      深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程Ø      为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited3、图的连通性要点：Ø深度优先搜索可以遍历一个连通分量上的所有顶点Ø对非连通图进行遍历，可以建立一个生成森林第六章有向图1、有向图的概念要点：Ø有向图的强连通的概念第七章集合和查找技术1、集合要点：Ø用位向量实现集合的操作2、查找表要点：Ø对有序顺序表的顺序搜索算法Ø      对有

5、序顺序表的折半搜索算法第八章排序1、基本概念：关键字、关键字比较次数、数据移动次数、稳定性2、熟悉常用排序算法的稳定性、算法的复杂度3、简单排序方法3．1插入排序要点：Ø直接插入、折半插入算法的原理和实现方法3．2选择排序要点：Ø算法的原理和实现方法3．3冒泡排序要点：Ø算法的原理和实现方法4、分治法排序4．1合并排序要点：Ø算法的原理和实现方法Ø针对给定的输入实例，写出排序过程4．2快速排序要点：Ø算法的原理和实现方法Ø快速排序是一个递归的排序方法Ø当待排序关键码序列已经基本有序时，快速排序显著变慢Ø针对给定的输入实例，写出排序过程5、比较型排序方法5．1堆排序要点：Ø算法的

6、原理5．2希尔排序要点：Ø算法的原理6、各种排序方法的比较（时间复杂性、稳定性方面）三、试卷题型选择题、简答题、算法实现题四、主要参考书1.   数据结构（C语言版）.严渭敏等著，清华大学出版社，1997