資源簡介

粵教版 選修1 第五章 數據結構的應用 單元練習
學校:___________姓名：___________班級：___________考號：___________
一、選擇題
1．有如下程序段：
a=[92,22,11,98,96,71]
n=len(a)
for i in range(n):
for j in range( ):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
print(a)
為實現n個數的升序排序，則劃線處應填（ ）
A．range(i-1) B．range(n-2,i-1,-1)
C．range(i,n) D．range(n-1,n-i-2,-1)
2．有如下程序：
a=[6,1,5,7,4,8,3,2]
for i in range(7):
k,f=i,(-1)**i
for j in range(i,8):
if a[j]*f>a[k]*f:
k=j
if i!=k:
a[i],a[k]=a[k],a[i]
該程序運行后，輸出的a結果為( )
A．[1,6,5,7,4,8,3,2] B．[1,8,2,7,3,6,4,5]
C．[8,1,5,7,4,6,3,2] D．[8,1,7,2,6,3,5,4]
3．對“842715”中的數字進行選擇排序中的兩遍加工，即為某密碼鎖的密碼，該密碼可能是（ ）。
A．124785 B．142785 C．842715 D．875412
4．二分查找算法利用的算法思想是（ ）
A．分治策略 B．窮舉法 C．回溯法 D．遞歸法
5．有如下對分查找程序段
#列表a存放整數升序數據，代碼略
key=int(input())
f=[0]*9
i=0
j=8
while i<=j:
m=(i+j)//2
f[m]=1
if a[m]>key:
j=m-1
else:
i=m+1
print(f)
輸入待查找數據，執行該程序段后，下列選項中，列表f的值不可能的是（ ）
A．[0, 0, 0, 0, 1, 1, 1, 0, 0] B．[1, 1, 0, 0, 1, 0, 0, 0, 0]
C．[0, 1, 0, 0, 1, 0, 1, 0, 0] D．[0, 0, 0, 0, 1, 0, 1, 1, 0]
6．運行以下Python程序段，結果是（ ）
A．Python B．C++ C．Welcome D．True
7．某對分查找算法如下：
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
8．某食品連鎖店5位顧客貴賓消費卡的積分依次為900、512、613、700、810，若采用選擇排序算法對其進行從小到大排序，如下表，第二趟的排序結果是（ ）。
原始數據 900 512 613 700 810
第一趟 512 900 613 700 810
第二趟
第三趟 512 613 700 900 810
第四趟 512 613 700 810 900
A．512 613 700 900 810
B．512 810 613 900 700
C．512 900 613 700 810
D．512 613 900 700 810
9．一個序列經過一趟冒泡排序后的結果是：10，21，13，24，28，則原始序列不可能是（ ）
A．21，13，24，28，10 B．21，10，24，28，13 C．21，10，24，13，28 D．21，24，13，28，10
10．下列選項中，遞歸算法不一定包括的是（ ）
A．遞推部分 B．回歸部分 C．終止條件 D．循環結構
11．斐波那契在《計算之書》中提出了一個有趣的兔子問題:從第三個月開始，每個月的兔子對數是前兩個月的兔子對數之和，又同時作為下一個月兔子對數的加數。這種重復反饋的過程稱為迭代。迭代法也稱輾轉法，閱讀下列程序代碼。
def fib(n):
#迭代求Fibonacci數列
f2=f1=1
for i in range(①，n+1):
②
return f2
n=int(input('輸入需要計算的月份數：'))
print('兔子總對數為：'，fib(n))
input("運行完畢，請按回車鍵退出...")
下列說法錯誤的是（ ）
A．確定迭代變量， 程序中的的f1、f2
B．建立迭代關系式，②處應填寫：f1，f2=f2，f1+f2
C．對迭代過程進行控制，①處應填寫range(3，n+1)枚舉從第三個月開始
D．f1，f2=f2，f1+f2不可以用temp=f1+f2，f1=f2，f2=temp代替
12．下列程序是用二分法從給定的有序數中查找并打印指定數的位置的代碼。
def search(x，nums):
low = 0
heigh = len(nums)-1
while low <=heigh:
mid = ①
if x == nums[mid]:
return mid
elif x > nums[mid]:
low = ②
else:
heigh =③
return -1
nums =[2，4，8，9，10，20，30，77，88，100]
num = int(input("請輸入你要查找的數:"))
print("你要找的數在數組從0開始的第"，search(num，nums)，"個位置")
下列說法正確的是（ ）
A．①的位置為(low+heigh)//2，②的位置為mid-1，③的位置為mid+1
B．①的位置為(low+heigh)//2，②的位置為mid+1，③的位置為mid-1
C．①的位置為(low+heigh)/2，②的位置為mid-1，③的位置為mid+1
D．①的位置為(low+heigh)/2， ②的位置為mid+1，③的位置為mid-1
13．二分查找實際上就是（ ）的一種典型運用。
A．動態規劃法 B．分治策略 C．回溯法 D．遞推法
14．某同學在做物理實驗時，需要用天平測量物品的質量，過程如下：先放置200克砝碼，若砝碼偏重；再將砝碼改為100克,若砝碼偏輕；再將砝碼改為150克，砝碼偏重；再將砝碼改為125克……以此類推。通過這種策略，該同學完成了物品的稱重。此過程借鑒的算法思想是( )
A．排序 B．二分查找 C．順序查找 D．枚舉
15．小華玩猜價格游戲，已知價格的范圍在 1 元到 200 元之間。他第一次猜 100 元，太低；第二次猜 150元，太高；第三次猜 125 元，又太低；……，小明在猜價格時采用的方法是（ ）。
A．順序查找 B．隨機查找 C．對分查找 D．排序查找
16．在漢諾塔問題中，現要將塔座A上的8個圓盤全部移到塔座B上，并仍按同樣順序疊放。移動圓盤時，需遵守漢諾塔問題的移動規則。由此，可設計出解漢諾塔問題的遞歸算法為（ ）。
A．def hanoi(n,A,C,B):
if n>0:hanoi(n-1,A,B, C)
print(n,A,"->”,B)
hanoi(n-1,C,A,B)
hanoi (8,A,C,B)
B．def hanoi(n,A,B,C):
if n>0:hanoi(n-1,A,B,C)
print(n, A,"->" ,B)
hanoi(n-1,C,A,B)
hanoi (8, A,B,C)
C．def hanoi (n,C,B,A):
if n>0:hanoi(n-1,A,C,B)
print(n, A,"->”，B)
hanoi(n-1,C,B,A)
hanoi (8, C, B,A)
D．def hanoi(n,A,C,B):
if n>0:hanoi (n-1,A,C,B)
print(n, A,"->,B)
hanoi(n-1,C,B, A)
hanoi(8,C,A,B)
17．斐波那契數列，運用函數遞歸的方法可以實現，運用迭代的方式也可以實現，而且比函數遞歸要快許多。下列關于斐波那契數列的迭代表達式正確的是（ ）。
A．f，f2，f2=f1+f2 B．fl=fl+f2，f2=
C．fl，f2=f2，fl+f2 D．f=f1+f2，fl=f2，f2=f
18．小明和小華玩猜數字的游戲，所猜數字不超過800，小明首先猜400，小華說大了，小明又猜200，當小華再次說大了，小明猜100，當小華說小了，小明猜150，以此類推，直到猜到正確的數字。上述方法中蘊含的算法思想是（ ）
A．窮舉算法 B．遞歸算法 C．二分查找法 D．順序查找法
19．（ ）是重復反饋過程的活動，其目的通常是逼近所需目標或結果。（）是直接或間接地調用函數自身。
A．枚舉 遞歸 B．遞歸 迭代 C．迭代 遞歸 D．遞歸 迭代
20．（ ）是重復反饋過程的活動，其目的通常是逼近所需目標或結果。是直接或間接地調用函數自身。
A．舉遞歸 B．遞歸代 C．迭代遞歸 D．遞歸迭代
21．以下程序代碼采用的算法是( )。
def gcd(m，n)：
while m%n != 0：
m，n=n，m%n
return n
a=int(input("請輸入a的值："))
b=int(input("請輸入b的值："))
print(gcd(a，b))
A．枚舉法 B．二分法 C．遞歸法 D．迭代法
22．采用冒泡排序算法對數據序列“4，9，8，2，6，3”完成升序排序，則需要交換的次數為（ ）
A．9 B．10 C．11 D．12
23．使用冒泡排序算法對序列6,10,7,4,9進行升序排序，則排序過程中總交換次數為（ ）
A．5 B．6 C．7 D．8
24．某二分查找算法的Python程序段如下：
list1=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","Tomato"]
key＝list1[2]
left，right＝0，len(list1)－1
c＝0
while left<＝right：
m＝(left＋right)//2
c＝c＋1
if list1[m]>key：
right＝m－1
else：
left＝m＋1
print(list1[left])
程序執行后，下列說法正確的是(　　)
A．變量c的值為4 B．程序輸出的結果為Lettuce
C．變量left的值為2 D．變量right的值為3
25．現有三個整數序列：“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
試卷第1頁，共3頁
試卷第1頁，共3頁
參考答案：
1．B
【詳解】本題主要考查冒泡排序算法。分析程序，外層循環變量i的范圍是0~n-1，該程序實現升序排序，比較的是索引j與j+1，內層循環可以從左往右比較每次將一個最大值放到最右邊，代碼為range(n-i-1)；也可以從右往左比較交換，每次將一個最小值放到最左邊從而實現升序排序，代碼為range(n-2,i-1,-1)，故本題選B選項。
2．D
【詳解】本題主要考查排序算法及Python程序實現。分析程序可知，該程序實現奇數位呈降序排序，偶數位呈升序排序，每次循環，當i是偶數時，則將剩余數中最大值移到左邊i處；當i是奇數時，將剩余數中最小值移到左邊i處從而實現排序。故該程序運行后，輸出的a結果為[8,1,7,2,6,3,5,4]，故本題選D選項。
3．A
【詳解】本題考查的是選擇排序。它的工作原理是每一次從待排序的數據元素中選出最小(或最大)的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。如果從左到右，按從大到小來選擇排序，兩遍加工后為：872415；如果從左到右，按從小到大來選擇排序，兩遍加工后為：124785；如果從右到左，按從大到小來選擇排序，兩遍加工后為：542178；如果從右到左，按從小到大來選擇排序，兩遍加工后為：845721；故本題應選A。
4．A
【詳解】本題主要考查二分查找算法。分治策略是對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個 規模 較小的子問題，這些子問題互相獨立且與原問題形式相同， 遞歸 地解這些子問題，然后將各子問題的解合并得到原問題的解。二分查找算法利用的算法思想是分治策略，故本題選A選項。
5．C
【詳解】本題主要考查對分查找算法。變量m是依次查找的下標索引值，第一次循環，m=4，f[4]=1，根據二叉樹查找規則，往后查找只會在m=4的左邊或右邊進行查找，不會出現選項C中f[1]和f[6]同時為1的情況，故本題選C選項。
6．B
【詳解】本題考查的是Python選擇語句。name的值為“C++”不為“Python”，故執行else分支的print語句，故輸出C++，選項B正確。
7．B
【詳解】本題主要考查對分查找。此題需要畫出二叉樹。數組為遞增的有序數列，根據算法要求有可能出現i=j+1，因此A選項正確；key=21時，發生指針跳轉，因此B選項符合題意；key=32時，m=3，i=m+1，然后m=5，j=m-1，然后m=4，m=j成立，因此C選項正確；key=38時，根據算法要求，查找失敗，且m=4，因此D選項正確。
【點睛】
8．D
【詳解】本題主要考查冒泡排序算法。第一趟是比較900和512，第二趟比較900和613，并交換順序實現升序排序，故第二趟的排序結果是512 613 900 700 810，故本題選D選項。
9．D
【詳解】本題主要考查冒泡排序。選項A、B、C自右向左比較，將最小值交換到最左邊，經過一趟冒泡排序后的結果是：10，21，13，24，28；選項D無論自左向右還是自右向左比較，均無法得到該結果，故本題選D選項。
10．D
【詳解】本題主要考查遞歸算法。遞歸算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸算法一定包括遞推部分、回歸部分以及終止條件，循環結構可能有也可能沒有，故本題選D選項。
11．D
【詳解】本題主要考查迭代算法及Python程序實現。從第三個月開始，每個月的兔子對數是前兩個月的兔子對數之和，又同時作為下一個月兔子對數的加數，故確定迭代變量， 程序中的的f1、f2；建立迭代關系式，②處應填寫：f1，f2=f2，f1+f2；對迭代過程進行控制，①處應填寫range(3，n+1)枚舉從第三個月開始；f1，f2=f2，f1+f2可以用temp=f1+f2，f1=f2，f2=temp代替，故本題選D選項。
12．B
【詳解】本題主要考查二分查找及Python程序實現。二分查找中間的位置mid=(low+heigh)//2，當x大于該位置的值，則說明要查找的值在mid的右邊，需要更新low的值為mid+1，否則更新heigh的值為mid-1，故①的位置為(low+heigh)//2， ②的位置為mid+1，③的位置為mid-1，故本題選B選項。
13．B
【詳解】本題主要考查二分查找算法。二分查找實際上就是分治策略的一種典型運用，所謂分治策略，就是把規模大的問題分成若干個規模小的問題來解決，最后把各自的結果再合并，故本題選B選項。
14．B
【詳解】本題主要考查二分查找算法。二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果xa[n/2],則只要在數組a的右半部搜索x，由題干可知，此過程借鑒的算法思想是二分查找，故本題選B選項。
15．C
【詳解】本題考查的是查找算法。對分查找首先將查找鍵與有序數組內處于中間位置的元素進行比較，如果中間位置上的元素內的數值與查找鍵不同，根據數組元素的有序性，就可確定應該在數組的前半部分還是后半部分繼續進行查找;在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。故本題應選C。
16．A
【詳解】本題主要考查遞歸算法及Python程序實現。要將塔座A上的8個圓盤全部移到塔座B上，并仍按同樣順序疊放。移動圓盤時，需遵守漢諾塔問題的移動規則。遞歸思想是首先將前n-1個圓盤遞歸從A塔座通過B塔座放到C塔座上，即hanoi(n-1,A,B, C)。其次將最后一個盤n放到B盤上，即print(n,A,"->”,B)。最后將n-1個圓盤遞歸從C塔座通過A塔座放到B塔座上，即hanoi(n-1,C,A,B)。將塔座A上的8個圓盤全部移到塔座B上，即借助C塔座，語句是hanoi (8,A,C,B)，故本題選A選項。
17．D
【詳解】本題主要考查迭代與遞歸算法。斐波那契數列指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義： F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)（ n ≥ 2， n ∈ N*）。所以關于斐波那契數列的迭代表達式正確的是f=f1+f2，fl=f2，f2=f，故本題選D選項。
18．C
【詳解】本題主要考查二分查找算法。二分查找(Binary Search)算法，也叫折半查找算法。二分查找的思想非常簡單，有點類似分治的思想。二分查找針對的是一個有序的數據集合，每次都通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0。分析題干可知，上述方法中蘊含的算法思想是二分查找法，故本題選C選項。
19．C
【詳解】本題主要考查迭代和遞歸算法。迭代是重復反饋過程的活動，其目的通常是逼近所需目標或結果。遞歸是直接或間接地調用函數自身，故本題選C選項。
20．C
【詳解】本題主要考查迭代與遞歸算法。迭代是重復反饋過程的活動，其目的通常是逼近所需目標或結果。遞歸是直接或間接地調用函數自身，故本題選C選項。
21．D
【詳解】本題主要考查迭代算法。迭代法是用計算機解決問題的一種基本方法，它讓計算機對一組指令或一定步驟進行重復執行，在每次執行這組指令或這些步驟是都從變量的原值推出他的一個新值，用迭代法解決問題，要考慮迭代的初值、迭代的過程、迭代的結束或迭代的次數。簡單地說就是運算過程中的變量的不斷交替，分析程序可知，輾轉相除法求最大公約數采用的算法是迭代法，故本題選D選項。
22．B
【詳解】本題主要考查冒泡排序算法。第一遍排序，9和8、9和2、9和6、9和3需要交換，排序后數據序列分別是4、8、2、6、3、9；第二遍循環，8和2、8和6、8和3需要交換，排序后數據序列分別是4、2、6、3、8、9；第三遍循環，2和4、6和3需要交換，排序后數據序列分別是2、4、3、6、8、9；第四遍循環，3和4需要交換，排序后數據序列分別是2、3、4、6、8、9，數據已有序，故需要交換的次數為4+3+2+1=10次，故本題選B選項。
23．A
【詳解】本題主要考查冒泡排序算法。第一遍，10分別與7、4、9進行交換，序列變為6,7,4,9,10；第二遍，7與4進行交換，序列變為6,4,7,9,10；第三遍，6與4交換，序列變為4,6,7,9,10，此時序列已有序，總交換次數為5次，故本題選A選項。
24．B
【詳解】本題主要考查二分查找算法及Python程序實現。已知left=0，right=7，key="Garlleftc"，第一次查找m=(left+right) //2=3，c=c+1=1，a (3) ="Lettuce"，判斷list1[m] > key成立，執行right=m-1=2；第二次查找m= (left+right) //2=1， c=c+1=2， a (2)= "Garlleftc"，判斷list1[m] > key不成立，執行left=m+1=2；第三次查找m= (left+right) //2=2，c=c+1=3，a (2) ="Garlleftc"，判斷list1[m] > key不成立，執行left=m+1=3；此時left=3，right=2不在滿足循環條件，輸出list1[3]= "Lettuce"，c的值為3，left=3，right=2，故本題選B選項。
25．A
【詳解】本題考查的是選擇排序。根據選擇排序思想可知，不管數據是否已經有序，部分有序或是無序，選擇排序還是要把每個數據都比較過去，最后選擇出一個最小的數據（題目為升序），若選擇出的這個最小數據本身位置不在第一個位置則進行交換，然后再剩下的數據中繼續找到第二個小的數同樣，如果不是本身自己第二個位置的數，則交換，依次類推，其總的比較次數為n*（n﹣1）/2次，由于三組數列中均為五個元素，故x＝y＝z故選：A。
答案第1頁，共2頁
答案第1頁，共2頁

展開更多......

收起↑