查找算法的程序实现「教师版」

查找算法程序实现教师版
例1 数组元素a(1)a(8)中查找键值key数序查找VB程序段请划线处填写正确语句
for i1 to 8
if ①　　　　　　　　then 
　　Text1textstr(i)
　　exit for
end if
next i
if ②　　　　　　　　then 
text1text″数组中没找″+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结束查找没找keyi值必定8划线①处条件表达式a(i)key划线②处条件表达式i>8
例2某数组6元素次273257788090该数组进行序查找均查找次数(1+2+3+4+5+6)672该数组进行分查找均查找次数 (　　)
A72 B73
C52 D2
答案：D
分查找进行[log2N]+1次查找N6进行2次查找
例3某分查找算法VB程序段
i1j8c0
Do While icc+1
mFix((i+j)2)
If keyb(m) Then Exit Do
If keyLoop
数组元素b(1)b(8)值次22323948718296106该程序段运行结束c值2key值(　　)
A4832 B4896
C3282 D8296
答案：C
解析：程序采分查找算法变量c表示查找次数第次查找值48第二次查找值3282二叉树方法考虑问题图示节点中数字表示元素编号节点第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程序段
i1j10
KeyVal(Text1Text)
Do While im(i+j)＼2
If a(m)Key Then Exit Do　＇Exit Do 表示退出循环
If Key Mod 21 And a(m) Mod 20 Then
　　　　(1) 
ElseIf Key Mod 20 And a(m) Mod 21 Then
　　　　(2) 
Else
　　　　(3) 
End If
Loop
If i>j Then s″没找″ Else s″位置″+Str(m)
Text2Texts
述程序中划线处选语句
①im+1
②jm1
③If Key(1)(2)(3)处语句次(　　)
A①②③ B①③②
C②①③ D③②①
答案：C
解析：果key奇数查找区间中间偶数前半段查找(半段肯定偶数)jm1否果key偶数查找区间中间奇数半段查找(前半段肯定奇数)im+1否纯偶数升序列中找偶数纯奇数升序列中找奇数正常分查找If Key强化训练
1数组a中存放着已排序n1实验数(a(1)≥a(2)≥……≥a(n1)a(n)暂未存储数)现文框Text1中输入新数插入数组a中相应位置n数保持序完成该功VB程序段请划线处填入正确语句
xVal(Text1Text)
iljnl
Do While im(i+j)＼2
If xLoop
For kn To 　①　 Step1 
a(k)a(k1)
Next k
a(i)x
答案 i+1j+2
解析 程序中通分查找法找插入位置该位置i需a(n1)a(n2)……a(i)次移位置相位置加1然x存入a(i)中该位置j+2
2某分查找算法VB程序段
n0i1j6
KeyVal(Text1Text)
Do While im(i+j)＼2
nn+1
If Keyd(m) Then Exit Do
If Key>d(m) Then jm1 Else im+1
Loop
If id(1)d(6)值次887753473928输入某Key值运行该程序段变量s结果1输入key值(　　)
　　　　　　　　　　　　　　
A89 B77 C47 D39
答案 C
解析 程序采分查找算法代码果sn1需满足i>j需查找key数组中仅查找1次满足该条件smn1查找3次满足题二叉树方法解决图示节点中数字表示元素编号节点第n层表示找该数n次满足mn1中点值查找次数1图知a(4)满足条件

3某分査找算法VB程序段
i 1j 7s ″ ″
key Int(Rnd * 100)
Do While i < j
m (i + j) ＼ 2
If key a(m) Then
s s + ″M″Exit Do　　＇Exit Do表示退出循环
ElseIf key < a(m) Then
j m1s s + ″L″
Else
i m + 1s s + ″R″
End If
Loop
Text1Text s
数组元素a(1)a(9)值次24353841456978该程序段执行文框Text1中显示容(　　)
ARL BLMR CRLR DLRLM
答案 C
解析 分析程序知查找成功会输出″M″循环结束 M 中间排B 选项 n 数查找查找次数 Log2n+1(取整)7 元素查找 3 次排 D 选项果法找(输出″M″)需查找 3 次查找次数选C
4数组a中存储左右交升n正整数表示：
a(1)
a(2)
a(3)
……
a(n－2)
a(n－1)
a(n)
3
25
38
……
55
31
12
分查找思想设计数组a中查找数key程序实现该功VB程序加框处代码错请改正
Private Sub Command1_Click( )
Const n＝6
Dim a(1 To n) As Integerflag As Boolean
Dim i As Integerj As Integerm As Integerkey As Integer
′读取组正整数述规存入数组a中代码略
key＝Val (Text1Text)
i＝1
j＝(n＋1)＼2
flagTrue
Do While And Not flag′(1)
m＝(i＋j)＼2
If keya(m) Then
flagTrue
ElseIf key＜a(m) Then
jm1
Else
im+1
End If
Loop
If Not flag And j＞0 Then
m′(2)
If key＝a(m) Then flag＝True
End If
If flag Then
Text2Text＝Str(m)
Else
Text2Text＝找
End If
End Sub
中加框(1)处应改正________
加框(2)处应改正________
解析　题考核分查找思想算法较简单关键数组a中存储左右交升n正整数理解数组前半部分递增半部分递减变化规律3→12→25→31→38→55果前半部分找右半部分称位置找(1)应修改i<＝j说次查找变量i＝j＝m果前半部分找该数a(m)时j＝m－1该数(j)a(m)j称位置(n－j＋1)找数该数a(m)时i＝m＋1该数a(m)a(i)(i－1)称位置(n－(i－1)＋1)找数
答案　(1)i＜＝j
(2)n－i＋2
n－j＋1
n＋1－(i＋j)＼2
等价表达式
5)数组a组正整数奇数前偶数奇数偶数已分升序排序分查找思想：设计数组a中查找数Key程序实现该功VB程序段：
i＝1∶j＝10
Key＝Val(Text1Text)
Do While i<＝j
　m＝(i＋j)＼2
　If a(m)＝Key Then Exit Do　′Exit Do表示退出循环
　If Key Mod 2＝1 And a(m) Mod 2＝0 Then

　ElseIf Key Mod 2＝0 And a(m) Mod 2＝1 Then

　Else

　End If
Loop
If i>j Then s＝没找　Else s＝位置：＋Str(m)
Text2Text＝s
述程序中方框处选语句：
①i＝m＋1
②j＝m－1
③If Key(1)(2)(3)处语句次(　　)
A①②③ B①③②
C②①③ D③②①
解析　题考核分查找算法基思想语句Key Mod 2＝1 And a(m) Mod 2＝0表示查找key奇数m指数偶数奇数前前找移动尾指针语句Key Mod 2＝0 And a(m) Mod 2＝1表示查找key偶数m指数奇数
答案　C
6采分查找算法数组a中7序数15385166778199进行查找查找数55
i＝1∶j＝7∶x＝55
Do While i＜＝j
　m＝(i＋j)＼2
If a(m)＝x Then Exit Do
If a(m)＞x Then j＝m－1 Else i＝m＋1
Loop
述代码查找列表述正确(　　)
Ai＝m＋1 Bi＝m－1
Cj＞m＋1 Dj＜m－1
解析　题分查找算法程序分析程序运行程中变量变化情况：
查找次数
变量i
变量j
变量m
a(m)
第1次查找
1
7
4
66
第2次查找
1
3
2
38
第3次查找
3
3
3
51
退出循环
4
3


3次查找i＝4j＝3i＞j退出循环根时变量值判断A正确
答案　A
7某学校图书理系统中10万条图书资料记录(已索引排序)假设中取出条记录查找项进行较花时间10毫秒分法该系统中查找意指定图书花费时间约(　　)
A100万毫秒 B50万毫秒
C10毫秒 D170毫秒
解析　分查找查找效率较高否找进行Int(log2n)＋1次查找表示等log2n＋1整数
n＝100000较次数17次花费时间170毫秒
答案　D
8VB程序查找单词间距文框Text1中输入段英文文框Text2中输入英文段落中某单词(字符串)单击间距钮(Command1)文框Text3中显示该单词文中某两次出现间距出现次出现显示值0程序运行界面图示

实现述功VB程序请划线处填入正确代码
Private Sub Command1_Click()
Dim a(1 To 1000)As String　＇数组a存储文中出现该指定单词(字符串)位置
Dim s As Stringc As Stringch As String
Dim n As Integermax As Integeri As Integer
sText1Text
cText2Text
n0∶Max0
For i1 To Len(s)Len(c)+1
ch　①　 
If chc Then
nn+1
　②　 
If n>2 Then
　　If a(n)a(n1)Len(c)>Max Then Maxa(n)a(n1)Len(c)
End If
End If
Next i
Text3Textstr(max)
End Sub
答案 ①mid(silen(c))　②a(n)i
解析 程序采序查找算法查找单词c输入英文总长度len(s)查单词长度len(c)循环查找第1字符开始次截取len(c)字符查单词致记录数出现位置出现位置存入数组a(n)i果找22相字符储存间距较间距值Max①处应段英文s中第i字符开始截取len(c)字符mid(silen(c))
9某排序算法VB程序段：
For i＝7 To 5 Step －1
k＝i
For j＝1 To i－1
If a(j) Next j
If i<>k Then
t＝a(i)：a(i)＝a(k)：a(k)＝t
End If
Next i
数组元素a(1)a(7)数次10417512631185排序加工数组元素a(1)a(7)数次(　　)
A85417563121110
B85756341121110
C10111263754185
D10111241637585
解析　选择排序变形i＝7时k＝ik指数前面6数进行较k指前面较数交换第轮1085互换
i＝6时k＝ik指数前面5数进行较k指前面较数交换第二轮没交换i＝5时k＝ik指数前面4数进行较k指前面较数交换第三轮1263交换
答案　A
10双选择排序算法典选择排序基础果选择出数时选择预见数两数放置合适位置样排序效率提高倍述双选择排序算法张编写VB程序功：列表框List中显示排序前数单击排序钮Command1列表框List中显示数升序排序结果运行效果图示

实现述功VB程序加框处代码错请改正
Const n＝10
Dim b(1 To n)As Integer
Private Sub command1_Click( )
Dim i As Integer
Dim t As Integer
For i＝1 To 　′①
　For j＝i To 　′②
If b(j) 　t＝b(i)：b(i)＝b(j)：b(j)＝t
End If
If b(j)>b(n－i＋1) Then
　t＝b(j)：b(j)＝b(n－i＋1)：b(n－i＋1)＝t
End If
Next j
Next i
For i＝1 To n
　List2AddItem Str(b(i))
Next i
End Sub
Private Sub Form_Load( )
For i＝1 To 10
　b(i)＝1＋Int(Rnd*100)
　List1AddItem Str(b(i))
Next i
End Sub
解析　次找出两值较趟数总数半次实现头尾序i相数n－i＋1
答案　n＼2 ni+1
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档