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

第二章数据与链表同步作业2023—2024学年高中信息技术浙教版（2019）选修1 一、选择题 1．有如下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]，输出结果将不含文字“枝” 2．某个正整数的每位数依次存储在链表d中各节点的数据区域中。例如，正整数572存储情况如图a所示，h为d的头指针。将该正整数翻倍后的计算结果（如572翻倍后的结果为1144）仍以这个链表存储，最高位存储于头节点中，如图b所示。实现该功能的程序段如下：       图a                           图b if d[h][0]>4: d.append([0,h])         #链表d新增一个节点 h=len(d)-1 p=h while p!=-1: d[p][0]=d[p][0]*2%10 cur=d[p][1] p=d[p][1] 方框中应填入的正确代码为（    ） A．if cur!=-1 and d[cur][0]>4: d[p][0]+=1 B．if cur!=-1 and d[p][0]>4: d[cur][0]=(d[p][0]*2+1)//10 C．if cur !=-1 and d[cur][0]>4: d[p][0]+=(d[cur][0]*2+1)%10 D．if cur!=-I and d[p][0]>4: d[cur][0]+=1 3．下到关于数据结构与算法效率的描述，不正确的是（   ） A．数据元素是数据的基本单位 B．数据的存储结构应能体现其逻辑结构 C．使用数组结构存储插入、删除较多的数据时，效率较低 D．某单向链表（结点数>2）设有头尾指针，在该链表尾节点后插入一个新节点时需要遍历多个结点 4．数组是一种采用哪种存储结构的数据结构（   ） A．顺序存储结构 B．非顺序存储结构 C．索引存储结构 D．散列存储结构 5．找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下： #链表a中存储了序列数据，head为其头指针，代码略 pre=p=head maxpre=maxp=head while p!=-1:    if a[p][0]>a[maxp][0]:        maxp=p ; maxpre=pre    pre=p    p=a[p][1] if maxp==head:    head=a[head][1] elif maxp!=pre:    ① a[pre][1]=maxp ② #遍历输出链表a 划线处的代码应为（   ） A．①a[maxp][1]=a[maxpre][1]          ②a[maxp][1]=a[p][1] B．①a[maxp][1]=a[maxpre][1]          ②a[maxp][1]=p C．①a[maxpre][1]=a[maxp][1]          ②a[maxp][1]=a[p][1] D．①a[maxpre][1]=a[maxp][1]          ②a[maxp][1]=p 6．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 7．在单向链表中，如何访问第n个节点（   ） A．从头节点开始遍历n次 B．通过下标直接定位 C．从尾节点开始反向遍历n次 D．无法直接访问，必须遍历整个链表 8．下列关于数据结构的说法，不正确的是（   ） A．数组、链表、队列和栈都是常见的线性表数据结构 B．数组的存储空间是连续的，链表的存储空间可以是不连续的 C．每个链表必定有一个头指针，同一链表中每个节点的结构均相同 D．对数组进行操作时，若某数组元素被删除，数组占用的存储空间会变小 9．有如下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，则方框处的语句依次为（   ） A．①②③ B．②③① C．③①② D．③②① 10．下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。 #建立链表 link1，代码略 key=int(input("输入要删除的数据：")) head=0 while link1[head][0]==key and head!=- 1:     head=link1[head][1]     p=q=head     if head==- 1:         print("全部数据删除")     else:         q=link1[q][1]         while   ① :             if link1[q][0]==key: ②             else:                p=link1[p][1] q=link1[q][1] 则划线①②处的代码分别为（　　） A．①link1[q][1]!=- 1              ②link1[p][1]=link1[q][1] B．①link1[q][1]!=- 1               ②link1[q][1]=link1[p][1] C．①q!=- 1                          ②link1[q][1]=link1[p][1] D．①q!=- 1                          ②link1[p][1]=link1[q][1] 11．有如下 Python 程序段 def bianli(head): pt = head while pt != -1: print(data[pt][0],data[pt][1],"->",end='') pt = data[pt][1] print() data = [['A',1],['B',2],['C',3],['D',-1]] head = 0 bianli(head)  #遍历链表，显示初始状态为“A 1 ->B 2 ->C 3 ->D -1 ->” qt = head pt = data[qt][1] bianli(head) #遍历链表，显示最终状态为“A 2 ->C 1 ->B 3 ->D -1 ->” 执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为： ①data[data[qt][1]][1] = pt ②data[qt][1] = data[pt][1] ③data[pt][1] = data[data[pt][1]][1] 则方框处代码的正确顺序是（   ） A．①②③ B．①③② C．②①③ D．②③① 12．语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （    ） A．二维单精度实型数组和二双精度型数组 B．二维长整型数组和二维单精度实型数组 C．一维单精度实型数组和二维整型数组 D．一维长整型数组和二维双精度型数组 13．设有数组定义语句：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) 14．有如下Python代码，函数Linkinsert功能是在升序链表lst中按序插入数据data def Linkinsert(lst, data, head):     p=head     lst.append([data,-1])     if data<=lst[head][0]:         lst[-1][1]=head         head=len(lst)-1     else:         q=lst[p][1]         while ① and data>lst[q][0]:             p=q             q=lst[p][1]         ②         lst[-1][1]=q     return head 则划线处应填写的代码是（   ） A．①q!=-1  ②lst[p][1]=len(lst)-1 B．①q!=-1  ②lst[p][1]=len(lst) C．①p!=-1  ②lst[q][1]=len(lst)-1 D．①p!=-1  ②lst[q][1]=len(lst) 15．利用列表a来模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域。head为头指针，各节点已按数据区域中数值由小到大排列。现要对该链表进行去重处理，将链表各节点数据区域中数值重复的节点予以删除。实现该功能的程序段如下，方框中应填入的正确代码为（    ） t=head p=a[t][1] while p!=-1: a[t][1]=-1 A． if a[t][0]==a[p][0]: t=p p=a[p][1]else: a[t][1]=p t=p p=a[p][1] B． if a[t][0]==a[p][0]: p=a[p][1]else: t=p a[t][1]=p C． if a[t][0]!=a[p][0]: a[t][1]=p t=pelse: t=p p=a[p][1] D． if a[t][0]!=a[p][0]: a[t][1]=p t=pp=a[p][l] A．A B．B C．C D．D 16．链表和数组在存储空间上的主要区别是什么（   ） A．链表需要连续的内存空间，数组则不需要 B．数组需要连续的内存空间，链表则不需要 C．两者都需要连续的内存空间 D．两者都不需要连续的内存空间 17．使用列表flink模拟链表结构（节点数大于1），每个节点包含起始数值、连续长度、指针区域，h为头指针。链表中各节点已按起始数值由小到大排列，各个节点表示的数值区间不重叠，例如链表 flink为[[20，100，3]，[150，50，2]，[250，60，-1]，[120，30，1]]，h-0，其中节点[20，100，3]表示从数值20开始有长度为100的连续值（20到119），3代表后继节点索引为3，现要合并链表各节点连续的数值区间，合并后链表flink的数据修改为[[20，180，2]，[150，50，2]，[250，60，-1]，[120，30，1]]，h=0。实现该功能的程序段如下: q=h=0 p=flink[q][2] while p!=-1:     if flink[p][0]==flink[q][0]+flink[q][1]:         flink[q][1]=flink[q][1]+flink[p][1]     else:         （1）     （2）     （3） 上述程序中方框处可选语句为:①q=p  ②flink[q][2]=p  ③p=flink[p][2] 则（1）、（2）、（3）处语句依次是（   ） A．①、②、③ B．①、③、② C．②、①、③ D．②、③、① 18．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 19．使用链表结构模拟某校游玩路线，链表a中每一个节点包含三个数据，第1个为景点名称，第2个为预计游玩时间（单位：分钟），第3个为下一个景点指针。该校可以从多个景点开始游玩，但只能从“南大门”离开，输出显示从各景点进入路线及预计总时间的代码如下。a=[["校训石",21,2]，["行政楼",40,2]，["风雨操场",50,5]，["丽泽湖",30,4]，["西餐厅",60,5]，["南大门",20,-1]] head=[0,1,3] for i in range(len(head)):       (1)      s=a[p][1]      while a[p][2]!=-1:           print(a[p][0],end="→")      (2)      (3)      print(a[p][0])      print("预计时间：",s,"分钟") 上述程序划线处的可选代码有： ①p=head    ②p=head[i]    ③s=s+a[p][1]    ④p=a[p][2] 则（1)、(2)、(3）处代码依次为（    ） A．①③④ B．①④③ C．②③④ D．②④③ 20．下列说法或用法正确的是(   ） A．OPTION   BASE   6 B．OPTION   BASE 语句的位置可以任意 C．DIM    A(6,3  TO  7)定义的是二维数组 D．数组元素的下标不能是负数。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．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。 2．A 【详解】本题考查链表节点插入知识。根据代码可知，当最高位数d[p][0]大于4(即5以上)时，其翻倍后的数将产生进位，因此需要新增加一个节点(默认在数据域插入0)，并将其作为新的头节点h。p 为高位节点，cur为p的后继节点(节点cur是节点p的低位)。该利用链表实现的乘法算法的顺序和常规乘法是相反的：先计算高位p然后再计算低位cur，p节点的数据域是本位d[p][0]的 2倍然后%10 后的值，但这还不是 d[p][0]的终值，还要看p的低位cur有没有产生进，若cur的数据域 d[cur][0] 大于4，则还会向p节点的数据域产生进位，由于最大的单位数9的2倍，其进位也只是1，因此每次 在p节点原先的数据域d[p][0]基础上加1即可实现进位操作。若没有产生进位则依次从高位向低位进 行迭代，直到链表遍历结束为止，综上述，本题应该选A。 3．D 【详解】本题考查不同数据结构的特性和算法描述。选项A：数据元素是构成数据的基本单位，正确；选项B：数据结构有逻辑结构和物理结构之分。逻辑结构反映数据之间的逻辑关系，物理结构反映数据在计算机内部的存储安排，正确；选项C：采用数组存储数据，进行插入、删除操作时，需要移动元素，效率较低；选项D：设有尾指针的单链表在表尾节点插入新节点时，只需要修改尾指针即可，不需要从表头开始遍历各节点，选项D错误。故本题正确答案是D。 4．A 【详解】本题考查数组。数组是一种典型的采用顺序存储结构的数据结构。在顺序存储结构中，数组元素在内存中是连续存储的，元素之间的逻辑关系和物理关系是一致的。通过索引可以快速定位到数组中的任意元素。故选择A。 5．D 【详解】本题考查链表的操作。如果maxp!=head，说明最大数节点不在头节点，同时当满足maxp!=pre时，则把最大数节点删除放到最后面，即a[maxpre][1]=a[maxp][1]，前驱节点的指针域指向最大数节点的指针域，从而实现跳过最大数节点。while循环结束，pre是最后一个节点，p是pre的指针域，即p=-1，将最大数节点maxp连接到最后面，即a[pre][1]=maxp，a[maxp][1]=p。故选D。 6．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 7．A 【详解】本题考查链表。从头节点开始遍历n次 - 在单向链表中，要访问第n个节点，必须从头节点开始，逐个遍历直到到达目标节点。故选择A。 8．D 【详解】本题考查的是数据结构。数组的存储空间都是固定不变的，若某数组元素被删除，数组占用的存储空间不会变。故选D。 9．C 【详解】本题主要考查Python程序的调试。 p=head=3，即指向的元素是[5,2]，也就是链表中最小的一个元素，则逆序后就是最后一个元素，因此其指针域应是-1，此时q=-1，因此第一个语句是lst[p][1]=q，原指针域已经保存在tmp中了，即tmp=lst[p][1]。接下来就是更新q的值为p=3，即下一个元素指向[5,-1]。更新p的值为tmp=2，即接下来处理倒数第二小元素[8,0]，其余元素依次类推，故方框处的语句依次为③①②，故本题选C选项。 10．D 【详解】本题主要考查链表的操作。通过遍历链表来寻找key，故第一空while循环条件是q!=-1。如果link1[q][0]==key，则删除key所在的节点，p是q的上一个节点，则通过p的指针域指向q的指针域以实现删除q节点，故第二空填link1[p][1]=link1[q][1]，故本题选D选项。 11．D 【详解】本题主要考查链表及其Python程序实现。本程序考查的是链表的重新链接，程序实现的效果是 A 1 ->B 2 ->C 3 ->D -1 ->，变为 A 2->C 1 ->B 3 ->D -1 ->，qt 指前一指针，pt 指后一指针，故‘A’要指向‘C’,‘B’要指向‘D’,然后‘C’要指向‘B’，即正确的顺序是，故本题选D选项。 12．D 【详解】本题主要考查数组的定义。符号“%”表示短整型，“&amp;”表示长整型，“！”表示单精度浮点型，“#”表示双精度浮点型，故语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为一维长整型数组和二维双精度型数组，故本题选D选项。 13．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 14．A 【详解】本题考查的是链表插入操作。根据题意if条件是在链表头部插入数据；else是在链表中插入数据，p引入头指针，q指向头指针的后继节点，需要遍历整个链表，只需要遍历到最后一个节点即可，若在while条件中令p！=-1，那么逻辑就会出错，p指向尾结点时，q指向-1，data就会和尾结点的后继指针的数据比较，故①应该是令q！=-1。执行插入的过程是p的后继指针指向data的位置即lst[q][1]=len(lst)-1。故本题答案是A选项。 15．D 【详解】本题考查链表操作。选项A，当t节点与p结点值重复时候，t节点移动到p节点处，p节点向后移动。这时应该删除p节点，p节点应该向下一个节点移动。故不能删除。 选项B，当节点值不同时，缺少p节点向下一个节点移动，故会死循环。 选项C与选项A错误相同，当t节点与p结点值重复时候，没有向p节点的下一个节点移动。 故正确答案为：选项D。 16．B 【详解】本题考查数组和链表。 数组的元素在内存中连续存储，而链表的节点可以分散在内存的不同位置。故选择B。 17．B 【详解】本题考查Python程序。当不满足合并条件时，需要将当前节点后移（q=p），更新当前节点的后继指针（flink[q][2]=p），然后再获取新的后继节点（p=flink[p][2]）。所以（1）处为①，（2）处为③，（3）处为②。故答案为：B。 18．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 19．D 【详解】本题考查的是链表。head列表里存放的是开始景点的指针。p表示头结点，故第一空应为：p=head[i] ；由于内循环开始前已经把头结点的时间存储到s中，故内循环要先指向下一个指针，再累加时间，故第二空应为：p=a[p][2]，第三空应为：s=s+a[p][1]。选项D正确。 20．C 【详解】本题考查的是VB数据定义。option base在模块级别中使用，用来声明数组下标的缺省下界，option base后面只能是0或者1，由于默认是0，所以是0的时候可以不用option，因此A、B选项错误；DIM    A(6,3  TO  7)定义的是一个35个元素的二维数组，因此C选项正确；数组下标可以是负数,系统只算区间的个数,因此D选项错误。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$