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

第二章 数据的存储方式 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．在Python中，如何使用列表模拟数组（   ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 2．链表相比于数组，在哪种情况下表现得更为高效（   ） A．需要频繁查找元素 B．需要随机访问元素 C．需要频繁在中间插入和删除元素 D．需要存储大量静态数据 3．现有单链表中的某两个节点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．②③① 4．有如下程序段： a=[[2,2,1],[8,0,4],[3,3,0],[6,-1,2],[8,1,-1]] ans=head=3 p=a[head][2] while p!=-1:     if a[ans][0] < a[p][0] :         ans=p     p=a[p][2] print(ans,a[ans][0],sep=",") 则程序运行后，下列说法正确的是（    ） A．链表数据值依次为2->8->3->6->8 B．程序输出结果为4,8 C．a[0][2]的值为1，双向链表a的头节点数据值为2 D．a[1][1]的值为0，双向链表a的尾节点数据值为8 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．数组是一种采用哪种存储结构的数据结构（   ） A．顺序存储结构 B．非顺序存储结构 C．索引存储结构 D．散列存储结构 7．有个列表n=[‘水果’, ‘砂糖橘’,’苹果’, ‘橙子’],请把列表中’苹果’改为’橘子’，选出修改正确的语句（   ） A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’] 8．某单向链表如下图所示，若要将数据data3和data4同时从链表中移除，至少需要修改几个节点的指针（   ） A．1 B．2 C．3 D．4 9．下列关于数组的描述，正确的是（    ） A．数组的大小是固定的，但可以有不同类型的数组元素 B．数组的大小是可变的，但所有数组元素的类型必须相同 C．数组的大小是固定的，所有数组元素的类型必须相同 D．数组的大小是可变的，可以有不同类型的数组元素 10．一维数组a（下标从0开始）中元素值依次为11--100之间的奇数，则数组元素a[k]的值是（  ） A．2*k+10 B．2*k+11 C．2*k+12 D．2*k+13 11．使用列表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 12．有关数组特征描述中，下列说法不正确的是（  ） A．同一数组中，每个数组元素的数据类型是相同的 B．通过数组名和下标可以对数组中任意位置的数组元素进行高效访问 C．数组的存储空间固定不变 D．数组是非顺序存储结构 13．链表和数组在存储空间上的主要区别是什么（   ） A．链表需要连续的内存空间，数组则不需要 B．数组需要连续的内存空间，链表则不需要 C．两者都需要连续的内存空间 D．两者都不需要连续的内存空间 14．如果一个链表的头指针为head，要访问链表中第i个节点，需要进行几次指针移动（   ） A．i次 B．i-1次 C．i+1次 D．无法确定，取决于链表长度 15．在一个长度为n的数组中的第i个元素（1<=i<=n）之前插入一个新元素时，需向后移动的元素个数为（   ） A．i B．n-i C．n-i+1 D．n-i-1 16．使用列表d模拟链表结构（节点数大于0）每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为（   ） 图a                 图b t = h p = d[h][1] while p != -1:     q = d[p][1]         p = q d[t][1]=-1 A． B． C． D． 17．王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下：a=[[“056”，4]，[“134”，-1]，[“215”，5]，[“098”，0]，[“144”，2]，[“024”，1]]。假设head=3，小明同学的号码是“215”，则他的出场次序是（    ） A．2 B．4 C．5 D．6 18．有如下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．③②① 19．下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。 #建立链表 link1，代码略 key=int(input("输入要删除的数据：")) head=0 while link1[head][0]==key and head!=- 1:     head=link1[head][1]     p=q=head     if head==- 1:         print("全部数据删除")     else:         q=link1[q][1]         while   ① :             if link1[q][0]==key: ②             else:                p=link1[p][1] q=link1[q][1] 则划线①②处的代码分别为（　　） A．①link1[q][1]!=- 1              ②link1[p][1]=link1[q][1] B．①link1[q][1]!=- 1               ②link1[q][1]=link1[p][1] C．①q!=- 1                          ②link1[q][1]=link1[p][1] D．①q!=- 1                          ②link1[p][1]=link1[q][1] 20．下列有关链表的描述，不正确的是（   ） A．要取出链表中的元素时，需要知道该元素在链表中的位置 B．要访问链表中的元素，只能从头节点开始遍历 C．在链表的首尾之间增加链接，就形成了循环链表 D．链表的存在形式主要有单向链表、双向链表和循环链表 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查列表模拟数组。 Python列表模拟数组的关键在于能够通过索引快速访问元素。故选择A。 2．C 【详解】本题考查链表和数组。选项C，需要频繁在中间插入和删除元素。链表由于其动态的内存分配和指针链接特性，使得在链表中间插入和删除元素比数组更为高效。故选择C。 3．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。 4．D 【详解】本题主要考查链表及Python程序。分析程序可知，a是双向链表，ans=head=3，故链表数据值依次为6->3->2->8->8；程序运行结束后，ans=1，a[ans][0]=8；a[0][2]的值为1，head=3，双向链表a的头节点数据值为6；a[1][1]的值为0，双向链表a的尾节点数据值为8，故本题选D选项。 5．C 【详解】本题考查数据结构。若删除链表节点[0,2],列表的数据变为[[23,3],[2,2],[8,0],[66,None]]，此时head指向节点[2,2]，因此head的值仍为1。故答案为：C。 6．A 【详解】本题考查数组。数组是一种典型的采用顺序存储结构的数据结构。在顺序存储结构中，数组元素在内存中是连续存储的，元素之间的逻辑关系和物理关系是一致的。通过索引可以快速定位到数组中的任意元素。故选择A。 7．A 【详解】本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 8．A 【详解】本题考查的是链表相关知识。由图中可知若要将数据data3和data4同时从链表中移除，至少要修改data2的指针指向data5，故本题应选A。 【点睛】 9．C 【详解】本题主要考查数组的描述。数组的大小是固定的，所有数组元素的类型必须相同，故本题选C选项。 10．B 【详解】本题主要考查数组。一维数组a（下标从0开始）中元素值依次为11--100之间的奇数，2*k是偶数，2*k+11表示11~100之间的奇数（k从0开始），故本题选B选项。 11．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选项。 12．D 【详解】本题主要考查数组特征。同一数组中，每个数组元素的数据类型是相同的；通过数组名和下标可以对数组中任意位置的数组元素进行高效访问；数组的存储空间固定不变；数组是顺序存储结构，故本题选D选项。 13．B 【详解】本题考查数组和链表。 数组的元素在内存中连续存储，而链表的节点可以分散在内存的不同位置。故选择B。 14．B 【详解】本题考查链表。要访问链表中第i个节点，从头节点开始需经过i-1个节点的指针移动。故选择B。 15．C 【详解】本题考查数组。在一个长度为n的数组中，第i个元素（1<=i<=n）之前插入一个新元素，从第n个元素开始，直到第i个元素，都需要向后移动一位，一共需要移动n-i+1个元素。例如，一个长度为5的数组，要在第3个元素前插入新元素，那么第5个、第4个和第3个元素都要向后移动，共5-3+1=3个元素。故答案为：C。 16．C 【详解】本题考查单链表及分支语句和数据排序等知识。 由于数据区域中数值的绝对值由小到大排列，由代码可知，原先的节点关系是：t→p→q，若数据区域d[p][0]的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可，即：t变为p，p变为g即可。若数据区域d[p][0]的数值为负数，则原先的链表各节点关系需要重新指向，由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越大，因此其相反数(负数)就越小，这样每一个当前节点p的负数肯定是当前链表中最小的数，因此该数应该变为最小的头节点，采用头插法可以实现，即将当前节点p的指针域指向原先的头节点h，然后再将头节点h变为当前节点p。故本题选C。 17．B 【详解】本题主要考查链表数据结构的操作。假设head=3，则出场顺序依次是“098”→“056”→“144”→“215”→“024”→“134”，小明同学的号码是“215”，则他的出场次序是4，故本题选B选项。 18．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选项。 19．D 【详解】本题主要考查链表的操作。通过遍历链表来寻找key，故第一空while循环条件是q!=-1。如果link1[q][0]==key，则删除key所在的节点，p是q的上一个节点，则通过p的指针域指向q的指针域以实现删除q节点，故第二空填link1[p][1]=link1[q][1]，故本题选D选项。 20．A 【详解】本题考查链表。在链表中组织处理数据时，不需要知道数据元素实际所处的具体位置，只需知道数据之间相互链接的顺序，因此答案为A。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$