第5章  数据结构与算法（单元检测卷）-高中信息技术选修1数据与数据结构 单元检测卷

第5章  数据结构与算法-综合与评价（分层作业） 【夯实基础】 1 . 定义如下函数： def f (x, n):        if n == 0:             return 1        return x * f (x, n - 1) 该函数的时间复杂度为（     ） A．0(1) B．0(log2n) C．0(n) D．0(xn) 2.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 （ ） A O(log2n) B O(n2) C O(nlog2n) D O(n) 3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 （ ） A (n+1)/2 B (n-1)/2 C n D n/2 4. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，需要多少次比较后才能查找成功（ ） A 4 B 1 C 2 D 8 5.从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为 （ ） A O(n) B O(1) C O(log2n) D O(n^2) 6. 在算法分析中，大O符号(O-notation)主要用来描述算法的：（ ） A. 最好情况执行时间 B. 平均情况执行时间 C. 最坏情况执行时间 D. 空间使用量 7. 递归算法设计的关键点是：（ ） A. 确保每次递归调用都朝着基本情况靠近 B. 保证递归函数的参数每次都减少 C. 设置明确的递归停止条件 D. 以上都是 8. 下列关于迭代和递归说法错误的是：（ ） A. 迭代通常比递归更节省空间 B. 递归更容易理解和实现 C. 迭代的效率通常高于递归 D. 递归算法中可能会出现大量的重复计算 【巩固提升】 9. 在二分查找算法中，要求数据必须是：（ ） A. 无序的 B. 有序的（升序或降序） C. 只能升序排列 D. 只能降序排列 10. 在数据查找中，顺序查找的时间复杂度在最坏情况下是：（ ） A. O(1) B. O(logn) C. O(n) D. O(n^2) 11. 二分查找法适用于哪种数据结构的查找？（ ） A. 无序数组 B. 有序数组 C. 链表 D. 栈 12. 在冒泡排序算法中，最好情况（即数组已经是有序的）下需要进行多少轮比较？（ ） A. n B. n-1 C. n(n-1)/2 D. 0 13. 什么是二分查找算法的基本思想？（ ） A. 通过不断将查找区间缩小一半来逼近目标值 B. 通过交换元素位置来排序数组 C. 通过比较数组元素来确定插入位置 D. 通过构建有序链表来加速查找 【拓展应用】 1 4. 以下程序代码采用的算法是(   )。 def gcd(m，n)： while m%n != 0： m，n=n，m%n return n a=int(input("请输入a的值：")) b=int(input("请输入b的值：")) print(gcd(a，b)) A． 枚举法 B．二分法 C．递归法 D．迭代法 15. 关于迭代与递归算法，下列说法错误的是（     ） A．迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B．递归是重复调用函数自身 C．迭代程序可以转换成等价的递归程序 D．迭代和递归是同一种算法的两种不同的表述 参考答案： 【夯实基础】 1. 本题考查算法时间复杂度相关内容。该函数采用了递归算法，执行过程为: f(x,n)->x*f(x,n-1)->x*f(x,-2)-.>......->x*f(x,n-2)，时间复杂度是O(n)。故本题答案是C选项 2. A 解析：二分查找法在长度为n的有序线性表中查找元素时，每次比较都将查找区间缩小一半，因此平均查找长度为O(log2n)。 3. A 解析：顺序查找法在长度为n的线性表中查找元素，平均情况下需要检查表中一半的元素，即(n+1)/2次比较。这是因为在最坏情况下（元素在表尾或不在表中）需要n次比较，而在最佳情况下（元素在第一个位置）只需1次比较，平均下来即为(n+1)/2次。 4. A 解析：在有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中，二分查找82的过程如下：首先比较中间值41，82大于41，则在右半边查找；接下来比较中间值77，82仍然大于77，继续在右半边查找；再次比较中间值82，刚好找到，因此总共比较了4次。 5. A 解析：在最坏的情况下，二叉排序树可能退化为一个链表，这时的查