第三节 排序算法的程序实现

第三节 排序算法的程序实现 一、选择题 1．关于排序和查找，以下说法正确的是（      ） A．冒泡排序算法中，数据的交换次数与比较次数一定相同 B．选择排序算法中，若某一趟排序中数组元素没有发生过交换，则数组已有序 C．有10个数据的数组，用顺序查找算法查找某个数，查找不成功的时，查找次数为11次 D．有10个数据的有序数组，利用二分查找算法查找某个数，最多的查找次数为4次 2．编写VB程序生成一个n行n列的数字矩阵（数组元素为1-99之间的随机整数），显示在列表框Listl中，并在列表框List2中输出每行的最大值及其所在的位置。 Const n=4 Dim a(1 To n * n) As Integer, i As Integer,j As Integer,w As Integer Dim s As String,pos As Integer,Max As Integer For i=1 To n Max=0:s="" For j=1 To n pos= ① a(pos)=Int(1+Rnd * 99) s=s+Str(a((pos)) If ② Then Max=a(pos) w=j End If Next j Listl. AddItem s List2. AddItem i &amp;"行"&amp; ③ &amp;"列最大:"&amp; Max Next i 划线处的代码应为（    ） A．①(i-1)* n+j    ②a(pos)>Max    ③w B．①I * n+j    ②a(pos)>Max    ③j C．①(i-1)* n+j    ②a(j)>Max    ③w D．①i * n+j    ②a(j)>Max    ③j 3．有如下程序段： 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 4．有如下ⅤB程序段： ＇生成6个随机正整数，依次存入数组元素a(1)到a(6)，代码略 For i=1 To 2 For j=6 To i+ 1 Step-l If a(j)Mod 3 >a(j-1)Mod 3 Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j Next i 执行上述程序段后，下列选项中，a(1)到a(6)各元素值不可能的是（    ）。 A．2，1，4，3，6，7 B．5，2，1，7，8，3 C．7，7，6，3，3，1 D．8，7，4，3，3，2 5．某对分查找算法的VB程序段如下： Dim d(1 to 63)As Integer For i=1 to 63 d(i)=i Next i s=0:i=1:j=63 Key=Int(Rnd*63)+1 Do While i<=j m=(i+j)\2 If Key=d(m)Then Exit Do If Key<d(m)Then j=m-1:s=2*s Else i=m+1:s=2*s+1 End If Loop Label1.Caption=Str(s) 若运行该程序段后，标签 Label1中显示的结果是 28，则查找的Key值是（    ） A．28 B．29 C．57 D．58 6．有如下VB程序段： Const n=7 For i = 1 To 2   For j = i To n - i       If a(j) < a(j + 1) Then          t = a(j): a(j) = a(j + 1): a(j + 1) = t       End If   Next j   k = i   For j = i + 1 To n - i       If a(k) > a(j) Then k = j   Next j   If i <> k Then       t = a(i): a(i) = a(k): a(k) = t   End If Next i 数组元素a(1)到a(7)的值依次为9，2，5，1，4，8，3， 经过该程序段“加工”后，数组元素a(1)到a(7)的值依次为（   ） A．2 4 5 8 9 3 1 B．2 4 8 9 5 3 1 C．2 4 9 5 8 3 1 D．9 8 5 4 3 2 1 7．以下程序段实现将数组中比a(1)大的数据都排在后面,不大于a(1)的数据都排在前面，a(1)在两者之间,例 a(1)~a(6)中的数为：6,7,2,4,8,9,则处理后 a(1)~a(6)依次为 2,4,6,8,9,7 '数组变量 a(1)~a(6)中随机存入6个正整数，代码略 L = 2: R = 6 Do While L <= R If （1） Then t = a(L): a(L) = a(R): a(R) = t （2） Else （3） End If Loop t = a(R): a(R) = a(1): a(1) = t 上述程序段中方框处可选语句为（   ）: ① a(L) > a(1)② a(L) > a(R)③R = R – 1④L = L + 1 A．①③④ B．②③④ C．①④③ D．②④③ 8．对n个元素进行排序，用冒泡法进行排序时，需交换的次数共为（  ） A．可能大于n*(n-1)/2 B．必定小于等于n*(n-1)/2 C．n*(n－1)/2 D．n*(n＋1)/2 9．有如下 VB 程序段： For i = 1 To 2 For j = 1 To 6 – i If a(j) - a(j + 1) > 0 Then t = a(j): a(j) = a(j + 1): a(j + 1) = t End If Next j Next i Text1.Text = "" For i = 1 To 6 Text1.Text = Str(a(i)) + Text1.Text Next i 数组元素 a(1)到 a(6)的初值依次为 15，11，58，38，26，9，执行该程序段，文本框 Text1 显示的内容是（    ） A．9 58 11 38 15 26 B．11 15 26 9 38 58 C．58 38 9 26 15 11 D．58 9 38 11 26 15 10．某升序排序算法的VB程序段如下： Dim a (8) As Integer For i＝2 To 8 a(0)＝a(i) Do While a (0)<a(j) j＝j－1 Loop Next i 数组元素a(1)~a(8)的值为随机生成的整数，为实现升序排序，则上述程序段3个方框处的表达式分别为(    ) A．①j＝i－1    ②a(j＋1)＝a(j)    ③a(j＋1)＝a(0) B．①j＝i＋1    ②a(j＋1)＝a(j)    ③a(0)＝a(j＋1) C．①j＝i－1    ②a(j)＝a(j＋1)    ③a(j＋1)＝a(0) D．①j＝i＋1    ②a(j)＝a(j＋1)    ③a(0)＝a(j＋1) 11．有如下VB程序段： For i = 1 To 3 For j = 5 To i + 1 Step -1 If a(j) < a(i) Then t = a(j): a(j) = a(i): a(i) = t End If Next j Next i 假定数组元素a(1)~a(6)的值依次hippo，Change， sky， sk2， bellow， Half，执行程序后，a(3)~a(6)的值依次是（    ） A．bellow，sk2，hippo，sky B．hippo，sk2，sky，Half C．bellow，hippo，sk2，sky D．hippo，sky，sk2，Half 12．有如下程序段： n = 0:i = 2:f = True Do While i <= 6 And f n = n+1 f = False For j = 6 To i Step-1 If a(j)< a(j-1)Then t = a(j):a(j)= a(j-1):a(j-1)= t Last = j f = True End If Next j i = Last +1 Loop 数组元素a(1)到a(6)的值依次为“10，16，82，36，51，87”，经过该程序段“加工”后，下列说法不正确的是（    ） A．变量n的值为5 B．此过程中数据共需比较8次 C．此过程中数据共需交换2次 D．数组元素a(1)到a(6)的值为升序 13．数组有5个元素，有以下 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       End If     Next j Next i 数据“56，23，78，11，8”依次存放在数组 a(1)到 a(5)中，执行下列 VB 程序段后，数组 a(1)到 a(5)中的数据依次为（  ） A．8，11，23，56，78 B．23，11，8，56，78 C．11，8，23，56，78 D．8，11，56，23，78 14．下列VB程序段功能为：根据文本框Text1中各字符的大小关系，计算各字符升序排列的序号，并将序号保存在数组y中。如文本框内容为“2011”，程序运行后y（1）〜y（4）各元素的值分别为“4，1，2，3”。 s = Text1. Text n = Len（ s） For i = 1 To n y（ i） = 1 Next i For i=1 To （ 1） For j=（ 2） To n If （ 3） Then y（ j）=y（ j）+1 Else y（ i） = y（ i） + 1 End If Next j Next i 上述程序段3个方框处的表达式分别为 A．（1）n（2）1（3）Mid（s，j，1）>= Mid（s，i，1） B．（1）n（2）1（3）Mid（s，j，1）> Mid（s，i，1） C．（1）n-1（2）i+1（3）Mid（s，j，1）>= Mid（s，i，1） D．（1）n-1（2）i+1（3）Mid（s，j，1）> Mid（s，i，1） 15．数组d中存放了一组数据如表所示。采用选择排序对这组数据进行递增次序排序，每次将最大值放到数组尾部。 d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] 90 84 85 73 80 71 66 70 第一遍加工后 d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] 70 84 85 73 80 71 66 90 第二遍加工后 d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] 70 84 66 73 80 71 85 90 第三遍加工过程中，进行数据交换的数组元素是（  ） A．d[3]与d[6] B．d[4]与d[6] C．d[2]与d[6] D．d[3]与d[4] 二、填空题 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．某社区为庆五一进行“摘草莓”比赛活动，最后取十人进入决赛，工作人员编制了如下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 在程序①和②划线处，填入适当的语句或表达式，把程序补充完整： 程序中①划线处应填入___________________。 程序中②划线处应填入___________________。 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 小胡收集了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”) ① 19 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 ② 20 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     ③ 21 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))=  ④ 22 Next i   '输出所有技术考试的学号、成绩、技术排名信息  代码略 End Sub 23．【加试题】小明想用VB编程制作一个名次计算器，首先将同学的成绩录入到计算机中，同时存放在数组a中，显示在左边列表框中。点击“排序”按钮后，程序会将成绩从高到低依次排序显示在右边的列表框中。运行界面如图所示，请在两个划线处填入代码。 Dim a(1 To 100) As Single Dim shu As Integer Private Sub Command1_Click() Dim i, j, k As Integer Dim t As Single For i =" 1" To shu - 1 k = i For j =" i" + 1 To shu If Then t =" a(j):" a(j) =" a(k):" a(k) = t End If Next j Next i For i =" 1" To shu List2.AddItem "第" &amp; Str(i) &amp; "名：" &amp; Str(a(i)) Next i End Sub Private Sub Text1_KeyPress(KeyAscii As Integer) Dim cj As Single If KeyAscii =" 13" Then cj = Val(Text1.Text) If cj > 0 Then List1.AddItem Str(shu) &amp; "：" &amp; Str(cj) a(shu) = cj End If Text1.Text = "" End If End Sub 三、操作题 24．数组元素个数为n， 程序实现'小的数从尾开始往前冒泡，请将划线处代码补充完整。 Private Sub Command2_Click() List1.Clear Const n = 6 Dim a(1 To n) As Integer Dim i As Integer, j As Integer, t As Integer a(1) = 2: a(2) = 1: a(3) = 3: a(4) = 4: a(5) = 5: a(6) = 6 For i = 2 To ①   For j = n To i 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 For i = 1 To n     List1.AddItem Str(a(i)) Next i End Sub Private Sub Command3_Click() 13 数组元素个数为n，程序实现小的数从头开始往尾冒泡，请将划线处代码补充完整。 List1.Clear Const n = 6 Dim a(1 To n) As Integer Dim i As Integer, j As Integer, t As Integer a(1) = 2: a(2) = 1: a(3) = 3: a(4) = 4: a(5) = 5: a(6) = 6 For i = 1 To ①   For j = 1 To ②      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 For i = 1 To n     List1.AddItem Str(a(i)) Next i End Sub 25．某学校为增强学生体质， 督促学生进行必要的体育锻炼， 每学年都会举行一次新生体能测试， 在 高一年级每班随机抽取 2 位学生参加体测并要求全部达标。 高一年级学生基本信息存储于相应的数据库文件中， 班级总数为 n，每班 45 名学生。抽选时以学生学号信息为依据（学号为 8 位数， 前 4 位数字表示年级， 5、6 两位数表示班级， 7、8 两位数表示学号）， 并将抽选结果按照班级和学号升序排列输出。 根据上述要求编写 VB 程序， 功能如下： 读取高一年级 n 个班级学生学号信息， 显示在列表框 List1 中。程序运行时， 单击“抽取”按钮 Command1， 在列表框 List2 中显示每班被抽取中的两名学生学号。程序运行界面如图所示。 （1）在 VB 表达式 List2.AddItem s(i)中， List2、AddItem 依次表示 （单选，填字母： A．对象名、属性名/B．对象名、事件名/C．对象名、方法名） （2） 实现上述功能的 VB 程序如下， 请在划线处填入合适的代码。 （3） 程序中加框处代码有错，请改正。 Const n = 8 Dim a(1 To 500) As String Private Sub Form_Load() ‘读取数据库中学生学号信息并存储于数组a 中， 过程略。 End Sub Private Sub Command1_Click() Dim s(1 To 8) As String Dim flag(1 To 500) As Integer Dim b(1 To n) As Integer Dim w As Integer, t As Integer, i As Integer, j As Integer Dim x As String For i = 1 To 45 * n flag(i) = 0 Next i For i = 1 To n b(i) = 0 Next i w = 0 For i = 1 To n t = If flag(t) = 1 Then i = i – 1 ElseIf b(i) < 2 Then w = w + 1 b(i) = b(i) + 1 flag(t) = 1 If w Mod 2 = 1 Then i = i - 1 End If Next i For          '排序并输出被抽中学生学号 If Then x = s(i + 1): s(i + 1) = s(i): s(i) = x End If For j = i To i + 1 List2.AddItem s(j) Next j Next i End Sub 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 2．A 3．A 4．D 5．C 6．A 7．A 8．B 9．C 10．A 11．B 12．A 13．B 14．C 15．C 16． C i<=n-1 and flag=true Str(i-1) true 17．①result(j)>result(k)  ②result(k)="X" 18． B i q(c(t)) = p(i) cj(q(m)) > cj(q(m - 1)) q(m - 1) = temp 19．rs.movenext 20．mid(info,3*i-2,2) 21．youkm(“技术” , xk(xh(i))) 22．mc+1 23． a(j) &amp;gt; a(k) shu =" shu" + 1 24． n n-1 n-i 25． C 1 To 2*n-1 Step 2 Int(Rnd*45)+(i-1)*45+1 s(w) = a(t) s(i + 1)<s(i) 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$