【加试题】字符串排序。编写VB程序，实现如下功能：程序运行时，单击命令按钮Command1 产生100个随机字符串（每个字符串长度不超过10），并显示在列表框List1中，单击命令按钮Command2对产生的100个随机字符串按权值进行降序排序，将排序结果显示在列表框List2中。每个字符串的权值定义为该字符串中ASCII码值最大的字母的ASCII码值，例如字符串“Hello”中ASCII码值最大的字母是“o”（ASCII码值为111），则字符串“Hello”的权值为111。程序运行效果如图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。 Dim a(1 To 100) As String '依次存放100 个随机字符串 Dim b(1 To 100) As Integer '依次存放每个字符串的权值 Private Sub Command1_Click() '产生100 个随机字符串 Dim i As Integer, k As Integer, t As Integer, x As Integer Randomize For i = 1 To 100 k = Int(Rnd * 10 + 1) : t = 0 'k 表示第i 个字符串的长度 Do While t < k '通过循环依次产生第i 个字符串a(i)的k 个字符 If Int(Rnd * 2 + 1) = 1 Then '产生一个小写字母的ASCII 码值 x = Asc("a") + Int(Rnd * 26) Else x = Asc("A") + Int(Rnd * 26) '产生一个大写字母的ASCII 码值 End If '① If b(i) < x Then b(i) = x t = t + 1 Loop List1.AddItem a(i) Next i End Sub Private Sub Command2_Click() '对100 个字符串按字符串权值降序排序 Dim i As Integer, j As Integer, y As Integer Dim s As String For i = 1 To 99 k = i For j = i + 1 To 100 '② Next j If k <> i Then s = a(k): a(k) = a(i): a(i) = s y = b(k): b(k) = b(i): b(i) = y End If Next i For i = 1 To 100 List2.AddItem a(i) Next i End Sub ① ②

1. 某商场有升降货梯需要在各个楼层（商场总楼层m=7）之间实现货物运送，已知需要运送的货物量为n件，分别需要从各个起点楼层送去目标楼层，例如“1-7”表示货物需要从楼层1送到楼层7，上下楼层间运作和停顿时间为3分钟，其他时间（包括空闲时上升或下降）不计。设计一个VB程序模拟运送过程，并计算输出上升过程和下降过程分别需要的时间。若起始位置楼层大于目标位置楼层，表示货物需要往下运送，为了提高运送的效率，先将货梯从下往上运送，再实现从上往下运送。

设计一个VB程序，模拟生成10件货物的上升或者下降需求，在数组en和ex中分别记录每件货物起始楼层和目标楼层，将初始需求输出到列表框List1中，然后点击按钮Command1完成货物起始楼层先升后降的排序，当起始楼层相同时，上升中则目标楼层升序，下降中则目标楼层降序。将排序结果输出到列表框List2，最后计算出上升和下降分别需要的总时长输出到文本框Text1。程序界面如下：

(1) 程序界面中有（填数字）类控件没有Caption属性。

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

Const n = 10：Const m = 7

Dim en(1 To n) As Integer, ex(1 To n) As Integer

Dimf(1 To n) As Integer '值为1表示货物往上运送，值为-1表示货物往下运送

'n件货物起始楼层、目标楼层以及升降值分别存入数组en，ex，f，输出到List1，代码略

Private Sub Command1_Click()

Dim i As Integer, j As Integer, up1 As Integer, up2 As Integer

Dim t(1 To 2) As Integer, first As Integer, last As Integer, p As Integer

For i = 1 To n -1

For j = n To i + 1 Step -1

up1 = f(j)*(en(j)*10+ex(j)): up2 = f(j-1)*(en(j-1)*10+ex(j-1))

If f(j) > f(j -1) Or f(j) = f(j -1) AndThen

p = f(j): f(j) = f(j -1): f(j -1) = p

p = en(j): en(j) = en(j -1): en(j -1) = p

p = ex(j): ex(j) = ex(j -1): ex(j -1) = p

End If

Next j

Next i

i = 1: first = en(1): last = ex(1): p = 1

Do While i < n '计算货梯上升时间和下降时间

i = i + 1

If Then '改错

t(p) = t(p) + (last -first) * 3

last = ex(i): first = en(i)

ElseIf f(i) * (en(i) -last) > 0 Then

t(p) = t(p) + f(i) * (last -first) * 3

last = ex(i): first = en(i)

ElseIf f(i) * (en(i) -last) <= 0 And f(i) * (ex(i) -last) > 0 Then

End If

Loop

t(p) = t(p) + f(i) * (last -first) * 3

Text1.Text = "升降货梯分别需要" & t(1) & "和" & t(2)& "分钟完成。"

'将排序后的升降信息输出到List2，代码略

End Sub

(3) 程序中加框处代码有错，请改正。

综合题困难

2. 某超市管理人员需要对一周以来商品交易的部分流水账单进行分析，以找出销售额排在前3名(同金额同名次)的商品信息。

编写VB程序，实现上述功能。运行程序，在列表框List1中显示每笔交易流水记录的商品货号与销售金额，单击“分析”按钮Command1，汇总同类商品的销售额并在列表框List2中显示销售额前3名的商品货号与销售金额。程序运行界面如图所示。

(1) 在列表框中显示结果时，使用到的“AddItem” 是。

(单选，填字母： A .类名/B .属性名/C .方法名/D .事件名)

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

'n是交易流水的记录总数，ng是商品种类，代码略

Dim goods(1 To n) As String '每笔交易的商品货号

Dim money(1 To n) As Single '每笔交易的销售金额

Dim g(1 To ng) As String

Dim c(1 To ng) As Single

Private Sub Form_ Load ()

'读取每笔交易流水，分别将商品货号存入数组goods、销售金额存入数组money

'g(1)~g (ng)分别存储ng种商品的货号，在List1中显示交易记录信息，代码略

End Sub

Private Sub Command1_Click ()

Dim i As Integer, j As Integer, tc As Single, tg As String

For i=1 To n

For j=1 To ng

If goods(i) = g(j) Then

Next j

Next i

i =1

Do While i <= ng

Fo rj=ng To i+1 Step-1

If c(j)>c(j-1) Then

tc=c(j) : c(j)=c(j-1) : c(j-1)=tc

tg=g(j) : g(j)=g(j-1) : g(j-1)=tg

End If

Next j

If Then Exit Do

i =i+1

Loop

For j=1 To

List2.AddItem g(j) +“”+ Str(c(j))

Next i

End Sub

(3) 程序中加框处代码有误，请改正。

综合题困难

3. 无重叠区间。在若干个区间中，删除重复区间，使得剩余区间互不重叠(区间[1，2]和[2，3]虽有边界值2相等，但不认为是重叠区间)。小李设计VB程序，在文本框Text1中输入用逗号分隔的整数，相邻两个整数表示一个区间(任意区间的左边数据小于右边数据)。如图中所示为区间[1，2]，[2，3]，[3，4]，[2，4]。点击“判断”按钮Command1后，删除重复区间[2，4]，在文本框Text2输出满足无重复区间时需要删除的最小区间数量。运行界面如图所示。

(1) 若输入的区间集合为[2，4]，[1，3]，[3，4]，[5，6]，则需要删除区间的最小数量为。

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

Private Sub Command1_Click( )

Dim a(1 To 100) As Integer

Dim i As Integer, j As Integer

Dim temp As Integer, k As Integer

Dim res As Integer, ed As Integer

'从文本框Text1中读入整数存储到数组a中，整数的个数存放在变量k中，代码略

For i=1 Tok\ 2-1 '以区间左边数据为主要关键字升序排序

For j=k\2 To i+1 Step-1

If Then

temp=a(j*2-1)：a(j*2-1)=a((j-1)*2-1)：a((j-1)*2-1)=temp.

temp=a(j*2)：a(j*2)=a((j-1)*2)：a((j-1)*2)=temp

End If

Next j

Next i

ed=a(2)

res= 0

For i=2 To k\2 '计算需要删除区间的最小数量

If Then

res=res+1

ed= min(ed, )

Else

ed=a(i * 2)

End If

Next i

Text2. Text= Str(res)

End Sub

Function min(x As Integer， y As Integer) As Inte-ger '函数功能：返回x与y的最小值

'代码略

End Function

综合题困难

1. 使用列表d模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为（）

图 a

图 b

t=h

p=d[h][1]

while p != -1 :

q=d[p][1]

p=q

d[t][-1]=-1

A. if d[p][0]>0:

d[q][1]=p

d[t][1]=q

else:

d[h][1]=q

h=p

B. if d[p][0]>0:

d[t][1]=q

t=q

else:

h=p

d[p][1]=t

C. if d[p][0]>0:

d[t][1]=p

t=p

else:

d[p][1]=h

h=p

D. if d[p][0]>0:

d[t][1]=q

d[q][1]=p

else:

d[p][1]=h

h=q

单选题普通

2. 已排序的列表a有n个整型元素，现要查找出现次数最多的值并输出。若出现次数最多的值有多个，则输出最前面的一个。实现该功能的程序段如下，方框中应填入的正确代码为（）

c,m,v =1,1,0

for i in range(1,n):

print(a[v])

A. if a[i]==a[i-1]:

c+=1

if c>m:

m=c

v=i

else:

c=1

B. if a[i]==a[i-1]:

c+=1

if c>m:

m=c

v=i

else:

c=1

C. if a[i]==a[i-1]:

c+=1

else:

if c>m:

m=c

v=i-1

c=1

D. if a[i]==a[i-1]:

c+=1

else:

if c>m:

m=c

v=i-1

c=1

单选题困难

3. 小孟为提高效率，对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：

p = 1: q = 10

Do While p < q

iMin = p: iMax = p

For i = p + 1 To q

If a(i) < a(iMin) Then

iMin = i

elseIf a(i) > a(iMax) Then

iMax = i

endif

Next i

t = a(iMax): a(iMax) = a(q): a(q) = t

①

t = a(iMin): a(iMin) = a(p): a(p) = t

p = p + 1:q = q -1

Loop

要使程序实现上述算法思想，则方框中的语句是（）

A. If iMax = q Then iMax = iMin B. If iMin = q Then iMin = iMax C. If iMax = q Then iMin = iMax D. If iMin = q Then iMax = iMin

单选题普通

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

单选题普通