第三节 排序-2023-2024学年高一信息技术浙教版选修1

第三节 排序 一、选择题 1．采用冒泡排序算法对数据序列“8，3，5，2，0，9”进行排序，第一轮排序后的结果为“0，8，3，5，2，9”，则整个序列完成排序的交换次数是（  ） A．6次 B．7次 C．8次 D．9次 2．分别采用选择排序和冒泡排序对数据序列“15 89 60 34 10 28 70”完成升序排序，则在两种排序方法过程中，数据“60”发生交换的次数分别可能为（ ） A．3   3 B．2 4 C．21   4 D．3  4 3．【加试题】以下一段程序其功能是对数组a(下标范围为1 to n)中的数据进行升序排序，划线处应填入的正确语句是（     ）   For i =   For j = 2 To i     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 A．n to 2 Step -1 B．2  to  n C．n-1 to 1 Step -1 D．1 to n -1 4．对5个字母“C、Y、E、A、J”进行两遍冒泡排序后即为某密码锁的密码，该密码可能是： A．ACEYJ B．ACYEJ C．CYEAJ D．ACEJY 5．有如下 VB 程序段： a(1) = 10: a(2) = 3: a(3) = 2: a(4) = 8: a(5) = 4: a(6) = 6 n = 6 For i = 1 To Int(Rnd() * 4 + 1)     For j = n To i + 1 Step -1         If a(j) * j < a(j - 1) * (j - 1) Then             tt = a(j): a(j) = a(j - 1): a(j - 1) = tt         End If     Next j Next i 上述程序运行后，a(1)到a(6)各元素值不可能是(    ) A．3,2,4,6,10,8 B．3,10,2,4,8,6 C．3,2,4,10,6,8 D．3,2,4,6,8,10 6．数组a中的n个元素经排序生成左右交替上升数据序列的VB程序段如下： For i = 1 To   （1）       For j =    （2）       To i + 1 Step -1 If d(j) <d(j - 1) Then t = d(j): d(j) = d(j - 1): d(j - 1) = t End If Next j For j = i + 1 To    （3）        If d(j) <d(j + 1) Then t = d(j): d(j) = d(j + 1): d(j + 1) = t End If Next j Next i 方框中的代码由以下三部分组成： ①n - i + 1                ②n \ 2                ③n - i 代码顺序正确的选项是 A．②①③ B．①②③ C．②③① D．③②① 7．对于数据 [4,5,1,3,2]，在使用选择排序从小到大进行第一轮排序之后，结果是（   ） A．[4,5,1,3,2] B．[4,1,3,2,5] C．[1,3,2,4,5] D．[1,5,4,3,2] 8．对N个数进行冒泡排序， 下列描述正确的是（   ） A．比较次数为N-1次 B．最多需交换N次 C．交换数据的次数一定比选择排序多 D．元素的交换次数小于或等于元素的比较次数 9．用选择排序将七个数“2022,2017,2018,2014,2021,2012,2015”从小到大进行排序,则第二轮交换数据后的顺序是(  ) A．2022,2021,2018,2017,2014,2012,2015 B．2012,2014,2018,2017,2021,2022,2015 C．2012,2017,2018,2014,2021,2022,2015 D．2022,2021,2018,2014,2017,2012,2015 10．采用选择排序算法对某数据序列进行排序，经过两轮排序后的结果是“9，8，3，5，2，7，6”，那么原数据序列不可能的是（    ） A．9，8，3，5，2，7，6 B．3，7，9，5，2，8，6 C．5，8，3，7，2，9，6 D．8，5，3，9，2，7，6 11．数组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] 66 84 85 73 80 71 90 70 第二遍加工后： d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] 66 70 85 73 80 71 90 84 第三遍加工过程中，待排序数据的范围是（）。 A．d[4]至 d[8] B．d[1]至 d[3] C．d[1]至 d[8] D．d[3]至 d[8] 12．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为19万、15万、21万、13万、12万元人民币。 若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是（    ） A．1 B．2 C．3 D．4 13．下列关于排序算法的描述，错误的是（   ） A．对规模为 n 的数据进行冒泡排序，交换次数一定不会超过比较次数 B．对规模为 n 的数据进行升序选择排序，交换次数为 n-1 次的最坏情况时，原数列可能是一个降序数列 C．对规模为 n 的数据进行未优化的冒泡排序，比较次数为 n×(n-1)/2 次 D．选择排序中，某一遍加工没有发生数据交换，此时的数据不一定有序 14．在上体育课的时候同学们随便排了队伍，老师要求按照身高从高到低依次排队，如果按照插入排序算法，第一步要做的是（   ） A．前2位同学从高到低排 B．前2位同学从低到高排 C．最高的同学跟最低的同学交换位置 D．最高的同学跟第一位同学交换位置 15．有如下程序段: For i = 1 To 8 a(i) = Int(Rnd * 10) + 1 Next i For i = 1 To 5 Step 2 k = i For j = i + 2 To 7 Step 2 If a(j) < a(k) Or a(j) = a(k) And a(j + 1) < a(k + 1) Then k = j Next j If i <> k Then t = a(i): a(i) = a(k): a(k) = t t = a(i + 1): a(i + 1) = a(k + 1): a(k + 1) = t End If Next i 运行该程序段后，数组a各元素的值可能是（  ） A．2,3,2,2,5,4,7,5 B．0,2,4,3,6,5,9,10 C．1,1,1,3,3,4,5,6 D．9,8,6,7,6,3,1,2 二、填空题 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．某会场每天会收到众多举办活动的申请。现需对活动申请进行统筹安排，以确保会场在同一时间内只安排一个活动且每天安排尽可能多的活动。具体规定如下： ●对各个活动按结束时间先后进行升序排序，若结束时间相同，按开始时间先后升序排序。 ●先安排结束时间最早的活动，依次考虑未安排的活动，如果和已安排的活动没有时间冲突，则予以安排；否则，不予安排。 小明为此编写了VB程序，功能如下：在列表框List1读取活动编号、活动时间（开始时间-结束时间）。按编号依次显示。单击“统筹安排”按钮Commandl，对申请的活动按规定进行排序，并在列表框List2中输出当天能安排的活动编号、活动时间和数量。程序运行界面如图所示： （1）某天收到8个活动申请，各活动时间（开始时间-结束时间）分别为“07-12，10-13，14-20，09-12， 12-15，09-11，10-12，08-10”。根据上述规定，当天最多能安排 个活动。 （2）实现上述功能的VB程序如下，请在划线处填入合适的代码。 Dim a(1 To 100)As ltege, b(1 To 100)As lee, c(1 To 100)As lteger Dim m As Integer Private Sub Form Load() '从数据库中读取活动编号、开始时间和结束时间,分别存储在数组c、a、b中,并在列表框list1中显示;统计收到的活动申请数量,存储在变量m中 '代码略 End Sub Private Sub Command1_ Click() Dim i As Integer,j As Integer,k As Integer Dim temp As Integer,n As Integer, last As Integer '对各个活动按时间进行排序 For i=1 To m-1     k=i     For j=i+ 1 To m         If b(c(j)) < b(c(k)) Then             k=j         Else If Then             k=j         End If     Next j     If k<> I Then         temp = c(k):e(k) = c(i): c(i)temp     End If Next i last = b(c(1)) 'CStr(n)将n转换成字符串并去除字符串前空格 List2．AddItem " "+ adj((c(1)),4)+ CStr(a(c(1)))+ "-" + CStrb(c(1))) ② For i= 2 To m If a(c(i)) >= last Then List2．AddItem " "+ adj((c(i)),4)+ CStr(a(c(i)))+ "-" + CStrb(c(i))) n=n+ 1 End If Next i List2.AddItem"最多能安排" &amp; CStr(n)&amp; "个活动" End Sub Function adj(a A s String, b A s Integer) 将字符串对齐输出,代码略 End Function 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 2．B 3．A 4．A 5．D 6．A 7．D 8．D 9．B 10．C 11．D 12．B 13．B 14．B 15．C 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． 3 ①b(c(j)) = b(c(k))And a(c(j)) < a(c(k)) (或等价答案) ②n= 1 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$