2023—2024学年高中信息技术浙教版（2019）选修1 第五章数据结构与算法同步作业

第五章数据结构与算法同步作业2023—2024学年高中信息技术浙教版（2019）选修1 1．图结构中的元素之间存在的关系是(  )。 A．一对一 B．一对多 C．多对一 D．多对多 2．已知单调函数f（x0）在[1，2]区间存在一个x0，使f（x0）=0。现用对分查找法无限逼近x0的值，开始检索的区间为[1，2]，若经过8次检索，还未达到要求，需要第9次检索，那么第9次检索的区间长度为（    ） A．1/8 B．1/9 C．1 / 28 D．1 / 2 9 3．由n个节点链接成的单链表如图所示，其中head为头指针。 使用列表link模拟该链表结构，每个节点包含数据域和指针域，如图中最后一个节点可以表示为［98，-1］。现要删除指针p所指向的节点，可以实现该操作的语句有（   ） ① link[p][1] = - 1        ② link[head][1] = q ③ link[head][1] = link[p][1]    ④ head = link[p][1] A．①② B．①③ C．②③ D．②④ 4．使用升序排序算法对列表[130,20,98,15,67,3 ]进行排序后结果为（    ） A．[130,20,98,15,67,3 ] B．[3,15,20,67,98,130 ] C．[15,20,98,67,3, 130] D．[130,98,67,20,15,3 ] 5．在浏览网页时，可以通过超链接的方式实现网页间的跳转。与这种网页之间相互链接的表现形式相似的数据结构是（   ） A．队列 B．栈 C．链表 D．树 6．用二分法求解 x3- x2 + x - 1 = 0，完善下面程序。 def f(x):     #定义方程     return x**3-x**2+x-1 a=float(input("请输入解区间的左边界：")) b=float(input("请输入解区间的右边界：")) while abs(b-a)>1e-6:     x0=(a+b)/2     if （   ①   ）:         b=x0           if （   ②   ）:         a=x0        if （   ③   ）:         break print("解为:",x0) input("运行完毕，请按回车键退出...") 程序中①②③处分别填入（  ） A．①f(a)*f(x0)>0；②f(b)*f(x0)<0；③f(x0)==0 B．①f(a)*f(x0)<0；②f(b)*f(x0)<0；③f(x0)==0 C．①f(a)*f(x0)<0；②f(b)*f(x0)<0；③f(x0)=0 D．①f(a)*f(x0)<0；②f(b)*f(x0)>0；③f(x0)==0 7．有如下Python程序段: a=[1,20,15,6,9,12,30,8,7,5] n=len(a) sumx=0 for i in range(n):     if a[i]%3==2:         sumx=sumx+a[i] print(sumx) 该程序段执行后,输出的结果为（   ） A．25 B．28 C．33 D．72 8．有如下自定义函数： def fg（n）：    if n<=2：       return n    else：       return fg（n-1）+fg（n-2） 执行语句s=fg（4），下列说法不正确的是（   ） A．s的值为5 B．函数fg被调用的次数是4 C．第二次被调用的函数是fg（3） D．该程序采用了递归算法 9．下列不是栈的基本运算的是（   ） A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．将栈置为空 10．一次运动会上，某组6位选手的百米成绩(单位：秒)分别是“14.1、12.3、11.2、14.8、13.9、11.0”，若使用选择排序法将该组的成绩按第一名、第二名、第三名……的顺序排序，则第一次交换数据后的顺序是（ ） A．14.8 14.1 12.3 11.2 13.9 11.0 B．11.0 12.3 11.2 14.8 13.9 14.1 C．14.8 12.3 11.2 14.1 13.9 11.0 D．11.0 14.1 12.3 11.2 14.8 13.9 11．全国航运图属于（   ） A．线性结构 B．树结构 C．图结构 D．以上均不是 12．下图是物流配送线路图，是树结构，下列说法错误的是( ) A．一级快件集散中心是树的根结点 B．二级公共配送中心进行地域分配，是一级快件集散中心根结点下的子树 C．共同配送点是二级公共配送中心的子树 D．共同配送点-社区便利店的树的深度是3 13．有如下 Python 程序段 from random import randint k=randint(0,2)*2 i=0;j=6;cnt=0 while i<=j:    cnt=cnt+1    m=(i+j)//2    if a[m]==a[k]:       break    if a[m] < a[k]:       i=m+1    else:       j=m-1 数组元素 a[0]到a[6]各不相同且按升序排列，执行该程序段，下列说法不正确的是（   ） A．m 的值不可能为 6 B．cnt 的值一定为 3 C．变量 i 、j  的值一定相同 D．i  的值可能小于 m 14．运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（    ） A．问题性质相同，问题规模相同 B．问题性质不同，问题规模相同 C．问题性质相同，问题规模不同 D．问题性质不同，问题规模不同 15．定义如下函数： def f（a，s）：     if a>=s：         return a     else：         return f（a+1，s-a） 执行语句k=f（6，21）后，k的值为（   ） A．6 B．7 C．8 D．9 16．在上体育课的时候同学们随便排了队伍，老师要求按照身高从高到低依次排队，如果按照插入排序算法，第一步要做的是（   ） A．前2位同学从高到低排 B．前2位同学从低到高排 C．最高的同学跟最低的同学交换位置 D．最高的同学跟第一位同学交换位置 17．小明学习了算法后，写了以下两段代码来求斐波那契数列的第6项： a=1;b=1 for i in range(2,6): c=a+b a=b b=cprint(c) def f(n): if n==1 or n==2: return 1 else: return f(n-1)+f(n-2) print(f(6)) 算法一 算法二 下列说法正确的是（    ） A．两种算法的时间复杂度均为O（1） B．算法一是迭代算法，算法二是递归算法，相比之下，算法二的时间效率更高 C．执行算法二代码，f（4）共被调用了2次 D．执行算法一代码，当i=4这一遍循环刚结束时，a的值等于5 18．有如下 VB 程序段： Dim n As Integer Dim sum As Integer Dim i As Integer Function fx(i As Integer) as Integer   If i = 1 Then fx = 5   Else   fx = 5 * 2 ^ (i - 1) + fx(i - 1)   End   if End Function Private Sub Command1_Click()   n = Val(Text1.Text): sum = 0   For i = 1 To n     sum = sum + fx(i)   Next i   Label1.Caption = Str(sum) End Sub 若在 Text1 中输入4，单击 Command1，则 Label1 中显示的内容为（   ） A．55 B．75 C．80 D．130 19．有如下Python程序段： a=[40，14，10，19，24，45]；n=len（a） for i in range（n-1）： flag=False for j in range（n-l，i，-1）： if a[j]>a[j-l]：    a[j]，a[j-l]=a[j-l]，a[j]    flag=True if not flag:break 执行该程序段后，下列说法正确的是（    ） A．该程序实现将数组a升序排序 B．元素14在程序运行过程中被交换2次 C．该程序的时间复杂度为0(n) D．程序结束后，i的值为3 20．下列有关迭代算法和递归算法的描述，不正确的是（   ） A．在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B．一般来说，迭代算法效率较低，而递归算法效率较高 C．递归中一定有迭代，但迭代中不一定有递归 D．通常情况下，迭代算法和递归算法可以相互转换 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题主要考查图结构。图结构中的元素之间存在的关系是多对多，故本题选D选项。 2．C 【详解】本题主要考查对分查找知识点。第一次检索的长度是20=1，第二次检索的长度是1/2，第三次检索的长度是1/22，那么第k次检索的区间长度是1/2k-1，故第9次检索的区间长度为1 / 28，故本题选C选项。 3．C 【详解】本题考查数据结构链表操作相关内容。要删除头节点后面的节点，只需将头节点的next指针指向下一个节点的下一个节点即可。link[p][1] = - 1操作使得指针p所指向的节点变为尾节点，不能实现删除操作。head = link[p][1]操作使得指针p所指向的节点变为头节点，不能实现删除操作。link[head][1] = q、link[head][1] = link[p][1] 可以实现删除指针p所指向的节点。故本题答案是C选项。 4．B 【详解】本题主要考查升序排序算法。使用升序排序算法对列表[130,20,98,15,67,3 ]进行排序后结果为[3,15,20,67,98,130 ]，故本题选B选项。 5．C 【详解】本题考查数据结构相关内容。网页之间通过超链接的方式来实现网页间的跳转，符合链表的特征，故本题答案为C选项。 6．B 【详解】本题主要考查Python程序及二分法。变量a保存区间左边界，变量b保存区间右边界，由代码“b=x0”可知①处填f(a)*f(x0)<0，同理②空填f(b)*f(x0)<0，当f(x0)==0时，则说明x0是方程的解，故③处填f(x0)==0，故本题选B选项。 7．C 【详解】本题考查Python程序设计相关内容。程序段功能是求数组a中的除3余2的元素之和，除3余2的数据有:20、8、5，因此sumx=20+8+5=33，故本题答案为C选项。 8．B 【详解】本题考查递归算法的应用。执行语句s=fg(4)=fg(3)+fg(2)=fg(1)+fg(2)+fg(2)=1+2+2=5，因此s的值为5；函数fg被调用的次数是6；第二次被调用的函数是fg(3)；该程序采用了递归算法。故选B。 9．B 【详解】本题考查数据结构相关内容。栈的操作有删除栈顶元素、判断栈是否为空、将栈置为空等。栈的插入和删除操作只能在栈顶进行，故本题答案为B选项。 10．B 【详解】本题考查的是选择排序。选择排序是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。故则第一次交换数据后的顺序是：11.0 12.3 11.2 14.8 13.9 14.1。选项B正确。 11．C 【详解】本题考查图数据结构的描述。图是最为复杂的数据结构，如果数据元素之间存在一对多或者多对多的关系，那么这种数据的组织结构就叫作图结构。全国航运图存在多对多的关系，属于图结构。线性结构和树结构不存在多对多的关系。故选C。 12．D 【详解】本题主要考查数据结构的应用。由图可知，是树结构，一级快件集散中心是树的根结点；二级公共配送中心进行地域分配，是一级快件集散中心根结点下的子树；共同配送点是二级公共配送中心的子树；共同配送点-社区便利店的树的深度是4，故本题选D选项。 13．D 【详解】本题主要考查二分查找算法。k=randint(0,2)*2，k是随机生成0、2、4， 以m的值绘制二叉树如下，显然m 的值可能为 6；k的取值对应树的第三层，cnt 的值一定为 3；循环会遍历到树的第三层，第三层变量 i 、j   的值一定相同；i  的值不可能小于 m，故本题选D选项。    14．C 【详解】本题主要考查分治算法。分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题的性质相同，规模不同，故本题选C选项。 15．C 【详解】本题考查递归算法及自定义函数。由自定义函数f（a，s）可知：当参数a≥s时（即递归结束条件），返回值a,否则递归调用f（a+1，s-a）。执行语句k=f（6，21），第一次调用函数f（6，21）未达到递归结束条件，第二次调用函数f（7，15）；未达到递归结束条件，第三次调用函数f（8，8），满足递归结束条件a≥s，返回值为a，得到答案8，故选C。 16．B 【详解】本题主要考查插入排序算法。插入排序的思想是： 将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。在上体育课的时候同学们随便排了队伍，老师要求按照身高从高到低依次排队，如果按照插入排序算法，第一步要做的是前2位同学从低到高排，其余学生在已排序好的学生序列中找到合适的位置依次插入即可，故本题选B选项。 17．C 【详解】本题主要考查算法的应用。两种算法的时间复杂度均不为O（1）；算法一是迭代算法，算法二是递归算法，相比之下，算法一的时间效率更高；执行算法二代码，f（4）共被调用了2次；执行算法一代码，当i=4这一遍循环刚结束时，a的值等于3，b的值等于5，故本题选C选项。 18．D 【详解】本题考查对递归算法的掌握。递归即调用自身函数在函数中，每次循环调用5*2^(i-1)+f(i-1)，当i为1时，直接返回5，作为递归边界。i等于4，则第一次计算f函数得到f(4)=40+f(3)，得到f(3)=20+f(2)，再次计算f(2)得到 f(2)=15，因此f(1)=5，f(2)=15，f(3)=35，f(4)=75，四个数累加为130。故选D。 19．D 【详解】本题主要考查排序算法及Python程序实现。该程序实现将数组a降序排序；元素14在程序运行过程中被交换3次；该程序的时间复杂度为0(n2)；当i=3时，a已有序，因此程序结束后，i的值为3，故本题选D选项。 20．B 【详解】本题考查迭代和递归算法。迭代算法通常效率较高，而递归算法可能效率较低。这是因为递归算法在递归调用时需要保存上下文，包括局部变量和返回地址，而这可能导致开销较大。此外，递归算法在递归深度较深时可能引起栈溢出，因此需要小心处理递归深度。故答案为B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$