选择性必修1数据与数据结构专题检测卷6-2024高考信息技术一轮复习高中总复习第1轮检测卷

选择性必修1数据与数据结构专题检测专题六检测卷一、选择题（本大题共12小题，每小题2分，共计24分。每题只有一个正确答案，多选、不选、错选均不给分）1.下列有关查找说法中，正确的是（）A.采用顺序查找时，被查找的数据序列必须有序 B.采用二分查找时，被查找的数据序列有序无序均可C.采用顺序查找总能找到要找的数据 D.二分查找的平均效率比顺序查找要高【答案】D【解析】【详解】本题考查的是查找算法。顺序查找对被查找的数据序列的有序性没有要求，而采用二分查找时，要求被查找的数据序列必须有序，因此AB选项错误；采用顺序查找或二分查找时，若数据序列中存在要找的数据，则查找成功，否则查找失败，因此C选项错误；二分查找的平均效率比顺序查找要高，因此答案为D。2.若采用冒泡排序对数据1，19，6，7，2，8，23，15进行排序处理，则第二遍加工后的结果是（）原始数据11967282315第一遍加工后23119672815第二遍加工后…A.23，19，1，15，8，6，7，2 B.23，19，1，15，6，7，2，8C.23，19，15，1，6，7，2，8 D.23，19，15，8，1，6，7，2【答案】B【解析】【详解】本题考查冒泡排序。观察第一遍加工后的结果可知，本题的排序方式为降序，并且从后往前进行数据比较和交换，若后面的数据比前面的大则进行互换，因此第二遍加工后的结果为23，19，1，15，6，7，2，8，故答案为B。3.采用冒泡排序对数据6，7，9，2，1，8，5，4进行升序排序，则排序完成时共进行数据交换次数为（）A.15 B.16 C.17 D.18【答案】C【解析】【详解】本题考查冒泡排序相关内容。采用冒泡排序对数据进行升序排序，以从后往前进行数据比较为例，具体排序过程如下表所示:则数据交换次数为:6+4+3+3+1=17，故本题答案为C选项。4.在数组a中存储的数据依次为“12，56，37，18，19，22，28，26，31，33”。现使用顺序查找算法在数组a中查找数据122，则共需查找的次数为（）A.8次 B.9次 C.10次 D.11次【答案】C【解析】【详解】本题考查顺序查找相关内容。122不存在于数组a中，数组a中共有10个元素，当与a数组中所有元素全部比较完结束，因此共查找10次，故本题答案为C选项。5.在数组d中存储的数据依次为:2，3，6，11，13，15，18，22，25，31。现使用二分查找算法在该数组中查找数据25，则共需查找的次数为（）A.1次 B.2次 C.3次 D.4次【答案】C【解析】【详解】本题考查二分查找相关内容。第一次找到的索引号为4的数据（13），因为13<25，因此向右查找，第二次找到索引号为7的数据（22），因为22<25，因此继续向右查找，第三次找到索引号为8的数据（25），找到目标数据，因此共查找了3次，故本题答案为C选项。6.有如下Python程序段:a=[15，20，11，6，12，8，7，3]foriinrange(1，3):forjinrange(0，8i):ifa[j]>a[j+1]:a[j]，a[j+1]=a[j+1]，a[j]程序段运行后，数组a中的数据依次为（）A.3，6，7，8，11，12，15，20 B.15，11，6，12，8，7，3，20C.11，6，12，8，7，3，15，20 D.6，11，8，7，3，12，15，20【答案】C【解析】【详解】本题考查Python程序。本题的功能是将数组a中的数据进行升序排序，求排序两遍后的数据序列情况，第一遍排序后的结果为“15，11，6，12，8，7，3，20”，第二遍排序后的结果为“11，6，12，8，7，3，15，20”，因此答案为C。7.下列Python程序段的功能是对数组a中的元素进行升序排序:#输入10个数据，并存储在数组a中，代码省略n=len(a)foriinrange(①):

forjinrange(②):

ifa[j]>a[j1]:a[j]，a[j1]=a[j1]，a[j]程序中划线①②处应填写的正确语句是（）A.①0n1②n1，i+1，1 B.①0n1②n1，iC.①1，n②n1，i1 D.①1，n②n1，i1，1【答案】D【解析】【详解】本题主要考查的是冒泡排序。根据代码“ifa[j]>a[j1]:”可知，排序时数据是从后往前进行比较和交换的，变量i表示排序的次数，n个数据排序共需进行n1遍，变量j表示当前数组元素的下标，因此方法一为:①处代码为0，n1，②处代码为n1，i，1；方法二为：①处代码为1，n，②处代码为n1，i1，1，因此答案为D。8.某查找算法的代码如下:a=[11，6，3，54，11，32，15，8，11，7]key=int(input())i=0whilei<len(a)anda[i]!=key:i+=1print(i)当输入key的值为11，执行该代码处理后输出的结果是（）A.0 B.1 C.4 D.8【答案】A【解析】【详解】本题考查Python程序设计相关内容。程序的功能是在数组a中查找是否存在值为key的数组元素，若有多个数组元素与key相等时，查找第一个即结束查找，i为值为key的数组元素的下标，a[0]的值为11，故本题答案为A选项。9.某二分查找的程序段如下:i=0j=9c=0key=int(input(′key:′))whilei<=j:c=c+1m=(i+j)∥2ifb[m]==key:breakelifb[m]<key:j=m+1else:i=m+1数组元素b[0]到b[9]的值分别是“100，89，81，76，74，66，62，50，44，30”。若该程序运行结束后，c的值为3，则key可能的值是（）A.89 B.76 C.50 D.44【答案】D【解析】【详解】本题考查二分查找相关内容。若key=89，则需查找2次，因此A选项错误；若key=76，则需查找4次，因此B选项错误；若key=50，则需查找2次，因此C选项错误；若key=44，则需查找3次，故本题答案为D选项。10.有如下Python段:importrandomb=[39，35，28，17，15，11，9，6]n=random.randint(1，4)*21foriinrange(8n):forjinrange(7，i，1):ifb[j]<b[j1]:tt=b[j]b[j]=b[j1]b[j1]=ttprint(b)执行该程序段后，输出的结果不可能是（）A.6，39，35，28，17，15，11，9 B.6，9，11，15，17，39，35，28C.6，9，11，15，39，35，28，17 D.6，9，11，39，35，28，17，15【答案】C【解析】【详解】本题考查Python程序设计相关内容。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。故本题答案是C选项。11.某二分查找算法的Python程序段如下:a=[1921，1927，1949，1998，2008，2019]i=0j=len(a)1c=0key=int(input())whilei<=j:c=c+1m=(i+j)∥2ifkey==a[m]:breakifkey<a[m]:j=m1else:i=m+1print(′i=′，i，′j=′，j，′m=′，m，′c=′，c)程序运行时，输入key的值为1998，上述程序段运行结束后，下列说法不正确的是（）A.变量i的值为3 B.变量j的值为4 C.变量m的值为3 D.变量c的值为3【答案】B【解析】【详解】本题考查的是二分查找。使用二分查找在数组a中查找数据1998的过程为：第一次查找时，m=2，而a[2]=1949，因此key>a[2]，继续往右查找，即i=m+1=3，第二次查找时，m=4，因为key<a[4]，所以j=m1=3，第三次查找时，m=3，key与a[3]相等，循环结束，此时变量i、j、m、c的值均为3，因此答案为B。12.数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据二分查找思想:设计一个在数组a中查找数据key的程序。实现该功能的Python程序段如下:i=1j=len(a)1key=int(input(′请输入key:′))whilei<=j:m=(i+j)∥2ifa[m]==key:breakif:j=m1elif:i=m+1else:if:j=m1else:i=m+1ifi>j:s="没有找到!"else:s="位置:"+str(m)print(s)上述程序中方框处可选语句为：①key%2==0anda[m]%2==1②key%2==1anda[m]%2==0③key<a[m]则程序加框处①、②、③处语句依次是（）A.①、②、③ B.①、③、② C.②、①、③ D.③、②、①【答案】C【解析】【详解】本题考查二分查找算法相关内容。本题是二分查找算法的一种变式，查找的数据有两类（偶数和奇数），则在查找过程中需分三种情况来讨论分析：（1）如果要查找的数据（key）是奇数并且当前被访问的数为偶数时，则要查找的数据必定在前半段中，因为后半段肯定都是偶数，即j=m1，故①处代码为：key%2==1anda[m]%2==0。（2）如果要查找的数据（key）是偶数并且当前被访问的数为奇数时，则要查找的数据必定在后半段中，因为前半段肯定都是奇数，即i=m+1，故②处代码为：key%2==0anda[m]%2==1。（3）除上面两种情况外的其他情况，要查找的数据是偶数（或奇数），当前被访问的数据也是偶数（或奇数）时，即ifkey<a[m]，则j=m1，否则i=m+1，即③处代码为：key<a[m]。故本题答案为C选项。二、非选择题(本大题共4题，第13题6分，第14题6分，第15题6分，第16题8分，共26分)13.编写一个单词查找程序，其功能是：在数组wordlist中存储了若干个单词，输入要查找的单词，找出所有的单词并统计个数，最后输出查找的结果。程序运行效果如下图所示。实现上述功能的Python程序如下，请在程序划线处填入合适的语句。#输入单词并存储在数组wordlist中，代码略print(′数组中存储的单词分别为:′)print(wordlist)word=input(′请输入要查找的单词:′)①

times=0foriinrange(n):if②:

times+=1iftimes>0:print("共找到"+③+"个"+word)

else:print("对不起，找不到你要查找的单词!")程序划线①处应填入的代码为:_____;

程序划线②处应填入的代码为:_____;

程序划线③处应填入的代码为:_____。【答案】①.n=len(wordlist)②.word==wordlist[i]③.str(times)【解析】【详解】本题主要考查的是顺序查找算法。根据代码“foriinrange(n)”，可知n是数组wordlist中的单词数，因此①处语句为n=len(wordlist)；如果输入的单词word与数组中某个元素wordlist[i]相等，表示找到，则进行计数，因此②处代码为word==wordlist[i]；times表示找到的单词个数，最后输出时要先转换为字符串，因此③处代码为str(times)。14.数字积木。小明有一款新式积木，每个积木上都有一个数，一天小明突发奇想，要是把所有的积木排成一排，所形成的数目最大是多少呢?你的任务就是读入n个数字积木，求出所能形成的最大数。【输入】第一行是一个整数n(n≤1000)，接下来n行每行是一个正整数。【输出】所能形成的最大整数。【样例输入】41313234345【样例输出】3453413213程序运行界面如下图所示:实现上述功能的Python程序如下，请回答下列问题。list1=list(range(100))n=int(input(′请输入数据个数:′))foriinrange(0，n):list1[i]=input(′请输入积木上的数字:′)foriinrange(0，n1):forjinrange(0，ni1):if①:temp=list1[j]②list1[j+1]=tempprint(′输出结果为:′)foriinrange(0，n):print(list1[i]，end=′′)（1）若现有5个积木，5个积木上的数字分别为67，675，78，781，9，123，则输出结果为_____________。

（2）请在程序划线处填入合适的代码。程序划线①处应填入的代码为:______；程序划线②处应填入代码为:______。【答案】①.97878167675123②.list1[j]+list1[j+1]<list1[j+1]+list1[j]③.list1[j]=list1[j+1]【解析】【详解】本题考查Python综合应用。（1）我们需要将所有的积木数字组合成一个最大的整数。因此，只需要将所有积木数字按照一定的规则排序后拼接即可，最终输出的结果为97878167675123。故答案为：97878167675123。（2）正确的比较方法为：比较拼接后的字符串大小，如有str1、str2两个字符串，若str1+str2>str2+str1，则将str1排在str2的前面，否则将str2排在str1的前面，因此程序划线①处代码为list1[j]+list1[j+1]<list1[j+1]+list1[j]，程序划线②处为数据交换，根据上下语句，可知划线②处的代码为list1[j]=list1[j+1]。故答案为：list1[j]+list1[j+1]<list1[j+1]+list1[j]、list1[j]=list1[j+1]。15.大家期盼的校运会要来了，同学们踊跃报名，共有20人报了100米，30人报了200米。小明编写了一个Python程序，用于查询同时报名参加100米和200米比赛的学生，并统计学生数。具体功能如下:程序运行时，分别列出报100米和200米的学生编号，最后输出同时报名参加100米和200米比赛的学生编号，并统计人数。程序运行界面如下图所示:实现上述功能的程序如下，请在划线处填入合适的代码。#从报名文件中获取报名100米的学生编号，并存储在bh1数组中，代码略#从报名文件中获取报名200米的学生编号，并存储在bh2数组中，代码略n=len(bh1)m=len(bh2)foriinrange(0，n1):forjinrange(①):

ifbh1[j]>bh1[j1]:bh1[j]，bh1[j1]=bh1[j1]，bh1[j]print(′报100米的学生如下:′)print(bh1)print(′\n报200米的学生如下:′)print(bh2)print(′\n同时报100米和200米的学生如下:′)k=0foriinrange(m):p=0②

flag=Falsewhilep<=qandflag==False:w=(p+q)∥2ifbh2[i]==bh1[w]:print(bh2[i]，end="")k=k+1flag=Trueelif③:

q=w1else:p=w+1print("\n共有"+str(k)+"位同学")程序划线①处应填入的代码为:_____；程序划线②处应填入的代码为:_____；程序划线③处应填入的代码为:_____。【答案】①.n1，i，1②.q=n1③.bh2[i]>bh1[w]【解析】【详解】本题考查冒泡排序与二分查找相关内容。程序①代码表示对报100米的学生按编号降序排序，根据语句“ifbh1[j]>bh1[j1]:”，可知数据是从后往前比较的，故①处答案为：n1，i，1。程序②处表示开始查找时的范围终点，共有n个元素，故②处答案为：q=n1。根据语句q=w1可知，程序③处的语句表示bh2[i]>bh1[w]时的情况，故③处答案为：bh2[i]>bh1[w]。16.编写Python程序，实现在一个升序排列的数组中查找绝对值最小的元素。已知数组元素由正数、负数或0构成。例如··数组元素值为“19，13，5，3，4，8，15，16，17，20，25，35，37”，该数组中绝对值最小的数为3。输入一组由正数、负数或0构成的升序排列的数据序列，输出绝对值最小的元素，运行效果如下图所示。实现上述功能的Python程序如下，请回答下列问题。defdmin(x，y):#求x、y中绝对值较小的元素if①:

dmin=xelse:dmin=yreturndmin#输入一组升序排列的数据序列，存储在数组b中print(′数组b中的数据为:′，b)n=len(b)flag=Falsei=0j=n1while:m=(i+j)∥2ifb[m]==0:flag=Trueabsmin=a[m]elifb[m]>0:ifb[m1]>0:j=m1else:flag=True