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

2023-2024学年浙教版高一下学期第五章第三节 排序算法的程序实现 一、选择题 1．在信息加工中，经常要对被处理的数据进行排序，数据的排序有多种方法，冒泡法是一种常用的排序方法，在排序时经常要进行数据的交换。下列四个选项中，（   ）不能正确地将x和y两个变量中的数据进行交换。 A．x = y y = x x = x － y B．x = x + y y = x － y y = m C．m = x x = y x = y － x D．x = x － y y = x + y A．A B．B C．C D．D 2．有如下VB程序段： For i=1 To 6 a(i) =Int(Rnd()*10)+1 If a(i) Mod 2=i Mod 2 Then i=i-1 Next i For i=1 To 2 For j= 6 To i+2 Step -1 If a(j)>a(j-2) Then t=a(j):a(j)=a(j-2):a(j-2)=t End If Next j Next i 执行程序后，数组a各元素可能是（   ） A．7,6,5,4,3,2 B．6,7,4,5,2,3 C．11,8,9,6,7,4,5 D．2,5,6,9,8,11 3．编写程序，实现功能：通过双向排序，使数组元素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．③② 4．有如下VB程序段： For i = 1 To 6 a（i） = Int（Rnd * 10） + 1 Next i For i = 1 To 5 If i Mod 2 = 1 And a（i） > a（i + 1） Then t = a（i） ： a（i） = a（i + 1） ： a（i + 1） = t Else a（i） = a（i） + 1 End If Next i 执行该程序段后，a（l）~a（6）各元素可能的值是 A．11，11，7，9，3，9 B．6，2，8，10，5，9 C．6，9，3，7，8，12 D．3，9，0，8，2，7 5．某排序算法的VB程序段如下： k=1 For i=1 To 2 For j=1 To 6-2*i If k* a(j)<k*a(j+2)Then t=a(j): a(j)=a(j+2): a(j+2)=t End if k=-k Next j Next i 数组元素a(1)到a(6)的初始值依次为“15，11，58，38，26，9”，该程序段执行后，数组a元素的值分别为（    ） A．58，9，26，11，15，38 B．58，38，26，11，15，9 C．15，38，26，11，58，9 D．58，38，26，15，11，9 6．有如下VB程序段： For i=1 To 2 For j=1 To 5-i If a(j+1)<a(j) Then t=a(j):a(j)=a(j+1):a(j+1)=t Next j Next i 数组a(1)到a(5)中数据分别为56，23，78，11，8，执行上述VB程序段后，数组元素的值分别为（    ） A．8，11，23，56，78 B．23，11，8，56，78 C．11，8，23，56，78 D．8，11，56，23，78 7．现有数组d如下： d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) 10 12 21 6 15 5 3 18 若按降序排列，采用选择排序算法选出最大值进行比较和交换，那么在第4轮的数据处理过程后，d(8)的值是（    ）。 A．21 B．6 C．5 D．12 8．某排序算法的VB程序段如下： '读取n个整数，依次存入a（1）到a（n）中，代码略 For i=1 To n - 1 For j=n To i+ 1 Step -l If a（j）>a（j-1）Then t=a（j）：a（j）=a（j-1）：a（j-1）=t Next j Next i 执行上述程序段，下列说法正确的是（    ） A．交换过位置的数据，可能会再回到其初始位置 B．执行完成后，数组元素a（1）到a（n）从小到大排列 C．若n为5，整个排序过程总的比较次数是20 D．整个排序过程总的交换次数至少为1 9．下列VB程序段的功能为：生成n个不重复的随机整数，保存在数组a中，并升序排序。 Const n = 6 Dim a(1 To n) As Integer, f(1 To 10) As Boolean Dim tmp As Integer, i As Integer, j As Integer, t As Integer ’f数组各元素的初值置为False，代码略 For i = 1 To    (1)       t = Int(1 + Rnd * 10)    If Not f(t) Then      a(i) = t : f(t) = True      For j =      (2)            If a(j) < a(j - 1) Then           tmp = a(j): a(j) = a(j - 1): a(j - 1) = tmp        End If      Next j    Else         (3)       End If Next i 上述程序段3个方框处的表达式分别为 A．（1）n - 1     （2）2 to i             （3）i = i - 1 B．（1）n         （2）i to 2 Step -1     （3）i = i - 1 C．（1）n - 1     （2）2 to i             （3）t = Int(1 + Rnd * 10) D．（1）n         （2）i to 2 Step -1     （3）t = Int(1 + Rnd * 10) 10．有一个数组，采用冒泡排序，第一遍排序后：结果为：3，18，5，35，8，9，11，13，32，那么该数组的原始顺序不可能是（  ） A．18，5，35，8，9，11，13，32，3 B．18，5，35，8，9，11，3，13，32 C．18，5，35，3，8，9，11，13，32 D．3，18，5，35，13，11，32，8，9 11．完成某排序算法的 VB 程序段如下： For i = 1 To 7 k = 0 For j = 8 To i+1 Step -1 If a(j) <a (j-1) Then t = a(j): a(j) = a(j-1): a(j-1) = t: k = 1 Next j If k = 0  Then   Exit For Next i 如果用上述算法对数据序列：38，11，21，62，59，65，77，79 进行排序（数据分别储存在数组元素 a(1)～a(8)中），执行程序后，数据的交换次数和比较次数分别为（   ） A．2，11 B．3，18 C．4，18 D．7，11 12．有如下程序段： i=1 Do while i<=2    j=1    Do while j<=7-i       If a(j) > a(j+1) Then          t = a(j): a(j) = a(j+1): a(j+1) = t        End If        j=j+1    Loop    i=i+1 Loop 数组元素a(1)到a(7)的值依次为“44，24，33，67，77，58，12”，经过该程序段“加工”后，数组元素a(1)到a(7)的值依次为                                                    （    ） A．24，33，44，58，12，67，77 B．12，24，33，67，77，58，44 C．12，24，44，33，58，67，77 D．44，24，33，58，12，67，77 13．有如下程序段： For i = 1 To 2 For j = 5 To i + 1 Step -1 If a(j) > a(j-1) Then t = a(j): a(j) = a(j-1): a(j-1) = t End If Next j Next i 数组元素a(1)到a(5)的值依次为“33，24， 45， 16， 77”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为（    ） A．77，45，33， 24，16 B．16， 24，33， 45， 77 C．77， 45， 24，16，33 D．16，24，45，33，77 14．有如下VB程序段: For i = 1 To 3     For j = 1 To 6-i         If a(j)>a(j+1) Then t=a(j):a(j)=a(j+1): a(j+1)=t     Next j Next i 数组元素 a(1)到 a(6)的数据依次为“55，31，19，42，37，23”，则此程序运行完成后数组元素的数据依次是（  ） A．55，42，37，31，23，19 B．19，23，31，55，37，42 C．19，23，31，37，42，55 D．19，31，23，37，42，55 15．编写一个基于对分查找插入数据的程序代码。实现把数据temp插入降序序列后得到一个新的降序序列，原序列各元素存放在数组元素a（1）～a（n）中。实现上述功能的程序段如下：     temp = Val(Text1.Text)     If temp <= a(n) Then         a(n + 1) = temp     Else         left = 1: right = n         Do While left <= right             mid = (left + right) \ 2             If ① Then right = mid - 1 Else left = mid + 1         Loop         For j = n To left Step -1              ②         Next j          ③    End If 则横线①②③上的语句分别是（   ） A．①a(mid) > temp②a(j) = a(j-1)③a(right+1) = temp B．①a(mid) < temp②a(j) = a(j-1)③a(left) = temp C．①a(mid) > temp②a(j+1) = a(j)③a(right+1) = temp D．①a(mid) < temp②a(j+1) = a(j)③a(left) = temp 二、填空题 16．将6名选手的歌唱比赛成绩存放在数组a中，如下表所示： 若按升序排列，采用冒泡排序算法自右向左进行比较和交换，第二轮排序之后a(4)中的值为 17．为了合理有效的共享学校图书馆自修室资源，学校实行自修室座位网上预约，学生 按学号登录系统进行预约（学号编码为六位数字，第一二位代表年级，第三四位代表班级，第五 六位代表顺序号。如 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 18．某地区进行了三个年级技术联考，现要求按学校分类对高三年级技术成绩降序排序后输出。小王编写了一个VB程序实现上述要求。先单击“统计”按钮Command1，读取数据库中每位学生的学校、年级、姓名和成绩等信息，进行统计分析后，并在列表框List2中分学校按成绩降序输出。程序运行时界面如图所示。 （1）根据图中示例数据，采用选择排序算法分别对学校B的数据进行排序，整个排序过程中，数组元素之间的比较次数是 （单选，填字母：A．37×19 次 / B．37×18 次/ C．36次）。 （2）请在划线处填入合适的代码。 Const rs = 480      '联考参加学生总人数rs Const no = 3        '联考参加学校数no Dim school(1 To rs) As String '存储学生的学校 Dim nj(1 To rs) As String     '存储学生的年级 Dim xm(1 To rs) As String     '存储学生的姓名 Dim cj(1 To rs) As Integer    '存储学生的成绩 Dim p(1 To rs) As Integer     '索引数组 Dim num(1 To no) As Integer Dim n As Integer Function id(s As String) As Integer '根据学校名称转换为对应的数字ID号，代码略 End Function Private Sub form_load() '本过程读取每位学生的学校、年级、姓名和成绩的数据分别存储在数组school，nj、xm 和 cj 中，并在 List1 中显示学生成绩数据和每个学校的高三人数，代码略； End Sub Private Sub Command1_Click()   Dim i As Integer, j As Integer, k As Integer, t As Integer, pos As Integer   Dim b(1 To no) As Integer, c(1 To rs) As Integer, q(1 To rs) As Integer   k = 0   For i = 1 To n      If nj(i) = "高三" Then          k = k + 1           p(k) =            num(id(school(i))) = num(id(school(i))) + 1      End If   Next i '在 List1 中显示各学校的高三人数，代码略；   c(1) = 1   For i = 2 To no      c(i) = c(i - 1) + num(i - 1)   Next i   For i = 1 To k      t = id(school(p(i)))            c(t) = c(t) + 1   Next i      '----按学校分类，从高分到低分排序后输出-----   pos = 1   For i = 1 To no       For j = pos To c(i) - 2         For m = c(i) - 1 To j + 1 Step -1                If      Then temp = q(m): q(m) = q(m - 1):              End If          Next m       Next j       pos = c(i)   Next i   For i = 1 To k       List2.AddItem school(q(i)) &amp; " " &amp; xm(q(i)) &amp; " " &amp; nj(q(i)) &amp; " " &amp; cj(q(i))   Next i End Sub 三、操作题 19．下列程序的功能是对某校2011年3月份技术高考成绩进行排名分析，数组a中保存学生技术考试的成绩，数组b中保存学生的姓名，第i个学生的技术成绩保存在a(i)中，对应的学生姓名保存在b(i)中，最后按技术成绩从高到低进行排序。程序界面如图所示，左边列表框List1中显示的是所有学生到的原始数据，单击"排序"按钮（Command1）后，在右边的列表框List2中显示排序完成后的结果（按成绩从高到低排列）。 （1）虚线内程序段所采用的排序算法名称是 。 （2）程序加框处代码有错，请改正。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 2．B 3．C 4．A 5．A 6．B 7．B 8．A 9．B 10．D 11．B 12．A 13．A 14．D 15．D 16．82 17． stu.accdb i=i+1 check(a(j - 1), a(j)) x1 = y1 And x2 = y2 And x3 > y3 18． B i q(c(t)) = p(i) cj(q(m)) > cj(q(m - 1)) q(m - 1) = temp 19．（1）冒泡排序 （2）①Single ② b(j - 1) = b(j) 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$