资源简介

粤教版 选修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页

展开更多......

收起↑