2023-2024学年浙教版高一下学期第二章第四节 查找

2023-2024学年浙教版高一下学期第二章第四节 查找 一、选择题 1．有如下 VB 程序段： i=1 : j=10 key=Val（Text1.Text） Do While i<j m=Fix（（i+j）/2） If key>a（m） Then i=m+1 Else j=m End If Loop 数组元素 a（1）到 a（10）依次为 2,3,7,9,9,10,13,13,13,19，如果key是数组a中的一个数，那么程序执行后正确的是（    ） A．i=j+1 B．a（i+1）=key C．i=j D．i>j 2．某对分查找算法的 VB 程序段如下: n=0:i=1:j=8   key=Val(Text1.Text) Do While i <=j   m=(i+j)\2   n=n+1   If key=d(m) Then Exit Do   If key > d(m) Then j=m-1 Else i=m+1 Loop If i<=j Then s=Str(m-n) Else s=Str(n) 数组元素 d(1)到d(8)的值依次为87，75，50，44，36，24，15，8，输入某个key值,运行该程序段后，变量s 结果为 2，则输入key的值是（    ） A．75 B．36 C．24 D．15 3．（一）顺序查找数据：我们假定被查找的数据存储在有n个元素的数组变量d中，要寻找的一个特定的数据(这个数据称为查找键)已经存储在变量key中。 下面是顺序查找算法的输入输出说明。 输入：查找键(设在变量key中)。 被查找的数据(设在数组变量d中)。 输出：若找到，输出值为key的数据所在的数组元素的下标，记为i； 若未找到，输出结果为提示字符串："找不到"。 当在n=8个元素的数组里顺序查找数据的示意图如下： 找到情况                     未找到情况 总结顺序查找数据结果判断条件： (1)、 当找到时，肯定i<="8," n个数据时，肯定i<=n，i即为找到的数组元素下标，d(i)=key； (2)、 当"找不到"时，i=9>8了；n个数据时，当i=n+1时，表示"找不到"。 顺序查找的主程序段如下： Private Sub 顺序查找_Click() n个数据放入d(1)到d(n)中 Key =" Val(Text1.Text):" i =　　1　　‘变量Key从文本框Text1取的数要查找的数； Do While ① i =" i" + 1 Loop If i <=" n" Then Text2.Text = "在d(" + Str(i) + ")中"  ‘例如在文本框Text2显示：“在d(6)中” Else Text2.Text = "找不到" End If End Sub 上程序Do While的条件 ① 是（ ） A．Key <> d（i） B．i <= n C．Key <> d(i) And i <= n D．Key <> d(i) or i <= n 4．某对分查找算法的VB程序段如下 Key =Val(Text1. Text) i=1:j=10:n=0 Do While i <=j   m= (i+j)\2   n=n+1   If a(m)>Key Then     j=m-1   Else     i=m+1   End If Loop Text2. Text = str(n) 数组元素a(1)到a(10)的值依次为“2，3，5，8，9，10，13，17，19，25”，在文本框Text1中入待查找的整数，执行该程序段，则文本框Text2中显示3，待查找数不可能是（    ） A．2 B．4 C．9 D．19 5．某对分查找算法的VB程序段如下： Key = Val(Text1. Text) n = Val(Text2. Text) i = 1:j = n Do While i < = j     m = (i+j) \2     If a(m) = Key Then Exit Do' Exit Do表示退出循环     If a(m)> Key Then j= m - 1 Else i= m+ 1 LooP 整数数组元素a(1)到a(100)为升序序列。在文本框Text1和Text2中分别输入待查找数Key及n，表示在数组a(1)~a(n)间查找数字key。输入key的值，若找不到该数，且“m=(i+j)\2”该语句执行了4次，则n值可能是（   ） A．7或8 B．5或31 C．8或30 D．6或15 6．图书管理系统对图书管理是按图书的序号从小到大进行管理的，若要查找一本已知序号的书，则能快速地查找的算法是（    ）。 A．穷举算法 B．解析算法 C．对分查找 D．冒泡排序 7．关于对分查找和顺序查找算法的叙述，正确的是（      ）。 A．顺序查找需要排序，效率低；对分查找不需要排序，效率高。 B．顺序查找不需要排序，效率低；对分查找需要排序，效率高。 C．顺序查找不需要排序，效率高；对分查找需要排序，效率低。 D．顺序查找需要排序，效率高；对分查找不需要排序，效率低。 8．有10个数据34，22，101，8，14，88，24，17，54，7依次存放在数组a(1 to 10)中，下列关于数据查找的说法中，正确的是（   ） A．数据19不在数组a(1 to 10)中，不能进行查找 B．可以直接对数组a(1 to 10)采用对分查找 C．最多经过10次比较，肯定能得出查找结论 D．顺序查找肯定比对分查找效率低 9．某对分查找算法的VB程序如下： n=0 i=1 j=6 key=val(Text1.text) f=False Do While i<=j And Not f m=(i+j+1)\2 n=n+1 If key=d(m) Then f=True ElseIf key>d(m) Then j=m-1 Else i=m+1 End if Loop 数组元素d（1）到d（6）的值依次为“87,72,53,41,29,18”，若该程段运行结束后，n的值为2，则key的值是 （  ） A．87或29 B．72或18 C．72 或 29 D．53 或 18 10．某学籍管理系统软件有2万个学生的电子档案（已按学籍号排序），假设从中取出一条记录并与待查项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一位学生档案最多花费的时间约（  ） A．10万毫秒 B．20万毫秒 C．130毫秒 D．150毫秒 11．某超市商品信息管理系统中有1万条商品资料记录(已经索引排序)，假设从中取出一条记录并与待查项进行比较所花的时间为20毫秒，则用对分法在该系统中查找任意一个指定商品最多花费的时间约为(  ) A．13毫秒 B．14毫秒 C．280毫秒 D．14万毫秒 12．某对分查找算法的VB程序段如下： Key= Val(Text1. Text) i=1: j=10 : n=0 Do While i<=j     m=(i+j)\2     n=n+1     If b(m) > Key Then         i=m+1     Else         j=m-1     End If Loop Text2. Text= str(n) 数组元素b(1)到b(10)的值依次为“25,19,17,13,10,9,8,5,3,2”。在文本框Text1中输入待查找的整数，执行该程序段后，文本框Text2中显示3，则待查找数不可能是（  ） A．19 B．9 C．4 D．2 13．【加试题】某对分查找算法的 VB 程序段如下： Key = val(text1.text)   N=0 i = 1: j = 7 flag = False Do While i <= j And flag = False n = n + 1 m = Fix((i + j) / 2) If a(m) = Key Then flag = True If Key < a(m) Then i = m + 1 Else j = m – 1    Loop If flag = True Then Text2.Text = "在第" &amp; Str(m) &amp; "个，" Else Text2.Text = "未找到，" End If 数组元素 a(1)到 a(7)的值依次为“89，72，68，45，23，19，17”。文本框 Text1 中输入 17，执 行该程序段后，下列变量的值不．正．确．的是（    ） A．n=2 B．m=7 C．i=7 D．j=6 14．有如下 VB 程序段： a(1) = 13: a(2) = 22: a(3) = 36: a(4) = 42: a(5) = 50: a(6) = 58: a(7) = 62: a(8) = 70 i = 1: j = 8: count = 0 Randomize key = Int(Rnd * 100 ) Do While i <= j   m = (i + j + 1) \ 2   If a(m) >= key Then      count = count * 2 + 1      j = m - 1   Else     count = count * 2     i = m + 1   End If Loop 执行该程序段后，count 的值不可能的是（   ） A．15 B．14 C．7 D．6 15．定义变量s表示团购价，则在窗口上显示团购价的语句应该是？（   ） A．label4.caption=str(s) B．label4.text=val(s) C．s=str(label4.caption) D．s=val(label4.caption) 二、填空题 16．现要求编写VB程序，界面如第2题-1图所示。程序功能如下：在文本框Text1中输入身份证号码，单击“识别”按钮Command1，在标签Label3中输出对应的性别。 具体方法为： （1）若身份证号为15位，则根据第15位数字来判断，若为偶数则性别“女”，否则为“男”；（2）若身份证号为18位，则根据第17位数字来判断，若为偶数时则性别为“女”，否则为“男”。应用程序界面设计时，为添加“识别”按钮，应使用2图中“控件工具箱”中的 （填写相应编号），并修改3图“属性窗口”中，将 属性值设置为“识别” 请根据题意将下列程序补充完整 Dim x As String, n As Integer, s As String x = Text1.Text n = Len(x) If n =" 15" Then s = Mid( ① , Len(x), 1) If Val(s) Mod 2 =" 0" Then Text2.Text = "女" Else Text2.Text = "男" End If Else s="Mid(x," 17, 1) If ② Then Text2.Text = "男" Else Text2.Text = "女" End If End If 17．王五为学生们设计了学校食堂学生校园卡查询系统，在终端机上输入学生的校园卡卡号，可以查出该卡对应的学生姓名及相应的余额。 校园卡信息存储在一个综合的数据库“school.mdb”,其中的“Yue”数据表用来存储学生的校园卡基本信息，包括学号（num）、姓名（name）、余额（money）,括号内的为对应字段名。下列VB程序用来实现根据学号查询并显示学生姓名及余额，运行界面如图所示： 数据库文件与应用程序在同一文件夹中，在文本框Text1中输入学生的学号，单击“查询”按钮，在标签Label4、Label5中分别显示学生姓名和余额。 Private Sub Command1_Click() Dim adocn As new connection Dim adors As new recordeset Dim str1 As string,str2 as string Str1="”driver=microsoft" access driver(*.mdb);dbq=”&amp;app.path&amp;”\ � .mdb” Adon.open str1 Str2="”select" * from Yue where � =’”+text1.text+”’” Adors.open str2,adocn,adOpenDynamic,adLockOptimistic If adors.eof then Msgbox”你输入的学号不存在!” Else Label4. caption =adors.Fields(“name”).value � =adors.Fields(“money”).value Endif Adors.close Adocn.close End Sub 为了实现上述目标，在画线处填入合适的语句或表达式： � � � 18．下面程序的功能是：找出10以内的奇数中能被3整除的正整数，并将它们累加起来。为了实现这一目标，程序中划线处的语句应更正为______ __________ X=0 For i=1  to 10 step 2 If i mod 2=0 then x=x+i Next i 19．下列程序的功能是在text1中输入的自然数，分解为3个互不相同的质数（三个质数的和等于输入的自然数），并把分解产生的质数按升序顺序显示在左边的列表框中。例如，输入20，那么在列表框中会显示如右图所示结果。其中，上述界面中“开始处理”按钮的名称是“Command1”，程序中函数f(x)的功能是判断x是否为质数，如果是质数则返回值为true，否则返回false。 请在下列程序代码的基础上按照要求设计该程序,完善程序中的划线部分。 Dim n As Integer, a1 As Integer, a2 As Integer, a3 As Integer Function f(x) As Boolean f = True For i =" 2" To Sqr(x) If x Mod i =" 0" Then ___________ Next i End Function Private Sub Command1_Click() n = ________________ For a1 =" 2" To n For a2 =" a1" To n For a3 =" a2" To n If _________________ And f(a1) And f(a2) And f(a3) Then List1.AddItem (Str(a1) + " " + Str(a2) + " " + Str(a3)) End If Next a3 Next a2 Next a1 End Sub 20．常用的查找算法有顺序查找和对分查找，使用对分查找时速度要快得多，但待查找的数据必须是 。 三、操作题 21．编写一个删除数字字符串s中的最大和次大数字字符的程序。具体功能如下：在文本框Text1中输入一个数字字符串，单击“删数”按钮Command1，将删除后的结果显示在文本框Text2中。程序运行界面如下图所示。 （1）要使程序运行时，按钮Command1上显示的标题为“删数”，可在Form_Load事件处理过程中添加语句 （单选,填字母： A．Caption.Command1 ="删数" / B．Command1.Caption ="删数" / C．Caption ="删数"/） （2）实现上述功能的VB程序如下，请在划线处填入合适的代码。 Private Sub Command1_Click()   Dim s As String, ch As String   Dim i As Integer, n As Integer   Dim max1 As Integer, max2 As Integer   s = Text1.Text: n = Len(Text1.Text)   If Mid(s, 1, 1) > Mid(s, 2, 1) Then     max1 = 1: max2 = 2   Else     max1 = 2: max2 = 1   End If   For i = 3 To n    ch = Mid(s, i, 1)    If ch > Mid(s, max1, 1) Then      ①      max1 = i    ElseIf ch >= Mid(s, max2, 1) Then      max2 = i    End If   Next i   For i = 1 To n     If ② Then Text2.Text = Text2.Text &amp; Mid(s, i, 1)   Next i End Sub （3）若在文本框Text1中输入的内容为“82176736”，单击按钮Command1,文本框Text2中显示的内容是 。 22．把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。 数组元素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．C 2．B 3．C 4．D 5．C 6．C 7．B 8．C 9．B 10．D 11．C 12．D 13．A 14．C 15．A 16．（1）3（1分） Caption（1分） （2）x（1分）   val(s) mod 2 =1（1分） 17．（1）school（1分）  （2）num（1分）  （3）Label5.caption（1分） 18．i mod 3=0 19．（1）f=False（1分） （2）Val(Text1.Text)（1分） （3）a1+a2+a3=n（1分） 20．有序的 21． B max2 = max1 i <> max1 And i <> max2或其它等价的答案 217636 22．（1）B （2）R-L=1 （3）inorder(L,R) （4）C 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$