【加试题】某排序算法思想如下：若有11个桶，编号从0～10，随机产生多个整数，每产生一个整数时，就在以该整数位编号的桶中放一面小旗子，最后只要按顺序数每个桶中有几面小旗子，就能得到这几个整数的有序排列。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次，按桶的编号顺序读出旗子数量，没有旗子的桶略过,得到有序整数为“2,3,5,5,8”。为此，小李编写了一个VB程序，功能如下：运行程序，窗体加载时随机产生6个[0,9]的随机整数，并在列表框List1中依次显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示经过上述排序算法后的数据。运行结果如图所示。实现上述功能的VB代码如下，但横线处代码有错，请改正。Dim a(10) As Integer'数组a表示桶的编号，如a(0)表示第0号桶Private Sub Command1_Click()Dim i As Integer, j As IntegerFor i = 0 To 10For j = 1 To i 错①处List2.AddItem CStr(i)Next jNext iEnd SubPrivate Sub Form_Load()Dim i As IntegerRandomizeFor i = 0 To 10'将数组初始化为0a(i) = 0Next iFor i = 1 To 6'产生6个[0,9]的随机数t = Int(Rnd * 10)a(t) = t + 1 '第t桶中小旗子数量加1 错②处List1.AddItem CStr(t)Next iEnd Sub① ②

1. 窗体上有一命令按钮(Command1)，单击此按钮，程序运行后使用“冒泡”法将数组x中的十个数从小到大进行排列，将排序前后的数据输出到窗体上。程序代码如下。请将程序补充完整。

Option Base 1

Private Sub Command1_Click()

Dim x

x=Array(123，23.45.5.9.53.78、99，295.654)

Print "排序前数组数据"

For i=1 To 10

Print x(i);

Next i

Print

For i = 1 To

For j = i+1 To

If x(i) x(j) Then

a = x(i)

x(i)= x(j)

x(j)= a

End lf

Print "排序后数组数据";

For i = 1 To 10

Print x(i);

Next i

Print

End Sub

填空题普通

2. n个数据的冒泡排序需要经过n-1遍的加工，每一遍加工都自下而上比较相邻的两个数据，把较小者交换到上面，在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下，第i遍加工过程中，在上面部分较小的数据已经有序的情况下，不需要再进行n-i对数据的比较，如对“17，18，19，24，23，20”这6个数据排序时，第1遍排序结束后的数据为“17，18，19，20，24，23”，那么第2遍排序时就不再需要对20及其前面3个数据进行比较。以下程序实现了冒泡排序的优化，其程序运行界面如图所示，但加框处代码有误，请改正。

Dim n As Integer

Dim a（1 to 10）As Integer

Private Sub Form_Load( )

‘n=10，排序前生成的数据存储在数组a中，并在列表框List1中显示

‘代码略

End Sub

Private Sub Command1_Click( )

Dim i，j As Integer

Dim start As Integer

‘①

Do While i<n

start=n

For j=n To i Step-1

If a（j）<a（j-1）Then

t=a（j）：a（j）=a（j-1）：a（j-1）=t

start=j

End If

Next j

‘②

Loop

For i=1 To n

List2.AddItem Str（a（i））

Next i

End sub

以上程序段运行时，为了实现上述功能，加框处代码应改正为：①；②。

填空题普通

1. 有如下程序段：

s = input()

head = 0; tail = 0; ans = 0; tmp = '' q = ['']*100

flag = True

for i in range(len(s)):

if s[i] == ',':

while head!=tail:

tmp += q[head]

head += 1

if flag and head < tail:

head += 1

flag = not flag

ans += int(tmp)

tmp = ''; flag = True

elif '0'<=s[i]<='9':

q[tail] = s[i]

tail += 1

若输入 s 为“1-500,2023900-,”，执行该程序段，变量 ans 的值为（）

A. 100 B. 22300 C. 22351 D. 22400

单选题普通

2. 某VB程序段如下：

S=””

For i=2 to 4

For j=8 to i+1 step -1

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

t=d(j)：d(j)=d(j-1)：d(j-1)=t

End if

Next j

s=s+" "+d(i)

Next i

Label1. caption=s，

若数组元素d(1)到d(8)的数据依次为：

"12"，"7"，"18”，"13"，”9"，"17"，"6"，"23"，运行该程序段后，标签label1中显示的内容是( )

A. 7 9 13 B. 6 7 9 C. 13 17 18 D. 12 13 17

单选题普通

3. 分别采用选择和冒泡排序算法对数据序列“2，3，4，5，1，0”完成升序排序，则需要交换的次数分别为（）

A. 5次和9次 B. 4次和12次 C. 5次和15次 D. 4次和18次

单选题普通

1. 某项活动有n个单位（编号1到n）参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。

若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。

设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。

编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：

(1) 由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为。

(2) 定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。

def bubble_sort(lst):

n=len(lst)

for i in range(0, n-1):

return

调用该函数，若 lst 为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]]，请回答①和②两个问题。

①虚线框中的程序段第 1 次执行后，关于 lst 中的剩余员工人数，下列说法正确的是（单选，填字母）。

A.lst[0][1]数值最小 B.lst[0][1]数值最大

C.lst[5][1]数值最小 D.lst[5][1]数值最大

②虚线框中的程序段执行的次数为。

(3) 实现分组功能的部分 Python 程序如下，程序中用到的列表函数与方法如图 c 所示，请在程序中划线处填入合适的代码。

函数与方法	功能
w.append(x)	在列表 w 末尾添加元素 x
x.w.pop()	将列表 w 末尾元素赋值给 x，并将其从 w 中删除

def group(data, m):

n=len(data)

a=[]

for i in range(n+1):

a.append([]) # a[i]初始化为空列表，存放编号为 i 的单位所分配的分组编号

gnum=0

for i in range(n): #各单位内部分组

while data[i][1]>=m:

gnum+=1

k=data[i][0]

a[k].append(gnum)

bubble_sort(data) #根据每个单位的剩余员工人数，对 data 进行降序排序

b=[]

for i in range(m):

b.append([])

i=0 #对剩余员工分组

while i<n and data[i][1]!=0:

while j<m and len(b[j])==0:

j+=1

if j<m:

v=b[j].pop()

else:

gnum+=1

v=gnum

a[data[i][0]].append(v)

i+=1

#输出各单位的分组编号，代码略

'''

读取小组人数上限存入 m；读取 1 至 n 号单位的数据，依次存入列表 data 的 data[0]至 data[n-1]中。

Data[i]包含 2 个数据项，data[i][0],data[i][1]分别存放单位编号及员工人数，代码略

'''

group(lst, m)

综合题困难

2. 有n个从小到大排列的整数依次存储在列表nums中，现要求将上述n个数的平方按从小到大的顺序依次存入列表ans中。如nums = [-4,-1,0,3,10]，则ans = [0,1,9,16,100]。

(1) 实现上述功能的部分 Python程序如下，请在划线处填入合适的代码。

# 输入n个数从小到大依次存储到列表nums中，代码略

k = -1

for i in range(n):

if nums[i] < 0:

k = i

else:

break

ans = []

i, j = k, k + 1

while i >= 0 or j < n:

if i < 0:

ans.append()

j += 1

elif j==n:

ans.append(nums[i] * nums[i])

elif :

ans.append(nums[i] * nums[i])

i -= 1

else:

ans.append(nums[j] * nums[j])

j += 1

print(ans)

(2) 若输入nums的数据为[-4,1,4]，则输出ans的值为。

综合题困难

3. 分组冒泡排序。分别对数组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]

综合题困难

1. 某排序算法排序过程如图所示，由图可知，该算法的时间复杂度为（）

A. O(n) B. O(n²) C. O(log₂n) D. O(2ⁿ)

单选题普通

2. 某排序算法的VB程序段如下：

‘读取n个整数，依次存入a（1）到a（n）中，代码略

For i=1 To n - 1

For j=n To i+ 1 Step -l

If a(j)>a(j-1) Then t=a(j) : a(j)=a(j-1) : a(j-1)=t

Next j

Next i

执行上述程序段，下列说法正确的是（）

A. 交换过位置的数据，可能会再回到其初始位置 B. 执行完成后，数组元素a(1)到a(n)从小到大排列 C. 若n为5，整个排序过程总的比较次数是20 D. 整个排序过程总的交换次数至少为1

单选题普通

3. 现有三个整数序列：“1，2，3，4，5，”“7，1，6，8，3”、“9，8，7，6，5”。用选择排序算法分别对三个序列进行升序排列，比较次数依次为x、y、z，则下列关系正确的是( )

A. x=y=z B. x>y>z C. y>z>x D. z>y>x

单选题普通