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

第二章数据与链表同步作业2023—2024学年高中信息技术浙教版（2019）选修1 1．链表中的节点通常包含哪两部分（   ） A．数据域和控制域 B．数据域和指针域 C．指令域和地址域 D．标志域和内容域 2．有如下 Python程序，用于判断链表是否为回文链表（回文链表是指正序遍历和逆序遍历得到的结点顺序一致的链表），则划线处代码是（   ） a=[[1,1],[2,2],[8,3],[2,4],[1,-1]] st=[];head=0;flag=True slow, fast=head, head while ① :     st.append (a[slow][o])     slow=a[slow][1]     fast=a[a[fast][1]][1]     if ② :         slow=a[slow][1] while slow!=-1:     if st.pop () !=a[slow][0]:         flag=False         slow=a[slow][1] if flag:     print("是回文链表!") else:     print("不是回文链表!") A．①fast!=-1 or a[fast][1]!=-1    ②fast!=-1 B．①fast!=-1 or a[fast][1]!=-1    ②a[fast][1]!=-1 C．①fast!=-1 and a[fast][1]!=-1   ②fast!=-1 D．①fast!=-1 and a[fast][1]!=-1   ②a[fast][1]!=-1 3．子序列是指数组中连续的若干个元素(至少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． 4．有如下 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．②③① 5．使用列表L模拟链表结构，每个节点包含数据区域和指针区域，现要删除该链表中的某一元素，示例输出结果如图所示，实现该功能的程序段如下： def delete(data,p):     head=0     if p==data[head][0]:         head=data[head][1]         print("找到删除数据",)     else:         cur=pre=head     while ______:         pre=cur         cur=data[cur][1]     if cur!=-1:         ______         print("找到删除数据",)     else:         print("未找到删除数据")     return head L=[[9,3],[4,2],[8,4],[7,1],[6,5],[5,-1]] key=int(input("请输入要删除的数据:")) head=delete(L, key) #输出删除后的结果程序省略 则下划线中应填入的正确代码依次为（   ） ①data[cur][0]!=p and data[cur][1]!=-1  ②data[cur][0]!=p and cur!=-1 ③data[pre][1]=data[cur][1]  ④data[cur][1]=data[pre][1] A．①③ B．①④ C．②③ D．②④ 6．有1个栈，栈底到栈顶的元素依次为a，b，c，d，e，f，g，有1个队列，初始为空。约定：P操作是指出栈后入队，Q操作是指仅出栈，R操作是指队列中1个元素出队后入队，S操作是指队列中1个元素出队。则经过PQPSRQPR系列操作后，队列中队首到队尾的元素依次为（    ） A．GFEDC B．GEC C．CE D．C 7．单向链表和双向链表的区别在于（   ） A．单向链表每个节点有一个指针，双向链表每个节点有两个指针 B．单向链表的节点存储空间小于双向链表 C．单向链表可以循环，双向链表不可以 D．单向链表的访问速度优于双向链表 8．以下代码可实现把多个升序链表合并成一个升序链表 class ListNode:     def __init__(self, val=0, next=None):         self.val = val         self.next = next def mergeTwoLists(list1, list2):     if （1） or （2） :         list1, list2 = list2, list1     if （3） :         list1.next =（4）     return list1 def mergeKLists(list1):     if （5） :     return None     if len(list1) == 1:         return list1[0]     mid = len(list1) // 2     left, right = mergeKLists(list1[:mid]), mergeKLists(list1[mid:])     return mergeTwoLists(left, right) 划线处（1）（2）（3）（4）（5）应填入的正确代码有 ①(list2 and list1.val > list2.val)    ②(list1 and list2.val > list1.val)    ③list1,list2=list2,list1 ④mergeTwoLists(list1.next, list2)  ⑤mergeTwoLists(list1, list2.next)  ⑥not list1  ⑦not list2 ⑧list1   ⑨list2 则正确代码的顺序是（   ） A．⑥①⑧④⑥ B．⑦②⑥④⑥ C．⑥①⑨④⑥ D．⑦②⑨④⑥ 9．下列关于数据结构的说法，不正确的是（   ） A．数组、链表、队列和栈都是常见的线性表数据结构 B．数组的存储空间是连续的，链表的存储空间可以是不连续的 C．每个链表必定有一个头指针，同一链表中每个节点的结构均相同 D．对数组进行操作时，若某数组元素被删除，数组占用的存储空间会变小 10．数组元素 a[0]至a[n-1]依次存放着n个数据，其中前 n-1个数据不重复且有序，现需要将x（与前 n-1个数据不重复） 插入到数组中，使数组仍然有序。例如: n为5，数组 a为[0,5,10,20,20] ， x为8，插入操作后 a为[0,5,8,10,20]。实现该功能的程序段如下： i=0 while i<n-1 and a[i]<x:     i+=1     for k in range(        a[k]= a[k-1]     a[i]=x 方框中应填入的正确代码为（   ） A．n,i,-1 B．n-1,i,-1 C．i+1,n D．i-1,n-1 11．有一组含有9个元素的有序链表：1->3->5->6->8->11->15->18->20，现为该链表增设关键节点，建立索引，下列说法不正确的是（    ） A．一级索引中的关键节点为1,5,8,15,20 B．二级索引中的关键节点为1,8,20 C．若要在建立的一级索引的基础上插入元素7，则需要比较3次即可找到7插入的位置 D．若要在建立的二级索引的基础上查找元素18，则需要比较4次就可以找到元素18 12．某个正整数的每位数依次存储在链表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 13．使用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" 14．小徐使用Python列表模拟建立单向有序链表，初始列表a=[],head=None,列表数据项作为节点，节点的第1个元素为数据域，第2个元素为指针域,指向下一个节点索引（若为None则该节点为尾节点）。执行程序后，输入23,0,2,8,66,列表a的值为[[23,4],[0,2],[2,3],[8,0],[66,None]], 此时head的值为1,下列说法不正确的是（   ） A．遍历该链表数据域输出依次分0,2,8,23,66 B．若继续输入11,则列表数据为[[23,4],[0,2],[2,3],[8,5],[66,None],[11,0]] C．若删除链表节点[0,2],则head的值为0 D．若删除链表节点[23,4],则列表数据为[[0,1],[2,2],[8,3],[66,None]] 15．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 16．使用链表结构模拟某校游玩路线，链表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．②④③ 17．设有一个5×8的二维数组a，若按行优先的顺序存储数组元素，则元素a[3][5]前面元素的个数为(　　) A．21 B．22 C．29 D．37 18．如下图所示的链表： 假如要查找元素11，共需遍历的次数为（   ） A．5 B．6 C．7 D．8 19．有如下 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 20．从链表b中随机取出6个不同节点元素存入数组a，方框中填入的代码不能实现该功能的为（   ） import random b=[["A",1],[ "B",2],[ "C",3],[ "D",4],[ "E",5],[ "F",6],[ "G",7],[ "H",-1]] head=0 a=[ ] for i in range(6):     k=random.randint(0,len(b)-i-1) if k==0:     a.append(b[head][0])     head=b[head][1] else: print（a） A． p=head for j in range(k):     pre=p     p=b[p][1]     b[pre][1]=b[p][1]     a.append(b[p][0]) B． p=head for j in range(k+1):     pre=p     p=b[p][1]     a.append(b[p][0])     b[pre][1]=b[p][1] C． p=head;i=0 while i＜k:     i=i+1；pre=p     p=b[p][1]     b[pre][1]=b[p][1]     a.append(b[p][0]) D． p=head;i=0 while i＜k-1:     i=i+1     p=b[p][1]     a.append(b[b[p][1]][0])     b[p][1]= b[b[p][1]][1] A．A B．B C．C D．D 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查链表。数据域：用于存储节点的数据信息。指针域：用于存储指向下一个节点的指针。故选择B。 2．C 【详解】本题考查程序分析。while循环缺少条件，保证链表没有到尾部，继续循环。if判断条件为，当fast指针位置有效，没有到结尾，则移动slow指针。故选择C选项。 3．C 【详解】本题考查的知识点是子序列的相关知识。子序列是指数组中连续的若干个元素(至少1个元素)。依题意知：数组a中和最大的子序列为[4,-1,2,1]，和为6。A选项运行结果为4，B选项运行结果为4，C选项运行结果6，D选项运行结果为1。故答案为C选项。 4．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选项。 5．C 【详解】本题考查链表。循环缺少条件判断，判断当前节点数据是否是要删除的数据，且不是最后节点，那么就继续循环指向下一个节点数据，遍历链表。故代码为data[cur][0]!=p and cur!=-1。根据代码if cur!=-1可知，当循环条件不是因为最后一个节点结束的，那么是因为找到要删除的节点结束的，故执行删除节点操作。删除节点就是当前节点的下一个节点接到当前节点的前趋节点。故代码为data[pre][1]=data[cur][1]。故正确答案为选项C。 6．C 【详解】本题考查数据结构相关知识。PQP操作完成，栈底到栈顶的元素依次为a，b，c，d，队列队列首到队尾为g，e。SRQ操作完成后，栈底到栈顶的元素依次为a，b，c，队列队列首到队尾为e。PR操作完成后，栈底到栈顶的元素依次为a，b，队列队列首到队尾为c，e。故正确答案为选项C。 7．A 【详解】本题考查链表。单向链表和双向链表的区别主要在于指针的数量和存储空间的不同。单向链表每个节点只有一个指向下一个节点的指针，而双向链表每个节点有两个指针，分别指向前一个节点和下一个节点，因此双向链表的节点存储空间比单向链表大。故答案为：A。 8．A 【详解】本题考查链表。（1）如果第一个链表为空，则直接返回第二个链表，故选⑥。（2）如果第二个链表不为空且第一个链表的值大于第二个链表的值，则交换两个链表，使得较小的值在前。故选①。（3）在递归合并两个链表时，将当前较小值的节点作为合并结果的头节点。故选⑧。（4）递归地合并剩余的链表部分。故选④。（5）如果链表数组为空，则返回None。故选⑥。故答案为：A。 9．D 【详解】本题考查的是数据结构。数组的存储空间都是固定不变的，若某数组元素被删除，数组占用的存储空间不会变。故选D。 10．B 【详解】本题考查的是Python数组操作。插入元素需要数组后移操作，且先移最后一个元素，第一次移动a[n-2]到n-1位置，所以开始值为：n-1，选项B正确。 11．C 【详解】本题主要考查链表数据结构。有序链表：1->3->5->6->8->11->15->18->20，则一级索引中的关键节点为1,5,8,15,20（取奇数位）；二级索引中的关键节点为1,8,20（取首尾以及中间元素）；若要在建立的一级索引的基础上插入元素7，则需要比较4次即可找到7插入的位置，首先分别与1、5、8比较，其次与6比较共4次；若要在建立的二级索引的基础上查找元素18，则需要比较4次就可以找到元素18，分别与8、20比较，再与19、18比较，共4次，故本题选C选项。 12．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。 13．D 【详解】本题主要考查链表的操作。head=3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依次类推，依次输出各节点数据域的值，内容为"rabbit","cat","dog","pig"，故本题选D选项。 14．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 15．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 16．D 【详解】本题考查的是链表。head列表里存放的是开始景点的指针。p表示头结点，故第一空应为：p=head[i] ；由于内循环开始前已经把头结点的时间存储到s中，故内循环要先指向下一个指针，再累加时间，故第二空应为：p=a[p][2]，第三空应为：s=s+a[p][1]。选项D正确。 17．C 【详解】本题主要考查Python二维数组结构。有一个5 × 8的二维数组a，若按行优先的顺序存储数组元素，则元素a 3| 5|前面元素的个数为29个。其中第一行为a0开头共8个元素，第二行以a [1]开头为8个元素，第三行以a [2]开头为8个元素，第四行以a [3]开头，到a [3] [5]前面有5个元素，所以共有3* 8+ 5 = 29，故本题选C选项。 18．B 【详解】本题考查链表。要在链表中查询元素，只能从链表的头节点开始遍历，11处于链表中的位置为6，因此需要遍历6次，故答案为B。 19．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。 20．B 【详解】本题考查Python以及链表。B选项的代码：for j in range(k+1):该代码在遍历链表时多取了一次节点，导致取出的节点数不符合要求。故答案为：B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$