查找算法的程序?qū)崿F(xiàn)【教師版】

1、查找算法的程序?qū)崿F(xiàn)【教師版】【例1】 在數(shù)組元素a(1)到a(8)中查找鍵值為key的數(shù),其順序查找的VB程序段如下,請(qǐng)?jiān)趧澗€處填寫正確的語(yǔ)句。for i=1 to 8if thenText1.text=str(i)exit forend ifnext iif thentext1.text=在數(shù)組中沒有找到+str(key)end if答案:a(i)=key i8解析:根據(jù)順序查找的基本思想,依次將數(shù)組元素a(1)到a(8)跟查找鍵值key比較,若相等,顯示找到結(jié)果并退出循環(huán),否則繼續(xù)查找。程序?qū)崿F(xiàn)時(shí),變量i用來表示第幾次查找,而a(i)則是第i次查找時(shí)被訪問到的數(shù)組元素。如果某個(gè)數(shù)組元素a(

2、i)的值等于key則將該數(shù)組元素的下標(biāo)值i顯示在text1文本框中,并通過exit for來結(jié)束查找。若沒有找到key,則i的值必定大于8,故劃線處的條件表達(dá)式為“a(i)=key”,劃線處的條件表達(dá)式為“i8”。【例2】.某數(shù)組的6個(gè)元素依次為“27,32,57,78,80,90”。若對(duì)該數(shù)組進(jìn)行順序查找,其平均查找次數(shù)為(1+2+3+4+5+6)/6=7/2;若對(duì)該數(shù)組進(jìn)行對(duì)分查找,其平均查找次數(shù)為 ()A.7/2B.7/3C.5/2D.2答案：D對(duì)分查找最多進(jìn)行l(wèi)og2N+1次查找,N=6,所以最多進(jìn)行2次查找?！纠?】.某對(duì)分查找算法的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數(shù)組元素b(1)到b(8)的值依次為“22,32,39,48,71,82,96,106”。若該程序段運(yùn)行結(jié)束后,c的值為2,則key的值是()A.48或32B.48或96C.32或82D.82或96答案：C解析：程序采用對(duì)分查找算法,變量c表示查找次數(shù),第一次查找的值為48,第二次查找的值為32或82?？梢杂枚鏄涞姆椒紤]這個(gè)問題,如下圖所示,節(jié)點(diǎn)中的數(shù)字表示元素編號(hào),節(jié)點(diǎn)在第n層,表示找到該數(shù)要n次。對(duì)于8個(gè)升序的數(shù)列a,第

4、1次查找的是a(4),第2次找的是a(2)、a(6),第3次找的是a(1)、a(3)、a(5)、a(7),第4次找的是a(8)?！纠?】.數(shù)組a為一組正整數(shù),奇數(shù)在前,偶數(shù)在后。奇數(shù)與偶數(shù)已分別按升序排序。依據(jù)對(duì)分查找思想:設(shè)計(jì)一個(gè)在數(shù)組a中查找數(shù)據(jù)Key的程序。實(shí)現(xiàn)該功能的VB程序段如下:i=1:j=10Key=Val(Text1.Text)Do While ij Then s=沒有找到! Else s=位置:+Str(m)Text2.Text=s上述程序中劃線處可選語(yǔ)句為:i=m+1j=m-1If Keya(m) Then j=m-1 Else i=m+1則(1)、(2)、(3)處語(yǔ)句依次

5、是()A.、B.、C.、D.、答案：C解析：如果key是奇數(shù)并且查找區(qū)間的中間是偶數(shù),則在前半段查找(因?yàn)楹蟀攵慰隙ǘ际桥紨?shù)),即j=m-1;否則如果key是偶數(shù)并且查找區(qū)間的中間是奇數(shù),則在后半段查找(因?yàn)榍鞍攵慰隙ǘ际瞧鏀?shù)),即i=m+1;否則就是純偶數(shù)升序列中找偶數(shù)或純奇數(shù)的升序列中找奇數(shù),按正常對(duì)分查找即If Keya(m) Then j=m-1 Else i=m+1。強(qiáng)化訓(xùn)練1.數(shù)組a中存放著已排序的n-1個(gè)實(shí)驗(yàn)數(shù)據(jù)(a(1)a(2)a(n-1),a(n)暫未存儲(chǔ)數(shù)據(jù))?，F(xiàn)將文本框Text1中輸入的新數(shù)據(jù)插入到數(shù)組a中相應(yīng)位置,從而使n個(gè)數(shù)據(jù)仍保持有序。完成該功能的VB程序段如下,請(qǐng)

6、在劃線處填入正確的語(yǔ)句。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解析 程序中通過對(duì)分查找法找到插入位置,該位置是i,那么就需要把a(bǔ)(n-1)、a(n-2)a(i)依次往后移一個(gè)位置,相當(dāng)于各位置加1,然后把x存入a(i)中。該位置也可以是j+2。2.某對(duì)分查找算法的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不在數(shù)組中,但是僅查找1次不滿足該條件,故s=m-n=1,查找3次滿足。本題可以用二叉樹的方法解決,如下圖所示,節(jié)點(diǎn)中的數(shù)字表示元素編號(hào),節(jié)點(diǎn)在第n層,表示找到該數(shù)要n次。要滿足m-n=1,即中點(diǎn)值比查找次數(shù)要大1,由圖可知,a(4)滿足這個(gè)條件。3.某對(duì)分査找算法的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表示退出循環(huán)ElseIf key

8、a(m) Then j = m-1:s = s + LElse i = m + 1:s = s + REnd IfLoopText1.Text = s數(shù)組元素a(1)到a(9)的值依次為“24,35,38,41,45,69,78”。若該程序段執(zhí)行后,文本框Text1中顯示的內(nèi)容可能是()A.RLB.LMRC.RLRD.LRLM答案 C解析 分析程序得知,查找成功會(huì)輸出M,循環(huán)結(jié)束,所以 M 不可能在中間,排除B 選項(xiàng)。對(duì) n 個(gè)數(shù)據(jù)查找,最多查找次數(shù)為 Log2n+1(向下取整),7 個(gè)元素,最多查找 3 次,所以排除 D 選項(xiàng)。如果無法找到(不輸出M),則需要查找 3 次,也就是最多查找次數(shù)

9、,故選C。4.數(shù)組a中存儲(chǔ)的是左右交替上升的n個(gè)正整數(shù)，如下表所示：a(1)a(2)a(3)a(n2)a(n1)a(n)32538553112依據(jù)對(duì)分查找思想，設(shè)計(jì)一個(gè)在數(shù)組a中查找數(shù)據(jù)key的程序。實(shí)現(xiàn)該功能的VB程序如下，但加框處代碼有錯(cuò)，請(qǐng)改正。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 讀取一組正整數(shù)，按上述規(guī)則存入數(shù)組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)處應(yīng)改正為_；加框(2)處應(yīng)改正為_。解析本題考核的對(duì)分查找的思

11、想，算法比較簡(jiǎn)單，關(guān)鍵是對(duì)數(shù)組a中存儲(chǔ)的是左右交替上升的n個(gè)正整數(shù)的理解，數(shù)組的前半部分是遞增的，后半部分是遞減的，且他們的大小變化規(guī)律是31225313855。因此如果在前半部分找不到，還可能在右半部分對(duì)稱的位置找到。因此(1)應(yīng)修改為ij，也就是說最后一次查找，變量ijm。如果在前半部分找不到，該數(shù)可能比a(m)小，此時(shí)jm1，該數(shù)大于(j)但小于a(m)，在與j對(duì)稱的位置(即nj1)可能是要找的數(shù)；該數(shù)可能比a(m)大，此時(shí)im1，該數(shù)大于a(m)但小于a(i)，在與(i1)對(duì)稱的位置(即n(i1)1)可能是要找的數(shù)。答案(1)ij(2)ni2或nj1或n1(ij)2或其他等價(jià)表達(dá)式5.

12、)數(shù)組a為一組正整數(shù)，奇數(shù)在前，偶數(shù)在后。奇數(shù)與偶數(shù)已分別按升序排序。依據(jù)對(duì)分查找思想：設(shè)計(jì)一個(gè)在數(shù)組a中查找數(shù)據(jù)Key的程序。實(shí)現(xiàn)該功能的VB程序段如下：i1j10KeyVal(Text1.Text)Do While ij Then s”沒有找到！”Else s”位置：”Str(m)Text2.Texts上述程序中方框處可選語(yǔ)句為： 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。輸入的英文總長(zhǎng)度為len(s),待查的單詞長(zhǎng)度為len(c),循環(huán)查找從第1個(gè)字符開始,依次截取len(c)個(gè)字符與待查單詞對(duì)比,對(duì)比一致則記錄個(gè)數(shù)和出現(xiàn)位置,出現(xiàn)位置存入數(shù)組,即a(n)=i。如果找到2個(gè)或2個(gè)以上相同的字符,儲(chǔ)存間距較大的間距值Max。所以處應(yīng)為在一段英文s中,從第i個(gè)字符開始截取len(c)個(gè)字符,即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數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“10，41，75，12，63，11，85”。則排序“加工”后數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次是()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解析這是選擇排序的變形。當(dāng)i7時(shí)，ki，k指向的數(shù)與前面6個(gè)數(shù)進(jìn)行比較，k指向前面較小的數(shù)，并交換，第一輪10與85互換。當(dāng)i6時(shí)，ki，k指向的數(shù)與前面5個(gè)數(shù)進(jìn)行比較，k指向前面較小的數(shù)，并交換，第二輪沒有交換。當(dāng)i5時(shí)，

15、ki，k指向的數(shù)與前面4個(gè)數(shù)進(jìn)行比較，k指向前面較小的數(shù)，并交換，第三輪12與63交換。答案A10.雙向選擇排序算法。在經(jīng)典的選擇排序基礎(chǔ)上，如果在選擇出最小數(shù)的同時(shí)，也能選擇預(yù)見最大數(shù)并將兩數(shù)放置合適位置，這樣就使排序效率提高一倍。依照上述雙向選擇排序的算法，小張編寫了一個(gè)VB程序，功能如下：在列表框List中顯示排序前數(shù)據(jù)，單擊“排序”按鈕Command1，在列表框List中顯示這些數(shù)據(jù)按升序排序后的結(jié)果。運(yùn)行效果如下圖所示。實(shí)現(xiàn)上述功能的VB程序如下，但加框處代碼有錯(cuò)，請(qǐng)改正。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(ni1) T