答案 A 本题考查对分查找算法及其程序的实现。第一次循环结束后,m=4,i=5,j=7;第二次循环结束后,m=6,i=5,j=5;第三次循环结束后,m=5,a(m)=x成立,循环结束。最终m=5,i=5,j=5,所以表达式i=j成立。 3.某高校学籍管理系统软件有2万个学生的电子档案(已按学籍号排序),假设从中取出一条记录并与待查项进行比较所花时间为8毫秒,则用对分法在该系统中查找任意一位学生档案最多花费的时间约为 ( ) A.16万毫秒B.8万毫秒 C.10毫秒 D.120毫秒
答案 D 在规模为n的数中查找一个数据至多进行Int(log2n)+1次查找就能得到结果。Int(log220000)+1=14+1=15,因此本题中最多查找15次,故最多花费时间为15*8=120毫秒。 4.有如下VB程序段:
a(1)=2: a(2)=6: a(3)=8: a(4)=9: a(5)=12 a(6)=15: a(7)=17: a(8)=18: a(9)=22: a(10)=30 k=Val(Text1.Text)
i=1: j=10 Do While i <=j m=(i+j) \\ 2 If a(m) <=k Then i=m+1 Else j=m-1 End If Loop
Text2.Text=Str(a(i))+\"← →\"+Str(a(j))
程序运行时,在文本框Text1中输入5,文本框Text2中显示的内容是( ) A.2← →1 B.6← →8 C.2← →6 D.6← →2
答案 D 本题考查对分查找算法及其实现。第1次循环时,变量i和j的值分别为1,10。第2次循环时,变量i和j的值分别为1,4。第3次循环时,变量i和j的值分别为1,1。第4次循环时,变量i和j的值分别为2,1。Do循环结束,最终输出Str(a(i))+\"← →\"+Str(a(j)),即Str(a(2))+\"← →\"+Str(a(1))。所以选D。 5.某对分查找算法的VB程序段如下: k=Val(Text1.Text)
i=1: j=6: Label1.Caption=\"\": f=False Do While i <=j And Not f m=(i+j) \\ 2
If a(m)=k Then f=True If a(m) > a(i) Then
If a(i) <=k And k < a(m) Then j=m-1 Else i=i+1 Else
If a(m) < k And k <=a(j) Then i=i+1 Else j=j-1 End If
Label1.Caption=Label1.Caption+Str(a(m)) Loop
数组元素a(1)到a(6)的值依次为“58,66,72,24,35,40”,在文本框Text1中输入的值为35,执行该程序段,标签Label1中显示的值是( ) A.72 35 B.24 35
C.72 24 35 D.72 24 24 35
答案 D 本题主要考查对分查找算法知识。根据程序代码模拟运行情况如下: 第一次查找:m=3,a(m)=72,i=2,j=6; 第二次查找:m=4,a(m)=24,i=3,j=6; 第三次查找:m=4,a(m)=24,i=4,j=6; 第四次查找:m=5,a(m)=35,f=True。
此时查找成功,循环结束,查找过的数组元素分别是72 24 24 35,因此D选项正确。注:对分查找只能查找有序序列,但本题的输入的数组序列是无序数列。 6.(2015浙江10月学考+选考,11,2分)已知单调函数f(x)在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为( ) A. B. C. D.
答案 D 本题考查对分查找的查找区间长度。对分查找的主要思想是在一个有序的数据序列中不断地寻找当前区间的“中点”,通过与“中点”元素的比对,决定是在前半部分还是后半部分数据中继续查找,通过不断缩小查找区间以提高查找效率。本题中第一次查找区间为[0,1],其查找区间的长度为1,则第二次查找的区间长度为1/2,第三次查找的区间长度为1/4,依此类推,第11次查找的区间长度为1/210。
7.(2016义乌中学3月选考模拟,17,5分)对于函数f(x),若在某区间[a,b]内是单调函数,且其图像与x轴有交点,则存在一个x0使得f(x0)=0,我们可以设法找到x0的值。
满足上述条件的区间[a,b]和函数f(x)必定有f(a)·f(b)<=0,我们设计如下算法:
第一步:区间中点m=
。
第二步:若f(a)·f(m)<0,则含零点的区间为[a,m];否则,含零点的区间为[m,b],将新得到的含零点的区间仍记为[a,b]。
第三步:判断[a,b]的长度是否小于一个足够小的值d。若是,则m是方程的
近似解;否则,返回第一步。
于是我们可以设计函数f(x)=x2-c,就可以用此算法求出任意非负常数c的非负平方根。程序运行效果如下图所示,程序中还输出了区间的左右端点和区间长度值。
Const min As Single=0.00005 Dim c As Single
Function fn(x As Single)As Single ① End Function
Private Sub Command1_Click() 按钮上的程序 Dim a As Single,b As Single,m As Single c=Val(Text1.Text)a=0 b=c
Do While ② m=(a+b)/2
List1.AddItem Str(a)&“”&Str(b)&“”&Str(b-a) If ③ Then b=m Else a=m End If Loop
Label2.Caption=Str(m) End Sub
回答以下问题:
(1)事件处理过程“Command1_Click()”用到的算法是 (填算法具体名称)。
(2)请将程序中的三处代码补充完整。
(3)通过测试可知,该程序得到的 的近似值为1.4142,实际上更精确的值是1.4142135623731,请问如何改善程序,得到一个更精确的近似值?请写出至少两种改善意见:
。 答案 (1)对分查找 (2)①fn=x*x-c
②(b-a)>=min(或abs(a-b)>=min,其中没有“=”亦可) ③fn(a)*fn(m)<0或fn(m)>0(有“=”亦可)
(3)把所有single换成double(双精度类型double的有效位数更多);把min的值设置得更小,如0.0000000001;结束条件的区间范围更小
解析 本题主要考查对分查找的算法思想:若函数f(x)在某区间[a,b]内是单调函数,若f(a)和f(b)的值互异,则该区间内必有某个值x0,使得f(x0)=0,则在曲线上体现为必和x轴相交。
程序实现时设计了一个结束条件:[a,b]的长度小于一个足够小的值,题中定义为一个常数:Const min As Single=0.00005,故②处代码含义为:当区间长度大于或者等于min时继续查找。变量m为当前区间[a,b]的中间点,若fn(a)*fn(m)<0,说明零点在区间[a,m]中,故将b的值设为m,否则,说明零点在区间[b,m]中,故将a的值设为m。
