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

第二章 数据的存储方式 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。      图a 图b 若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作： ①“上海”所在节点的next值赋为“杭州”所在节点的next值 ②“上海”所在节点的next值赋为5 ③“杭州”所在节点的next值赋为“上海”所在节点的next值 ④“杭州”所在节点的next值赋为-1 链表更新顺序正确的是（    ） A．③② B．③① C．①④ D．②④ 2．有如下Python程序段，其功能是将一个单向链表转换成原链表的逆序链表： lst=[[15,4],[30,-1],[8,0],[5,2],[19,1]] head=3 p=head q=-1 while p!=-1:     tmp=lst[p][1] head=q 上述程序段执行后lst内容变为[[15,2],[30,4],[8,3],[5,-1],[19,0]]。方框处可选代码有：①q=p   ②p=tmp   ③lst[p][1]=q，则方框处的语句依次为（   ） A．①②③ B．②③① C．③①② D．③②① 3．找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下： #链表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 4．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果        A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃” 5．下列哪个特性不属于数组的特点（   ） A．所有元素的数据类型相同 B．可以通过下标直接访问任意元素 C．存储空间固定不变 D．插入和删除元素操作高效 6．链表去重。单向链表a中的节点由[数据区域，指针区域]构成，现需要将相邻的重复数据进行去重，即若有多个连续重复数据，仅保留最早出现的节点。 如原始链表a=[[1,1],[1,2],[4,3],[5,4],[1,5],[4,6],[4,7],[4,-1]]，head=0 去重后结果为[[1,2],[1,2],[4,3],[5,4],[1,5],[4,-1],[4,7],[4,-1]]，head=0 遍历去重后的链表，输出的结果为1 4 5 1 4。python代码如下。 a=[[1,1],[1,2],[4,3],[5,4],[1,5],[4,6],[4,7],[4,-1]] q=p=head=0 while a[p][1]!=-1:      （A）     if a[q][0]==a[p][0]:          （B）     else:          （C） 划线处可供选择的代码如下，（A）（B）（C）处填入的代码依次是（   ） ① p=a[p][1]       ②q=p      ③a[q][1]=a[p][1]    ④p=q A．①②③ B．①③② C．②③① D．①③④ 7．如果要在一个已有的链表中删除一个节点，需要修改哪些节点的指针（   ） A．只需要修改该节点的前驱节点 B．只需要修改该节点的后继节点 C．需要修改该节点的前驱节点和后继节点 D．不需要修改任何节点的指针，直接释放该节点的内存 8．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 9．有个列表n=[‘水果’, ‘砂糖橘’,’苹果’, ‘橙子’],请把列表中’苹果’改为’橘子’，选出修改正确的语句（   ） A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’] 10．小徐使用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]] 11．链表a中各节点由数据域和指针构成，并按数据域数值升序排列（头节点数据为奇数），现要修改各节点顺序，按奇数在前升序，偶数在后升序的顺序排列，如图所示。实现该功能的程序段如下，方框中应填入的正确代码是（   ） a=[[8,1],[9,-1],[6,0],[1,5],[5,2],[2,4]] p=t = head=3 while a[t][1]!=-1:     k=a[t][1]     if a[k][0]%2== 1:             else:         t=a[t][1] A． a[t][1]=a[p][1] a[p][1]=t p=t t=k B． a[t][1]=a[k][1] a[k][1]=a[p][1] a[p][1]=k p=a[p][1] C． a[p][1]=t a[t][1]=a[p][1] p=[p][1] t=k D． t=a[t][1] a[k][1]=a[p][1] a[p][1]=k p=k A．A B．B C．C D．D 12．使用链表结构模拟某校游玩路线，链表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．②④③ 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．用Python程序实现删除链表的倒数第n（n不大于链表长度）个节点，如n=2时，链表 更新为。 部分代码如下： # 读入链表存储在列表s中，head存储链表的头节点，代码略 n=int(input()) pl=p2=head while p2!=-1:    if n>=0：       (1)       n -= l    else:       (2)       p2 = s[p2] [1] if p1 == head :    head=s[head]  [1] else：    (3) 上述程序段中划线处可选的语句为： ①p1=s[p1][1]   ②p2=s[p2][1]    ③s[p1][1]=s[s[p1][1]][1]    ④s[p2][1]=s[s[p2][1]][1] 则（1）~（3）划线处语句依次为（   ） A．①③④ B．①④③ C．②①④ D．②①③ 15．语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （    ） A．二维单精度实型数组和二双精度型数组 B．二维长整型数组和二维单精度实型数组 C．一维单精度实型数组和二维整型数组 D．一维长整型数组和二维双精度型数组 16．有一组含有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 17．如下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]] 18．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 19．数组是一种怎样的数据结构（     ） A．体现数据的线性关系 B．只能存储相同类型的数据 C．不能直接通过下标访问元素 D．不适合用于顺序遍历数据 20．下列关于数组的描述，正确的是（    ） A．数组的大小是固定的，但可以有不同类型的数组元素 B．数组的大小是可变的，但所有数组元素的类型必须相同 C．数组的大小是固定的，所有数组元素的类型必须相同 D．数组的大小是可变的，可以有不同类型的数组元素 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查链表的操作。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，则首先杭州所在的节点指向成都，即③“杭州”所在节点的next值赋为“上海”所在节点的next值。其次上海指向杭州，即②“上海”所在节点的next值赋为5。故选A。 2．C 【详解】本题主要考查Python程序的调试。 p=head=3，即指向的元素是[5,2]，也就是链表中最小的一个元素，则逆序后就是最后一个元素，因此其指针域应是-1，此时q=-1，因此第一个语句是lst[p][1]=q，原指针域已经保存在tmp中了，即tmp=lst[p][1]。接下来就是更新q的值为p=3，即下一个元素指向[5,-1]。更新p的值为tmp=2，即接下来处理倒数第二小元素[8,0]，其余元素依次类推，故方框处的语句依次为③①②，故本题选C选项。 3．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。 4．B 【详解】本题考查的是pandas库相关知识。Series中如果没有指定索引，索引值就从 0 开始，故s[2]值为3，故选项B正确。 5．D 【详解】本题考查数组。数组在插入和删除元素时通常需要移动大量元素，效率相对较低。故选择D。 6．B 【详解】本题考查链表。如果节点没有到最后，则进入循环，移动节点指向下一个节点。故A处填写p=a[p][1]。if判断如果当前节点与上一个节点的数据相等，故p节点的下一个节点的指针赋值给q的下一个节点指针。B处填写a[q][1]=a[p][1]。如果不相等，则继续进行节点移动。故C处填写q=p。故选择B。 7．C 【详解】本题考查链表。 删除链表中的节点时，要保持链表的连贯性，通常需要修改被删除节点的前驱节点的指针，使其指向后继节点，同时如果链表是双向链表，还需要修改后继节点的指针，使其指向前驱节点。故选择C。 8．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 9．A 【详解】本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 10．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 11．B 【详解】本题考查链表。当遇到偶数节点时，要将其调整到偶数部分。首先将当前节点（t）的下一个指针（a[t][1]）指向后面一个节点的下一个指针（a[k][1]），然后将后面一个节点（k）的下一个指针（a[k][1]）指向原来当前节点的下一个指针（a[p][1]），最后将原来当前节点的下一个指针（a[p][1]）指向当前节点（k），并且更新p为后面一个节点（k），继续遍历。只有B选项的代码符合这个逻辑。故答案为：B。 12．D 【详解】本题考查的是链表。head列表里存放的是开始景点的指针。p表示头结点，故第一空应为：p=head[i] ；由于内循环开始前已经把头结点的时间存储到s中，故内循环要先指向下一个指针，再累加时间，故第二空应为：p=a[p][2]，第三空应为：s=s+a[p][1]。选项D正确。 13．D 【详解】本题考查的是链表操作。从图中可以知道，出队后立即入队，反映到链表上就是：tail指针指向head，head指针后移，让原head位置变为队尾（修改p的指针域为-1），即②①④。故选D。 14．D 【详解】本题主要考查Python程序的综合应用。①第一空更新p2的位置，即指向下一个节点，p2=s[p2][1]，同时n递减1。②当n<0时，此时需要更新p1的位置为p1=s[p1][1]，同时p2也指向下一个节点，当p2=-1时，p1的位置为删除节点的前一个节点。③如果p1!=head，则p1需要跳过删除的节点，即s[p1][1]=s[s[p1][1]][1]，故本题选D选项。 15．D 【详解】本题主要考查数组的定义。符号“%”表示短整型，“&amp;”表示长整型，“！”表示单精度浮点型，“#”表示双精度浮点型，故语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为一维长整型数组和二维双精度型数组，故本题选D选项。 16．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选项。 17．A 【详解】本题考查链表。节点odd的指针链接着下一个节点的下一个节点，这时odd节点移动一次，这时将odd节点的下一个节点链接到even的下一个节点。故排除选项B、D。按照程序执行一次，列表第二个元素变化为[6,0]，排除C。故选择A。 18．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 19．A 【详解】本题考查数据结构中的数组。数组是一种线性结构，元素按照线性顺序排列，可以通过下标直接访问。故选择A。 20．C 【详解】本题主要考查数组的描述。数组的大小是固定的，所有数组元素的类型必须相同，故本题选C选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$