单元素养检测卷(四)(数据与数据结构 模块卷1)-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

单元素养检测卷(四)(数据与数据结构 模块卷1)(见学生用书P269) [时间：45分钟　满分：50分] 学科网（北京）股份有限公司 一、选择题(本大题共12小题，每小题2分，共24分。在每小题给出的四个选项中，只有一个是符合题目要求的。) 1．下列关于数据结构的说法中，不正确的是(　C　) A．数据结构是指数据的组织形式 B．二维数组属于线性数据结构 C．链表是一种优于数组的数据结构 D．队列是限定仅在一端进行插入、在另一端进行删除的线性数据结构 【解析】 链表和数组各有优缺点，选项C错误。 2．有如下Python程序段： a＝b＝”” k＝0 s＝input().strip() for i in range(len(s))： if '0'<＝s[i]<＝'9'： 　k＋＝1 else： b＝s[i－k：i] if a <b： a＝b k＝0 print(a) 若输入“3.803.93.520.888”(不包括引号)，则输出的结果是(　B　) A．803　　　B．93　　　C．520　　　D．888 【解析】 由循环中第6行代码知，变量k统计了数字字符的个数，因此第8行变量b保存了点号间的整个数字字符串，而后第9行进行字符串大小比较，将更大的字符串b保存于变量a中，因此本题是将字符串中最大的数字字符串输出。要注意的是，数字字符串比较与整数比较有差别，因此最大的是93。且最后数字字符串888并不会参与比较。 3．有如下Python自定义函数： def jg(a)： if a＝＝1： return 1 elif a%2＝＝0： return jg(a//2) else： return jg(a*3＋1) 若执行语句n＝jg(5)，则函数jg() 被调用的次数是(　C　) A．1 B．5 C．6 D．7 【解析】 jg(5)→jg(16)→jg(8)→jg(4)→jg(2)→jg(1)，共调用了6次，选项C正确。 4．有如下Python 程序段： import random n＝5 data＝[i＋1 for i in range(n)] random.shuffle(data) #将序列的所有元素随机排序 print(data) flag＝True；i＝0 while i<n－1 and flag： x＝data[i] for j in range(i＋1，n)： if data[j]<data[i]： if data[j]<x： x＝data[j] else： flag＝False break i＋＝1 若flag的值是 True，执行该程序段后，则输出的 data的值不可能是(　B　) A．[2，3，4，1，5] B．[4，5，2，3，1] C．[1，3，2，5，4] D．[1，2，4，3，5] 【解析】 根据代码可知，列表data 中初始值是1～5之间的随机整数。while 循环实现的功能是：若前面的数data[i]比后面的数data[j]大，且data[j]小于x，此时更新x 的值；若data[j]大于或等于x，则将flag 的值置为False，并强行退出。经过模拟可以发现，选项A、C、D 的data 值经过处理后flag的值都为True。选项B，当i＝0，j＝2 时，x 被更新为2，接下去当j＝3 时，满足条件data[j]<data[i]，但此时data[3]>x，因此flag 被赋值为False，并直接退出循环。因此，执行程序段后，flag的值一定为False才能输出选项B中的data，选项B符合题意。 5．有判断是否为素数的Python 程序段如下： from math import sqrt def prime(x，y)： if y>int(sqrt(x))＋1： return ____(1)____ elif x<2 or x%y＝＝0： return ____(2)____ else： return ____(3)____ a＝int(input(”请输入正整数：　”)) if prime(a，2)： print(a，”是素数！　”) else： print(a，”不是素数！　”) 上述程序段中，横线处的代码由以下三部分组成： ①True　②False　③prime(x，y＋1) 下列选项中，代码顺序正确的是(　D　) A．②③① B．②①③ C．①③② D．①②③ 【解析】 本题考查递归算法及自定义函数知识。本题的突破点是，根据素数问题的定义，以及代码“elif x<2 or x%y＝＝0”可知，x 能被y 整除，因此x 肯定不是素数，故返回值应该是False，选项D正确。 6．有四个元素A，B，C，D 按顺序入栈。约定P 操作是指一个元素入栈，O 操作是指一个元素出栈。经过一系列操作后，四个元素的出栈顺序为C，D，B，A，则经过的操作是(　B　) A．PPPOOPOO B．PPPOPOOO C．PPOOPPOO D．PPPPOOOO 【解析】 栈是一种先进后出的数据结构，C 要第一个出栈，则A，B，C 分别入栈后，C出栈，D 入栈后再出栈，最后将栈中B 和A 分别出栈。选项B正确。 7．有一个环形队列，长度为10，头指针为head，尾指针为tail，则下列选项中，队列元素个数与其他三项不同的是(　C　) A．head＝1，tail＝6 B．head＝3，tail＝8 C．head＝6，tail＝0 D．head＝9，tail＝4 【解析】 循环队列中，tail 指向最后一个元素的下一位置，而head 和tail 的先后顺序不一定，数据循环放置。 选项A，放置位置分别为1，2，3，4，5，共5 个； 选项B，放置位置分别为3，4，5，6，7，共5 个； 选项D，放置位置分别为9，0，1，2，3，共5 个； 选项C，放置位置分别为6，7，8，9，只有4 个。选项C符合题意。 8．已知某二叉树的前序遍历结果为“ABCDEF”，中序遍历结果为“CBDAEF”，则下列说法正确的是(　C　) A．其后序遍历结果为“DCBFEA” B．该二叉树为完全二叉树 C．该二叉树深度为3，叶子节点数为3 D．该二叉树用一维数组实现需要6 个节点的存储空间才能表示 【解析】 根据前序和中序遍历的结果还原这棵二叉树，如下图： 选项A，其后序遍历结果为“CDBFEA”，选项错误；选项B，该二叉树不是完全二叉树，选项错误；选项C，该二叉树深度为3，叶子节点数为3，选项正确；选项D，该二叉树用一维数组实现需要7 个节点的存储空间才能表示，选项错误。 9．有如下Python 程序段： a＝[12，45，45，63，0，0，63] cnt＝0 for i in range(1，len(a))： j＝i－1 t＝a[i] while j>＝0 and t>a[j]： a[j＋1]＝a[j] j＝j－1 cnt＝cnt＋1 a[j＋1]＝t print(cnt) 执行该程序段后，输出的结果是(　B　) A．8 B．10 C．11 D．13 【解析】 程序中的内循环用于查找合适的插入位置，从第二个数据开始就执行插入算法，待插入的数a[i]暂时存放于变量t 中，若t 比前面的数据a[i]大，则将数据a[i]移动到后面，然后继续往前查找直到找到合适的位置将t 插入。执行该段代码后，列表a 变为降序序列，其最终结果为a＝[63，63，45，45，12，0，0]。代码中的变量cnt用于记录移动数据的次数，经过模拟后可知在执行插入算法的过程中，总共需要移动10 次。选项B正确。 10．有如下Python 程序段： def tra(head，a)： if head＝＝－1： return ” ” tra(a[head][1]，a) print(a[head][0]，end＝” ”) a＝[[”A”，3]，[”C”，2]，[”D”，4]，[”B”，1]，[”E”，－1]] head＝0 tra(head，a) 执行该程序段后，输出的结果是(　A　) A．E D C B A B．A B C D E C．E B D C A D．A C D B E 【解析】 自定义函数tra()属于递归函数，其递归结束条件是head＝－1，其递归公式是tra(a[head][1]，a)。因此结合列表a，可以根据递归函数tra()和初始条件head＝0，模拟出其输出值为E、D、C、B、A。选项A正确。 11．有如下Python 程序段： from random import randint k＝randint(0，2)*2 i＝0；j＝6；cnt＝0 while i<＝j： cnt＝cnt＋1 m＝(i＋j)//2 if a[m]＝＝a[k]： break if a[m]<a[k]： i＝m＋1 else： j＝m－1 数组元素a[0]～a[6]各不相同且按升序排列，执行该程序段后，下列说法不正确的是(　D　) A．m 的值不可能为6 B．cnt 的值一定为3 C．变量i和j 的值一定相同 D．i 的值可能小于m 【解析】 由代码可知，变量k 值的取值范围是0、2、4，cnt 记录查找次数，m 为数组中值下标。且数组元素a[0]到a[6]各不相同且按升序排列，要查找的key 相当于就是数据a[k]。按照k 的取值，列出如下二分查找的表格，用于模拟查找过程中的各种可能： 综上所述，可知执行该程序段后，选项A、B、C 均正确，且i 的终值都等于m，故选项D错误。 12．有如下 Python 程序段： import random a＝[1，2，3，4，5] st＝[0]*len(a)；top＝－1 i＝0；res＝[] while i<len(a)： if random.randint(0，1)！＝0 or top＝＝－1： top＋＝1 st[top]＝a[i] else： res.append(st[top]) top－＝1 continue i＋＝1 while top！＝－1： res.append(st[top]) top－＝1 print(res) 执行上述程序段后，输出的res的值不可能是(　A　) A． [3，1，2，4，5] B． [1，5，4，3，2] C． [3，4，2，1，5] D． [1，3，2，4，5] 【解析】 第一个while循环中，当栈为空或者生成的随机数为1时，a[i]入栈且i＋1；当生成的随机数为0，且栈不为空时栈顶元素出栈；若退出循环时，栈中还有数据，则全部出栈。该算法相当于给定入栈顺序，随机输出出栈顺序。选项A中，1，2，3依次入栈，3出栈，当前栈顶为2，故下一个出栈的数不可能是1，选项错误。 二、非选择题(本大题共3小题，第13题9分，第14题8分，第15题9分，共26分) 13．大部分社交软件都有好友推荐的功能，当用户A和用户B的共同好友数量超过阈值p时，由系统向用户A推荐用户B。其中共同好友判定方法为：用户A和用户B不是好友，用户C分别是用户A和用户B的好友，则共同好友数量加1。编写Python程序，实现好友推荐功能。执行程序，首先从文件中读取用户id及好友列表，处理后显示用户之间的关系，再输入推荐目标用户id和阈值p；最后显示向目标用户推荐的好友列表。 图1　数据文件　　　　　图2　运行结果 请回答下列问题。 (1)根据如图所示数据分析，若输入推荐目标用户id为“1”，输入阈值为“4”，则推荐好友为：__8__(1分)__。 (2)主程序。读取“数据．txt”文件，进行处理后显示用户关系二维表，再输入推荐目标用户id和阈值p，显示向目标用户推荐的好友列表，请在横线处填入合适的代码。 n＝10 sj＝[]；zj＝[]；tj＝[] #按行读取“数据．txt”文件，每次读一行文字存入字符串变量line中 f＝open(”数据．txt”) line＝f.readline()　　# 读取标题行 line＝f.readline() while line： sj.append(line.split(” ”)) #将字符串以” ”为间隔分割成多个字符串组成的列表 line＝f.readline()　 #读取下一行 zj＝zhengli(sj) # 显示各用户之间关系二维表，代码略 # 输入推荐目标用户id和阈值p，显示向目标用户推荐的好友列表 id＝int(input(”请输入推荐目标用户id：　”)) p＝int(input(”请输入阈值p：　”)) ①__tj＝fenxi(id，p)__(2__分)__#调用函数进行好友推荐 if len(tj)！＝0： 　t＝0 　print(”推荐好友为：　”，end＝” ”) 　while t<len(tj)： print(tj[t]，end＝” ”) t＝t＋1 else： print(”没有推荐好友”) (3)编写用于整理数据的函数zhengli()，根据好友列表，生成关系二维表，请在横线处填入合适的代码。 def zhengli(sj)： r＝[[0 for i in range(n)]for j in range(n)] for i in range(n)： for j in sj[i][1：]： r[i][int(j)－1]＝1 ②__r[int(j)－1][i]＝1__或r[int(j)－1][i]＝r[i][int(j)－1]__(2__分)__# 对角位置同样设置为1 return r (4)编写函数fenxi()，根据输入推荐目标用户id和阈值p，显示向目标用户推荐的好友列表，请在横线处填入合适的代码。 def fenxi(id，p)： res＝[] for i in range(n)： c＝0 for j in range(n)： if i ！＝id－1 and j！＝id－1 and i！＝j： if ③__zj[id－1][j]＝＝1__and__zj[i][j]＝＝1__and__zj[id－1][i]＝＝0__(2分)__： 　　　c＋＝1 if ④__c>__p__(2分)__： res.append(i＋1) return res 【解析】 (1)从题意可知，当两人非好友，但共同好友数量超过阈值时，则可以推荐好友。 1号的非好友是：8、10。 1号与8号的共同好友有：3、4、5、7，共4人。 1号与10号的共同好友是：2、4、6，共3人。 阈值为4，则共同好友超过4个的是8号。 (2)①结合上下代码，调用函数fenxi()，并将返回值存在变量tj中，答案为tj＝fenxi(id，p)。 (3)②第一步是建立表示关系的模型，题干中将这种关系用矩阵的形式表现，其中i行j列表示用户i与用户j，值为1表示有关系，为0表示没有关系。 (4)③此时要满足三个条件： id和j是好友：r[id－1][j]＝＝1 i和j是好友： r[i][j]＝＝1 id和i不是好友： r[id－1][i]＝＝0　三个条件同时成立，则计数器加1。④ 共同好友数量超过阈值p。 14．编程实现将一个正整数n 分解为m 个完全平方数的和，当有多种方案时，输出m 最小时的分解方案。如：12可分解为12 个12之和，4 个完全平方数之和(32＋12＋12＋12)等， 最少可分解为3 个完全平方数之和(22＋22＋22)，则结果为12＝22＋22＋22。程序运行界面如图所示： 请回答下列问题。 (1)若输入整数96，则分解后的完全平方数最少个数为__3__(2分)__个。 (2)下列能够判断正整数a 是完全平方数的表达式有__AC__(2分)__(多选，填字母)。 A． a＝＝int(a**0.5)**2 B． a%int(a**0.5)＝＝0 C． int(a**0.5)＝＝a**0.5 D． a//a**0.5＝＝int(a/a**0.5) (3)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 n＝int(input(”请输入要分解的正整数：　”)) path＝[[－1，－1]]*(n＋1) q＝[0]*n；vis＝[False]*(n＋1) head＝0；q[0]＝n；tail＝1；vis[n]＝True while head<tail and q[head]！＝int(q[head]**0.5)**2： 　　　①__num＝q[head]__(2分)__ head＋＝1 i＝1 while i*i<＝num： tNum＝num－i**i if tNum>0 and vis[tNum]＝＝False： q[tail]＝tNum tail＋＝1 path[tNum]＝[num，i] ②__vis[tNum]＝True__(2分)__ i＋＝1 #统计完全平方数个数m，输出表达式和个数，代码略 【解析】 (1)96＝8**2＋4**2＋4**2，不会有比3 个更少的结果。 (2)选项A、C 是正确的表达式。选项B，当int(a**0.5)＝＝1 时，a%1 必定为0，a 不一定是平方数。选项D 表达式对于任意正整数都是成立的。 (3)①必定是给变量num 赋值，依据队列的特点，head＋＝1 之前应该是num＝q[head]。②tNum 访问过后，应该标记为已经访问过：vis[tNum]＝True。 15．某校工会组织包饺子比赛，为体现团队协作，将包饺子分成和面、调馅、擀饺子皮和包饺子下锅四道工序。每个工会小组派4名选手参加，要求每名选手完成其中一道工序。考虑到包饺子各道工序及选手包饺子的熟练程度差异，为了让团队能取得最佳成绩，比赛负责人将各位选手完成各道工序所用的时间保存在如图1所示的“data.txt”文件中，并编写了一段Python程序，来求出完成包饺子任务所需的最短时间，并按顺序输出各位选手的姓名，程序运行界面如图2所示。 请回答下列问题。 (1)由文件及输出的结果可知，包饺子任务顺序依次为：小博，小茜，__小李，小夫__(1分)__。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 def cal(num)： global top top＝－1 st＝[－1]*n for i in range(n) ： if ①__num%n__in__st__(2分)__： return False else： top＋＝1 st[top]＝num%n num＝num//n return st def pp()： p＝st_min[top] print(”各位选手的安排顺序依次为：　”，end＝””) while p！＝－1： print(b[p][0]，end＝”，”) p＝b[p][1] f＝open(”data.txt”，”r”) #读取“data.txt”中的数据，并存储在列表a中 a＝[] line＝f.readline() for line in f．readlines()： t＝line.split() score＝list(map(int，t[1：])) #score中数据示例：[60，20，85，40] a．append(score) b＝[[”小博”，－1]，[”小夫”，－1]，[”小李”，－1]，[”小茜”，－1]] n＝4 mint＝1000 m＝n**n－1 while m>0： m1＝m if cal(m1)！＝False： ②__st＝cal(m1)__(2分)__ time＝0 while top！＝－1： ③__time＋＝s[st[top]][n－1－top]__(2分)__ top－＝1 if time<mint： 　mint＝time 　st_min＝st m－＝1 print(”完成包饺子任务所需最短时间为：　”，mint) top＝n－1 head＝p＝st_min[top] top－＝1 while top！＝－1: ④__b[p][1]＝st_min[top]__(2分)__ p＝st_min[top] top－＝1 b[p][1]＝－1 pp() #调用函数，按顺序输出各位选手的姓名 【解析】 题意理解：已知4个人每个步骤所需要的时间，现在通过筛选并组合成最佳组合完成整个任务，每个步骤一个人。实现算法是使用枚举法找出所有组合中的最佳方案，每个人都可以安排在任何岗位，每个岗位分别用0～3表示，则4个人的组合就形成一个四进制数，枚举所有四位四进制数，找出最佳组合。 (1)由图可知和面安排小博，调馅安排小茜，擀饺子皮安排时间最少的小李，包饺子下锅安排小夫，所以安排顺序是：小博，小茜，小李，小夫。 (2)每个人在每个岗位所需要的时间存储在列表a中，形成如题干图1的二维列表，枚举所有n(n＝4)位四进制数，共n**n个，十进制数值为0～n**n－1，函数cal()的功能是使用栈把一个十进制数转换为四进制数，因为每个人只安排一个岗位，就要求四位四进制数里不能有相同的数，第①空在转换四进制时发现有数字重复则停止转换，返回False，故①处填写num%n in st；如果cal返回的结果不是False，说明当前的四进制数是一个可用的组合，则返回的是整个栈，所以第②空取得当前组合：st＝cal(m1)；接下来计算当前组合所用的总时间，此时栈st里存放的是每个人的岗位，从栈里取出每个人的岗位，累加每个岗位所需时间。假设当前四进制数为0123，第一个人在第一个岗位，而0在栈顶，它的时间所在位置为n－1－top，所以第③空填写的是time＋＝a[st[top]][n－1－top]；计算出所有可用组合的时间后需要找出时间最小值，并把当前栈的存储情况保存在st_min中，最后从st_min中取出每个人的安排情况并输出，第④空所在位置把每个人的安排情况形成链表保存在列表b中，依次从st_min中取出岗位，添加到链表中。因为栈中保存的顺序是倒置的，所以需要把栈中的位置反序并输出，所以第④空填写b[p][1]＝st_min[top]。 学科网（北京）股份有限公司 $$