第二轮排序和查找算法综合1
行政班：教学班：姓名：学号：
根据课本上的排序算法和查找算法回答1-6题：
1．【加试题】有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能
．．．的是（）
A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7
2.【加试题】对下列数据序列进行冒泡升序排序，排序效率最低的序列（）
A.31，29，24，20，15，10
B.10，15，20，24，29，31
C.29，10，31，15，20，24
D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（）
A．69 B．66、69 C．66、76、69 D．56、66、76、69
4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种方法都能访问到的数字是（）
A.3
B.5
C.8
D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为（）
A.feel, data, easy
B.great, data, easy
C.bike, cake, dada，easy
D.feel,cake,data,easy
6.【加试题2】下列有关查找的说法，正确的是（）
A．进行对分查找时，被查找的数据必须已按升序排列
B．进行对分查找时，如果查找的数据不存在，则无需输出结果
C．在新华字典中查找某个汉字，最适合使用顺序查找
D．对规模为n的数据进行顺序查找，平均查找次数是21 n
7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。
经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是（）
For i = 1 To 1
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.70，57，38，53，30
B.30, 38，70，53，57
C.70，38，57，53，30
D.30, 38，57，53，70 8.【加试题】有如下程序段：
For i = 1 To 2
For j = 1 To 6 - 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(1)到a(6)的值依次为“71，54，58，29，31，78”，经过该程序段“加工”后，数组元素a(1)到a(6)的值依次为（）
A. 29，31，54，58，71，78
B. 78，71，58，54，31，29
C. 54，29，31，58，71，78
D. 71，58，54，78，31，29 9．【加试题】对数组a中的5个数据“5，10， 6，30，9”进行排序，部分程序如下：
For i = 1 To 4
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.升序排序，实线框中的语句共执行了2次
C.降序排序，实线框中的语句共执行了5次B.升序排序，实线框中的语句共执行了3次
D.降序排序，实线框中的语句共执行了6次
10.【加试题】有如下程序段：
tot = 0
For i = 1 To 4
For j = 5 To i + 1 Step -1 If a(j) > a(i) Then
tot = tot + 1
t = a(j): a(j) = a(i): a(i) = t End If Next j Next i
数组元素 a(1)到 a(5)的值依次为“33,24,4,16,77”，经过该程序段“加工”后，变量 tot 的值为（）
A.2
B.3
C.4
D.5 11.【2015年9月测试卷加试题,知识点1】采用如下选
择排序算法对数组a中5个数据“23，86，98，65，2”按从小到大的顺序进行排序。
For i = 1 To 4 k = i
For j = i + 1 To 5
If a(j) < a(k) Then k = j Next j
If k <> i Then
t = a(i) ： a(i) = a(k) : a(k) = t End If Next i
整个排序过程中，数组中的数据比较次数和交换次数分别是（）
A. 10次和3次
B.10次和4次
C. 15次和3次
D.15次和10次
命题：杜宗飞
1.答案D.【解析】第一遍排序后的结果为：4，10，5，32，6，7，9，17，24；可知为升序排序。
按照冒泡排序规则，D选项无法满足要求。
2.答案A.【解析】交换次数越多，排序效率越低。
A选项是数据已经是降序，转变为升序交换次数最多。
3.答案C.【解析】第一次查找区间【1,8】中点为4，第二次查找区间为【1,3】中点为2，第三次查找区间为【3，3】查找成功
4.答案C.【解析】对分查找访问到的数字为8、21、3，顺序查找访问到的数字为1,2,3,5,8,13。
两者共同为8
5.答案D.【解析】字符比较大小，首先比较第一个字符，第一个字符相同再比较第二个字符。
第一次查找区间【1,9】中点为5，即feel；第二次查找区间为【1,4】中点为2，即cake；第三次查找区间为【3，4】中点为3，即data；第四次查找区间为【4，4】中点为4，即easy；查找成功
6.答案D.【解析】对分查找的数组必须有序（升序或降序）。
如果找不到，程序应该要输出未找到的相关提示信息。
字典按字母顺序排列，适合用对分查找。
顺序查找至少查找1次，最多查找n次，平均为（1+n）/2。
7.答案C.【解析】分析可知为冒泡排序，If a(j) > a(j - 1) Then可知为降序排序，排序一趟。
8.答案D.【解析】此题为冒泡排序变形，降序排序。
从前往后，两两比较。
9.答案B.【解析】此题为冒泡排序，由If a(j) < a(j - 1) Then可知为升序排序，总共交换次数为3次
10.答案B.【解析】此题为选择排序变形，tot为交换的次数
11.答案B.【解析】：这是课本上的选择排序，交换次数根据公式n(n-1)/2=5*4/2=10次。
或者采用代入法逐步计算：i=1时，代入内循环For j =2 to 5比较4次，内循环结束后k=5，k和i不相等，交换1次。
同理i=2、3、4依次代入……得出答案：B。
