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

第二章 数据的存储方式 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．下列关于数组的描述，正确的是（    ） A．数组的大小是固定的，但可以有不同类型的数组元素 B．数组的大小是可变的，但所有数组元素的类型必须相同 C．数组的大小是固定的，所有数组元素的类型必须相同 D．数组的大小是可变的，可以有不同类型的数组元素 2．在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 3．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 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．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 6．设有一个5×8的二维数组a，若按行优先的顺序存储数组元素，则元素a[3][5]前面元素的个数为(　　) A．21 B．22 C．29 D．37 7．有如下Python程序段： import random a=[[1,3],[3,4],[5,-1],[2,1],[4,2]];head=0 x=random.randint(2,4) p=q=head while a[q][0]<x and a[q][1] != -1:     p=q;q=a[q][1] a[p][1]=a[q][1] q=head while q != -1:     print(a[q][0],end=" ")     q=a[q][1] 执行该程序段后，输出的结果可能是（   ） A．1 3 5 2 B．2 3 4 5 C．1 2 4 5 D．1 3 5 4 8．某Python程序如下： a=[[3,2],[2,3],[7,1],[1,0]] p=head=0 while a[p][1]!=head:     print(a[p][0],end='->')     p=a[p][1] print(a[p][0]) 程序运行后，输出的结果是（   ） A．3->7->2->1 B．3->2->7->1 C．1->7->3->2 D．3->7->1->2 9．使用列表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．②④ 10．现有单链表中的某两个节点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．②③① 11．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（    ）来表示。 A．数组 B．链表 C．栈 D．队列 12．一维数组a（下标从0开始）中元素值依次为11--100之间的奇数，则数组元素a[k]的值是（  ） A．2*k+10 B．2*k+11 C．2*k+12 D．2*k+13 13．设双向链表的某中间节点p由一个一维数组表示，其中k[p][1]和k[p][2]分别是该节点的前驱及后继。现要求从该链表中删除结点p，则下面语句序列中正确的是（   ） A．k[p][1][2]=k[p][2]；k[p][2][1]=k[p][1] B．k[k[p][1]][2]=k[p][2]；k[k[p][2]][1]=k[p][1] C．k[p][2][2]=k[p][1]；k[p][1][1]=k[p][2] D．k[k[p][2]][2]=k[p][1]；k[k[p][1]][1]=k[p][2] 14．创建一个空链表时，通常会设置什么来表示链表的起始（   ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 15．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 16．给定两个相交的单链表均存储在列表link中，头节点分别是headA和headB，用最少的循环次数找出两个链表相交的起始点。如图所示，两个链表在节点c1开始相交。 p1,p2=headA,headB c=0 while (1) :     if p1!=-1:         p1=link[p1][1]     else:         (2)     if p2!=-1:         p2=link[p2][1]     else:         (3)     c+=1 print(f'循环{c}次后找到交叉点{link[p1][0]}') 上述程序段划线出可选的代码为： ①p1!=p2      ②p1!=-1 and p2!=-1      ③p1=headB      ④p2=headA 则(1)、(2)、(3)处可选的代码依次为（   ） A．①③④ B．②③④ C．①④③ D．②④③ 17．有Python程序段如下： #链表1st中的每个元素由数据和指针两个数据项组成，其中数据可能重复且呈升序排列 p1＝head p2＝lst[pl][1] while p2!＝-1： if 1st[p1][0]==1st[p2][0]： p2=1st[p2][1] 1st[p1][1]=p2 else： p1＝p2 p2＝1st[p2][1] 若链表1st的初始状态为，则执行完该程序段后链表1st更新为（    ） A． B． C． D． 18．使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有的偶数项（头节点为该链表的第1项），部分代码如下： p=head             #head指向该链表的头节点 while p!=-1: q=a[p][1]   if （1） : （2） p=a[p][1] 上述程序段划线处可选语句为 ①q!=-1        ②a[q][1]!=-1        ③a[q][1]=a[p][1]        ④a[p][1]=a[q][1] 则（1）（2）处填入的语句依次为（   ） A．①③ B．①④ C．②③ D．②④ 19．有如下 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．②③① 20．找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下： #链表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 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题主要考查数组的描述。数组的大小是固定的，所有数组元素的类型必须相同，故本题选C选项。 2．B 【详解】本题主要考查链表数据结构。若要在p节点之后插入新的节点x（x作为p的新后继节点），则x的指针域指向p的下一个节点，即a[x][1]=a[p][1]。其次将x与p连接起来，即p的指针域指向x，即a[p][1]=x，故本题选B选项。 3．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 4．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 5．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 6．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选项。 7．C 【详解】本题考查Python程序。给定一个链表a，每个节点包含两个元素，第一个元素是当前节点的值，第二个元素是指向下一个节点的索引。程序段中使用了链表来表示一个有序序列，并根据随机生成的数x对链表进行部分遍历和删除操作。程序段的大致思路：给定一个有序链表a和一个随机数x。从链表头开始遍历链表，找到第一个值大于等于x或者指向下一个节点为空的节点，记录当前节点的索引为p。删除索引为p的节点，并将其前一个节点的指针指向其后一个节点。重新遍历链表，并输出节点的值。根据以上思路，当x为2时，输出的结果为：1 3 4 5；当x为3时，输出的结果为：1 2 4 5；当x为4时，输出的结果为：1 2 3 5。故答案为：C。 8．A 【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3->7->2->1。选项A正确。 9．C 【详解】本题考查程序分析。（1）当头节点为奇数时，需要更新头节点。则移动头节点。故h=d[h][1]。（2）当p节点为奇数时候，需要删除该节点，将p的后继节点接到p的前驱结点q的下一个节点指针上。故d[q][1]=d[p][1]。故正确答案为选项C。 10．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。 11．B 【详解】本题考查的是链表相关知识。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。寻宝游戏中通过一个线索找到下一个线索，最好用链表来表示，故选B选项。 12．B 【详解】本题主要考查数组。一维数组a（下标从0开始）中元素值依次为11--100之间的奇数，2*k是偶数，2*k+11表示11~100之间的奇数（k从0开始），故本题选B选项。 13．B 【详解】本题考查的是双向链表的删除。删除节点p，则使当前节点p的前驱指针指向p的后续节点，p的后续节点的前驱指针指向p的前驱节点，故选B。 14．C 【详解】本题考查链表。创建空链表时，通常会将头指针设置为一个表示空的值，如NULL（在C/C++中）或-1（在某些特定场景下的约定）。故选择C。 15．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 16．C 【详解】本题考查数据结构。首先，需要判断两个指针p1和p2是否相等，即链表是否相交。这可以通过比较节点的地址来实现，因此划线处应选择代码①p1!=p2。 当p1指针达到链表末尾时，应该将其重新指向另一个链表的头节点，以继续遍历。因此，划线处应选择代码③p1=headB。 同样，当p2指针达到链表末尾时，应该将其重新指向另一个链表的头节点。因此，划线处应选择代码④p2=headA。故答案为：C。 17．A 【详解】本题考查链表。 该程序功能为，去除链表中的重复数据。通过观察链表图，可知选项A为去除重复。故正确答案为：选项A。 18．B 【详解】本题主要考查链表数据结构及Python程序实现。头节点为该链表的第1项，p的初值指向head，q为p的下一个节点，因此每次删除q节点即可，删除之前需要判断q是否为-1，故if判断条件是q!=-1，删除q节点的方法是，p的后继节点指向q的后继节点，即a[p][1]=a[q][1]，选项B符合题意，故选B。 19．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选项。 20．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。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$