2.2 链表（分层作业）信息技术浙教版2019选择性必修1

2.2链表 3课时（分层作业） 【基础达标】 1.链表的节点由 和 两部分组成。 2.每一个链表都有一个 （也称为 ），它的作用之一是： ，作用之二是： 。 3.链表可以根据每个节点中指针的数量分为两类： 和 。 4.链表的基本操作主要有 、 、 和 等 5.python中通过来 和 模拟实现链表结构。 6.链表的特性包括哪些？ 7.以下有关链表的描述,不正确的是( ） A.插入、删除操作无须移动数据元素 B.增加或减少节点会改变链表占用的存储空间 C.可随机快速访问任何一个数据元素 D.同一链表中每个节点的结构均相同 8.在列表： a =[[ 99, 1 ],[ 95, 2 ],[ 88, -1] ]中，列表a有 个元素；数据元素(a[0])的第一个元素(99)为 ，数据元素(a[0])的第二个元素(1)为 ，是列表a的第二元素的 。 9.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a: a=[[“hello”,1],[“china”,3],[“Olympics”,-1],[“winter”,2]] head=0 ①a[1][1]的值为:（ ） A.1 B.2 C.0 D.3 ②a[1][1]的含义是什么? 【巩固提升】 1.有如下python程序段： a = [[3, 2], [2, 3], [7, 1], [1, 0]] head = 0 p = head while a[p][1] != head: print(a[p][0], end="->") p = a[p][1] print(a[p][0]) 执行上述语句后，程序输出的结果为（ ） 2.有如下python程序段： a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有几个节点（ ） A.1 B.2 C.3 D.4 程序实现了什么功能？ 程序执行后链表a变为： 3.对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ) A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 4.下列关于数据结构的说法，正确的是（ ） A.常见的线性关系数据结构有数组、链表、队列、栈和图 B.数组和链表在操作时，其存储空间固定不变 C.链表在插入和删除元素时，算法效率比数组高 D.进行数据的插入操作时，链表中的元素会被移动 【链接高考】 1.对于单向链表的节点结构，以下说法不正确的是（ ） A.节点的数据区域用于存放实际需要处理的数据元素 B.节点的指针区域用于存储相邻节点的存储地址 C.单向链表必须带有数据区域为空的头节点和尾节点 D.单向链表中的各个节点在内存中可以非顺序存储 2.有如下Python程序段: d=[["a",2],["b",-1],["c",1]] head=0 p=0 d.append(["d",d[p][1]]) d[p][1]=len(d)-1 执行上述程序段后，下列说法正确的是（ ） A.d[0][1]的值为2，单向链表d的尾节点数据值为“b” B.d[1][1]的值为-1，单向链表d的尾节点数据值为“b” C.d[3][1]的值为1，单向链表d的尾节点数据值为“c” D.d[2][1]的值为1，单向链表d的尾节点数据值为“c” 3.采用列表模拟单向链表，data[p][0]为数据区域，data[p][1]为指针区域。在单向链表指针为 p的节点之后插入指针为 s 的节点，正确的操作是( ) A.data[s][1]=p data[p][1]=data[s][1] B.data[p][1]=s data[s][1]=data[p][1] C.data[s][1]=data[p][1] data[p][1]=s D.data[p][1]=data[s][1] data[s][1]=p 4.有一组数据集合由1到m之间的正整数组成。指定一段数据的开始位置和结束位置，能够统计出该段数据中不同数值的个数。编写Python，实现上述统计功能。运行程序，随机生成n个1到m之间的正整数和Q个询问L和R。 实现上述功能的Python程序如下，请在划线处填入合适的代码。 n=int(input()) a=list(map(int,input().split())) Q=int(input()) ask=[[0]*100 for i in range(100)] Min=9999999 Max=-1 pos=[0]*100 Next=[-1]*100 for i in range(Q): L,R=map(int ,input().split()) if(L<Min): Min=L if(R>Max): Max=R ask[i][0],ask[i][1]=L,R for i in range(Min,Max+1): if pos[a[i]]==0: pos[a[i]]=i Next[i]=0 else: ① pos[a[i]]=i for i in range(Q): num= ② for j in range(ask[i][1],ask[i][0]+1,-1): if ③ : num-=1 print(ask[i][0],"到",ask[i][1],"之间有：",num,"个不同的数") 参考答案 【基础达标】 1.数据区域和指针区域。 2.表头、头指针、作为链表的入口、为循环链表设立一个边界。 3.单向链表、双向链表。 4.空链表的创建、节点访问、节点插入和删除 5.列表、类 6.（1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 7.[解析]链表的访问需要通过头指针以节点链接的方式依次访问，选项C描述的是数组的访问方式。因此正确答案是C。 答案：C 8.3、数据域、指针域、索引。 9.[解析]根据head=0，头节点是[“hello”,1]，依次访问的节点就是[“china”,3],[“Olympics”,-1],[“winter”,2]，因此输出的类容就是3。 答案：①D②china后面指向的下一个节点是[“winter”,2]。 【巩固提升】 1.[解析]二维数组a表示一个循环单向链表,a[p][0]和a[p][1]分别存储节点p的数据和指针,程序功能从 头节点开始遍历链表输出各节点的值。 答案：3->7->2->1 2.[解析]根据Python程序段，程序语句执行后，链表a有3个节点。 答案：C、删除了头部节点[6,0]、a=[[7,1],[8,2],[9,-1],[6,0]] 3.B 4.[解析]常用的线性结构有:线性表，栈，队列，双队列，串(一维数组)，但树和图是非线性结构选项A错误;数组在创建时其存储空间就已经固定，选项B错误;链表在插入和删除元素时，算法效率比数组 高;进行数据的插入操作时，链表中的元素不会被移动。 答案：C 【链接高考】 1.[解析] 单向链表的头节点和尾节点可以是单独的数据区域为空的节点,也可以将节点序列中的第一个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式,即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。 答案：C 2.答案：B 3. [解析] 在单向链表指针为p的节点之后插入指针为s的节点，则s的指针域指向p的下一个节点，即data [s] [1] = data [p] [1]，其次将p和s连接起来即p的指针域指向s，所以选项C符合题意。 答案：C 4. ①Next[i]=pos[a[i]] ②ask[i][1]-ask[i][0]+1 ③Next[j]>=ask[i][0] and Next[j]<=ask[i][1] 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$