浙教版（2019）选修一5.3数据排序同步练习

浙教版（2019）选修一5.2数据排序同步练习 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．在信息加工中，经常要对被处理的数据进行排序，数据的排序有多种方法，冒泡法是一种常用的排序方法，在排序时经常要进行数据的交换。下列四个选项中，（   ）不能正确地将x和y两个变量中的数据进行交换。 A．x = y y = x x = x － y B．x = x + y y = x － y y = m C．m = x x = y x = y － x D．x = x － y y = x + y A．A B．B C．C D．D 2．已知列表a中包含100个随机数 （随机数的范围为0-9），现要输出每个数字在序列中的排名，数字越小，排名靠前 （从 1开始计数），且当数字大小相同时，排名相同，下一组数字的排名为当前数字排名加上当前数字的数量, 如列表a中部分数据为[9,2,1,6,2,6,1,9,7,2]，则其排名依次为“9316361983”。实现该功能的程序段如下，方框中应填入的正确代码为（  ） b=[0]*10 for i in a: b[i]+= 1 print（s） A． B． C． D． for i in range（1,10）: b[i]+=b[i-1] s="" for i in range（100）: s+=str(b[a[i]])+"" c=[0]*10 for i in range（1,10）: c[i]=b[i-1]+c[i-1] s="" for i in range（100）: s+=str（c[a[i]]+1）+"" c=[0]*10 for i in range（1,10）: c[i]=b[i-1]+c[i] s="" for i in range（100）: s+=str（c[a[i]]+ 1）+"" c=[0]*10 for i in range（10）: c[i]=b[i]+c[i-1] s="" for i in range（100）: s+= str（c[i]）+"" A．A B．B C．C D．D 3．数组L长度为n，要实现数组元素L[a]至L[b]升序排列（0≤a<b≤n－1），其余元素的位置不变，实现相应功能的程序段如下： for i in range (0, b-a): for j in range (b-1, a-1, -1): if L[j]<L[j-1]: L[j], L[j-1]=L[j-1], L[j] 加框处代码在测试程序时发现有误，可修改为（    ） A．range(a, b-1) B．range (b, a-i, -1) C．range (b, a+i, -1) D．range (a-i+1, b) 4．有如下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] 5．用数组a和b存储两个降序序列，用数组c存储合并后的降序序列。如a=[19,16,12,8,5]，b=[20,15,14,10,6]，c=[20,19,16,15,14,12,10,8,6,5]。实现该功能的程序段如下： c=[-1]*(len(a)+len(b)) p=0；tot=len(a) for i in range(len(a)):     (1) for i in range(len(b)):     while b[i] < c[p]:         p +=1     if c[p]==-1:         c[p]=b[i];tot+=1     else:         for j in range( (2) ):             c[j+1]=c[j]         c[j]c[p]=b[i]         tot+=1 上述程序段划线处可选代码为： ①c.append(a[i])    ②c[i]=a[i]    ③tot,p-1,-1    ④tot,p;-1    ⑤tot-1,p-1,-1 则（1）（2）处的代码依次为（   ） A．①③ B．①④ C．②⑤ D．②③ 6．采用冒泡排序对数据6，7，9，2，1，8，5，4进行升序排序，则排序完成时共进行数据交换的次数为（   ） A．15 B．16 C．17 D．18 7．若采用冒泡排序对数据1，19，6，7，2，8，23，15进行排序处理，则第二遍加工后的结果是（   ） 原始数据 1 19 6 7 2 8 23 15 第一遍加工后 23 1 19 6 7 2 8 15 第二遍加工后 … A．23，19，1，15，8，6，7，2 B．23，19，1，15，6，7，2，8 C．23，19，15，1，6，7，2，8 D．23，19，15，8，1，6，7，2 8．下列Python程序段的功能是对数组a中的元素进行升序排序: #输入10个数据，并存储在数组a中，代码省略 n=len(a) for i in range(　　　①　　　):     for j in range(　　　②　　　):     if a[j]>a[j-1]:     a[j]，a[j-1]=a[j-1]，a[j] 程序中划线①②处应填写的正确语句是（   ） A．①0 n-1　②n-1，i+1，-1 B．①0 n-1　②n-1，i C．①1，n　②n-1，i-1 D．①1，n　②n-1，i-1，-1 9．有如下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 10．以下两个程序段的功能相同，实现的功能是：删除列表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．在实现该功能的过程中，程序段②比程序段①需要更多的存储空间 11．有如下Python程序段:   flag =True;n = 6 while flag :      i = 0; flag = False      while i < n-1 :           if a[i] % 2 != 0 :                   if a[i] < a[i+1] or a[i+1] % 2 == 0 :                          a[i] , a[i+1] = a[i+1] , a[i]                   flag = True           i += 1      n -= 1 若数组a的元素为“89,79,34,76,85,70”，则程序段执行完毕后，数组a的内容是（　　） A．[76,70,34,89,85,79] B．[34,76,70,89,85,79] C．[34,70,76,79,85,89] D．[34,76,70,79,85,89] 12．使用选择排序法对数据“8,7,5,9,5,6”从大到小排序，共需经过（   ）次数据对调。 A．3 B．4 C．5 D．6 13．在上体育课的时候同学们随便排了队伍，老师要求按照身高从高到低依次排队，如果按照插入排序算法，第一步要做的是（   ） A．前2位同学从高到低排 B．前2位同学从低到高排 C．最高的同学跟最低的同学交换位置 D．最高的同学跟第一位同学交换位置 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．有如下Python程序段： from random import randint n=8 a=[0]*n k=randint(1,3) for i  in  range(n):       a[i]=randint(0,50) for i in range(0,n//k+1):       j=0       while j+k< n:               if a[j]>a[j+k]:                      t=a[j];a[j]=a[j+k];a[j+k]=t               j+=1 print(a) 执行该程序段后，输出的结果不可能是（   ） A．[3,14,17,25,28,31,32,37] B．[31,6,29,12,18,31,17,34] C．[1,4,20,5,48,23,49,46] D．[3,6,30,14,38,32,41,45] 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查排序方法。x=y；y=x；x=x-y。在执行第二行语句时，y已经被赋值为x的原始值，导致第三行的赋值操作出现问题，无法正确实现数据交换。故答案为：A。 2．B 【详解】本题考查的是桶排序。b[i]存放的是数字i的个数，可以设置10个桶c数列。数字越小，排名靠前 （从 1开始计数），且当数字大小相同时，排名相同，下一组数字的排名为当前数字排名加上当前数字的数量。故第一个循环循环体为： c[i]=b[i-1]+c[i-1]。故选B。 3．C 【详解】本题考查的是冒泡排序。选项A，根据比较位置是j和j-1，排序的元素是L[a]至L[b]，a和a-1比较肯定是错误的； 选项B，由于i是越来越大，a-i越来越小，这样排序的范围变大，错误； 选项C，根据选项B的分析，C正确；选项D，冒泡排序的特点，起始位置是不变的，这里的起始位置是a-i+1不断变化，错误。故选C。 4．D 【详解】本题考查的是插入排序。阅读程序可知，比较的是abs (a[j]-2)>abs(k-2)，即最终是按abs (a[i]-2)升序排列，即最后每个数据项减2后求绝对值应为升序，4个选项结果如下表： A B C D 原始值 -5，-2，4，0，1 3，-1，0，2，-3 1，2，3，4，5 0，4，0，-2，-4 -2 -7，-4，2，-2，-1 1，-3，-2，0，-5 -1，0，1，2，3 -2，2，-2，-4，-6 求绝对值 7，4，2，2，1 1，3，2，0，5 1，0，1，2，3 2，2，2，4，6 故本题应选D。 5．C 【详解】本题考查插入排序。已知c已赋长度，因此(1)应填写②而非①。从tot=len(a)，可知 tot 表示数组的最后个元素的后一个位置或数组的元素个数。例如c=[10,20.30,40.-1,-1...], tot=4，因此向后移动时，先执行c[4]=c[3]，因此(2)填写⑤。故本题应选C。 6．C 【详解】本题考查冒泡排序相关内容。采用冒泡排序对数据进行升序排序，以从后往前进行数据比较为例，具体排序过程如下表所示: 则数据交换次数为:6+4+3+3+1=17，故本题答案为C选项。 7．B 【详解】本题考查冒泡排序。观察第一遍加工后的结果可知，本题的排序方式为降序，并且从后往前进行数据比较和交换，若后面的数据比前面的大则进行互换，因此第二遍加工后的结果为23，19，1，15，6，7，2，8，故答案为B。 8．D 【详解】本题主要考查的是冒泡排序。根据代码“if a[j]>a[j-1]:”可知，排序时数据是从后往前进行比较和交换的，变量i表示排序的次数，n个数据排序共需进行n-1遍，变量j表示当前数组元素的下标，因此方法一为:①处代码为0，n-1，②处代码为n-1，i，-1；方法二为：①处代码为1，n，②处代码为n-1，i-1，-1，因此答案为D。 9．C 【详解】本题考查Python程序执行。分析程序，可知外循环一次，c递增1，内循环交换一次，c递增1。无交换时，循环结束。 当i=0时，c=c+1=1，内循环中，2和5交换1次，2和7交换1次，此时d=[1，2，7，5，3]，c=3，last=2； 当i=last=2时，c=c+1=4，内循环中，3和5交换1次，3和7交换1次，此时d=[1，2，3，7，5]，c=6，last=3； 当i=last=3时，c=c+1=7，内循环中，5和7交换1次，此时d=[1，2，3，5，7]，c=8，last=4。不再满足while循环条件，循环结束。程序运行后，变量c的值为8。故选C。 10．D 【详解】本题考查的是循环语句及算法效率。由程序代码可知，程序①的时间复杂度为O（n2），程序②时间复杂度为O（n），选项A错误；当i位置上有连续3个以上的相同数据时，若没有i-=1，将会遗落一次比较，选项B错误；修改后，原程序输出结果将变为升序，选项C错误；程序段②增加了数组b，将会占用较大空间，选项D正确。故本题应选D。 11．B 【详解】本题考查排序算法。这个程序段是一个排序算法，但在排序的过程中，只涉及奇数元素。初始数组：[89,79,34,76,85,70]。让我们逐步分析程序的执行：第一轮循环后：[89,34,76,85,70,79]；第二轮循环后：[34,76,89,70,85,79]；第三轮循环后：[34,76,70,89,85,79]；第四次循环后：[34,76,70,89,85,79]；第五次循环后：[34,76,70,89,85,79]；第六次循环后：[34,76,70,89,85,79]，之后退出循环，程序执行结束。故答案为B选项。 12．B 【详解】本题主要考查选择排序算法。选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。使用选择排序法对数据“8,7,5,9,5,6”从大到小排序，第一次交换8和9，变为“9,7,5,8,5,6”；第二次交换8和7，变为“9,8,5,7,5,6”；第三次交换5和7，变为“9,8,7,5,5,6”；第四次交换5和6，变为“9,8,7,6,5,5”，此时已有序，故本题选B选项。 13．B 【详解】本题主要考查插入排序算法。插入排序的思想是： 将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。在上体育课的时候同学们随便排了队伍，老师要求按照身高从高到低依次排队，如果按照插入排序算法，第一步要做的是前2位同学从低到高排，其余学生在已排序好的学生序列中找到合适的位置依次插入即可，故本题选B选项。 14．D 【详解】本题主要考查选择排序。选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。对于数据 [4,5,1,3,2]，在使用选择排序从小到大进行第一轮排序之后，结果是 [1,5,4,3,2]，故本题选D选项。 15．B 【详解】本题考查的是随机函数及排序。由 while语句段，可知最终列表a是间隔k个元素升序排列。由k=randint(1,3)可知，k的取值是1、2、3。选项A是k取值为1时，可能实现；选项C是k取值为2时，可能实现；选项D是k取值为2时，可能实现；故本题应选B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$