资源简介

2023-2024学年高二上学期浙教版(2019)选修一5.3数据排序
一、选择题
1．下列哪种算法不属于搜索算法（ ）
A．暴力枚举 B．顺序枚举 C．二分查找 D．堆排序
2．某冒泡排序算法的VB程序段如下：
i=6: flag =1: cnt=0
Do While i >=2 And flag=1
flag=0: cnt= cnt +1
For j =
If a(j)>a(j-1)Then
k=a(j):a(j)=a(j-1):a(j-1)=k
flag= 1
End If
Next j
i=i-1
Loop
数组元素a(1)到a(6)的值依次为“79，13，93，55，29，17”，执行该程序段后，cnt的值为3，数组元素实现有序，则方框中的代码是（ ）
A．2 To i-1 B．2 To i
C．6 To 7-i Step-1 D．6 To 8-i Step -1
3．以下哪种排序算法不是比较排序（ ）
A．归并排序 B．快速排序 C．计数排序 D．堆排序
4．归并排序是一种基于分治思想的排序算法，它的基本思想是将两个有序的子序列合并成一个有序序列。归并排序的时间复杂度是（ ）
A．O(n) B．O(n^2) C．O(n^3) D．O(nlogn)
5．以下哪个算法不是时间复杂度为O(n^2)的排序算法（ ）
A．冒泡排序 B．插入排序 C．选择排序 D．快速排序
6．一次运动会上，某组6位选手的百米成绩(单位：秒)分别是“14.1、12.3、11.2、14.8、13.9、11.0”，若使用选择排序法将该组的成绩按第一名、第二名、第三名……的顺序排序，则第一次交换数据后的顺序是（ ）
A．14.8 14.1 12.3 11.2 13.9 11.0
B．11.0 12.3 11.2 14.8 13.9 14.1
C．14.8 12.3 11.2 14.1 13.9 11.0
D．11.0 14.1 12.3 11.2 14.8 13.9
7．某市组织了一次我心目中最喜爱的球队的评比活动，6个球队网上投票数为201、287、501、189、397、295，若采用冒泡排序算法对其进行从大到小排序，则第三遍加工后的结果是( )
原始数据 201 287 501 189 397 295
第一遍 501 201 287 397 189 295
第二遍 501 397 201 287 295 189
第三遍
A．501 397 295 287 201 189
B．501 397 201 287 295 189
C．501 397 295 201 189 287
D．501 397 295 201 287 189
8．在实现排序算法时，以下哪种算法的时间复杂度最低（ ）
A．冒泡排序 B．选择排序 C．插入排序 D．快速排序
9．对一列数据[40、7、37、27、18、63、49、15]按升序排列，使用冒泡排序方法，第一、二轮需进行相邻列表元素交换的次数一共为（ ）
A．4次 B．5次 C．9次 D．7次
10．某 VB 程序段如下：
n = 6: i = 1
Do While i <= 3
k = i: j = i + 1
Do while j <= n
If a(j) < a(k) Then
k = j
j = j +1
Loop
If i <> k Then
t = a(i): a(i) = a(k): a(k) = t
End If
i=i+1
Loop
数组元素 a(1)到 a(6)的值依次为 1，6，5，3，4，2，则该程序段运行后，数组元素 a(1)到 a(6)的值依次为（ ）
A．1，2，3，5，4，6 B．6，4，5，3，2，1
C．1，2，3，4，5，6 D．6，5，4，3，2，1
11．有如下 VB 程序段：
For i = 1 To 8
a(i) = Int(Rnd * 7) + 1
Next i
For i = 1 To 3
For j = 1 To 8 - 2 * i If a(j) Mod 7 > a(j + 2) Mod 7 Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
Next j
Next i
For i = 1 To 8
ch(i) = Chr(a(i) + Asc("A") - 1)
Next i
执行该程序段后，ch(1)～ch(8)各元素值不可能的是（ ）
A．AACBFBFE B．GGABCDDE C．ABBBCDDE D．ABBCDDEG
12．以下哪种排序算法的时间复杂度在最坏情况下是O(n^2)（ ）
A．快速排序 B．归并排序 C．冒泡排序 D．堆排序
13．以下哪种排序算法是原地排序（ ）
A．快速排序 B．归并排序 C．堆排序 D．所有以上
14．选择排序的主要思想是在未排序的序列中找到最小（或最大）的元素，将其存放到已排序序列的末尾。这个过程会重复进行，直到整个序列变得有序。选择排序的时间复杂度是（ ）
A．O(n) B．O(n^2) C．O(n^3) D．O(nlogn)
15．字符串数组a中a(1)到a(6)的原始数据为57，3，24，34， 6，120，为了对该数组进行排序操作，编写了以下VB程序。
i=2
Do While i<=6
For j=6 To i+2 Step -2
If a（j）>a（j-2）Then t=a（j）:a（j)=a（j-2）:a（j-2)=t
Next j
i=i+2
Loop
则程序运行之后，数组元素a(1)和a(2)的值分别是（　　）
A．6 3 B．57 120
C．120 57 D．6 34
二、填空题
16．选择排序的主要思想是在未排序的序列中找到最小（或最大）的元素，将其存放到已排序序列的末尾。选择排序的平均时间复杂度为 。
17．在实现排序算法时，快速排序的平均时间复杂度为 。
18．在快速排序算法中，选择一个好的基准元素可以显著提高算法的效率。通常使用 方法选择基准元素。
19．若要取消排序操作，可以点击Excel工作表中的任意 。
三、操作题
20．某会务组根据参会者到达指定上车点时间和每位参会者可以等待的时间信息，安排车辆接送参会者去宾馆（不考虑车子座位数量）。参会者到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如“08：15 2”表示参会者当天8点15分到达上车点，最多等待2分钟（每个人的等待时间都小于10），那么该参会者最晚8点17分出发去宾馆（若8点17分刚到的参会者也一同出发）。编写Python程序，统计接送n个参会者所需的最少车辆数。运行程序，显示所有参会者提交的信息，按到达时间先后排列，再显示所需的最少车辆数，程序运行结果如图所示。
（1）若将图中第4行“08：154”数据改为“08：151”，程序输出的结果是否会发生改变 （A．会改变B．不会改变）
（2）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
a=［'08：15 4'，'08：14 3'，'08：23 4'，'08：15 2'，'08：12 2'，'08：17 1'，'08：17 3'，'08：19 4'，'08：21 4'，'08：17 1'］
def tran（str1）：
ss=int（str1［：2］）*60+int（str1［3：6］）
return ss
for i in range（len（a）-1）：
for j in range（len（a）–1，i，-1）：
if a［j］a［j］，a［j-1］=a［j-1］，a［j］
n=len（a）
b=［］
c=［］
for i in range（n）：
b.append（tran（a［i］［：5］））
c.append（b［-1］+int（a［i］［6：］））
for j in range（i，0，-1）：
①
if c［k］>c［j］：
b［k］，b［j］=b［j］，b［k］
c［k］，c［j］=c［j］，c［k］
else：
break
sum=0
flag=［False for i in range（n）］
for i in range（n）：
if flag［i］==False：
for j in range（i，n）：
if ② ：
flag［j］=True
③
print（'接送所有参会者最少需要%d辆车'%sum）
21．有如下Python程序对列表内的数字进行排序:
请编写并补充代码，完善程序:
(1)第5行下划线处应填入 。
(2)第8行下划线处应填入 。
(3)该程序采用了 算法。
四、简答题
22．说明归并排序的步骤。
23．论述归并排序的基本思想和实现步骤。
参考答案：
1．D
2．B
3．C
4．D
5．D
6．B
7．D
8．D
9．C
10．A
11．D
12．C
13．A
14．B
15．B
16．O(n^2)
17．O(nlogn)
18．随机选择
19．单元格
20． A k=j-1 flag［j］== False and b［j］<=c［i］或b［j］<=c［i］ sum+=1或sum=sum+1
21． i+1 k!=i 或 i!=k 选择排序
22．归并排序的步骤包括分解、递归排序和合并。首先将数组分解成两个子数组，然后对它们分别进行归并排序，最后将两个有序子数组合并成一个有序数组。
23．归并排序的基本思想是将两个有序的子序列合并成一个有序序列。实现步骤包括递归地将数组分成两半，对每一半进行归并排序，然后将两个有序的子序列合并成一个有序序列。归并排序的平均时间复杂度为O(nlogn)。

展开更多......

收起↑