沪教版（2019）选修1第五单元排序与查找 练习及参考答案

中小学教育资源及组卷应用平台
第五单元练习及参考答案
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)