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

[] (这是边文，请据需要手工删加) 单元素养检测卷(一)(数据的组织、数组与链表)(见学生用书P256) [时间：45分钟　满分：50分] 学科网（北京）股份有限公司 一、选择题(本大题共12小题，每小题2分，共24分。在每小题给出的四个选项中，只有一个是符合题目要求的。) 1．下列关于数据结构的说法中，不正确的是(　D　) A．队列和栈都是操作受限的线性表 B．计算机中一般会采用树结构来管理文件 C．链表中数据元素的逻辑顺序是通过链表中指针的指向实现的 D．同一个数组中，元素的数据类型可以不同 【解析】 选项D，同一个数组中，各元素的数据类型相同，选项错误。 2．下列关于数据结构的说法中，正确的是(　D　) A．数组的最大元素数量在定义时就已确定，因此在操作过程中不会导致内存浪费 B．删除链表节点时，链表中必定存在某个节点的指针区域发生变化 C．浏览器采用队列结构组织网页数据，从而实现“后退”按钮的功能 D．栈结构只有一端开放，数据进、出操作都只能在开放的一端进行 【解析】 选项A，数组在操作过程中会导致内存浪费，选项错误；选项B，删除头节点，没有节点的指针区域发生变化，选项错误；选项C，浏览器采用栈结构组织网页数据，从而实现“后退”按钮的功能，选项错误。 3． 幼儿园中有8 个小朋友正在玩“依次编号(1～8)”的游戏。他们按编号顺序排队围成一圈，由编号为1 号的小朋友开始报数，报数报到3 的小朋友出列，下一个编号的小朋友又从1 开始报数，一直反复直到剩下最后一个小朋友。在该问题上适合采用的数据结构和剩下的小朋友的编号分别是(　B　) A． 二叉树　7　　　　B． 队列　7 C． 栈　4 D． 链表　4 【解析】 适合的数据结构应为队列，出队的顺序为：3，6，1，5，2，8，4，最后剩下的一人编号为7，选项B正确。 4．有如下Python程序段： import random a＝[0]*6 a[0]＝random.randint(1，5) i＝1 while i<6： a[i]＝a[i－1]＋random.randint(1，5) if i%2＝＝0： a[i]＝a[i]＋a[i]%2 else： a[i]＝a[i]//2 i＋＝1 print(a) 执行该程序段后，a[0]～a[5]中的值可能是(　A　) A．[2，3，8，6，12，7] B．[2，1，2，3，3，4] C．[4，5，6，4，8，6] D．[6，5，10，7，10，8] 【解析】 程序实现的功能为：生成一个升序排序的数组，当i为偶数时a[i]为偶数；当i为奇数时，a[i]是原来的一半；选项B，a[4]不可能为3，选项错误；选项C，5在奇数位，a[1]最大可能为(4＋random.randint(1，5))//2＝4，不可能为5，选项错误；选项D，a[0]＝6，但random.randint(1，5)最大产生5不可能为6，选项错误。 5．有如下Python程序段： import random a＝[0]*5；i＝0 while i<5： a[i]＝random.randint(1，9) if i %2＝＝1： a[i]＝a[i]＋a[i－1] elif a[i]%2＝＝0： i－＝1 i＋＝1 执行该程序段后，数组a中各元素的值可能是(　C　) A．9，18，8，12，9 B．5，8，11，12，9 C．7，8，9，18，3 D．5，12，3，13，7 【解析】 程序实现的功能为：当i为奇数时，执行a[i]＝a[i]＋a[i－1]，当前项的值为当前项与上一项之和；当i为偶数且a[i]是偶数，则当前位置重新产生一个新的数。选项A，a[2]＝8，i值是偶数时，a[i]不能是偶数，选项错误；选项B，i＝2时，偶数位随机产生的最大值为9，不可能是11，选项错误；选项D，随机产生的最大值为9，a[3]＝a[3]＋a[2]，a[2]＝3，a[3]的最大值为12，不可能是13，选项错误。 6．有如下Python 程序段： n＝6 a＝[[0]*n for i in range(n)] for i in range(n)： for j in range(i＋1)： if j！＝0 and j！＝i： a[i][j]＝a[i－1][j－1]＋a[i－1][j] else： a[i][j]＝1 执行该程序段后，a[4]的值为(　C　) A．[1，3，3，1，0，0] B．[1，4，6，6，4，1] C．[1，4，6，4，1，0] D．[1，5，10，10，5，1] 【解析】 该程序生成一个二维列表，执行后的结果为： [[1，0，0，0，0，0], [1，1，0，0，0，0]， [1，2，1，0，0，0], [1，3，3，1，0，0], [1，4，6，4，1，0], [1，5，10，10，5，1]] 选项C正确。 7．有如下Python 程序段： import random n＝random.randint(50，101) a＝[] for i in range(2，n)： while n%i＝＝0： a＋＝[i] n//＝i print(a) 执行该程序段后，输出的结果可能是(　A　) A．[3，3，3，3] B．[2，2，9] C．[55] D．[5，15] 【解析】 随机数n 的值域为[50，101]，外循环遍历了n 所有可能的因子，当找到n 的因子，将因子连接到列表a 中，同时分解n，不断分解直至不能被整除，则进入大循环取下一个因子。因此本题在对随机数n 进行质因分解。选项A，3*3*3*3＝81，数据在[50，101]范围内，有可能；选项B，9 可以被分解为3*3，且2*2*9＝36，数据不在[50，101]范围内，选项错误，同理选项C、D 都未完全分解，选项错误。 8．有如下Python程序段： a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]] x＝1 p＝head＝2 if x＝＝a[p][0]： head＝a[p][1] else： while p！＝－1： if x＝＝a[p][0]： a[pre][1]＝a[p][1] else： pre＝p p＝a[p][1] 执行该程序段后，a[2][1]的值为(　D　) A．－1　　B．0　　C．1　　D．3 【解析】 阅读代码可知，选择结构部分的操作为：如果x为当前链表头指针所指的节点的数据，那么删除头节点，如果不是就遍历后续节点并删除节点数据为1的节点。因为删除需要记录链表的前驱，这里使用pre来存储。原链表为7→1→1→4→6→1。故删除了数据为1的节点之后，7指向了数据4，即a[2][1]为3，选项D正确。 9．有如下Python程序段： a＝[[3，1]，[2，2]，[3，3]，[3，4]，[17，5]，[2，6]，[3，－1]] p＝head＝0 while p！＝－1: q＝p while q！＝－1： t＝q q＝a[q][1] if q！＝－1 and a[q][0]＝＝a[p][0]: a[t][1]＝a[q][1] q＝t p＝a[p][1] p＝head while p！＝－1： print(a[p][0], end＝' ') p＝a[p][1] 执行该程序段后，输出的结果是(　A　) A．3，2，17　　　　　B．3，2，17，2 C．3，2，17，2，3 D． 17 【解析】 考查链表的操作。由第3行和第5行的代码可知p对应外层循环，q对应内层循环。从第8行开始的if语句块可以看出：当a[q]节点上的值与a[p]节点上的值相同时，q指针往后移一位。这是典型的去重操作，将与p指针所指示的节点值相同的a[q]节点删除。指针t的作用是维护了去重后链表最后一个节点的位置。链表中的所有节点应该是不重复的。最后输出的就是链表的所有非重复节点。选项A正确。 10．有如下Python 程序段，其功能是将一个单向链表转换成原链表的逆序链表： lst＝[[15，4]，[30，－1]，[8，0]，[5，2]，[19，1]] head＝3 p＝head q＝－1 while p！＝－1： tmp＝lst[p][1] # head＝q 执行上述程序段后，lst的内容变为[[15，2]，[30，4]，[8，3]，[5，－1]，[19，0]]。加框处的代码由以下三部分组成： ①q＝p　②p＝tmp　③lst[p][1]＝q 下列选项中，代码顺序正确的是(　C　) A．①②③ B．②③① C．③①② D．③②① 【解析】 按照题意，该代码的功能是将一个单向链表转换成原链表的逆序链表。结合代码，可知其算法思想是：在遍历链表的同时，修改当前节点的指针域的指向，让其指向它的前驱节点。p 为当前节点，先将q 的值赋值给lst[p][1]，然后将p 赋值给q，实现了后继节点变为前驱节点。接着继续遍历下一个节点，依次进行迭代。整个循环结束后再修改头指针head 的值为q，这样就可以实现单向链表的逆转。选项C正确。 11．已知链表a 中的每个节点包含数据区域和指针区域两部分，下列Python 程序段的功能是在链表a 中删除数据值为key 的所有节点。 key＝int(input(”输入要删除的数据：　”)) head＝0 while a[head][0]＝＝key and head！＝－1： head＝a[head][1] p＝q＝head if head！＝－1： q＝a[q][1] while①____________： if a[q][0]＝＝key： ②____________ else： p＝a[p][1] q＝a[q][1] 则①、②处填入的代码分别为(　D　) A．①a[q][1]！＝－1　②a[p][1]＝a[q][1] B．①a[q][1]！＝－1　②a[q][1]＝a[p][1] C．①q！＝－1　②a[q][1]＝a[p][1] D．①q！＝－1　②a[p][1]＝a[q][1] 【解析】 在链表中删除值为key 的节点，除了找到当前节点q(a[q][0]＝＝key)外，重要的是要跟踪到q 的前驱节点。从代码中可以看出，q 的前驱节点为p。当找到节点q 时，要删除q 节点，只需要修改p 的指针为q 的后继，如图所示： ②空填： a[p][1]＝a[q][1]。①空循环条件遍历链表a，q 为当前元素指针，要将所有数据都找完，循环条件应为q！＝－1，若条件为a[q][1]！＝－1，则会漏判最后一个数。综上可知，选项D正确。 12．用Python 程序实现删除链表的倒数第n(n 不大于链表长度)个节点，如n＝2 时，链表 更新为 部分代码如下： #读入链表存储在列表s 中，head 存储链表的头节点，代码略 n＝int(input()) pl＝p2＝head while p2！＝－1： if n>＝0： n－＝1 else： p2＝s[p2][1] if p1＝＝head ： head＝s[head][1] else： 上述程序段中加框处可选的代码有： ① p1＝s[p1][1]　②p2＝s[p2][1] ③s[p1][1]＝s[s[p1][1]][1] ④s[p2][1]＝s[s[p2][1]][1] 下列选项中，代码顺序正确的是(　D　) A．①③④ B．①④③ C．②①④ D．②①③ 【解析】 while 循环查找待删除节点的前驱节点位置。通过p1 和p2 遍历链表，前n 次只遍历p2，后续同时遍历p1 和p2，当p2 遍历结束时，p1 刚好指向倒数第n＋1 个节点。所以(1)处选p2＝s[p2][1]，(2)处选p1＝s[p1][1]。确定p1 位置后，执行删除操作。如果p1 指向头节点head，要删除头节点，即更新head 指向原头节点指针区域对应的节点；否则删除p1 的后继节点，即p1 的指针区域更新为p1 后继节点的指针区域，(3)处应选s[p1][1]＝s[s[p1][1]][1]。综上，选项D正确。 二、非选择题(本大题共3小题，第13题7分，第14题9分，第15题10分，共26分) 13．由数组a生成数组b的方法描述如下： (1)将数组a中的n个元素依次分割出若干个数据块，每个数据块有m×m个元素，m最大值为8，最小值为2。分割时，按尽可能大的数据块进行分割； (2)对每个分割出的数据块用“方阵转换法”进行转换，每次转换后得到的数据块依次存储在数组b中； (3)数组a分割后的剩余元素(个数小于4)，直接依序存储到数组b中。 例如：n＝140时，可依次分割出3个数据块，元素的个数分别为64(8×8)、64(8×8)、9(3×3)，剩余元素为3个。 “方阵转换法”过程如下：将数据块中m×m个元素按行序排列成一个数字方阵，从该数字方阵中按列序得到转换后元素的次序。以3×3数据块为例： 程序运行界面如下图所示： 小明依据上述描述设计了如下Python程序。 请回答下列问题。 #读取n个转换前的数据，依次存储到a[0]，a[l]，…，a[n－1]中，代码略 #说明：pa、pb分别是数组a、b的下标 import random b＝[0]*n print(”转换前的元素为：　”) print(a) m＝8 start＝0 #当前未分割数据的第1个元素下标 left＝n　#当前未分割数据的个数 while left>3： if ①__left<m*m__(2分)__： m－＝1 else： pa＝start pb＝start for i in range(m*m)： b[pb]＝a[pa] pb＋＝1 if (i＋1)%m＝＝0： ②__pa＝start＋i//m__或__pa＝pa－(m－1)*m＋1__(2分)__ else： pa＋＝m ③__left＝left－m*m__或__left＝n－start－m*m＋1__(2分)__ start＝start＋m*m for i in range(start，n)： b[i]＝a[i] print(”转换后的元素为：　”) print(b) (1)当 n＝63时，分割出的第2个数据块元素个数为__9__(1分)__。 (2)请在横线处填入合适的代码。 【解析】 (1)n＝63时．可依次分割出3 个数据块，元素的个数分别为：49(7×7)、9(3×3)、4(2×2)，剩余元素为1个。因此，第2个数据块为9个元素。 (2)横线①处代码的功能表示当剩余元素的数量不够分割成数据块m×m时 ，则下一次尝试分割数据块(m－1)×(m－1)，下面分析当m＝3时转置处理： 当i＝0时，执行b[0]＝a[0]，然后推算出下一个存入数组b的元素a[pa]，pa＝pa＋m＝3； 当i＝1时，执行b[1]＝a[3]，然后推算出下一个存入数组b的元素a[pa]，pa＝pa＋m＝6； 当i＝2时．执行b[2]＝a[6]，此时，(i＋1)%m＝＝0，即pa＝start＋1； 当i＝5时，执行b[5]＝a[6]，此时，(i＋1)%m＝＝0，然后推算出下一个存入数组b的元素a[pa], 即pa＝start＋2分割之后剩余元素的数量left＝left－m*m，则下一个数据块的头元素的位置start＝start＋m*m。 14．摘苹果问题：树上有n 个苹果，小明身高160 cm，板凳高度40 cm。每个苹果大小不一样。摘苹果和搬板凳分别需要消耗1 个能量点。假设小明共有ey 个能量点，则如何能使小明摘到苹果的总重量最大？ 编写程序思路：先按苹果高度(小于等于160，大于160 且小于等于200)将数据分别存储在apple_a和apple_b 中，并按苹果重量降序排列。再对两组数据进行比较。若消耗2 个能量点的最重苹果大于消耗1 个能量点的最重两个苹果之和，则摘下消耗2 个能量点的最重苹果，否则摘下消耗1 个能量点的最重苹果。苹果的高度与重量存储在列表apple 中，每个元素中的第一个表示高度(cm)，第二个表示苹果重量(g)。 如apple＝[[100，202]，[210，300]，[170，400]，[110，100]，[140，150]，[180，340]]，ey＝5，则摘下的苹果：[170，400]，[100，202]，[180，340]。 请回答下列问题。 (1)若apple＝[[200，102]，[205，200]，[160，400]，[150，304]，[130，189]，[175，104]，[188，350]]，能量点数ey＝6，则摘到的总重量最大是__1243__(1分)__g。 (2)定义link(d)函数。函数功能将列表d 创建成链表。则①处合适的代码是__d[i－1][2]＝i__(2分)__。 def link(d)： for i in d： i．append(－1) #d[i]追加一个元素－1 head＝0 for i in range(1，len(d))： ①____________ return d (3)解决摘苹果问题的主程序如下，请在横线处填入合适的代码。 apple＝[[100，202]，[210，300]，[170，400]，[110，100]，[140，150]，[180，340]] apple_a＝[]；apple_b＝[] for i in range(len(apple))： if apple[i][0]<＝160： apple_a.append(apple[i]) elif 160<apple[i][0]<＝200： apple_b.append(apple[i]) sort(apple_a)；sort(apple_b) #sort()函数可以将苹果按重量降序排列，代码略 link(apple_a)；link(apple_b) head_a，head_b＝0，0 apple_end＝[] alen＝len(apple_a)；blen＝len(apple_b) ey＝int(input(”请输入能量值”)) def linkdel(d，head，dlen)： apple_end.append(d[head]) ②__head＝d[head][2]__(3分)__ dlen＝dlen－1 return head，dlen while ey>0： if alen>1 and blen>0： if ③　apple_b[head_b][1]>apple_a[head_a][1]＋apple_a[apple_a[head_a][2]][1] 或apple_b[head_b][1]>apple_a[head_a][1]＋apple_a[head_a＋1][1]　(3分)　and ey>＝2： 　　　ey＝ey－2 head_b，blen＝linkdel(apple_b，head_b，blen) else： ey＝ey－1 head_a，alen＝linkdel(apple_a，head_a，alen) elif blen＝＝0 and alen>0： ey＝ey－1；head_a，alen＝linkdel(apple_a，head_a，alen) elif blen>0 and alen＝＝1： if ey>1 and apple_b[head_b][1]>apple_a[head_a][1]： 　　　ey＝ey－2；head_b，blen＝linkdel(apple_b，head_b，blen) else： ey＝ey－1；head_a，alen＝linkdel(apple_a，head_a，alen) elif blen>0 and alen＝＝0 and ey>1： ey＝ey－2；head_b，blen＝linkdel(apple_b，head_b，blen) else： break print(”剩下能量值：　”，ey) print(”摘下的苹果：　”，end＝””) for i in range(len(apple_end))： print(apple_end[i][：2]，end＝””) 【解析】 (1)根据题目中描述的算法，可先将数组apple 中的值分为两部分，同时按苹果重量降序排序，得到结果为： [[160，400]，[150，304]，[130，189]] 与[[188，350]，[175，104]，[200，102]], 然后依次摘取，苹果重量为400＋304＋350＋189＝1243。 (2)该段程序用于按列表顺序创建链表，d[0]的后继为d[1]，即d[0][2]＝1，d[1]的后继为d[2]，即d[1][2]＝2，以此类推，故应填入d[i－1][2]＝i。 (3)主程序根据题意中算法描述通过for 循环先将所有的苹果分为2 部分，小于等于160 的存储在apple_a中，大于120 小于等于200 的存储在apple_b中；然后调用函数sort()进行排序，再调用link()函数创建链表，接下来通过while 循环依次分情况处理，第③空所在程序段用于处理“若消耗2 个能量点的最重苹果大于消耗1 个能量点的最重两个苹果之和，则摘下消耗2 个能量点的最重苹果”的情况，第③空即需要填入该条件表达式判断，故应填入apple_b[head_b][1]>apple_a[head_a][1]＋apple_a[apple_a[head_a][2]][1]，满足该条件则调用自定义函数linkdel()，将该节点从链表中删除(表示摘下该重量的苹果)，故第②空为删除头节点，应填入head＝d[head][2]。 15．操作系统在管理磁盘时，会将磁盘分为一个个“盘块”。在为文件分配空间时，可以将文件装到离散的盘块中。读取一个文件时，首先在目录结构中找到文件项。从文件项中可以获取文件名、存储时间、该文件在存储块中的起始地址等基本信息，但不包含文件具体内容，然后在磁盘文件分配表中找到对应的文件。磁盘文件分配表如图1 所示。 文件结束块用“－1”表示，空闲盘块用“0xff”表示。 　　　　　　　　　　图1 请回答下列问题。 (1)根据文件的起始地址，能方便地找到文件的其他盘块。如图1中，文件“abc”在磁盘中的盘块号依次是__9→4→3→7__(1分)__(注：各盘块号用→分隔)。 (2)如果目录结构损坏，就不能获取文件的基本信息和起始地址。但我们可以借助文件分配表来恢复部 分数据(不考虑恢复文件名、存储时间等信息)。函数regain()的功能是模拟数据恢复，找到各个文件的起始地址和大小(盘块数量)，并返回以[[起始地址， 文件大小], …]形式的列表lst。变量allot 存储文件分配表信息。其实现程序如下： def regain(allot)： lst＝[] visited＝[] #记录allot 的访问情况 for i in range(len(allot))： if allot[i]！＝0xff and i not in visited: #盘块i 需要处理 　　　fsize＝0 p＝i while p！＝－1 and p not in visited： visited.append(p) fsize＋＝1 p＝allot[p] if p＝＝－1： lst.append([i，fsize]) else： for j in range(len(lst))： if lst[j][0]＝＝p： lst[j][0]＝i lst[j][1]＝lst[j][1]＋fsize return lst ①若allot 为[3，7，13，9，0xff，0xff，0xff，8，－1，－1，0xff，1，0，11，0xff，0xff]，调用regain()函数，则语句lst[j][1]＝lst[j][1]＋fsize 一共会被执行__2__(1分)__次。 ②如果把while p！＝－1 and p not in visited 改写为while p！＝－l，对程序的影响是__AD__(2分)__(多选，填字母)。 A．会增加while 的循环体执行次数 B．返回的lst 中的节点数量保持不变 C．while 循环不能正常结束 D．返回的lst 中，文件的起始地址部分不正确 (3)在创建文件时，若新文件需要占据5 个盘块大小，只需要从头到尾找到空闲盘块，并依次链接，并把首地址存放到文件项中。为了有效管理空闲盘块，我们可以将所有空闲盘区(每个空闲盘区可以包括若干个空闲盘块)构建到一条空闲链freelst 中。freelst 每个节点存储本空闲盘区的盘块号、长度和指向下个盘块的指针，创建时把新节点链接到freelst 尾部。 　　　　　　　　　　图2 如图2 所示，共有3 个空闲盘区，盘块号依次为4、5、6、10、14、15。请在横线处填入合适的代码。 def mergefree(allot): #mergefree()函数的功能是从头到尾扫描文件分配表，创建空白盘区链 　　　freeh＝－1；freelst＝[] n＝len(allot) i＝0 while i<n： if allot[i]＝＝0xff： j＝i＋1 while ①__j<n__and__allot[j]＝＝oxff(2分)__ j＋1 freelst.append([i，j－i，－1]) if freeh＝＝－1： freeh＝cur＝len(freelst)－1 else： freelst[cur][2]＝len(freelst)－1 ②__cur＝freelst[cur][2]__或cur＝len(freelst)－1__(2分)__ i＝j＋1 else： i＋＝1 return freeh，freelst #读取文件分配表信息存储到allot 中，代码略 head，freelst＝mergefree(allot) p＝head whi1e p！＝－1: #打印出所有空闲盘块号 for i in range(freelst[p][1])： print(③__freelst[p][0]＋i__(2分)__，end＝'，') p＝freelst[p][2] 【解析】 本题考查了标记数组、链表插入和连续子串问题的处理。 (1)根据图1 的数据模拟，文件abc 的起始地址是9，分配表allot[p]表示地址p 的下一个文件的地址，直到allot[p]＝－1 为止。注意用→分隔地址，答案为9→4→3→7。 (2)第①问代码的作用是读取到已记录的文件，将当前文件合并到已记录的文件中，lst[j][0]＝i 重置文件起点，lst[j][1]＝lst[j][1]＋fsize 修改文件大小。本题中的文件连接关系如下： 文件1：0→3→9、文件2：1→7→8、文件3：2→13→11→1、文件4：12→0可见文件4 与文件1 合并，文件3 与文件2 合并，因此修改大小的语句执行2 次；第②问代码删除了“p not in visited” 后，对已记录文件会重复访问，因此会增加while 循环的次数。同时，循环结束后文件必定已－1 结束，因此合并文件部分的代码将不会执行，无法完成重置文件起始地址的操作，所以结果中的文件的起始地址可能不正确。 (3)记录连续的空白区域，实际上就是连续重复子序列问题。第①空allot[i]＝＝0xff 时，从j＝i＋1 开始查找连续的重复数据，这里额外约束j 不超过最大索引值即可。答案j<n and allot[j]＝＝oxff；第②空将当前新增空白区域的结点插入到链表freelist 末尾，其中cur 标记了链表的尾节点，代码freelst[cur][2]＝len(freelst)－1将尾节点的后继更新为当前新增节点，同时移动尾节点标记cur 为当前新增节点，答案cur＝len(freelist)－1。第③空输出连续的空白盘符，freelst[p][1]是p 指针所指向节点的连续盘符的长度，freelst[p][0]是其起始地址，所以从freelst[p][0]开始的freelst[p][0]＋i 就是连续盘符。 学科网（北京）股份有限公司 $$