沪教版（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]=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]=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 ... ...