单元素养检测卷(二)(字符串、队列、栈与树)-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

单元素养检测卷(二)(字符串、队列、栈与树)(见学生用书P261) [时间：45分钟　满分：50分] 学科网（北京）股份有限公司 一、选择题(本大题共12小题，每小题2分，共24分。在每小题给出的四个选项中，只有一个是符合题目要求的。) 1．有如下Python 程序段： s1＝”1324”；s2＝”friendly” j＝0；m＝0；c＝”” for i in range(len(s2))： k＝int(s1[j]) c＝c＋s2[m＋k－1] j＝j＋1 if j>3： j＝0 m＝m＋4 print(c) 执行该程序段后，变量c 的值是(　A　) A．”firenldy”　　　　 B．”firendly” C．”frienldy” D．”friendly” 【解析】 变量j<＝3 时，m＝0，m＋k与i的值相等，当j>＝4时，j重新从0开始计算，而m＋＝4；故m＋j的值与i始终相等，c与s2相等，选项A正确。 2．小明编写Python程序统计一段英语文章中单词的数量(假设单词以非字母字符隔开并结尾)，代码如下： s＝input(”输入一段英语文章：　”) s＝ dic＝{} temp＝”” for i in range(len(s))： if ”a”<＝s[i]<＝”z”： 　　 else： if temp in dic： dic[temp]＋＝1 else： temp＝”” for i in dic： print(i，dic[i]) 上述程序段中加框处可选的代码有： ①s.lower()　 ②s.upper()　③temp＋＝s[i] ④temp＝s[i]　⑤dic[temp]＝1　⑥temp＝”” 下列选项中，代码顺序正确的是(　A　) A．①③⑤ B．②③⑤ C．①④⑥ D．②③⑥ 【解析】 (1)处代码结合后面的语句“if ”a”<＝s[i]<＝”z””只判断小写字母，可知应该选择①，将所有字母置换为小写；(2)s[i]是小写字母，单词的组成部分，应连接为单词，所以选择③；(3)dic为字典，保存单词和单词数量，temp为一个单词，temp已经在字典中时，数量＋1，不在字典中时， 字典中添加一项，键为单词，值为数量1。选项A正确。 3．有如下Python 程序段： p＝”)！@#$%^&*(” c＝”cra2edu” t＝”” for i in range(len(c)//2＋1)： if i%2＝＝0： t＋＝c[len(c)－i－1] elif c[i]>＝”0” and c[i]<＝”9”： t＋＝p[int(c[i])] else： t＋＝c[i] print(t) 执行该程序段后，输出的结果是(　C　) A．ude@ B． cda# C． ure@ D．arc# 【解析】 程序段实现了对字符串的处理。由“range(len(c)//2＋1)”生成的序列为[0，1，2，3]，for循环执行4次。索引i 为偶数时，在字符串c 中取与c[i]对称的字符，因此i＝0 时，将字符“c”对称的字符“u”取出并拼接在字符串t 中；索引i 为奇数时，取出字符“r”并拼接在字符串t 中；i＝2 时，将字符“a”对称的字符“e”取出并拼接在字符串t 中；当i为奇数且c[i]为数字时，则在字符串p 中以c[i]为索引取出字符“@”。选项C正确。 4．已知某循环队列分配的最大空间为10，其中队首指针head＝8，队尾指针tail＝5，则此队列中的元素个数为(　A　) A．7 B．8 C．4 D．3 【解析】 5－8＋10＝7，选项A正确。 5．使用键盘输入“ac←booo←←un←t”，其中“←”表示一次撤销操作(删除前一个字母)。模拟输入过程，合适的数据结构和最后的单词分别是(　A　) A．栈　about B．栈　account C．队列　about D．队列　account 【解析】 “撤销”操作删除前一个字母， 即后输入的字母先删除， 这符合栈“后进先出”的特性。键盘输入“ac←booo←←un←t”，最后的单词为about，选项A正确。 6．使用Python 自带的队列模块queue 可以更便捷地实现队列的操作，代码如下： import queue q＝queue.Queue(5) q．put(”A”) #字符A 入队 q．put(”B”) q．put(”C”) 已知get() 函数可以按照队列特性出队，若要使字符“C”从队列q 中出队，正确的方法是(　D　) A．直接使用语句q.get(”C”) B．直接使用语句q.get() C．使用两次语句q.get() D．使用三次语句q.get() 【解析】 题中所给代码实现了字符“A”“B”“C”依次入队，要让字符“C”出队，根据队列“先进先出”的特性，应执行三次出队操作，选项D正确。 7．已知一棵二叉树有13 个节点，树中度为1 的节点数为2，则该树中度为2 的节点数为(　B　) A．4 B．5 C．6 D．11 【解析】 根据二叉树的性质，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5，选项B正确。 8．用数组表示二叉树的示意图如下，则该二叉树的中序遍历序列为(　A　) A．BEDFAC B．ABDEFC C．DBEAFC D．BDAECF 【解析】 根据题意，创建如下所示的二叉树，然后进行中序遍历，可以得到中序遍历序列为BEDFAC，选项A正确。 9．如图所示，将二叉树A 的根节点与二叉树B 的根节点连接，使得二叉树A 成为二叉树B 的左子树，合并为一棵新的二叉树C。下列说法中正确的是(　C　) A．二叉树C 的高度为3 B．二叉树C 的叶子节点数量为3 C．二叉树C 是一棵完全二叉树 D．二叉树C 中序遍历的结果是一个有序序列 【解析】 选项A，二叉树C的高度为4，选项错误；选项B，二叉树C的叶子节点数量为4，选项错误；选项C，二叉树C是一棵完全二叉树，选项正确；选项D，二叉树C中序遍历的结果为84251637，不是一个有序序列，选项错误。 10．有如下Python 程序段： sz＝[”94”，”98”，”156”，”80”，”87”，”178”] dt＝[0，1，0，1，0，0] st＝[]；top＝0 st.append(top) for i in range(1，len(sz))： flag＝False while len(st)>0 and dt[st[top]]＝＝1 and dt[i]＝＝0： if sz[st[top]]<sz[i]： st.pop() top＝top－1 else： flag＝True；break if not flag： top＋＝1 st.append(i) 执行该程序段后，st 中的元素个数为(　B　) A．6 B．2 C．4 D．3 【解析】 st 是列表模拟的栈，st.pop()表示出栈，st.append(i)表示元素i 入栈，st[top]是栈顶元素。while 循环是根据给定的条件进行出栈的操作。首先“94”对应的下标0 入栈；i＝1：此时dt[i]＝＝1，没有出栈动作，此时“98”对应的下标1 入栈；i＝2：while 条件满足，但是“156”不比栈顶元素“98”大，flag＝True，此时“156”对应的下标2 不会入栈；i＝3：此时dt[i]＝＝1，没有出栈动作，“80”对应的下标3 入栈；i＝4：此时while 条件满足，此时“87”比栈顶元素“80”大，“80”对应的下标3 出栈，接下来的栈顶元素是“98”，flag＝True，没有入栈动作；i＝5：“178”和“87”类似，对应下标也无法入栈。最后栈中只有[0，1]2 个元素，选项B正确。 11．有如下Python 程序段： Q＝[0]*10 cnt，head，tail＝0，0，0 S＝input() for i in range(0，9，2)： t＝S[i] n＝int(S[i＋1]) if t＝＝'A'： for j in range(n)： Q[tail]＝cnt tail＋＝1 cnt＋＝1 elif t＝＝”D”： while head！＝tail and n>0： head＋＝1 n－＝1 print(Q[head：tail]) 若输入S 的值为“A2D1A1D3A2”，则输出的结果是(　B　) A．[3，4，5] B．[3，4] C．[4，5] D．[4] 【解析】 字符串S 中两个字符为一组，其中第一个元素t 代表入队或出队，第二个元素代表n 入队或出队的次数。A是入队，D 是出队，若出队过程中队空，则中止出队。过程如下，选项B正确。 i t n 队列Q 0 A 2 0.1 2 D 1 1 4 A 1 1.2 6 D 3 出队2次，队空 8 A 2 3，4 12．判断某序列b是否为入栈序列[1，2，3，4，5]的出栈序列，编写Python程序如下： a＝[1，2，3，4，5] b＝list(map(int，input().split())) stack＝[] i＝j＝0 while i<len(a): stack.append(①____________ ) i＋＝1 while len(stack)>0 and ②____________ ： stack.pop() j＋＝1 if len(stack)＝＝0 and i＝＝j＝＝len(a): print(b，'是'，a，'的出栈序列') else: print(b，'不是'，a，'的出栈序列') 则①、②处填入的代码分别为(　B　) A．①a[i]　②stack[－1]＝＝a[j] B．①a[i]　②stack[－1]＝＝b[j] C．①b[i]　②stack[－1]＝＝b[i] D．①b[i]　②stack[－1]＝＝a[j] 【解析】 考查栈的操作与程序实现。由第6行的添加操作和第9行的删除操作可以判断stack用于存储栈元素。因此可以通过将a中的元素不断入栈，看能否形成和b一样的出栈序列。第①空应该让a中的元素入栈，填写a[i]。而出栈时，需要判定栈顶元素是否和b序列中当前元素一致，一致才能出栈，尽可能形成与b一样的序列，选项B正确。 二、非选择题(本大题共3小题，第13题8分，第14题8分，第15题10分，共26分) 13．某酒店共有A、B、C三种房间型号，A、B、C型房间的住宿团购价分别为500元/晚、300元/晚、200元/晚。因房型和房间数量有限，酒店规定A型房间只能订1～9个，而B型和C型房间都必须订10～99个。每两个团队的订房信息组成一个订单码，该订单码以第一个团队编号“g1”和字符“－”开头，后面由房间型号及其数量组成，两个团队的信息编号以逗号分隔。例如，订单码“g1－A2B15C27，g2－A6B11C22”，表示团队g1 所订A、B、C型房间的数量分别为2个、15个、27个，团队g2所订A、B、C型房间的数量分别为6个、11个、22个。 请回答下列问题。 (1)若某订单码为“g1－A2B11C17，g2－A8B19C23”，则该订单一天住宿的总金额为__22000__(2分)__元。 (2)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。 def fi(s，b，e)： income＝0 i＝b while i<＝e： if s[i]＝＝”A”： income＋＝①__int(s[i＋1])*500__(2分)__ i＋＝2 elif s[i]＝＝”B”： income＋＝int(s[i＋1：i＋3])*300 i＋＝3 elif s[i]＝＝”C”： income＋＝int(s[i＋1：i＋3])*200 i＋＝3 return income s＝input(”请输入订单码：　”) flag＝False for i in range(len(s))： if s[i]＝＝”－” and not flag： ②__p＝i__(2分)__ flag＝True elif s[i]＝＝”－”： q＝i elif s[i]＝＝”，”： e＝i total＝fi(s，p＋1，e－1) total＋＝fi(s，③__q＋1__(2分)__，len(s)－1) print(total) 【解析】 (1)由规则可知g1、g2 团队订的房型总共为：A 型10(2＋8)个、B 型30(11＋19)个、C 型40(17＋23)个，则该订单一天住宿的总金额为10×500＋30×300＋40×200＝22000元。(2)①此处位于多分支内，由其他分支内容可以看出income累加的是所定A、B、C房型的价格。则该处应为订A房型的总价格，且由题目可知A房型只能订1～9 个，数字只有1位，所以此处应填int(s[i＋1])*500。 ②由该for循环的最后一行total＝fi(s，p＋1，e－1)可知p未赋值，p＋1 为g1团队的订单房型的起始位置(A所在位置)，则p的值应为“－”所在位置，即当前i的位置，填p＝i。 ③由total＝fi(s，p＋1，e－1)可知只计算了g1团队的总金额，还需计算g2团队的总金额，则此处total累加的是g2团队的总金额，填空处应为g2团队房型的起始位置。在上面的for循环中遍历完了整个订单码，那么会记录g2团队的“－”位置q，则此处应填q＋1。 14．某种密码设计方法如下：给定两个数组，数组元素由数字1～9 组成，从中选出k(k 小于等于两个数组长度之和)个数字拼接成一个新的数，同一数组中取出的数字保持其在原数组中的相对顺序，每个数组中至少有1 个数被选中，满足该条件的最大数即为密码。程序运行界面如图所示： 请回答下列问题。 (1)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。 def select_num(nums，k)： stack＝[0]*len(nums)；top＝－1；cnt＝len(nums)－k for num in nums： while cnt>0 and top！＝－1 and stack[top]<num： 　　　top－＝1；cnt－＝1 top＋＝1; ①__stack[top]＝num__(2分)__ while cnt>0： top－＝1；cnt－＝1 return stack[0：top＋1] def merge(a，b)： c＝””；i＝0；j＝0 while ： if j＝＝len(b) or i<len(a) and a[i]>＝b[j]： c＋＝str(a[i])；i＋＝1 elif i＝＝len(a) or j<len(b) and a[i]<b[j]： c＋＝str(b[j])；j＋＝1 return int(c) num1＝input(”请输入数组1：　”) num2＝input(”请输入数组2：　”) num1＝list(map(int，num1.split(” ”))) num2＝list(map(int，num2.split(” ”))) k＝int(input(”请输入k：　”)) ②__m＝0__(2分)__ for i in range(1，k)： a＝select_num(num1，i) ③__b＝select_num(num2，k－i)__(2分)__ c＝merge(a，b) if c>m： m＝c print(”密码为：　”＋str(m)) (2)程序中加框处代码有误，请改正：__i<len(a)__or__j<len(b)__(2分)__。 【解析】 这段代码实现了求两个数组中各取k 个数后组合成的最大数字。具体实现方法是：自定义函数select_num()，用于从一个数组中选择k 个数，使得这k 个数组成的数字最大。具体实现方法是利用栈的思想，建立一个栈内元素从栈底到栈顶从小到大的单调递减栈，当遇到比栈顶元素更大的数时，弹出栈顶元素，直到栈顶元素比当前数大或者栈为空或者已经选够了k 个数为止。最后返回栈中的前k 个元素即可。所以①处的答案为stack[top]＝num。自定义函数merge()用于实现归并排序。具体实现是利用双指针法，从两个数组的首位开始比较，每次将更大的那个数字添加到结果变量c 中。通过后续代码可得，指针i 指向数组a，指针j 指向数组b，当i<len(a) or j<len(b)时，表示指针i 和j 未完成数组a 或者数组b 中的元素遍历，循环继续。变量m 表示所有合并数字的最大值，因此需要对m 赋初值0。最后，通过枚举思想，利用select_num() 和merge() 函数，a、b 两个数组分别表示对num1 和num2 分别选择i个数和k－i 个数，得到两个数字串后进行合并，得到一个新的数字串c，如果c 比之前得到的最大数字m 更大，则更新m 的值。最后输出m 即为所求的最大数字。 15．某办事处每天都有客户来办理业务，每位客户信息包括客户编号、到达时间、办理业务所需时长和客户等级(1 代表是VIP，0 代表不是VIP)如图1 所示。已将当天所有客户信息按照到达时间的先后顺序存储在文件中。该办事处共有 2个窗口，初始时仅开通1个窗口，当排队人数到达m时，增开1个窗口，增开窗口后，不再关闭。所有客户按照到达时间排成一队办理业务，VIP客户优先。 　　　　　　　　　图1 　　　　　　　　　图2 从文件中读取当天客户信息，根据上述规则，按办理业务顺序输出办理结果，如图2 所示。 请回答下列问题。 (1)以图1 为例，若只开1 个窗口，第4 个办理业务的客户编号为__5__(2分)__。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 '''从文件中读取客户信息存入data 中(到达时间已转换为分钟，如07：53 转换为473)，其中data[0]存储第1 个客户信息，data[0][0]、data[0][1]、data[0][2]、data[0][3]分别表示第1 个客户的客户编号、到达时间、办理业务所需时长(分)和客户等级，代码略。''' def mt(x)： #将分钟转换为时间格式，如473 转换为07：53，代码略 def gs(x)： #格式化输出，代码略 t＝[[9999，9999]，[9999，9999]]#t[0]代表第一个窗口的开始时间和结束时间，t[1]代表第二个窗口的开始时间和结束时间 m＝int(input(”请输入m 的值：　”)) n＝len(data) t[0][0]＝data[0][1] t[0][1]＝data[0][1]＋data[0][2] print(”办理序号”，”客户编号”，”开始时间”，”结束时间”，”窗口编号”) print(gs(1)，gs(data[0][0])，gs(mt(t[0][0]))，gs(mt(t[0][1]))，gs(0)) waitnum＝0 full＝False #full 为True，表示2 个窗口办理业务 openwin＝False #openwin 为True，表示增开1 个窗口 i＝1；q＝1；head＝1；tail＝1 #第一个人已经在办理业务，队伍为空 while ①__q<n__或q！＝n__或i<n__or__waitnum>0(2分)__： while i<n and data[i][1]<min(t[0][1]，t[1][1])： tail＋＝1 waitnum＋＝1 tmp＝data[tail－1] j＝tail－2 while ②__j>＝head__and__tmp[3]>data[j][3]__或j>＝head__and__tmp[3]＝＝1__and__data[j][3]＝＝0__(2分)__： #根据优先级调整排队次序 　　　data[j＋1]＝data[j] j－＝1 data[j＋1]＝tmp i＋＝1 if waitnum＝＝m and not full： full＝True openwin＝True break x＝0 #办理业务的窗口编号 if openwin or full and t[1][1]<t[0][1]： x＝1 if openwin＝＝True: #新开一个窗口 t[x][1]＝③__tmp[1]__(2分)__ openwin＝False if waitnum>0： t[x][0]＝t[x][1] t[x][1]＝t[x][1]＋data[head][2] waitnum－＝1 q＋＝1 print(gs(q)，gs(data[head][0])，gs(mt(t[x][0]))，gs(mt(t[x][1]))，gs(x)) ④__head＋＝1__(2分)__ else： t[x][0]＝data[i][1] t[x][1]＝data[i][1]＋data[i][2] q＋＝1 print(gs(q)，gs(data[i][0])，gs(mt(t[x][0]))，gs(mt(t[x][1]))，gs(x)) i＋＝1 head＝tail＝i 【解析】 (1)根据题意，并结合图1，在只开一个窗口的前提下：首先给编号为1 的客户办理业务，开始时间和结束时间分别为7：53和8：01；在业务办理期间，编号2、3 的客户也已经到达，第二个办理业务的是编号为2 的客户，开始和结束时间分别为8：01和8：07，在此期间编号4 的VIP 客户已经到达，所以第三个办理业务的是编号4 客户，开始和结束时间分别为8：07和8：15，在此期间编号5的VIP客户已经到达，所以第四个办理业务的是编号5 客户，开始和结束时间分别为8：15和8：25。 (2)本题是一个银行排队模拟程序，用于模拟银行窗口的客户排队情况和窗口的办理业务情况。程序从文件中读取当天客户信息，包括客户编号、到达时间、办理业务所需时长和客户等级，然后将到达时间转换为分钟，并将其存储在一个列表中。接下来，程序初始化了一个二维列表t，其中t[0]代表第一个窗口的开始时间和结束时间，t[1]代表第二个窗口的开始时间和结束时间。然后程序根据第一个客户的信息初始化了第一个窗口的开始时间和结束时间，并输出了第一个客户的办理情况。程序通过while 循环来模拟客户排队和窗口的办理业务。循环中q 表示已经在办理业务的人数，n 表示办理业务的总人数，所以①空答案为：q<n 或其他等价答案。在每次循环中，如果客户到达时刚好有其他客户在办理，即当前客户将到达时间早于当前窗口结束时间，将新客户加入队列中，需要根据新客户的等级调整队列顺序。②此空考察插入排序，tmp表示新客户的信息，从队尾往队首遍历，当新客户的等级大于队伍中其他客户的等级时，将data[j]后移一位，所以答案为：j>＝head and tmp[3]>data[j][3]或其他等价答案。当有新用户入队，若队列长度达到了设定的最大值m，且当前没有两个窗口同时办理业务，则需要增开一个窗口。此时，新用户的到达时间tmp[1]即为新窗口服务的开始时间，如果此时队伍中仍然有客户在等待，则让排在队首的客户优先去新窗口办理业务，该客户办理业务的开始时间即为tmp[1]；当开启新窗口(x＝1)且队伍中还有客户时，t[x][0]表示新窗口服务的开始时间。而t[x][0]＝t[x][1]则可以反推出上述③空所在代码中t[x][1]需要记录新用户的到达时间。所以③空答案为：tmp[1]或者data[j＋1][1]。④表示将队首客户分配到相应窗口办理业务，同时更新相应业务办理窗口的开始时间和结束时间，需要进行出队的操作，所以答案为：head＋＝1。如果没有客户在等待，则直接将下一个客户分配给一个窗口办理业务，并更新该窗口的开始时间和结束时间。 学科网（北京）股份有限公司 $$