第二章数据与链表同步作业2023—2024学年高中信息技术浙教版（2019）选修1

第二章数据与链表同步作业2023—2024学年高中信息技术浙教版（2019）选修1 一、选择题 1．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 2．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果        A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃” 3．用两个列表a、b分别保存单向链表中的数据区域和指针区域。如下图所示，在节点x与节点y之间插入一个新节点，操作步骤正确的是（  ） ①b[i]= b[y]        ②b[i]= b[x]               ③b[y]= i            ④b[x]=i           ⑤b[i]= x                 ⑥b[i]= y A．③⑥ B．④② C．①③ D．②④ 4．设有数组定义语句：Dim a(5) As Integer，Listl 为列表框控件。下列给数组元素赋值的语句，错误的是（  ）。 A．a(3)=3 B．a(3)=VAL(InputBox(“InputData”） C．a(3)=Listl.ListIndex D．a=Array(1,2,3,4,5,6) 5．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 6．下到关于数据结构与算法效率的描述，不正确的是（   ） A．数据元素是数据的基本单位 B．数据的存储结构应能体现其逻辑结构 C．使用数组结构存储插入、删除较多的数据时，效率较低 D．某单向链表（结点数>2）设有头尾指针，在该链表尾节点后插入一个新节点时需要遍历多个结点 7．下列数据中，不属于列表的是（   ） A．{10，15，20，25} B．[10，1.5，20，2.5] C．[10,15,20，25] D．[a,"b"，20，25] 8．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（    ）来表示。 A．数组 B．链表 C．栈 D．队列 9．有如下 python 程序： a=[2, 5, 3, 11, 12, 4, 8, 10] n=8; num=[0]*n i=0 while i<n: num[i]=1 for j in range (0, i) : if a[j]<a[i] and num[j]>=num[i]: num[i]=num[j]+1 i=i+1 ans=0 for i in range (n) : if num[i]>ans: ans=num[i] print (ans) 执行该程序段后，输出ans 的值是（    ） A．2 B．4 C．5 D．6 10．使用列表a模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，head为头指针。链表中各节点已按数据区域中的数值由小到大排列。现要计算链表中的中位数，处在链表最中间位置的数叫做中位数。说明：当数据元素为奇数个时中位数为最中间的数，偶数个时中位数为最中间两个数的平均数。实现功能的Python程序如下，划线处应填入的正确代码为（   ） fast=slow=head while fast!=-1 and ① :     p=slow     slow=a[slow][1]     fast=a[a[fast][1]][1] if ② :     mid=(a[p][0] +a[slow][0])/2 else:     mid=a[slow][0] print("中位数是:", mid) A．①slow!=-1  ②fast!=-1 B．①a[slow][1]!=-1 ②fast==-1 C．①a[fast][1]!=-1  ②fast!=-1 D．①a[fast][1]!=-1  ②fast==-1 11．有如下图所示的单向链表： 从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（   ） A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次 C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个 12．关于线性链表的描述，以下选项中正确的是（   ） A．存储空间不一定连续，且各元素的存储顺序是任意的 B．存储空间必须连续，且各元素的存储顺序是任意的 C．存储空间不一定连续，且前件元素一定存储在后件元素的前面 D．存储空间必须连续，且前件元素一定存储在后件元素的前面 13．创建一个空链表时，通常会设置什么来表示链表的起始（   ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 14．子序列是指数组中连续的若干个元素(至少1个元素)。数组a中有n个整型元素(有正有负)，现要查找和最大的子序列，并输出和。实现该功能的程序段如下，方框中应填入的正确代码为（   ）     def maxsub(a):        tot=-1; tmp = 0        for num in a:           tmp += num                  return tot     a = [-2,1,-3,4,-1,2,1,-5,4]     print(maxsub(a)) A． B． C． D． 15．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 16．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（    ） A．删除该链表中的最后一个节点 B．删除该链表中的第一个节点 C．在该链表第一个节点前插入一个新节点 D．在该链表最后一个节点后插入一个新节点 17．使用列表d模拟链表结构，每个节点包含数据区域（数据均为整型，范围为0~9）和指针区域，h为头指针。若d=[[1,2],[4,4],[3,3],[2,1],[5,-1]]，h=0，遍历该链表得到的数据为（   ） A．1、2、3、4、5 B．1、3、2、4、5 C．1、4、5 D．1、3、4、2、5 18．有如下Python程序段： def poem(1st,q,flag):     st=""     for i in range(7):         st+=1st[q][0]         q=1st[q][flag]     print(st) hw=[["冬",-1,1],["梅",0,2],["枝",1,3],["几",2,4],["点",3,5],["雪",4,6],["花",5,7],["开",6,8],["春",7,9],["信",8,10],["来",9,0]] p=head=0 flag =1;step=3 for i in range(2):     p=hw[head][flag]     poem(hw,p,flag)#①     for j in range(step):         p=hw[p][flag]     poem(hw,p,flag)#② 关于上述程序段的说法，不正确的是(   ) A．语句①第一次执行时，输出“梅枝几点雪花开” B．语句②第二次执行时，输出“开花雪点几枝梅” C．若加框处语句改为flag+=(-1)**i，不会影响程序运行结果 D．若将hw中的["梅",0,2]修改为["梅",0,3]，输出结果将不含文字“枝” 19．使用列表d模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h为头指针。下列程序段实现了删除数据区域为奇数的节点。 q=p=h=2 while p！=-1：     if d[h][0]%2==1：        （1）       q=p=h     elif d[p][0]%2==1：        （2）       p=d[p][1]     else：       q=p       p=d[p][1] 划线处可选代码如下： ①h=d[h][1]     ②p=d[p][1]     ③d[p][1]=d[q][1]    ④d[q][1]=d[p][1] 下列选项中，代码顺序正确的是（    ） A．①③ B．②③ C．①④ D．②④ 20．使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a a=[["cat",1],[ "dog",2],[ "pig",-1],[ "rabbit",0]] head=3 依次输出各节点数据域的值，内容为(　　) A．"cat","dog","pig","rabbit" B．"pig","rabbit","cat","dog" C．"pig","dog","cat","rabbit" D．"rabbit","cat","dog","pig" 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 2．B 【详解】本题考查的是pandas库相关知识。Series中如果没有指定索引，索引值就从 0 开始，故s[2]值为3，故选项B正确。 3．D 【详解】本题主要考查链表数据结构。在节点x与节点y之间插入一个新节点i前x与y相连，b[x]=y，插入i后需要将i连接进来，首先将i节点与y相连接，即②b[i]=b[x]=y，再将x与i连接起来，即④b[x]=i，故本题选D选项。 4．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 5．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 6．D 【详解】本题考查不同数据结构的特性和算法描述。选项A：数据元素是构成数据的基本单位，正确；选项B：数据结构有逻辑结构和物理结构之分。逻辑结构反映数据之间的逻辑关系，物理结构反映数据在计算机内部的存储安排，正确；选项C：采用数组存储数据，进行插入、删除操作时，需要移动元素，效率较低；选项D：设有尾指针的单链表在表尾节点插入新节点时，只需要修改尾指针即可，不需要从表头开始遍历各节点，选项D错误。故本题正确答案是D。 7．A 【详解】本题考查的知识点是列表数据类型。列表用方括号“[]”来表示，元素之间以逗号“,”分隔。不同类型的元素可以存在于同一列表中。{10，15，20，25}是集合数据类型。故答案为A选项。 8．B 【详解】本题考查的是链表相关知识。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。寻宝游戏中通过一个线索找到下一个线索，最好用链表来表示，故选B选项。 9．C 【详解】本题考查的是数组子序列。阅读程序可知，程序的功能是求最长递增子序列的长度是多少，具体执行过程如下： 索引 0 1 2 3 4 5 6 7 数组a 2 5 3 11 12 4 8 10 数组num 1 2 2 3 4 3 4 5 最长子序列为：2, 3, 4, 8, 10长度为5，故选C。 10．D 【详解】本题考查的是链表的应用。程序的思想是：对链表按1:3的比例，不段扩大，直到链表尾结束。如果数据项为偶数，查找结束刚好是fast!=-1，如果是奇数项，则按1:3的比例扩大后，最后还会剩一项，故①处应为：a[fast][1]!=-1 ，由mid=(a[p][0] +a[slow][0])/2可知，数据项为偶数，查找结束刚好是fast!=-1，故②处为：ast==-1。选项D正确。 11．D 【详解】本题考查的知识点是链表数据结构。从头指针head指向的节点开始查找数据元素“5”，“5”是第4个元素，共查找4次。删除节点时，找到要删除的节点后，修改其前一个节点的指针域，使其指向要删除节点的下一个节点，后续节点不存在移动。由于删除的是第三个节点，因此头指针head将指向第四个节点，即数据元素为“1”的节点。操作完成后，链表中数据元素的个数为6个。故答案为D选项。 12．A 【详解】本题考查线性链表。具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据元素，逻辑上相邻的元素在物理上不要求也相邻。选项A正确，其它选项错误。故正确答案为选项A。 13．C 【详解】本题考查链表。创建空链表时，通常会将头指针设置为一个表示空的值，如NULL（在C/C++中）或-1（在某些特定场景下的约定）。故选择C。 14．C 【详解】本题考查的知识点是子序列的相关知识。子序列是指数组中连续的若干个元素(至少1个元素)。依题意知：数组a中和最大的子序列为[4,-1,2,1]，和为6。A选项运行结果为4，B选项运行结果为4，C选项运行结果6，D选项运行结果为1。故答案为C选项。 15．B 【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。 16．A 【详解】本题主要考查链表数据结构。删除该链表中的第一个节点、在该链表第一个节点前插入一个新节点、在该链表最后一个节点后插入一个新节点均不需要遍历多个节点，只需一次操作即可完成。删除该链表中的最后一个节点需要从头开始遍历，故本题选A选项。 17．B 【详解】本题考查链表。据题目描述，列表 d 模拟了一个链表，每个元素是一个列表，包含两部分：数据区域和指针区域。h 是头指针，表示链表的起始位置。具体来说，d 中每个元素的第一个值表示节点的数据，第二个值表示下一个节点在列表 d 中的索引，如果为 -1 表示链表结束。  根据题目给出的 d=[[1,2],[4,4],[3,3],[2,1],[5,-1]]，从头节点开始遍历链表应该按照如下顺序得到数据：1、3、2、4、5，对应选项 B。 18．D 【详解】本题考查链表的综合应用。原循环双向链表是：冬→梅→枝→几一点→雪→花一开→春→信一来→冬，第1次从p节点开始输出七言，再跳3个节点，继续输出七言。第2次反向从p节点开始输出七言，再跳3个节点，继续输出七言。因此依次输出 4句话是梅枝几点雪花开，点雪花开春信来，来信春开花雪点，开花雪点几枝梅。因此AB选项正确。C选项，i=0 时，flag+=(-1)**i=2，切片效果等效flag=-1。i=1 时，flag+=(-1)**i=1。因此C也正确。D选项，修改后，第4次输出还是含有枝。故本题应选D。 19．C 【详解】本题考查程序分析。（1）当头节点为奇数时，需要更新头节点。则移动头节点。故h=d[h][1]。（2）当p节点为奇数时候，需要删除该节点，将p的后继节点接到p的前驱结点q的下一个节点指针上。故d[q][1]=d[p][1]。故正确答案为选项C。 20．D 【详解】本题主要考查链表的操作。head=3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依次类推，依次输出各节点数据域的值，内容为"rabbit","cat","dog","pig"，故本题选D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$