课堂练习5data(答案).ppt

数据结构与算法课堂练习 5 答案 选择题 排序 1 排序方法中 依次取出数据与已排序的序列 初始为空 中的数据进行比较 将其放入已排序序列的正确位置上的方法 称为 A 直接插入排序B 冒泡排序C 选择排序D 希尔排序2 待排序的元素序列基本有序的前提下 下述排序方法中效率最高的排序方法是 A 直接插入排序B 直接选择排序C 快速排序D 归并排序3 下列排序方法中 平均情况下排序速度最快的为 A 归并排序B 希尔排序C 快速排序D 堆排序4 在各种排序方法中 平均情况下速度最快的排序方法为 A 希尔排序B 快速排序C 气泡排序D 归并排序 选择题 5 快速排序在方面最佳 A 最好情况下时间性能B 空间性能C 最坏情况下时间性能D 平均时间性能6 排序的分类 就其对象的存储介质而言 可分为 A 插入排序和选择排序B 交换排序和归并排序C 堆排序和快速排序D 内部排序和外部排序7 排序时要使用较多的辅助空间的排序是 A 直接选择排序B 归并排序C 直接插入排序D 堆排序8 下述排序方法中属于稳定的排序方法是 A 直接选择排序和堆排序B 气泡排序和快速排序C 直接插入排序和希尔排序D 直接插入排序 气泡排序和归并排序 1 已知一组元素的排序码为 42 31 20 15 40 65 28 18 53 10 若采用冒泡排序法从小到大排序 请写出前二趟排序后的结果 若采用希尔排序法排序 增量序列为d1 5 d2 3 d3 1 请写出前二次排序后的结果 解答题 解 10 42 31 20 15 40 65 28 18 5310 15 42 31 20 18 40 65 28 53 42 31 20 15 40 65 28 18 53 10 d1 5 42 28 18 15 10 65 31 20 53 40 d2 3 15 10 18 31 20 53 40 28 65 42 2 已知一组元素的排序码为 50 65 48 36 98 76 70 23 54 11 写出采用快速排序法第一趟排序后的结果 用图示给出采用堆排序法排序时形成的初始堆 以及交换最大排序码后重建的堆 解答题 解 写出采用快速排序法第一趟排序后的结果 50 65 48 36 98 76 70 23 54 11i j50 11 48 36 98 76 70 23 54 65i j50 11 48 36 23 76 70 98 54 65i j50 11 48 36 23 76 70 98 54 65i j23 11 48 36 50 76 70 98 54 65 解 用图示给出采用堆排序法排序时形成的初始堆 以及交换最大排序码后重建的堆 3 已知一组元素的排序码为 46 74 16 53 14 26 40 38 86 65 27 34 利用快速排序的方法写出每一趟划分后的结果 利用归并排序的方法写出每一趟二路归并排序后的结果 解答题 解 利用快速排序的方法写出每一趟划分后的结果46 74 16 53 14 26 40 38 86 65 27 34i j46 34 16 53 14 26 40 38 86 65 27 74i j46 34 16 27 14 26 40 38 86 65 53 74i j38 34 16 27 14 26 40 46 86 65 53 74 利用归并排序的方法写出每一趟二路归并排序后的结果 46 74 16 53 14 26 40 38 86 65 27 34 46 74 16 53 14 26 38 40 65 86 27 34 16 46 53 74 14 26 38 40 27 34 65 86 14 16 26 38 40 46 53 74 27 34 65 86 14 16 26 27 34 38 40 46 53 65 74 86 1 写出对数组A中的n个元素进行直接插入排序函数 voidInsertSort ElemTypeA intn 解 voidInsertSort ElemTypeA intn inti j ElemTypex for i 1 i 0 j 从第i 1个开始往前找插入点 if x stn A j stn A j 1 A j elsebreak A j 1 x 插入 编程题 2 写出对数组A中的n个元素进行选择排序函数 voidSelectSort ElemTypeA intn解 voidSelectSort ElemTypeA intn inti j k ElemTypex for i 0 i n 2 i 每一趟选择最小元素并与A i 交换k i for j i 1 j n 1 j 查找最小元素的下标if A j stn A k stn k j if k i 交换x A i A i A k A k x 编程题 3 写出对数组A中的n个元素进行气泡排序函数 voidBubbleSort ElemTypeA intn 解 voidBubbleSort inta intn inti j x for i 1 i i j if a j a j 1 x a j a j a j 1 a j 1 x 编程题 4 编写一个对整型数组元素进行改进的选择排序的算法 要求首先从待排序区间中选出一个最小值并与第一个元素交换 再从待排序区间中选出一个最大值并与最后一个元素交换 反复进行直到全部排序完成 设函数原型为 voidSelectSort intx intn