第九单元 算法的程序实现
单元小结
知识系统构建
第九单元 算法的程序实现
单元检测题组
时间:40分钟 分值:50分
一、选择题(每题3分,共27分)
1.对包含100个元素递增排序的数组a,采用对分查找法找某关键字,若查找不成功,则关键字的比较次数最多是( )
A.100 B.6 C.7 D.8
答案 C 本题考查对分查找的基本原理。n个元素中查找不成功的最多比较次数为[log2n]+1。
2.有如下某排序算法程序段:
For i=1 To 3
k=i
For j=i+1 To 6
If a(j) > a(k) Then k=j
Next j
t=a(i):a(i)=a(k):a(k)=t
Next i
数组元素a(1)到a(6)的值依次为“8,2,9,3,5,1”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )
A.8,2,9,3,5,1 B.9,2,8,3,5,1
C.9,8,5,2,3,1 D.9,8,5,3,2,1
答案 D 本题考查排序算法及其程序的实现。i=1时,代入循环体,计算得到数组元素的值依次为9,2,8,3,5,1。i=2时,代入循环体,计算得到数组元素的值依次为9,8,2,3,5,1。i=3时,代入循环体,计算得到数组元素的值依次为9,8,5,3,2,1。
3.某VB程序段如下:
For i=1 To 6
j=7
Do While j > i
If a(j)>a(j-1) Then
a(j)=a(j)+a(j-1)
a(j-1)=a(j)-a(j–1)
a(j)=a(j)-a(j-1)
End If
j=j-1
Loop
Next i
For i=3 To 6
s=s+a(i)
Next i
Label1. Caption=Str(s)
已知数组元素a(l)到a(7)的值依次为“8, 2, 3, 7, 10, 6, 5”,则执行该程序段后,标签Label1中显示的是( )
A.21 B.26 C.41 D.18
答案 A 首先理解 a(j)=a(j)+a(j-1),a(j-1)=a(j)-a(j-1),a(j)=a(j)-a(j-1)这三个语句实际上就是将a(j)与 a(j-1)两数据交换。两数交换的经典写法是:t=a,a=b,b=t。程序首先实现数组a中的数据降序,得到“10,8,7,6,5,3,2”,而后将 a(3),a(4),a(5),a(6)的值相加输出。
4.有如下程序段:
Dim a(4) As Integer
Private Sub Command1_Click()
Dim s As String
a(1)=10:a(2)=30:a(3)=20:a(4)=40
s=doit(4)
Label1.Caption=s
End Sub
Function doit(k As Integer) As String
If k=1 Then
doit=Str(a(1))
Else
doit=doit(k-1) & Str(a(k))
End If
End Function
程序运行后,标签Label1中显示的内容是( )
A.10 20 30 40 B.10 30 20 40
C.40 30 20 10 D.40 20 30 10
答案 B 本题考查递归程序。递归调用过程如下:
5.用以下对分查找算法:在一个包含有重复元素且从小到大排序(相等元素排在一起)的整数数组a中,查找某个重复出现的整数key,其中数组元素的总个数是n。
i=1: j=n
Do While i <=j
m=(i+j) 2
If a(m) < key Then i=m+1
Else
j=m-1
End If
Loop
那么执行该程序后,下列说法正确的是( )
A.程序可以找到重复元素key最开始出现的位置,该位置信息由变量i指示
B.程序可以找到重复元素key最后出现的位置,该位置信息由变量i指示
C.程序可以找到重复元素key最开始出现的位置,该位置信息由变量j指示
D.程序可以找到重复元素key最后出现的位置,该位置信息由变量j指示
答案 A 本题考查对分查找算法的理解和应用。由程序可知,当i≤j时程序要循环,而循环时,当a(m)≥key时,变量j移动,这就表明当找到key时,指示变量j势必会跑到key所在位置的前面去,key所在位置由i来指示。由升序排序和j的移动方向可知,这是起始位置。
6.有以下VB程序段
i=1: j=10: flag=True: cs=0
Key=Int(Rnd()*10)+28
Do While i <=j And flag=True
m=(i+j) 2 : cs=cs+1
If a (m)=Key Then
flag=False
Else If a(m) < Key Then
i=m+1
Else
j=m-1
End If
Loop
数组元素a(1)到a(10)依次是3 10 17 23 27 30 35 40 45 50,变量cs的值可能是( )
A.1或2 B.2或3
C.3或4 D.4或5
答案 C 本题考查对分查找,key=Int(Rnd() * 10)+28即产生[28,37]的随机整数。cs表示查找次数,10个数查找过程如下(只需要考虑28至37范围内的数):
3
10
17
23
27
30
35
40
45
50
①
③
④
②
因此三次(如30)、四次(如35)都可能,找不到的情况也可能是三次(如28)或四次(如33),10个数不管找不找得到,最多查找次数不超过int(log210)+1=4次。
7.有如下程序段:
For i=1 To 2
k=i
For j=i+1 To 5
If d(k) < d(j) Then k=j
Next j
If k <> i Then t=d(k): d(k)=d(i) :d(i)=t
Next i
经过该程序段“加工”后,数组元素d(1)到d(5)的值依次为“44, 35, 30, 11,7”,则数组元素d(1)到d(5)的原始数据依次为( )
A.30,44,7,11,35 B.30,11,44,7,35
C.44,30,11,7,35 D.30,7,44,11,35
答案 D 该段程序仅进行了两趟排序,数据就已完成降序排序。而选项 A 需要三趟,B、C两个选项都需要四趟才能使数据完成降序排序。 所以答案选 D。
8.有如下VB程序段:
i=1
j=6
s=“”
Key=Text1. Text
Do While i <=j
m=Int((i+j) / 2+0. 5)
s=s+“ ”+a(m)
If Key > a(m) Then
i=m+1
Else
j=m-1
End If
Loop
Text1. Text=s
数组元素a(1)到a(6)的值分别为“Beijing”“Guangdong”“Jiangsu” “Jiangxi”“Shanghai” “Zhejiang”,己按字典序排序。当key的值为“Zhejiang”时,单击命令按钮Command1,文本框Text1中显示的内容为( )
A.Jiangxi Zhejiang
B.Jiangsu Shanghai Jiangxi Zhejiang
C.Jiangxi Zhejiang Shanghai
D.Jiangsu Shanghai Zhejiang
答案 C 本题考查对分查找,第一次查找时i=1,j=6,得到m=4,因此s=“Jiangxi”,因为key>a(m),因此第二次查找时i=5,j=6,得到m=6,因此s=“Jiangxi Zhejiang”,此时key=a(m),执行j=m-1=5;因此第三次查找时i=5,j=5,得到m=5,因此s=“Jiangxi Zhejiang Shanghai”,此时key>a(m),因此执行i=m+1=6,此时i>j,退出循环。所以答案选择C。
9.有如下VB程序段:
s=“7218634594” : n=Len(s): c=0
For i=1 To n-1
a(i)=Val(Mid(s, i, 2))
Next i
For i=1 To n-2 Step 2
k=i
For j=i+2 To n-1 Step 2
If a(j) < a(k) Then k=j
Next j
If k <> i Then
t=a(i): a(i)=a(k): a(k)=t: c=c+1
End If
Next i
Text1.Text=Str(c)
该程序段运行后,Text1中显示的内容是( )
A.1 B.2 C.3 D.4
答案 B 首先获取 a数组的各元素为72,21,18,86,63,34,45,59,94。然后从外层For i=1 To n-2 Step 2看出,仅对奇数位上的数据排序。变量c统计排序过程中数据交换的次数。第一趟排序,数据“ 72 ”与“ 18 ”交换。第二趟排序,数据“ 72 ”与“ 45 ”交换。而后奇数位上的数据已有序。 所以答案选 B。
二、非选择题(共23分)
10.现有n根棍子,第i根棍子的长度为ai。想要从中选出三根棍子组成周长尽可能长的三角形,输出最大的周长;若无法组成三角形,则输出0。如当n=5,a={2,3,4,5,10}时,输出12,即选择了3、4、5。当n=4,a={4,5,10,20}时,无法组成三角形,输出0。加框处代码有误,请改正。
Dim a(1 To 1000) As Integer
Dim n As Integer
Private Sub Form_Load()
’确定 n 的值和数组 a 的各个元素值,即每根棍子的长度值,代码略
End Sub
Function max(x As Integer , y As Integer) As Integer
If x > y Then
max=x
Else
max=y
End If
End Function
Private Sub Command1_Click()
Dim i As Integer , j As Integer , k As Integer
Dim ans As Integer , c As Integer , longest As Integer , rest As Integer
ans=0
’让 i
For i=1 To n
For j=i+1 To n
For k=j+1 To n
c=a(i)+a(j)+a(k)
longest=max(longest, c) ’①
rest=c-longest ’rest 保存最短的两条边的和
If ans > c Then ’②
ans=max(ans , c)
End If
Next k
Next j
Next i
Print ans
End Sub
答案 ①max(a(i), max(a(j), a(k)))(或其他写法) ②rest > longest
解析 由三重For循环和变量c的组成可以判断这是一个枚举算法,c是当前枚举到的周长。而由程序的输出可知ans是最长的周长,显然要找到最大值,需要比较,还有一个很重要的条件就是三条边可以组成三角形。大小比较的任务已经由ans=max(ans,c)来完成,那么第②空就是判断能否成为三角形的条件。这里可以写成a(i)+a(j)>a(k)&a(i)+a(k)>a(j) &a(j)+a(k)>a(i)的复合表达式,但由前面的rest=c-longest可以猜测出longest保存了最长边,而rest是剩余两边之和。于是第②空的条件可以简单地变成最短两边之和大于最长边,即rest>longest。而第①空就是a(i),a(j),a(k)三者的最大值,可以迭代调用函数max(),即现调用任意两个,再调用第3个,如max(max(a(i),a(j)),a(k))或者任意交换这三个变量的书写位置都可以。
11.小王编写“合并区间” VB程序,功能如下:窗体加载时,获取并存储合并前的区间数据,并显示在列表框List1中。单击“合并”按钮后,以区间左端点数值对区间进行升序排序,然后相邻区间的相交进行合并,最后在列表框List2上显示合并后的区间。程序运行如图所示:
实现以上功能的VB程序如下,在横处填入合适的代码。
Dim a(1 To 20) As Integer ??存储区间的左端点数值
Dim b(1 To 20) As Integer ??存储区间的右端点数值
Private Sub Form_Load()
’将区间左端点存入数组a,区间右端点存入数组b,并在列表框List1显示,代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim curL As Integer, curR As Integer
For i=1 To n-1
For j=l To n-i
If ① Then?
t=a(j): a(j)=a(j+1): a(j+1)=t
t=b(j): b(j)=b(j+1): b(j+1)=t
End If
Next j
Next i
curL=a(1): curR=b(1)
For i=2 To n
If ② Then?
If curR < b(i) Then ③ ?
Else
List2.AddItem“["+Str(curL)+Str(curR)+"]”
curL=a(i): curR=b(i)
End If
Next i
List2. AddItem “[”+Str(curL)+Str(curR)+“]”
End Sub
答案 ①a(j) > a(j+1) ②a(i) <=curR ③curR=b(i)
解析 第①空,以区间左端点数值,即数组a,对区间进行升序排序。
第②空和第③空,这是需要合并区间的情况,首先理解变量 curR 的含义,curR 表示第i个区间的上一个区间的右端点数值。因此如果当前区间的左端点数值即a(i)<=curR,而当前区间的右端点数值即b(i)>curR时,上一个区间与当前区间就可以合并。因此第②空填a(i) <=curR。第③空是合并后,右区间curR则等于第 i 个区间右端点数值。
12.插数。输入一个整数x,要将x插入到n(n<50)个有序(按降序排列)数据中,并使数据序列仍保持有序,试求出x应插入的位置。界面设计如图所示。
程序说明:
(1)其中n由文本框Text1中数据得到,x由文本框Text2中数据得到,插入位置显示在文本框Text3中。
(2)其中n个有序数据将通过随机函数Rnd产生,并对n个数进行降序排序后存入数组a中,同时显示在列表框List1中。
为了实现这一目标,完善下面的VB程序,在横线处填入合适的语句或表达式,完成程序设计。
Private Sub Command1_Click()
Dim a(1 To 50)As Integer
Dim n As Integer,i As Integer
Dim x As Integer,temp As Integer
Randomize
List1.Clear
n=Val(Text1.Text)
x=Val(Text2.Text)
’随机产生n个数,并存放至a数组中
For i=1 To n
a(i)=Rnd*200+1
Next i
’将数组a中的数按降序排序
For i=2 To n
For j=n To i Step-1
If (1) Then?
temp=a(j):a(j)=a(j-1):a(j-1)=temp
Next j
Next i
’将排序后的数组元素显示在列表框List1中
For i=1 To n
List1.AddItem Str(a(i))
Next i
’插入操作
If (2) Then?
i=n+1
Else
(3) ?
Do While x i=i+1
Loop
End if
’在文本框Text3中显示插入位置
Text3 Text=Str(i)
End Sub
(1) 。?
(2) 。?
(3) 。?
答案 (1)a(j)>a(j-1) (2)x<=a(n) (3)i=1
解析 本题主要考查排序算法的程序实现。
(1)本题采用了冒泡排序。冒泡排序的算法特点是相邻两个元素的两两比较,并根据需要交换,代码中a(j)与a(j-1)的交换语句说明该程序采用了冒泡排序。因为是降序排序,因此大的数在前,小的数在后,如果次序反了,则需要交换两数。因此该处应该填:a(j)>a(j-1)。
(2)变量i用于存储x应该插入的位置。由于数据源是从大到小排列,因此如果x小于或等于数据源中最后一个数据,则它应该插在最后面,这是最简单的情况。该数据源总共有n个数,最后一个数据是a(n)。因此如果x≤a(n),则i=n+1。
(3)如果x比数据源中最后一个数据要大,那么就要寻找它合适的位置。方法是通过循环语句,将x与该数列中的每一个数据a(i)比较,如果xa(i),则当前的i值就是x该插入的位置。
13.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 100) As Integer
’n=10,排序前生成的数据存储在数组a中,并在列表框List1中显示,代码略
Private Sub Command1_Click()
Dim i As Integer, j As Integer, start As Integer, t As Integer
i=2
Do While i < n start=n
For j=n To i Step-1
If ① Then?
t=a(j):a(j)=a(j-1):a(j-1)=t
② ?
End If
Next j
i=start+1
Loop
For i=1 To n
List2.AddItem ③ ?
Next i
End Sub
答案 ①a(j) < a(j-1) ② start=j ③ Str(a(i))
解析 第①空,从图中得知程序要实现升序排序,所以只有当后面的数据小于前面的数据时才需要数据交换,而从后面交换的语句中可以看出是 a(j) 与 a(j-1)交换,所以填 a(j) < a(j-1)。
第②空,冒泡升序排序优化即每一趟排序记录下最后一个数据交换的位置,那么下一趟排序时就不需要对该位置前面的数据进行比较了。因此把每一趟的最后一个数据交换的位置定义为下一趟排序时的结束位置,所以 start=j 。
第③空, 列表框中输出排序好的数组 a,同时注意列表框输出结果是字符串类型。
14.查找最接近的数。编写一个查找最接近的数的VB程序:程序运行时,在文本框Text1中输入产生随机数的个数(1到100之间),单击命令按钮“产生随机数并升序排列”后,在列表框List1中显示已经按升序排列后的随机整数。然后在文本框Text2中输入要查找的整数,单击命令按钮“查找”后,在标签Label3中显示随机整数序列中与待查找数最接近的整数(当最接近的数有2个时,输出较大的一个)。程序运行效果如图所示。实现上述功能的VB代码如下,请在横线处填入合适代码。
Dim n As Integer ’存储随机数的个数
Dim f(1 To 100) As Boolean ’f (i)为true时表示随机整数i已经产生过
Dim a(1 To 100) As Integer ’依次存放升序排序后的n个随机数
Private Sub Command1_Click()’命令按钮“产生随机数并升序排列”的单击事件
Dim i As Integer
Randomize
For i=1 To 100
f(i)=False
Next i
n=Val(Text1. Text)
For i=1 To n
t=Int(Rnd * 100+1)
Do While f(i)=True
t=Int (Rnd * 100+1)
Loop
① ?
Next i
j=0
For i=1 To 100??实现排序并输出
If f(i)=True Then
② ?
a(j)=i
List1.AddItem Str(i)
End If
Next i
End Sub
Private Sub Command2_Click()??命令按钮“查找”的单击事件
Dim key As Integer
key=Val(Text2. Text)
If key <=a(1) Then Label3. Caption=Str(a(1)) : Exit Sub
If key >=a(n) Then Label3. Caption=Str(a(n)) : Exit Sub
L=1: R=n
Do While L <=R??找到与key较为接近的两个数a(R)和a(L)
m=(L+R) 2
If key <=a(m) Then
R=m-1
Else
L=m+1
End If
Loop
If ③ Then ??在a(R)和a(L)中选出更接近key的数?
Label3. Caption=Str(a(R))
Else
Label3. Caption=Str(a(L))
End If
End Sub
答案 ① f(t)=True ②j=j+1 ③Abs(a(R)-key) < Abs(a(L)-key)
解析 ①处根据题干可知该处为产生不重复的随机数,产生之后将对应的f数组内的值改为 True,标记该数字已产生,故①f(t)=True,②将产生的数依次输出,故②j=j+1,③通过对分查找到二个数 a(R)、 a(L),判别更接近key的数。故③Abs(a(R)-key) < Abs(a(L)-key)。
15.有100个大小形状一样的玻璃球,其中有1个玻璃球的重量轻于其他99个玻璃球,如何用一台无砝码的天平,以最快的速度找出这个轻玻璃球?运用“三分筛选”法来模拟“寻找”这个轻玻璃球的算法如下:
步骤1:如果待筛选的玻璃球个数<3,则认定己经找出了这个玻璃球(认定方法参照步骤2中描述), 停止筛选,并输出经过的筛选总次数;否则,重复执行步骤2。
步骤2:按编号依次将玻璃球均分成3份,如果有多余的放入第3份中;比较第1、2份的玻璃球重量:
①如果第1份等于第2份的重量,则选取第3份的玻璃球作为下一次筛选的对象;
②如果第1份小于第2份的重量,则选取第1份的玻璃球作为下一次筛选的对象;
③如果第1份大于第2份的重量,则选取第2份的玻璃球作为下一次筛选的对象;
重复执行步骤1。
例如:第1次筛选的小球编号区间是1~100,均分成三份的待称重小球编号分别是1~33、34~66、67~100;第 2次则选取以上3份中的一份进行再筛选、再均分……直至找到。
解决上述问题的VB程序功能如下:运行程序,在列表框List1中显示100组数据,分别代表每个编号及对应的小球重量(其中有且只有一个小球的重量与其他小球不同),单击“筛选”按钮Command1,在列表框 List2中显示每次筛选的编号区间和完成筛选的总次数。程序运行界面如图。
(1)如果编号为88的小球是最轻的,按照题中给定算法,找到此小球需经历的筛选次数是
次。?
(2)实现上述功能的VB程序如下,请在横线处填入合适的代码。
Const maxn=100
Dim a(1 To maxn) As Integer
Dim w(1 To 2) As Integer ??数组w用来存储第1份和第2份小球的重量
Private Sub Form Load()
??此处代码用来模拟产生100个小球的重量,分别存储在数组元素a(1)~a(100)中;
??其中只有1个小球的重量为8,随机存储在数组a的某元素中,其余重量均为10;
??此处代码略
End Sub
Private Sub Command1_Click()
Dim left As Integer, right As Integer ??left 为起始编号,right 为结束编号
Dim s As Integer, c As Integer ??s为每次查找的区间长度
left=1: right=maxn
c=1: s=right: i=0
List2. AddItem Str (i+1)+“--->”+Str(maxn)
Do While right-left > 3
w(1)=0: w(2)=0: k=1
i=left
s= ① ?
Do While i<=(s 3) * 2+left-1??Do语句用于将待筛选的数据进行区域划分
w(k)=w(k)+a(i)
If i=(s 3) * k+left-1 Then k=k+1
i=i+1
Loop
If w(1)=w(2) Then
left=left+(s 3) * 2
Elself w(1) < w(2) Then
② ?
Else
right=left+(s 3) *2-1
left=s 3+left
End If
③ ?
List2. AddItem Str(left) &“--->” & Str(right)
Loop
List2. AddItem “经过” +Str (c)+“次后找到”
End Sub
答案 (1)5 (2) ①right-left+1 ②right=s 3+(left-1) ③c=c+1
解析 (1)处根据题干第一次查找范围[1,100],第二次查找范围[67,100],第三次查找范围[78,88],第四次查找范围[84,88],第五次查找范围[86,88],区间长度小于等于3,结束,故为5次。(2)①处为赋值区间长度的初始值,故①right-left+1,②为当第一份小于第二份的情况,待查找在第一份里找,赋值右端点值,故②right=s 3+(left-1),③为满足一次区间相关次数加1故③c=c+1。
16.活动课上,n个学生要两两组队进行拔河比赛,要求每个小组总体重不超过120kg,小林想知道最多可以组成多少个队伍,并希望得到可行的组队方案。于是设计了如下界面的程序,在文本框Text1中输入n 个学生的体重(数字之间用逗号隔开),单击“队伍”按钮Command1后在标签Label1上显示最多可组队数量,同时在列表框List1输出方案。
实现上述功能程序如下,在横线处填入合适的代码。
Dim n As Integer
Dim a(1 To 50) As Integer
Sub makedata(s As String) ??该过程实现将输入的体重分别存入数组a中
Dim in As Long, x As Long, c As String, i As Integer
m=Len (s) : n=0
For i=1 To m
c=Mid(s, i, 1)
If c >=“0” And c <=“9” Then
① ?
x=x+Asc(c)-Asc(“0”)
Else
If x > 0 Then n=n+1: a(n)=x
x=0
End If
Next i
n=n+1: a(n)=x
End Sub
Private Sub Command1_Click()
Dim s As String, i As Integer, j As Integer, t As Integer
Dim cnt As Integer, st As Integer, ed As Integer
s=Text1.Text Call makedata(s) ??调用过程
For i=1 To n-1??实现降序排序
For j=n To i+1 Step-1
If ② Then?
a(j)=a(j)+a(j-l) : a(j-l)=a(j)-a(j-l) : ③ ?
End If
Next j
Next i
??下列程序段实现计算最多可组队伍
cnt=0: st=1: ed=n
Do While st < ed
If a(st)+a(ecl) <=120 Then
List1. AddItem Str(a(st))+“和”+Str(a(ed))+“组队”
cnt=cnt+1
st=st+1
④ ?
Else
st=st+1
End If
Loop
Label2. Caption=“最多可以组”+Str (cnt)+“组队伍”
End Sub
答案 ① x=x * 10 ② a(j) > a(j-1) ③ a(j)=a(j)-a(j-1) ④ ed=ed-1
解析 第①空,变量 c 为文本框中截取下来的每一个字符,如果截取下来的字符是数字,那么通过它的ASCII 码值减去数字“0”的 ASCII 码值求得该数值存储在变量 x 中,x=x+Asc(c)-Asc(“0”),如果截取下来的下一个字符还是数字,那么 x 需要乘以 10 变成十位上的一个数,即 x=x * 10,然后与新截取下来的数值相加 x=x+Asc(c)-Asc(“0”),得到一个两位数的体重存储在变量 x 中。
第②空,冒泡排序,降序,从后往前,相邻两数比较大小,后面的数大于前面的数时需要交换,即 a(j) > a(j-1)。
第③空,数据 a(j) 与 a(j-1)交换。
第④空, 组队伍, 第一个数据与最后一个数据加起来如果小于 120 那么可以组一队。 组队后组数加 1,即 cnt=cnt+1,同时指向下一组数据的位置,即起始位置往后移一个 st=st+1,终止位置往前移一个 ed=ed-1。
