2-1

用二分查找从100个有序整数中查找某数,最坏情况下需要比较的次数是:(3分)

  1. 7
  2. 10
  3. 50
  4. 99

作者: DS课程组

单位: 浙江大学

题目详情

A。 2的7次方 64 > 100/2

2-2

在下列查找的方法中,平均查找长度与结点个数无关的查找方法是: (3分)

  1. 顺序查找
  2. 二分法
  3. 利用哈希(散列)表
  4. 利用二叉搜索树

作者: DS课程组

单位: 浙江大学

C. 哈希散列、复杂度1

题目详情

2-3

将10个元素散列到100000个单元的哈希表中,是否一定产生冲突? (3分)

  1. 一定会
  2. 可能会
  3. 一定不会
  4. 有万分之一的可能会

作者: DS课程组

单位: 浙江大学

题目详情

B 可能会,又没说好怎么存储,可能就存一起了

2-4

对一个长度为 10 的排好序的表用二分法查找,若查找不成功,至少需要比较的次数是()。 (3分)

  1. 4
  2. 3
  3. 5
  4. 6

作者: 严冰

单位: 浙江大学城市学院

B。三次  8>10/2;

题目详情

2-5

(NeuDS_C++)在二叉排序树上查找关键码为28的结点(假设存在),则依次比较的关键码有可能是( )。 (3分)

  1. 30, 36, 28
  2. 38, 48, 28
  3. 48, 18, 38, 28
  4. 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分)

  1. 冒泡排序
  2. 插入排序
  3. 堆排序
  4. 快速排序

作者: 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分)

  1. 冒泡排序
  2. 希尔排序
  3. 归并排序
  4. 基数排序

作者: DS课程组

单位: 浙江大学

题目详情

A。每次排出一个最大值,所以是冒泡

2-8

下面四种排序算法中,稳定的算法是: (3分)

  1. 堆排序
  2. 希尔排序
  3. 归并排序
  4. 快速排序

作者: DS课程组

单位: 浙江大学

题目详情

稳定算法 C 归并 

堆排序快速排序希尔排序直接选择排序不是稳定的排序算法,而基数排序冒泡排序直接插入排序折半插入排序归并排序是稳定的排序算法。

2-9

对于序列{ 49,38,65,97,76,13,27,50 },按由小到大进行排序,下面哪一个是初始步长为4的希尔排序法第一趟的结果? (3分)

  1. 13,27,38,49,50,65,76,97
  2. 49,13,27,50,76,38,65,97
  3. 49,76,65,13,27,50,97,38
  4. 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. -1,4,8,9,20,7,15,7
  2. -1,7,15,7,4,8,20,9
  3. -1,4,7,8,20,15,7,9
  4. A,B,C均不对。

 

 

选C

链接:https://www.nowcoder.com/questionTerminal/a9b93bb3c120416380799043335bf63e?pos=43&mutiTagIds=586&orderByHotValue=0
来源:牛客网

如果你的问题是递减排序,就需要首先建立一个小根堆
因为其中有重复的关键字,因此当左右孩子相等并且需要和双亲调整时,原则上无论左右哪一个都可以,所以实际上这个问题会出现两个答案:
-1, 4, 7, 8, 20, 15, 7, 9 和-1, 4, 7, 8, 20, 7, 15, 9
一般算法都是和左子树的调整,这时就是前面的答案了

如果你的问题是递增排序,就需要先建立一个大根堆,不过这时只有唯一的答案:
20, 15, 7, 8, 9, -1, 7, 4