数据结构范围

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

1、不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。各章节以下面的内容为复习重点，尤其是绿颜色文字、红色文字或★标出部分为重中之重。其中红色部分为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。第1章概论（教材中本章作者为许卓群）一.重要概念    1.数据类型2.抽象数据结构3.数据结构4.存储结构5.算法6.算法度量(时间代价、空间代价)    7. 数据结构的选择和评价二.方法     1.根据二元组画出图示逻辑结构(注意边的方向)    2.根据要求设计数据结构 

2、   3.算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）第2章线性表（教材中本章作者为许卓群）一.概念     1.线性表2.单链表3.双链表4.循环表5.栈6.队列7.循环队列二.方法    1.线性表的运算(指针操作的正确性)   2.循环队列队列的实现  ★3.表达式求值(前中后缀各种表达式互相转化、表达式树与各种表达式互相转换、前缀后缀表达式求值)   4.栈的性质，用栈来生成序列第3章字符串（教材中本章作者为许卓群）一.概念  1.串  2.模式匹配二.方法  1.串的基本操作  2.串的存储★3.串的KMP快速模式匹配算法(next数组

3、)，求特征next数组（N数组）和利用next数组完成匹配的方法  4.相关串运算和处理算法第4章二叉树（教材中本章作者为杨冬青）一.概念      1.二叉树2.二叉树的前序、中序、后序周游3.二叉排序树4.穿线树(中序、前序、后序)5.Huffman树、Huffman编码6.堆、堆排序二.方法      1．二叉树的链式存储        （1）二叉链表        （2）带父指针的三重链表      2.二叉树的顺序存储          完全二叉树的顺序存储   ★3.使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归的方法)

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

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

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

7、法分析      （1）基于比较次数和移位次数（一个移位就是一次纪录赋值操作，例如一次swap交换是3次移位），分析最好、最坏的时间、空间      （2）记住各种排序方法的平均时间     3.各种排序方法的局部修改和混合应用第8章文件管理和外排序（教材中本章作者为唐世渭）一.概念    1.顺序文件2.散列文件3.倒排文件二.方法     1.置换选择排序    2.赢者树、败者树    3.多路归并 第9章检索（教材中本章作者为张铭）一.概念    1.平均检索长度    2.二分法检索  ★3.散列表、同义词、碰撞、堆积（聚积）、二次聚集二.方法    

8、1.二分法检索的判定树、