浙教版（2019）选修一 5.3 数据排序

5.3数据排序 一、选择题 1．假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序的过程中，进行第一趟排序结束时，元素40不可能在哪个元素之后（    ） A．38 B．46 C．56 D．64 2．有如下Python程序段 #随机产生5个整数，存储在列表a中 for i in range (1,5): k=a[i] j=i-1 while j>=0 and abs (a[j]-2)>abs(k-2):     a[j+1]=a[j]     j-=1 a[j+1]=k 执行该程序段后，列表a的值可能是（    ） A．[-5，-2，4，0，1] B．[3，-1，0，2，-3] C．[1，2，3，4，5] D．[0，4，0，-2，-4] 3．一个序列经过一趟冒泡排序后的结果是：10，21，13，24，28，则原始序列不可能是（  ） A．21，13，24，28，10 B．21，10，24，28，13 C．21，10，24，13，28 D．21，24，13，28，10 4．以下两个程序段的功能相同，实现的功能是：删除列表a（元素个数为n）中的重复元素（只保留一个），并将剩下的元素降序输出。 # 程序段① # 对列表a进行降序排序，代码略 i=1 while i<n:     if a[i]==a[i-1]:         for j in range（i+1,n）:             a[j-1]=a[j]         ;n-=1    i+=1 # 输出列表元素a[0]到a[n-1]，代码略 # 程序段② max_num=max（a）#求出列表a中的最大值max_num b=[0]*（max_num+1） for i in range（0,n）:     b[a[i]]+=1 :    if b[i]>0:         print（i,end=""） 关于上述两个程序段及功能的描述，正确的是（    ） A．同样的数据规模，两个程序段的时间效率一样 B．程序段①加框处语句是否执行不受列表a原数据的影响 C．程序段②加框处语句修改为“for i in range（1,max_num+1）”，输出结果不变 D．在实现该功能的过程中，程序段②比程序段①需要更多的存储空间 5．有如下phthon程序，程序运行后，变量c的值为：（   ） d=[1，7，5，2，3] flag=False；last=i=c=0 while i<4 and flag==False：     flag=True     c+=1     for j in range（4，i，-1）：       if d[j] < d[j-1]：         d[j]，d[j-1]=d[j-1]，d[j]         flag=False；last=j         c+=1     i=last A．6 B．7 C．8 D．9 6．有如下程序段： For i=1 To 9   For j=10 To i+2 Step -1     If a(j)<a(j-2) Then       t=a(j): a(j)=a(j-2): a(j-2)=t     End If   Next j Next i 数组元素 a(1)到 a(10)的值依次为20，19，18，17，16，15，14，13，12，11，执行该程序段后，数组元素 a(8)的值为（   ） A．17 B．18 C．19 D．20 7．有如下 python 程序段，运行该程序段后， 列表a 中的值可能是（   ） import random a = [] for i in range(6): a.append(random.randint(1,5)*2+i%2) for i in range(1,5): j = i;  k = a[j] while a[j-1]<k and j>0: a[j] = a[j-1] ; j=j-1 a[j] = k A．11,8,7,6,5,5 B．8,6,5,5,3,8 C．9,6,7,8,8,11 D．11,11,8,2,2,11 8．字符串数组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 9．对一组数据采用冒泡排序算法进行排序，若第一趟排序完成后的数据序列为：31，24，23，15，20，10，则该数据序列的原始顺序不可能的是（   ） A．24，23，15，31，10，20 B．24，23，15，20，31，10 C．24，31，23，15，10，20 D．23，24，15，20，31，10 10．定义： a[1]，a[2]，……，a[n]为1，2，……，n的一个排列，若p>q，且a[p]<a[q]，则称p，q为a[1]，a[2]，……，a[n]的一个逆序。排列a[1]，a[2]，……，a[n]的个数极为该排列的逆序数。例如：2，1，5，3，4为一个排列，由于1<2，并且1排在2的前面，所以1，2为该排序的一个逆序。同理，5，3和5，4均为该排序的一个逆序。所以该排序的逆序数为3。现在有一个对1，2，……，n的排列，其逆序数为20。那么，用冒泡排序将其排为一个 从小到大递增的序列，则共进行交换的次数（    ） A．20 B．25 C．10 D．40 11．采用冒泡排序对数据6，7，9，2，1，8，5，4进行升序排序，则排序完成时共进行数据交换的次数为（   ） A．15 B．16 C．17 D．18 12．有如下程序段： def bubbleSort (n):    if  n == 1:       return    for i in range (n - 1):       if arr [i]  > arr[i+1]：          arr[i],  arr[i+1] =arr [i+1], arr[i]    bubbleSort（n-1） from random import randint n=randint(3, 5) bubbleSort(n) 若数组arr的值为“64，34，25，12，22，11，90”，则调用函数bubbleSort(n)后 arr[3]的值不可能的是（   ） A．12 B．25 C．34 D．64 13．有如下VB程序段： 生成6个随机正整数，依次存入数组元素a（1）到a（6），代码略 For i = 1 To 5 k = i For j = 5 To i + 1 Step -1 If a（k） Mod 2 <= a（j） Mod 2 Then k = j Next j If k <> i Then t = a（k）: a（k）= a（i）: a（i）= t Next i 执行该程序段后，a（1）到a（6）各元素值可能的是（    ） A．3， 7， 4， 4， 5， 8 B．2， 4， 6， 8， 10， 12 C．1， 3， 7， 2， 6， 3 D．1， 3， 5， 2， 4， 6 14．对于数据 [4,5,1,3,2]，在使用选择排序从小到大进行第一轮排序之后，结果是（   ） A．[4,5,1,3,2] B．[4,1,3,2,5] C．[1,3,2,4,5] D．[1,5,4,3,2] 15．在冒泡排序算法中，最好情况（即数组已经是有序的）下需要进行（   ）轮比较。 A．n B．n-1 C．n(n-1)/2 D．0 二、填空题 16．下表列出了存放在列表d中的8个学生的考试成绩，若用选择排序算法升序排列，在第三遍加工结束后，列表变量d[8]的值应该为 ，总共需要做 遍加工。 d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] 90 80 85 73 72 71 66 70 三、操作题 17．有如下Python程序对列表内的数字进行排序: 请编写并补充代码，完善程序: (1)第5行下划线处应填入 。          (2)第8行下划线处应填入 。 (3)该程序采用了 算法。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．D 3．D 4．D 5．C 6．A 7．D 8．B 9．D 10．A 11．C 12．B 13．B 14．D 15．B 16． 80 6 17． i+1 k!=i 或 i!=k 选择排序 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$