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

第二章 数据的存储方式2024—2025学年高中信息技术粤教版（2019）选修1 一、选择题 1．某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 2．设有数组定义语句：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) 3．某个正整数的每位数依次存储在链表d中各节点的数据区域中。例如，正整数572存储情况如图a所示，h为d的头指针。将该正整数翻倍后的计算结果（如572翻倍后的结果为1144）仍以这个链表存储，最高位存储于头节点中，如图b所示。实现该功能的程序段如下：       图a                           图b if d[h][0]>4: d.append([0,h])         #链表d新增一个节点 h=len(d)-1 p=h while p!=-1: d[p][0]=d[p][0]*2%10 cur=d[p][1] p=d[p][1] 方框中应填入的正确代码为（    ） A．if cur!=-1 and d[cur][0]>4: d[p][0]+=1 B．if cur!=-1 and d[p][0]>4: d[cur][0]=(d[p][0]*2+1)//10 C．if cur !=-1 and d[cur][0]>4: d[p][0]+=(d[cur][0]*2+1)%10 D．if cur!=-I and d[p][0]>4: d[cur][0]+=1 4．使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a a=[["cat",1],[ "dog",2],[ "pig",-1],[ "rabbit",0]] head=3 依次输出各节点数据域的值，内容为(　　) A．"cat","dog","pig","rabbit" B．"pig","rabbit","cat","dog" C．"pig","dog","cat","rabbit" D．"rabbit","cat","dog","pig" 5．链表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 6．有如下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．③②① 7．关于数组和链表，以下描述不正确的是（   ） A．数组通过下标访问或遍历序列中的数据元素 B．常见的链表有单向链表、双向链表和循环链表 C．一般情况下，数组元素的插入和删除效率比链表要低 D．一般情况下，数组元素的查找效率比链表要低 8．下列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] 9．使用列表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． 10．某单向链表如下图所示，若要将数据data3和data4同时从链表中移除，至少需要修改几个节点的指针（   ） A．1 B．2 C．3 D．4 11．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 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．一头指针 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．①②③ 14．下列关于数据结构的说法，不正确的是（   ） A．数组、链表、队列和栈都是常见的线性表数据结构 B．数组的存储空间是连续的，链表的存储空间可以是不连续的 C．每个链表必定有一个头指针，同一链表中每个节点的结构均相同 D．对数组进行操作时，若某数组元素被删除，数组占用的存储空间会变小 15．有如下 python 程序： a=[2, 5, 3, 11, 12, 4, 8, 10] n=8; num=[0]*n i=0 while i<n: num[i]=1 for j in range (0, i) : if a[j]<a[i] and num[j]>=num[i]: num[i]=num[j]+1 i=i+1 ans=0 for i in range (n) : if num[i]>ans: ans=num[i] print (ans) 执行该程序段后，输出ans 的值是（    ） A．2 B．4 C．5 D．6 16．有个列表n=[‘水果’, ‘砂糖橘’,’苹果’, ‘橙子’],请把列表中’苹果’改为’橘子’，选出修改正确的语句（   ） A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’] 17．现有单链表中的某两个节点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．②③① 18．创建一个空链表时，通常会设置什么来表示链表的起始（   ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 19．使用列表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 20．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果        A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃” 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3->7->2->1。选项A正确。 2．D 【详解】本题主要考查数组的赋值。array()函数的作用：返回一个包含数组的Variant（可变的），题干定义了一个容量固定的数组a（Dim a(5) As Integer），故赋值语句a=Array(1,2,3,4,5,6)是错误的，故本题选D选项。 3．A 【详解】本题考查链表节点插入知识。根据代码可知，当最高位数d[p][0]大于4(即5以上)时，其翻倍后的数将产生进位，因此需要新增加一个节点(默认在数据域插入0)，并将其作为新的头节点h。p 为高位节点，cur为p的后继节点(节点cur是节点p的低位)。该利用链表实现的乘法算法的顺序和常规乘法是相反的：先计算高位p然后再计算低位cur，p节点的数据域是本位d[p][0]的 2倍然后%10 后的值，但这还不是 d[p][0]的终值，还要看p的低位cur有没有产生进，若cur的数据域 d[cur][0] 大于4，则还会向p节点的数据域产生进位，由于最大的单位数9的2倍，其进位也只是1，因此每次 在p节点原先的数据域d[p][0]基础上加1即可实现进位操作。若没有产生进位则依次从高位向低位进 行迭代，直到链表遍历结束为止，综上述，本题应该选A。 4．D 【详解】本题主要考查链表的操作。head=3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依次类推，依次输出各节点数据域的值，内容为"rabbit","cat","dog","pig"，故本题选D选项。 5．B 【详解】本题考查链表。当遇到偶数节点时，要将其调整到偶数部分。首先将当前节点（t）的下一个指针（a[t][1]）指向后面一个节点的下一个指针（a[k][1]），然后将后面一个节点（k）的下一个指针（a[k][1]）指向原来当前节点的下一个指针（a[p][1]），最后将原来当前节点的下一个指针（a[p][1]）指向当前节点（k），并且更新p为后面一个节点（k），继续遍历。只有B选项的代码符合这个逻辑。故答案为：B。 6．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选项。 7．D 【详解】本题考查的是链表和数组。一般情况下，数组元素的查找效率比链表要高，数组元素的插入和删除效率比链表要低。故本题应选D。 8．D 【详解】本题主要考查链表的操作。通过遍历链表来寻找key，故第一空while循环条件是q!=-1。如果link1[q][0]==key，则删除key所在的节点，p是q的上一个节点，则通过p的指针域指向q的指针域以实现删除q节点，故第二空填link1[p][1]=link1[q][1]，故本题选D选项。 9．C 【详解】本题考查单链表及分支语句和数据排序等知识。 由于数据区域中数值的绝对值由小到大排列，由代码可知，原先的节点关系是：t→p→q，若数据区域d[p][0]的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可，即：t变为p，p变为g即可。若数据区域d[p][0]的数值为负数，则原先的链表各节点关系需要重新指向，由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越大，因此其相反数(负数)就越小，这样每一个当前节点p的负数肯定是当前链表中最小的数，因此该数应该变为最小的头节点，采用头插法可以实现，即将当前节点p的指针域指向原先的头节点h，然后再将头节点h变为当前节点p。故本题选C。 10．A 【详解】本题考查的是链表相关知识。由图中可知若要将数据data3和data4同时从链表中移除，至少要修改data2的指针指向data5，故本题应选A。 【点睛】 11．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 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．A 【详解】本题主要考查链表及Python程序实现。因为是逆序链表，q的初值为-1，故L[p][1]即p的下一个节点指向q，③L[p][1]=q。由题干单项链表可知，接下来更新q的值为p即②q=p，p的值为tmp①p=tmp，故本题选A选项。 14．D 【详解】本题考查的是数据结构。数组的存储空间都是固定不变的，若某数组元素被删除，数组占用的存储空间不会变。故选D。 15．C 【详解】本题考查的是数组子序列。阅读程序可知，程序的功能是求最长递增子序列的长度是多少，具体执行过程如下： 索引 0 1 2 3 4 5 6 7 数组a 2 5 3 11 12 4 8 10 数组num 1 2 2 3 4 3 4 5 最长子序列为：2, 3, 4, 8, 10长度为5，故选C。 16．A 【详解】本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 17．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。 18．C 【详解】本题考查链表。创建空链表时，通常会将头指针设置为一个表示空的值，如NULL（在C/C++中）或-1（在某些特定场景下的约定）。故选择C。 19．A 【详解】本题考查程序分析。数据区域中数值的绝对值由大到小排列，若数据区域a[p][0]的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可。若数据区域d[p][0]的数值为负数，则原先的链表各节点关系需要重新指向，由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越小，这样每一个当前节点p的负数肯定是当前链表中最小的数，因此该数应该变为最小的头节点，采用头插法可以实现，故本题选A。 20．B 【详解】本题考查的是pandas库相关知识。Series中如果没有指定索引，索引值就从 0 开始，故s[2]值为3，故选项B正确。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$