6.1 实时查询系统中数据的组织（分层作业）信息技术浙教版2019选择性必修1

6.1实时查询系统中数据的组织 2课时（分层作业） 【基础达标】 1. 利用分布在不同物理位置的服务器来分担系统存储任务，既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有较好的 。 2.实时查询系统的两个特殊性： 、 。 3.针对在数组中插入新元素时引起的数据移动低效的问题，可以考虑用 代替 。 4.数据序列在不断地变化，所以需要对关键节点进行动态的调整，即数据增加时增设 ，而数据减少时删除 。 5.某班级的同学制作了一个以“加油吧高考”为主题的网站，现在他想让别人来共同分享欣赏他们的作品，那么可以通过()方式来发布。 ①在网上邻居中发布 ②保存到电子邮箱中 ③在因特网上发布 ④在本机上发布， A.①②③ B.①②④ C.①③④ D.②③④ 6.如图所示，此网站发布方式属于() A.因特网上发布 B.局域网内发布 C.本机发布 D.网上邻居发布 7.下列关于数据结构的说法正确的是() A.同一数据元素中各数据项的数据类型一定相同 B.跳跃表是立足链表、借鉴二分查找的思想而形成的数据结构 C.若入栈序列为abcd，则出栈序列可能为dbca D.在浏览器中执行“后退”、“前进”操作的原理与队列的特点相同 8.下列选项中可以看出都是文本文件的选项是() A.学习强国.doc、lover.SWF B.湖北省12月计算机调考成绩.xls、校运会 成绩排序.exe C.算法代码.txt、九九乘法表.docx D.Python.exe、21.swf 9.关于结构化程序设计所要求的基本结构，以下描述错误的是() A.重复(循环) B.选择(分支) C.goto 跳转 D.顺序 10.一个数组的第一个元素的存储位置为1000(表示在第1000个字节处)，每个元素所占空间大小为8个字节，则第5个元素的位置是（ ）? A.1000 B.1040 C.1032 D.1256 【巩固提升】 1.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 2.递归算法的函数调用时,处理参数和返回地址,通常使用的数据结构是（） A.数组 B.链表 C.队列 D.栈 3.算法的时间复杂度是指什么?() A.算法执行所需的时间 B.算法中语句的数量 C.算法所需内存空间 D.算法执行所需时间随输入规模增长的趋势 4.若数据库中有10万条记录以链表形式有序存放,现要在原链表基础上增设关键节点创建索引,若以二分的形式创建每一级索引,则最多需要创建索引的级数是() A.8 B.17 C.100 D.1000 5.有如下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 6.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 7.阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”。相关代码如下: 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] 8.通过以下 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.①②③ 9.使用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“ 10.arr=[1,3,4,5,6,8,9,12,15,0] #0表示该位置未存储元素 num=int(input("输入需要插入的数据:")) for i in range(len(arr)): if arr[i]>num: for j in range(len(arr)-1,i-1,-1): arr[j]=arr[j-1] arr[i]=num break else: arr[-1]=num print(arr) 执行该程序段后,输入数字9,则位置下标发生改变的数据个数是() A.3 B.2 C.1 D.0 11.下列Python程序的功能是在数据有序的链表中插入一个整数，使链表中的数据仍保持有序. a=[[8,3],[6,0],[2,1],[11,4],[15,-1]] n-int(input("请输入一个整数:")) p=q=head=2 if n<=a[head][0]: a.append([n,head]) ① else: while p!=-1 and ②: q=p p=a[p][1] a.append([n,p]) a[q][1]=1en(a)-1 划线处应填入的代码是() A.①head=a[p][1] ②n>a[p][0] B.①head=a[p][1] ②n>a[q][0] C.①head=len(a)-1 ②n>a[p][0] D.①head=len(a)-1 ②n>a[q][0] 【链接高考】 1.已知1班、2班各有m位同学，要在两个班中挑选身高最高的n位同学参加合唱队。小明编写了如下程序： a=[0]*m;b=[0]*m;hc=[0]*m #读取两个班同学的身高数据，分别存储在数组a、数组b中；分别将两个班同学的身高数据进行降序排列，代码略。 m1,m2=0,0 for i in range(n): if a[m1]>=b[m2]: hc[i]=a[m1] ____①_______ else: c[i]=b[m2] _____②_______ print(“身高前n位的值是：”，hc) 2.已知有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）请在划线处填入合适的代码。 3.有以下Python代码段: def jishu(n): s=0 while n>0: s+=n%2 n//=2 return s n=int(input("输入一个正整数:")) ans=jishu(n) print(ans) 阅读以上代码,回答以下问题: (1)该程序运行后输入整数23,输出结果为 。 (2)若输入整数23,则程序中自定义函数jishu( )中语句"s+=n%2”执行的次数是 。 (3)函数jishu( )的时间复杂度为 (单选:A.〇(n) B.〇(log2n))。 4.当数据从磁盘数据库读取出来并保存到内存中时,需要考虑用某种数据结构来组织并存储。这种数据结构既能体现数据之间的逻辑关系,又能为后续的查询提供算法上的支持。假如有一组由1000万个有序的整型数据组成的集合,希望使用某种数据结构在插人、删除、查找等操作上尽量高效,请回答下列问题: (1)采用数组组织处理该组数据。 ①假设查找一个元素需要0.5 毫秒,若使用顺序查找,则最多需要花费的时间为 毫秒;若使用二分查找,则最多需要花费的时间为 毫秒。 ②在数组中插入和删除操作所需的时间复杂度为 。 (2)采用链表组织处理该组数据。 ①在链表中查找一个元素所需的时间复杂度为 。 ②在链表中插入和删除操作所需的时间复杂度为 。 (3)采用跳跃表组织处理该组数据。 ①跳跃表是基于链表,借鉴二分查找思想而形成的数据结构。为原有序链表增设一组关键节点作为一级索引,需要增设的关键节点的数量为 。 ②最多需要创建索引的级数为 。 5.杨辉三角是二项式系数在三角形中的一种几何排列,在我国南宋数学家杨辉1261年所编写的《详解九章算法》一书中出现。我们可以把杨辉三角看作这样的图形:最左侧一列数字和右边的斜边数字均为1,内部其他位置上的每个数字均为上一行同一列的数字与上一行前一列数字之和,前10行的杨辉三角如图2-1所示。 (1)为了在计算机中存储和处理如图2-1所示的数据,可用如图2-2所示的二维数组来表示。从图2-2中可知数字“6”存储在数组元素pas[4][2]中,其值由数组元素 和 相加得到。 (2) 在程序设计时,先将数组pas中的数据元素均赋初值为1,然后从数组元素 开始进行计算(数字“1”无须再次计算)。 (3)实现输出该图形的代码如下,在程序划线处填入适当的语句或表达式。 n = int(input("请输入行数n-")) #输出n行的杨辉三角 pas =[[1 for i in range(n)] for j in range(n)] for i in range(2,n): for j in range( l,i): pas[i][i] = pas[i-1][j-1]+ ① for i in range(n): s=[] #定义列表s用于输出每一行所需数据 for j in range( ② ): s.append(pas[i][i]) print(s) 程序中划线①处应填人 。 程序中划线②处应填人 。 6.打印杨辉三角。利用队列打印杨辉三角形,杨辉三角形的图案如下图所示。 由图可看出杨辉三角形的特点:每一行的第一个元素和最后一个元素均为1,其他位置上的数字是其上一行中与之相邻的两个整数之和。所以第i行上的元素要由第i-1行中的元素来生成。可以利用循环队列实现打印过程:在循环队列中依次存放第i-1行上的元素,然后逐个出队并打印,同时生成第i行元素并入队。 使用队列的思想来实现杨辉三角的流程: ①首先,需要初始化一个队列,即队头一队尾=0; ②将第一行的元素1入队,接着操作第二行(一二行不需要求和操作,直接将元素入队即可); ③从第三行开始,现在的队头指向i-1行,先将每行的固定元素1人队,然后循环操作求和过程:将队首元素出队,并保存它的值temp;获取当前队头的元素x,并进行temp=temp+x,且将temp入队; ④循环结束后,队头在i-1行的最后一个元素处,现将其出队,然后将每行最后的固定元素1入队; ⑤循环3、4步就可以输出杨辉三角形了。 实现上述功能的Python代码如下,请回答问题。 (1)请写出杨辉三角形第7行的输出结果。 (2)请在程序划线处填上合适的代码。 maxsize=100 head=0 tail=0 que=[""]* maxsize #建队 x=0 def que_in(x): #入队 global tail if (tail+1)%maxsize==head: return None else: ① tail=(tail+1)%maxsize def que_out(): #出队 global head if head==tail: return None else: x=que[head] head= ② return x def gethead(): #获取队头元素 global head if head==tail: return None else: x=que[head] return x n=int(input("输入行数:")) que_in(1) #第一行入队 for i in range(2,n+2): que_in(1) #第i行的第一个入队 for j in range(1,i-1): #利用第i-1行元素产生第i行的中间i-2个元素，并入队 temp=que_out() print(temp,end=") x=gethead() ③ que_in(temp) x=que_out() print(x) #打印第i-1行的最后一个元素 que_in(1) #第i行的最后一个元素 入队 7.在一个有序数据构成的链表中插入一个新的节点,使得新链表仍保持有序。程序运行时,首先创建一个由升序序列构成的链表,输入要插入的数据,输出插入操作后的新链表。程序运行界面如下图所示: 原链表为: [[4,1],[9,2],[11,3],[15,4],[19,5],[24，-1] 请输入要插入的数据:20 新链表为: [[4,1],[9,2],[11,3],[15,4],[19,5],[20，6],[24,-1]] 实现上述功能的Python程序如下,请在划线处填入合适的代码。 from random import randint head=-1 a=[] #a[i][0]为第i个节点的数据区域，a[i][1]为指针区域 temp=randint(1,10) a.append([temp,head]) for i in range(1,6): temp=a[i-1][0]+randint(1,5) a.append([temp,head]) for i in range(l,6): temp=a[i-1][0]+randint(1,5) a.append([temp,head]) a[i-1][1]=i print("原链表为:") print(a) key=int(input("请输入要插入的数据:)) head=0;p=head if a[p][0]>=key: a.append([key,0]) ① else: while a[p][0]<key and a[p][1]!=1: p=a[p][1] if a[p][1]==-1and a[p][0]<key: a.append([key,-1]) ② else: a.append([key,p]) ③ print("新链表为:");print(a) print("新链表中数据系列为:") p=head while a[p][1]!=-1: print(a[p][0],end="") ④ print(a[p][0]) 划线①处应填入的代码为 ; 划线②处应填入的代码为 ; 划线③处应填入的代码为 ; 划线④处应填入的代码为 。 8.假如用某种数据结构来维护一组由有序的整型数据组成的集合,并且希望这个数据结构在插人、删除、查找等操作上尽可能高效,那么,该用何种数据结构来实现呢? (1)一种简单的方法是采用数组。在查找方面,用数组存储的话,采用顺序查找可以在 (填写时间复杂度)的时间里找到指定元素,采用二分法可以在 的时间里找到指定的元素。假设检查一个元素需要1毫秒,使用顺序查找时,检查10亿个元素可能需要10亿毫秒,采用二分查找,则大约需要 毫秒。不过数组在插入,删除这些操作中比较不友好,进行插入和删除操作所需的时间复杂度为 ,所以最终所需要的时间复杂度 。 (2)另一种简单的方法是采用链表。链表在插入或删除操作上相对友好,当我们找到目标位置之后,插入、删除元素所需的时间复杂度为 。但链表在查找操作上比较不友好,不能像数组那样采用二分查找的方式,只能一个一个节点地遍历,所以查找所需的时间复杂度为 ，所以最终所需要的时间复杂度为 。 (3)还可以使用跳跃表进行查询。对于如图1所示的链表: 假如要查找元素9.则需要从头节点开始遍历 次才能找到。 由于元素的有序性,可以通过增加一些路径(索引,如图2所示)来加快查找速度。 通过这种方法,我们只需要遍历元素 ,共遍历 次就可以找到元素9。 我们还可以再增加二级索引,如图3所示。 通过这种方法,我们只需要遍历元素 ,共遍历 次就可以找到元素9。 参考答案 【基础达标】 1.分布式存储系统、可扩展性。 2.能实现上千个请求的实时响应、支持后续商品信息的更改。 3.链表、数组 4.关键节点、关键节点 5.【答案】C [解析]本题考查信息发布的方式，信息发布的类型多种多样，大致可分为两种:一种是借用现成的网络工具和资源发布信息，另一种是建立自己的网站发布信息。题目中的1和3是借助网络进行发布，4在本机建立自己的网站进行发布，故通过1、3、4都能实现让别人来分享自己他们的作品。故选:C。 6.【答案】C [解析]在因特网上发布网站:①申请网站空间:ISP:互联网服务提供商②上传网站:常用的FTP工具:CuteFTP、LeachFTP、WebPublisher等维护和宣传网站包括:①内容的更新，如文字、图片、动画等信息的校对、增加和修改等②根据信息发布活动的需求，阶段性地调整网站的整体风格，如更换版面结构，颜色搭配等。通过图片可知，是在本地的D盘上发布的，故选:C. 7.【答案】B [解析]跳跃表(SkipList)是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(log N)。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。故选项B说法错误。故选:B。 8.【答案】C [解析]文本文件主要包括:txt(所有文字处理软件或编辑器都可打开)、doc(word及wps等软件可打开)、hlp (adobe acrobat reader可打开)、wps(wps软件可打开)、rtf(word及wps等软件可打开)、html(各种浏览器可打开、用写字板打开可查看其源代码)、pdf(adobe acrobat reader和各种电子阅读软件可打开)等.A:doc为电子文档;SWF是基于矢量的Flash动画[3]文件格式，A错误;B: xls是电子表格;exe是可执行文件[4]，B错误;C:txt是文本文档;docx是电子文档，C正确;D:exe是可执行文件，swf是基于矢量的Flash动画文件格式，D错误.故选C. 9.【答案】C [解析]本题主要考查程序基本结构。结构化程序设计所要求的基本结构，包括三种:重复(循环)、选择(分支)和顺序结构，故本题选C选项。 10.【答案】C [解析]第五个元素的存储地址为1000+8×（5-1）=1032 【巩固提升】 1.【答案】D [解析]算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 2.【答案】D [解析]本题主要考查的是递归算法。计算机在执行递归程序时，是通过栈结构的调用来实现的，因此答案为D。 3.【答案】A [解析]所谓算法的时间复杂度，是指执行算法所需要的计算:工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程叶，所需基本运算的执行次数米度量.算法的工作量。故选:A。 4.【答案】B [解析]二分查找最多的查找次数为[log2n]+1。 5.【答案】C [解析]本题主要考查的是二维数组创建与访问。数组a为间接创建方式，当某个元素值改变时，对应的该列所有值改变，数组b使用的是列表生成式创建,各个元素独立。 6.【答案】A [解析]本程序只包含顺序结构，时间复杂度为〇(1),因此,答案为A。 7.【答案】B [解析]考查数组的基本知识。遍历a数组的元素，p[0]获取省份,p[1]获取城市,因此①、②处分别应填写的代码为p[0],p[1]。 8.【答案】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。 9.【答案】D [解析]根据引用域的排列顺序可知[“rabbit“，0][“cat“，1],[“dog“，2],[“pig“，-1]，列表是这样的顺序。故选:D。 10.【答案】B [解析]当数组arr中的元素arr[i]大于新数据num时,则将位置i及其之后的数据都向后移动,所以当输入的数字为9时,12大于num,则12和15的位置下标将发生改变。 11.【答案】C [解析]本题考查Python程序。首先分析程序逻辑，程序要在有序链表中插入一个整数n并保持有序。如果n小于等于表头元素的值，就在表头插入。否则，通过循环找到合适的插入位置。对于①处，如果n小于等于表头元素，要更新表头指针，应将表头指针指向新插入元素，即head=len(a)-1。对于②处，在循环中要判断n是否大于当前指针所指元素的值，即n>a[p][0]。故答案为: C。 【链接高考】 1.【答案】①处填m1=m1+1,②处填m2=m2+1 [解析]根据题目要求要把数组a和数组b中最大的n个身高数据存入数组hc中，当选择数组a的数据存储后，对应数组a的下标m1后移；同理，当选择数组b的数据存储后，对应数组b的下标m2后移。 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]。 3.【答案】(1) 4 (2)5 (3) B [解析]代码实现的功能是统计正整数n的二进制表示中1的个数，利用while循不每次将n整除2。直到商是0为止。23D-10111B，所以有4个"1"；"23”在统计过程中“s+=n%2”会执行5次，所以该算法的时间复杂度为〇(log2n)。 4.【答案】(1)①500 万;12②〇(n) (2)①〇(n)②〇(1) (3)①500 万②24 [解析](1)①顺序查找是从数组中第1个元素开始,逐个查找,需要遍历整个数组,所以最多要花费的时间为0.5×1000万=500万毫秒。二分查找的时间复杂度为〇( log2n),223<10000000<224,所以最多要花费的时间为0.5×24=12毫秒。②将新元素插入到数组中必须先将插入位置及其后面的所有元素依次往后移一位，所以需要的时间复杂度为〇(n)。 (2)①在链表中查找一个元素需要从链表的一端依次遍历查找,所以时问复杂度为〇(n)。②在链表中插入或删除元素不需要移动数据,只需要修改对应节点的指针值,所以时间复杂度为〇(1)。 (3)①原链表中的一半节点会出现在关键节点中。②最多需要创建索引的级数等于二分查找最多的查找次数,为24。 5.【答案】(1) pas[3][1]pas[3][2] (2) pas[2][1] (3) ①pas[i-1][j]②i+l [解析](1)本题使用了二维数组来存储每一行的数据,根据图2-2所示的二维数组的行、列下 标,可知数字“6”位于第5行第3列(pas[4][2]),其值通过上一行前一列元素pas[3][1]和上一行同一列元素pas[3][2]计算可得。 (2)根据图2-2所示,数组元素初始化为1后,可从数字“2”开始计算,数字“2”所在的数组元素为pas[2][1]。 (3)下三角部分位置上的每个数字均为上一行同一列的数字与上一行前一列的数字之和,pas[i-1][j-1]为上一行前一列数据,则①划线处的代码应该为上一行同一列的数据,即 pas[i-1][i]。根据二维数组下标的规律,第i行的列下标的值为0到i-1,注意题图中的行数是1到10行,行列的数组元素下标从0开始编号,每一行需要输出的数据只包含图2-2中的下三角部分,因此②划线处的代码为i+1。 6.【答案】(1)第7行结果为:16 15 20 15 6 1 (2)①que[tail]=x②(head+1)%maxsize ③temp=temp+x [解析]解析本题考查队列的程序实现。题目描述中已经非常清晰地描述了算法思想,que[tail]=x入队操作。②出队操作,head十1。从第三行开始，现在的队头指向i-1行,先将每行的固定元素1入队,然后循环操作求和过程:将队首元素出队，并保存它的值temp;获取当前队头的元素x,并进行temp=temp十x,且将temp入队。 7.【答案】①head=len(a)-1；②a[p][1]=len(a)-1； ③a[p-1][1]=len(a)-1；④p=a[p][1] [解析]①处表示在头节点前插入新节点，新节点变为头节点，需要将头指针指向新插入的节点，新节点添加在数组的末尾，即 head=len(a)-1;程序②处表示在链表最后插入节点，需将p节点的指针域赋值为新节点的位置,即②处代码为a[p][1]=len(a)-1;程序③表示在链表中间插入新节点，需先将插入节点的指针域修改为p,然后将p一1节点的指针指向最后一个插入的节点，因此③处代码为a[p-1][1]=len(a)-1;输出链表时,通过p=a[p][1]来获取当前节点的后一个节点的位置，因此④处代码为p=a[p][1]。 8.【答案】(1)〇(n)；〇( log2n)；30；〇(n)；〇(n) (2)〇(1)；〇(n)；〇(n) (3)8；0,2,6,8,9;5；0,6,8,9；4 [解析](1)根据数组的特性及二分查找次数的计算公式可知,采用顺序查找需要遍历整个数组,时间复杂度为〇(n),采用二分查找的时间复杂度为〇(log2n)。10亿个元素采用二分查找只需查找30次,故时间为30毫秒。但进行插入或删除操作的时间复杂度为〇(n),所以最终所需要的时间复杂度为〇(n)。(2)链表插入或删除元素无须移动数据,时间复杂度为〇(1),但查找数据需要从链表的一端依次遍历查找,因此最终所需要的时间复杂度为〇(n)。(3)在题图1的链表中,需要遍历0,1,2,5,6,7,8,9,共8次。在题图2的链表中,可从一级索引开始,遍历0,2,6,8,9,共5次。在题图3的链表中,从二级索引开始,遍历0,6,8,9,共4次。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$