- 二一组卷

题型：综合题题类：难易度：困难

浙江省宁波市余姚名校2023-2024学年高二上学期信息技术第一次质量检测试卷

分组冒泡排序。分别对数组a的奇数和偶数位置的元素进行冒泡排序，即采用“跳跃式冒泡”的方法，每次跳跃的步长为2，将数组分成2个子序列，分别对这2个子序列进行排序。例如，对数组a=[6,3,5,4,1,2,8,7]进行分组跳跃式升序冒泡排序，排序后的数组a=[1,2,5,3,6,4,8,7]。

（1）、对数组a=[4,5,2,9,6,7,10,3,8,1]进行分组跳跃式升序冒泡排序，则排序后的数组

（2）、实现上述功能的Python程序如下，请在划线处填入合适的代码。

import random

n=8

a=[random.randint(1 ,9) for i in range(n)]

for i in range(0,n,)

forj in range()

if a[j]<a[j-2]:

a[j],a[j-2]=a[j-2],a[j]

（3）、将分组跳跃式冒泡排序推广到每次跳跃的步长为m的情形，例如对数组a=[6,3,5,4,1,2,8,7]进行分组跳跃式升序冒泡排序，当m=3时，排序后的数组a=[4,1 ,26,3,5,6,7]。

相关代码如下，请在划线处填入合适的代码。

import random

m=int(input(“请输入步长m:”))

n=8

a=[random.randint(1,9) for i in range(n)]

print(“排序前”,a)

for i in range()

for j in range()

if a[j]<a[j-m]:

a[j],a[j-m]=a[j-m],a[j]

举一反三

【加试题】已知数组a（1）到a（6）的原始数据为”118”，”36”，”98”，”15”，”88”，”2”，对该数组进行排序操作，某同学编写了以下VB程序：

For i=1 to 3

For j=6 to i+1 step -1

If a(j)<a(j-1) then

t=a(j): a(j)=a(j-1): a(j-1)=t

End if

Next j

Next i

则程序运行之后，数组a（1）到a（6）的值依次为（）

对N个元素用选择排序法进行排序，元素交换次数SWAP的范围是（）

【加试题】n堆金币，把两堆金币合并到一起，n堆金币经过n-1次合并之后就只剩下一堆了。如何消耗最少的体力，把这n堆金币合并成一堆？合并所消耗的体力等于每次合并两堆金币的重量之和。比如，n=3时表示共有3堆金币，每堆重量分别是2、1、9.一种合并方案是2和9合并，新堆重量是11，消耗体力为11；接着11和1合并，新堆重量是12，消耗体力为12，因此总消耗体力是11+12=23。另一种方案是：1和2合并，新堆重量是3，消耗体力为3；接着3和9合并，新堆重量是12，消耗体力为12，因此总消耗体力是3+12=15。可以证明这就是最少消耗体力。

小张经分析，每次n堆金币如果都是从小到大，将前两堆合并成新一堆，然后，继续进行从小到大排序，如此合并成最后一堆，此时消耗体力最少，为此他编写了一个解决上述问题，求最少体力的VB程序，功能如下：窗体加载时，自动读取n堆金币的数据，依次存储在数组元素a(1)、a(2)、a(3)…中，金币堆数存储在变量n中，n堆金币的重量数据显示在列表框List1中。单击“求解”按钮Command1，程序对n堆金币进行合并处理，消耗最少的体力显示在文本框Text1中。程序运行界面如图所示。