2023-2024学年浙教版高一下学期第五章第三节 排序算法的程序实现

2023-2024学年浙教版高一下学期第五章第三节 排序算法的程序实现 一、选择题 1．a(1)=17:a(2)=16:a(3)=12:a(4)=18:a(5)=15:a(6)=13:a(7)=17:a(8)=20 i=2 Do While i <=8     If  i mod 2=0 and a(i)>a(i-1)then         t=a(i):a(i)=a(i-1):a(i-1)=t     Else  If  a(i-1) mod  2=1 then         a(i-1)=a(i-1)+1     End If     i=i+1 Loop 执行程序后，a数组各元素是（    ） A．17，16，18，12，16，14，20，18 B．18，16，18，12，16，14，20，17 C．16，17，18，12，13，16，20，17 D．18，16，18，12，14，15，17，20 2．编写程序，实现功能：通过双向排序，使数组元素a（1）到a（n）升序排列。 Const n =10 Dim a（1 To n）As Integer ’随机生成10个1-100之间的数存储在数组a中，代码略 For i=1 to n\2 For j=（1）To i+1 Step-1 If a（j）<a（j-1）Then t = a（j）：a（j）=a（j-1）：a（j-1）=t Next j For k=i+1 To （2） If a（k）>a（k +1）Then t =a（k）：a（k）= a（k +1）：a（k+1）=t Next k Next i 划线处可选代码为： ①2            ②n-i+1            ③n                ④n-i 则（1）、（2）处语句依次为（    ） A．①③ B．③① C．②④ D．③② 3．有如下程序段： s = 0 For i = 1 To 5 If a(i) Mod 2 = 1 Then s = s+1 Next i For i = i To 4 If a(i) Mod 2 = 0 Then For j = 5 To i + 1 Step-1 If a(j)Mod 2 = 1 Then a(6)= a(i):a(i)= a(j):a(j)= a(6) Exit For End If Next j End If Next i For I = s+2 To 5 k = i-1 For j = i To 5 If a(k)> a(j)Then k = j Next j If k <> i-1 Then a(6)= a(i-1):a(i-1)= a(k):a(k)= a(6) End If Next i 数组a(1)至a(5)中的数据分别为64，57，22，96，71，运行该程序段，数组a中数据依次为（    ） A．22，57，64，71，96 B．71，57，22，96，64 C．71，57，22，64，96 D．57，71，22，64，96 4．有如下VB程序： n = 7 For i = 1 To n \ 2 For j = n - i + 1 To i + 1 Step -1 If a(j) Mod 10 > a(j – 1) Mod 10 Then t = a(j): a(j) = a(j – 1): a(j – 1) = t End If Next j Next i 已知a(1)到a(7)各元素初值分别是31、22、73、 54、 85、26、 37，运行上述程序后，a(1)到a(7) 各元素的值分别是 A．85、73、54、31、22、37、26 B．37、26、22、31、54、73、85 C．37、85、73、31、22、54、26 D．26、54、22、31、73、85、37 5．已知有这样一种对冒泡排序的优化方法：在每一遍“加工”过程中，记录在这遍“加工”中是否进行过数据交换。若在一遍“加工”过程中没有进行过数据交换，则数据已经有序，可以直接退出循环结束排序。则下列说法错误的是 （   ） A．对有n个数据的数组进行优化后的冒泡排序，最小比较次数为n-1。 B．对有n个数据的数组进行冒泡排序，无论是否优化，最大比较次数相同。 C．对冒泡排序算法进行优化，能够较大提高其效率，符合算法设计的一般原则。 D．若待排序数组中的数据依次为23，17，46，58，34，11，对其使用优化后的冒泡排序进行升序排序，比较次数为9。 6．下表记录了6个数据的排序过程。分析表中数据可知，该排序采用的算法与排序方式分别为(    ) A．冒泡排序，降序 B．选择排序，降序 C．冒泡排序，升序 D．选择排序，升序 7．下列说法正确的是（    ） A．未优化过的选择排序和冒泡排序，比较次数肯定是相同的，所以交换次数也肯定相同 B．对包含7个数据的有序数组a进行对分查找，平均查找次数为17/7次 C．VB调用数据库时，rs. fields（1）指的是调用某数据表中某条记录第1个字段的值 D．使用选择排序时，若某--遍排序时，并没有数据进行交换，说明数据已经有序 8．关于排序和查找，以下说法正确的是（      ） A．冒泡排序算法中，数据的交换次数与比较次数一定相同 B．选择排序算法中，若某一趟排序中数组元素没有发生过交换，则数组已有序 C．有10个数据的数组，用顺序查找算法查找某个数，查找不成功的时，查找次数为11次 D．有10个数据的有序数组，利用二分查找算法查找某个数，最多的查找次数为4次 9．五位评委给黑板报打分的成绩依次为95，85，92，84，90。如下表所示： 原始数据 95 85 92 84 90 第一遍 84 95 85 92 90 第二遍                第三遍 84 85 90 92 95 若采用冒泡排序算法对其进行从小到大排序，则上表中第二遍的排序结果是（  ） A．84，90，85，95，92 B．84，85，95，90，92 C．84，85，95，90，92 D．84，90，92，85，93 10．有如下VB程序段: Dim a(8) As Integer，b(8) As Integer，flag(10) As Integer For i  =  1 To 8 t = a(i) flag(t)  =  flag(t) + 1 Do While flag(t)<>1 t = (t + 1) Mod 10 flag(t) = flag(t) + 1 Loop b(i)  =  t Next i 数组b和flag中各元素的初值均为0，数组元素a(1)至a(8)的初值分别为“8，5，9，4，9，4，6，7”，程序运行后，b(8)的值为(      ) A．0 B．1 C．8 D．9 11．字符串数组a中a(1)到a(6)的原始数据为57，3，24，34， 6，120，为了对该数组进行排序操作，编写了以下VB程序。 i=2 Do While i<=6 For j=6 To i+2 Step -2 If a（j）>a（j-2）Then t=a（j）:a（j)=a（j-2）:a（j-2)=t Next j i=i+2 Loop 则程序运行之后，数组元素a(1)和a(2)的值分别是（　　） A．6    3 B．57    120 C．120   57 D．6    34 12．若采用冒泡排序算法对数据2， 36， 98， 15， 88， 118进行排序，排序过程如表所示。 原始数据 2 36 98 15 88 118 第一遍加工后 36 98 15 88 118 2 第二遍加工后          则第二遍加工后的结果是（  ） A．2，15，36，88，98，118 B．98，88，118，36，15，2 C．98，36，88，118，15，2 D．98，36，88，15，118，2 13．下列 VB 程序段功能为：将数组a(1)到a(6)中所有的偶数升序排序，且奇数所在的位置保持不变的功能。例如，a(1)到a(6)的初始值为“5,8,2,7,4,1”，则排序后的值为“5,2,4,7,8,1”。 flag = True Do While flag     flag = False     j = -1     For i = 1 To n         If a(i) Mod 2 = 0 Then             If ① Then                 tmp = a(i): a(i) = a(j): a(j) = tmp                 flag = True             End If             j = i         End If     Next i Loop 为实现上述功能，则划线处①的语句为（   ） A．a(i)<a(j) Or j<>-1 B．a(i)<a(j) And j<>-1 C．a(i)>a(j) Or j<>-1 D．a(i)>a(j) And j<>-1 14．将数据3、6、9、5、8、1进行一趟冒泡排序后得到的数据刚好是小杨的银行卡密码，那么小杨的银行卡密码可能是（       ） A．136958 B．369581 C．135698 D．316958 15．【加试题】有如下程序段： k = 0 : First = 1 : Last = 5 : Flag = True Do While Flag   k = k + 1   p = False : Flag = False   For j = First To Last      If a(j) > a(j + 1) Then        t = a(j): a(j) = a(j + 1): a(j + 1) = t        Last = j : Flag = True        If p = False Then          First = j ：p = True        End If      End If    Next j    If First <> 1 Then First = First - 1    Last = Last - 1 Loop 数组元素a(1)到a(6)的值依次为“3，6，8，5，7，9”，经过该程序段“加工”后，下列说法正确的是(     ) A．此过程中数据共交换了3次 B．此过程中该数组的数据共比较了7次 C．变量k的值为2 D．数组元素a(1)到a(6)的数未排成有序 二、填空题 16．n个数据的冒泡排序需要经过n-1遍加工，每一遍加工自下而上比较相信两个数据，把较小者交换到上面。小刘发现：当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。为此，小刘对算法进行优化，编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Commaiid1，在列表框List2 中显示这些数据按升序排序后的结果，在标签Label3中显示排序过程的加工遍数。运行效果如下图所示， 实现上述功能的VB代码如下： Dim a(1 To 8) As Integer Dim n As Integer Private Sub Form_Load() 'n=8，排序前数据存储在数组a中，并在列表框Listl中显示 '代码略 End Sub Private Sub Command1_Click() Dim flag As Boolean           i = 1 flag = True Do While        '改错      flag = False      For j = n To i + 1 Step -1         If a(j) < a(j - 1) Then            k = a(j): a(j) = a(j - 1): a(j - 1) = k            flag = True         End If      Next j      i = i + 1 Loop Label3.Caption = "排序过程的加工遍数为" +     '填空 For i = 1 To n    List2.AddItem Str(a(i)) Next i End Sub （1）代码“Private Sub Command1_Click()”中的Click是 。（单选，填字母：A．对象名/B．属性名/C．事件名） （2）程序代码中，Do While语句加框处有错，请改正。 （3）程序代码中，将Label3.Caption赋值语句补充完整。 （4）程序代码中，flag值为 表示某一遍加工中发生过交换。 17．将6名选手的歌唱比赛成绩存放在数组a中，如下表所示： 若按升序排列，采用冒泡排序算法自右向左进行比较和交换，第二轮排序之后a(4)中的值为 小胡收集了2018届高三学生高考成绩及相关的选科情况，存入数据库中，部分界面截图如图所示： 程序功能如下： 在窗体加载时，从数据库中读取学生总数N；读取N名学生的信息存储在相关数组中。N名学生的学号依次存储在数组xh(1)~xh(n) 中；学号为i的学生的总成绩存储在数组 zf(i)中，课程选修信息存储在xk(i)中； 点击“统计”按钮后，程序筛选出所有技术考生的相关信息，并计算该学生在所有技术考生中的排名（总分相同的，排名也相同）。 实现上述功能的VB程序如下，请回答下列问题： （1）请在划线处填入合适的代码。 Dim xh(1 To 1000) As Integer     ’数据库中读取时第i为学生的学号存储在xh(i) Dim zf(1 To 1000) As Integer     ’学号为i的考生的总分存储在zf(i) Dim xk(1 To 1000) As String         ’学号为i的考生的选考课程信息存储在zf(i)                                  ’ 数据格式 **-**-**   （如：物理-化学-生物） Dim jspm(1 To 1000) As Integer   ’学号为i的技术选考生的总分在所有技术考生中的                                  ’排名存储在数组jspm(i) Private Sub Form_Load() Dim conn   As New ADODB．Connection Dim rs As New ADODB．Recordset Dim  constr  as string , sql as string Constr = "Provider=Microsoft.ace.OLEDB．12.0;" Constr = constr &amp;  "Data Source=" &amp; App.Path + "\data\stu2018.accdb" conn.ConnectionString = constr conn.open( ) rs.Open  "select * from 2018cj  "  ,  conn i=0 Do While Not rs.EOF i=i+1 xh(i)=rs(“xuehao”) zf(rs(“xuehao”)) = rs(“fenshu”) xk(rs(“xuehao”))=rs(“xkinfo”) ① 18 Loop  N=i End Sub ’判断选科信息info中是否包含科目km   Function YouKM(ByVal km As String, ByVal Info As String) As Boolean         Dim km1 As String         YouKM = False         For i = 1 To 3         If ② 19 Then             YouKM = True             Exit For         End If         Next i End Function '为技术学科考试求名次 Private Sub Command1_Click() Dim jsinfo(1 To 1000) As Integer    ’依次存储每个技术选考生的学号和成绩 Dim k as integer                      ’存储找到的技术选考学生的数量 '将所有选考“技术”的考生学号、成绩依次存入数组jsinfo中    k = 0     For i = 1 To n         If     ③ 20 Then             k = k + 1             jsinfo(2 * k - 1) = xh(i)             jsinfo(2 * k) = cj(xh(i))         End If     Next i     '学号为i的学生在技术选考生中的排名,存入jspm（i）中     For i = 1 To k         mc = 0         For j = 1 To k             If jsinfo (2 * j) > jsinfo (2 * i) Then mc = mc + 1         Next j        jspm(jsinfo(2*i-1))=  ④ 21 Next i   '输出所有技术考试的学号、成绩、技术排名信息  代码略 End Sub 22．某社区为庆五一进行“摘草莓”比赛活动，最后取十人进入决赛，工作人员编制了如下Visual Basic程序，功能是根据草莓颗数进行排序，程序中所有参赛者的成绩保存在数组result中，对应的姓名保存在数组name中。 程序界面如图所示，左边列表框List1中显示数据（成绩和姓名），单击 “开始排序”按钮（Command1），排序后的结果按成绩从高到低显示在列表框List2中。 解决此问题的排序部分的程序段如下： Dim result(1 To 10) As Single Dim name(1 To 10) As String Private Sub Command1_Click( ) Dim I, J, K, X As Single, Y As String For I =" 1" To 9 K = I For J =" I" + 1  To  10 If ① Then K = J Next J If K <> I Then X =" result(I)" : result(I) =" result(K)" : ② Y =" name" (I) :  name (I) =" name" (K)   :  name (K) = Y End If Next I For I =" 1"  To  10 List2.AddItem Str(result(i)) + "     " + result(i) Next i End Sub Private Sub Form_Load() ' 此过程用于对数组a和数组b进行初始赋值，代码略 End Sub 在程序①和②划线处，填入适当的语句或表达式，把程序补充完整： 程序中①划线处应填入___________________。 程序中②划线处应填入___________________。 23．为了合理有效的共享学校图书馆自修室资源，学校实行自修室座位网上预约，学生 按学号登录系统进行预约（学号编码为六位数字，第一二位代表年级，第三四位代表班级，第五 六位代表顺序号。如 030102 表示高三 1 班 2 号同学）。为了方便老师管理，预约结束由电脑进行 排位。排位规则如下： ①年级优先原则，先高三再高二最后高一 ②班号优先原则，同年级的班号小的排前面 ③序号优先原则，同班级同学序号小的排前面 小张根据以上要求编写了 VB 程序，程序界面如下图所示： 实现上述功能的 VB 程序代码如下，请回答下列问题： ⑴分析程序，可知调用的数据库的名称为 。 ⑵请在划线处填入合适的代码。 Dim a(200) As String Const num = 200 Dim temp As String Private Sub Form_Load()    ‘此处代码实现将预约信息存储到数组 a(i)中 Dim cn As New ADODB．Connection Dim rs As New ADODB．Recordset cn.Open "provider=Microsoft.ACE.OLEDB．12.0;data source=" &amp; App.Path &amp; "\" &amp;"stu.accdb" rs.Open "select * from student" i = 1 Do While Not rs.EOF a(i) = rs("xuehao")   rs.MoveNext ① Loop rs.Close cn.Close List1.AddItem "预约号" &amp; "    " &amp; "学号" For i = 1 To num List1.AddItem Str(i) &amp; "    " &amp; a(i) Next i End Sub Private Sub Command1_Click() For i = 1 To num - 1 For j = num To i + 1 Step -1 If    ②   Then temp = a(j) a(j) = a(j - 1) a(j - 1) = temp End If Next j Next i List2.Clear List2.AddItem "座位" &amp; "    " &amp; "学号" For i = 1 To num List1.AddItem Str(i) &amp; "    " &amp; a(i) Next i End Sub Function check(x As String, y As String) As Boolean Dim x1 As Integer, x2 As Integer, x3 As Integer Dim y1 As Integer, y2 As Integer, y3 As Integer x1 = Val(Mid(x, 1, 2)) : x2 = Val(Mid(x, 3, 2)) : x3 = Val(Mid(x, 5, 2)) y1 = Val(Mid(y, 1, 2)) : y2 = Val(Mid(y, 3, 2)) : y3 = Val(Mid(y, 5, 2)) If x1 < y1 Or x1 =   y1 And x2 > y2 Or    ③    Then check = True Else check = False End If End Function 三、操作题 24．某校运动会跳远比赛，共m位(m≤20)选手参加该比赛，第一轮初赛每位选手跳3次，然后按每位选手的最好成绩，按高到低取前k名（若最好成绩相同，则名次相同）进入第二轮复赛。每位选手的成绩数据记录规则如下：成绩数据以“；”(分号)结尾，中间用“/”(斜杠)分隔，例如：“王一超/4.10/-/3.78；李雨歆/3.87/3.85/4.20；”，表示第一位选手王一超，第一次成绩4.10米，第二次成绩无效(用“-”表示），第三次成绩3.78米，最好成绩为4.10米。第二位选手李雨歆，3次成绩分别是3.87米、3.85和4.20米，最好成绩为4.20米。 小强编写VB程序实现上述功能：程序运行时，读取所有选手数据保存在变量cj中，并显示在列表框 List1中。在文本框Text1中输入进入第二轮的名次，单击“第二轮复赛名单”按钮 Command1，对数据进行统计分析，并在列表框 List2 中显示进入复赛的选手名单和最好成绩，程序运行界面如图所示，请回答下列问题。 （1）代码“List2.AddItem”中的 AddItem 是 （单选，填字母：A．事件名 / B．方法名 / C．属性名）。 （2）实现上述功能的 VB 程序如下，请在划线处填入合适的代码。 （3）程序中加框处代码有错，请改正。 Private Sub Command1_Click()    Dim cj As String, xm(1 To 20) As String, maxcj(0 To 20) As Single    Dim s As String, c As String, t As Single, z As Integer    Dim i As Integer, j As Integer, n As Integer, k As Integer, m As Integer    '读取所有选手数据保存在变量cj中，并显示在列表框 List1中，代码略    n = Len(cj)    i = 1 : m = 1 : z = 1    Do While i <= n       c = Mid(cj, i, 1)       j = i       Do While              '（3）          i = i + 1          c = Mid(cj, i, 1)       Loop       If z = 1 Then           ①       Else          t = Val(Mid(cj, j, i - j))          If t > maxcj(m) Then maxcj(m) = t       End If       z = z + 1 : i = i + 1       If c = ";" Then m = m + 1: z = 1    Loop    m = m - 1    k = Val(Text1.Text)    For i = 1 To m - 1       For j = ②          If  maxcj(j) > maxcj(j - 1)  Then             c = xm(j): xm(j) = xm(j - 1): xm(j - 1) = c             t = maxcj(j): maxcj(j) = maxcj(j - 1): maxcj(j - 1) = t          End If       Next j       If ③ Then          List2.AddItem xm(i) + Str(maxcj(i))       Else          Exit For       End If    Next i End Sub 25．有一组正整数，要求仅对其中的奇数进行升序排序。排序后在列表框List2中也仅显示奇数部分数据，结果如图所示。                     实现上述功能的VB代码如下，但加框处有错，请改正。 Const n=10 Dim a (1 To n) As Integer Private Sub Command1_Click() Dim t As Integer, i As Integer, j As Integer, m As Integer Dim tmp As Integer '读取一组正整数，存储在数组a中，并显示在列表框List1，代码略 i=1 Do While i<=n For j=n To i+1 Step-1 If a(j) Mod 2=1 Then   If    Then               '(1) tmp =a(j):a(j)=a(j-1):a(j-1)=tmp t=t+1 End If     End If Next j If     Then m=m+1        '(2) i=i+1 Loop For i=1 to m List2.AddItem Str(a(i)) Next i List2.AddItem "一共交换了"&amp; t &amp; "次" End Sub 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 2．C 3．C 4．C 5．D 6．C 7．B 8．D 9．C 10．B 11．B 12．C 13．B 14．A 15．D 16． C i<=n-1 and flag=true Str(i-1) true 17．82 18．rs.movenext 19．mid(info,3*i-2,2) 20．youkm(“技术” , xk(xh(i))) 21．mc+1 22．①result(j)>result(k)  ②result(k)="X" 23． stu.accdb i=i+1 check(a(j - 1), a(j)) x1 = y1 And x2 = y2 And x3 > y3 24．（1）B                                       （2）①xm(m) = Mid(cj, j, i - j)        ②m To i + 1 Step -1       ③i <= k Or maxcj(i) = maxcj(k) （3）c <> "/" And c <> ";" 25． a(j)<a(j-1) Or a(j-1) Mod 2=0 a(i) mod 2=1 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$