第四节 查找-2023-2024学年高一信息技术浙教版选修1

第四节 查找 一、选择题 1．数组a为一组已按降序排序的正整数，依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下： Dim a(1 To 6) As Integer Const n = 6 a(1) = 98: a(2) = 96: a(3) = 95 a(4) = 90: a(5) = 87: a(6) = 81 i = 1: j = n Key = Val(Text1.Text) f = False Do While And f = False     m = (i + j) \ 2     If a(m) = Key Then         Text1.Text = “已找到”: f = True     ElseIf a(m) > Key Then     Else              End If Loop 上述程序中方框(1)(2)(3)处语句依次为（   ） A．i <= j      i = m + 1   j = m - 1 B．i <= j      j = m - 1   i = m + 1 C．i < j      j = m - 1   i = m + 1 D．i < j      i = m + 1   j = m - 1 2．萧明申请了一个网银账号，登录网银账号时要输入密码。如果密码输入的错误次数超过3次，那么当日网银账号将被锁定，次日自动解锁。下图是登录网银的流程图，萧明不小心输入密码错误了2次，第3次才正确，那么他的操作流程应该是（ ） A．①→②→③→①→②→③→①→②→③→④→⑤ B．①→②→③→①→②→③→④→⑤ C．①→②→③→④→⑤ D．①→②→③→④→⑤→⑥ 3．下列关于程序设计中查找算法的描述，正确的是（       ） A．顺序查找和二分法查找都是常用的查找算法 B．二分法查找一定优于顺序查找 C．顺序查找一定优于二分法查找 D．当数据有序时，不适用二分法查找 4．某算法的VB程序段如下： key = Int (Rnd *5)*2+ 11 i = 1:j = 8:c = 0 Do While i <= j m = (i+j+1) \ 2 If a(m) >= key Then i = m+1 EIse j = m-1 c = c+1 Loop 数组元素a(1)到a(8)的值依次为“23，21，19，18，16，15，14，11”。若该程序段执行后，下列说法错误的是（   ） A．i 的值为j+1 B．i 的值可能是9 C．j 的值可能是5 D．c 的值一定是3 5．某对分查找算法的VB程序段如下: key=Int(Rnd*20)+3 i=1:j=6:id=1 Do While i<=j     m=(i+j)\2     If key=a(m)Then Exit Do     If key〈a(m)Then         j=m-1:id=id*2     Else         i=m+1:id=id*2+1     End If Loop Labe11. Caption=Str(id) 数组元素a（1）到a（6）的值依次为“4，7，9，14，15，21”，执行该程序段后，标签Labell中显示的内容不可能的是（   ） A．4 B．7 C．13 D．15 6．某一算法的流程图如第9题图所示，则该算法的功能是(    ) A．求三个数中最大的数 B．求三个数中最小的数 C．将三个数从小到大排列 D．将三个数从大到小排列 7．已知一无序数组a中的元素为“90，15，40，72，65，32，81，6”，通过引入数组b存储数组a元素按升序排列时的下标，b数组元素为“8，2，6，3，5，4，7，1”，使得a(b(1))≤a(b(2))≤a(b(3))……≤a(b(n))，从而对a数组中的数据进行对分查找。部分程序如下：    i＝1:j＝8:c＝0     key＝Val(Text1.Text）     Do While i＜＝j        m＝Int((i+j)/2)        t＝b(m)        c＝c+1        If a(t)＝key Then p＝t:Exit Do        If a(t)＜key Then            i＝m+1        Else           j＝m-1        End If     Loop     当文本框Text1中输入的值为32时，程序运行结束后变量c的值为（   ） A．1 B．2 C．3 D．4 8．数组a中存放了某校田径运动会中7名100米短跑运动员的成绩，数据存放情况如下表： a(1) a(2) a(3) a(4) a(5) a(6) a(7) 12.1 12.3 12.6 12.8 13.0 13.3 13.5 若用对分查找算法查找数值 13.5，则第 2 次查找到的数组元素的下标是（ ）。 A．2 B．5 C．6 D．7 9．二分查找又称折半直找，是种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（  ） A．1，4，7，15，13 B．15，14，12，7，2，3 C．34，25，17，9，10，3 D．6，9，12，14，23，25 10．如下图所示的链表： 假如要查找元素11，共需遍历的次数为（   ） A．5 B．6 C．7 D．8 11．有如下 VB 程序 a(1) = 1 For i = 2 To 12 a(i) = a(i - 1) + Int(Rnd * 2) + 1   Next i Key = Val(Text1.Text) i = 1: j = 12: cnt = 1: flag = False   Do While i <= j And flag = False cnt = cnt + 1 m = (i + j + 1) \ 2   If a(m) = Key Then flag = True ElseIf Key > a(m) Then i = m + 1 Else j = m - 1  End If Loop 程序运行后，下列说法正确的是(    ) A．在Text1输入15，程序运行后m肯定为 12 B．在Text1输入6，程序运行后 cnt可能大于4 C．若查找不成功，则 j>m肯定成立 D．若查找不成功，则 i<=m 肯定成立 12．某对分查找算法的VB程序段如下： i=1:j=8:s=0: key= Int(Rnd * 45)*2+5 Do While i<= j     m=(i+j)\2     If key = a(m) Then         Exit Do     EseIf key < a(m) Then         j=m-1:s=s-1     EIse     i=m+1:s=s+ 1     End If Loop 已知数组元素a(1)到a(8)的值依次为5，16，20，28，44，55，67，85，执行该程序段后，s的值不可能是（    ） A．0 B．-2 C．3 D．-1 13．数组a中存放了一批数据如下表，现采用对分查找方式在这批数据中查找“gou”，以下说法正确的是（   ）。 a(1) a(2) a(3) a(4) a(5) a(6) a(7) hou ji long ma niu she tu A．依次被比较的数据是“ma”，“ji”，“hou” B．依次被比较的数据是“ma”，“she”，“tu” C．无法进行对分查找，因为这批数据还没排好序 D．无法进行查找操作，因为这批数据中没有“gou” 14．用对分查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是（  ） A．2 B．4 C．3 D．7 15．有100个大小形状一样的透明玻璃球，其中有1个玻璃球的重量轻于其他99个玻璃球，小明想利用一台无砝码的天平，运用合理的算法保证一定能找出这颗轻玻璃球的最少的次数为：（ ） A．100 B．10 C．8 D．6 二、填空题 16．依照中华人民共和国《机动车驾驶员驾车时血液中酒精含量规定》，血液中酒精含量大于或等0.3mg/ml 驾驶机动车的属酒后驾车；大于或等于1.0mg/ml 驾驶机动车的属醉酒驾车。设计一个程序，帮助交警判定某人属酒后驾车、醉酒驾车还是没有违法。 解决此问题的流程图如图所示， （1）该算法属于 （填：顺序/选择/循环）结构 （2）要在窗体Form1的标题栏内显示字符串“酒精测试”，需要更改的是 属性（填：name/caption/text） （3）根据流程图编写的VB程序如下： Private Sub Command1_Click( ) Dim x As Single x =  Val(Text1.Text)   If ① Then Label2.Caption = "你属于醉酒驾车!" ② x >=" 0.3" Then Label2.Caption = "你属于酒后驾车!" Else ③ End If    End Sub 则划线处填入的语句为① ② ③ 。 17．递增数列用二分法查找时，先以 位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列 为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。 18．下面程序的功能是：找出10以内的奇数中能被3整除的正整数，并将它们累加起来。为了实现这一目标，程序中划线处的语句应更正为______ __________ X=0 For i=1  to 10 step 2 If i mod 2=0 then x=x+i Next i 三、判断题 19．基于链表的数据结构，可以从以下两方面来优化查找效率：①减少查找插入位置过程中的比较次数；②借鉴二分查找算法的思想。( ) 四、操作题 20．把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。 数组元素a(1)至a(5)依次为5，22，28，42，55，在a(3)处分成两段，交换位置后为： a(1) a(2) a(3) a(4) a(5) 28 42 55 5 22 旋转数组a的最小元素是5。 数组d(1)至d(5)依次为0，1，1，1，1，在d(5)处分成两段，交换位置后为： d(1) d(2) d(3) d(4) d(5) 1 0 1 1 1 旋转数组d的最小元素是0。 小明依据查找算法思想，设计一个查找旋转数组d最小元素的程序，功能如下：运行程序时，利用“添加”按钮Command1和文本框Text1依次输入旋转数组d的值，在列表List1中显示旋转数组，单击“求解”按钮Command2，在标签Label2中显示旋转数组d最小元素值。运行效果图所示，实现该功能的的VB程序如下。 (1)要使程序运行时，文本框Text1无显示内容，下列方法不能实现该要求的是_______（单选，填字母：A．在Form_Load事件处理过程中添加语句“Text1.Text=""”/B．在Command1_Click事件处理过程中添加语句“Text1.Text=""”/C．设计程序界面时，在属性面板设置文本框Text1的Text属性值为空） (2)程序代码中，加框处有错，请改正。 (3)程序代码中，将划线处代码补充完整。 (4)程序代码中，虚线框内自定义函数中主要采用的算法是__________(单选，填字母：A．冒泡排序/B．选择排序/C．顺序查找/D．对分查找)。 Dim n As Integer Dim d(1 To 100) As Integer '数组 d 存储待排序数据 Private Sub Command1_Click() '按旋转数组规则将数据存入数组d中，代码略 End Sub Private Sub Command2_Click()   Dim mid As Integer, L As Integer, R As Integer   L = 1: R = n   mid = L   Do While d(L) >= d(R)     If L=R Then'改错       mid = R       Exit Do     End If     mid = (L + R) \ 2     If d(L)=d(R) And d(mid)=d(R) Then mid =______________                              '填空       Exit Do     End If     If d(L) < d(mid) Then       L = mid ElseIf d(mid) < d(R) Then       R = mid     End If   Loop Label2.Caption = "最小值为" + Str(d(mid)) End Sub     End If   Next i End Function 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 2．A 3．A 4．C 5．C 6．B 7．C 8．C 9．D 10．B 11．B 12．A 13．A 14．B 15．D 16．（1）选择；（2）caption；（3）①x＞＝1；②elseif；③label2.caption＝“恭喜你没有违法” 17． 中点 缩小 18．i mod 3=0 19．正确 20．（1）B （2）R-L=1 （3）inorder(L,R) （4）C 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$