数据结构作业7.ppt

数据结构第七次作业,选择题,1堆排序的时间复杂度是（D）。A）O(1)B）O(n)C）O(n2)D）O(nlogn)2.若一个具有N个顶点，K条边的无向图是一个森林（NK），则该森林中必有（C）棵树。A）KB）NC）N-KD）13每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（B）。A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序4快速排序执行一遍之后，已经到位的元素个数是（A）。A）1B）3C）n/4D）n/25数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（C）排序算法最节省时间。A）快速排序B）希尔排序C）堆排序D）直接选择排序,1如果一棵树有n1个度为1的结点,有n2个度为2的结点,nm个度为m的结点,试问有多少个度为0的结点?试推导之。（8）,综合题,2请画出右图所示的树所对应的二叉树。（8）,3.判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则将它调整为大根堆。,4给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。（1）希尔排序（第一趟排序的增量为6）（2）快速排序（选第一个记录为枢轴）,答案：因为堆为完全二叉树，因此只需要判断是不是所有节点，都大于或小于子节点，即节点n需要大于或小于2n节点和2n+1节点；序列不是堆如调整为大根堆为：(92，86，56，70，33，33，48，65，12，24)若调整为小根堆为：(12，24，33，65，33，56，48，92，86，70),答案：(1)（4，2，16，6，8，28，12，10，20，30，18）(2)（6，2，10，4，8，12，28，30，20，16，18）,5.利用比较的方法进行排序，在最坏情况下，能达到的最好的时间复杂度是什么？,答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。若二叉树高度是h，则叶子结点个数最多为2h-1；反之，若有u个叶子结点，则二叉树的高度至少为log2u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log2n!+1的路径。即任何一个籍助比较进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有log2(n!)=O(nlog2n)。即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog2n)。证毕。,6.19DrawthegeneraltreerepresentedbythefollowingsequentialrepresentationforgeneraltreesillustratedbyExample6.8:XPC)Q)RV)M)（8）翻译：对下列用6.8编码方法写出的树的顺序表示，画出树的形状。,X|P-|CQR-|VM,voidStackSort(Stack,7.2编写一个处理整数关键码的插入排序。条件如下：输入的是一个栈（不是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是(n2)。,初始序列为：(18,12,56,9,55,8)插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个插入到这个有序子序列中。,1812,E=18,E=12,E=56,IN,8912185556,E=19,E=55,E=8,最终结果,7.3冒泡排序的实现过程中有如下循环：for(intj=n-1;ji;j-)；考虑将它换成以下语句的影响for(intj=n-1;j0;j-)；请问新的实现方式还能正常执行吗？这种改变会影响到程序的渐近复杂度吗？这个改变对运行时间有什么影响？,答案：新的实现方式能正常执行，程