第二章 数据与链表 2023-2024学年高中信息技术浙教版（2019）选修1

第二章数据与链表同步作业2023—2024学年高中信息技术浙教版（2019）选修1 一、选择题 1．有如下Python程序段： a=[[1.3]，[3.4]，[5.-1]，[2.1]，[4.2]] h=p=0；t=b=2 x=random.randint（2，4） while a[p][1] ！ = t：     q=a[p][1]     a[p][1]=a[a[p][1]][1]     if a[q][0] < x：         a[q][1]=h         h=q     else：         a[q][1]=a[b][1]         a[b][1]=q while h！=-1：     print（a[h][0]，end=" "）     h=a[h][1] 执行该程序段后，输出的结果不可能是（   ） A．1 5 4 3 2 B．2 1 5 4 3 C．3 2 1 5 4 D．4 3 2 1 5 2．有个列表n=[‘水果’, ‘砂糖橘’,’苹果’, ‘橙子’],请把列表中’苹果’改为’橘子’，选出修改正确的语句（   ） A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’] 3．有一组含有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 4．下列哪个特性不属于数组的特点（   ） A．所有元素的数据类型相同 B．可以通过下标直接访问任意元素 C．存储空间固定不变 D．插入和删除元素操作高效 5．一个数组的第一个元素的存储位置为1000（表示在第1000个字节处），每个元素所占空间大小为8个字节，则第5个元素的位置是（   ） A．1000 B．1040 C．1032 D．1256 6．下到关于数据结构与算法效率的描述，不正确的是（   ） A．数据元素是数据的基本单位 B．数据的存储结构应能体现其逻辑结构 C．使用数组结构存储插入、删除较多的数据时，效率较低 D．某单向链表（结点数>2）设有头尾指针，在该链表尾节点后插入一个新节点时需要遍历多个结点 7．有如下程序段： 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 8．使用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" 9．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（  ） A．16 B．8 C．10 D．13 10．数组是由 构成的一个序列。 11．链表中的节点通常包含哪两部分（   ） A．数据域和控制域 B．数据域和指针域 C．指令域和地址域 D．标志域和内容域 12．下列关于数组的描述，正确的是（    ） A．数组的大小是固定的，但可以有不同类型的数组元素 B．数组的大小是可变的，但所有数组元素的类型必须相同 C．数组的大小是固定的，所有数组元素的类型必须相同 D．数组的大小是可变的，可以有不同类型的数组元素 13．使用列表flink模拟链表结构（节点数大于1），每个节点包含起始数值、连续长度、指针区域，h为头指针。链表中各节点已按起始数值由小到大排列，各个节点表示的数值区间不重叠，例如链表 flink为[[20，100，3]，[150，50，2]，[250，60，-1]，[120，30，1]]，h-0，其中节点[20，100，3]表示从数值20开始有长度为100的连续值（20到119），3代表后继节点索引为3，现要合并链表各节点连续的数值区间，合并后链表flink的数据修改为[[20，180，2]，[150，50，2]，[250，60，-1]，[120，30，1]]，h=0。实现该功能的程序段如下: q=h=0 p=flink[q][2] while p!=-1:     if flink[p][0]==flink[q][0]+flink[q][1]:         flink[q][1]=flink[q][1]+flink[p][1]     else:         （1）     （2）     （3） 上述程序中方框处可选语句为:①q=p  ②flink[q][2]=p  ③p=flink[p][2] 则（1）、（2）、（3）处语句依次是（   ） A．①、②、③ B．①、③、② C．②、①、③ D．②、③、① 14．下列有关链表的描述，不正确的是（   ） A．要取出链表中的元素时，需要知道该元素在链表中的位置 B．要访问链表中的元素，只能从头节点开始遍历 C．在链表的首尾之间增加链接，就形成了循环链表 D．链表的存在形式主要有单向链表、双向链表和循环链表 15．语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （    ） A．二维单精度实型数组和二双精度型数组 B．二维长整型数组和二维单精度实型数组 C．一维单精度实型数组和二维整型数组 D．一维长整型数组和二维双精度型数组 16．在一个单向链表（如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点），则执行的操作是(　　) A．tail所指节点的data3值赋为r所指节点的data4值 B．r所指节点的next值赋为tail C．r所指节点的next值赋为－l D．tail所指节点的next赋为r,r所指节点的next值赋为－l 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．需要频繁查找元素 B．需要随机访问元素 C．需要频繁在中间插入和删除元素 D．需要存储大量静态数据 19．利用列表a来模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域。head为头指针，各节点已按数据区域中数值由小到大排列。现要对该链表进行去重处理，将链表各节点数据区域中数值重复的节点予以删除。实现该功能的程序段如下，方框中应填入的正确代码为（    ） t=head p=a[t][1] while p!=-1: a[t][1]=-1 A． if a[t][0]==a[p][0]: t=p p=a[p][1]else: a[t][1]=p t=p p=a[p][1] B． if a[t][0]==a[p][0]: p=a[p][1]else: t=p a[t][1]=p C． if a[t][0]!=a[p][0]: a[t][1]=p t=pelse: t=p p=a[p][1] D． if a[t][0]!=a[p][0]: a[t][1]=p t=pp=a[p][l] A．A B．B C．C D．D 20．创建一个空链表时，通常会设置什么来表示链表的起始（   ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查链表操作。 遍历链表，尾节点除外，将比x 小的放表头，大于等于x的放表尾。随机数x，产生的范围为2到4。故当x=2时，选项A符合，节点1小于x，放表头，其它节点放表尾。同理可知，选项B、C均符合。选项D，当x=4时，节点4应该放到表尾，而放到表头，故选项D不可能。故正确答案为：选项D。 2．A 【详解】本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 3．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选项。 4．D 【详解】本题考查数组。数组在插入和删除元素时通常需要移动大量元素，效率相对较低。故选择D。 5．C 【详解】本题考查数组。第一个元素在第1000个字节处，每个元素占8个字节。那么第5个元素与第一个元素相隔4个元素，所以第5个元素的位置为1000+4*8=1000+32=1032。故答案为：C。 6．D 【详解】本题考查不同数据结构的特性和算法描述。选项A：数据元素是构成数据的基本单位，正确；选项B：数据结构有逻辑结构和物理结构之分。逻辑结构反映数据之间的逻辑关系，物理结构反映数据在计算机内部的存储安排，正确；选项C：采用数组存储数据，进行插入、删除操作时，需要移动元素，效率较低；选项D：设有尾指针的单链表在表尾节点插入新节点时，只需要修改尾指针即可，不需要从表头开始遍历各节点，选项D错误。故本题正确答案是D。 7．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选项。 8．D 【详解】本题主要考查链表的操作。head=3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依次类推，依次输出各节点数据域的值，内容为"rabbit","cat","dog","pig"，故本题选D选项。 9．A 【详解】本题主要考查数组运算。数组索引是从0开始，故a[1]+a[3]+a[5]=5+3+8=16，故本题选A选项。 10．相同类型的变量 【详解】本题考查数组。 数组是由相同类型的变量构成的一个序列。这些变量按照一定的顺序排列，每个变量可以通过索引（或下标）来访问。在大多数编程语言中，数组是一种基本的数据结构。 11．B 【详解】本题考查链表。数据域：用于存储节点的数据信息。指针域：用于存储指向下一个节点的指针。故选择B。 12．C 【详解】本题主要考查数组的描述。数组的大小是固定的，所有数组元素的类型必须相同，故本题选C选项。 13．B 【详解】本题考查Python程序。当不满足合并条件时，需要将当前节点后移（q=p），更新当前节点的后继指针（flink[q][2]=p），然后再获取新的后继节点（p=flink[p][2]）。所以（1）处为①，（2）处为③，（3）处为②。故答案为：B。 14．A 【详解】本题考查链表。在链表中组织处理数据时，不需要知道数据元素实际所处的具体位置，只需知道数据之间相互链接的顺序，因此答案为A。 15．D 【详解】本题主要考查数组的定义。符号“%”表示短整型，“&amp;”表示长整型，“！”表示单精度浮点型，“#”表示双精度浮点型，故语句Dim a&amp;(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为一维长整型数组和二维双精度型数组，故本题选D选项。 16．D 【详解】本题主要考查链表的操作。链表中尾结点的next指针为-1，若在尾指针tail所指节点之后插入新节点(r所指节点），则执行的操作是：tail所指节点的next赋为r，r所指节点的next值赋为－l，故本题选D选项。 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 【详解】本题考查链表和数组。选项C，需要频繁在中间插入和删除元素。链表由于其动态的内存分配和指针链接特性，使得在链表中间插入和删除元素比数组更为高效。故选择C。 19．D 【详解】本题考查链表操作。选项A，当t节点与p结点值重复时候，t节点移动到p节点处，p节点向后移动。这时应该删除p节点，p节点应该向下一个节点移动。故不能删除。 选项B，当节点值不同时，缺少p节点向下一个节点移动，故会死循环。 选项C与选项A错误相同，当t节点与p结点值重复时候，没有向p节点的下一个节点移动。 故正确答案为：选项D。 20．C 【详解】本题考查链表。创建空链表时，通常会将头指针设置为一个表示空的值，如NULL（在C/C++中）或-1（在某些特定场景下的约定）。故选择C。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$