《数据结构作业》

数据结构第七次作业.选择题1．堆排序的时间复杂度是（D）。A）O(1) B）O(n) C）O(n2) D）O(nlogn)2.若一个具有N个顶点，K条边的无向图是一个森林（N＞K），则该森林中必有（C）棵树。A）K B）N

C）N-K D）13．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（B）。A）冒泡排序 B）简单选择排序

C）希尔排序

D）直接插入排序4．快速排序执行一遍之后，已经到位的元素个数是（A）。A）1 B）3 C）n/4 D）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<int>&IN){Stack<int>Temp1,Temp2;while(!IN.isEmpty())//TransfertoanotherstackTemp1.push(IN.pop());IN.push(Temp1.pop());//Putbackoneelementwhile(!Temp1.isEmpty())//Processrestofelems{while(IN.top()>Temp1.top())//Findelem’splaceTemp2.push(IN.pop());IN.push(Temp1.pop());//Puttheelementinwhile(!Temp2.isEmpty())//PuttherestbackIN.push(Temp2.pop());}}7.2编写一个处理整数关键码的插入排序。条件如下：输入的是一个栈（不是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是θ(n2)。.初始序列为：(18,12,56,9,55,8)插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个插入到这个有序子序列中。855956121818第一个元素1812569558Temp1ININ1812569558Temp11218IN569558Temp11812IN9558Temp1121856Temp2E=18E=12E=56IN.IN558Temp19121856IN9558Temp1121856Temp2Temp2IN8Temp1555618129Temp2IN

Tem=19E=55E=8最终结果.7.3冒泡排序的实现过程中有如下循环：for(intj=n-1;j>i;j--)；考虑将它换成以下语句的影响for(intj=n-1;j>0;j--)；请问新的