资源简介

第五章 数据结构与算法 章节测试
一、选择题
1．有如下 VB 程序段：
For i = 1 To 8
a(i) = Int(Rnd * 7) + 1
Next i
For i = 1 To 3
For j = 1 To 8 - 2 * i
If a(j) Mod 7 > a(j + 2) Mod 7 Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
Next j
Next i
For i = 1 To 8
ch(i) = Chr(a(i) + Asc("A") - 1)
Next i
执行该程序段后，ch(1)～ch(8)各元素值不可能的是（ ）
A．AACBFBFE B．GGABCDDE C．ABBBCDDE D．ABBCDDEG
2．某书店在5所学校流动售书量（单位，本）分别是88,110,48,64,35。若采用冒泡排序算法对其进行从小到大排序，则第二趟的排序结果是（ ）。
A．35 88 110 48 64
B．35 48 88 64 110
C．35 48 88 110 64
D．35 48 64 88 110
3．下列关于递归算法的说法中，正确的是（ ）
A．在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间
B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些
C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些
D．对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））；”就是一种递归调用
4．使用升序排序算法对列表[130,20,98,15,67,3 ]进行排序后结果为（ ）
A．[130,20,98,15,67,3 ] B．[3,15,20,67,98,130 ]
C．[15,20,98,67,3, 130] D．[130,98,67,20,15,3 ]
5．有如下Python程序段
def s(x):
if x<=2:
y=x
else:
y=s(x-1)+s(x-2)
return y
a=int(input("请输入正整数："))
result=s(a)
print(result)
运行程序，输入值为6，则输出结果为（ ）
A．8 B．9 C．13 D．14
6．下列关于递归和迭代两种算法的描述错误的是（ ）
A．迭代算法和递归算法原理不同，因此迭代程序和递归程序不能相互转换
B．递归是重复调用函数自身
C．迭代通常使用计数器结束循环
D．递归中遇到满足终止条件的时候逐层返回
7．某个使用递归算法的Python程序段如下：
def doit(x):
tmp=0
if x<=2:
tmp=2
else:
tmp=3*doit(x-1)+2*doit(x-2)
return tmp
print(doit(5))
执行该程序段后，输出的结果是（ ）
A．16 B．34 C．122 D．434
8．某对分查找算法如下：
i=1:j=6:c=1
key=int（rnd*100+1）
do while i <= j
m=（i+j）\2
c=c+1
if key1oop
数组d（1）~d（6）的值分别为“17，21，29，32，39，75”，则程序运行结束后，下列说法错误的是（ ）
A．i=j+1是成立的 B．若key=21，则i=1
C．当key=32时，m=j是成立的 D．若key如果是38，那么m=4
9．小明和小华玩猜数字的游戏，所猜数字不超过800，小明首先猜400，小华说大了，小明又猜200，当小华再次说大了，小明猜100，当小华说小了，小明猜150，以此类推，直到猜到正确的数字。上述方法中蕴含的算法思想是（ ）
A．穷举算法 B．递归算法 C．二分查找法 D．顺序查找法
10．观察如下VB程序段：
Function fx(n As Integer) As Long
If n＝1 Then
fx＝1
Else
fx＝2*fx(n－1)
End If
End Function
Private Sub Command1_Click()
Dim n As Integer，x As Long
n＝Val(Text1.Text)
x＝fx(n)
Text2.Text＝Str(x)
End Sub
若在文本框Text1中输入数字5，单击命令按钮Command1后，在文本框Text2显示的内容为( )
A．2 B．8 C．16 D．32
11．有如下程序段：
def bubbleSort (n):
if n == 1:
return
for i in range (n - 1):
if arr [i] > arr[i+1]：
arr[i], arr[i+1] =arr [i+1], arr[i]
bubbleSort（n-1）
from random import randint
n=randint(3, 5)
bubbleSort(n)
若数组arr的值为“64，34，25，12，22，11，90”，则调用函数bubbleSort(n)后 arr[3]的值不可能的是（ ）
A．12 B．25 C．34 D．64
12．关于栈，下列说法错误的是( )
A．栈是先进后出（FILO）表。它的数据元素只能在同一端（称为栈顶）进行操作，添加（进栈），删除（出栈）
B．pop(0)方法可以删除列表的尾元素(相当于栈的“出栈”操作)
C．pop()方法可以删除列表的尾元素(相当于栈的“出栈”操作)
D．append方法可以在列表尾部添加一个数据元素（相当于栈的“入栈”操作）
13．有一入栈序列为“ABCD”，以下以“C”开头的出栈序列中不正确的是（ ）
A．CABD B．CBAD C．CBDA D．CDBA
14．已知链表a中的每个节点包含数据区域和指针区域两部分，下列Python 程序段的功能是在链表a中删除数据值为key的所有节点
key=int(input("输入要删除的数据："))
head=0
while a[head][ 0]==key and head!=-1:
head=a[head][1]
p=q=head
if head!=- 1:
q=a[q][1]
while ① :
if a[q][0]==key:
②
else:
p=a[p][1]
q=a[q][1]
则划线①②处的代码分别为（ ）
A．①a[q][1]!=-1 ②a[p][1]=a[q][1] B．①a[q][1]!=-1 ②a[q][1]=a[p][1]
C．①q!=-1 ②a[q][1]=a[p][1] D．①q!=-1 ②a[p][1]=a[q][1]
15．在信息加工中，经常要对被处理的数据进行排序，在排序时经常要进行数据的交换。下列四个选项中，能正确地将x和y两个变量中的数据进行交换的是（ ）。
A． B． C． D．
二、填空题
16．递增数列用二分法查找时，先以 位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列 为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。
17．迭代法也称 ，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的 称为一次“迭代”，而每一次迭代得到的 会被用来作为下一次迭代的 。
18．小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1，停靠站时间忽略不计；换乘地铁的用时也都相等，记为t2。
（1）如果t1＝t2，小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线。
（2）设t1＝2min，t2＝lmin，则小明从A站出发到达B站的最短用时为 min。
19．递归的要素： 的递归的重要组成； ，它保证递归能在 的计算后得出结果，而不会产生 的情况。
20．class UnionFindSet(object):
def __init__(self, data_list):
self.father_dict = {}
self.size_dict = {}
for node in data_list:
self.father_dict[node] = node
self.size_dict[node] = 1
def find(self, node):
father = self.father_dict[node]
if(node != father):
if father != self.father_dict[father]: # 在降低树高优化时，确保父节点大小字典正确
self.size_dict[father] -= 1
father = self.find(father)
self.father_dict[node] = father
return father
def is_same_set(self, node_a, node_b):
return self.find(node_a) == self.find(node_b)
def union(self, node_a, node_b):
if node_a is None or node_b is None:
return
a_head = self.find(node_a)
b_head = self.find(node_b)
if(a_head != b_head):
a_set_size = self.size_dict[a_head]
b_set_size = self.size_dict[b_head]
if(a_set_size >= b_set_size):
self.father_dict[b_head] = a_head
self.size_dict[a_head] = a_set_size + b_set_size
else:
self.father_dict[a_head] = b_head
self.size_dict[b_head] = a_set_size + b_set_size
N = int(input())
for i in range(N):
M = int(input())
nums = []
maxNum = 0
for j in range(M):
tempTwoNum = list(map(int, input().split()))
maxNum = max(maxNum, max(tempTwoNum))
nums.append(tempTwoNum)
union_find_set = UnionFindSet(list(range(maxNum+1)))
for i in range(M):
union_find_set.union(nums[i][0], nums[i][1])
res_dict = {}
for i in union_find_set.father_dict:
rootNode = union_find_set.find(i)
if rootNode in res_dict:
res_dict[rootNode].append(i)
else:
res_dict[rootNode] = [i]
#print(res_dict)
print( len(res_dict.keys()))
输入：
1
10
0 1
2 3
4 6
2 5
5 4
1 6
10 11
7 9
8 10
7 11
输出：
三、判断题
21．迭代算法与递归算法都需要重复执行某些代码，两者基本相同。 ( )
22．集合结构中的数据元素存在多对一的关系。( )
23．图结构中数据元素是多对多的关系。( )
24．递归的边界条件要素，是为了保证递归能在有限次的计算后得出结果，而不会产生无限循环的情况。 ( )
四、操作题
25．有n件重量各不相同的物品，从中挑选2件物品使其重量和等于k。编写了一个VB程序实现上述功能，运行程序，从数据库中读取n件物品的编号和重量并在列表框List1中显示，在文本框Text1中输入重量k后，单击“挑选”按钮Command1，在列表框List2中按重量从小到大显示各物品的编号和重量，在列表框List3中显示所有符合条件的物品编号；若未找到，则输出“未找到这样的组合”。程序运行界面如图所示。
（1）程序运行时，按钮Command1上显示“挑选”，是通过设置该对象的 属性实现的（单选，填字母：A．Text / B．Caption / C．Font）。
（2）实现上述功能的VB程序如下，请在划线处填入合适代码。
（3）程序加框处的代码有误，请改正。
Const n = 10
Dim num(1 To n) As Integer, w(1 To n) As Integer
Private Sub Form_Load()
'本过程从数据库中读入n件物品的编号和重量分别存数组num，w中，并在List1中显示，代码略。
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim t As Integer, f As Boolean
Dim p As Integer, q As Integer
Dim k As Integer, flag As Boolean
f = False
i = 1
Do While
f = True
For j = n To i + 1 Step -1
If ① Then
t = num(j): num(j) = num(j - 1): num(j - 1) = t
t = w(j): w(j) = w(j - 1): w(j - 1) = t
f = False
End If
Next j
②
Loop
For i = 1 To n
List2．AddItem Str(num(i)) + " " + Str(w(i))
Next i
k = Val(Text1．Text)
flag = False
p = 1: q = n
Do While ③
If w(p) + w(q) < k Then
p = p + 1
ElseIf w(p) + w(q) > k Then
q = q - 1
Else
List3．AddItem Str(num(p)) + "和" + Str(num(q))
flag = True
p = p + 1: q = q - 1
End If
Loop
If Not flag Then
List3．AddItem "未找到这样的组合"
End If
End Sub
26．小美在研究自定义货币系统，她想知道和自己定义的任意货币系统等价，同时面额种数最少的货币系统中有多少种面额。例如，和{3,6,10,19}等价的货币系统中，面额种数最少的是{3,10}，即可用{3,10}表示{3,6,10,19}中的任意数。
在寻找等价货币系统时，小美发现了如下规律：（1）、与给定货币系统等价的货币系统必定是该货币系统的子集；（2）、如果货币系统中的某个面额可以被其他货币表示时，该面额是无效的；为此，小美按照如下方法构造最小等价货币系统B：先将原货币系统A的所有面额升序排序，每次把A中可以被B中的货币表示的面额删去后，将A中的最小面额放入B中。以此类推。基于此方法，小美编写了如下程序，在文本框Text1中输入给定的货币系统，单击按钮Command1后，在标签Label1中输出与其等价的货币系统的最小面额种数，在标签Label2中输出该货币系统。程序运行界面如图所示。
（1）若给定货币系统为{4,6,8,14,22}，则与其等价的面额种数最少的货币系统为 。
（2）按此要求编写的程序如下，请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String, tmp As String, c As String
Dim n As Integer, i As Integer, j As Integer, ans As Integer
Dim a(1 To 100) As Integer, b(1 To 10000) As Boolean
'数组b(i)用于表示值i能否用已经放入新货币系统中的面额来表示
'此段程序用于将给定货币系统存储在a数组中并将其元素个数存储在变量n中
s = Text1.Text
tmp = "": n = 0
For i = 1 To Len(s)
c = Mid(s, i, 1)
If c >= "0" And c <= "9" Then

ElseIf tmp <> "" Then
n = n + 1
a(n) = Val(tmp)
tmp = ""
End If
Next i
For i = 1 To n - 1
For j = n To i + 1 Step -1
If Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
ans = 0: s = "{"
For i = 1 To a(n)
b(i) = False
Next i
For i = 1 To n
If Not b(a(i)) Then
ans = ans + 1
If ans <> 1 Then s = s + ","
s = s + CStr(a(i)) 'Cstr函数用于将数值变量转为字符串变量并去除首位空格

For j = a(i) + 1 To a(n)
If b(j - a(i))= True Then b(j) = True
Next j
End If
Next i
s = s + "}"
Label1.Caption = "与之等价的最小货币系统面额种数为" + Str(ans)
Label2.Caption = "其为" + s
End Sub
27．某协会进行钓鱼比赛，最后有十人进入决赛，录入员编制了如下Visual Basic程序，功能是根据成绩进行排序，程序中数组 a保存所有参赛者的成绩，数组b保存此成绩对应的姓名，第i位参赛者的成绩保存在a(i)中，姓名保存在b(i)中。
程序界面如图所示，左边列表框List1中显示原始数据(成绩和相应的姓名)，单击“排序”按钮(Command1)，排序后的结果按成绩从高到低显示在列表框List2中。
解决此问题的算法流程图如图所示，排序部分的程序段如下：
Dim a (1 To 10) As Single
Dim b (1 To 10) As String
Private Sub Command1_Click()
Dim i As Integer，j As Integer，k As Integer，x As Single，y As String
For i＝1 To 9
k＝i
For j＝i＋1 To 10
If ①________ Then k＝j
Next j
If k＜＞i Then
x＝a(i)：a(i)＝a(k)：②________
y＝b(i)：b(i)＝b(k)：b(k)＝y
End If
Next i
For i＝i To 10
List2.AddItem Str(a(i))＋“ ”＋b(i)
Next i
End Sub
Private Sub Form_Load()
’此过程用于对数组a和数组b进行初始赋值，代码略
End Sub
(1)解决此问题的算法是________。(选填：冒泡排序或选择排序)
在程序①和②画线处，填入适当的语句或表达式，把程序补充完整：
(2)程序中①画线处应填入________。
程序中②画线处应填入________。
28．小王利用循环排序思想编写了一个VB程序，用于计算下一轮比赛的出场顺序。从数据库中读取本轮比赛的人员姓名存在数组xm中，成绩存在数组cj中（成绩均不重复）。编程实现将这些成绩进行循环升序排列。要求最低成绩的位置不变，然后依次进行升序排序，即从最小值开始向下尾首相连形成升序数列。程序运行界面如图所示。点击“排序”按钮，完成循环升序排序。
（1）“排序”按钮的对象名为_
（2）请在划线处填入合适代码。
（3）加框处代码出错，请改正。
Dim xm（1 to 100）As String ,cj（1 to 100）As Integer
Dim flag（1 to 100）As Boolean
Private Sub Form_ Load（ ）
'从数据库中读取数据，存储到相应数组中，并输出在列表框Listl。第i个人，姓名为xm（i），成绩为cj（i）。人员数量存储到变量n中（）。代码略
End Sub
Private Sub Cmd__Click（）
Dim min As Integer, pmin As Integer
min = cj(1): pmin = 1
For i=2 To n
If cj（i） < min Then min = cj（i）：__①__
Next i
flag（pmin） = True
pmin= pmin + 1
If pmin=n+1 Then pmin=1
For i=1 To n-2
k = pmin
For j=1 To n
If ② Then k= j
Next j
If k <> pmin Then
t = cj（k）: cj（k） = cj（pmin）: cj（pmin） = t
C = xm（k）: xm（k） = xm（pmin）: xm（pmin） = c
End If
flag（pmin） = True
pmin=pmin+1
Next i
'将排序后的人员姓名和成绩输出到列表框List2中，代码略。
End Sub
29．程序设计：在舞会上，男生、女生各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。跳完后的两人重新回到队尾。
例如：boy＝['Alex','Steven','Jack'],girl＝['Ada*,'Babs'.,'Danla','Jane']
输出：
Turn1:(Alex,Ada)
Turn2:(Steven,Babs)
Turn3:(Jack,Danla)
Turn4:(Alex,jane)
……
Turn12:(Jack,jane)
代码如下：
boy＝['Alex','Steven',‘Jack']
girl＝['Ada','Babs','Danla','Jane']
for i in range(12):
x,y＝ ① #出队
print(“Turn{:2}):({}，{})".format(i＋1,x，y))
boy.append( ② ) #再进队
girl.append( ③ ) #再进队
（1）程序代码中①处正确的代码是( )。
A．boy.pop(l).girl.pop(l) B．girl.pop(l),boy.pop(l)
C．boy.pop(0),girl.pop(0) D．girl.pop(0),boy.pop(0)
（2）程序代码中②处正确的代码是( )。
A．x B．y C．i D．i＋1
（3）程序代码中③处正确的代码是( )。
A．x B．y C．i D．i＋1
参考答案：
1．D
2．C
3．A
4．B
5．C
6．A
7．C
8．B
9．C
10．C
11．B
12．B
13．A
14．D
15．BCD
16．中点 缩小
17．辗转法 重复 结果 初始值
18．A-L-K-H-G-B 或 A-L-K-J-I-B 12
19．递推关系 边界条 有限 无限循环
20．2
21．错
22．错误
23．正确
24．对
25．B （3）i <= n - 1 And Not f 或 i <= n - 1 And f = False ① w(j) < w(j - 1) ② i = i + 1 ③ p < q
26．{4,6} tmp = tmp + c a(j) < a(j - 1) b(a(i)) = True
27．(1)选择排序
(2)①a(k)＜a(j)或a(j)＞a(k)
②a(k)＝x
28．（1） Cmd
（2）①pmin=i ②cj（j） < cj（k） And flag（j） = False
（3）pmin = pmin Mod n+ 1
29．C A B

展开更多......

收起↑