数据结构重点复习内容.docVIP

数据结构重点复习内容 教材P143-P147：树、森林与二叉树的相互转换，并做一到两个练习，如教材P154的6.11并求各树与森林的各种遍历序列； 教材P147-P151：哈夫曼树，并做一到两个练习，如教材P153的6.9并计算其WPL； 教材P160-P165：图的邻接矩阵与邻接表的定义及其图的建立算法，可参考实验内容； 教材P168-P171：图的深度优先遍历算法的实现； 教材P175-P179：最小生成树，并做一到两个练习，要求会根据一个图的邻接矩阵，画出图，并求出其最小生成树，且过程要完整； 教材P197-P200：顺序查找、二分查找算法的实现，可参考实验内容； 教材P224-P231：哈希查找，并做一到两个练习，如教材P232的8.5； 教材P2414-P242：冒泡排序算法的实现，可参考实验内容； 各章知识的总结。 数据结构复习要点 一．基础知识 （一）述论 1．数据结构、逻辑结构、存储结构和算法的定义； 2．逻辑结构、存储结构的分类与特点； 3．算法的特征与评价标准； 4．时间与空间复杂度的定义； 5．算法的描述形式。 （二）线性结构 1．线性结构的定义与特点； 2．线性表的定义和特点； 3．线性表的两种存储结构的定义； 4．栈与队列的定义与操作特点； 5．栈与队列的存储结构的定义。 （三）树结构 1．树结构的定义与特点； 2．树结构的基本术语； 3．二叉树的定义与特点； 4．二叉树的性质； 5．树与二叉树的存储结构； （四）图结构 1．图结构的定义与特点； 2．图结构的基本术语； 3．图的存储结构； 4．最小生成树、AOE、AOV。 （五）查找与排序 1．查找与排序的定义与分类； 2．查找与排序的存储结构。 二．方法与技术 1．线性表的查找、建立、插入和删除操作的实现与分析，特别是头、尾插入法建立单链表的算法（重点）； 2．顺序栈与循环队列的基本操作。 3．二叉树的有关操作的递归实现，比如建立二叉树（重点）； 4．二叉树的四种遍历、树与森林的遍历、森林与二叉树的转换（重点）； 5．哈夫曼树的建立与WPL的计算（重点）； 6.图的邻接矩阵和邻接表存储结构下的图的建立算法的实现（重点）； 7.图的邻接矩阵和邻接表存储结构下的图的深度优先遍历算法的实现（重点）； 8．求最小生成树的方法（重点）； 9．顺序查找与二分查找算法的实现（重点）； 10．哈希查找方法与平均查找长度的计算（重点）； 11．冒泡排序数据结构--排序 数据结构--排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（ ） （4）排序的平均时间复杂度为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 2．比较次数与排序的初始状态无关的排序方法是( )。 A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38,46,84,56,79) 6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D. 堆 7. 就平均性能而言，目前最好的内排序方法是( )排序法。 A. 冒泡 B. 希尔插入 C. 交换 D. 快速