《数据结构作业》PPT课件.ppt

数据结构第七次作业 选择题 1 堆排序的时间复杂度是 D A O 1 B O n C O n2 D O nlogn 2 若一个具有N个顶点 K条边的无向图是一个森林 N K 则该森林中必有 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 j i j 考虑将它换成以下语句的影响for intj n 1 j 0 j 请问新的实现方式还能正常执行吗 这种改变会影响到程序的渐近复杂度吗 这个改变对运行时间有什么影响 答案 新的实现方式能正常执行 程序的渐进复杂度没有改变 依旧是 n2 但是 程序的比较次数会增加两倍的样子 因为对于那些已经排好序的元素程序依旧会拿相邻的进行比较 而这些额外的比较是无需的 结束