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

[时间：45分钟　满分：50分] 单元素养检测卷(三)(数据结构与算法) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 一、选择题(本大题共12小题，每小题2分，共24分。在每小题给出的四个选项中，只有一个是符合题目要求的。) 1．解决某问题的算法流程和程序代码如下图所示，两者均不完整。 结合算法流程和程序代码，若输入s1 和s2 的值分别为“012”，“121210”，则输出的num 的值为(　　) A．3　　　 B．5　　　 C．7　　　 D．11 【解析】 结合流程图和程序代码可知，该算法循环取出s1 和s2 中的字符，得到a 和b，并比较a和b的关系，如果满足b＝(a＋1)%3，则进行计数。这个过程执行11 次，过程如下表。输出的num 为5。选项B正确。 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2．有如下 Python 程序段： def fac(n)： s＝1 else： s＝n*fac(n－1) return s print(fac(3)) 下列说法不正确的是(　　) A．该程序应用了递归算法 B．程序运行后，fac()函数被调用了3次 C．若问题规模为n，该程序段的时间复杂度为O(n) D．将①处代码改为“n＝＝1”，该程序的功能不变 【解析】 选项A，该程序使用了递归算法，选项正确；选项B，程序的递推过程：fac(3)＝3*fac(2)，fac(2)＝2*fac(1)，fac(1)＝1*fac(0)，fac(0) B ＝1，故fac()函数调用次数为4，选项错误；选项C，递归函数每执行一次的时间复杂度为O(1)，输入规模为n的时间复杂度为：O(1)*n，故该程序的时间复杂度为O(n)，选项正确；选项D，程序在n＝＝0时和在n＝＝1时返回不影响结果，选项正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3．定义如下Python函数： def pell(n)： if n＝＝1： return 0 elif n＝＝2： return 1 elif n>2： return pell(n－1)*2＋pell(n－2) 下列说法不正确的是(　　) A．执行语句print(pell(3))，输出2 B．函数pell()体现了递归的算法思想 C．当n>＝3 时，函数pell()被调用的次数为n*(n－1)//2 次 D．执行语句pell(3)，判断条件“n＝＝2”共执行了2 次 【解析】 本题考查递归算法及自定义函数知识。在使用递归算法解决问题时，应该满足两个条件：一是该问题能够被递归公式描述；二是存在 C 递归结束的边界条件。pell()函数符合这两个特征，因此体现了递归的算法思想。将参数3 代入，pell(3)＝pell(2)*2＋pell(1)＝3，调用过程中，判断条件“n＝＝2”共执行了2 次。因此选项A、B、D 均正确。当n＝4 时，函数总共被调用4 次，而4*3//2＝＝6，故选项C 错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4．有一堆桃子，猴子第一天吃掉其中的一半，并再多吃一个。之后每天猴子都吃掉剩余桃子的一半，再多吃一个。假设到第十天时，猴子发现只剩下了一个桃子，则这堆桃子最初有多少个？实现上述问题的两段Python 程序如下： 下列说法不正确的是(　　) A．程序1 和程序2输出的结果相同，均为第1 天的桃子数量 C B．程序2 使用递归算法，eat_peach()函数的调用次数为10 次 C．将程序1 的画线语句修改为range(day，10)，输出的结果发生改变 D．将程序2 的画线语句修改为print(eat_peach(8))，输出的结果为10 【解析】 程序1 通过迭代算法实现桃子数量的计算，调用函数eat_peach(day)，s＝(s＋1)*2 执行了9－day＋1 次，计算得到第day天桃子的数量，day＝1 时即输出第1 天桃子的数量。程序2 通过递归算法实现，同样是输出第1 天桃子的数量，选项A正确；程序2 为了计算eat_peach(1)，第一次调用函数，应执行计算调用(eat_peach(2)＋1)*2， 引起对函数的第二次调用(递归调用)，重新进入函数，这一过程重复直到参数累加到10 为止，函数调用了10 次，选项B正确；程序1 的画线语句修改为range(day，10)，循环执行次数为10－day＋1，执行次数和输出结果发生改变，选项C不正确；将程序2 的画线语句修改为print(eat_peach(8))，计算的是第8 天剩余的桃子数量，输出的结果为10，选项D正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5．采用冒泡排序算法对数据序列“7，3，8，2，1，9”进行排序，第一轮排序后的结果为“3，7，2，1，8，9”，则完成整个排序需要交换的次数是(　　) A．6 次 B．7 次 C．8 次 D．9 次 【解析】 从第一轮排序后的结果来看，实现的是从前往后升序排列，只要找出序列中的逆序对，就可以判断交换次数。7 和后面的3、2、1 是逆序对，3 和2、1 是逆序对，8 和2、1 是逆序对，2 和1 是逆序对，共有8 组逆序对。选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6．列表s 包含8 个互不相等的元素，即s[0]，s[1]，s[2]，…， s[7]，有如下Python 程序段： n＝8 for i in range(1，5)： for j in range(n－2，i，－1)： if s[j]<s[j＋1]： s[j]，s[j＋1]＝s[j＋1]，s[j] 该程序段实现的是(　　) A．s[0]到s[3]的升序排列 B．s[4]到s[7]的升序排列 C．s[2]到s[5]的降序排列 D．s[1]到s[4]的降序排列 【解析】 根据代码if s[j]<s[j＋1]可知，这是降序排序，相当于将较大的数从后往前推，故可以排除选项A、B。然后将i 的范围代入，当i＝1 时，j 的范围是6 到2，因此列表s 的有序区的起始位置从s[2]开始，排除选项D。选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 7．对一个有n个元素的数组进行排序，下列说法正确的是(　　) A．采用冒泡排序的比较次数和选择排序的比较次数一样，都需要比较n*(n－1)/2次 B．采用冒泡排序肯定比采用选择排序交换的次数多 C．采用选择排序时，若发现某轮没有数据交换，则可提前完成排序 D．采用选择排序时，每轮完成一头一尾两个元素的排序，可减少总交换的次数 A 【解析】 选项B，采用冒泡排序一般比采用选择排序交换的次数多，选项错误；选项C，采用冒泡排序时，若发现某轮没有数据交换，可提前完成排序，选项错误；选项D，采用选择排序时，每轮完成一头一尾两个元素的排序，不会减少总交换次数，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8．某二分查找算法的Python 程序如下： import random key＝random.randint(0，4)*2＋5 n＝10；ans＝0 a＝[4，5，5，8，9，11，11，13，15，17] i＝0；j＝n－1 while i<＝j： m＝(i＋j)//2 if a[m]<＝key： 　 i＝m＋1 else： j＝m－1 ans＋＝a[m] print(ans) 执行该程序段后，输出ans 的值不可能是(　　) A．19 B．27 C．37 D．44 【解析】 本段代码是标准的边界二分查找，key 可能的值有：5、7、9、11、13，ans 是查找中点并累加的和。列表a第一次找到的中点为a[4]＝9，往左查找中点累加的值比往右查找时的累加值小。当key＝5或7时，a[m]分别是：9、5、5、8，ans＝27，为ans的最小值，故选项A的19不可能。 A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 9．某二分查找算法的Python程序段如下： key＝int(input('待查数据为：　')) i＝0；j＝10；n＝0 while i<＝j： m＝(i＋j＋1)//2 if a[m]＝＝key： break elif a[m]>key： j＝m－1；n＝n－1 else： i＝m＋1；n＝n＋1 执行该程序段后，下列说法正确的是(　　) A．若该程序要实现对分查找，则要求数组a中的元素按降序排列 B．若n 为－2，则查找key的值可能等于a[3]的值 C．若n 为2，则查找key 的值可能小于a[10]的值 C D．n 的值最小为－4，最大为4 【解析】 注意中点取值：m＝(i＋j＋1)//2。选项A，从“if a[m]>key：j＝m－1”可以看出数组a中的元素是升序排列的，选项错误；选项B，a[5]－>a[2]－>a[4]－>a[3]，如果key的值等于a[3]，此时n＝－1，选项错误；选项C，a[5]－>a[8]－>a[10]－>a[9]－>end，如果key 值介于a[9]、a[10]之间，此时n＝2，选项正确；选项D，如果要n 的值最小为－4，最大为4，至少节点数满15 个，本题节点数只有11 个，不满足，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10．有如下Python程序段： import random a＝[0]*8；a[0]＝1 for i in range(1，8)： a[i]＝a[i－1]＋random.randint(1，10) i，j，n＝0，7，0；key＝5 while i<＝j： m＝(i＋j)//2；n＋＝1 if a[m]<＝key： 　i＝m＋1 else： j＝m－1 print(n) 执行该程序段后，输出的结果是(　　) A． 1 B． 2 C． 3 D． 4 C 【解析】 数组a中共有8个元素，a[0]＝1，a[1]～a[7]的值均比前一项大1～10，故数组为升序序列，且a[5]>5恒成立。画出该程序段的二叉查找树。key＝5，因此，程序可能从a[2]的两侧或者a[4]的两侧退出，需要查找3次，选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 11．有如下Python 程序段： def find_base(x，y)： left，right＝2，10 while left<＝right： mid＝(left＋right)//2 value＝calc(mid，y) #calc 函数将mid 进制的整数y 转化为十进制数 if value＝＝x： return mid elif value<x： left＝mid＋1 else： right＝mid－1 return－1 x＝int(input())；y＝int(input()) print(find_base(x，y)) 若依次输入83 和123，则输出的结果是(　　) A．2 B．6 C．8 D．－1 【解析】 函数find_base(x，y)的功能为通过二分查找算法查找十进制数x 对应另一进制数y 的基数，如果不存在则返回－1。由于123O＝83D，最后能够找到对应的基数为8，选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12．有如下Python程序段： def bubbleSort(n)： if n＝＝1： return for i in range(n－1)： if arr[i]>arr[i＋1]： arr[i]，arr[i＋1]＝arr[i]＋arr[i] bubbleSort(n－1) from random import randint n＝randint(3，5) bubbleSort(n) 若数组arr 的值为[64，34，25，12，22，11，90]，则调用函数bubbleSort(n)后，arr[3]的值不可能是(　　) A．12 B．25 C．34 D．64 B 【解析】 函数bubbleSort(n)的功能为对数组arr 的前n 个元素进行升序排序。当n 分别为3、4、5 时，arr[3]的值依次为12、64、34，不可能是25，选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 二、非选择题(本大题共3小题，第13题8分，第14题8分，第15题10分，共26分) 13．某年级要选出3位同学参加市趣味科学竞赛，现有8位同学报名参赛。参赛选手展示后由大众评委投票产生前三名。投票结果存储在“vote.txt”文件中，如图1所示。其中choose列的数据为大众评委的投票对象，均以选手代码显示。选手名称与选手代码的对应关系如下表： 选手 名称 选手 A 选手 B 选手 C 选手 D 选手 E 选手 F 选手 G 选手 H 选手 代码 0 1 2 3 4 5 6 7 小明用Python编写了一个统计得票数的程序，用于检查每位大众评委的投票是否有效(每人投3票且不重复)，并对有效结果进行统计，按照得票数从高到低输出投票结果，如图2所示。若存在并列且前三名总人数超过3人，则输出所有满足条件的选手，并通过随机抽奖形式在末位同分同学中抽取参赛学生，如图3所示，在选手C、E、H中抽取一位同学作为第三名。 图1　　　　　　图2　　　　　图3 请回答下列问题。 (1)根据题意，若评委人数为7人，投票数据分别为“142，565，620，361，203，604，136”，则入选人员不可能为___________(单选，填字母)。 A．选手A、选手B、选手G B．选手C、选手D、选手G C．选手A、选手C、选手D D．选手B、选手D、选手G (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 C (1分) from random import randint def check(x)：　#检测投票是否有效 flag＝False sum，checklist＝0，[0]*8 if len(x)＝＝3： for i in range(3)： if ”0”<＝x[i]<＝”7”： checklist[int(x[i])]＝1 for i in range(8)： sum＋＝checklist[i] if ①__________________________________：#输出最终入选人员 　　　 flag＝True return flag dict＝{0：”选手A”，1：”选手B”，2：”选手C”，3：”选手D”，4：”选手E”，5：”选手F”，6：”选手G”，7：”选手H”} f＝open(”vote.txt”，”r”) sum＝＝3 或sum＝＝len(x) (1分) line＝f.readline()　#第一行为列标题，读取两次跳过该行 line＝f.readline() count＝[0]*8 while line： linelist＝line.split(”，”)#将字符串按逗号分隔为列表 ②_______________________ if check(s)： for i in range(3)： s＝linelist[2] (2分) count[int(s[i])]＋＝1 line＝f.readline() f．close() a＝[] for i in range(8)： a．append([dict[i]，count[i]]) #将列表a按照选手票数从高到低排序并输出，代码略 m＝3　#入选人数 b＝[a[0]]；k＝1；st＝0 for i in range(1，len(a))： if ③_______________________________________________________ ___________________： 　　　 break if a[i][1]！＝a[i－1][1]： st＝i k >＝m and a[i][1]！＝a[i－1][1] 或k >＝3 and a[i][1]！＝ a[i－1][1] (2分) k＋＝1 b．append(a[i]) print(”满足条件的选手：　”) for i in range(k)： print(b[i])　#输出满足票数前m条件的参赛选手 print(”最终入选人员：　”) for i in range(st)： print(b[i])　#输出最终入选人员 #末位同分的同学，用抽奖的方式确定入选人员 flag＝[0]*k ④____________________ while d>0： lucky＝randint(st，k－1)　#在最后同分的同学中随机抽取 if flag[lucky]＝＝0： print(b[lucky]) flag[lucky]＝1 d＝m－st (2分) d－＝1 【解析】 (1)已知投票“142，565，620，361，203，604，136”，其中“565”无效，其余选票统计结果为： 选手G一定入选，选项C符合题意。 选手 名称 选手 A 选手 B 选手 C 选手 D 选手 E 选手 F 选手 G 选手 H 选手 代号 0 1 2 3 4 5 6 7 票数 111 111 111 111 11   1111   (2)①函数check判断投票是否有效，利用checklist列表标识选票是否重复，如果sum＝＝3则选票有效，答案为sum＝＝3 或sum＝＝len(x)。②s是选票，第3个元素，答案为s＝linelist[2]。③将列表a按照选手票数从高到低排序，选取前m名，当超过m名且票数与前一项不同，查找结束，答案为k>＝m and a[i][1]！＝a[i－1][1]或k>＝3 and a[i][1]！＝a[i－1][1]。④ 末位同分的同学，用抽奖的方式确定入选人员，st是不同分的结束位置，d为剩余名额，答案为d＝m－st。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14．汽车整车安装流水线有n 个工序(编号为0～n－1)，每个工序可以有若干个前置工序，但最多只有一个未完成的后续工序。对于每个工序，只有完成其所有的前置工序，才能开始作业，完成每个工序需要不同的费用。编写Python程序模拟该安装过程，输入每个工序的编号、后续工序及费用，计算编号为m 的工序需要的费用。 请回答下列问题。 (1)如图所示，工序5 有两个前置工序(2 和4)，需要先完成两个流程：工序0→工序1→工序2，以及工序3→工序4，才能开始工序5 的作业。总 费用为(1＋2＋8)＋(4＋2)＋3＝20。完成工序7的总费用为____________。 (2)定义sort(info)函数，将输入的工序信息info 排序。 def sort(info)： m＝len(info) 28 (1分) for i in range(1，m)： for j in range(0，m－i)： if info[j][0]>info[j＋1][0]： info[j]，info[j＋1]＝info[j＋1]，info[j] 若输入的info＝[[1，2，1]，[0，1，3]，[2，3，4]，[3，－1，2]]，运行sort(info)后，info 中的数据为___________(单选，填字母)。 A．[[3，－1，2]，[2，3，4]，[1，2，1]，[0，1，3]] B．[[0，1，3]，[1，2，1]，[2，3，4]，[3，－1，2]] B (1分) C．[[3，－1，2]，[0，1，3]，[1，2，1]，[2，3，4]] D．[[2，3，4]，[1，2，1]，[0，1，3]，[3，－1，2]] (3)实现输入工序m，计算完成工序m 所需费用的部分Python 程序如下，请在横线处填入合适的代码。 def crt_lnk(): #创建工序链表，维护相关信息 for job in info： ①____________________________ lnk.append([job[0]，job[1]]) pre[job[1]]＋＝1 (2分) for i in range(n)： if pre[i]＝＝0： cur＝i while cur！＝－1： src[cur].append(i) ②__________________________ def cal_ans(obj): #计算完成工序obj 的费用 flag＝[0]*n cur＝lnk[cur][1] (2分) res＝info[obj][2] for i in src[obj]： p＝i while p！＝obj： if flag[p]＝＝0： ③____________________________ flag[p]＝1 p＝lnk[p][1] res＋＝info[p][2] (2分) return res #读取数据到列表info中，每个元素依次为工序编号、后续工序及该工序的费用，代码略 n＝len(info) pre＝[0]*n #pre 列表用于存储每个工序的前置工序的数量 lnk＝[] src＝[[] for i in range(n)] sort(info) m＝int(input()) crt_lnk() print(cal_ans(m)) 【解析】 (1)工序7 的前置工序有工序5 和6，完成工序5 的总费用为20，工序6 没有前置工序，工序7 本身费用为7，总费用为20＋1＋7＝28。 (2)对info 数组从前往后按第1个数据项进行升序排列。该程序段的功能是按当前工序升序排列。 (3)该程序段的功能是计算编号为m的工序需要的费用，费用取决于它的 前置工序和本身费用之和，因此需找出该工序所有的前置工序。①对pre 列表进行赋值，用于存储每个工序的前置工序的数量，job 中包含的信息有工序编号、后续工序和费用，遍历到当前工序，那么该后续工序的前置工序数量会增加1 个。②遍历链表，把某个工序的所有前置工序编号保存到src 列表中。当pre[i]的值为0 时，表示该工序没有前置工序，是后续工序的开始，相当于头节点，对该链表进行遍历，把当前工序的所有前置工序编号保存起来，如图所示的表格中有编号为0 和6 工序的前置工序数量为0，因此需遍历2 条链表，工序7 的前驱编号为5 和6。③计算完成工序obj 的费用。对obj 所有的前置工序编号进行累加求和，编号p 工序的费用info[p][2]。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15．贪吃蛇在大小为n×n(1≤n≤10)的方阵中游走，它可以往上下左右四个方向游走，当穿越方阵的边界时，还可以从该边界的对立面继续进入方阵。初始时，可以任意安排贪吃蛇的起点位置，并且选择一个方向一直走n步。方阵中的“.”表示空位置，数字表示可以吃的食物，每吃到一个数字时，这个数字便会附着到贪吃蛇的尾部，同时方阵中该数字消失。问：在某个时刻，贪吃蛇身上会不会出现我们想要的某个整数？若有，会有多少个数小于该整数？ 例如：在下面大小为5×5的方阵中可以产生[1，3，4，12，21，234， 243，324，342，423，432]共11个数。其中数“234”的产生过程可能是：选择第4行第2列为起点，第一步吃掉2，接着往右走三步吃掉3，再往右走一步穿越到对面的4，吃掉它成为“234”，共五步。“1234”或“123”等整数是不可能出现的。 请回答下列问题。 (1)输入方阵保存至数组a，然后将贪吃蛇可能吃到的所有数字组合保存到数组b中，请在横线处填入合适的代码。 dx＝[0，1，0，－1] #模拟贪吃蛇往四个方向游走时行号变化的数组 dy＝[1，0，－1，0] #列号变化的数组 n＝int(input()) #方阵的大小 a，b＝[]，[] for i in range(n): s＝input().strip().split() #方阵中的一行数据，“.”号和数字字符都以 空格分隔 a．append(s) def calc(i，j，p): x，y，res＝i，j，0 if '0'<＝a[x][y]<＝'9'： res＝int(a[x][y]) for i in range(n－1): x＝①__________________________ #产生新的行号 y＝#产生新的列号(与行号类似)，代码略 if '0'<＝a[x][y]<＝'9': res＝res*10＋int(a[x][y]) return res for i in range(n): for j in range(n): for k in range(4): (x＋dx[p]＋n)%n (2分) num＝②_____________________ if num>0： b．append(num) print(b) #输出所有可能产生的整数(可能会产生重复的整数) (2)若数组a＝[['.'，'1'，'.']，['.', '2'，'3']，['.'，'.'，'.']]，上述程序处理完后数组b中__________________ (选填：存在/不存在)整数2。 (3)对数组b中的所有整数进行升序排序，输入待查找的数据，统计小于等于该数字的数的数量并输出。请在横线处填入合适的代码。 calc(i，j，k) (2分) 不存在 (2分) bn＝len(b) for i in range(bn－1): for j in range(③__________________________________________): 　　　if b[j]>b[j＋1]: b[j]，b[j＋1]＝b[j＋1]，b[j] key＝int(input(”请输入待查找的整数： ”)) i，j＝0，bn－1 while i<＝j: bn－i－1 或bn－2，i－1，－1 (2分) m＝(i＋j)//2 if ④____________________： i＝m＋1 else ： j＝m－1 print(”小于等于”，key，”的数共有”， i，”个”) 【解析】 (1)第5行所在的for循环实现了将n行字符逐行输入并保存至数组a的过程，由此也可以看出数组a是二维数组，那么第20行i和j的循环 b[m]<＝key (2分) 是遍历整个二维数组。第22行k的循环又是什么呢？注意到数组b保存了所有可能产生的数组组合，而b中的元素是满足num>0时才插入，因此num是贪吃蛇游走时产生的数字，这个数字的形成是贪吃蛇游走的结果。 阅读第9行函数calc()，其返回值是res，由第12行代码可知，res的初始值是a[i][j]，即函数的初始参数值，第13行是n－1次的循环，由此可以判断参数i、j分别是行号和列号，参数p是上下左右四个方向值的其中一个。所以第①空是根据方向值p产生新的行号和列号，若当前行号是i，方向是p，新行号是i＋dx[p]，这个值若超过最大行号则变为第一行，因此答案是(x＋dx[p]＋n)%n。加n是为了防止x＋dx[p]出现负值。第②空是调用该函数，k表示的是四个方向，答案是calc(i, j, k)。 (2)绘制a的二维数组形式如图所示，从2所在位置出发，上下左右无论哪个方向都会遇到其他数字，因此不存在单独的整数2。 (3)考查了数据排序和二分查找算法。题目要求数组b中的数进行升序排序，第4行代码中的比较和交换的元素是当前位与后面位元素的比较，因此j可以从前往后循环，即从0到bn－i－1；也可以从后往前循环，即从bn－2到i－1，且步长是－1。对于第④空，由于数据是升序排序的，当第11行条件成立时，i指针往后移一位，否则j前移一位，由此可以初 [['.'，'1'，'.']， ['.'，'2'，'3']， ['.'，'.'，'.']] 步确定第④空的条件是b[m]<key。从输出结果上看，小于等于key的元素共i个，也就是说最后一个可能等于key的元素的位置是i－1，即j。因此，结合第9行循环结束的条件i<＝j可以得到结论：b[m]＝key 应加在if条件中，只有这样才能让i所指向最后一个可能相等的元素的后一个位置(或大于key的元素的位置)，而j指向最后一个可能相等的元素(或小于key的元素)。因此第④空的答案是b[m]<＝key。 感谢聆听，再见！ if ： #① $$