第二章 数据的存储方式 2023-2024学年高中信息技术粤教版(2019) 选修1

第二章 数据的存储方式 一、选择题 1．链表相比于数组，在哪种情况下表现得更为高效（   ） A．需要频繁查找元素 B．需要随机访问元素 C．需要频繁在中间插入和删除元素 D．需要存储大量静态数据 2．如下Python程序段的功能是将链表中奇数位置的节点和偶数位置的节点分别排序排列。如原始链表为，执行该程序后的新链表为。 a=[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，-1]] head=1；odd=head even=a[odd][1]；tmp=even while a[odd][1]！=-1 and a[even][1]！=-1：      ①     odd=a[odd][1]      ②     even=a[even][1] a[odd][1]=tmp print（a） 上述程序段中①、②处语句和运行结果分别为（    ） A．a[odd][1]=a[even][1]    a[even][1]=a[odd][1]     [[20，2]，[6，0]，[35，3]，[18，4]，[27，5]，[59，-1]] B．a[even][1]=a[odd][1]    a[odd][1]=a[even][1]     [[20，2]，[6，3]，[35，4]，[18，0]，[27，5]，[59，-1]] C．a[odd][1]=a[even][1]    a[even][1]=a[odd][1]     [[20，2]，[6，3]，[35，4]，[18，0]，[27，5]，[59，-1]] D．a[even][1]=a[odd][1]    a[odd][1]=a[even][1]     [[20，2]，[6，0]，[35，3]，[18，4]，[27，5]，[59，-1]] 3．某个正整数的每位数依次存储在链表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 4．数组a的数据存放情况如下表，则当i=2时，a[6/i-1]的值是（     ）。 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 48 52 98 26 47 22 82 33 A．98 B．26 C．52 D．22 5．现采用新的排队方案为小明、小红、小丽、小辉四人排队， Python程序段如下： linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]] def reset(head):    if linklist[head][1]==- 1 or head==- 1:       return head    else:       new_head=reset(linklist[head][1])       linklist[linklist[head][1]][1]=head       linklist[head][1]=- 1    return new head p=h=reset(0) while p!=- 1:    print(linklist[p][0],end="")    p=linklist[p][1] 执行该程序段后，输出的结果是（    ） A．小明小红小丽小辉 B．小明小辉小丽小红 C．小辉小丽小红小明 D．小明小丽小红小辉 6．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 7．有如下图所示的单向链表： 从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（   ） A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次 C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个 8．有如下 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 9．语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （    ） A．二维单精度实型数组和二双精度型数组 B．二维长整型数组和二维单精度实型数组 C．一维单精度实型数组和二维整型数组 D．一维长整型数组和二维双精度型数组 10．子序列是指数组中连续的若干个元素(至少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． 11．栈和队列的顺序存储结构通常使用哪种数据结构（     ） A．链表 B．数组 C．树 D．图 12．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（    ） A．删除该链表中的最后一个节点 B．删除该链表中的第一个节点 C．在该链表第一个节点前插入一个新节点 D．在该链表最后一个节点后插入一个新节点 13．用链表模拟队列操作（队列长度大于1），链表的每个节点包含数据区域和指针区域。指针head指向队列的第一个元素，指针tail指向队列的最后一个元素，如图所示。现执行n次“出队后立即入队”操作，实现该功能的Python程序段如下： k=1 while k<=n:     p=head     tail=p     k+=1 数据区域 指针区域 0 “A” 4 1 “B” 2 tail→ 2 “C” -1 head→ 3 “D” 0 4 “E” 1 上述程序段中方框处可选代码有： ①head=que[head][1]    ②que[tail][1]=head    ③que[head][1]=-1    ④que[p][1]=-1 则方框内应填入的正确代码顺序为（    ） A．①②③ B．①②④ C．②①③ D．②①④ 14．创建一个空链表时，通常会设置什么来表示链表的起始（   ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 15．使用列表a模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，head为头指针，如a=[["Z"，2]，["J"，0]，["H"，-1]，["S"，1]]，head=3，现要修改该链表各节点的链接关系，修改结果为a=[["Z"，1]，["J"，3]，["H"，0]，["S"，-1]]，head=2。实现该功能的程序段如下，方框中应填入的正确代码为（   ） q=head;p=-1 while q!=-1：      head=p A． a[q][1]=p nxt=a[q][1] p=q q=nxt B． a[q][1]=p nxt=a[q][1] q=nxt p=q C． nxt=a[q][1] a[q][1]=p q=nxt p=q D．nxt=a[q][1] a[q][1]=p p=q q=nxt A．A B．B C．C D．D 16．设有数组定义语句：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) 17．下列关于链表节点插入操作的描述，哪个是正确的（   ） A．插入操作总是从链表头部开始 B．只需要修改新节点的指针域即可完成插入 C．必须先找到插入位置的前驱节点，再修改前驱节点的指针域 D．链表插入操作的时间复杂度总是O(1) 18．一头指针 head=2 的单向链表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通过以下 Python 程序段，转换为原链表的逆序链表，即头指针 head=1，L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。 q=-1 p=head    #head 为原链表头指针 while p!=-1 : tmp=L[p][1] head=q 上述程序段中方框处可选的语句为：①p=tmp    ②q=p    ③L[p][1]=q 则方框处语句依次为(     ) A．③②① B．③①② C．①③② D．①②③ 19．在Python中可以使用列表模拟单向链表，如链表中的节点p，a[p] [0]存储p节点的数据，a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x（x作为p的新后继节点），需要执行的语句是（    ） A．a[p][1]=x; a[x][1]=a[p][1] B．a[x][1]=a[p][1]; a[p][1]=x C．a[p][0]=x; a[x][0]=a[p][0] D．a[x][0]=a[p][0]; a[p][0]=x 20．现有单链表中的某两个节点a、b，其中b为a的后继。现要将节点b与其后继节点c进行交换，其余部分不变，如图所示。 初始链表: 交换后链表: 若节点a、b的指针域表示为next[a]、next[b]，可选语句为： ①next[next[a]] = b  ②next[a] = next[b]  ③next[b] = next[next[b]] 则正确的顺序是（    ） A．①③② B．③①② C．②①③ D．②③① 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查链表和数组。选项C，需要频繁在中间插入和删除元素。链表由于其动态的内存分配和指针链接特性，使得在链表中间插入和删除元素比数组更为高效。故选择C。 2．A 【详解】本题考查链表。节点odd的指针链接着下一个节点的下一个节点，这时odd节点移动一次，这时将odd节点的下一个节点链接到even的下一个节点。故排除选项B、D。按照程序执行一次，列表第二个元素变化为[6,0]，排除C。故选择A。 3．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。 4．C 【详解】本题主要考查数组知识点。当i=2时，a[6/i-1]= a[2]=52，故本题选C选项。 5．C 【详解】本题主要考查链表数据结构及Python程序实现。分析程序可知，reset(head)函数实现将列表linklist逆着连接起来，linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]]，因此执行该程序段后，输出的结果是小辉小丽小红小明，故本题选C选项。 6．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 7．D 【详解】本题考查的知识点是链表数据结构。从头指针head指向的节点开始查找数据元素“5”，“5”是第4个元素，共查找4次。删除节点时，找到要删除的节点后，修改其前一个节点的指针域，使其指向要删除节点的下一个节点，后续节点不存在移动。由于删除的是第三个节点，因此头指针head将指向第四个节点，即数据元素为“1”的节点。操作完成后，链表中数据元素的个数为6个。故答案为D选项。 8．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。 9．D 【详解】本题主要考查数组的定义。符号“%”表示短整型，“&amp;”表示长整型，“！”表示单精度浮点型，“#”表示双精度浮点型，故语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为一维长整型数组和二维双精度型数组，故本题选D选项。 10．C 【详解】本题考查的知识点是子序列的相关知识。子序列是指数组中连续的若干个元素(至少1个元素)。依题意知：数组a中和最大的子序列为[4,-1,2,1]，和为6。A选项运行结果为4，B选项运行结果为4，C选项运行结果6，D选项运行结果为1。故答案为C选项。 11．B 【详解】本题考查数据结构。栈和队列的顺序存储结构通常使用数组实现，因为数组支持快速的随机访问，可以高效地进行元素的入栈、出栈、入队和出队操作。故答案为：B。 12．A 【详解】本题主要考查链表数据结构。删除该链表中的第一个节点、在该链表第一个节点前插入一个新节点、在该链表最后一个节点后插入一个新节点均不需要遍历多个节点，只需一次操作即可完成。删除该链表中的最后一个节点需要从头开始遍历，故本题选A选项。 13．D 【详解】本题考查的是链表操作。从图中可以知道，出队后立即入队，反映到链表上就是：tail指针指向head，head指针后移，让原head位置变为队尾（修改p的指针域为-1），即②①④。故选D。 14．C 【详解】本题考查链表。创建空链表时，通常会将头指针设置为一个表示空的值，如NULL（在C/C++中）或-1（在某些特定场景下的约定）。故选择C。 15．D 【详解】本题考查的是链表操作。原始数据是：S→J→Z→H，修改后为：H→Z→J→S，这是一个链表的倒置。思路是遍历原来的链表把每个遍历到的结点头插入一个新的链表头中。具体操作，将遍历到的结点的指针域指向新的链表的头节点，同时修改新链表的头节点（a[q][1]=p，p=q）。为了遍历原来的链表，则要保留遍历到的结点的指针域为头指针（nxt=a[q][1]这要先执行）。故选项D正确。 16．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 17．C 【详解】本题考查链表。必须先找到插入位置的前驱节点，再修改前驱节点的指针域，C该选项描述了链表插入操作的正确步骤，需要先定位到插入位置的前驱节点，然后修改其指针指向新节点。故答案为：C。 18．A 【详解】本题主要考查链表及Python程序实现。因为是逆序链表，q的初值为-1，故L[p][1]即p的下一个节点指向q，③L[p][1]=q。由题干单项链表可知，接下来更新q的值为p即②q=p，p的值为tmp①p=tmp，故本题选A选项。 19．B 【详解】本题主要考查链表数据结构。若要在p节点之后插入新的节点x（x作为p的新后继节点），则x的指针域指向p的下一个节点，即a[x][1]=a[p][1]。其次将x与p连接起来，即p的指针域指向x，即a[p][1]=x，故本题选B选项。 20．D 【详解】本题考查链表。要实现将节点b与其后继节点c进行交换，第一步：将节点a的指针域指向节点c，即next[a]=next[b]，这样就将节点a与节点c连接起来了。第二步：将节点b的指针域指向节点c的后继节点，即next[b]=next[next[b]]，这样就将节点b与其原来的后继节点断开了。第三步：将节点c的指针域指向节点b，即next[next[a]]=b，这样就将节点c的后继节点变为节点b。故答案为：D。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$