2-1
用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：(3分)
- 7
- 10
- 50
- 99
作者: DS课程组
单位: 浙江大学
A。 2的7次方 64 > 100/2
2-2
在下列查找的方法中，平均查找长度与结点个数无关的查找方法是： (3分)
- 顺序查找
- 二分法
- 利用哈希（散列）表
- 利用二叉搜索树
作者: DS课程组
单位: 浙江大学
C. 哈希散列、复杂度1
2-3
将10个元素散列到100000个单元的哈希表中，是否一定产生冲突？ (3分)
- 一定会
- 可能会
- 一定不会
- 有万分之一的可能会
作者: DS课程组
单位: 浙江大学
B 可能会，又没说好怎么存储，可能就存一起了
2-4
对一个长度为 10 的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是（）。 (3分)
- 4
- 3
- 5
- 6
作者: 严冰
单位: 浙江大学城市学院
B。三次 8>10/2;
2-5
(NeuDS_C++)在二叉排序树上查找关键码为28的结点（假设存在），则依次比较的关键码有可能是（ ）。 (3分)
- 30, 36, 28
- 38, 48, 28
- 48, 18, 38, 28
- 60, 30, 50, 40, 38, 36
作者: 姚志军
单位: 广东东软学院
C。
D选项没查到28，而且查到30之后应该搜索30以下，下一个却是50
A，30之后 36 与D选项同理
B. 38之后应该比38小，48不对。
2-6
下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2） (3分)
- 冒泡排序
- 插入排序
- 堆排序
- 快速排序
作者: DS课程组
单位: 浙江大学
B，插入排序可能插在第一个，所有元素后移一位。
2-7
对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是： (3分)
- 冒泡排序
- 希尔排序
- 归并排序
- 基数排序
作者: DS课程组
单位: 浙江大学
A。每次排出一个最大值，所以是冒泡
2-8
下面四种排序算法中，稳定的算法是： (3分)
- 堆排序
- 希尔排序
- 归并排序
- 快速排序
作者: DS课程组
单位: 浙江大学
稳定算法 C 归并
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
2-9
对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？ (3分)
- 13,27,38,49,50,65,76,97
- 49,13,27,50,76,38,65,97
- 49,76,65,13,27,50,97,38
- 97,76,65,50,49,38,27,13
作者: DS课程组
单位: 浙江大学
B
步长是4应该是 49 76 50 排序，是B满足
2-10
有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）。 (3分)
- -1，4，8，9，20，7，15，7
- -1，7，15，7，4，8，20，9
- -1，4，7，8，20，15，7，9
- A，B，C均不对。
京公网安备 11010502036488号