资源简介

中小学教育资源及组卷应用平台
第五单元 把数据排列有序
一、选择题（每题3分，共30分）
1. 在选择排序算法中，每一轮会（ ）
A. 从未排序元素中选择最小（或最大）元素放到已排序序列末尾
B. 依次比较相邻元素并交换
C. 把数据分到不同的桶中再分别排序
D. 直接将数据按顺序排列好
2. 对于一组有n个数据的列表进行冒泡排序，在最坏情况下，比较次数是（ ）
A. n - 1 B. n(n - 1)/2 C. n D. n^2
3. 桶排序算法的关键在于（ ）
A. 确定合适的桶数量和范围 B. 比较相邻元素
C. 选择最小元素 D. 多次交换元素位置
4. 以下关于冒泡排序的说法，错误的是（ ）
A. 冒泡排序是一种稳定的排序算法
B. 每一轮比较都会将最大（或最小）元素“冒泡”到末尾
C. 冒泡排序的效率一定比选择排序高
D. 冒泡排序通过相邻元素比较和交换实现排序
5. 对列表[5, 3, 8, 1, 2]进行选择排序，第一轮排序后结果是（ ）
A. [1, 3, 8, 5, 2] B. [3, 5, 1, 2, 8]
C. [2, 3, 5, 8, 1] D. [5, 1, 3, 2, 8]
6. 若要对班级学生成绩（成绩范围0 - 100分）进行排序，较适合的排序算法是（ ）
A. 选择排序 B. 冒泡排序 C. 桶排序 D. 无法确定
7. 选择排序算法的执行次数与数据量的关系是（ ）
A. 执行次数与数据量无关
B. 数据量越大，执行次数越少
C. 数据量越大，执行次数越多
D. 执行次数固定不变
8. 冒泡排序在最好情况下的时间复杂度是（ ）
A. O(1) B. O(n) C. O(n^2) D. O(log n)
9. 桶排序中，桶的数量设置过少会导致（ ）
A. 每个桶内数据量过少，浪费空间
B. 每个桶内数据量过多，失去桶排序优势
C. 排序速度加快
D. 无法进行排序
10. 以下排序算法中，属于不稳定排序算法的是（ ）
A. 冒泡排序 B. 桶排序
C. 选择排序 D. 以上都不是
二、填空题（每题4分，共20分）
1. 选择排序的基本步骤是每次从未排序元素中选择______元素，与未排序序列的第一个元素交换。
2. 冒泡排序是通过相邻元素的______和交换，将最大（或最小）元素逐步移到序列末尾。
3. 桶排序的算法思想是把数据分到不同的______中，再对每个桶内的数据进行排序。
4. 在对数据量为n的序列进行冒泡排序时，平均时间复杂度为______。
5. 对于数值型数据排序，若数据范围较小且分布均匀，______排序算法可能具有较好的效率。
三、简答题（每题10分，共20分）
1. 简述冒泡排序和选择排序的主要区别。
2. 说明桶排序的适用场景及优势。
四、操作题（30分）
1. 编写Python程序实现冒泡排序算法，对列表[4, 6, 2, 8, 1, 9]进行排序，并输出排序后的结果。
2. 用流程图描述选择排序算法的过程。
参考答案：
一、选择题
1. A：选择排序每次从未排序元素中选最小（或最大）元素放到已排序序列末尾；B是冒泡排序特点，C是桶排序，D说法错误。
2. B：冒泡排序最坏情况需比较n(n - 1)/2次 ，即对n个数据两两比较。
3. A：桶排序关键是确定合适桶数量和范围，以合理划分数据；B是冒泡排序，C是选择排序部分操作。
4. C：冒泡排序不一定比选择排序效率高，二者时间复杂度相近，在不同场景各有优劣；A、B、D说法正确。
5. A：选择排序第一轮从未排序元素找最小元素1 ，与第一个元素5交换。
6. C：学生成绩范围0 - 100分，数据范围固定，桶排序可按成绩区间设桶，效率较高；A、B也可行但相对复杂数据量时桶排序更优。
7. C：选择排序数据量越大，比较和交换次数越多，执行次数越多。
8. B：冒泡排序最好情况（数据已有序）只需比较n - 1次，时间复杂度O(n)。
9. B：桶数量过少，每个桶内数据多，失去桶排序分治优势，排序效率降低；A说法相反，C排序速度会减慢，D能排序但效果差。
10. C：选择排序在交换元素时可能改变相同元素相对顺序，是不稳定排序；冒泡排序和桶排序是稳定排序。
二、填空题
1. 最小（或最大）
2. 比较
3. 桶
4. O(n^2)
5. 桶
三、简答题
1. 冒泡排序：相邻元素比较交换，每轮将最大（或最小）元素移到末尾，多次重复实现排序，是稳定排序。
选择排序：每次从未排序元素选最小（或最大）与未排序首元素交换，不相邻元素交换，可能破坏相同元素相对顺序，是不稳定排序。
2. 适用场景：数据分布均匀、范围可合理划分；如整数排序且范围有限，或对特定范围内数据分组排序。
优势：利用分治思想，若桶划分合理，可并行处理各桶数据，提高排序效率；对大量数据且分布均匀情况，比一些传统比较排序算法（冒泡、选择）效率高。
四、操作题
1. Python程序
lst = [4, 6, 2, 8, 1, 9]
n = len(lst)
for i in range(n):
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j[j lst[j + 1] = lst[j + 1[j lst[j]
print(lst)

2. 流程图要点
- 开始框。
- 输入框：输入待排序列表。
- 循环开始框：设置外层循环变量（如i ）控制轮数，从0到列表长度减2 。
- 内层循环开始框：设置内层循环变量（如j ） ，从i + 1到列表末尾。
- 比较框：比较列表第i个元素和第j个元素大小。
- 判断框：判断是否交换元素（如第i个元素大于第j个元素），是则交换，否则继续。
- 循环结束框：内外层循环结束后，进入输出框输出排序后列表。
- 结束框。 （用标准流程图符号绘制，体现流程逻辑即可）
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
21世纪教育网(www.21cnjy.com)

展开更多......

收起↑