資源簡介

中小學教育資源及組卷應用平臺
第五單元練習及參考答案
1. 請采用不同的排序方法對序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的數據元素按字母序的升序進行排序，編程并上機調試，說說你采用的數據結構和理由。
_______________________________________________________________________________________
2.已知某企業生產部門員工的工齡記錄為(5,3,10,8,7,14,15,12,18,16,25,17)(按工號的順序排列)，現要找出工齡為25年的員工。
(1)使用順序查找法完成。
_______________________________________________________________________________________ _______________________________________________________________________________________ _______________________________________________________________________________________ _______________________________________________________________________________________ (2)使用索引查找法完成。
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
(3)對記錄進行排序后用二分查找法完成。
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
3.假設有3個分別命名為A、B和C的柱子，在柱A上插有n個直徑大小各不相同，從上到下，以從小到大順序排列的編號分別為1,2..的圓盤，(如圖5-18A,圖中n=4)。現要求將A柱上的n個圓盤移至C柱上并仍按同樣的順序疊排，且圓盤移動時必須遵循下列規則：
(1)每次只能移動一個圓盤
(2)圓盤可以插在A、B和C中的任一柱上。
(3)任何時刻都不能將一個大的圓盤壓在小的圓盤之上。
可參照以下解法：
2 用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上；
②將A柱上最后一個盤子直接移到C柱上；
③用A柱做過渡，將B柱上的(n-1)個盤子移到C柱上。
請使用遞歸法編寫程序
______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
參考答案：
冒泡排序。
r=['Q’,’H’,'C',’Y’,'P','A','M',’S’,R','D','F’,'X']
i=0
while i<11:
j=11
while j>=1:
if r[j]temp=r[j]
r[j]=r[j-1]
r[j-1]=temp
j=j-1
i=i+1
for e in r:
print(e)
插人排序
r=['Q','H',’C','Y’,'P','A','M','S’,'R','D','F','X']
i=1
while i<12:
temp=r[i]
j=i-1
while temp=0:
r[j+1]=r[j]
j=j-1
r[j+1]=temp
i=i+1
for e in r:
print(e)
選擇排序
r=['Q',’H','C’,'Y','P’,'A','M','S','R','D','F','X']
i=0
while i<11:
min=i
j=i+1
while j<=11:
if r[j]min=j
j=j+1
if i!=min:
temp=r[i]
r[i]=r[min]
r[min]=temp
i=i+1
for e in r:
print(e)
分析：
數據結構采用順序存儲結構，Python可使用列表實現。列表使用下標表示元素間的先后邏輯關系，算法實現比較簡單。
(2)已知某企業生產部門員工的工齡記錄為(5,3,10,8,7,14,15,12,18,16,25,17)(按工號的順序排列)，現要找出工齡為25年的員工。
①使用順序查找法完成
②使用索引查找法完成
③對記錄進行排序后用二分查找法完成
參考答案
①順序查找法。
r=[-1,5,3,10,8,7,14,15,12,18,16,25,17]
key=25 #key為待查找數據
i=12
while i>=0andr[i]！=key:
i=i-1
print(i)
#輸出為待查找數據在列表中的下標
②索引查找法。
r=[-1,5,3,10,8,7,14,15,12,18,16,25,17]
index=[10,0,15,5,25,8]
key=25 #key為待查找數據
i=0
while key>index[i] and i<=2:
i=i+2
if key>index[i]：
print(-1)
else:
j=i+1
while key!=r[j] and r[j]<=index[i] and j<=11:
j=j+1
if key==r[j]：
print(j)
else:
print(-1)
③二分查找法。
r=[5,3,10,8,7,14,15,12,18,16,25,17]
i=1
while i<12:
temp=r[i]
j=i-1
while temp=0:
r[j+1]=r[j]
j=j-1
r[j+1]=temp
i=i+1
k=25
low=0
high=11
while low<=high:
mid=int((low+high)/2)
if k!=r[mid]：
if k>r[mid]：
low=mid+1
else:
high=mid-1
else:
break
if low>high:
print(-1)
else:
print(mid)
#輸出為待查找數據在排序后列表中的下標
(3)假設有3個分別命名為A,B和C的柱子，在桂A上插有幾個直徑大小各不相同，從上到下，以從小到大順序排列的編號分別為1.2.....的圓盤(如敦材圖5-18A所示，圖中n=4)。現要求將A柱上的n個圓盤移至C桂上并仍按同樣的順序疊排，且圓盤移動時必須遵循下列規則：
每次只能移動一個圓盤。
圓盤可以插在A,B和C中的任一柱上。
任何時刻都不能將一個大的圓盤壓在小的圓盤之上。
可參照以下解法：
①用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上；
②將A柱上最后一個盤子直接移到C柱上；
③用A柱過渡，將B柱上的(n-1)個盤子移到C桂上。
請使用遞歸法編寫程序。
參考答案：
def mov(n,a,c,b)：
if(n==0)：
return
mov(n-1,a,b,c)
print(a,’--->',c)
mov(n-1,b,c,a)
n=3
mov(n,'a','c','b’)
21世紀教育網 www.21cnjy.com 精品試卷·第 2 頁 （共 2 頁）
HYPERLINK "http://21世紀教育網(www.21cnjy.com)
" 21世紀教育網(www.21cnjy.com)

展開更多......

收起↑