《《数据结构作业》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构作业》PPT课件.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第七次作业选择题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如果一棵树有
2、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节点；序列不是
3、堆如调整为大根堆为：(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个叶子结点，则二叉树的高度至少为log2
4、u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log2n!+1的路径。即任何一个籍助比较进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有log2(n!)=O(nlog2n)。即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog2n)。证毕。6.19 Draw the general tree represented by the following sequential representation forgeneral trees illustrated by Example 6.8:XPC)Q)RV)M)（8）
5、翻译：对下列用6.8编码方法写出的树的顺序表示，画出树的形状。X|P -|C Q R -|V M void StackSort(Stack&IN)Stack Temp1,Temp2;while(!IN.isEmpty()/Transfer to another stack Temp1.push(IN.pop();IN.push(Temp1.pop();/Put back one element while(!Temp1.isEmpty()/Process rest of elems while(IN.top()Temp1.top()/Find elems place Temp2.push(IN
6、.pop();IN.push(Temp1.pop();/Put the element in while(!Temp2.isEmpty()/Put the rest back IN.push(Temp2.pop();7.2 编写一个处理整数关键码的插入排序。条件如下：输入的是一个栈（不是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是(n2)。初始序列为：(18,12,56,9,55,8)插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个插入到这个有序子序列中。855 956121818第一个元素1
7、81256 955 8Temp1ININ181256 955 8Temp11218IN56 955 8Temp11812IN 955 8Temp1121856Temp2E=18E=12E=56ININ55 8Temp1 9121856IN 955 8Temp1121856Temp2Temp2IN 8Temp155561812 9Temp2IN Temp1 8 912185556E=19E=55E=8最终结果7.3 冒泡排序的实现过程中有如下循环：for(int j=n-1;ji;j-)；考虑将它换成以下语句的影响for(int j=n-1;j0;j-)；请问新的实现方式还能正常执行吗？这种改变会影响到程序的渐近复杂度吗？这个改变对运行时间有什么影响？答案：新的实现方式能正常执行，程序的渐进复杂度没有改变，依旧是(n2)，但是，程序的比较次数会增加两倍的样子，因为对于那些已经排好序的元素程序依旧会拿相邻的进行比较，而这些额外的比较是无需的。结束_