资源简介

专题六　检测卷
一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)
1.下列有关查找的说法中,正确的是(　　)
A.采用顺序查找时,被查找的数据序列必须有序
B.采用二分查找时,被查找的数据序列有序无序均可
C.采用顺序查找总能找到要找的数据
D.二分查找的平均效率比顺序查找要高
2.若采用冒泡排序对数据1,19,6,7,2,8,23,15进行排序处理,则第二遍加工后的结果是(　　)
原始数据 1 19 6 7 2 8 23 15
第一遍加工后 23 1 19 6 7 2 8 15
第二遍加工后
…
A.23,19,1,15,8,6,7,2 B.23,19,1,15,6,7,2,8
C.23,19,15,1,6,7,2,8 D.23,19,15,8,1,6,7,2
3.采用冒泡排序对数据6,7,9,2,1,8,5,4进行升序排序,则排序完成时共进行数据交换的次数为(　　)
A.15 B.16 C.17 D.18
4.在数组a中存储的数据依次为“12,56,37,18,19,22,28,26,31,33”。现使用顺序查找算法在数组a中查找数据122,则共需查找的次数为(　　)
A.8次 B.9次 C.10次 D.11次
5.在数组d中存储的数据依次为:2,3,6,11,13,15,18,22,25,31。现使用二分查找算法在该数组中查找数据25,则共需查找的次数为(　　)
A.1次 B.2次 C.3次 D.4次
6.有如下Python程序:
res="
k=1
for i in range(len(a)-2):
if ord(a[i]) * ka[i],a[i+2]=a[i+2],a[i]
k=-k
for s in a:
res+=s
print(res)
已知数组a共8个元素,每个元素都为单个字符,运行该程序后输出结果可能是(　　)
A.computer B.repomcut C.nesesicc D.sciences
7.下列Python程序段的功能是对数组a中的元素进行升序排序:
#输入10个数据,并存储在数组a中,代码省略
n=len(a)
for i in range(　　　①　　　):
for j in range(　　　②　　　):
if a[j]>a[j-1]:
a[j],a[j-1]=a[j-1],a[j]
程序中划线①②处应填写的正确语句是(　　)
A.①0,n-1　②n-1,i+1,-1 B.①0,n-1　②n-1,i
C.①1,n　②n-1,i-1 D.①1,n　②n-1,i-1,-1
8.某查找算法的代码如下:
a=[11,6,3,54,11,32,15,8,11,7]
key=int(input())
i=0
while ii+=1
print(i)
当输入key的值为11,执行该代码处理后输出的结果是(　　)
A.0 B.1 C.4 D.8
9.已知非降序列表 a 由若干个整型元素构成,现要查找并输出 a 中整数 key 出现的次数。实现该功能的程序段如下:
def search(a,key):
L,R=0,len(a)-1
while L<=R:
m=(L+R)∥2
if　　　:
　 R=m-1
else:
　 L=m+1
　　return L
#列表a和key初始化,代码略
print(search(a,key+1)-search(a,key))
加框处应填入的正确代码为(　　)
A.a[m] >= key B.a[m] > key
C.a[m] < key D.a[m] <= key
10.有如下Python段:
import random
b=[39,35,28,17,15,11,9,6]
n=random.randint(1,4)*2-1
for i in range(8-n):
for j in range(7,i,-1):
if b[j]tt=b[j]
b[j]=b[j-1]
b[j1]=tt
print(b)
执行该程序段后,输出的结果不可能是(　　)
A.6,39,35,28,17,15,11,9 B.6,9,11,15,17,39,35,28
C.6,9,11,15,39,35,28,17 D.6,9,11,39,35,28,17,15
11.有如下 Python 递归程序:
def f(left,right):
if left >=right:
return left
m=(left+right)∥2
if key<=a[m]:
return f(left,m)
else:
return f(m+1,right)
若 key=11,下列选项中的数组 a 调用 f(0,8)的结果与其他三项不同的是(　　)
A.a=[3,3,7,7,7,9,11,11] B.a=[3,3,9,9,9,9,16,17]
C.a=[3,3,9,9,9,11,11,17] D.a=[3,4,6,8,8,8,11,13]
12.数组a为一组正整数,奇数在前,偶数在后。奇数与偶数已分别按升序排序。依据二分查找思想:设计一个在数组a中查找数据key的程序。实现该功能的Python程序段如下:
i=1
j=len(a)-1
key=int(input('请输入key:'))
while i<=j:
m=(i+j)∥2
if a[m]==key:
　break
if ①:
　j=m-1
elif ②:
　i=m+1
else:
　if ③:
　　j=m-1
　else:
　　i=m+1
if i>j:
　s="没有找到!"
else:
　s="位置:"+str(m)
print(s)
上述程序中方框处可选语句为:
①key%2==0 and a[m]%2==1
②key%2==1 and a[m]%2==0
③key则程序加框处①、②、③处语句依次是(　　)
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、①
二、非选择题(本大题共4小题,其中第13小题6分,第14小题6分,第15小题6分,第16小题8分,共26分)
13.编写一个单词查找程序,其功能是:在数组wordlist中存储了若干个单词,输入要查找的单词,找出所有的单词并统计个数,最后输出查找的结果。程序运行效果如下图所示。
数组中存储的单词分别为:
['bike','black','bike','book','pen','paper','word','work','bike','desk']
请输入要查找的单词:bike
共找到3个bike
实现上述功能的Python程序如下,请在程序划线处填入合适的语句。
#输入单词并存储在数组wordlist中,代码略
print('数组中存储的单词分别为:')
print(wordlist)
word=input('请输入要查找的单词:')
　　　　　①　　　　
times=0
for i in range(n):
if 　　　　　②　　　　　:
　　　 times+=1
if times>0:
print("共找到"+　　　③　　　+"个"+word)
else:
　print("对不起,找不到你要查找的单词!")
程序划线①处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　。(2分)
14.数字积木。小明有一款新式积木,每个积木上都有一个数,一天小明突发奇想,要是把所有的积木排成一排,所形成的数目最大是多少呢 你的任务就是读入n个数字积木,求出所能形成的最大数。
【输入】 第一行是一个整数n(n≤1000),接下来 n行每行是一个正整数。
【输出】 所能形成的最大整数。
【样例输入】
4
13
132
34
345
【样例输出】
3453413213
程序运行界面如下图所示:
请输入数据个数:4
请输入积木上的数字:13
请输入积木上的数字:132
请输入积木上的数字:34
请输入积木上的数字:345
输出结果为:
3453413213
实现上述功能的Python程序如下,请回答下列问题。
　list1=list(range(100))
　n=int(input('请输入数据个数:'))
　for i in range(0,n):
list1[i]=input('请输入积木上的数字:')
　for i in range(0,n-1):
for j in range(0,n-i-1):
　　　　if 　①　:
temp=list1[j]
　②
list1[j+1]=temp
print('输出结果为:')
for i in range(0,n):
print(list1[i],end='')
(1)若现有5个积木,5个积木上的数字分别为67,675,78,781,9,123,则输出结果为
　　　　　　　　　　　　　　。(2分)
(2)请在程序划线处填入合适的代码。
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　　　。(2分)
15.大家期盼的校运会要来了,同学们踊跃报名,共有20人报了100米,30人报了200米。小明编写了一个Python程序,用于查询同时报名参加100米和200米比赛的学生,并统计学生数。具体功能如下:程序运行时,分别列出报100米和200米的学生编号,最后输出同时报名参加100米和200米比赛的学生编号,并统计人数。程序运行界面如下图所示:
报100米的学生如下:
['s399','s319','s313','s310','s255','s238','s218','s217','s208','s207','s206','s205','s198','s132','s105','s051','s039','s037','s032','s031','s028','s022','s021','s016','s015','s011','s008','s003','s002','s001']
报200米的学生如下:
['s001','s013','s015','s031','s318','s515','s216','s022','s039','s512','s137','s213','s206','s417','s338','s339','s340','s313','s298','s399']
同时报100米和200米的学生如下:
['s001','s015','s031','s022','s039','s206','s313','s399']
共有8位同学
实现上述功能的程序如下,请在划线处填入合适的代码。
#从报名文件中获取报名100米的学生编号,并存储在bh1数组中,代码略
#从报名文件中获取报名200米的学生编号,并存储在bh2数组中,代码略
n=len(bh1)
m=len(bh2)
for i in range(0,n-1):
for j in range(　①　):
if bh1[j]>bh1[j-1]:
bh1[j],bh1[j-1]=bh1[j-1],bh1[j]
print('报100米的学生如下:')
print(bh1)
print('\n报200米的学生如下:')
print(bh2)
print('\n同时报100米和200米的学生如下:')
k=0
for i in range(m):
p=0
　②
flag=False
while p<=q and flag==False:
w=(p+q)∥2
if bh2[i]==bh1[w]:
　print(bh2[i],end=" ")
　k=k+1
　flag=True
elif 　③　:
　q=w-1
else:
　p=w+1
print("\n共有"+str(k)+" 位同学")
程序划线①处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　。(2分)
16.编写Python程序,实现在一个升序排列的数组中查找绝对值最小的元素。已知数组元素有正数、负数或0。例如:数组元素值为“-19,-13,-5,-3,4,8,15,16,17,20,25,35,37”,该数组中绝对值最小的数为-3。输入一组由正数、负数或0构成的升序排列的数据序列,输出绝对值最小的元素,运行效果如下图所示。
数组b中的数据为:[-19,-13,-5,-3,4,8,15,16,17,20,25,35,37]
绝对值最小的元素是:-3
实现上述功能的Python程序如下,请回答下列问题。
def dmin(x,y):　　#求x、y中绝对值较小的元素
if 　　　　　①　　　　　:
　dmin=x
else:
　dmin=y
return dmin
#输入一组升序排列的数据序列,存储在数组b中
print('数组b中的数据为:',b)
n=len(b)
flag=False
i=0
j=n-1
while im=(i+j) ∥ 2
if b[m]==0:
　　flag=True
　　absmin=a[m]
elif b[m]>0:
　if b[m-1]>0:
　　　j=m-1
　else:
　　　flag=True
　　　　　　　　②　　　　
else:
　　if 　　　　　③　　　　　:
　　　i=m+1
　　else:
　　　flag=True
　　　absmin=dmin(b[m],b[m+1])
print("绝对值最小的元素是:",absmin)
(1)程序中加框处的代码有误,应修改为　。(2分)
(2)请在划线处填入合适的代码。
程序划线①处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　。(2分)
专题六　检测卷
一、选择题
1.D　
2.B　解析:观察第一遍加工后的结果可知,本题的排序方式为降序,并且从后往前进行数据比较和交换,若后面的数据比前面的大则进行互换,因此第二遍加工后的结果为23,19,1,15,6,7,2,8,故答案为B。
3.C　解析:本题采用冒泡排序对数据进行降序排序,以从后往前进行数据比较为例,具体排序过程如下表所示:
原始数据 6 7 9 2 1 8 5 4 交换次数
第一遍加工 1 6 7 9 2 4 8 5 6次
第二遍加工 1 2 6 7 9 4 5 8 4次
第三遍加工 1 2 4 6 7 9 5 8 3次
第四遍加工 1 2 4 5 6 7 9 8 3次
第五遍加工 1 2 4 5 6 7 8 9 1次
则数据交换次数为:6+4+3+3+1=17,因此答案为C。
4.C　解析:122不存在于数组a中,数组a中共有10个元素,当与a数组中所有元素全部比较完结束,因此共查找10次,答案为C。
5.C　解析:本题主要考查二分查找的查找次数。第一次找到的索引号为4的数据(13),因为13<25,因此向右查找,第二次找到索引号为7的数据(22),因为22<25,因此继续向右查找,第三次找到索引号为8的数据(25),找到目标数据,因此共查找了3次,答案为C。
6.D　解析:本题主要考查字符串处理和排序思想原理。由比较表达式 ord(a[i])*k7.D　解析:本题主要考查的是冒泡排序。根据代码“if a[j]>a[j-1]:”可知,排序时数据是从后往前进行比较和交换的,变量i表示排序的次数,n个数据排序共需进行n-1遍,变量j表示当前数组元素的下标,因此方法一为:①处代码为0,n-1,②处代码为n-1,i,-1;方法二为:①处代码为1,n,②处代码为n-1,i-1,-1,因此答案为D。
8.A　解析:本题程序的功能是在数组a中查找是否存在值为key的数组元素,若有多个数组元素与key相等时,查找第一个即结束查找,i为值为key的数组元素的下标,a[0]的值为11,因此答案为A。
9.A　解析:本题主要考查的是二分查找算法。根据输出语句:print(search(a,key+1)-search(a,key))以及二分查找函数的返回值L,二次查找的L应该分别指向第一个key的位置和第一个大于key的位置。由以上分析可知,数据分成二部分:左半部分是a[m]= key。所以方框处是填写R指针移动的条件,也就是右半部分:a[m] >= key,因此答案为A。
10.C　解析:n的值为1、3、5、7,当n=7时,将b数组中的数据进行1遍排序,排序结果为“6,39,35,28,17,15,11,9”,因此A选项有可能;当n=3时,排序结果为“6,9,11,15,17,39,35,28”,因此B选项有可能;当n=5时,排序结果为“6,9,11,39,35,28,17,15”,因此D选项有可能;C选项是当n=4时的排序结果,而n是[1,8]间的奇数,因此不可能是C。
11.C　解析:本题主要考查的是递归函数和对分查找算法。由选项知,所有数据都升序排序。由程序知,若当前元素a[m]小于key 时,在列表后半段查找;若当前元素a[m]大于或等于key时,在列表前半段查找。注意相等也是往前半段查找,当列表数据有重复时会一直往前半段查找,找到第一个等于key的位置。也可以将各个选项代入程序阅读,选项A和选项D的结果是6,即11出现的第一个位置;选项B找不到11,但能返回第一个大于11的位置,也是6;选项C,返回11出现的第一个位置,即5。因此答案为C。
12.C　解析:本题主要考查的是二分查找算法。本题是二分查找算法的一种变式,查找的数据有两类(偶数和奇数),则在查找过程中需分三种情况来讨论分析:(1)如果要查找的数据(key)是奇数并且当前被访问的数为偶数时,则要查找的数据必定在前半段中,因为后半段肯定都是偶数,即j=m-1,因此①处代码为key%2==1 and a[m]%2==0;(2)如果要查找的数据(key)是偶数并且当前被访问的数为奇数时,则要查找的数据必定在后半段中,因为前半段肯定都是奇数,即i=m+1,因此②处代码为key%2==0 and a[m]%2==1;(3)除上面两种情况外的其他情况,要查找的数据是偶数(或奇数),当前被访问的数据也是偶数(或奇数)时,即if key二、非选择题
13.①n=len(wordlist)　②word==wordlist[i] ③str(times)
解析:本题主要考查的是顺序查找算法。根据代码“for i in range(n)”,可知n是数组wordlist中的单词数,因此①处语句为n=len(wordlist);如果输入的单词word与数组中某个元素wordlist[i]相等,表示找到,则进行计数,因此②处代码为word==wordlist[i];times表示找到的单词个数,最后输出时要先转换为字符串,因此③处代码为str(times)。
14.(1)97878167675123　(2)①list1[j]+list1[j+1]解析:本题主要考查的是冒泡排序算法的变式。(1)输出的结果为97878167675123。(2)正确的比较方法为:比较拼接后的字符串大小,如有str1、str2两个字符串,若str1+str2>str2+str1,则将str1排在str2的前面,否则将str2排在str1的前面,因此程序划线①处代码为list1[j]+list1[j+1]15.①n-1,i,-1　②q=n-1　③bh2[i]>bh1[w]
解析:本题主要考查的是冒泡排序和二分查找算法。程序①处代码表示对报100米的学生按编号降序排序,根据语句“if bh1[j]>bh1[j-1]··”,可知数据是从后往前比较的,因此①处应填入的代码为n-1,i,-1;程序②处表示开始查找时的范围终点,共有n个元素,因此②处代码为q=n-1;根据语句q=w-1可知,程序③处的语句表示bh2[i]>bh1[w]时的情况,因此③处代码为bh2[i]>bh1[w]。
16.(1)i<=j and not flag或i<=j and flag==False
(2)①abs(x)③b[m + 1]<0
解析:(1)加框处代码是继续查找的条件,绝对值最小的元素还未找到时并且b数组中的数据还未找完,则继续进行查找,因此加框处的代码为i<=j and not flag或i<=j and flag==False。由于本题一定会找到绝对值最小的元素,因此条件i<=j可以省略。(2)本题的程序的功能是使用二分查找算法在升序数组中查找绝对值最小的元素,查找过程分为下列三种情况:当b[m]=0时,说明找到了绝对值最小的元素,查找结束,绝对值最小的元素为b[m];当b[m]>0时,若b[m-1]也大于0,说明绝对值最小的元素在m的前面,即调整j的值为m-1,若b[m-1]小于0,说明绝对值最小的元素为b[m-1]与 b[m]中的较小值,自定义函数dmin(x,y)的功能是求x、y中绝对值较小的数,因此程序①处的代码为abs(x)0,说明绝对值最小的元素为b[m]与b[m+1]中绝对值较小的数。

展开更多......

收起↑