（新教材）教科版高中信息技术必修一 4.3 非数值计算 同步练习（含答案）

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