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

第五章 数据结构的应用 一、选择题 1．有一组升序排列的数：3、6、7、10、12、17、26、31、79，如果用对分法查找数据10，则依次访问的数据为（    ） A．12、6、7、10 B．12、7、10 C．12、6、10 D．12、7、6、10 2．数据结构设计中，如何体现数据之间的逻辑关系（     ） A．通过数据元素的物理地址 B．通过数据存储的格式 C．通过数据元素的组织方式 D．通过算法的复杂度 3．定义如下函数： 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的值 4．下列函数实现的功能是（    ） def mi（x，n）： if n==0：    return 1 else：    return x*mi（x，n-1） A．计算x的n次方 B．计算n的x次方 C．计算x！*n D．计算x*n！ 5．分别采用选择和冒泡排序算法对数据序列“2，3，4，5，1，0”完成升序排序，则需要交换的次数分别为（   ） A．5次和9次 B．4次和12次 C．5次和15次 D．4次和18次 6．数组a为一组已按降序排序的正整数，依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下： Dim a(1 To 6) As Integer Const n = 6 a(1) = 98: a(2) = 96: a(3) = 95 a(4) = 90: a(5) = 87: a(6) = 81 i = 1: j = n Key = Val(Text1.Text) f = False Do While And f = False    m = (i + j) \ 2     If a(m) = Key Then         Text1.Text = “已找到”: f = True     ElseIf a(m) > Key Then     Else             End If Loop 上述程序中方框(1)(2)(3)处语句依次为（   ） A．i <= j      i = m + 1   j = m - 1 B．i <= j      j = m - 1   i = m + 1 C．i < j      j = m - 1   i = m + 1 D．i < j      i = m + 1   j = m - 1 7．【加试题】采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”， i = 1: j = 7: x = 55 Do While i <= j      m = (i + j) \ 2      If a(m) = x Then Exit Do      If a(m) > x Then j = m - 1 Else i = m + 1 Loop 经过上述代码查找后，下列表达式正确的是 A．i=m+1 B．i=m-1 C．j>m+1 D．j<m-1 8．运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（    ） A．问题性质相同，问题规模相同 B．问题性质不同，问题规模相同 C．问题性质相同，问题规模不同 D．问题性质不同，问题规模不同 9．在数据查找中，顺序查找的时间复杂度在最坏情况下是（   ） A．O(1) B．O(logn) C．O(n) D．O(n^2) 10．有如下Python程序段： a=[34,35,38,41,41,41,45,45,69,78] i=0;j=9;key=41;n=0 while i<=j:     m=(i+j)//2     if key < a[m]:         j=m-1     else:         i=m+1 该程序段运行结束后，下列说法正确的是（   ） A．i的值是3 B．j的值是3 C．i的值是6 D．j 的值是6 11．下列程序代码采用的算法是（    ） def mi（x，n）：     if n==0：          return 1     else：          return x*mi（x，n-1） A．迭代法 B．枚举法 C．递归法 D．解析法 12．【加试题】入围“十佳歌手”的10位学生的编号依次为：47，36，35，31，28，23，17，8，3，1，主持人通过对分查找最终确定35号为首位出场学生，则主持人查找过程中依次被访问的编号是（   ） A．47，36，35 B．23，35 C．28，35 D．28，36，35 13．迭代法也称（ ），是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的（ ）称为一次“迭代”，而每一次迭代得到的（ ）会被用来作为下一次迭代的（ ）。（  ） A．辗转法；重复；结果；初始值 B．重复；结果；辗转法；初始值 C．辗转法；结果；重复；初始值 D．结果；初始值；辗转法；重复 14．递归也可用“分”“治”“合”三个字概括。下列说法错误的是（  ） A．分:将原问题分解成k个子问题 B．治:对这k个子问题分别求解，如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解 C．合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解 D．整个递归不需要终止条件，自动返回运算结果 15．斐波那契数列：1，1，2，3，5，8，13，……，现用递归算法求解第 n 项，代码如下， def fib(n): if (n > 2): return fib(n - 1) + fib(n - 2)    return 1 n = int(input('输入一个整数')) print(fib(n)) 程序执行时，输入一个整数5，则函数 fib 被第 3 次调用时的返回值为（   ） A．2 B．3 C．5 D．8 16．有如下自定义函数： 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．该程序采用了递归算法 17．有如下Python程序： def hill(n):     if n==1 or n==2:         return 1     elif n==3:         return 2     else:         return hill(n-1)+hill(n-3) x=int(input()) print(hill(x)) 执行该程序，若输入的值为6，输出的结果是（ ） A．5 B．6 C．7 D．8 18．运行以下Python程序段，结果是（   ） A．Python B．C++ C．Welcome D．True 19．数组A 中存放了某校学生的身高数据（单位：厘米），数据存放情况如下表： 若要查找数组中是否存在数据182，以下表述正确的是（    ） A．本组数据既能采用对分查找算法，也能采用顺序查找算法 B．本组数据采用对分查找需比较4次，而顺序查找只需2 次，所以对分查找效率高的说法不对 C．本组数据须先对数据进行升序排序后才能进行对分查找 D．本组数据由于存在相同数据176，所以不能采用对分查找算法 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题主要考查对分查找算法。一共9个数，（1+9）/2=5，第一次查找的数是12，10<12，（1+4）/2=2，第二次查找的数是6，6<10，（3+4）/2=3，第三次查找的数是7，7<10，（4+4）/2=4，第四次查找的数是10，故依次访问的数据为12、6、7、10，故本题选A选项。 2．C 【详解】本题考查数据结构。数据结构通过元素间的组织方式来体现逻辑关系，如线性、树形或图状结构等。故选择C。 3．B 【详解】本题考查函数。A选项错误，fn1是线性时间复杂度，fn2是指数时间复杂度。B选项正确，两者都计算斐波那契数列的第n项。C选项错误，fn2(5)会被调用多于2次。D选项错误，fn1函数的调用次数只取决于参数n的值，与num1和num2无关。故答案为：B。 4．A 【详解】本题主要考查递归算法及Python程序实现。分析程序，参数是x和n，当n=0时，返回1，否则返回x*mi(x,n-1)。而函数mi(x,n-1)当n-1不等于0时，返回x*mi(x,n-2)，依次类推，即函数实现的功能是计算x的n次方，故本题选A选项。 5．A 【详解】本题主要考查冒泡和选择排序算法。冒泡排序（Bubble Sort）将一个列表中的两个元素进行比较，并将最小的元素交换到顶部。两个元素中较小的会冒到顶部，而较大的会沉到底部，该过程将被重复执行，直到所有元素都被排序。选择排序（Select Sort） 是直观的排序，通过确定一个 Key 最大或最小值，再从待排序的的数中找出最大或最小的交换到对应位置，再选择次之。选择排序需要交换5次，第一次是5和0交换，变为2、3、4、0、1、5；第二次是4和1交换，变为2、3、1、0、4、5；第三次是3和0交换，变为2、0、1、3、4、5；第四次是2和1交换，变为1、0、2、3、4、5；第五次是1和0交换，变为0、1、2、3、4、5。冒泡排序需要9次交换，第一次是5分别和1、0交换，共2次，变为2、3、4、1、0、5；第二、三、四次是2、3、4分别和1、0交换，共6次，变为1、0、2、3、4、5；第五次是1和0交换，变为0、1、2、3、4、5，一共2+6+1=9次，故本题选A选项。 6．A 【详解】本题主要考查对分查找程序实现。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到i>j时，查找结束，获得最终结果。另题中数组为降序排列，则当a(m) > Key 时，调整i 为m+1，否则调整j为m-1，因此A选项正确。 【点睛】 7．A 【详解】本题主要考查对分查找算法。i = 1， j = 7， x = 55，第一次循环，m=(1+7)/2=4，a(4)=66>x，j=m-1=3；第二次循环，m=(1+3)/2=2，a(2)=38<x，i=m+1=3；第三次循环，m=(3+3)/2=3，a(3)=51<x，i=m+1=4，程序结束，故经过上述代码查找后，表达式i=m+1正确，故本题选A选项。 8．C 【详解】本题主要考查分治算法。分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题的性质相同，规模不同，故本题选C选项。 9．C 【详解】本题考查数据查找。顺序查找的时间复杂度在最坏的情况下是O(n)，即需要查找的元素位于数组的末尾或根本不在数组中，这时需要遍历整个数组。故答案为：C。 10．C 【详解】本题考查二分查找（折半查找）及python程序设计相关内容。初始状态，i=0；j=9；key=41；（1）此时满足循环条件i<=j，第一次进入循环，m=(i+j)//2，求得m=4，key< a[m]不成立，执行i=m+1，即i=5。（2）此时i=5，j值未变，仍然为9，满足循环条件i<=j，第二次进入循环，m=(i+j)//2，求得m=7，key< a[m]成立，执行 j=m-1，即j=6。（3）此时i=5，j=6，满足循环条件i<=j，第三次进入循环，m=(i+j)//2，求得m=5，key< a[m]成立，执行 i=m+1，即i=6。（4）此时i=6，j=6，满足循环条件i<=j，第四次进入循环，m=(i+j)//2，求得m=6，key< a[m]成立，执行 j=m-1，即j=5。（5）此时i=6，j=5，不满足循环条件i<=j，结束循环。结束循环后，i=6，j=5。故本题答案是C选项。 11．C 【详解】本题考查的是算法相关知识。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题；枚举法将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃；能采用递归描述的算法通常有这样的特征:为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解；解析法又称为分析法，它是应用数学推导、演绎去求解数学模型的方法。分析本题代码可知采用的算法是递归法，故本题应选C。 12．D 【详解】本题主要考查对分查找算法。设i=1，j=10，第一次循环，m=（1+10）\2=5，a(5)=28<35，j=m-1=4；第二次循环，m=（1+4）\2=2，a(2)=36>35，i=m+1=3；第三次循环，m=（3+4）\2=3，a(3)=35，循环结束。故主持人查找过程中依次被访问的编号是28，36，35，故本题选D选项。 13．A 【详解】本题主要考查迭代算法。迭代法也称辗转法，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值，故本题选A选项。 14．D 【详解】本题主要考查递归算法。递归也可用分、治、合三个字概括，分:将原问题分解成k个子问题；治:对这k个子问题分别求解，如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解；合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解，整个递归需要终止条件，故本题选D选项。 15．A 【详解】本题考查递归调用相关知识。第一次调用函数为fib(5)，fib(5)=fib(4)+fib(3)，fib(4)为第二次调用，fib(3)为第三次调用，fib(3)=fib(2)+fib(1)=1+1=2。故第三次调用返回值为2。故答案为：A。 16．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。 17．B 【详解】本题考查的是Python迭代。若输入的值为6，则hill(6)=hill(5)+hill(3)=hill(4)+hill(2)+hill(3)=hill(3)+hill(1)+hill(2)+hill(3)=2+1+1+2=6。故本题应选B。 18．B 【详解】本题考查的是Python选择语句。name的值为“C++”不为“Python”，故执行else分支的print语句，故输出C++，选项B正确。 19．A 【详解】本题主要考查对分查找知识点。本数组已经是降序排序，故本组数据既能采用对分查找算法，也能采用顺序查找算法，故本题选A选项；本次数据采用对分查找比较次数高，并不能否定对分查找的效率低，选项B说法错误；本组数据可以直接进行对分查找，选项C说法错误；本组数据存在相同数据176，可以采用对分查找算法，选项D说法错误。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$