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

第二章 数据的存储方式 一、选择题 1．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 2．链表中的节点通常包含哪两部分（   ） A．数据域和控制域 B．数据域和指针域 C．指令域和地址域 D．标志域和内容域 3．链表相比于数组，在哪种情况下表现得更为高效（   ） A．需要频繁查找元素 B．需要随机访问元素 C．需要频繁在中间插入和删除元素 D．需要存储大量静态数据 4．在单向链表中，如何访问第n个节点（   ） A．从头节点开始遍历n次 B．通过下标直接定位 C．从尾节点开始反向遍历n次 D．无法直接访问，必须遍历整个链表 5．在单向链表如下图所示，在data2与data3之间插入一个新节点data4（p指向data2，r指向data4。列表data来记录链表数据域，列表next来记录指针域），在以下选项中选择正确的执行步骤（     ） ①next[p]= next[r]    ②next[p]= r             ③next[r]= p ④next[r]= -1         ⑤next[r]= next[p]       ⑥next[p]= -1 A．③⑥ B．⑤② C．①④ D．⑤②④ 6．单向链表和双向链表的区别在于（   ） A．单向链表每个节点有一个指针，双向链表每个节点有两个指针 B．单向链表的节点存储空间小于双向链表 C．单向链表可以循环，双向链表不可以 D．单向链表的访问速度优于双向链表 7．双向链表中有两个指针域llink和rlink，llink指向当前节点的前一个节点，rlink指向当前节点的后一个节点。假定链表中节点数大于3个，p指向链表中的某一个节点（p不是头节点），现要求删除p所指的节点，则下列操作能实现的是（   ） A．p.llink.rlink=p.rlink B．p.llink.rlink=p.rlink C．p.rlink.llink=p.llink；p.llink.rlink=p.rlink D．p.llink.rlink=p.llink；p.llink.rlink=p.rlink 8．设有一个5×8的二维数组a，若按行优先的顺序存储数组元素，则元素a[3][5]前面元素的个数为(　　) A．21 B．22 C．29 D．37 9．小徐使用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]] 10．有一组含有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 11．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 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．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（    ）来表示。 A．数组 B．链表 C．栈 D．队列 14．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 15．链表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 16．某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 17．有如下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．③②① 18．在一个列表a中隐藏着一个链表，a=[[4,0],[5,2],[7,4],[8,5],[6,3],[1,-1]]。链表节点a[i]中，a[i][0]表示数据，a[i][1]表示指针，下列说法正确的是（   ） A．链表的两个相邻节点，其存储空间必须连续 B．该隐藏链表的表头head=2 C．该隐藏链表有5个节点 D．代码“a[i][1]=a[i+1][1]”可以实现删除节点“i+1” 19．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果        A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃” 20．子序列是指数组中连续的若干个元素(至少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． 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 2．B 【详解】本题考查链表。数据域：用于存储节点的数据信息。指针域：用于存储指向下一个节点的指针。故选择B。 3．C 【详解】本题考查链表和数组。选项C，需要频繁在中间插入和删除元素。链表由于其动态的内存分配和指针链接特性，使得在链表中间插入和删除元素比数组更为高效。故选择C。 4．A 【详解】本题考查链表。从头节点开始遍历n次 - 在单向链表中，要访问第n个节点，必须从头节点开始，逐个遍历直到到达目标节点。故选择A。 5．B 【详解】本题主要考查链表的操作。在data2与data3之间插入一个新节点data4，p指向data2，r指向data4，则正确的步骤是，先将r的next指针域指向p的next节点，其次更新p的next为r，故分别是：next[r]= next[p] 和next[p]= r ，故本题选B选项。 6．A 【详解】本题考查链表。单向链表和双向链表的区别主要在于指针的数量和存储空间的不同。单向链表每个节点只有一个指向下一个节点的指针，而双向链表每个节点有两个指针，分别指向前一个节点和下一个节点，因此双向链表的节点存储空间比单向链表大。故答案为：A。 7．C 【详解】本题考查双向链表。双向链表中，每个节点有两个指针域，分别指向前一个节点和后一个节点。当要删除某个节点时，需要将该节点前后两个节点的指针重新连接起来，以维持链表的连续性。而操作p.rlink.llink=p.llink是将p节点后一个节点的llink指针指向p节点前一个节点，而p.llink.rlink=p.rlink是将p节点前一个节点的rlink指针指向p节点后一个节点，两者均能实现删除p节点的目的。故答案为：C。 8．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选项。 9．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 10．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选项。 11．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 12．D 【详解】本题考查链表结构。链表结构模拟景区游玩路线的程序中，需要注意如下的逻辑：(1)处：应该设置当前节点的指针p为head[i]，表示第i个大门的开始路线，即p=head[i]。（2）（3）处注意s的初值为a[p][1]，同时最后一个节点取不到，所以应先跳入下一节点再统计当前时间的和，所以答案为②④③，故答案为D选项。 13．B 【详解】本题考查的是链表相关知识。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。寻宝游戏中通过一个线索找到下一个线索，最好用链表来表示，故选B选项。 14．B 【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。 15．B 【详解】本题考查链表。当遇到偶数节点时，要将其调整到偶数部分。首先将当前节点（t）的下一个指针（a[t][1]）指向后面一个节点的下一个指针（a[k][1]），然后将后面一个节点（k）的下一个指针（a[k][1]）指向原来当前节点的下一个指针（a[p][1]），最后将原来当前节点的下一个指针（a[p][1]）指向当前节点（k），并且更新p为后面一个节点（k），继续遍历。只有B选项的代码符合这个逻辑。故答案为：B。 16．A 【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3->7->2->1。选项A正确。 17．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选项。 18．C 【详解】本题考查链表。A选项错误，链表的相邻节点存储时不需要连续空间。B选项错误，该隐藏链表的表头head=1。D选项错误，删除节点“i+1”的代码是“a[i][1]=a[a[i][1]][1]”。故答案为：C。 19．B 【详解】本题考查的是pandas库相关知识。Series中如果没有指定索引，索引值就从 0 开始，故s[2]值为3，故选项B正确。 20．C 【详解】本题考查的知识点是子序列的相关知识。子序列是指数组中连续的若干个元素(至少1个元素)。依题意知：数组a中和最大的子序列为[4,-1,2,1]，和为6。A选项运行结果为4，B选项运行结果为4，C选项运行结果6，D选项运行结果为1。故答案为C选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$