2006数据结构大纲

《2006数据结构大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1. 关于算法： （1）算法语言无所谓，只要能看懂。考试用C++出题，但答题随意(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以)。 （2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的注释  （3）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并说明函数功能、入口参数、出口参数2. 考试范围和重点不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。各章节以下面的内容为复习重点，尤其是___________、黑体

2、字或★标出部分为重中之重。其中黑体字为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。第1章概论（教材中本章作者为许卓群）一.重要概念    1.数据类型2.抽象数据结构3.数据结构4.存储结构5.算法6.算法度量(时间代价、空间代价)    7. 数据结构的选择和评价二.方法     1.根据二元组画出图示逻辑结构(注意边的方向)    2.根据要求设计数据结构    3.算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）　第2章线性表（教材中本章作者

3、为许卓群）一.概念     1.线性表2.单链表3.双链表4.循环表5.栈6.队列7.循环队列二.方法    1.线性表的运算(指针操作的正确性)   2.循环队列队列的实现  ★3.表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法)   4.栈的性质，用栈来生成序列　第3章字符串（教材中本章作者为许卓群）一.概念1.串2.模式匹配二.方法1.串的基本操作2.串的存储★3.串的KMP快速模式匹配算法(next数组)，求特征next数组（N数组）和利用next数组完成匹配的方法　第4章二叉树（教材中本章作者

4、为杨冬青）一.概念      1.二叉树2.二叉树的前序、中序、后序周游3.二叉排序树4.穿线树(中序、前序、后序)5.Huffman树、Huffman编码6.堆、堆排序二.方法       1．二叉树的链式存储        （1）二叉链表        （2）带父指针的三重链表       2.二叉树的顺序存储          完全二叉树的顺序存储   ★3.使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归的方法)、使用队列层次地周游二叉树，在周游过程中寻找某个结点或进行某种操作(结

5、合应用，例如穿线树，或把快速排序转换成非递归形式)       4.二叉检索树的插入与删除       5.构造Huffman树，利用Huffman树进行编码、解码       6.堆排序的建堆过程　第5章树（教材中本章作者为杨冬青）一.概念       1.树、森林 2.树、森林的先根周游、后根周游、层次周游二.方法     1.树林与二叉树相互转换      2．森林的链式存储           (1)转换为相应的二叉树，用二叉链表表示           (2)父指针表示法            (3)子结点

6、表表示法      3.森林的顺序存储      不必死记各种顺序存储方法，要了解原理。其本质是按照周游的性质，把顺序存储的森林信息反构造成森林（在内存中往往用二叉树来表示）      4.二叉树和森林的层次周游(用队列)，可能结合应用　第6章图（教材中本章作者为杨冬青）一.概念    1.图的深度周游2.图的宽度周游3.图的生成树、生成树林、最小生成树（不要求掌握关键路径）二.方法  ★1.图的存储方法      （1）相邻矩阵（2）邻接表(结点表--边表)    2.图的周游      （1）深度优先（2）宽度优

7、先    3.图的生成树与最小生成树      （1）从某一点出发，按深度优先或宽度优先周游的生成树      （2）最小生成树①Prim算法②Kruskal算法(避圈法)    4.拓扑排序:对于给定图，找出若干个或所有拓扑序列       任何无环的有向图，都可以拓扑排序。    5.最短路径       Dijkstra算法、Floyd算法(这两个算法都属于贪心法，也属于动态规划法)★两个算法的关键都在求Min的部分    6.贪心法　★第7章内排序（教材中本章作者为张铭）二.方法    1.重点排序算法：直接

8、插入法、Shell排序、★快速排序、基数排序、归并排序    2.算法分析      （1）基于比较次数和移位次数（一个移位就是一次纪录赋值操作，例如一次swap交换是3次移位），分析最好、最坏的时间、空间      （2）记住各种排序方法的平均时间     3.各种排序方法的局部修改和混合应用　第8章文件管理和外排序（教材中本章作者为唐世渭）