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

第二章 数据的存储方式2024—2025学年高中信息技术粤教版（2019）选修1 一、选择题 1．如下图所示的链表： 假如要查找元素11，共需遍历的次数为（   ） A．5 B．6 C．7 D．8 2．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 3．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 4．有关数组特征描述中，下列说法不正确的是（  ） A．同一数组中，每个数组元素的数据类型是相同的 B．通过数组名和下标可以对数组中任意位置的数组元素进行高效访问 C．数组的存储空间固定不变 D．数组是非顺序存储结构 5．使用链表结构模拟某景区游玩路线，链表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．②④③ 6．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。      图a 图b 若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作： ①“上海”所在节点的next值赋为“杭州”所在节点的next值 ②“上海”所在节点的next值赋为5 ③“杭州”所在节点的next值赋为“上海”所在节点的next值 ④“杭州”所在节点的next值赋为-1 链表更新顺序正确的是（    ） A．③② B．③① C．①④ D．②④ 7．在一个长度为n的数组中的第i个元素（1<=i<=n）之前插入一个新元素时，需向后移动的元素个数为（   ） A．i B．n-i C．n-i+1 D．n-i-1 8．下列关于数据结构的说法，不正确的是（   ） A．数组、链表、队列和栈都是常见的线性表数据结构 B．数组的存储空间是连续的，链表的存储空间可以是不连续的 C．每个链表必定有一个头指针，同一链表中每个节点的结构均相同 D．对数组进行操作时，若某数组元素被删除，数组占用的存储空间会变小 9．利用列表模拟某单向非循环链表a(其中可能存在已被删除的节点），下列程序运行完毕后，变量p肯定表示尾节点的节点位置的是（　　） 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．有如下图所示的单向链表： 从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（   ） A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次 C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个 12．有如下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) 13．小徐使用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]] 14．定义数组 a(1 to 5,5)后,下列哪一个数组元素不存在（ ）。 A．a(1,1) B．a(1,5) C．a(0,1) D．a(5,5) 15．将英文单词“student”中的每个字符按次序以单链表的形式进行存储，操作过程中漏掉了字符 e，存储状态如图所示： 现将字符e存放于1111H处，并按正确的次序插入单链表中，则元素d、e、n的“链接地址”依次是（    ） A．100CH，1014H，1111H B．100CH，1111H，1014H C．1111H，100CH，1014H D．1111H，1014H，100CH 16．使用列表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 17．设有数组定义语句：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) 18．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 19．列表a存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为ha、hb，且a［ha］［0］＜a［hb］［0］，如图1所示。现要将其合并为一个升序链表，头指针为h，结果如图2所示，实现功能的程序段如下：               图1                          图2 q = h = ha p = a[ha][1] k = hb while p ! = -1 and k ! = -1:     if a[p][0] <= a[k][0]:        q = p        p = a[q][1]     else:          if k ! = -1:     a[q][1] = k 方框中应填入的正确代码为（   ） A．a[p][1]=k p=k k=a[p][1] a[p][1]=q B．a[q][1]=k q=k k=a[q][1] a[q][1]=p C．a[q][1]=k k=a[q][1] p=k a[q][1]=p D．a[p][1]=k k=a[p][1] y=b a[p][1]=q A．A B．B C．C D．D 20．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查链表。要在链表中查询元素，只能从链表的头节点开始遍历，11处于链表中的位置为6，因此需要遍历6次，故答案为B。 2．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 3．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 4．D 【详解】本题主要考查数组特征。同一数组中，每个数组元素的数据类型是相同的；通过数组名和下标可以对数组中任意位置的数组元素进行高效访问；数组的存储空间固定不变；数组是顺序存储结构，故本题选D选项。 5．D 【详解】本题考查链表结构。链表结构模拟景区游玩路线的程序中，需要注意如下的逻辑：(1)处：应该设置当前节点的指针p为head[i]，表示第i个大门的开始路线，即p=head[i]。（2）（3）处注意s的初值为a[p][1]，同时最后一个节点取不到，所以应先跳入下一节点再统计当前时间的和，所以答案为②④③，故答案为D选项。 6．A 【详解】本题考查链表的操作。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，则首先杭州所在的节点指向成都，即③“杭州”所在节点的next值赋为“上海”所在节点的next值。其次上海指向杭州，即②“上海”所在节点的next值赋为5。故选A。 7．C 【详解】本题考查数组。在一个长度为n的数组中，第i个元素（1<=i<=n）之前插入一个新元素，从第n个元素开始，直到第i个元素，都需要向后移动一位，一共需要移动n-i+1个元素。例如，一个长度为5的数组，要在第3个元素前插入新元素，那么第5个、第4个和第3个元素都要向后移动，共5-3+1=3个元素。故答案为：C。 8．D 【详解】本题考查的是数据结构。数组的存储空间都是固定不变的，若某数组元素被删除，数组占用的存储空间不会变。故选D。 9．B 【详解】本题主要考查链表数据结构的应用。选项A执行完，变量p表示尾节点的指针域，即-1；选项B执行完，变量p表示尾节点的节点位置；选项C执行完，变量p表示尾节点的前一个节点位置；选项D中，如果存在已被删除的节点，则变量p不一定表示尾节点的节点位置，故本题选B选项。 10．C 【详解】本题考查的知识点是子序列的相关知识。子序列是指数组中连续的若干个元素(至少1个元素)。依题意知：数组a中和最大的子序列为[4,-1,2,1]，和为6。A选项运行结果为4，B选项运行结果为4，C选项运行结果6，D选项运行结果为1。故答案为C选项。 11．D 【详解】本题考查的知识点是链表数据结构。从头指针head指向的节点开始查找数据元素“5”，“5”是第4个元素，共查找4次。删除节点时，找到要删除的节点后，修改其前一个节点的指针域，使其指向要删除节点的下一个节点，后续节点不存在移动。由于删除的是第三个节点，因此头指针head将指向第四个节点，即数据元素为“1”的节点。操作完成后，链表中数据元素的个数为6个。故答案为D选项。 12．A 【详解】本题考查的是链表插入操作。根据题意if条件是在链表头部插入数据；else是在链表中插入数据，p引入头指针，q指向头指针的后继节点，需要遍历整个链表，只需要遍历到最后一个节点即可，若在while条件中令p！=-1，那么逻辑就会出错，p指向尾结点时，q指向-1，data就会和尾结点的后继指针的数据比较，故①应该是令q！=-1。执行插入的过程是p的后继指针指向data的位置即lst[q][1]=len(lst)-1。故本题答案是A选项。 13．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 14．C 【详解】本题主要考查二维数组。定义数组 a(1 to 5,5)，第一个参数的范围是从1到5，第二个参数是5，故数组元素a(0,1)不存在，故本题选C选项。 15．C 【详解】本题考查的是链表的读取。将字母e插入后，其链接地址如下图： 故，d、e、n的“链接地址”依次是111H、100CH、1014H。选项C正确。 16．B 【详解】本题考查链表。据题目描述，列表 d 模拟了一个链表，每个元素是一个列表，包含两部分：数据区域和指针区域。h 是头指针，表示链表的起始位置。具体来说，d 中每个元素的第一个值表示节点的数据，第二个值表示下一个节点在列表 d 中的索引，如果为 -1 表示链表结束。  根据题目给出的 d=[[1,2],[4,4],[3,3],[2,1],[5,-1]]，从头节点开始遍历链表应该按照如下顺序得到数据：1、3、2、4、5，对应选项 B。 17．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 18．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 19．B 【详解】本题考查数据结构链表相关内容。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。在循环中，首先比较两个当前节点的值，如果链表a的当前节点的值小于等于链表b的当前节点的值，则将链表a的当前节点连接到结果链表中，否则将链表b的当前节点连接到结果链表中。a[q][1]=k将当前结果链表节点的下一个节点指针指向链表b的当前节点。然后使用q=k更新当前结果链表节点为链表b的当前节点。接着更新链表b的当前节点为其下一个节点，即k=a[q][1]。最后将当前结果链表节点的下一个节点指针指向链表a的当前节点，即a[q][1]=p。故答案为：B。 20．B 【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$