资源描述：
《数据结构重点复习内容》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构重点复习内容教材P143-P147：树、森林与二叉树的相互转换，并做一到两个练习，如教材P154的6.11并求各树与森林的各种遍历序列；教材P147-P151：哈夫曼树，并做一到两个练习，如教材P153的6.9并计算其WPL；教材P160-P165：图的邻接矩阵与邻接表的定义及其图的建立算法，可参考实验内容；教材P168-P171：图的深度优先遍历算法的实现；教材P175-P179：最小生成树，并做一到两个练习，要求会根据一个图的邻接矩阵，画出图，并求出其最小生成树，且过程要完整；教材P197-P200：顺序查找、二分查找算法的实现，可参考实验内容；教
2、材P224-P231：哈希查找，并做一到两个练习，如教材P232的8.5；教材P2414-P242：冒泡排序算法的实现，可参考实验内容；各章知识的总结。数据结构复习要点一．基础知识（一）述论1．数据结构、逻辑结构、存储结构和算法的定义；2．逻辑结构、存储结构的分类与特点；3．算法的特征与评价标准；4．时间与空间复杂度的定义；5．算法的描述形式。（二）线性结构1．线性结构的定义与特点；2．线性表的定义和特点；3．线性表的两种存储结构的定义；4．栈与队列的定义与操作特点；5．栈与队列的存储结构的定义。（三）树结构1．树结构的定义与特点；2．树结构的基本术语；3．二
3、叉树的定义与特点；4．二叉树的性质；5．树与二叉树的存储结构；（四）图结构1．图结构的定义与特点；2．图结构的基本术语；3．图的存储结构；4．最小生成树、AOE、AOV。（五）查找与排序1．查找与排序的定义与分类；2．查找与排序的存储结构。二．方法与技术1．线性表的查找、建立、插入和删除操作的实现与分析，特别是头、尾插入法建立单链表的算法（重点）；2．顺序栈与循环队列的基本操作。3．二叉树的有关操作的递归实现，比如建立二叉树（重点）；4．二叉树的四种遍历、树与森林的遍历、森林与二叉树的转换（重点）；5．哈夫曼树的建立与WPL的计算（重点）；6.图的邻接矩阵和邻
4、接表存储结构下的图的建立算法的实现（重点）；7.图的邻接矩阵和邻接表存储结构下的图的深度优先遍历算法的实现（重点）；8．求最小生成树的方法（重点）；9．顺序查找与二分查找算法的实现（重点）；10．哈希查找方法与平均查找长度的计算（重点）；11．冒泡排序数据结构--排序数据结构--排序一、单项选择题1．下列内部排序算法中：A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<5、率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为O(n?n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是()。A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入4．下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆5．一组
6、记录的关键码为（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.快速8.下列排序算法中，占用辅助空间最多的是：()A.归并排序B.快速排序C.希尔排序D.
7、堆排序9.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A.3B.10C.15D.2510.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序11．下列四个序列中，哪一个是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1512.有一组数据（15，9，7，8，20
8、，-1，7，4），用堆排序的筛选方法建
