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

第五章 数据结构的应用 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是： A．2 B．3 C．4 D．7 2．有10个数据34，22，101，8，14，88，24，17，54，7依次存放在数组a(1 to 10)中，下列关于数据查找的说法中，正确的是（   ） A．数据19不在数组a(1 to 10)中，不能进行查找 B．可以直接对数组a(1 to 10)采用对分查找 C．最多经过10次比较，肯定能得出查找结论 D．顺序查找肯定比对分查找效率低 3．采用冒泡排序算法对数据序列“4，9，8，2，6，3”完成升序排序，则需要交换的次数为（  ） A．9 B．10 C．11 D．12 4．什么是数据的物理结构（     ） A．数据元素之间的逻辑关系 B．数据在计算机中的实际存储方式 C．数据的抽象表示 D．数据的操作算法 5．现有8位同学的身高数据如列表[155、165、168、172、175、178、180、185]，若用对分查找算法查找数值155，则依次被访问到的数据是（   ） A．155 B．168、155 C．172、165、155 D．175、165、155 6．已知单调函数f(x)在[0，1]区间存在一个x0，使f(x0)＝0。现用对分查找法搜索x0的值，开始搜索区间为[0，1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为( ) A．1/2 B．1/10 C．1/102 D．1/210 7．递归也可用“分”“治”“合”三个字概括。下列说法错误的是（  ） A．分:将原问题分解成k个子问题 B．治:对这k个子问题分别求解，如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解 C．合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解 D．整个递归不需要终止条件，自动返回运算结果 8．列表d中存入了一列数据如表所示，采用对分查找数据7，第一次查找的列表元素是d[5]，以下叙述正确的是（    ） d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] 2 3 5 7 11 13 17 19 23 29 A．如果列表d中存入的数据是递减次序排序，则无法实施对分查找 B．列表d只能使用对分查找，不能使用顺序查找 C．查找过程中，共需要比较三次 D．第二次的查找范围是d[1]至d[4] 9．某超市商品信息管理系统中有1万条商品资料记录(已经索引排序)，假设从中取出一条记录并与待查项进行比较所花的时间为20毫秒，则用对分法在该系统中查找任意一个指定商品最多花费的时间约为(  ) A．13毫秒 B．14毫秒 C．280毫秒 D．14万毫秒 10．对5个字母“C、Y、E、A、J”进行两遍冒泡排序后即为某密码锁的密码，该密码可能是： A．ACEYJ B．ACYEJ C．CYEAJ D．ACEJY 11．有如下Python程序段： def sm（a）：   if len（a）==1：      return a[0]    else:        return a[0]+sm（a[1:]） a=[7，8，9，1，5，6] print（sm（a）） 程序运行后，函数sm被调用的次数是（   ） A．5 B．6 C．7 D．12 12．数组a共有9个整数元素，依次为“8，7，3，1，9，5，6，3，1”，则执行下列程序后Label1中显示的是（    ） i = 1: j = 9:s=" ":flag=True Key = 3 Do While i <= j And flag m = (i + j) \ 2 s = s + Str(m) If a(m) = Key Then flag = False Exit Do                         'Exit Do表示退出循环 ElseIf Key > a(m) Then i = m + 1 Else j = m - 1 End If Loop If flag then s="没有找到" Label1.Caption = s A．没有找到 B．3 C．9 D．5 2 1 13．下列Python程序段的功能是对数组a中的元素进行升序排序: #输入10个数据，并存储在数组a中，代码省略 n=len(a) for i in range(　　　①　　　):     for j in range(　　　②　　　):     if a[j]>a[j-1]:     a[j]，a[j-1]=a[j-1]，a[j] 程序中划线①②处应填写的正确语句是（   ） A．①0 n-1　②n-1，i+1，-1 B．①0 n-1　②n-1，i C．①1，n　②n-1，i-1 D．①1，n　②n-1，i-1，-1 14．有如下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 15．将6名选手的歌唱比赛成绩存放在数组a中，如下表所示： 若按升序排列，采用冒泡排序算法自右向左进行比较和交换，那么完成前二轮的数据处理，比较的总次数为 A．10 B．4 C．9 D．5 16．在数据查找中，顺序查找的时间复杂度在最坏情况下是（   ） A．O(1) B．O(logn) C．O(n) D．O(n^2) 17．有如下VB程序段： 生成6个随机正整数，依次存入数组元素a（1）到a（6），代码略 For i = 1 To 5 k = i For j = 5 To i + 1 Step -1 If a（k） Mod 2 <= a（j） Mod 2 Then k = j Next j If k <> i Then t = a（k）: a（k）= a（i）: a（i）= t Next i 执行该程序段后，a（1）到a（6）各元素值可能的是（    ） A．3， 7， 4， 4， 5， 8 B．2， 4， 6， 8， 10， 12 C．1， 3， 7， 2， 6， 3 D．1， 3， 5， 2， 4， 6 18．采用冒泡排序算法对数据序列“8，7，2，3，9，6，5”完成升序排序，排序2趟后，正确的顺序是（   ） A．2，3，8，7，5，6，9 B．2，3，8，7，9，6，5 C．2，3，5，6，7，8，9 D．2，3，7，5，6，8，9 19．有如下两段python程序 若数组a的元素为[34，33，25，46，17，77]，则下列说法不正确的是（   ） A．两段程序的比较次数一样 B．两段程序的交换次数一样 C．两段程序的输出结果一样 D．两段程序都能实现数组a降序排序 20．采用二分查找方法，在1-100中查找53需要比较（   ）次。 left=l right = 100 cnt=0 while left<=right: mid=(left+right)//2 cnt +=i if mid==53: Break elif mid<53: left = mid+1 else: right = mid-1 print("采用二分查找方法,在1-100中查找53需要比较()次".format(cnt)) A．5 B．6 C．7 D．8 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题主要考查对分查找算法。令i=1，j=9，m=(i+j)/2=5，第五个值12>10，j=m-1=4；第二次查找，m=(i+j)/2=2，第二个值6<10，i=m+1=3；第三次查找，m=(i+j)/2=3，第三个值7<10，i=m+1=4；第四次查找，m=(i+j)/2=4，第四个数是10，故需要查找的次数是4次，故本题选C选项。 2．C 【详解】本题考查查找算法相关知识。数据19虽然不在数组a（1 to 10）中，仍旧可对其进行查找，只是查找结果是找不到，选项A错误；数组a是无序数组，无法采用对分查找，对分查找是数组必须是有序排列的，选项B错误；最多经过10次比较，肯定能得出查找结论，选项C正确；若查找元素是第一个，则顺序查找比对分查找效率高，选项D错误。故本题正确的是选项C的说法。 3．B 【详解】本题主要考查冒泡排序算法。第一遍排序，9和8、9和2、9和6、9和3需要交换，排序后数据序列分别是4、8、2、6、3、9；第二遍循环，8和2、8和6、8和3需要交换，排序后数据序列分别是4、2、6、3、8、9；第三遍循环，2和4、6和3需要交换，排序后数据序列分别是2、4、3、6、8、9；第四遍循环，3和4需要交换，排序后数据序列分别是2、3、4、6、8、9，数据已有序，故需要交换的次数为4+3+2+1=10次，故本题选B选项。 4．B 【详解】本题考查数据结构。数据的物理结构涉及数据在内存或磁盘上的实际存储布局。故选择B。 5．C 【详解】本题考查对分查找。 索引从0开始到7，存放8个同学的升高数据到列表，故对分查找的第一个数的索引为int(7/2)，列表中索引为3的数据为172。故正确答案为：选项C。 6．D 【详解】本题主要考查对分查找算法。第1次搜索区间的长度为1，第2次搜索区间的长度为1/2，第3次搜索区间的长度为1/22，……，第11次搜索区间的长度为1/210，故本题选D选项。 7．D 【详解】本题主要考查递归算法。递归也可用分、治、合三个字概括，分:将原问题分解成k个子问题；治:对这k个子问题分别求解，如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解；合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解，整个递归需要终止条件，故本题选D选项。 8．D 【详解】本题考查二分查找。 采用对分查找数据7，第一次查找的列表元素是d[5]，由于按照升序排序，判断d[5]的值为11，大于7，故第二次比较的数据范围向低下标区域移动。故第二次的查找范围是d[1]至d[4]。选项A，对分查找的数据，要求数据有序，不要求是降序还是升序。选项B，对于该列表d，可以使用顺序查找，没有其它条件限制。选项C，查找过程中，共需要比较二次，可以找到。故正确答案为：选项D。 9．C 【详解】本题主要考查对分查找算法。对具有n个元素的有序数组进行二分法查找，最多需要比较log2(n)+1次。对1万条商品资料记录进行对分查找，最多需要log2(10000)+1=14次，从中取出一条记录并与待查项进行比较所花的时间为20毫秒，则最多花费的时间约为14*20=280毫秒，故本题选C选项。 10．A 【详解】本题主要考查冒泡排序算法。观察选项可知，应为冒泡升序排序，从左边，第一遍排序后是C、E、A、J、Y，第二遍排序后是C、A、E、J、Y；从右边，第一遍排序后是A、C、Y、E、J，第二遍排序后是A、C、E、Y、J，故该密码可能是ACEYJ，故本题选A选项。 11．B 【详解】本题考查的是迭代。阅读程序可知，a=[7，8，9，1，5，6]调用函数sm一次，[8，9，1，5，6]又调用函数sm一次，直到列表只有一个元素[6]最后调用函数sm一次。故一共调用了6次。选项B正确。 12．A 【详解】本题主要考查VB程序的执行。i=1，j=9，flag=True，Key=3，第一遍循环，m=(1+9)\2=5，s=“5”，key<a(5)，j=m-1=4；第二遍循环，m=(1+4)\2=2，s=“52”，key<a(2)，j=m-1=3；第三遍循环，m=(1+3)\2=2，s=“522”，key<a(2)，j=m-1=2；第四遍循环，m=(1+2)\2=1，s=“521”，key<a(1)，j=m-1=1；第五遍循环，m=(1+1)\2=1，s=“5211”，key<a(1)，j=m-1=0，退出循环，flag=True，执行s="没有找到"，故Label1中显示的是没有找到，故本题选A选项。 13．D 【详解】本题主要考查的是冒泡排序。根据代码“if a[j]>a[j-1]:”可知，排序时数据是从后往前进行比较和交换的，变量i表示排序的次数，n个数据排序共需进行n-1遍，变量j表示当前数组元素的下标，因此方法一为:①处代码为0，n-1，②处代码为n-1，i，-1；方法二为：①处代码为1，n，②处代码为n-1，i-1，-1，因此答案为D。 14．D 【详解】本题主要考查排序算法及Python程序实现。该程序实现将数组a降序排序；元素14在程序运行过程中被交换3次；该程序的时间复杂度为0(n2)；当i=3时，a已有序，因此程序结束后，i的值为3，故本题选D选项。 15．C 【详解】本题主要考查冒泡排序算法。第一轮需要比较5次，最终90会被放到最右边，下一轮不参与比较，第二轮其余5个数会参与比较，比较4次，故完成前二轮的数据处理，比较的总次数为5+4=9，故本题选C选项。 16．C 【详解】本题考查数据查找。顺序查找的时间复杂度在最坏的情况下是O(n)，即需要查找的元素位于数组的末尾或根本不在数组中，这时需要遍历整个数组。故答案为：C。 17．B 【详解】本题考查排序算法相关知识。从双重For循环可知，此处是选择排序，选择排序将所选出的数值放入指定的位置。根据内循环中If a（k）Mod 2 <= a（j）Mod 2 Then k=j，可知选出除以2余数最小的数字，除以2的余数是0或者1，若数组中有偶数，则排序后排在最前面的一定是偶数。选项ACD，数组中都有偶数，但没有排在前面，故错误，选项B数组全都是偶数，则该排序可能，故本题选B。 18．A 【详解】本题主要考查冒泡排序算法。冒泡排序，它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来，走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。排序第1趟后，顺序为2，8，7，3，5，9，6，排序第2趟后，顺序为2，3，8，7，5，6，9，故本题选A选项。 19．C 【详解】本题主要考查Python程序的执行与调试。分析程序可知，两个程序分别从前往后比较和从后往前比较，因此比较次数和交换次数相等，两段程序都能实现数组a降序排序，但第一个程序内层循环每次会将最小值放到最右边，第二个程序内层循环每次循环会将右边的最大值放到左边，因此最终的输出结果不相等。第一个程序的输出结果是“34,46,77,33,25,”；第二个程序输出结果是“77,46,34,33,25,”，故本题选C选项。 20．A 【详解】本题主要考查二分查找算法及Python程序实现。第一次比较，mid=(1+100)//2=50，left=mid+1=51；第二次比较，mid=(51+100)//2=75，right=mid-1=74；第三次比较，mid=(51+74)//2=62，right=mid-1=61；第四次比较，mid=(51+61)//2=56，right=mid-1=55；第五次比较，mid=(51+56)//2=53，循环结束，故查找53需要比较5次，故本题选A选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$