資源簡介

第五章 數(shù)據(jù)結(jié)構(gòu)與算法 章節(jié)測試
一、選擇題
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
執(zhí)行該程序段后，ch(1)～ch(8)各元素值不可能的是（ ）
A．AACBFBFE B．GGABCDDE C．ABBBCDDE D．ABBCDDEG
2．某書店在5所學(xué)校流動售書量（單位，本）分別是88,110,48,64,35。若采用冒泡排序算法對其進(jìn)行從小到大排序，則第二趟的排序結(jié)果是（ ）。
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．下列關(guān)于遞歸算法的說法中，正確的是（ ）
A．在1977年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級語言“F0RTRAN77”禁止在程序使用遞歸，原因之一是該方法可能會占用更多的內(nèi)存空間
B．和非遞歸算法相比，解決同一個問題，遞歸算法一般運(yùn)行得更快一些
C．對于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些
D．對于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)sin（x），應(yīng)用程序中的語句“y=sin（sin（x））；”就是一種遞歸調(diào)用
4．使用升序排序算法對列表[130,20,98,15,67,3 ]進(jìn)行排序后結(jié)果為（ ）
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("請輸入正整數(shù)："))
result=s(a)
print(result)
運(yùn)行程序，輸入值為6，則輸出結(jié)果為（ ）
A．8 B．9 C．13 D．14
6．下列關(guān)于遞歸和迭代兩種算法的描述錯誤的是（ ）
A．迭代算法和遞歸算法原理不同，因此迭代程序和遞歸程序不能相互轉(zhuǎn)換
B．遞歸是重復(fù)調(diào)用函數(shù)自身
C．迭代通常使用計(jì)數(shù)器結(jié)束循環(huán)
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))
執(zhí)行該程序段后，輸出的結(jié)果是（ ）
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
數(shù)組d（1）~d（6）的值分別為“17，21，29，32，39，75”，則程序運(yùn)行結(jié)束后，下列說法錯誤的是（ ）
A．i=j+1是成立的 B．若key=21，則i=1
C．當(dāng)key=32時，m=j是成立的 D．若key如果是38，那么m=4
9．小明和小華玩猜數(shù)字的游戲，所猜數(shù)字不超過800，小明首先猜400，小華說大了，小明又猜200，當(dāng)小華再次說大了，小明猜100，當(dāng)小華說小了，小明猜150，以此類推，直到猜到正確的數(shù)字。上述方法中蘊(yùn)含的算法思想是（ ）
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中輸入數(shù)字5，單擊命令按鈕Command1后，在文本框Text2顯示的內(nèi)容為( )
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)
若數(shù)組arr的值為“64，34，25，12，22，11，90”，則調(diào)用函數(shù)bubbleSort(n)后 arr[3]的值不可能的是（ ）
A．12 B．25 C．34 D．64
12．關(guān)于棧，下列說法錯誤的是( )
A．棧是先進(jìn)后出（FILO）表。它的數(shù)據(jù)元素只能在同一端（稱為棧頂）進(jìn)行操作，添加（進(jìn)棧），刪除（出棧）
B．pop(0)方法可以刪除列表的尾元素(相當(dāng)于棧的“出棧”操作)
C．pop()方法可以刪除列表的尾元素(相當(dāng)于棧的“出棧”操作)
D．a(chǎn)ppend方法可以在列表尾部添加一個數(shù)據(jù)元素（相當(dāng)于棧的“入棧”操作）
13．有一入棧序列為“ABCD”，以下以“C”開頭的出棧序列中不正確的是（ ）
A．CABD B．CBAD C．CBDA D．CDBA
14．已知鏈表a中的每個節(jié)點(diǎn)包含數(shù)據(jù)區(qū)域和指針區(qū)域兩部分，下列Python 程序段的功能是在鏈表a中刪除數(shù)據(jù)值為key的所有節(jié)點(diǎn)
key=int(input("輸入要刪除的數(shù)據(jù)："))
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．在信息加工中，經(jīng)常要對被處理的數(shù)據(jù)進(jìn)行排序，在排序時經(jīng)常要進(jìn)行數(shù)據(jù)的交換。下列四個選項(xiàng)中，能正確地將x和y兩個變量中的數(shù)據(jù)進(jìn)行交換的是（ ）。
A． B． C． D．
二、填空題
16．遞增數(shù)列用二分法查找時，先以 位置的元素作為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列 為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。
17．迭代法也稱 ，是用計(jì)算機(jī)解決問題的一種基本方法。迭代通常是為了接近并達(dá)到所需的目標(biāo)或結(jié)果。每一次對過程的 稱為一次“迭代”，而每一次迭代得到的 會被用來作為下一次迭代的 。
18．小明同學(xué)所在城市的地鐵線路局部圖，如圖所示。他計(jì)劃從A站出發(fā)去B站附近的圖書館學(xué)習(xí)。假設(shè)地鐵各線路每兩站間行車用時相等，記為t1，停靠站時間忽略不計(jì)；換乘地鐵的用時也都相等，記為t2。
（1）如果t1＝t2，小明同學(xué)希望盡快到達(dá)B站，試為他推薦一條最佳乘車路線。
（2）設(shè)t1＝2min，t2＝lmin，則小明從A站出發(fā)到達(dá)B站的最短用時為 min。
19．遞歸的要素： 的遞歸的重要組成； ，它保證遞歸能在 的計(jì)算后得出結(jié)果，而不會產(chǎn)生 的情況。
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]: # 在降低樹高優(yōu)化時，確保父節(jié)點(diǎn)大小字典正確
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．迭代算法與遞歸算法都需要重復(fù)執(zhí)行某些代碼，兩者基本相同。 ( )
22．集合結(jié)構(gòu)中的數(shù)據(jù)元素存在多對一的關(guān)系。( )
23．圖結(jié)構(gòu)中數(shù)據(jù)元素是多對多的關(guān)系。( )
24．遞歸的邊界條件要素，是為了保證遞歸能在有限次的計(jì)算后得出結(jié)果，而不會產(chǎn)生無限循環(huán)的情況。 ( )
四、操作題
25．有n件重量各不相同的物品，從中挑選2件物品使其重量和等于k。編寫了一個VB程序?qū)崿F(xiàn)上述功能，運(yùn)行程序，從數(shù)據(jù)庫中讀取n件物品的編號和重量并在列表框List1中顯示，在文本框Text1中輸入重量k后，單擊“挑選”按鈕Command1，在列表框List2中按重量從小到大顯示各物品的編號和重量，在列表框List3中顯示所有符合條件的物品編號；若未找到，則輸出“未找到這樣的組合”。程序運(yùn)行界面如圖所示。
（1）程序運(yùn)行時，按鈕Command1上顯示“挑選”，是通過設(shè)置該對象的 屬性實(shí)現(xiàn)的（單選，填字母：A．Text / B．Caption / C．Font）。
（2）實(shí)現(xiàn)上述功能的VB程序如下，請?jiān)趧澗€處填入合適代碼。
（3）程序加框處的代碼有誤，請改正。
Const n = 10
Dim num(1 To n) As Integer, w(1 To n) As Integer
Private Sub Form_Load()
'本過程從數(shù)據(jù)庫中讀入n件物品的編號和重量分別存數(shù)組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．小美在研究自定義貨幣系統(tǒng)，她想知道和自己定義的任意貨幣系統(tǒng)等價，同時面額種數(shù)最少的貨幣系統(tǒng)中有多少種面額。例如，和{3,6,10,19}等價的貨幣系統(tǒng)中，面額種數(shù)最少的是{3,10}，即可用{3,10}表示{3,6,10,19}中的任意數(shù)。
在尋找等價貨幣系統(tǒng)時，小美發(fā)現(xiàn)了如下規(guī)律：（1）、與給定貨幣系統(tǒng)等價的貨幣系統(tǒng)必定是該貨幣系統(tǒng)的子集；（2）、如果貨幣系統(tǒng)中的某個面額可以被其他貨幣表示時，該面額是無效的；為此，小美按照如下方法構(gòu)造最小等價貨幣系統(tǒng)B：先將原貨幣系統(tǒng)A的所有面額升序排序，每次把A中可以被B中的貨幣表示的面額刪去后，將A中的最小面額放入B中。以此類推。基于此方法，小美編寫了如下程序，在文本框Text1中輸入給定的貨幣系統(tǒng)，單擊按鈕Command1后，在標(biāo)簽Label1中輸出與其等價的貨幣系統(tǒng)的最小面額種數(shù)，在標(biāo)簽Label2中輸出該貨幣系統(tǒng)。程序運(yùn)行界面如圖所示。
（1）若給定貨幣系統(tǒng)為{4,6,8,14,22}，則與其等價的面額種數(shù)最少的貨幣系統(tǒng)為 。
（2）按此要求編寫的程序如下，請?jiān)趧澗€處填入合適的代碼。
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
'數(shù)組b(i)用于表示值i能否用已經(jīng)放入新貨幣系統(tǒng)中的面額來表示
'此段程序用于將給定貨幣系統(tǒng)存儲在a數(shù)組中并將其元素個數(shù)存儲在變量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函數(shù)用于將數(shù)值變量轉(zhuǎn)為字符串變量并去除首位空格

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 = "與之等價的最小貨幣系統(tǒng)面額種數(shù)為" + Str(ans)
Label2.Caption = "其為" + s
End Sub
27．某協(xié)會進(jìn)行釣魚比賽，最后有十人進(jìn)入決賽，錄入員編制了如下Visual Basic程序，功能是根據(jù)成績進(jìn)行排序，程序中數(shù)組 a保存所有參賽者的成績，數(shù)組b保存此成績對應(yīng)的姓名，第i位參賽者的成績保存在a(i)中，姓名保存在b(i)中。
程序界面如圖所示，左邊列表框List1中顯示原始數(shù)據(jù)(成績和相應(yīng)的姓名)，單擊“排序”按鈕(Command1)，排序后的結(jié)果按成績從高到低顯示在列表框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(luò)
Next j
If k＜＞i Then
x＝a(i)：a(i)＝a(k)：②________
y＝b(i)：b(i)＝b(k)：b(k)＝y(tǒng)
End If
Next i
For i＝i To 10
List2.AddItem Str(a(i))＋“ ”＋b(i)
Next i
End Sub
Private Sub Form_Load()
’此過程用于對數(shù)組a和數(shù)組b進(jìn)行初始賦值，代碼略
End Sub
(1)解決此問題的算法是________。(選填：冒泡排序或選擇排序)
在程序①和②畫線處，填入適當(dāng)?shù)恼Z句或表達(dá)式，把程序補(bǔ)充完整：
(2)程序中①畫線處應(yīng)填入________。
程序中②畫線處應(yīng)填入________。
28．小王利用循環(huán)排序思想編寫了一個VB程序，用于計(jì)算下一輪比賽的出場順序。從數(shù)據(jù)庫中讀取本輪比賽的人員姓名存在數(shù)組xm中，成績存在數(shù)組cj中（成績均不重復(fù)）。編程實(shí)現(xiàn)將這些成績進(jìn)行循環(huán)升序排列。要求最低成績的位置不變，然后依次進(jìn)行升序排序，即從最小值開始向下尾首相連形成升序數(shù)列。程序運(yùn)行界面如圖所示。點(diǎn)擊“排序”按鈕，完成循環(huán)升序排序。
（1）“排序”按鈕的對象名為_
（2）請?jiān)趧澗€處填入合適代碼。
（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（ ）
'從數(shù)據(jù)庫中讀取數(shù)據(jù)，存儲到相應(yīng)數(shù)組中，并輸出在列表框Listl。第i個人，姓名為xm（i），成績?yōu)閏j（i）。人員數(shù)量存儲到變量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．程序設(shè)計(jì)：在舞會上，男生、女生各自排成一隊(duì)。舞會開始時，依次從男隊(duì)和女隊(duì)的隊(duì)頭各出一人配成舞伴。跳完后的兩人重新回到隊(duì)尾。
例如：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＝ ① #出隊(duì)
print(“Turn{:2}):({}，{})".format(i＋1,x，y))
boy.append( ② ) #再進(jìn)隊(duì)
girl.append( ③ ) #再進(jìn)隊(duì)
（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．中點(diǎn) 縮小
17．輾轉(zhuǎn)法 重復(fù) 結(jié)果 初始值
18．A-L-K-H-G-B 或 A-L-K-J-I-B 12
19．遞推關(guān)系 邊界條 有限 無限循環(huán)
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

展開更多......

收起↑