数据结构作业7实用教案

1、选择题1堆排序的时间复杂度是（D）。A）O(1)B）O(n)C）O(n2)D）O(nlogn)2. 若一个具有N个顶点，K条边的无向图是一个森林(snln)（NK），则该森林(snln)中必有（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）直接选择排序

2、第1页/共10页第一页，共10页。1如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问(shwn)有多少个度为0的结点? 试推导之。（8）综合题2请画出右图所示的树所对应(duyng)的二叉树。（8）第2页/共10页第二页，共10页。3. 判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果(rgu)不是，则将它调整为大根堆。4给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。（1）希尔排序（第一趟排序的增量(zn lin)为6）（2）快速排序（选

3、第一个记录为枢轴）答案：因为(yn wi)堆为完全二叉树，因此只需要判断是不是所有节点，都大于或小于子节点，即节点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）第3页/共10页第三页，共10页。5. 利用比较的方法进行排序，在最坏情况(qngkung)下，能达到的最好的时间复杂度是什么？答案

4、：假定待排序的记录有n个。由于含n个记录的序列可能(knng)出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。若二叉树高度是h，则叶子结点个数最多为2h-1；反之，若有u个叶子结点，则二叉树的高度至少为log2u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log2n!+1的路径。即任何一个籍助比较进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有log2(n!) =O(nlog2n)。即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog2n)。证毕。 第4页/共10页第四页，共10页。6.19

5、 Draw the general tree represented by the following sequential representation forgeneral trees illustrated by Example 6.8: XPC)Q)RV)M)（8）翻译：对下列(xili)用6.8编码方法写出的树的顺序表示，画出树的形状。 X | P - | | | C Q R - | | V M 第5页/共10页第五页，共10页。void StackSort(Stack& IN) Stack Temp1, Temp2; while (!IN.isEmpty() / Trans

6、fer 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.pop(); IN.push(Temp1.pop(); / Put the element in while (!Temp2.isEmpty() / Put the rest back IN.push(Temp

7、2.pop(); 7.2 编写一个处理(chl)整数关键码的插入排序。条件如下：输入的是一个栈（不是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是(n2) 。第6页/共10页第六页，共10页。初始序列为：(18,12,56,9,55,8) 插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个(zhg)插入到这个有序子序列中。 855 956121818第一个元素181256 955 8Temp1ININ181256 955 8Temp11218IN56 955 8Temp11812IN 955 8T

8、emp1121856Temp2E=18E=12E=56IN第7页/共10页第七页，共10页。IN55 8Temp1 9121856IN 955 8Temp1121856Temp2Temp2IN 8Temp155561812 9Temp2IN Temp1 8 912185556E=19E=55E=8最终(zu zhn)结果第8页/共10页第八页，共10页。7.3 冒泡排序的实现过程中有如下循环：for(int j=n-1;ji;j-)；考虑将它换成以下语句的影响for(int j=n-1;j0;j-)；请问(qngwn)新的实现方式还能正常执行吗？这种改变会影响到程序的渐近复杂度吗？这个改变对运行时间有什么影响？答案：新的实现方式能正常执行，程序的渐进复杂度没有改变，依旧是(n2