資源簡介

數據與數據結構 綜合檢測
一、選擇題
1．有如下Python程序段：
import random
lst=['A'，'B'，'C'，'D']
st=[0]*len（lst）
i，top=0，-1
while i k=random.randint（0，1）
if k==0：
top+=1
st[top]=lst[i]
i+=1
elif top!=-1：
lst[i]=st[top]
top-=1
執行該程序段后，lst的值不可能是（ ）
A．['A'，'B'，'C'，'D'] B．['A'，'B'，'A'，'C'] C．['A'，'A'，'C'，'D'] D．['A'，'A'，'C'，'A']
2．有如下自定義函數：
def fg（n）：
if n<=2：
return n
else：
return fg（n-1）+fg（n-2）
執行語句s=fg（4），下列說法不正確的是（ ）
A．s的值為5 B．函數fg被調用的次數是4
C．第二次被調用的函數是fg（3） D．該程序采用了遞歸算法
3．一條狹長的管道內有3個物體，每個物體可向左或向右移動，也可停在緩沖帶上（最多停一個）。經過多次移動，物體狀態從a變成c，其中b為移動中某次狀態，如圖所示，則移動過程中所有物體經過T點的最少總次數是（ ）
A．8 B．7 C．5 D．3
4．下列二叉樹中，前序和中序遍歷結果一樣的選項是（ ）
A． B． C． D．
5．設棧S初始狀態為空，元素A、B、C、D、E、F依次入棧，出棧的序列為D、F、E、C、B、A，則棧S的容量至少應該是（ ）
A．5 B．4 C．3 D．2
6．某二叉樹前序遍歷為ABDFGCEH，后序遍歷為FGDBHECA，則下列選項不可能是此二叉樹的是（ ）
A． B． C． D．
7．有如下Python程序：
def fun(x,n):
if x == n:
return 1
if n % x == 0:
return fun(x,n//x)+1
else:
return fun(x+1,n)
print(fun(2,100))
執行上述程序后，輸出的結果是（ ）
A．2 B．3 C．4 D．5
8．有如下Python程序段：
a = [1,2,3,4,5];b = [3,2,5,1,4]
stack =[];i = j = 0
while i < len(a):
stack.append(a[i])#將a[i]添加到stack末尾
i += 1
while len(stack)>0 and stack[-1] == b[j]:
stack.pop()#移除stack末尾元素
j +=1
執行該程序段后，stack中的元素個數為（ ）
A．0 B．1 C．2 D．3
9．某二叉樹對應的一維數組表示如下圖所示：
下列關于該二叉樹的說法正確的是（ ）
A．這是一棵完全二叉樹 B．節點F是節點D的孩子節點
C．該二叉樹有1個葉子結點 D．該二叉樹中序遍歷的結果是DBEACF
10．某二叉樹的樹形結構如下圖所示，后序遍歷結果為“WUSVTR”，則該二叉樹的前序遍歷結果為（ ）
A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV
11．若有一批元素的出棧順序為“i, n, p, u, t”，其入棧順序不可能是（ ）
A．n, i, t, u, p B．n, i, u, t, p C．t, u, p, n, i D．i, n, p, u, t
12．諸葛亮家族的部分家譜如圖所示。和家譜圖結構相似的數據結構是（ ）
A．樹 B．棧 C．隊列 D．鏈表
13．用一帶蓋的玻璃筒來放取乒乓球，放、取球只能在帶蓋的一端進行（另一端為封閉狀態），且筒的直徑只允許一個乒乓球進出。若放入球的編號序列為1、2、3、4，則取出球的編號序列不可能的是（ ）
A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4
14．利用棧求逆波蘭表達式（表達式由操作數和運算符組成）的方法是:從左往右掃描該表達式，遇到操作數時入棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復操作，直至表達式掃描結束。當用該算法求逆波蘭表達式abcd-*e/+f-的值時（abcdef表示不同的操作數），所使用的棧的深度至少為（ ）
A．3 B．4 C．5 D．6
15．下列二叉樹中，后序遍歷結果不為CBFEAD的是（ ）
A． B． C．D．
16．已知x="123"，y="456"，則表達式x+y 的值為（ ）
A．"123456" B．"567" C．"123"+"456" D．"579"
17．斐波那契數列也叫兔子繁殖數列，小明編寫了下列代碼求第74個月能繁殖多少對兔子，他使用的算法是（ ）
A．解析法
B．迭代法
C．枚舉法
D．二分法
18．有如下程序段：
def cal(n):
if n <= 1:
return 1
if n % 2 == 0:
return 2*cal(n-1)
return 1+cal(n-1)
執行語句k=cal(5)，則k的值為（ ）
A．6 B．7 C．10 D．11
19．下列有關迭代算法和遞歸算法的描述，不正確的是（ ）
A．在使用遞歸算法時，必須有一個明確的遞歸結束條件，稱為遞歸出口
B．一般來說，迭代算法效率較低，而遞歸算法效率較高
C．遞歸中一定有迭代，但迭代中不一定有遞歸
D．通常情況下，迭代算法和遞歸算法可以相互轉換
20．某二叉樹的樹形結構如圖所示，其后序遍歷結果為FABGDEC，則中序遍歷結果為（ ）
A．FDAGBCE B．FDABGEC
C．AGBDFCE D．FDAGBEC
二、填空題
21．Python 表達式int (2.5)的值為 。
22．def f(x,y):
ans=y;
for i in range(1,y-x+1):
ans = ans + f(x+i,y-i)
return ans;
def init():
x = int(input())
y = int(input())
print(f(x,y))
init()
(1)
輸入：4
5
輸出：
(2)
輸入：3
6
輸出：
23．有如下Python程序段：
import random
n=6
a=[9,4,3,4,7,6]
for i in range(n-1,0,-1):
for j in range(0,i):
if a[i] < a[j]:
a[i],a[j]=a[j],a[i]
print(a)
排序后，數組a=
24．下面程序輸出結果是( )
S=0
For i in range(1,5):
S=S+20
print(“S=”,S,end=”\n”)
25．已知 x = [3, 5, 7] ，那么執行語句 x[1:] = [2] 之后，x 的值為 。
三、判斷題
26．在程序語言中都規定了運算符的優先級，通常是算術運算符高于關系運算符，關系運算符高于邏輯運算符，在一個表達式中無法通過其他手段改變運算順序。( )
27．算術運算符中*、/的運算優先級高于//和%。( )
28．Python語言的表達式中，“%”是取模算術運算符。( )
29．如果變量a=5，那么表達式10>a and a<3的結果為False。( )
30．在 Python語言環境下，表達式13%2+7//2的值為4.5。 ( )
四、操作題
31．檢查數學表達式中的括號是否配對是計算機進行數學計算的重要環節。括號序列“（）（）”中的“（”與“）”是配對的，而序列“（））（”中的括號則是不配對的。對于不配對的序列，可以將“（”修改為“）”,或者將“）”修改為“（”來實現配對。如圖所示是括號序列“（））（（）”通過不同的修改方案使其配對所需要的修改次數，最少修改次數為2。
請回答下列問題：
（1）若括號序列為“（））））（））”，最少需要修改 次才能使得括號序列中的括號配對。
（2）編寫程序，計算修改括號序列使其配對的最少次數。部分Python程序如下，請在劃線處填入合適的代碼。
s=input（）#輸入括號序列，序列中僅包含“（”、“）”兩種字符，且長度為偶數
x=0
ans=0
for i in range（len（s））:
if s[i]=='（':
①
elif s[i]=='）'and x>=1:
x-=1
elif s[i]=='）'and② :
ans+=1;x+=1;
ans+=③
print（ans）
32．某奶茶店收到了n杯奶茶的訂單，這n杯奶茶分別經過甲、乙兩個工序加工，并且必須先在甲工序加工后才可以進行乙工序。為了使得總加工時間最短，我們可以將這n杯奶茶分為兩類：
第一類：甲工序的加工時長少于乙工序的加工時長。
第二類：甲工序的加工時長不少于乙工序的加工時長。
第一類應將在甲工序花費時間少的產品排在前面，第二類應將在乙工序花費時間少的產品排在后面，然后先處理所有第一類產品，再處理第二類產品。可以證明，這樣排序后所有奶茶加工完成花費的總時間最少。
如：有4杯奶茶的訂單，它們在甲工序的加工時長分別為2、3、5、1，在乙工序的加工時長分別為3、1、2、5，將奶茶分類、排序、合并、計算時長的過程如圖所示，最后得出總時長為12。(每杯奶茶在乙工序開始加工需同時滿足它甲工序加工完并且乙工序已加工完上一個產品這兩個條件)
編寫程序模擬奶茶店對這n杯奶茶的處理過程，計算總加工時間。
請回答下列問題:
（1）由題意可知，若3杯奶茶在甲工序加工時長分別為3、1、3，乙工序加工時長分別為2、4、3，則總加工時長為 。
（2）小李先編寫了如下將第一類產品排序的函數:
def order1(a,b): #參數a、b的元素分別表示每杯奶茶在甲乙兩道工序的加工時長。
ans=[0]*100
idx=[0]*100
tmp1=[];tmp2=[]
for i in range(len(a)):
①
idx[a[i]]=b[i] #原始序號排序后會跑到第b[i]位置上
for i in range(len(ans)):
while ans[i]>0:
②
tmp2.append(idx[i])
ans[i]-=1
return tmp1,tmp2
請在劃線處填入合適的代碼。
（3）小方編寫了將第二類產品排序的函數:
def order2(a,b): #參數a、b的元素分別表示每杯奶茶在甲乙兩道工序的加工時長。
#代碼略
小張結合前兩位同學的程序，計算產品加工總時長。請在劃線處填入合適的代碼。讀取n杯奶茶在甲乙兩道工序加工的時間，根據題目要求分為兩類，第一類在甲乙兩道工序加工的時間分別存儲在列表a1和列表b1中,并通過order1()函數排序，第二類在甲乙兩道工序加工的時間分別存儲在列表a2和列表b2中,并通過order2()函數排序，代碼略。
‘’’#代碼略
a=a1+a2
b=b1+b2
n= len(a)
ta,tb=0,0 #ta為甲加工時間，tb為乙加工時間
for i in range (n) :
ta+=a[i]
if ① :
tb=ta
②
print("總加工時長最短為:",tb)
33．小強學習過大數據的“分治”思想后，對經“分治”處理后的數據合并產生了興趣。他設計了一個算法，對兩個升序列表a、b中的數據(均為正整數)進行合并，合并后的數據仍保持升序。
（1）為了生成長度為num 的升序列表x，小強寫了如下代碼。
import random
def mk(num) ：
x= [0]*num #創建列表 x= [0，0，……，0]，其中 0 的個數是 num
x[0]=random.randint(5，10) #randint(a，b)返回[a，b]區間內的一個隨機整數
for i in range(1，num) ：
return x
m=n=5
a=mk(m)
b=mk(n)
print("原始數據序列 a 為："，a)
print("原始數據序列 b 為："，b)
①使用語句 a= mk(5)調用函數，加框處語句的執行次數是 (填寫阿拉伯數字) 。
②執行上述代碼后，關于輸出的列表a、b 中的數據，下列說法正確的是 (單選，填字母： A .相同 / B .不相同 / C .可能相同)
（2）為了描述方便，假設兩個列表中的元素個數m=n=5，其初始狀態如下：
b[0] b[1] b[2] b[3] b[4]
10 11 15 16 17
為了使合并后的數據保存在列表a 中，現對列表 a 擴充 n 個元素“-1”，擴充后狀態如下：
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
7 9 10 14 19 -1 -1 -1 -1 -1
變量i賦值為0，指向列表b的首數據，變量p賦值為0，指向列表a的首數據，變量tot指向列表a的最后一個有效數據(如圖所示) 。
合并的具體算法如下：
Ⅰ.如果 a [p]= – 1 ，則直接將 b[i]存儲到 a [p]中，同時 tot 值增加 1；
Ⅱ.如果 a [p]>b[i] ，則整體將 a [p] ，… ，a [tot]向右移動一個位置，然后將 b[i]存儲到空出的位置， 同時 tot 值增加 1。
Ⅲ. p 值增加 1；
小強編寫的合并代碼如下，請在劃線處填入合適代碼。
#將列表a 的數據個數存入m，列表b 的數據個數存入 n，代碼略
#對列表 a 擴充 n 個-1，代碼略
p=0
tot=
i=0
while ： #將列表b 中元素 b[i]逐個插入到列表 a 中
if a[p]==-1 ：
a[p]=b[i]
tot+=1
i+=1
elif a[p]>b[i] ：
for j in range(tot，p-1，-1)： #整體將 a[p]， … ，a[tot]向右移動一個位置
a[j+1]=a[j]
tot+=1
i+=1
p+=1
print("合并后的數據序列為："，a)
34．有五位同學參加了植樹活動，他們完成植樹的棵數都不相同。問第一位同學植了多少棵時，他指著旁邊的第二位同學說比他多植了兩棵；追問第二位同學，他又說比第三位同學多植了兩棵；如此追問，都說比另一位同學多植兩棵，最后問到第五位同學時，他說自己植了10棵。問第一位同學植了多少棵樹？以下代碼是求第一位同學植樹數量的代碼，請你補全程序。
def f(n):
if n == 5:
return ___①___
else:
return _____②____
print(___③___)
（1）程序代碼中①處的代碼是( )
A．1 B．2 C．10 D．18
（2）程序代碼中②處的代碼是( )
A．f(n)-2 B．f(5)+2 C． f(n-1)+2 D．f(n+1)+2
（3）程序代碼中③處的代碼是( )
A．f(n) B．f(1) C． f(5) D．5
35．利用歐幾里得輾轉相除法求兩數最大公約數
def gcd（m，n）：
if ：
return n
else：
r=m%n
return
a=int（input（'請輸入第一個正整數："））
b=int（input（'請輸入第二個正整數：））
print( )
（1）A．m//n==0 B．m//n！=0 C．m%n==0 D．m%n！=0
（2）A．gcd（m，n） B．gcd（m，r） C．Gcd（n，r） D．gcd（n，r）
參考答案：
1．B
2．B
3．C
4．D
5．A
6．B
7．C
8．C
9．D
10．D
11．B
12．A
13．C
14．B
15．D
16．A
17．B
18．B
19．B
20．A
21．2
22． 9 22
23．[3, 4, 4, 6, 7, 9]
24．S=20
S=40
S=60
S=80
25．[3,2]
26．錯誤
27．錯誤
28．正確
29．正確
30．錯誤
31． 2 x+=1 或x=x+1 x==0 x//2
32． 10 ans[a[i]]+=1 tmp1.append(i) tb33． 4 C m-1 或其它等價答案 i34． C D B
35． C D gcd(a,b)

展開更多......

收起↑