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

第五章 数据结构的应用2024—2025学年高中信息技术粤教版（2019）选修1 一、选择题 1．关于对分查找和顺序查找算法的叙述，正确的是（   ） A．对分查找之前需要对数据进行排序，查找过程效率较低 B．顺序查找之前不需要对数据进行排序，查找过程效率较低 C．顺序查找之前需要对数据进行排序，查找过程效率较高 D．对分查找之前不需要对数据进行排序，查找过程效率较高 2．已知递归式为F（n）=F（n-1）+2，且F（1）=5，则当n=3时，F的值为（    ） A．7 B．9 C．11 D．13 3．二分查找的时间复杂度是O(logn)。以下哪种情况不适合使用二分查找？（   ） A．数组已排序 B．数组中数据量较大 C．数组中数据量较小 D．以上都不适合 4．在序列“7,14,18,21,23,29,31,35,38,42,46,49,52”中用二分查找法查找数字“42”，一共找了（    ）就找到了。（   ） A．2次 B．3次 C．4次 D．5次 5．有自定义函数如下： def p(a,b):     a=a+2     if a>=9:         return b     else:         return p(a,b+1)+p(a,b-1) print(p(4,4)) 程序运行后，输出的结果是（   ） A．16 B．18 C．29 D．32 6．有如下排序程序：    程序运行后，列表a中的内容是（　　） A．[20，19，18，15，12，10，10，10，9，3] B．[3，9，10，10，10，12，15，18，19，20] C．[19，20，15，18，10，12，10，9，10，3] D．[20，15，19，10，18，10，12，10，9，3] 7．定义如下函数: def chg(k): if k==-1: return "" else: c=chr(ord("a")+k) if k%2==1: return c+chg(k-l) else: return chg(k-1)+c 执行语句m=chg(4)后，m的值为（   ） A．"ecabd" B．"dbace" C．"abcde" D．"edcba" 8．下列对数据结构的描述正确的是（   ） A．逻辑结构相邻的两个数据元素，其存储位置也一定相邻 B．对于同一个问题，只能使用一种数据结构来设计算法并解决 C．选择的数据结构不同，算法的处理效率、程序的运行效率也不同 D．对同一操作（如插入、删除数据），不同的数据结构实现的方法相同 9．采用冒泡排序算法对数据序列“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 10．下列关于递归算法的说法中，正确的是（    ） A．在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D．对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））；”就是一种递归调用 11．猴子吃桃：猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了，问第一天共摘了多少个桃子？使用迭代法时首先确定迭代变量为桃子数n，并设置最后一天的桃子数1为初始值，则迭代关系式和迭代次数分别是（   ） A．n=n/2-1           9 B．n=(n+1)*2     9 C．n=n/2-110         10 D．n=(n+1)*2     10 12．在插入排序中，最坏的情况发生在什么情况下（   ） A．数组已经有序 B．数组逆序 C．数组随机 D．数组中有重复元素 13．有如下Python程序段： def double f(m):    if   m==1   or   m==2:       return    m    else:       return double f(m-2)*m n=int(input("请输入一个正整数n:") print(double f(n)) 执行该程序段后，输入n 的值为7，输出的结果是（   ） A．1 B．7 C．105 D．35 14．以下哪种语言对递归算法的支持较好？（   ） A．C B．Java C．Python D．所有以上 15．在线性查找中，如果数组中存在多个相同的目标元素，查找会返回第一个找到的元素吗？（   ） A．是 B．否 C．不确定 D．以上都不对 16．小明编写程序实现数据排序功能，部分程序如下： n=len（d） for i in range（1，n）：   for j in range（n-i-1，-1，-1）：      if d[j]>d[j+1]：         d[j]，d[j+1]=d[j+1]，d[j] print（d） 此程序存在问题，不适合作为测试数据的是（   ） A． d=[9，6，5，8] B．d=[9，8，6，5] C．d=[8，9，5，6] D．d=[6，5，9，8] 17．以下哪种排序算法适用于大数据量（   ） A．选择排序 B．快速排序 C．冒泡排序 D．鸡尾酒排序 18．某对分查找算法的VB程序段如下： i = 1 : j = 7 : S = "" : key = 3 Do While i<=j m =(i+j)\ 2 If key = a(m) Then S = S + "M" If key < a(m) Then j = m - 1 : S = S + "L" Else i = m + l : S = S + "R" End If Loop Text1.Text = S 数组元素a(1)到a(7)的值依次为1，2，3，3，3，5，8。该程序执行后，文本框Text1中显示的内容是（    ） A．MRLMR B．MLMR C．MLML D．LRLM 19．下列哪种查找算法的时间复杂度最高（   ） A．顺序查找 B．二分查找 C．插值查找 D．哈希表查找 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查查找算法相关内容。顺序查找是一种基本的查找算法，它按照数据元素的顺序从前往后依次查找目标元素。顺序查找的基本思路是将目标元素与当前位置的元素进行比较，若相等则查找成功；否则继续向后查找，直到找到目标元素或搜索到末尾位置为止。顺序查找适用于线性表的顺序存储结构和链式存储结构，对数据的存储和记录的有序性没有特殊要求。然而，顺序查找的缺点是当数据量较大时，平均查找长度会较大，导致查找效率较低。二分查找法（也称折半查找法）是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。对分查找之前需要对数据进行排序，查找过程效率较高；顺序查找之前不需要对数据进行排序，查找过程效率较低。故本题答案是B选项。 2．B 【详解】本题主要考查递归算法。F(n)=F(n-1)+2，F(1)=5。当n=3时，F(3)=F(2)+2=F(1)+2+2=5+2+2=9，故本题选B选项。 3．C 【详解】本题考查查找算法。当数组中数据量较小时，二分查找的优势不明显，此时使用线性查找可能更为简单高效。故选C。 4．A 【详解】本题考查二分查找法。二分查找法是一种将已排序的数组或列表中的元素进行查找的算法。它通过将待查找的区间不断缩小一半来快速定位目标元素。在这个序列中，首先确定整个区间的左右边界，即左边界为0，右边界为12（序列长度减1）。然后取中间位置的元素，即索引为6的元素31，与目标元素42进行比较。由于31小于42，因此目标元素一定在右半部分，于是将左边界更新为中间位置的下一个位置7，右边界不变。再次取中间位置的元素，即索引为9的元素42，由于该元素为42，因此找到了目标元素。因此，在这个序列中用二分查找法查找数字“42”，一共找了2次就找到了。选项A正确。 5．A 【详解】本题考查的是递归函数。p(6,5)=p(8,6)+p(8,4)=6+4=10；p(6,3)=p(8,4)+p(8,2)=4+2=6；p(4,4)=p(6,5)+p(6,3)=10+6=16。故选A。 6．C 【详解】本题主要考查排序算法及Python程序实现。阅读程序段可知，i的取值范围为[0,9]，当i=0时，j的取值范围为2,4,6,8。如果满足a[i]<a[j]，那么交换两个数的位置，所以最终实现的是偶数位上的降序排列，同理奇数位上也最终实现降序，所以列表a最终的排序为：[19，20，15，18，10，12，10，9，10，3]，故本题选C选项。 7．B 【详解】本题考查递归。执行m=chg(4)的过程如下：当k=4时，生成字母"e"，进入递归调用chg(k-1)。当k=3时，生成字母"d"，返回"d"+chg(k-1)。当k=2时，生成字母"c"，进入递归调用chg(k-1)。当k=1时，生成字母"b"，返回"b"+chg(k-1)。当k=0时，生成字母"a"，因为k为偶数，返回chg(k-1)+"a"。当k=-1时，递归结束，返回空字符串，即chg(k-1)=""。回到步骤4，拼接得到chg(k-1)+"a"，即"b"+"a"。回到步骤3，拼接得到"ba"+"c"。回到步骤2，拼接得到"d"+"bac"。回到步骤1，拼接得到"dbac"+"e"，即最终的m的值为"dbace"。故答案为：B。 8．C 【详解】本题考查数据结构。逻辑结构相邻的元素，其存储位置不一定相邻，如链表，A选项错误；同一个问题可以使用不同的数据结构来解决，不同的数据结构使用的算法也不同，B选项错误；对同一操作，不同的数据结构实现的算法也不同，D选项错误。故答案为：C。 9．A 【详解】本题主要考查冒泡排序算法。冒泡排序，它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来，走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。排序第1趟后，顺序为2，8，7，3，5，9，6，排序第2趟后，顺序为2，3，8，7，5，6，9，故本题选A选项。 10．A 【详解】本题主要考查递归算法的描述。在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间；和非递归算法相比，解决同一个问题，递归算法一般运行得更慢一些；对于较复杂的问题，用递归方式编程一般比非递归方式更容易一些；对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））；”不属于递归调用，故本题选A选项。 11．B 【详解】本题考查的是迭代算法相关知识。采用倒推方法，每天都吃前一天剩下的一半多一个，故迭代关系式为：n=(n+1)*2 ；从第9天倒推到第1天，共需要迭代9次。选项B正确。 12．B 【详解】本题考查插入排序。插入排序的基本思想是将未排序元素依次插入已排序部分的合适位置。在数组逆序的情况下，每个未排序元素都需要与已排序部分的所有元素进行比较和移动，操作次数最多。而数组已经有序时，插入排序效率很高，几乎不需要移动元素。数组随机和有重复元素的情况，其最坏情况的可能性都小于数组逆序。故答案为：B。 13．C 【详解】本题主要考查递归函数的应用。n=7，double_f(7)=double_f(5)*7=double_f(3)*5*7=double_f(1)*3*5*7=1*3*5*7=105，故本题选C选项。 14．D 【详解】本题考查递归。所有以上语言都对递归算法有较好的支持，因为它们都允许函数调用自身。故答案为：D。 15．A 【详解】本题考查的是线性查找。在线性查找中，如果数组中存在多个相同的目标元素，查找通常返回第一个找到的元素。故选A。 16．D 【详解】本题考查的是冒泡排序。 冒泡排序它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。由d[j]>d[j+1]可知，程序是想实现升序排序。选项D，d=[6，5，9，8]，依据程序，第一趟：9>8，对换位置；6>5，对换位置，新的数据顺序[5，6，8，9]已经是升序排序，不适合作为测试数据。故本题应选D。 17．B 【详解】本题考查排序。快速排序适用于大数据量，因为它的时间复杂度较低，且在平均情况下表现良好。故答案为：B。 18．A 【详解】本题主要考查对分查找算法的程序实现。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果或查找结束。题中a数组元素为1，2，3，3，3，5，8，查找键为3，则文本框Text1输出为MRLMR，因此A选项正确。 【点睛】 19．A 【详解】本题考查查找算法。顺序查找的时间复杂度为O(n)，是这几种查找算法中最高的。二分查找的时间复杂度为O(log n)，插值查找的时间复杂度在最坏情况下为O(n)，但在均匀分布的情况下接近O( log n)，哈希表查找的时间复杂度为O(1)（在理想情况下）。因此，顺序查找的时间复杂度最高。故选A。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$