查找算法的程序实现【教师版】.docx
查找算法的程序实现【教师版】【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。for i=1 to 8if then Text1.text=str(i)exit forend ifnext iif then text1.text=在数组中没有找到+str(key)end if答案:a(i)=key i>8解析:根据顺序查找的基本思想,依次将数组元素a(1)到a(8)跟查找键值key比较,若相等,显示找到结果并退出循环,否则继续查找。程序实现时,变量i用来表示第几次查找,而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中,并通过exit for来结束查找。若没有找到key,则i的值必定大于8,故划线处的条件表达式为“a(i)=key”,划线处的条件表达式为“i>8”。【例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 While i<=jc=c+1m=Fix(i+j)/2)If key=b(m) Then Exit DoIf key<b(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,第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 i<=jm=(i+j)2If a(m)=Key Then Exit Do'Exit Do 表示退出循环If Key Mod 2=1 And a(m) Mod 2=0 Then(1) ElseIf Key Mod 2=0 And a(m) Mod 2=1 Then(2) Else(3) End IfLoopIf i>j Then s=没有找到! Else s=位置:+Str(m)Text2.Text=s上述程序中划线处可选语句为:i=m+1j=m-1If Key<a(m) Then j=m-1 Else i=m+1则(1)、(2)、(3)处语句依次是()A.、B.、C.、D.、答案：C解析：如果key是奇数并且查找区间的中间是偶数,则在前半段查找(因为后半段肯定都是偶数),即j=m-1;否则如果key是偶数并且查找区间的中间是奇数,则在后半段查找(因为前半段肯定都是奇数),即i=m+1;否则就是纯偶数升序列中找偶数或纯奇数的升序列中找奇数,按正常对分查找即If Key<a(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程序段如下,请在划线处填入正确的语句。x=Val(Text1.Text)i=l:j=n-lDo While i<=jm=(i+j)2If x<a(m) Then i=m+1 Else j=m-1LoopFor k=n To Step-1 a(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 i<=jm=(i+j)2n=n+1If Key=d(m) Then Exit DoIf Key>d(m) Then j=m-1 Else i=m+1LoopIf i<=j Thens=m-nElses=nd(1)到d(6)的值依次为“88,77,53,47,39,28”,输入某个Key值后,运行该程序段后,变量s结果为1,则输入key的值是()A.89B.77C.47D.39答案 C解析 程序采用对分查找算法,由代码得如果s=n为1,需满足i>j,即需要查找的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 Do'Exit Do表示退出循环ElseIf key < 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 次,也就是最多查找次数,故选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 (Text1.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)处应改正为_。解析本题考核的对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解，数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是31225313855。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此(1)应修改为i<j，也就是说最后一次查找，变量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.)数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i1j10KeyVal(Text1.Text)Do While i<jm(ij)2If a(m)Key Then Exit DoExit Do表示退出循环If Key Mod 21 And a(m) Mod 20 Then ElseIf Key Mod 20 And a(m) Mod 21 Then Else End IfLoopIf i>j Then s”没有找到！”Else s”位置：”Str(m)Text2.Texts上述程序中方框处可选语句为： im1 jm1 If Key<a(m) Then jm1 Else im1则(1)、(2)、(3)处语句依次是()A.、 B.、C.、 D.、解析本题考核对分查找算法基本思想。语句Key Mod 21 And a(m) Mod 20表示要查找的key是奇数，且m指向的数是偶数。奇数在前，向前找，移动尾指针。语句Key Mod 20 And a(m) Mod 21表示要查找的key是偶数，且m指向的数是奇数。答案C6.采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”，i1j7x55Do While ij m(ij)2 If a(m)x Then Exit Do If a(m)x Then jm1 Else im1 Loop 经过上述代码查找后，下列表述正确的是()A.im1 B.im1C.jm1 D.jm1解析本题为对分查找算法程序，分析程序运行过程中的变量变化情况：查找次数变量i变量j变量ma(m)第1次查找17466第2次查找13238第3次查找33351退出循环43经过3次查找，i4，j3，ij，退出循环，根据此时变量值判断A正确。答案A7.某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为()A.100万毫秒 B.50万毫秒C.10毫秒 D.170毫秒解析对分查找的查找效率较高，无论是否找到，最多进行Int(log2n)1次查找，表示小于等于log2n1的最大整数。n100000，比较次数为17次，因此最多花费的时间是170毫秒。答案D8.使用VB程序查找单词最大间距:在文本框Text1中输入一段英文,并在文本框Text2中输入英文段落中的某个单词(或字符串),单击“最大间距”按钮(Command1)后,在文本框Text3中显示该单词在文中某两次出现的最大间距,若只出现一次或不出现则显示值为0。程序运行界面如下图所示:实现上述功能的VB程序如下,请在划线处填入正确的代码。Private Sub Command1_Click()Dim a(1 To 1000)As String'数组a存储文中出现该指定单词(或字符串)的各个位置Dim s As String,c As String,ch As StringDim n As Integer,max As Integer,i As Integers=Text1.Textc=Text2.Textn=0Max=0For i=1 To Len(s)-Len(c)+1ch= If ch=c Thenn=n+1 If n>=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(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 i<>k Then ta(i)：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时，ki，k指向的数与前面4个数进行比较，k指向前面较小的数，并交换，第三轮12与63交换。答案A10.双向选择排序算法。在经典的选择排序基础上，如果在选择出最小数的同时，也能选择预见最大数并将两数放置合适位置，这样就使排序效率提高一倍。依照上述双向选择排序的算法，小张编写了一个VB程序，功能如下：在列表框List中显示排序前数据，单击“排序”按钮Command1，在列表框List中显示这些数据按升序排序后的结果。运行效果如下图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。Const n10Dim b(1 To n)As IntegerPrivate Sub command1_Click( )Dim i As IntegerDim t As IntegerFor i1 To For ji To If b(j)<b(i) Then tb(i)：b(i)b(j)：b(j)t End If 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
