高中信息技術(shù)選修1：算法與程序設(shè)計(jì) 5.4 查找算法的程序?qū)崿F(xiàn) 說課一等獎(jiǎng)

二叉樹在對(duì)分查找中的應(yīng)用玉環(huán)中學(xué)林巍【多選】如下對(duì)分查找程序：i=1:j=10:nx=0Key=Int(Rnd*100)+0.5DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDoElseIfKey<a(m)Thenj=m-1:nx=nx-1Elsei=m+1:nx=nx+1EndIfLoopText1.Text=Str(nx)已經(jīng)數(shù)組元素a(1)到a(10)分別為“11,26,37,49,55,62,78,79,85,98”，按照該程序執(zhí)行后，Text1中的內(nèi)容不可能的數(shù)字有（）A．-4

B．-3

C．-2

D．-1

E．0F．1

G．2

H．3

I．4典型題對(duì)分查找模型Key=Val(Text1.Text)i=1:j=10:s=""DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDo'ExitDo表示退出循環(huán)ElseIfKey<a(m)Thenj=m-1Elsei=m+1EndIfs=s+Str(a(m))Loop二叉樹的概念在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。根結(jié)點(diǎn)：最上面的結(jié)點(diǎn)葉子結(jié)點(diǎn)：沒有子結(jié)點(diǎn)的結(jié)點(diǎn)二叉樹的子樹有左右之分建樹——對(duì)分查找模型Key=Val(Text1.Text)i=1:j=10:s=""DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDo'ExitDo表示退出循環(huán)ElseIfKey<a(m)Thenj=m-1Elsei=m+1EndIfs=s+Str(a(m))Loop建樹key=Val(Text1.Text)i=1:j=10Text2.Text=""DoWhilei<=jm=Int((i+j)/2+0.5)Ifkey=a(m)ThenExitDoIfkey<a(m)Thenj=m-1Elsei=m+1Text2.Text=Text2.Text+Str(a(m))Loop第3題探究二叉樹的性質(zhì)性質(zhì)1：從每節(jié)點(diǎn)出發(fā)，往左走數(shù)字______，往右走數(shù)字______。性質(zhì)2：每個(gè)節(jié)點(diǎn)為每次計(jì)算的m值。m、i、j的關(guān)系是什么？若存在左子樹，最左邊的結(jié)點(diǎn)序號(hào)就是______，若不存在，就是______。若存在右子樹，最右邊的結(jié)點(diǎn)序號(hào)就是______，若不存在，就是______。性質(zhì)3：如果數(shù)據(jù)找不到，m、i、j的關(guān)系是什么？若往左走出，則__________若往右走出，則__________變大變小i值m值j值m值j=m-1i=m+1探究二叉樹的性質(zhì)性質(zhì)4：每個(gè)數(shù)所在的______，就是對(duì)分查找需要的______；如果找不到，最后走出的__________就是__________。層數(shù)次數(shù)結(jié)點(diǎn)層數(shù)查找次數(shù)【多選】如下對(duì)分查找程序：i=1:j=10:nx=0Key=Int(Rnd*100)+0.5DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDoElseIfKey<a(m)Thenj=m-1:nx=nx-1Elsei=m+1:nx=nx+1EndIfLoopText1.Text=Str(nx)已經(jīng)數(shù)組元素a(1)到a(10)分別為“11,26,37,49,55,62,78,79,85,98”，按照該程序執(zhí)行后，Text1中的內(nèi)容不可能的數(shù)字有（）A．-4

B．-3

C．-2

D．-1

E．0F．1

G．2

H．3

I．4解決問題1第1題解決問題2對(duì)數(shù)組a中6個(gè)有序數(shù)據(jù)“11,22,33,44,55,66”，用下面的程序代碼查找數(shù)據(jù)“23”，程序執(zhí)行完畢后，下列各變量值正確的是a(1)=11:a(2)=22:a(3)=33:a(4)=44:a(5)=55:a(6)=66i=1:j=6:p=0:Key=23DoWhilei<=jp=p+1m=(i+j)\2IfjMod2=0Thenm=m+1Ifa(m)=KeyThenExitDoIfKey<a(m)Thenj=m-1Elsei=m+1LoopA．i=5 B．j=4 C．m=3 D．p=2第2題解決問題3（2017年4月選考）某對(duì)分查找算法的VB程序段如下：key=Val(Text1.Text)i=1:j=10Text2.Text=""DoWhilei<=jm=Int((i+j)/2+0.5)Ifkey=a(m)ThenExitDo'ExitDo表示退出循環(huán)Ifkey<a(m)Thenj=m-1Elsei=m+1Text2.Text=Text2.Text+Str(a(m))Loop數(shù)組元素a(1)到a(10)的值依次為“8,17,24,30,36,40,55,58,61,66”，文本框Text1中輸入的值是30，執(zhí)行該程序段，文本框Text2中顯示的是A．4024 B．402436 C．3624 D．361724第3