1、4.3非数值计算一、 填空题1.二分查找又叫（ ），该方法主要将数列（ ）排列，采用（ ）的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。2.递增数列用二分法查找时，先以（ ）位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列（ ）为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。3.二分法查找的前提条件是被查找的数据（ ）的。4.在数学与计算机领域中，递归函数是指用（ ）定义该函数的方法。5.递归的要素：（ ）的递归的重要组成；（ ），它保证递归能在（ ）的计算后得出结果，而不会产生（ ）的情况。6.递归的基本思想是把（
2、）的问题层层转化为规模较小的（ ）问题求解。对递归而言，（ ）与（ ），二者缺一不可。7.结合分治策略，递归也可以用（ ）（ ）（ ）三个字概况。分：将原有问题（ ）成K个子问题；治：对这K个子问题（ ）。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合：将求出的小规模问题的解（ ）为一个更大规模问题的解，自下而上逐步求出原问题的解。8.迭代算法与递归算法都需要（ ）某些代码，两者既有区别又有密切的联系。迭代是重复（ ）的活动，其目的通常是逼迫（ ），其结束方式，通常使用（ ）结束循环。递归的重复方式是重复（ ），其结束方式是遇到
3、（ ）的情况时逐层返回。二、 单选题1.若提示还是高了，则第三次猜12，依次类推；。这种每次缩小一半查找范围而达到迅速确定目标的算法称为（）。A.排序法 B.顺序查找法 C.解析法 D.二分查找法2.二分查找又称折半查找,是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是( )A.85 78 59 53 19 18B.67 62 68 4 1 17C.11 99 4 25 3 39D.43 71 78 81 6 553. 查找的基本算法不包括（ ） A. 顺序查找 B.二分查找 C.哈希查找 D.递归三、 判断题1. 递归的边界条件要素，是为了保证递归能在有限次的计算后得出结果
4、，而不会产生无限循环的情况。2. 迭代算法与递归算法都需要重复执行某些代码，两者基本相同。四、 程序分析用二分法求解 x3- x2 + x - 1 = 0，完善下面程序。def f(x): #定义方程 return x*3-x*2+x-1a=float(input(请输入解区间的左边界：)b=float(input(请输入解区间的右边界：)while abs(b-a)1e-6: x0=(a+b)/2 if （）: b=x0 if （）: a=x0 if （）: breakprint(解为:,x0)input(运行完毕，请按回车键退出.)参考答案一、 填空题1.折半查找 有序 跳跃式2.中点 缩小3.函数自身 4.递推关系 边界条件 有限次 无限循环5.必须是有序6.规模较大 同类 递推 回归7.“分”“治”“合” 分解 分别求解 合并8.重复执行 反馈过程 所需目标或结果 计数器调用函数自身 满足终止条件二、 单选题1. DAD三、 判断题1.对 2.错四、 程序分析f(a)*f(x0)0 f(b)*f(x0)0 f(x0)=0
