第九章--华工数据结构试卷资料-电信学院-

习 题 9 1 一 选择题 1 一组记录的排序码为 46 79 56 38 40 84 则利用堆排序的方法建立的初 始堆为 B B A 79 46 56 38 40 80 B 84 79 56 38 40 46 C 84 79 56 46 40 38 D 84 56 79 40 46 38 2 排序趟数与序列原始状态 原始排列 有关的排序方法是 ACDACD 方法 A 插入排序 B 选择排序 C 冒泡排序 D 快速排序 3 下列排序方法中 B B 是稳定的排序方法 A 直接选择排序 B 二分法插入排序 C 希尔排序 D 快速排序 4 数据序列 8 9 10 4 5 6 20 1 2 只能是下列排序算法中 C C 的两趟 排序后的结果 A 选择排序 B 冒泡排序 C 插入排序 D 堆排序 5 对序列 15 9 7 8 20 1 4 进行排序 进行一趟排序后 数据的排列变为 4 9 1 8 20 7 15 则采用的是 C C 排序 A 选择 B 快速 C 希尔 D 冒泡 6 一组待排序记录的关键字为 46 79 56 38 40 84 则利用快速排序 以第 一个记录为基准元素得到的一次划分结果为 C C A 38 40 46 56 79 84 B 40 38 46 79 56 84 C 40 38 46 56 79 84 D 40 38 46 84 56 79 7 用直接插入排序对下面四个序列进行排序 由小到大 元素比较次数最少的是 C C A 94 32 40 90 80 46 21 69 B 32 40 21 46 69 94 90 80 C C 21 32 46 40 80 69 90 9421 32 46 40 80 69 90 94 D D 90 69 80 46 21 32 94 4090 69 80 46 21 32 94 40 8 若用冒泡排序对关键字序列 18 16 14 12 10 8 进行从小到大的排序 所需进 行的关键字比较总次数是 B B A A 1010 B B 1515 C C 2121 D D 3434 9 就排序算法所用的辅助空间而言 堆排序 快速排序和归并排序的关系 A A A 堆排序 快速排序 归并排序 B 堆排序 归并排序归并排序 快速排序 D 堆排序 快速排序 归并排序 E 以上答案都不对 10 采用败者树进行 k 路平衡归并的外部排序算法 其总的归并效率与 k A 有关 B 无关 9 2 填空题 1 在直接插入排序和直接选择排序中 若初始数据基本有序 则选用 直接插入排序直接插入排序 若初始数据基本反序 则选用 直接选择排序直接选择排序 2 在归并排序中 若待排序记录的个数为 20 则共需要进行 5 5 趟归并 在第三趟 归并中 是把长度为 4 4 的有序表归并为长度为 8 8 的有序表 3 在内排序中 平均比较次数最多的是 快速排序快速排序 要求附加的内存空间最大的是 归并排序归并排序 排序时不稳定的有 希尔排序希尔排序 选择排序选择排序 快速排序快速排序 和 堆排序堆排序 等 几种方法 4 对 n 个元素的序列进行冒泡排序 最少的比较次数是 n 1n 1 此时元素的排列情况 从小到大排列从小到大排列 在 从大到小排列从大到小排列 情况下比较次数最多 其比较次数为 n n 1 2n n 1 2 5 对一组记录 50 40 95 20 15 70 60 45 80 进行直接插入排序时 当把 第 7 条记录 60 插入到有序表中时 为寻找插入位置需比较 3 3 次 9 3 应用题 1 在各种排序方法中 哪些是稳定的 哪些是不稳定的 并为每一种不稳定的排序方 法举出一个不稳定的实例 答 稳定的排序算法有直接插入排序 折半插入排序 冒泡排序 归并排序和基数排序 答 稳定的排序算法有直接插入排序 折半插入排序 冒泡排序 归并排序和基数排序 不稳定的排序算法有希尔排序 直接选择排序 堆排序 快速排序 不稳定的排序算法有希尔排序 直接选择排序 堆排序 快速排序 例子 讲课是的例子 例子 讲课是的例子 2 设待排序的关键码分别为 28 13 72 85 39 41 6 20 按折半插入排序已使 前七个记录有序 中间结果如下 6 13 28 39 41 72 85 20 i 1 m 4 r 7 试在此基础上 沿用上述表达方式 给出继续采用折半插入第八条记录的比较过程 并回 答以下问题 1 使用折半插入排序所要进行的比较次数 是否与待排序的记录的初始状态有关 2 在一些特殊情况下 二分法插入排序比直接插入排序要执行更多的比较 这句话对吗 答 答 插入插入 2020 的过程 的过程 39 2039 20 r m 1 3 i r m i r 2 4 2 2r m 1 3 i r m i r 2 4 2 2 13 20 13r i m 1 3 i r 查找过程结束 插入位置为查找过程结束 插入位置为 i i 最终结果为 最终结果为 6 6 1313 2020 2828 3939 4141 7272 8585 1 1 插入排序所要进行的比较次数与待排序的记录的初始状态有关 若初始状态基本有序 插入排序所要进行的比较次数与待排序的记录的初始状态有关 若初始状态基本有序 每次查找时都会搜索到有序表的最后一个元素才找到插入位置 若每次插入的元素在有序每次查找时都会搜索到有序表的最后一个元素才找到插入位置 若每次插入的元素在有序 表中的插入位置靠中间 则查找次数最少 表中的插入位置靠中间 则查找次数最少 2 2 在一些特殊情况下 二分法插入排序比直接插入排序要执行更多的比较 这句话是对 在一些特殊情况下 二分法插入排序比直接插入排序要执行更多的比较 这句话是对 的 若初始状态基本有序 则折半插入排序 每次查找时都会搜索到有序表的最后一个元的 若初始状态基本有序 则折半插入排序 每次查找时都会搜索到有序表的最后一个元 素才找到插入位置 直接插入排序则每次只比较一次就找到合适位置 素才找到插入位置 直接插入排序则每次只比较一次就找到合适位置 3 已知一关键码序列为 3 87 12 61 70 97 26 45 试根据堆排序原理 填 写完整下示各步骤结果 建立初始堆 97 97 8787 2626 6161 7070 1212 3 3 4545 堆排序过程 1 87 70 26 61 45 12 3 97 2 7070 6161 2626 3 3 4545 1212 8787 9797 3 61 45 26 3 12 70 87 97 4 4545 1212 2626 3 3 6161 7070 8787 9797 5 26 12 3 45 61 70 87 97 6 1212 3 3 2626 4545 6161 7070 8787 9797 7 3 12 26 45 61 70 87 97 4 全国有 10000 人参加物理竞赛 只录取成绩优异的前 10 名 并将他们从高分到低 分输出 而对落选的其他考生 不需排出名次 问此种情况下 用何种排序方法速度最快 为什么 答 因排序的元素个数很大 所以需要采用排序速度较快的排序方法 排序速度比较答 因排序的元素个数很大 所以需要采用排序速度较快的排序方法 排序速度比较 快的排序方法有快速排序 堆排序 归并排序和基数排序等 其中快速排序 归并排序和快的排序方法有快速排序 堆排序 归并排序和基数排序等 其中快速排序 归并排序和 基数排序都是在排序结束后才能确定数据元素的全部序列 而排序过程中无法知道部分连基数排序都是在排序结束后才能确定数据元素的全部序列 而排序过程中无法知道部分连 续位置上的最终元素 但堆排序则每次输出一个堆顶元素 即最大或最小元素 续位置上的最终元素 但堆排序则每次输出一个堆顶元素 即最大或最小元素 然后对堆 然后对堆 进行再调整 保证堆顶元素总是剩下元素的最大或最小的 从而可知 若在大量数据的文进行再调整 保证堆顶元素总是剩下元素的最大或最小的 从而可知 若在大量数据的文 件中 只选取排序后的前几名 采用堆排序最合适 件中 只选取排序后的前几名 采用堆排序最合适 5 5 判断下列序列是否为堆 若不是堆 则把它们调整为堆 判断下列序列是否为堆 若不是堆 则把它们调整为堆 1 100 85 95 75 80 60 82 40 20 10 65 2 100 95 85 82 80 75 65 60 40 20 10 3 100 85 40 75 80 60 65 95 82 10 20 4 10 20 40 60 65 75 80 82 85 95 100 答 答 1 1 100100 8585 9595 7575 8080 6060 8282 4040 2020 1010 65 65 是堆 是堆 2 2 100100 9595 8585 8282 8080 7575 6565 6060 4040 2020 10 10 是堆 是堆 3 3 100100 8585 4040 7575 8080 6060 6565 9595 8282 1010 20 20 不是堆不是堆 调整以后的堆为 调整以后的堆为 100100 9595 6565 8585 8080 6060 4040 7575 8282 1010 2020 4 4 1010 2020 4040 6060 6565 7575 8080 8282 8585 9595 100 100 是堆 是堆 9 4 算法题 1 假设待排序序列以单链表的形式存储 头指针为 head 编写选择排序算法 作为 上机实践题目 include struct Rtype KeyType key 关键字域 struct Lnode Elemtype data struct Lnode next void selectsort Lnode L Lnode p q r Rtype temp for p L next p next NULL p p next q p for r p next r NULL r r next if q data r data q r if p q temp p data p data q data q data temp 2 试以 L e L len 1 这监视哨 改写直接插入排序算法 struct Rtype KeyType key 关键字域 define maxlen maxsize maxsize 为分配的存储单元个数 struct ListSq Rtype e maxlen 0 号单元空闲 元素从 1 号单元开始存放 int len void insertsort ListSq r int n 待排序元素 r 1 r n int i j for i n ir e j key r e j 1 r e j j r e j 1 r e n 1 3 奇偶交换排序如下所述 第一趟对所有奇数 i 将 a i 和 a i 1 进行比较 第二 趟对所有的偶数 i 将 a i 和 a i 1 进行比较 若 a i a i 1 则将两者交换 第三趟 对奇数 i 第四趟对偶数 i 依次类推 直到整个序列有序为止 试问 这种排序方法的结 束条件是什么 编写相应的实现算法 作为上机实践题目 struct Rtype KeyType key 关键字域 define maxlen maxsize maxsize 为分配的存储单元个数 struct ListSq Rtype e maxlen 0 号单元空闲 元素从 1 号单元开始存放 int len void qiousort ListSq r int n int flag 1 while flag flag 0 int i 1 while i r e i 1 key Rtype temp r e i r e i r e i 1 r e i 1 temp flag 1 i 2 i 2 while i r e i 1 key Rtype temp r e i r e i r e i 1 r e i 1 temp flag 1 i 2 4 设计一个双向冒泡排序算法 即在排序过程中交替改变扫描方向 作为上机实践 题目 算法为 struct Rtype KeyType key 关键字域 define maxlen maxsize maxsize 为分配的存储单元个数 struct ListSq Rtype e maxlen 0 号单元空闲 元素从 1 号单元开始存放 int len void dbubblesort ListSq r int n int i j flag Rtype temp flag 1 i 0 while flag flag 0 for j n i j i j if r e j key r e j 1 key flag a temp r e j r e j r e j 1 r e j 1 temp for j i jr e j 1 key flag a temp r e j r e j r e j 1 r e j 1 temp i 5 写出快速排序的非递归算法 Struc