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

第二章 数据的存储方式 一、选择题 1．如果一个链表的头指针为head，要访问链表中第i个节点，需要进行几次指针移动（   ） A．i次 B．i-1次 C．i+1次 D．无法确定，取决于链表长度 2．下列哪个特性不属于数组的特点（   ） A．所有元素的数据类型相同 B．可以通过下标直接访问任意元素 C．存储空间固定不变 D．插入和删除元素操作高效 3．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 4．定义数组 a(1 to 5,5)后,下列哪一个数组元素不存在（ ）。 A．a(1,1) B．a(1,5) C．a(0,1) D．a(5,5) 5．小徐使用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]] 6．如下图所示的链表： 假如要查找元素11，共需遍历的次数为（   ） A．5 B．6 C．7 D．8 7．使用列表da和db模拟2个链表结构（节点数均大于0），每个节点包含数据区域和指针区域，ha和hb分别为链表da和db的头指针。链表中各节点已按数据区域中数值由小到大排列，且链表da头节点值小于链表db头节点值。现要将链表db中数据合并到链表da中，且保持升序排列。实现该功能的程序段如下，方框中应填入的正确代码为（    ） q=ha while hb!=-1： p=da[q][1] A． if p==-1 or da[p][0]>db[hb][0]： da．append（[db[hb][0]，p]） da[q][1]=len（da）-1 hb=db[hb][1]q=da[q][1] B． if p==-1 or da[p][0]>db[hb][0]： da．append（[db[hb][0]，p]） da[q][1]=len（da）-1 hb=db[hb][1] q=da[q][1] C． if p==-1 or da[p][0]>db[hb][0]： da．append（[db[hb][0]，p]） da[q][1]=len（da）-1 hb=db[hb][1]q=p D． if p==-1 or da[p][0]>db[hb][0]： da．append（[db[hb][0]，p]） da[q][1]=len（da）-1hb=db[hb][1] q=da[q][1] A．A B．B C．C D．D 8．有个列表n=[‘水果’, ‘砂糖橘’,’苹果’, ‘橙子’],请把列表中’苹果’改为’橘子’，选出修改正确的语句（   ） A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’] 9．一头指针 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．①②③ 10．使用列表模拟单向链表，链表中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．②④ 11．某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 12．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 13．数组元素 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 14．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果        A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃” 15．使用列表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 16．使用列表a模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，head为头指针。链表中各节点已按数据区域中数值的绝对值由大到小排列，如图1所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由大到小排列，结果如图2所示。实现该功能的Python程序段如下：              图1                          图2 flag=False；p=head head=-1    #head作为新链表的头指针 while p!=-1:     k=a[p][1]     if flag==False:         a[p][1]=head;head=p         if ① :             flag=True;q=head     else:         a[p][1]=a[q][1];a[q][1]=p         if ② :             q=a[q][1]     p=k 划线处应填入的正确代码为（   ） A．①a[p][0]>0   ②a[p][0]>0 B．①a[p][0]>0   ②a[p][0]<0 C．a[p][0]<0   ②a[p][0]<0 D．①a[p][0]<0   ②a[p][0]>0 二、操作题 17．最幸运的人。某公司开展工会活动，其中有一个游戏是“谁是最幸运的人”，游戏规则如下：参加活动的员工每人领取一个编号（1～n），然后让他们按编号顺序围成一圈，由公司老总掷骰子的方法决定报数m（1～6），游戏开始时，从编号1号的人开始1～m报数，凡报到m的人退圈，接着由退圈的下一位开始重新从1开始报数，直到圈上最后只剩下一个人为止，他就是最幸运的人，将获得一份神秘礼物。程序运行界面如图所示。 输入活动人数n:100 报数m为:6 依次退圈的人的编号为: 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 2 9 16 23 31 38 45 52 59 67 74 81 88 95 3 11 20 28 37 46 55 63 71 80 89 98 7 17 27 39 49 58 69 79 91 100 13 25 35 50 62 75 86 99 14 29 43 57 73 87 4 21 40 56 76 93 10 33 53 77 97 22 47 70 1 32 64 92 26 65 5 44 85 41 94 61 19 8 83 15 51 34 82 最幸运的人(编号)是：68 使用链表方式实现的Python程序如下，请回答下列问题： import random list1=[] n=int(input(′输入活动人数n:′)) m=random.randint(1,6) #报数 print(′报数m为:′,m) for i in range(n-1): #初始化单向循环链表     list1.append([i+1,i+1]) #指针域存放后继节点的索引     ① head=0 left=n print(′依次退圈的人的编号为:′) while left>1: #删除节点直到只剩下1节点为止     for i in range(m-2):         head=list1[head][1]         t=list1[head][1]         print(list1[t][0],end=" ")         ②     head=list1[head][1]　#新一轮报数起点重新定位为删除节点的后继节点     left-=1 print(" 最幸运的人(编号)是:",③ ) （1）若活动人数为10人，报数为5，则最幸运的人的编号为 。 （2）请在程序划线处填入合适的代码。 划线①处应填入的代码为： ；划线②处应填入的代码为： ；划线③处应填入的代码为： 。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查链表。要访问链表中第i个节点，从头节点开始需经过i-1个节点的指针移动。故选择B。 2．D 【详解】本题考查数组。数组在插入和删除元素时通常需要移动大量元素，效率相对较低。故选择D。 3．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 4．C 【详解】本题主要考查二维数组。定义数组 a(1 to 5,5)，第一个参数的范围是从1到5，第二个参数是5，故数组元素a(0,1)不存在，故本题选C选项。 5．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 6．B 【详解】本题考查链表。要在链表中查询元素，只能从链表的头节点开始遍历，11处于链表中的位置为6，因此需要遍历6次，故答案为B。 7．A 【详解】本题考查数据结构链表相关内容。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。结合题目内容，分析程序段，要将链表db中数据合并到链表da中，且保持升序排列，可以考虑：（1）在两个链表均未到表尾时，若da[p][0]>db[hb][0]成立，则将db[hb][0]追加到da当前位置，再继续通过遍历两个链表；若不成立，再对比db链表后继元素；（2）若da已到表尾，db还存在元素，则将db剩余元素追加到da中；（3）若db已到表尾，da还存在元素，则不需要再移动元素；对比四个选项，A选项可以满足题目要求。故本题答案是A选项。 8．A 【详解】本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 9．A 【详解】本题主要考查链表及Python程序实现。因为是逆序链表，q的初值为-1，故L[p][1]即p的下一个节点指向q，③L[p][1]=q。由题干单项链表可知，接下来更新q的值为p即②q=p，p的值为tmp①p=tmp，故本题选A选项。 10．B 【详解】本题主要考查链表数据结构及Python程序实现。头节点为该链表的第1项，p的初值指向head，q为p的下一个节点，因此每次删除q节点即可，删除之前需要判断q是否为-1，故if判断条件是q!=-1，删除q节点的方法是，p的后继节点指向q的后继节点，即a[p][1]=a[q][1]，选项B符合题意，故选B。 11．A 【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3->7->2->1。选项A正确。 12．B 【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。 13．B 【详解】本题考查的是Python数组操作。插入元素需要数组后移操作，且先移最后一个元素，第一次移动a[n-2]到n-1位置，所以开始值为：n-1，选项B正确。 14．B 【详解】本题考查的是pandas库相关知识。Series中如果没有指定索引，索引值就从 0 开始，故s[2]值为3，故选项B正确。 15．B 【详解】本题考查链表。据题目描述，列表 d 模拟了一个链表，每个元素是一个列表，包含两部分：数据区域和指针区域。h 是头指针，表示链表的起始位置。具体来说，d 中每个元素的第一个值表示节点的数据，第二个值表示下一个节点在列表 d 中的索引，如果为 -1 表示链表结束。  根据题目给出的 d=[[1,2],[4,4],[3,3],[2,1],[5,-1]]，从头节点开始遍历链表应该按照如下顺序得到数据：1、3、2、4、5，对应选项 B。 16．A 【详解】本题考查程序分析。数据区域中数值的绝对值由大到小排列，若数据区域a[p][0]的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可。若数据区域d[p][0]的数值为负数，则原先的链表各节点关系需要重新指向，由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越小，这样每一个当前节点p的负数肯定是当前链表中最小的数，因此该数应该变为最小的头节点，采用头插法可以实现，故本题选A。 17． 3 list1.append([n，0]) list1[head][1]=list1[t][1] list1[head][0] 【详解】本题主要考查的是链表的综合应用。（1）n=10，m=5，依次退圈的人的编号为：5，10，6，2，9，8，1，4，7，最后圈上只剩下3号，因此最幸运的人（编号）是3号。（2）首先，将人的编号构建一个单向链表，节点的指针域存放的是后继节点的索引号，将最后一个节点的指针域存储第一个人的编号，这样就构建了一个循环链表，因此程序①处代码为list1.append([n，0])；要处理报到m的人退圈操作，需要找到退圈的人的前一个人，指针t指向当前出圈的人，指针head指向出圈人的前一位，要删除指针t指向的节点，只需将head指向的节点的指针域赋值为t节点的指针域，因此程序②处代码为list1[head][1]=list1[t][1]；最后圈上剩下的人是head指向的节点，因此只要输出head指向的节点的数据域即可，因此程序③处代码为list1[head][0]。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$