题

折半查找在有序数组A中查找特定的记录K：通过比较K和数组中的中间元素A[mid]进行，如果相等，则算法结束；如果K小于A[mid]，则对数组的前半部分进行折半查找；否则对数组的后半部分进行折半查找。根据上述描述，折半查找算法采用了（）算法设计策略。对有序数组（3，14，27，39，42，55，70，85，93，98），成功查找和失败查找所需要的平均比较次数分别是（(假设查找每个元素的概率是相同的)

问题1

A.分治
B.动态规划
C.贪心
D.回溯

问题2

A.29/10和29/11
B.30/10和30/11
C.29/10和39/11
D.30/10和40/11

分析

构造对应的折半查找判定树如下：

根为42，即：第5个元素，算法：(1 + 10) / 2 = 5
第二层结点：
- 第2个元素14，算法：(1+4)/2 = 2
- 第8个元素85，算法：(6+10)/2 = 8
第三层结点：
- 第1个元素3
- 第3个元素27，算法：(3+4)/2 = 3
- 第6个元素55，算法：(6+7)/2 = 6
- 第9个元素93，算法：(9+10)/2 = 9
第四层结点：
- 39
- 70
- 98

成功查找次数

41：在第一层，所以比较1次就能找到
14、85：在第二层，所以比较2次能找到
3、27、55、98：在第三层，所以比较3次能找到
39、70、98：在第四层，所以比较4次能找到

总共查找次数：1+2*2+3*4+4*3 = 29
平均查找次数：29次/10个

失败查找次数

折半查找失败的过程，可以理解为对处于这10个元素之前的间隔位置的数进行了查找，对各个元素间隔进行编号依次为1、2、3、.….、11，此时：

1号间隔位于3的左侧（要查找的数字比3还小），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3;
2号位置位于3和14之间（要查找的数字在3-14之间），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3;
3号位置位于14和27之间，此时需要分别与元素42、14、27比较后才会查找失败，比较次数为3；
4号位置位于27和39之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4;
5号位置位于39和42之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4;
6号位置位于42和55之间，此时需要分别与元素42、85、55比较后才会查找失败，比较次数为3；
7号位置位于55和77之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4;
8号位置位于77和85之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4;
9号位置位于85和93之间，此时需要分别与元素42、85、93比较后才会查找失败，比较次数为3；
10号位置位于93和98之间，此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4;
11号位置位于98右侧（要查找的数字比98还大），此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4;

此时平均查找次数为 （3*5+4*6）/11=39/11

因此第二问选择C选项。

题

n个关键码构成的序列[k1,k2,..Kn}当且仅当满足下列关系时称其为堆。

以下关键码序列中，（）不是堆。
A.15,25,21,53,73, 65,33
B.15,25,21,33,73,65,53
C.73,65,25,21,15,53,33
D.73,65,25,33,53,15,21

答案

根据顺序应该是大很多，如下：

25 比左孩子小，不符合

题

对数组A=(2,8,7,1,3,5,6,4)构建大顶堆为（）（用数组表示）。
A.(1,2,3,4,5,6,7,8)
B.(1,2,5,4,3,7,6,8)
C.(8,4,7,2,3,5,6,1)
D.(8,7,6,5,4,3,2,1)

答案

过程如下：

将待排序的关键字分到一棵完全二叉树的各个结点中：

根是第1个元素
第2层是第 2、3 元素
第3层是第 4-7 元素
…以此类推

如果父元素比子元素小，就交换位置，过程如下图：

最终结果：

题

对n个数排序，最坏情况下时间复杂度最低的算法是（）排序算法。
A.插入
B.冒泡
C.归并
D.快速

答案

注意：时间复杂度最低，就是执行最快

A.插入、B.冒泡、D.快速最坏的情况是 O(n²)

C.归并，O(nlog₂n）

题

设用线性探查法解决冲突构造哈希表，且哈希函数为H(key)=key%m，若在该哈希表中查找某关键字e是成功的且与多个关键字进行了比较，则（）。

A.这些关键字形成一个有序序列
B.这些关键字都不是e的同义词
C.这些关键字都是e的同义词
D.这些关键字的第一个可以不是e的同义词

分析

1. 先计算每个关键字的哈希地址（m = 10）

H(14) = 14 % 10 = 4
H(24) = 24 % 10 = 4
H(15) = 15 % 10 = 5

2. 插入过程

插入 14：地址 4 为空，直接放入。
表：[_, _, _, _, 14, _, _, _, _, _]
插入第一个 24：地址 4 被 14 占据（同义词冲突），线性探查下一个地址 5，地址 5 为空，放入。
表：[_, _, _, _, 14, 24, _, _, _, _]
插入第二个 24：地址 4 被 14 占据，探查地址 5 被第一个 24 占据，再探查地址 6，放入。
表：[_, _, _, _, 14, 24, 24, _, _, _]
插入 15：计算地址为 5，但地址 5 已被 24 占据。这里发生了冲突，但 15 和 24 不是同义词（因为 (H(15)=5)，(H(24)=4)）。于是继续探查地址 6，也被 24 占据，再探查地址 7，放入 15。
表：[_, _, _, _, 14, 24, 24, 15, _, _]

3. 查找 15 的过程

现在我们来查找关键字 15：

计算哈希地址：(H(15) = 5)。
去地址 5 比较，关键字是 24，不是 15。
- 这里的 24 和 15 不是同义词，因为它们的原始哈希地址不同（4 vs 5）。
线性探查下一个地址 6，关键字是 24，也不是 15。
再探查地址 7，关键字是 15，查找成功。

4. 回到题目和选项

在这个查找 15 的成功案例中，我们比较了三个关键字：24（地址5）、24（地址6）、15（地址7）。

第一个被比较的关键字是 24，它和 15 不是同义词。
这就证明了，在使用线性探查法的成功查找中，第一个被比较的关键字确实可以不是目标关键字的同义词。

因此，选项 D. 这些关键字的第一个可以不是e的同义词 是完全正确的✅。

题

对数组A= (2,8,7,1,3,5,6,4) 构建大顶堆为（）（用数组表示）。

A.(1,2,3,4,5,6,7,8)
B.(1,2,5,4,3,7,6,8)
C.(8,4,7,2,3,5,6,1)
D.(8,7,6,6,5,4,3,2,1)

分析

先根据数组构建二叉树：

最后一个节点 4 与父结点 1 ，构造大顶堆，结果如下：

从后往前构造大顶堆，5、6 和父结点 7 这3个父子节点是大顶堆，不动

从后往前构造大顶堆，4、3 和父结点 8 这3个父子节点是大顶堆，不动

从后往前构造大顶堆，8、7 和父结点 2 这3个父子节点不是大顶堆，移动，如下图：

同理，从后往前构造大顶堆，4、3 和父结点 2 这3个父子节点不是大顶堆，移动，如下图：

到此为止，完全是大顶堆，用数组表示：[8,4,7,2,3,5,6,1]

题

最大子段和问题描述为，在n个整数（包含负数）的数组A中，求元素之和最大的非空连续子数组，如数组 A= (-2, 11, -4, 13, -5, -2)，其子数组 B= (11, -4, 13) 具有最大子段和 20（11-4+13=20）。求解该问题时，可以将数组分为两个n/2个整数的子数组最大子段和或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为（）。

A. O(nlgn)
B. O(n^2)
C. O(n^2lgn)
D. O(n^3)

分析

根据题干描述“求解该问题时，可以将数组分为两个 n/2 个整数的子数组最大子段和或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和”。可知采用的是分治法求解，时间复杂度为 O(nlgn)。

原文出处：/show_1GW16hc4oLUa.html