第二章 数组与链表（单元测试）信息技术浙教版2019选择性必修1

第二章 数组与链表 单元测试 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 13 27题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.一个数组的第一个元素的存储位置为1000(表示在第1000个字节处)，每个元素所占空间大小为8个字节，则第5个元素的位置是（ ）? A.1000 B.1040 C.1032 D.1256 2.有如下Python程序段: a=[[0]*4]*3 b=[[0]*4 for i in range(3)] a[2][3]=8 b[2][3]=8 则程序执行后，下列说法正确的是( ) A.a[0][3]的值为0,b[0][3]的值为0 B.a[0][3]的值为0,b[0][3]的值为8 C.a[0][3]的值为8,b[0][3]的值为0 D.a[0][3]的值为8,b[0][3]的值为8 3.有如下 Python程序段: a=[[1,3,8],[2,6,7],[5,4,1],[7,9,6]] n=len(a) sumx=0 for i in range(4): for j in range(3): if j%2==0: sumx=sumx+a[i][j] print( sumx) 程序执行后,输出的结果为( ) A.8 B.22 C.37 D.59 4.阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”。相关代码如下: a=[["浙江省","杭州市"]，["吉林省","长春市"],["湖南省","长沙市"],["湖北省","武汉市"],["江苏省","南京市"],["广东省","广州市"]] for p in a: print(f"{ }的省会是{ }") 则划线①和②处分别应填写的代码为( ) A.①p[1];②p[0] B.①p[0];②p[1] C.①a[p][0];②a[p][1] D.①p[1];②p[2] 5.下列有关数据的描述正确的是（ ） A.数组是由多种不同类型的变量构成的一个序列 B.数组是由相同类型的变量构成的一个序列 C.一个数组在内存中的存储空间不一定是连续的 D.一个数组在内存中的存储方式为非顺序结构 6.有如下Python程序， n = 0，s = [1,1,2, 2, 2, 3, 1,1,3, 3] for i in range(0,len (s) - 1): if s [i] == s [i +1]: n+=1 else: n-=1 print(n) 执行以上程序后，变量n的值为( ) A.0 B.1 C.-1 D.2 7.有如下Python程序段: s =“22py4th18“ ; sum =t=0 for i in range(len (s)): if “0“<= s [i] <=“9“: t=t*10 +int (s [i]) else: sum+ =t t=0 print (sum) 执行该程序段后，变量sum的值为( ) A.22 B.26 C.40 D.44 8.有如下Python程序段： ma=a[0] mb=a[0] pa,pb=0,0 for i in range(1,10): if ma<a[i]: ma=a[i] ; pa=i if mb>a[i]: mb=a[i] ; pb=i 下列关于该程序段功能描述正确的是( ) A.变量pa存储a[0]至a[9]中的最大值 B.变量ma存储a[0]至a[9]中的最小值 C.变量pb存储a[0]至a[9]中的最大值 D.变量mb存储a[0]至a[9]中的最小值 9.采用列表模拟单向链表，datap0]为数据区域，datap为指针区域。在单向链表指针为p的 节点之后插入指针为s的节点，正确的操作是（） A.data [p][1]=s data [s] [1] == data [p] [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]= datal [s] [1] data [s] [1]=p 10.通过以下 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 ③L[p][1] =q ②q=p 则方框处语句依次为 A.③②① B.③①② C.①③② D.①②③ 11.使用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“ 12.某python 程序段如下: a=[28,29,79,14,24,43] m=int(input("请输入一个整数:")) pos=-1 for i in range(len(a)): if a[i]>m: if pos==-1 or a[i]<a[pos]: pos=i 运行该程序段，若输入40，变量pos的值是( ) A.-1 B.2 C.3 D.5 13.有下列python程序段: a=[3,7,8,2,19,10,16,12] n=len(a) for i in range(2): k=i for j in range(i+1,n): if a[k]<a[j]: k=j if i!=k: a[i],a[k]=a[k],a[i] 下列说法正确的是( ) A.程序段执行后，数组a中的元素为[19,16,8,2,3,10,7,12] B.程序段执行后，数组a中的元素为[3,2,8,7,19,10,16,12] C.程序段执行后，变量k的值为7 D.程序段执行后，数组a中数据元素发生位置变化的有2个 14.有如下Python程序段: s = [1, 3, 4, 3,1] m，sum =s [0]，0 for i in range(1,len(s)): if s [i] > m: m = s [i] sum+=m 执行该程序后，sum的值为() A.15 B.12 C.11 D.7 15.对于单向链表的节点结构，以下说法不正确的是（ ） A.节点的数据区域用于存放实际需要处理的数据元素 B.节点的指针区域用于存储相邻节点的存储地址 C.单向链表必须带有数据区域为空的头节点和尾节点 D.单向链表中的各个节点在内存中可以非顺序存储 16.有如下 Python 程序段: a =[[7,1],[8,2],[9,-1]] head =0 p=1 a. append([6,a[p][1]]) a[p][1] =len(a) -1 则程序执行后,下列说法正确的是 A.a[2][0]的值为6,链表a的尾结点数据值为6 B.a[2][0]的值为9,链表a的尾结点数据值为6 C.a[3][1]的值为2,链表a的尾结点数据值为9 D.a[3][1]的值为-1,链表a的尾结点数据值为9 17.采用列表模拟单向链表，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 18.有个列表n =「‘水果’，‘砂糖橘’，’苹果’，‘橙子’]，请把列表中’苹果’改为’橘子’，选出修改正确的语句( ) A.n [2] = ‘橘子’ B.n[‘橘子’] C.n [3] = ‘橘子’ D.list[‘橘子’] 19.有如下 Python程序段: s=0 a=[[2,8,3],[1,6,4],[5,7,9]] for i in range(3): for j in range( 3) : if i==j: s=s+a[i][i] 程序段执行后,变量s的值为（ ） A.11 B.14 C.17 D.21 20.使用列表生成式创建数组代码如下a=[i*i-1 for i in range(10)ifi%2==0]则数组元素a[3]的值为( ) A.2 B.8 C.15 D.35 二、填空题（每空2分，共计40分） 1.在日常幻灯片(如使用PowerPoint制作的讲稿)的放映中，可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是 。 2. 将数组元素a[i]中各项的名称填入方框中： 3.在一个长度为n的数组中的第i个元素 (1<=i<=n) 之前插入一个新元素时，需向后移动的元素个数为 。 4.在单向链表中，增加头指针的目的是 。 5.数组a的数据存放情况如下表，则当i=2时，a[6/i-1]的值是 。 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 48 52 98 26 47 22 82 33 6.在一个包含 n( n>1 ) 个节点的单链表上，没有头和尾两个指针，下列操作需要遍历多个节点的是 。 7.数组a和数组b的数据存放情况如下表，则b (a (8)) - a (8)的值是 。 数组a a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 7 4 -2 31 -7 9 25 6 数组b b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] 1 41 22 3 -7 5 9 6 8.有如下python程序段: a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有 个节点。 9.在程序运行过程中可以改变数组元素个数的是 数组，不可以改变数组元素个数的是 数组。 10.有如下程序段: for i in range (3,5): for j in range(5,i,-1): if a[j] <a[j-1]: a[j]，a[j -1]=a[j -1]，a[j] 若数组a中的值为46，62，53，86，15，48，则执行该段程序后，a中的值变为 。 11.有如下 python程序段: for i in range(1,1001): flag=True for j in range(3): if i%a[2*j]!=a[2*j+1]: flag=False if flag: ans=i break 已知列表 a=[3,1,5,1,7,3]，该段程序执行后，变量ans的值为 。 12.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a: a=[[“hello”,1],[“china”,3],[“Olympics”,-1],[“winter”,2]] head=0 ①a[1][1]的值为 。 ②a[1][1]的含义是 。 13.已知有Python列表L表示一个单向链表,其中的子列表表示链表节点,子列表中第一个数据区域存储 节点中的实际数据,第二个数据区域存储节点的后继指针。现要实现逆序输出该链表的功能,首先将 该单向链表修改为双向链表,为其节点增加一个指针域,使得表示节点的列表中,第一个数据区域存 储链表节点中的实际数据,第二个数据区域存储节点的前驱指针,第三个数据区域存储节点的后继指 针。实现上述功能的Python程序如下。 L=[["A",3],["C",4],["D",-1],["E",6],["B",7],["G",0],["F",2],["N",5]] head=1 prev=head #初始化存储前驱指针的变量 cur=L[head][1] #初始化存储当前节点的变量 #头节点单独操作,其前驱指针为-1 L[head].append(L[head][1]) L[head][1]=-1 #为其余节点添加前驱指针 while len(L[cur]) == 2: L[cur].append(L[cur][1]) next=L[cur][1] #存储后继指针 L[cur][1]=prev prev= ① cur= ② tail=head #初始化尾节点的位置 While ③ : tail=L[tail][2] while tail!=-1: if L[tail][1]!=-1: print(L[tail][0],end="→") else: print(L[tail][0]) tail= ④ 请回答下列问题: (1)若有一Python列表link=[["W",3],["Q",2],["B",4],["C",1],["Y",-1]],head=0表示一个单向链表，若子列表中第一个数据表示节点的实际数据，第二个数据表示节点的后继指针,则将该单向链表根据题目要求修改为双向链表后,link的值变为 。 （2）请在划线处填入合适的代码。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $ 第二章 数组与链表 单元测试 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 填空题 总计 题数 20 13 27题 分数 60 40 100分 得分 一、单项选择题（每题3分，共60分） 1.一个数组的第一个元素的存储位置为1000(表示在第1000个字节处)，每个元素所占空间大小为8个字节，则第5个元素的位置是（ ）? A.1000 B.1040 C.1032 D.1256 【答案】C [解析]第五个元素的存储地址为1000+8×（5-1）=1032。 2.有如下Python程序段: a=[[0]*4]*3 b=[[0]*4 for i in range(3)] a[2][3]=8 b[2][3]=8 则程序执行后，下列说法正确的是( ) A.a[0][3]的值为0,b[0][3]的值为0 B.a[0][3]的值为0,b[0][3]的值为8 C.a[0][3]的值为8,b[0][3]的值为0 D.a[0][3]的值为8,b[0][3]的值为8 【答案】C [解析]本题主要考查的是二维数组创建与访问。数组a为间接创建方式，当某个元素值改变时，对应的该列所有值改变，数组b使用的是列表生成式创建,各个元素独立。 3.有如下 Python程序段: a=[[1,3,8],[2,6,7],[5,4,1],[7,9,6]] n=len(a) sumx=0 for i in range(4): for j in range(3): if j%2==0: sumx=sumx+a[i][j] print( sumx) 程序执行后,输出的结果为( ) A.8 B.22 C.37 D.59 【答案】B [解析]本题的功能是求二维数组中列满足条件“j%2==0”的各数组元素之和,即求二维数组b中第0列第2列的各元素之和,求得sumx=22,因此答案为B。 4.阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”。相关代码如下: a=[["浙江省","杭州市"]，["吉林省","长春市"],["湖南省","长沙市"],["湖北省","武汉市"],["江苏省","南京市"],["广东省","广州市"]] for p in a: print(f"{ }的省会是{ }") 则划线①和②处分别应填写的代码为( ) A.①p[1];②p[0] B.①p[0];②p[1] C.①a[p][0];②a[p][1] D.①p[1];②p[2] 【答案】B [解析]考查数组的基本知识。遍历a数组的元素，p[0]获取省份,p[1]获取城市,因此①、②处分别应填写的代码为p[0],p[1]。 5.下列有关数据的描述正确的是（ ） A.数组是由多种不同类型的变量构成的一个序列 B.数组是由相同类型的变量构成的一个序列 C.一个数组在内存中的存储空间不一定是连续的 D.一个数组在内存中的存储方式为非顺序结构 【答案】B [解析]本题考查数组的定义。数组是由相同类型的变量构成的一个序列;一个数组在内存中的存储空间是连续的,存储方式为顺序结构。故选B。 6.有如下Python程序， n = 0，s = [1,1,2, 2, 2, 3, 1,1,3, 3] for i in range(0,len (s) - 1): if s [i] == s [i +1]: n+=1 else: n-=1 print(n) 执行以上程序后，变量n的值为( ) A.0 B.1 C.-1 D.2 【答案】B [解析]程序执行过程中，遍历列表中的前n-1个元素，若相邻两个位置的元素数值相同则执行n+=1操作，若不同则执行n-=1操作，故可计算出n = 1。故选:B。 7.有如下Python程序段: s =“22py4th18“ ; sum =t=0 for i in range(len (s)): if “0“<= s [i] <=“9“: t=t*10 +int (s [i]) else: sum+ =t t=0 print (sum) 执行该程序段后，变量sum的值为( ) A.22 B.26 C.40 D.44 【答案】B [解析]分析程序可知，当s[i]是数字时，则执行t=t*10 +int (s [i])，其他字符执行sum +t,t =0;最后一组数字后没有字符，所以t=18不会累加到sum中，此时sum =22+4=26。故选:B。 8.有如下Python程序段： ma=a[0] mb=a[0] pa,pb=0,0 for i in range(1,10): if ma<a[i]: ma=a[i] ; pa=i if mb>a[i]: mb=a[i] ; pb=i 下列关于该程序段功能描述正确的是( ) A.变量pa存储a[0]至a[9]中的最大值 B.变量ma存储a[0]至a[9]中的最小值 C.变量pb存储a[0]至a[9]中的最大值 D.变量mb存储a[0]至a[9]中的最小值 【答案】D [解析]if ma <a[i] : ma =a[i]; pa =i说明将较大的值存储在ma中;if mb> a[i]: mb=a[i];pb= i说明将较小的值存储在mb中故选:D。 9.采用列表模拟单向链表，datap0]为数据区域，datap为指针区域。在单向链表指针为p的 节点之后插入指针为s的节点，正确的操作是（） A.data [p][1]=s data [s] [1] == data [p] [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]= datal [s] [1] data [s] [1]=p 【答案】C [解析]在单向链表指针为p的节点之后插入指针为s的节点，则s的指针域指向p的下一个节点，即data[s][1]= data[p][1]，其次将p和s连接起来即p的指针域指向s，所以选项C符合题意。故选:C。 10.通过以下 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 ③L[p][1] =q ②q=p 则方框处语句依次为 A.③②① B.③①② C.①③② D.①②③ 【答案】A [解析]考查数据结构中链表的知识。将原链表转换为逆序链表,需要将原链表遍历一遍,记录链表指向,并进行交换逆向输出。观察代码,head为原链表头指针且p=head,当P值不为1即链表不为空时，执行tmp=L[p][1],将当前链表位指向临时放人p 并给其赋值为q,再将p赋值给q,然后将tmp赋值给p,准备下一轮赋值给q。如此循环,直到原链表的最后一位结束,最后 head 就是最后一次的位置。因此方框中可选的语句顺序是:L[p][1]=q-->q=p-->p =tmp。故选 A。 11.使用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“ 【答案】D [解析]根据引用域的排列顺序可知[“rabbit“，0][“cat“，1],[“dog“，2],[“pig“，-1]，列表是这样的顺序。故选:D。 12.某python 程序段如下: a=[28,29,79,14,24,43] m=int(input("请输入一个整数:")) pos=-1 for i in range(len(a)): if a[i]>m: if pos==-1 or a[i]<a[pos]: pos=i 运行该程序段，若输入40，变量pos的值是( ) A.-1 B.2 C.3 D.5 【答案】D [解析]改题通过遍历数组a中的元素，找出比40大的元素a[i]并且要满足pos==-1或a[i]<a[pos],最终输出该元素的下标i。 13.有下列python程序段: a=[3,7,8,2,19,10,16,12] n=len(a) for i in range(2): k=i for j in range(i+1,n): if a[k]<a[j]: k=j if i!=k: a[i],a[k]=a[k],a[i] 下列说法正确的是( ) A.程序段执行后，数组a中的元素为[19,16,8,2,3,10,7,12] B.程序段执行后，数组a中的元素为[3,2,8,7,19,10,16,12] C.程序段执行后，变量k的值为7 D.程序段执行后，数组a中数据元素发生位置变化的有2个 【答案】A [解析]找出数组中2个最大的数，并让其与前2个数组元素进行位置的交换。 14.有如下Python程序段: s = [1, 3, 4, 3,1] m，sum =s [0]，0 for i in range(1,len(s)): if s [i] > m: m = s [i] sum+=m 执行该程序后，sum的值为() A.15 B.12 C.11 D.7 【答案】A [解析]本题考查的是Python循环语句。For语句是循环语句，它的格式是:For变量=初值To终值[Step步长]循环体Next变量。len (s) = 5, range (1,len (8))生成序列数是1，2，3，4。i取到序列数1，时s1] -3>m成立，m = s[1] = 3,sum+=m=0+3=3；i取到序列数2，时s[2] =4>m成立，m =s[2]=4,sum+=m=3+4=7；i取到序列数3，时s[3]=3>m不成立，sum+=m=7+4=11;i取到序列数4，时s [4]=1>m不成立，sum+=m=11+4=15;最终sum =15。故选:A。 15.对于单向链表的节点结构，以下说法不正确的是（ ） A.节点的数据区域用于存放实际需要处理的数据元素 B.节点的指针区域用于存储相邻节点的存储地址 C.单向链表必须带有数据区域为空的头节点和尾节点 D.单向链表中的各个节点在内存中可以非顺序存储 【答案】C [解析]单向链表的头节点和尾节点可以是单独的数据区域为空的节点,也可以将节点序列中的第一个和最后一个节点作为头节点和尾节点。在Python程序设计时我们通常使用第二种方式,即直接使用带数据区域的节点作为头节点或尾节点来标记和使用。 16.有如下 Python 程序段: a =[[7,1],[8,2],[9,-1]] head =0 p=1 a. append([6,a[p][1]]) a[p][1] =len(a) -1 则程序执行后,下列说法正确的是 A.a[2][0]的值为6,链表a的尾结点数据值为6 B.a[2][0]的值为9,链表a的尾结点数据值为6 C.a[3][1]的值为2,链表a的尾结点数据值为9 D.a[3][1]的值为-1,链表a的尾结点数据值为9 【答案】C [解析]考查链表。程序创建了一个链表a,其节点数据值依次为7→8→9;然后在节点p之后插入一个新节点,使得链表各节点数据值依次为7→8→6→9,对应列表a的值为[[7,1]，[8,3],[9,-1],[6,2]],故答案为C。 17.采用列表模拟单向链表，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 【答案】C [解析]在单向链表指针为p的节点之后插入指针为s的节点，则s的指针域指向p的下一个节点，即data [s] [1] = data [p] [1]，其次将p和s连接起来即p的指针域指向s，所以选项C符合题意。 18.有个列表n =「‘水果’，‘砂糖橘’，’苹果’，‘橙子’]，请把列表中’苹果’改为’橘子’，选出修改正确的语句( ) A.n [2] = ‘橘子’ B.n[‘橘子’] C.n [3] = ‘橘子’ D.list[‘橘子’] 【答案】A [解析]由于列表的下标是从0开始的，列表中’苹果’为2，所以改为’橘子’的表达式为n[2] =‘橘子’。故选:A。 19.有如下 Python程序段: s=0 a=[[2,8,3],[1,6,4],[5,7,9]] for i in range(3): for j in range( 3) : if i==j: s=s+a[i][i] 程序段执行后,变量s的值为（ ） A.11 B.14 C.17 D.21 【答案】C [解析]本题考查二维数组的操作。程序的功能是求二维数组中正对角线上的元素之和,即s=2+6+9=17,故选C。 20.使用列表生成式创建数组代码如下a=[i*i-1 for i in range(10)ifi%2==0]则数组元素a[3]的值为( ) A.2 B.8 C.15 D.35 【答案】D [解析]本题考查的是python中列表的相关知识。从形式上看，列表会将所有元素都放在一对中括号 []里面，相邻元素之间用逗号，分隔，如下所示:[element1，element2，element3，..，elementn]，格式中，element1~elementn表示列表中的元素，个数没有限制，只要是Python 支持的数据类型就可以。从内容上看，列表可以存储整数、小数、字符串、列表、元组等任何类型的数据，并且同一个列表 中元素的类型也可以不同。已知i的取值范围为iin range(10)并且要求i的取值必须i%2==0，所以i的取值为[0，2，4，6，8]，可知a[3]=6*6-1=35.故选:D。 二、填空题（每空2分，共计40分） 1.在日常幻灯片(如使用PowerPoint制作的讲稿)的放映中，可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是 。 【答案】链表 [解析]行幻灯片之间的任意跳转的方式与链表的指针域有相似之处，该组织方式与链表的数据结构相似。 2. 将数组元素a[i]中各项的名称填入方框中： 【答案】①数组名、②下标/索引 [解析]数组是一组具有相同数据类型的变量集合，用一个数组名和下标来唯一确定数组元素。 3.在一个长度为n的数组中的第i个元素 (1<=i<=n) 之前插入一个新元素时，需向后移动的元素个数为 。 【答案】n-i+1 [解析]在数组中某个位置插入一个新的数据时，必须先将该位置及其后的所有数据向后移动一个位置。第i个元素的下标为i-1，故需要向后移动的元素个数为n-i+1。 4.在单向链表中，增加头指针的目的是 。 【答案】算法实现上的方便 [解析]每个链表必定有一个头指针，以实现对链表的引用和边界处理，即算法实现上的方便。 5.数组a的数据存放情况如下表，则当i=2时，a[6/i-1]的值是 。 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 48 52 98 26 47 22 82 33 【答案】52 [解析]解析:当i=2时，a[6/i-1]=a[6/2-1]=a[3-1]=a[2]=52。 6.在一个包含 n( n>1 ) 个节点的单链表上，没有头和尾两个指针，下列操作需要遍历多个节点的是 。 【答案】删除该链表中的最后一个节点 [解析]链表节点的删除，并没有将元素从列表中删除，而仅仅修改了节点指针域的值,通过将被删除节点的前驱节点和其后继节点直接相连的方式实现。题目中描述的该单链表中没有头指针和尾指针，此时若要删除该链表中的最后一个节点需遍历多个节点。 7.数组a和数组b的数据存放情况如下表，则b (a (8)) - a (8)的值是 。 数组a a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 7 4 -2 31 -7 9 25 6 数组b b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] 1 41 22 3 -7 5 9 6 【答案】-1 [解析]阅读题干可知，a(8) =6，所以b (a (8)) - a (8) =5-6=-1。故答案为:-1。 8.有如下python程序段: a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有 个节点。 【答案】4 [解析]程序创建了一个拥有4个节点的链表a，刚开始其头指针head 值为3，则头节点为a[3]。语句head=a[head][1]的作用是删除头节点，并让头指针指向新的头节点a[0]。故程序执行后，链表a的节点数量为3。 9.在程序运行过程中可以改变数组元素个数的是 数组，不可以改变数组元素个数的是 数组。 【答案】动态;静态 [解析]动态数组可以改变数组内的元素个数，静态数组的元素个数不可以改变。 10.有如下程序段: for i in range (3,5): for j in range(5,i,-1): if a[j] <a[j-1]: a[j]，a[j -1]=a[j -1]，a[j] 若数组a中的值为46，62，53，86，15，48，则执行该段程序后，a中的值变为 。 【答案】46,62,53,15,48,86 [解析]本题主要考查冒泡排序算法。冒泡排序的思路为将相邻位置的关键字进行比较，若为逆序则交换之，重复该过程直到序列已排好序;选择排序算法的思路是每一次从待排序的数据元素中选出最小(或者最大)的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小(或者最大)元素，然后放到已排序序列的末尾，依此类推，知道全部待排序的数据元素排完。阅读程序可知，外循环i的取值范围为3，4。所以当i=3时，那么内循环j的取值范围为5,4]所以当j= 4时，j-1=3，程序实现的是最后三个元素的升序排列。 11.有如下 python程序段: for i in range(1,1001): flag=True for j in range(3): if i%a[2*j]!=a[2*j+1]: flag=False if flag: ans=i break 已知列表 a=[3,1,5,1,7,3]，该段程序执行后，变量ans的值为 。 【答案】31 [解析]改题关键点在i%a[2*j]!=a[2*j+1]，分别把i和j的值代进去，发现当i的值为31和136时，flag的值都为True，但后面的 break语句决定了ans只会被赋值一次，所以ans=31。 12.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a: a=[[“hello”,1],[“china”,3],[“Olympics”,-1],[“winter”,2]] head=0 ①a[1][1]的值为 。 ②a[1][1]的含义是 。 【答案】①3②china后面指向的下一个节点是[“winter”,2] [解析]根据head=0，头节点是[“hello”,1]，依次访问的节点就是[“china”,3],[“Olympics”,-1],[“winter”,2]，因此输出的类容就是3。 13.已知有Python列表L表示一个单向链表,其中的子列表表示链表节点,子列表中第一个数据区域存储 节点中的实际数据,第二个数据区域存储节点的后继指针。现要实现逆序输出该链表的功能,首先将 该单向链表修改为双向链表,为其节点增加一个指针域,使得表示节点的列表中,第一个数据区域存 储链表节点中的实际数据,第二个数据区域存储节点的前驱指针,第三个数据区域存储节点的后继指 针。实现上述功能的Python程序如下。 L=[["A",3],["C",4],["D",-1],["E",6],["B",7],["G",0],["F",2],["N",5]] head=1 prev=head #初始化存储前驱指针的变量 cur=L[head][1] #初始化存储当前节点的变量 #头节点单独操作,其前驱指针为-1 L[head].append(L[head][1]) L[head][1]=-1 #为其余节点添加前驱指针 while len(L[cur]) == 2: L[cur].append(L[cur][1]) next=L[cur][1] #存储后继指针 L[cur][1]=prev prev= ① cur= ② tail=head #初始化尾节点的位置 While ③ : tail=L[tail][2] while tail!=-1: if L[tail][1]!=-1: print(L[tail][0],end="→") else: print(L[tail][0]) tail= ④ 请回答下列问题: (1)若有一Python列表link=[["W",3],["Q",2],["B",4],["C",1],["Y",-1]],head=0表示一个单向链表，若子列表中第一个数据表示节点的实际数据，第二个数据表示节点的后继指针,则将该单向链表根据题目要求修改为双向链表后,link的值变为 。 （2）请在划线处填入合适的代码。 【答案】(1)[["W",-1,3],["Q",3,2],["B",1,4],["C",0,1],["Y",2,-1]] (2)①cur②next③L[tail][2]!=-1④L[tail][1] [解析] (1)题目要求修改完成的列表中,子列表的第一个数据区域存储节点的实际数据,第二个数据区域存储节点的前驱指针,第三个数据区域存储节点的后继指针。首先判断单向链表的逻辑结构为W→C→Q→B→Y,根据逻辑结构,修改节点W的前驱指针为-1,存储在子列表中下标为1的位置,后继指针存储在下标为2的位置;修改节点C的前驱指针为节点W所在的位置下标,即0;修改节点Q的前驱指针为节点C所在的位置下标，即3，以此类推,得到双向链表的Python列表表示为[["W",-1,3],["Q",3,2],["B",1,4],["C",0,1],["Y",2,-1J]。 (2)①所在的while循环的作用是为除头节点之外的其余节点添加前驱指针。首先在节点中用append()方法再添加一个数据区域存储后继指针,然后再把原来存储后继指针的区城修改为存储前驱指针。变量prev存储的是前驱指针,此时要将prev赋值为下一个节点的前驱指针的值,也就是当前节点的位置,即变量cur的值;②处同样的道理,为下一次迭代做准备,下一个节点即是当前节点的后继,故将cur赋值为next;③处由于题目要求对双向链表进行逆序遍历,故需要从尾节点开始对链表进行遍历输出.tail存储尾节点的位置,while循环的作用是找出尾节点,尾节点的特征是后继指针为空,故当节点后继指针不为空时继续迭代,故填入代码为L[tail][2]!=-1;④处逆序遍历双向链表,tail根据节点的前驱指针进行迭代，故填入代码为L[tail][1]。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $