查找算法的程序实现【教师版】.docx

《查找算法的程序实现【教师版】.docx》由会员分享，可在线阅读，更多相关《查找算法的程序实现【教师版】.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、查找算法的程序实现【教师版】【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。for i=1 to 8if thenText1.text=str(i)exit forend ifnext iif thentext1.text=在数组中没有找到+str(key)end if答案:a(i)=key i8解析:根据顺序查找的基本思想,依次将数组元素a(1)到a(8)跟查找键值key比较,若相等,显示找到结果并退出循环,否则继续查找。程序实现时,变量i用来表示第几次查找,而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(

2、i)的值等于key则将该数组元素的下标值i显示在text1文本框中,并通过exit for来结束查找。若没有找到key,则i的值必定大于8,故划线处的条件表达式为“a(i)=key”,划线处的条件表达式为“i8”。【例2】.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6)/6=7/2;若对该数组进行对分查找,其平均查找次数为 ()A.7/2B.7/3C.5/2D.2答案：D对分查找最多进行log2N+1次查找,N=6,所以最多进行2次查找。【例3】.某对分查找算法的VB程序段如下:i=1:j=8:c=0Do Whi

3、le i=jc=c+1m=Fix(i+j)/2)If key=b(m) Then Exit DoIf keyb(m) Then j=m-1 Else i=m+1Loop数组元素b(1)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是()A.48或32B.48或96C.32或82D.82或96答案：C解析：程序采用对分查找算法,变量c表示查找次数,第一次查找的值为48,第二次查找的值为32或82。可以用二叉树的方法考虑这个问题,如下图所示,节点中的数字表示元素编号,节点在第n层,表示找到该数要n次。对于8个升序的数列a,第

4、1次查找的是a(4),第2次找的是a(2)、a(6),第3次找的是a(1)、a(3)、a(5)、a(7),第4次找的是a(8)。【例4】.数组a为一组正整数,奇数在前,偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想:设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下:i=1:j=10Key=Val(Text1.Text)Do While ij Then s=没有找到! Else s=位置:+Str(m)Text2.Text=s上述程序中划线处可选语句为:i=m+1j=m-1If Keya(m) Then j=m-1 Else i=m+1则(1)、(2)、(3)处语句依次

5、是()A.、B.、C.、D.、答案：C解析：如果key是奇数并且查找区间的中间是偶数,则在前半段查找(因为后半段肯定都是偶数),即j=m-1;否则如果key是偶数并且查找区间的中间是奇数,则在后半段查找(因为前半段肯定都是奇数),即i=m+1;否则就是纯偶数升序列中找偶数或纯奇数的升序列中找奇数,按正常对分查找即If Keya(m) Then j=m-1 Else i=m+1。强化训练1.数组a中存放着已排序的n-1个实验数据(a(1)a(2)a(n-1),a(n)暂未存储数据)。现将文本框Text1中输入的新数据插入到数组a中相应位置,从而使n个数据仍保持有序。完成该功能的VB程序段如下,请

6、在划线处填入正确的语句。x=Val(Text1.Text)i=l:j=n-lDo While i=jm=(i+j)2If xa(m) Then i=m+1 Else j=m-1LoopFor k=n To Step-1a(k)=a(k-1)Next ka(i)=x答案 i+1或j+2解析 程序中通过对分查找法找到插入位置,该位置是i,那么就需要把a(n-1)、a(n-2)a(i)依次往后移一个位置,相当于各位置加1,然后把x存入a(i)中。该位置也可以是j+2。2.某对分查找算法的VB程序段如下:n=0:i=1:j=6Key=Val(Text1.Text)Do While id(m) Then

7、 j=m-1 Else i=m+1LoopIf ij,即需要查找的key不在数组中,但是仅查找1次不满足该条件,故s=m-n=1,查找3次满足。本题可以用二叉树的方法解决,如下图所示,节点中的数字表示元素编号,节点在第n层,表示找到该数要n次。要满足m-n=1,即中点值比查找次数要大1,由图可知,a(4)满足这个条件。3.某对分査找算法的VB程序段如下:i = 1:j = 7:s = key =Int(Rnd * 100)Do While i = jm = (i + j) 2If key = a(m) Then s = s + M:Exit DoExit Do表示退出循环ElseIf key

8、a(m) Then j = m-1:s = s + LElse i = m + 1:s = s + REnd IfLoopText1.Text = s数组元素a(1)到a(9)的值依次为“24,35,38,41,45,69,78”。若该程序段执行后,文本框Text1中显示的内容可能是()A.RLB.LMRC.RLRD.LRLM答案 C解析 分析程序得知,查找成功会输出M,循环结束,所以 M 不可能在中间,排除B 选项。对 n 个数据查找,最多查找次数为 Log2n+1(向下取整),7 个元素,最多查找 3 次,所以排除 D 选项。如果无法找到(不输出M),则需要查找 3 次,也就是最多查找次数

9、,故选C。4.数组a中存储的是左右交替上升的n个正整数，如下表所示：a(1)a(2)a(3)a(n2)a(n1)a(n)32538553112依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。Private Sub Command1_Click( ) Const n6 Dim a(1 To n) As Integer，flag As Boolean Dim i As Integer，j As Integer，m As Integer，key As Integer 读取一组正整数，按上述规则存入数组a中，代码略。 keyVal (Tex

10、t1.Text) i1j(n1)2flag=TrueDo While And Not flag(1) m(ij)2 If key=a(m) Then flag=True ElseIf keya(m) Then j=m-1 Else i=m+1 End If Loop If Not flag And j0 Then m=(2) If keya(m) Then flagTrue End If If flag Then Text2.TextStr(m) Else Text2.Text”找不到” End IfEnd Sub其中，加框(1)处应改正为_；加框(2)处应改正为_。解析本题考核的对分查找的思

11、想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解，数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是31225313855。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此(1)应修改为ij，也就是说最后一次查找，变量ijm。如果在前半部分找不到，该数可能比a(m)小，此时jm1，该数大于(j)但小于a(m)，在与j对称的位置(即nj1)可能是要找的数；该数可能比a(m)大，此时im1，该数大于a(m)但小于a(i)，在与(i1)对称的位置(即n(i1)1)可能是要找的数。答案(1)ij(2)ni2或nj1或n1(ij)2或其他等价表达式5.

12、)数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i1j10KeyVal(Text1.Text)Do While ij Then s”没有找到！”Else s”位置：”Str(m)Text2.Texts上述程序中方框处可选语句为： im1 jm1 If Key=2 ThenIf a(n)-a(n-1)-Len(c)Max Then Max=a(n)-a(n-1)-Len(c)End IfEnd IfNext iText3.Text=str(max)End Sub答案 mid(s,i,len

13、(c)a(n)=i解析 程序采用顺序查找算法,查找单词c。输入的英文总长度为len(s),待查的单词长度为len(c),循环查找从第1个字符开始,依次截取len(c)个字符与待查单词对比,对比一致则记录个数和出现位置,出现位置存入数组,即a(n)=i。如果找到2个或2个以上相同的字符,储存间距较大的间距值Max。所以处应为在一段英文s中,从第i个字符开始截取len(c)个字符,即mid(s,i,len(c)。9.某排序算法的VB程序段如下： For i7 To 5 Step 1 ki For j1 To i1 If a(j)a(k) Then kj Next j If ik Then ta(i

14、)：a(i)a(k)：a(k)t End IfNext i数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则排序“加工”后数组元素a(1)到a(7)的数据依次是()A.85，41，75，63，12，11，10B.85，75，63，41，12，11，10C.10，11，12，63，75，41，85D.10，11，12，41，63，75，85解析这是选择排序的变形。当i7时，ki，k指向的数与前面6个数进行比较，k指向前面较小的数，并交换，第一轮10与85互换。当i6时，ki，k指向的数与前面5个数进行比较，k指向前面较小的数，并交换，第二轮没有交换。当i5时，

15、ki，k指向的数与前面4个数进行比较，k指向前面较小的数，并交换，第三轮12与63交换。答案A10.双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个VB程序，功能如下：在列表框List中显示排序前数据，单击“排序”按钮Command1，在列表框List中显示这些数据按升序排序后的结果。运行效果如下图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。Const n10Dim b(1 To n)As IntegerPrivate Sub command1_Cli

16、ck( )Dim i As IntegerDim t As IntegerFor i1 To For ji To If b(j)b(ni1) Then tb(j)：b(j)b(ni1)：b(ni1)t End If Next jNext iFor i1 To nList2.AddItem Str(b(i)Next iEnd SubPrivate Sub Form_Load( )For i1 To 10b(i)1Int(Rnd*100)List1.AddItem Str(b(i)Next iEnd Sub解析每次找出两个最值，因此只要比较的趟数是总数的一半即可。每次实现头尾有序，i相对的数在ni1。答案n2 n-i+1