第五章 数据结构的应用 2024-2025学年高中信息技术粤教版(2019) 选修1

第五章 数据结构的应用 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．图书管理系统对图书管理是按图书的序号从小到大进行管理的，若要查找一本已知序号的书，则能快速地查找到的算法是（   ） A．枚举算法 B．选择排序 C．对分查找 D．冒泡排序 2．数据结构设计的主要目的是（     ） A．只为了数据的存储 B．反映数据之间的逻辑关系并提高数据处理效率 C．仅仅为了美观地展示数据 D．无特定目的，仅作为编程习惯 3．关于迭代与递归算法，下列说法错误的是（   ） A．迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B．递归是重复调用函数自身 C．迭代程序可以转换成等价的递归程序 D．迭代和递归是同一种算法的两种不同的表述 4．有如下 Python 程序段： import random a=[4,2,6,5,4,2,9,7] k=random.randint(1,10) i=0;j=len(a)-1;x="" while i<=j:    m=(i+j)//2    if k<=a[m]:       j=m-1;x=x+"L"    else:       i=m+1;x=x+"R" print(x) 执行该程序段后，输出的结果不可能出现的是（   ） A．"LLL" B．"LRL" C．"RLR" D．"RRRR" 5．阅读下列用二分法查找输入的1000以内的整数次数的程序 x=int(input("请输入要查找的1000以内的整数:")) step=0 flag1=1 flag2=1000 while(flag1<=flag2):     mid=①       step=step+1     if mid>x:         flag2=②           elif mid<x:         flag1=③         else:                break print("查找次数为："，step) input("运行完毕，请按回车键退出...") 下列说法正确的是（  ） A．①处填(flag1+flag2)/2，②处填mid-1，③处填mid+1 B．①处填(flag1+flag2)//2，②处填mid-1，③处填mid+1 C．①处填(flag1+flag2)//2，②处填mid+1，③处填 mid-1 D．以上都不对 6．有如下对分查找程序段    #列表a存放整数升序数据，代码略    key=int(input())    f=[0]*9    i=0    j=8    while i<=j:        m=(i+j)//2        f[m]=1        if a[m]>key:            j=m-1        else:            i=m+1    print(f)    输入待查找数据，执行该程序段后，下列选项中，列表f的值不可能的是（     ） A．[0, 0, 0, 0, 1, 1, 1, 0, 0] B．[1, 1, 0, 0, 1, 0, 0, 0, 0] C．[0, 1, 0, 0, 1, 0, 1, 0, 0] D．[0, 0, 0, 0, 1, 0, 1, 1, 0] 7．在冒泡排序算法中，最好情况（即数组已经是有序的）下需要进行（   ）轮比较。 A．n B．n-1 C．n(n-1)/2 D．0 8．下面关于递归说法正确的是（    ） A．函数间接调用自己不是递归 B．递归函数的嵌套调用次数没有限制 C．递归函数的执行效率优于非递归函数 D．递归出口和递归关系是递归函数编写的关键 9．数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据二分查找思想:设计一个在数组a中查找数据key的程序。实现该功能的Python程序段如下: i=1 j=len(a)-1 key=int(input(′请输入key:′)) while i<=j:     m=(i+j)∥2     if a[m]==key:      　break     if :      　j = m - 1     elif :      　i=m+1     else:      　if :     　　j=m-1      　else:     　　i=m+1 if i>j: 　s="没有找到!" else: 　s="位置:"+str(m) print(s) 上述程序中方框处可选语句为：     ①key%2==0 and a[m]%2==1     ②key%2==1 and a[m]%2==0     ③key<a[m] 则程序加框处①、②、③处语句依次是（   ） A．①、②、③ B．①、③、② C．②、①、③ D．③、②、① 10．19世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。玩家要将最左边杆上的盘子全部移到最右边的杆子上，要求一次只能移动一个盘，且不允许大盘放在小盘的上面。如果最左边杆子上只有3个盘子，则最少需要移动（    ）步才能将所有的盘子移至最右边杆。（   ） A．15 B．31 C．7 D．8 11．定义如下函数： def  f(s,r): if  s-r**2<0 or r==0 return  r+1 else: return  f(s-r**2,r-1) 执行语句k=f(50,5)后，k的值为（   ） A．4 B．3 C．2 D．1 12．下列适合用来解决裴波那契数列的方法的是（   ） A．枚举法 B．直接法 C．迭代法 D．以上均不是 13．有如下VB程序段： a(1)=7:a(2)=3:a(3)=5:a(4)=2:a(5)=9:a(6)=6 p=2*Int(Rnd*3)+1 For i= p To 5 k=i For j=i+1 To 6 If a(j) < a(k) Then k=j Next j If k <>i Then temp=a(i):a(i)=a(k):a(k)=temp End If Next i 执行该程序段后，a（1）～a（6）各元素的值不可能是（   ） A．7，3，5，2，6，9 B．7，3，2，5，6，9 C．7，2，3，5，6，9 D．2，3，5，6，7，9 14．定义如下函数： def fnl (n, num1, num2):     if n==1:         return num1     return fn1 (n-1, num2, num1 +num2) def fn2(n):     if n==1or n==2:         return 1     return fn2(n-1)+fn2(n-2) 下列说法正确的是（   ） A．两种算法的时间复杂度相同 B．fn1(n,1,1)与fn2(n)的功能相同 C．执行语句fn2(8)时，fn2(5)被调用了2次 D．fn1函数的调用次数取决于num1和num2的值 15．如下Python程序段 x = -2.5 if x > 0 : print (1) elif x == 0 : print (0) else: print( -1) 运行后的结果是（    ） A．-2.5 B．0 C．1 D．-1 16．数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”，文本框Text1中输入的值是33，执行该程序段，下列描述正确的是（    ） key = Val(Text1.Text) i = 0: j = 9: s = 0 Do While i <= j m = Fix((i + j) \ 2 + 0.5) s = s + 1 If key = a(m) Then Label1.Caption = Label1.Caption + "→" + Str(m) Exit Do                    'Exit Do表示退出循环 End If If key < a(m) Then j = m - 1 Else i = m + 1 Label1.Caption = Label1.Caption + "→" + Str(m) Loop Label2.Caption = "历经" + CStr(s) + "步" A．标签Label1显示内容为“→4→7→5” B．标签Label2显示内容为“历经1步” C．该程序为顺序查找，查找次数为3 D．该程序为对分查找，查找次数为4 17．采用冒泡排序算法对数据序列“8，3，5，2，0，9”进行排序，第一轮排序后的结果为“0，8，3，5，2，9”，则整个序列完成排序的交换次数是（  ） A．6次 B．7次 C．8次 D．9次 18．列表s包含8个互不相等的元素，即s[0]，s[1]，s[2]，……，s[7]，有如下Python程序段： n=8 for i in range（l，n-l）： for j in range（l，n-i-l）： if s[j]>s[j-l] s[j]，s[j-1]=s[j-1]，s[j] 该程序段实现的是（   ） A．s[0]到s[5]的降序排列 B．s[1]到s[6]的降序排列 C．s[1]到s[7]的升序排列 D．s[2]到s[6]的升序排列 19．定义如下函数： def f(n):     if n<=1:         return 1     elif n==2:         return 2     return f(n-1)+f(n-2)+f(n-3) 执行语句 v=f(5)，变量v的值是（   ） A．13 B．17 C．24 D．31 20．有如下Python程序： a=[0,20,23,23,24,24,31,48,49,73,75] key=int (input ()) c=0；i，j=1，10 while i<=j：    m=(i+j)//2    if a[m]<=key：       i=m+1    else：       j=m-1    c+=1 print (c) 若程序运行后，输出的结果是3，则输入的key可能是（    ） A．20或73 B．24或49 C．23或24 D．23或49 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查对分查找相关内容。枚举算法通过列举问题所有可能的解，并逐一检查每个解是否满足问题的条件。递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。对分查找的前提是被查找的数据是有序的（升序或降序）。选择排序法是一种不稳定的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据 进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前 半部分还是后半部分；在新确定的缩少范围内，继续按上述方法进行查找，直到找到要查找的数据，即查 找成功，如果要查找的数据不存在，即查找不成功。冒泡排序基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序。若要查找一本已知序号的书，则能快速地查找到的算法是对分查找。故本题答案是C选项。 2．B 【详解】本题考查数据结构。数据结构设计的根本目的是为了更好地表达数据间的逻辑关系，从而提高数据处理和算法执行的效率。故选择B。 3．D 【详解】本题主要考查迭代与递归算法。迭代是重复反馈的活动，其目的通常是逼近所需目标或结果；递归是重复调用函数自身；迭代程序可以转换成等价的递归程序；迭代和递归不是同一种算法的两种不同的表述，故本题选D选项。 4．C 【详解】本题主要考查二分查找及Python程序实现。输入的内容可分为四种情况，(-∞,2],[3,5],[6,9][10,∞)，故可能产生四种不同的 s 的值['LLL', 'LRL', 'RRL', 'RRRR']，则输出的结果不可能出现的是RLR，故本题选C选项。 5．B 【详解】本题主要考查二分查找及Python程序实现。flag1=1，flag2=1000，二分查找的中间位置mid=(flag1+flag2)//2，故①处填(flag1+flag2)//2， mid>x，说明要查找的x在mid的左边，需要更新flag2=mid-1，否则更新flag1=mid+1，故②处填mid-1，③处填mid+1，故本题选B选项。 6．C 【详解】本题主要考查对分查找算法。变量m是依次查找的下标索引值，第一次循环，m=4，f[4]=1，根据二叉树查找规则，往后查找只会在m=4的左边或右边进行查找，不会出现选项C中f[1]和f[6]同时为1的情况，故本题选C选项。 7．B 【详解】本题考查冒泡排序。在冒泡排序算法中，如果数组已经是有序的，理论上外层循环会执行n-1轮，但实际的冒泡排序实现中，可以设置一个标志位来检测是否进行了交换，如果没有交换发生，说明数组已经是有序的，可以提前结束排序，因此实际最好情况下可能少于n-1轮比较，但题目选项中没有这一选项，因此按照传统的冒泡排序逻辑，答案是n-1。故答案为：B。 8．D 【详解】本题考查递归。A选项错误。函数间接调用自己仍然是递归，只是通过其他函数进行了间接调用而已。B选项错误。在实际情况下，递归函数的嵌套调用次数是有限制的，受限于计算机的内存和栈空间。C选项错误，通常情况下，递归函数的执行效率较低，因为它需要频繁地压栈和出栈操作，相比之下，非递归函数可能会更高效。D选项正确。递归函数的正确性取决于递归出口（递归终止条件）和递归关系（递归调用），它们是递归函数编写的关键。故答案为：D。 9．C 【详解】本题考查二分查找算法相关内容。本题是二分查找算法的一种变式，查找的数据有两类（偶数和奇数），则在查找过程中需分三种情况来讨论分析：（1）如果要查找的数据（key）是奇数并且当前被访问的数为偶数时，则要查找的数据必定在前半段中，因为后半段肯定都是偶数，即j=m-1，故①处代码为：key%2==1 and a[m]%2==0。（2）如果要查找的数据（key）是偶数并且当前被访问的数为奇数时，则要查找的数据必定在后半段中，因为前半段肯定都是奇数，即i=m+1，故②处代码为：key%2==0 and a[m]%2==1。（3）除上面两种情况外的其他情况，要查找的数据是偶数（或奇数），当前被访问的数据也是偶数（或奇数）时，即if key<a[m]，则j=m-1，否则i=m+1，即③处代码为：key<a[m]。故本题答案为C选项。 10．C 【详解】本题主要考查递归算法。已知最左边有三个盘子，所以先想办法移动前两个，第一个放在最右边，第二个放中间，然后将第一个移动到中间，然后将最左边的最大的移动到最右边，然后将中间的最小的移动至最左边，将中间部分的中间那个移动至最右端，然后将最小的移动到最右端，完成，共进行了7次移动，故本题选C选项。 11．B 【详解】本题考查递归函数。这个函数的递归终止条件是 s - r**2 < 0 或 r == 0。 现在，执行语句 k = f(50, 5)。我们将按照函数的定义逐步展开： 第一次调用：f(50, 5)，此时不满足终止条件，进入else分支，执行 f(50 - 5**2, 5 - 1)。 第二次调用：f(25, 4)，此时同样不满足终止条件，进入else分支，执行 f(25 - 4**2, 4 - 1)。 第三次调用：f(9, 3)，仍不满足终止条件，再次进入else分支，执行 f(9 - 3**2, 3 - 1)。 第四次调用：f(0, 2)，此时满足终止条件，返回 2 + 1，即 3。故答案为：B。 12．C 【详解】本题考查迭代法。迭代法是一种通过重复应用某个固定的程序来逼近所需解的方法。在裴波那契数列中，可以使用循环来计算每个数字，直到得到所需的结果。故答案为：C。 13．C 【详解】本题考查VB程序段。根据代码p=2*Int（Rnd*3）+1，可知p的取值是1，3，5。双重For循环是选择排序，并且是一个升序排序，若p=1，For i=1 To 5，实现全部排序，排序后a（1）至a（6）各元素的值是2，3，5，6，7，9。若p=3，For i=3 To 5，a（3）至a（6）实现升序排序，排序后a（1）至a（6）各元素的值是7，3，2，5，6，9。若p=5，则For i=5 To 5，a（1）至a（6）各元素的值和初始值一样。故本题a（1）至a（6）各元素的值不可能是选项C的数值，本题选C。 14．B 【详解】本题考查函数。A选项错误，fn1是线性时间复杂度，fn2是指数时间复杂度。B选项正确，两者都计算斐波那契数列的第n项。C选项错误，fn2(5)会被调用多于2次。D选项错误，fn1函数的调用次数只取决于参数n的值，与num1和num2无关。故答案为：B。 15．D 【详解】本题考查的是Python多分支结构。x=-2.5，不满足x > 0，也不满足x = 0，故最后输出为-1。选项D正确。 16．A 【详解】本题主要考查对分查找算法知识点。key=33，i=0，j=9，第一遍循环，m = Fix((0 + 9) \ 2 + 0.5)=4，s=s+1=1，key>a(4)=30,i=m+1=5，Label1.Caption ="→4"，第二遍循环，m = Fix((5 + 9) \ 2 + 0.5)=7，s=s+1=2，key<a(7)=52，j=m-1=6，Label1.Caption ="→4→7"，第三遍循环，m = Fix((5 + 6) \ 2 + 0.5)=5，s=s+1=3，key=a(5)=33，Label1.Caption ="→4→7→5"，循环结束，故标签Label1显示内容为“→4→7→5”，该程序是对分查找，查找次数是3，故本题选A选项。 17．D 【详解】本题考查的是冒泡排序。冒泡排序如1，2，3，4最好的情况是按完全升级排列，最坏就是数字完全按降序排列： 第一次是1：然后1和2，3，4； 第2次是2：比较谁比它小交换，于是2和34交换，答案是3421； 第3次为3：3和4; 最后是4321； 这就是最坏情况下的次数3+2+1=6=4*3/2; 其实对于n个数的话，你要求降低排列，但是偏偏都是升序的数字；最坏的情况就是如此：次数为：n-1+n-2......+1=n*(n-1)/2。 本题的6个数据，835209， 第一次：083529，交换次数为4次， 第二次：028359，交换次数为3次， 第三次，023859，交换次数为1次， 第四次，023589，交换次数为1次， 总次数为4+3+1+1=9次。故答案为D。 18．A 【详解】本题考查的是Python冒泡排序变式。结合外循环可知只对s[0]到s[5]进行排序，由选择语句s[j]>s[j-l]，可知是降序排列，故选项A正确。 19．A 【详解】本题考查Python递归函数相关内容。f(5)=f(4)+f(3)+f(2)=f(3)+f(2)+f(1)+f(3)+2=2*f(3)+2+1+2=2*f(3)+5=2*(f(2)+f(1)+f(0))+5=2*(2+1+1)+5=2*4+5=13。选A。 20．B 【详解】本题主要考查二分查找及Python程序实现。该二分查找用二叉树表示如下，变量c表示查找的深度，由图可知，73和23有右子树，还会继续往下查找，因此c不可能为3，排除A、C、D选项，key值为20、24、49时，c值均为3，故本题选B选项。    答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$