2023-2024学年浙教版高一下学期第二章第三节 排序

2023-2024学年浙教版高一下学期第二章第三节 排序 一、选择题 1．采用选择排序算法对数据序列“8，9，6，1，3，0，-6，5”完成降序排序，则需要比较的次数为（   ） A．4 次 B．8 次 C．28 次 D．56 次 2．采用选择排序算法对某数据序列进行排序，经过某轮排序后的结果是“1，3，4，9，2，8，5”，再经过2轮排序后，该数据序列的顺序是（   ） A．1，2，3，9，4，8，5 B．1，2，3，4，9，8，5 C．1，2，3，5，4，9，8 D．1，2，3，4，5，8，9 3．下列VB程序段功能为：在文本框 Text中显示整型数组元素a(1)到a(9)中的最小值和最大值。 amin= a(1):amax=a(1) i=2:j=9 Do While i <= j If a(i) > a(j) Then     (1)         (2)     Else     (3)         (4)     End If i=1:j=j-1 Loop Text 1. Text= Str(amin)+"," Str(amax) 上述程序段中方框处可选语句为： ①If a(j)>amax Then amax =a(j) ②If a(j)< amin Then amin =a(j) ③If a(i)<amin Then amin =a(i) ④If a(i)>amax Then amax =a(i) 则（1）（2）（3）（4）处语句依次可为（    ）。 A．④③②① B．④②③① C．③②④① D．③①④② 4．某数据序列为“23，8，15，33，52，27，63，78”，采用选择排序算法将数据从小到大排序，那么排序过程中需要交换元素的次数是（   ） A．7 B．6 C．5 D．4 5．【加试题】实现某排序算法的部分VB程序如下： For i＝1 To 5 　     k＝i For j＝i＋1 To 6 　      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(6)的数据依次为“96，90，91，88，95，94”。则下一遍排序“加工”后数组元素a(1)到a(6)的数据依次是(　　) A．96，95，91，90，88，94 B．96，95，94，91，88，90 C．96，95，91，88，90，94 D．96，95，94，91，90，88 6．如下VB程序段实现对数组元素a（1）到a（10）从小到大排序。 i=1 Do While i<10 k=i：i=10 For j=10 To k + 1 Step -1 If a（j）<a（j-1） Then     t=a（j）：a（j）=a（j-1）：a（j-1）=1 ① End If Next j Loop 则代码中①处的语句可为（    ） A．i=i+1 B．i=j+1 C．i=k-1 D．i=j 7．【加试题】某排序算法的VB程序段如下： n = 10 Text1.Text = ""   For i = 1 To 5     For j = n To i + 1 Step -1       If a(j) < a(i) Then         temp = a(j): a(j) = a(i): a(i) = temp       End If     Next j   Next i   For i = 1 To 10       Text1.Text = Text1.Text + Str(a(i))   Next i 数组元素a(1)到a(10)的值依次为“965,155,195,444,106,734,172,983,898,360”，执行该程序段，文本框Text1中显示的是 A．106 155 172 195 360 444 734 898 965 983 B．106 155 172 195 360 734 444 983 898 965 C．983 965 898 734 444 360 172 195 155 106 D．106 155 172 195 360 965 444 734 898 983 8．有一数组a (1 to 6) ，其数值分别为44、38、78、37、96、69想要从小到大排序，编写如下程序代码： Dim flag As Boolean 'flag值为True表示某一遍加工中发生过交换 i = 1：n=6 flag = True Do While i <=n- 1 And flag = True 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 以上代码在整个排序过程中, 数组中的数据比较次数和交换次数分别是（ ） A．9次和4次 B．9次和6次 C．12次和9次 D．15次和12次 9．将数组a 中的 8 个数据“ 18， 33， 5， 26， 86， 0， 60， 200”按从大到小的顺序，使用选择排序，则需要交换的次数是（    ） A．4 B．5 C．6 D．7 10．采用选择排序算法对数据系列“1，3，5，2，4，0”完成降序排序，则需要交换的次数为（   ） A．2次 B．3次 C．4次 D．5次 11．以下VB程序段用以实现10个数组元素升序排序。 Dim a(1 To 10) As Integer Dim flag As Boolean Dim i As Integer, j As Integer, tmp As Integer '随机生成10个不重复的数据存入数组a中，代码略 For i= 2 To 10 tmp = a(i) j=i flag = False Do While   ① And Not flag a(j)=a(j-1) j=j-l          ② Loop a(j)= tmp Next i 要实现上述功能，方框①②中的语句分别是（    ） A．①tmp < a(j- 1) ②If j= 1 Then flag= True B．①tmp > a(j- 1)  ②If j= 1 Then flag= True C．①tmp < a(j)     ②If j= 0 Then flag = True D．①tmp > a(j)     ②If j= 0 Then flag = True 12．将数组a中的8 个数据“18,33,5,26,86,0,60,200”按从大到小的顺序排列,每次可以交换任意两个元素,最少需要交换的次数是(  ) A．4 B．5 C．6 D．7 13．采用冒泡排序算法对某数据序列进行排序，第一轮排序后的结果是“2,8,6,3,5,7,9”，则第二轮排序需要交换的次数为（   ） A．4 次或 2 次 B．4 次或 3 次 C．3 次或 1 次 D．2 次或 1 次 14．某书城五种畅销图书的市场价格(单位：元)存放在数组d中，如下表所示。现对这些数据进行升序排列，若采用冒泡排序算法自下而上进行比较和交换，那么在第一遍的加工过程中，数据的比较次数和交换次数依次为：(    )。 d[1] 26.80 d[2] 32.80 d[3] 20.00 d[4] 29.00 d[5] 36.00 A．2    2 B．4   4 C．4    2 D．5   2 15．在冒泡排序算法中，最好情况（即数组已经是有序的）下需要进行（   ）轮比较。 A．n B．n-1 C．n(n-1)/2 D．0 二、填空题 16．小佳编写了一个统计每个单词出现次数的程序，单词中字母不区分大小写。程序功能如下： 程序运行时在文本框 Text1 中输入一段英文文章，单击“统计”按钮 Command1，程序统计每个单词出现的次数，结果输出在列表框 List1 中，按出现次数由多到少显示，当出现次数一样时，按字母顺序从小到大排列。程序运行界面如图所示。 （1）实现上述功能的 VB 程序如下，请在划线处填入合适的代码。 ①处代码为 ，②处代码为 ，③处代码为 。 （2）程序中加框处代码有错，请改正。 应改为 Private Sub Command1_Click() Dim dict(1 To 10000) As String ‘存储自建单词字典 Dim n(1 To 10000) As Integer  ‘存储单词出现次数 Dim w As String, a As String, ch As String, x As String, y As Integer Dim i As Integer, b As Integer, k As Integer, d As Integer, j As Integer a = Text1.Text: k = 1 For i = 1 To 10000 n(i) = 0 Next i b = 1 For i = 1 To Len(a) ch = Mid(a, i, 1) If  Not (ch >= "A" And ch <= "Z" Or ch >= "a" And ch <= "z") Then If  i > b Then w = ‘取出单词,转为小写,存入 w 中 d = 1 Do While w <> dict(d) And d < k d = d + 1 Loop If d = k Then dict(k) = w: n(k) = 1: k = k + 1 Else n(d) = ① End If End If b = i + 1 End If Next i For i = 1 To k - 2 For j = k - 1 To i + 1 Step -1 If n(j) > n(j - 1) Or ( ② ) Then x = dict(j): dict(j) = dict(j - 1): dict(j - 1) = x y = n(j): n(j) = n(j - 1): n(j - 1) = y End If Next j Next i For i = 1 To k - 1 List1．AddItem dict(i) &amp; " " &amp; n(i) Next i End Sub Function LC(s As String) As String ‘单词中字母转为小写 Dim i As Integer, c As String For i = 1 To Len(s) c = Mid(s, i, 1) If c >= "A" And c <= "Z" Then c = Chr(Asc(c) + 32) ③ Next i End Function 17．下列VB程序的功能是：程序运行时，单击命令按钮Commandl后，产生10个[1，999]范围内互不相同的随机整数，依次显示在列表框List1中，然后将它们按从小到大的顺序排序，排序结果显示在列表框List2中。数组a用于存储产生的10个随机整数，函数f(x)用于判断随机整数x与已生成的整数是否有重复，若有重复则返回True，否则返回False。 （1）虚线框内程序段所采用的排序算法名称是 。（填：冒泡排序/选择排序） （2）在程序(1)和(2)划线处，填入适当的语句或表达式，把程序补充完整。 Dim a(1 To 10) As Integer Function f(x As Integer) As Boolean      ′代码略 End Function Private Sub Commandl_Click() Dim n As Integer                         ′n用于统计已经产生的随机整数个数 Dim i As Integer.j As Integer Dim x As Integer.k As Integer Randomize                                ′初始化Rnd函数 n=0 List1.Clear                              ′清除列表框中内容 List2.Clear Do While n<10 x=Int(Rnd*999)+1                         ′产生[1，999]范围内的随机整数 If Not f(x) Then n=n+1 a(n)="x" List1.AddItem Str( （1） ) End If Loop For i="1" To 9                             ′进行排序 For j="10" To i+1 （2） If a(j)<a(j-1) Then k=a(j):a(j)=a(j-1):a(j-1)=k End If Next j    Next i For i="1" To 10 List2.AddItem Str(a(i)) Next i End Sub 三、操作题 18．某著名景点在七月份收到若干旅游公司的通告，通告中包括该公司旅游的起始时间和终止时间， 如[6，10]表示该旅行团 6 号早上到，10 号早上回。疫情期间为避免人员扎堆，公司在时间段[start， ending]进行限流操作，要求在该时间段内景点每天都接待游客，且接待的旅行团越少越好。若景点收到的旅行团的数据是[3，8]、[3，6]、[8，15]、[18，25]、[14，20]、[5，10]，[10，18]、[13，18]限流时间是[4，19]。工作人员对旅行团的数据做了如下处理： ①将旅行团的旅行时间按照“到达时间”为主要关键字，“返回时间”为次要关键字升序排序。排好序的时间段是[3，6]、[3，8]、[5，10]、[8，15]、[10，18]、[13，18]，[14，20]、[18，25]. ②从前往后遍历时间段，选择“到达时间”不大于“限流开始时间”的时间段，若有多个时间段满足条件，且时间段未超出限流时间，应选择“返回时间”最大的时间段，选择的时间段是[3，8]。 ③缩小限流时间[8，19]，重复步骤 2，选择满足条件的时间段是[8，15]，缩小限流时间[15，19]，重复步骤 2，选择满足条件的时间段是[14，20]，结束时间已超过限流终止时间，结束。 ④若在遍历时间过程中出现“到达时间”大于“限流开始时间”，景点不能每天接待旅客，则没有满足条件的旅行社。 小王编写 VB 程序，程序界面如下所示，单击“排序”按钮，将旅行团的时间按照“到达时间”为主要关键字，“返回时间”为次要关键字升序排序，在 Text1 和 Text2 中输入限流的起始时间和终止时间，单击“满足条件的旅行团”按钮，在列表框输出满足条件的旅行团的时间，若没有满足条件的旅行社，则在列表框输出“没有满足条件的旅行团！” 回答下列问题： （1）若景点接收到的旅行社的起始时间和终止时间分别为[5，17]、[7，18]、[4，12]、[3，8]、[2，10]， 限流时间是[3，15]，筛选出的旅行团的时间是 （2）请在横线处填入合适的代码 Dim i As Integer, j As Integer, n As Integer, t As Integer Dim a(100) As Integer, b(100) As Integer Private Sub Command1_Click() ' 将旅行团个数存入 n,加载 n 个旅行团的起始时间、终止时间并分别放在数组 a 和数组 b 中,代码略 For i = n to 2 step -1   j=1   Do while ①     If a(j) > a(j + 1) Or a(j) = a(j + 1) And b(j) > b(j + 1) Then       t = a(j): a(j) = a(j + 1): a(j + 1) = t       t = b(j): b(j) = b(j + 1): b(j + 1) = t     End If     j=j+1 Loop Next i ' 输出排好序的时间段,代码略 End Sub Private Sub Command2_Click()   Dim arrivetime As Integer, leavetime As Integer   start = Val(Text1.Text): ending = Val(Text2.Text)   For i = 1 To n     arrivetime = start     If a(i) <= arrivetime Then         If b(i) > leavetime Then leavetime = b(i):t=i          If② Then              List2.AddItem  Str(a(t))  &amp;  "---"  &amp;  Str(b(t)) Exit For          End If     Else          If start < arrivetime or i = 1 Then             List2.Clear             List2.AddItem "没有满足条件的旅行团!"            Exit For        End If        List2.AddItem Str(a(t)) &amp; "---" &amp; Str(b(t)) ③ i = i – 1     End If   Next i End Sub 19．【加试题】有一组正整数，基于冒泡排序对其中的数进行升序排序。排序后奇数在前，偶数在后。排序示例如下： 排序前 78 30 64 39 49 4 8 32 18 32 排序后 39 49 83 4 8 18 30 32 64 78 实现上述功能的VB程序如下，但加框处代码有误，请改正。 Const n = 10 Dim d(1 To n) As Integer Private Sub Command1_Click()   Dim i As Integer, j As Integer, t As Integer   '读取一组正整数，存储在数组d中，代码略   i = 1   Do While i <= n - 1     For j = n To i + 1 Step -1       If d(j) Mod 2 = d(j - 1) Mod 2 Then         If  d(j) > d(i)  Then              '(1)           t = d(j): d(j) = d(j - 1): d(j - 1) = t         End If        Else                             '(2)           t = d(j): d(j) = d(j - 1): d(j - 1) = t       End If     Next j     i = i + 1   Loop   '依次输出排序后的数据，代码略 End Sub 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．A 3．B 4．D 5．C 6．D 7．B 8．C 9．B 10．B 11．A 12．B 13．A 14．C 15．B 16． n(d) + 1 n(j) = n(j - 1) And dict(j) < dict(j - 1) LC = LC &amp; c  或 LC = LC + c LC(Mid(a, b, i - b)) 17．（1）冒泡排序   （2）a（n）   Step-1 18． [2， 10]， [5， 17] j<i或者j<=i-1 leavetime>=ending start= leavetime 19． d（j） < d（j-1） ElseIf d（j） mod 2 = 1 And d（j-1） mod 2 = 0 then或其它等价的答案 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$