内容发布更新时间 : 2024/5/10 9:36:03星期一 下面是文章的全部内容请认真阅读。
第二轮 排序和查找算法综合1
行政班：
教学班： 姓名： 学号： 课本上的排序算法，补充完整 冒泡排序 变量n代表数组元素的个数 选择排序:升序排序 升序排序： For i = 1 To n-1 k = i For j For i = 1 To n-1 For j = n To i = i + 1 To n + 1 Step -1 If If a(j) < a(k) Then k = j a(j)
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。