高考信息技術(shù)復(fù)習(xí)專題八-查找算法的程序?qū)崿F(xiàn)

專題八查找算法的程序?qū)崿F(xiàn)【考綱標(biāo)準(zhǔn)】考試內(nèi)容考試要求查找算法的程序?qū)崿F(xiàn)：①順序查找②對(duì)分查找c1．(2018·11月浙江選考)數(shù)組a中存儲(chǔ)的是左右交替上升的n個(gè)正整數(shù)，如下表所示：a(1)a(2)a(3)……a(n－2)a(n－1)a(n)32538……553112依據(jù)對(duì)分查找思想，設(shè)計(jì)一個(gè)在數(shù)組a中查找數(shù)據(jù)key的程序。實(shí)現(xiàn)該功能的VB程序如下，但加框處代碼有錯(cuò)，請(qǐng)改正。EndIfEndSub解析本題考核對(duì)分查找的思想，算法比較簡(jiǎn)單，關(guān)鍵是對(duì)數(shù)組a中存儲(chǔ)的是左右交替上升的n個(gè)正整數(shù)的理解，數(shù)組的前半部分是遞增的，后半部分是遞減的，且他們的大小變化規(guī)律是3→12→25→31→38→55。因此如果在前半部分找不到，還可能在右半部分對(duì)稱的位置找到。因此(1)應(yīng)修改為i<＝j(luò)，也就是說(shuō)最后一次查找，變量i＝j(luò)＝m。如果在前半部分找不到，該數(shù)可能比a(m)小，此時(shí)j＝m－1，該數(shù)大于(j)但小于a(m)，在與j對(duì)稱的位置(即n－j＋1)可能是要找的數(shù)；該數(shù)可能比a(m)大，此時(shí)i＝m＋1，該數(shù)大于a(m)但小于a(i)，在與(i－1)對(duì)稱的位置(即n－(i－1)＋1)可能是要找的數(shù)。答案

(1)i＜＝j(luò)

(2)n－i＋2或n－j＋1或n＋1－(i＋j)2．(2018·11月浙江選考)數(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)DoWhilei<＝j(luò)m＝(i＋j)\2Ifa(m)＝KeyThenExitDo′ExitDo表示退出循環(huán)IfKeyMod2＝1Anda(m)Mod2＝0Then①i＝m＋1②j＝

m－1③IfKey<a(m)Thenj＝m－1Elsei＝m＋1則(1)、(2)、(3)處語(yǔ)句依次是(

)A．①、②、③ B．①、③、②C．②、①、③ D．③、②、①解析本題考核對(duì)分查找算法。語(yǔ)句KeyMod2＝1Anda(m)Mod2＝0表示要查找的key是奇數(shù)，且m指向的數(shù)是偶數(shù)。奇數(shù)在前，向前找，移動(dòng)尾指針。語(yǔ)句KeyMod2＝0Anda(m)Mod2＝1表示要查找的key是偶數(shù)，且m指向的數(shù)是奇數(shù)。答案C3．(2017·11月浙江選考)某算法的VB程序段如下：i＝1：j＝7：s＝""Key＝Int(Rnd*100)DoWhilei<＝j(luò)m＝(i＋j)\2IfKey＝a(m)Then

s＝s＋"M"：ExitDo

′ExitDo表示退出循環(huán)ElseIfKey<a(m)Then

j＝m－1：s＝s＋"L"Else

i＝m＋1：s＝s＋"R"EndIfLoopText1.Text＝s數(shù)組元素a(1)到a(7)的值依次為“24，35，38，41，45，69，78”。執(zhí)行該程序段后，文本框Text1中顯示內(nèi)容可能的是(

)A．RL B．LMR C．RLR D．LRLM解析找到的情況下，顯示M并停止查找，因此B選項(xiàng)是不可能的。7個(gè)數(shù)據(jù)，在找不到的情況下，至少查找的次數(shù)是Int(Log27)＋1＝3，因此A選項(xiàng)還需繼續(xù)查找。D選項(xiàng)的查找次數(shù)超過(guò)了3次。第一次找到41，向右找，找到69，向左找，找到45，再向右找，沒有找到，該數(shù)在(45，69)之間。答案C一、順序查找1．查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步驟或較短的時(shí)間找到所需的對(duì)象。2．順序查找是在一個(gè)已知無(wú)(或有序)序隊(duì)列中找出與給定關(guān)鍵字相同的數(shù)的具體位置。原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從第一個(gè)開始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)為止。3．由于該部分在前面的幾個(gè)專題均有練習(xí)，本專題不做專題講述。二、對(duì)分查找 (一)基本算法思想

在一個(gè)升序或降序的數(shù)組中，確定該數(shù)組的開始位置i、結(jié)束位置j和中間位置m，用待查找的數(shù)key與m位置所在的值d(m)比較，如果相等，表示找到了，如果在前半段，把結(jié)束位置j修改為m－1，重新查找，如果在后半段，把開始位置i修改為m＋1，再次查找，直到找到或者開始位置大于結(jié)束位置為止。

中間位置m的計(jì)算公式：m＝Int((i＋j)/2)或者m＝(i＋j)\2或者m＝fix((i＋j)/2)。(二)核心代碼1．在升序的數(shù)列d(1)至d(n)中查找key。用i表示開始位置下標(biāo)，用j表示結(jié)束位置下標(biāo)，m表示中間位置下標(biāo)。若找到，輸出該數(shù)據(jù)所在位置pos.如果pos＝0表示沒有找到。 pos＝0:c＝0:i＝1:j＝n DoWhilei<＝j(luò)

′進(jìn)入查找的條件，i與j的關(guān)系

m＝Int((i＋j)/2)

c＝c＋1

′表示查找次數(shù)

Ifd(m)＝KeyThenpos＝m

′找到，用xb記錄下標(biāo)位置ExitDo

′退出循環(huán)

ElseIfKey<d(m)Then

j＝m－1

Else

i＝m＋1

EndIfLoopIfpos＝0ThenText2.Text＝“找不到”ElseText2.Text＝“在數(shù)組中位置為”

＋Str(pos)＋“共查找了”

＋Str(c)＋“次”EndIf2．關(guān)于頭尾指針移動(dòng)有兩種IF結(jié)構(gòu)Ifd(m)＝KeyThen

pos＝m

′記錄下標(biāo)位置

ExitDo

′退出循環(huán)ElseIfKey<d(m)Then

j＝m－1Else

i＝m＋1EndIfIfd(m)＝KeyThen

pos＝m

′下標(biāo)位置

ExitDo

′退出循環(huán)Else

IfKey<d(m)Then

j＝m－1

Else

i＝m＋1

EndIfEndIf3.根據(jù)pos變量的值判斷結(jié)果，如果pos＝0，表示沒有找到，否則輸出查找位置pos。4．根據(jù)循環(huán)結(jié)束后變量i的值判斷結(jié)果，如果沒有找到，頭指針i將移動(dòng)到尾指針j的后面，即i>j；否則在中間位置找到，使用ExitDO語(yǔ)句中途退出，此時(shí)變量m表示查找位置。(三)查找過(guò)程1．明確i、j和m的含義，i表示開始位置，j表示結(jié)束位置，m表示[i，j]的中間位置。d(m)表示m這個(gè)位置所對(duì)應(yīng)的數(shù)值。2．修改i、j的值，如果是升序系列，當(dāng)要查找的數(shù)比中間的數(shù)d(m)小，表示要查找的數(shù)在前半段，讓j＝m－1；否則在后半段，讓i＝m＋1。如果是降序系列，則相反。3．結(jié)束查找有兩個(gè)條件，中間m位置值d(m)與要查找的數(shù)key相等，或者是頭指針i已經(jīng)大于尾指針j。滿足其中一個(gè)，就不再查找了。4．查找結(jié)束后，查找的結(jié)論是要查找的數(shù)在數(shù)組中位置m或者沒有找到。(四)N個(gè)數(shù)最多的查找次數(shù) N個(gè)數(shù)最多的查找次數(shù)最多的查找次數(shù)為Int(Log2N)＋1。(五)常用解題技巧1．列表法

用表格列出每次查找的區(qū)間和比較數(shù)的位置及值。2．二叉樹法

假設(shè)有10個(gè)數(shù)據(jù)1、2、3、4、5、6、7、8、9、10②右2堆依次求出m值(2、8)，m值保留在原位，然后把2邊數(shù)分別放入它的左右2個(gè)子樹(小的放左子樹，大的放右子樹)；③節(jié)點(diǎn)里還有2個(gè)及以上數(shù)的，按照上面規(guī)則求m值，m值保留在原位，其他數(shù)放入它的左右2個(gè)子樹(小的放左子樹，大的放右子樹)；④有左子樹的往左畫條線，代表往左查找失敗的范圍；沒有右子樹的往右畫條線，代表往右查找失敗的范圍?！纠?】

某對(duì)分查找算法的VB程序段如下：i＝1:j＝6:n＝0:f＝False：key＝Val(Text1.Text)DoWhilei<＝j(luò)andNotf

n＝n＋1m＝Fix((i＋j)/2)Ifkey＝a(m)Thenf＝TrueIfkey<a(m)Thenj＝m－1Elsei＝m＋1Loop數(shù)組元素a(1)到a(6)的值依次為“12，19，27，31，46，55”。文本框Text1中輸入“30”后運(yùn)行該程序，則以上程序段運(yùn)行結(jié)束后，下列說(shuō)法不正確的是(

)A．變量i的值為4 B．變量j的值為5

C．變量m的值為4 D．變量n的值為3解析本題考核的知識(shí)點(diǎn)是對(duì)分查找?？梢杂昧斜矸ㄟM(jìn)行跟蹤變量。當(dāng)i>j時(shí)，不再查找。答案Bijma(m)nflag163271False465462False444313False43

【變式訓(xùn)練1】

某對(duì)分查找算法的VB程序段如下：i＝1:j＝6:n＝0:f＝False：key＝Val(Text1.Text)DoWhilei<＝j(luò)andNotfn＝n＋1m＝Fix((i＋j)/2)Ifkey＝a(m)thenf＝TrueIfkey<a(m)thenj＝m－1Elsei＝m＋1Loop數(shù)組元素a(1)到a(6)的值依次為“12，19，27，31，46，55”。文本框Text1中輸入“31”后運(yùn)行該程序，則以上程序段運(yùn)行結(jié)束后，下列說(shuō)法不正確的是(

)A．變量i的值為4 B．變量j的值為5

C．變量m的值為4 D．變量n的值為3解析采用列表法進(jìn)行分析。答案Bijma(m)fn16327False146546False244431True3【例2】

一組“非降序”的數(shù)據(jù)分別存儲(chǔ)在數(shù)組元素a(1)……a(n)中，用對(duì)分查找算法在數(shù)組a中查找key值所在位置，如果有重復(fù)的元素，則顯示最小的位置。部分VB程序如下：Key＝Val(Text1.Text)i＝1:j＝nDoWhilei<＝j(luò)

m＝(i＋j)\'2

Ifa(m)>KeyThen

j＝m－1

Elseifa(m)<KeyTheni＝m＋1

Else

If__________Thenj＝m－1

ElseLabel2.Caption＝Str(Key)＋

“的起始位置是”

＋Str(m):ExitDo

EndIfEndIfLoopIfi>jThenLabel2.Caption＝“找不到”

＋Str(Key)要使程序?qū)崿F(xiàn)上述算法思想，則劃線處的語(yǔ)句為(

)A．a(chǎn)(m－1)＝keyB．a(chǎn)(m)＝keyC．m－1>0anda(m－1)＝keyD．m－1>0anda(m)＝key解析要求如果有重復(fù)的元素，則顯示最小的位置。即m不是第1個(gè)元素且a(m－1)＝key時(shí)，將尾指針移到m的前一個(gè)位置，繼續(xù)查找。同時(shí)如果要取最后一個(gè)相同的數(shù)值。答案C【變式訓(xùn)練2】

某對(duì)分查找算法的VB程序段如下：L＝1:R＝10:Key＝21DoWhileL<＝Rm＝(L＋R)\2Ifa(m)<＝KeyThen

L＝m＋1

Else

R＝m－1Loop數(shù)組元素a(1)到a(10)的值依次為3，9，21，21，21，21，27，28，39，40，執(zhí)行該程序段，變量R、a(R)的值分別是(

)A．2，9 B．3，21 C．6，21 D．7，27解析采用列表法進(jìn)行分析。可見此時(shí)R指向的位置就是要查找的元素。答案CLRma(m)a(m)<＝Key？110521True610828False67621True77727False76

【例3】

某對(duì)分査找算法的VB程序段如下：Key＝Int(Rnd*100)i＝1:j＝7：s＝

""DoWhilei<＝j(luò)m＝(i＋j)\2IfKey＝a(m)Thens＝s＋

“M”：ExitDoIfKey<a(m)Thenj＝m－1:s＝s＋

“L”Elsei＝m＋1:s＝s＋

“R”EndIfLoopText1.Text＝sText1.Text＝s數(shù)組元素a(1)到a(7)的值依次為“25，36，39，42，47，66，78”，執(zhí)行該程序段，文本框Text1中顯示的內(nèi)容是“RLR”，則可以確定隨機(jī)產(chǎn)生的Key值范圍是(

)A．(25，36) B．(47，66)C．(66，78) D．(78，100)解析畫出對(duì)應(yīng)的二叉樹圖如圖所示，其中圈中所示數(shù)字均為元素在數(shù)組中位置。第一次查找，m的值為4，程序運(yùn)行時(shí)，文本框Text1中顯示的內(nèi)容是“RLR”，即從第4個(gè)元素開