高中信息技术粤教版(2019)选修一 5.2查找

高中信息技术粤教版(2019)5.2查找 一、选择题 1．某算法的VB程序段如下： key=randint（0，3）*2+13 i，j，c=0，len（a）–1，0 while i<=j： m=（i+j+1）//2 if a［m］>=key： i=m+1 else： j=m-1 c+=1 列表a=［23，21，19，18，16，15，14，11］，该程序段执行后，下列说法不正确的是（   ） A．i的值为j+1 B．i的值可能是8 C．j的值可能是5 D．c的值一定是3 2．有如下VB程序段： i =1:j= 6:n =o :Key = Val(Text1.Text) Do While i<= j m = (i+j) \ 2 n = n＋1 If Key > a(m) Then j = m- 1 Else i = m ＋1 Loop a(1)到a(6)的值依次为“99，77，55，44，33，22”，下列说法正确的是（   ） A．数组a中的元素若无序，也可用此程序段进行查找某个数字 B．无论key值是多少，循环结束后“i >j”一定成立 C．如果key值为55，那么该程序段运行后，变量n的值为1 D．如果key值为40，那么该程序段运行后，变量m的值为5 3．数组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 4．某对分查找算法如下： i=1:j=6:c=1 key=int（rnd*100+1） do while i <= j m=（i+j）\2 c=c+1 if key<d（m）then j=m-1 else i=m+1 1oop 数组d（1）~d（6）的值分别为“17，21，29，32，39，75”，则程序运行结束后，下列说法错误的是（    ） A．i=j+1是成立的 B．若key=21，则i=1 C．当key=32时，m=j是成立的 D．若key如果是38，那么m=4 5．有如下 VB 程序段： s = "" low = 1: high = 8 Key = Text1.Text Do While low <= high     m = (low + high) \ 2     If a(m) < Key Then        high = m - 1     Else        low = m + 1        s = s + Str(low)     End If Loop 数组元素 a(1)到 a(8)的值依次为“27,25,20,15,12,8,6,5”。该程序段执行后s的值为“5,6”， Text1 中输入待查找数可能是（    ） A．8 B．7 C．12 D．14 6．二分法查找又称为折半查找，是常用的查找算法之一。关于二分查找，下列说法错误的是（    ） A．二分查找要求被查找的数据是有序的 B．二分查找要求被查找的数据必须是数值型数据 C．二分查找算法的时间复杂度为log2n D．二分查找实际上就是分治策略的一种典型运用 7．7位幼儿园小朋友的体重(单位kg)从低到高依次为：13，15，16，18，20，21，23。用对分查找法找到23的过程中，依次被访问到的数据是(  ) A．23 B．18，21，23 C．18，23 D．18，20，21，23 8．数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”，文本框Text1中输入的值是33，执行该程序段，下列描述正确的是（    ） key = Val(Text1.Text) i = 0: j = 9: s = 0 Do While i <= j m = Fix((i + j) \ 2 + 0.5) s = s + 1 If key = a(m) Then Label1.Caption = Label1.Caption + "→" + Str(m) Exit Do                    'Exit Do表示退出循环 End If If key < a(m) Then j = m - 1 Else i = m + 1 Label1.Caption = Label1.Caption + "→" + Str(m) Loop Label2.Caption = "历经" + CStr(s) + "步" A．标签Label1显示内容为“→4→7→5” B．标签Label2显示内容为“历经1步” C．该程序为顺序查找，查找次数为3 D．该程序为对分查找，查找次数为4 9．数组 a 中存放了某校田径运动会中 7 名 100 米短跑运动员的成绩，数据存放情况如下表： 若用对分查找算法查找数值 13.5，则第 2 次查找到的数组元素的下标是（   ）。 A．2 B．5 C．6 D．7 10．数据1~1000升序排列，若用二分查找其中的某个数，最多需要查找的次数为（  ） A．3 B．10 C．100 D．500 11．已知一元二次函数 f（x）=在区间[0，1]之间必定存在着一个极大点x0，使 f（x0）达到最大值。现用对分查找算法搜索x0的值，开始搜索区间为[0，1]，在搜索到第 n 次时找到x0，已知第n次搜索区间的长度是1/32，则 n 的值是（    ） A．3 B．4 C．5 D．6 12．有如下Python程序段： d=[1，3，8，15，22，26，28，40，46，61，80] i=0；j=len(d)-1 while i<=j：    m=(i+j)//2    if key < d[m]：       j=m-1    else： 若key值为22，程序运行结束后，加框处语句执行的次数为（   ） A．1 B．2 C．3 D．4 13．以下是依据对分查找思想,设计的一个三分查找程序。已知数组a(1 To 10)中的数据分别是12、21、34、45、59、63、72、86、94、100,当在文本框Text1中输入“34”时,输出“34”的位置值“3”,当输入“33”时,输出“33”邻近数的位置值“23”。实现该功能的VB程序段如下: Key = Val (Text1. Text) i=1 : j=10 flag = False Do While i < = j And Not flag mid1= Int (i + (j-i) /3) mid2= Int (j - (j-i) /3) If Key = a(mid1) Or Key = a (mid2) Then flag = True ElseIf Key < a (mid1) Then ______(1)______ ElseIf Key > a (mid2) Then ______(2)_______ El se i=mid1 + 1 j=mid2 - 1 End If Loop If _______(3)_______ Then List2. AddItem Str (mid1) ElseIf flag Then List2. AddItem Str (mid2) Else List2. AddItem Str(j) + Str (i) End If 上述程序中方框处可选语句为 ①i=mid1+1;② i=mid2+1;③ j=mid1-1;④ j=mid2-1;⑤ Key=a(mid1);⑥ flag And Key=a(mid1),则(1)、(2)、(3)处语句依次是（   ） A．④②⑤ B．③②⑥ C．②③⑥ D．④③⑤ 14．某对分查找算法如下 i=1:j=1000:p=0:n=1000 Key=val(textl. text) Do while i＜j m=(i+j)\2 p=p+1 If a(m)>key then j=m-1 else i=m+1 Loop Text2.text=str(n-i+1) 数组元素a（1）到a（1000）中存放的升序排列数据，下列说法正确的是（    ） A．若key的值小于a（1），则执行该段程序后，变量i的值等于0 B．若key的值大于a（1000），则执行该段程序后，变量i的值等于1001 C．若key的值等于a（1），则执行该程序后，变量p的值等于10 D．在文本框Text2中输出大于key的数据个数 15．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，需要（   ）次比较后才能查找成功。 A．4 B．1 C．2 D．8 二、填空题 16．有一维数组1、2、3、4、5，依次按照某一线性存储，请回答以下问题： （1）如果该线性结构是队列，写出出队序列。 （2）如果该线性结构是栈，输出序列可能是4、3、5、1、2吗？为什么？ （3）在一维数组A中有5个元素：8、12、20、25、33，采用二分查找25，请写出每次查找的过程？ 三、操作题 17．编写VB程序，实现如下功能：在文本框Text1中输入一个整数，单击“查找删除”按钮Command1，采用对分查找法在数组A(从小到大排列，并显示在标签Label1中)中查找该数。若找到，则从数组A中删除该数(该数后面的数组元素都前移一位)，并在标签Label2中显示删除后的结果(运行效果如图所示)；否则，在标签Label2中显示“该数没有找到”。 实现上述功能的VB代码如下，请在划线处填入适当的语句： Dim A(1 To 10) As Integer ’用于保存10个按从小到大顺序排列的整数 ’Form_Load事件过程产生10个整数，按升序保存在数组A中，并在标签Label1中显示Private Sub Form_Load() ’代码略 End Sub Private Sub Command1_Click() Dim i As Integer，j As Integer，m As Integer，k As Integer Dim x As Integer，f As Boolean  ’变量f用于标记是否在数组中找到x x＝Val(Text1.Text) i＝1：j＝10 f＝False Do While(i＜＝j)And (f＝False) m＝Int((i＋j)/2) If A(m)＝x Then f＝True If （1） Then i＝m＋1 Else j＝m－1 Loop If f＝True Then For k＝m To 9 （2） Next k Label2.Caption＝“” For k＝1 To 9 Label2.Caption＝Label2.Caption＋Str(A(k))＋“” Next k Else Label2.Caption＝“该数没有找到” End If End Sub 18．程序设计：唐三藏又被妖怪抓走了，这次孙悟空还是没打得过妖怪，于是来求观音菩萨。观音菩萨告诉孙悟空，在天庭里身高正好为1000米的那位神仙可以降伏此妖。于是悟空立刻来到天上，在玉皇大帝的神仙册上看到了按身高从矮到高排列有10000个神仙。由于时间紧迫，悟空想用最短的时间找到这位神仙，这样才可以尽快解救唐僧。 代码如下： List＝list(map(int，input(“请按身高递增顺序依次输入10000个神仙的身高”).split())) left＝1 right＝10000 while ① mid＝ ② if List[mid]＝＝1000: ③ elif List[mid]＜1000: ④ else: ⑤ print(“能帮孙悟空的神仙在第｛0｝位上”.format(mid＋l)) （1）程序代码中①处正确的代码是( )。 A．left＜right      B．left＜＝right    C． left!＝right     D．left＞right （2）程序代码中②处正确的代码是( )。 A．(left＋right)/2    B．(left＋right)\2 C．(left＋right)//2    D．(left＋right)\\2 （3）程序代码中③处正确的代码是( )。 A．pass           B．print(mid)z      C． break         D．continue （4）程序代码中④处正确的代码是( )。- A．left＝mid       B．right＝mid     C． left＝mid＋1    D．right＝mid-1 （5）程序代码中⑤处正确的代码是( )。 A．left＝mid       B．right＝mid     C． left＝mid＋1    D．right＝mid-1 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 2．B 3．A 4．B 5．C 6．B 7．B 8．A 9．C 10．B 11．D 12．C 13．B 14．D 15．A 16． 1、2、3、4、5 不可能，因为：4是第一出栈字符，说明1,2已别压入栈内；并且压入栈的次序为12345;由以上得出：12出栈的顺序只能是2、1，而不是1、2。所以，出栈序列4,3,5,1,2是不可能的 第一次查找，找到的元素为20，此时20小于目标数，所以在列表的后半部分查找，第二次查找到的元素为25，此时找到，所以共需要两次找到 17．(1)A(m)＜x (2)A(k)＝A(k＋1) 18． B C C C D 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$