错题整理
- 某算法计算时间表示为递推关系式：T(N)=N+T(N/2)，则该算法时间复杂度为（ ）
A. \(O(n^2)\)
B. \(O(N log N)\)
C. \(O(N)\)
D. \(O(1)\)
题解
根据递推关系式 \(T(N) = N + T(N/2)\)，每次的运算规模减少一半 \((N/2)\)，并且每次的运算时间是线性的 \((N)\)。这是一种典型的分治算法的时间复杂度形式。
通过递归展开可以观察到：
\(T(N) = N + T(N/2)\)
\(= N + (N/2 + T(N/4))\)
\(= N + N/2 + (N/4 + T(N/8))\)
\(= N + N/2 + N/4 + (N/8 + T(N/16))\)
...
可以看到，递归展开后，每一项都是 \(N\) 的一部分，并且会一直减少至最后变为 \(T(1)\)。
因此，总的时间复杂度为 \(N + N/2 + N/4 + N/8 + ... + T(1)\)，即 \(O(N)\)。
所以，该算法的时间复杂度为 \(O(N)\)
- 斐波那契数列的定义如下：\(F_1 = 1, F_2 = 1, F_n = F_{n - 1} + F_{n - 2}\) \((n>=3)\) 如果用下面的函数计算斐波那契数列的第 n 项，则其时间复杂度为（ ）
int F(int n) {
if (n <= 2)
return 1;
else
return F(n - 1) + F(n - 2);
}
A. \(O(1)\)
B. \(O(n)\)
C. \(O(n^2)\)
D. \(O(F_n)\)
题解
时间复杂度为 \(O(F_n)\)，其中 \(F_n\) 是斐波那契数列的第 \(n\) 项。
在这个递归函数中，每次递归调用都会生成两个新的递归调用，直到递归到基本情况\(（n <= 2）\)为止。在每一次递归调用中，需要计算 \(F_{n-1}\) 和 \(F_{n-2}\) 的值，这两个值又会依次生成更多的递归调用。
递归树的形状与斐波那契数列的定义相对应，每个节点的值都需要计算一次。因此，递归调用的次数与斐波那契数列的第 \(n\) 项的大小成正比。
所以，时间复杂度可以表示为 \(O(F_n)\)，其中 \(F_n\) 是斐波那契数列的第 n 项
- 二分搜索算法是利用（ ）实现的算法。
A. 分治策略
B. 动态规划
C. 贪心法
D. 回溯法
- 设一组初始记录关键字序列为 \((50，40，95，20，15，70，60，45)\)，则以增量 \(d=4\) 的一趟希尔排序结束后前4条记录关键字为（ ）
A. \(40，50，20，95\)
B. \(15，40，60，20\)
C. \(15，20，40，45\)
D. \(45，40，15，20\)
题解
将序列分成 \(4\) 组，分别是 \((50, 15)\)，\((40, 70)\)，\((95, 60)\)，\((20, 45)\)
对每一组进行插入排序：
对组 \((50, 15)\) 进行插入排序，结果为 \((15, 50)\)
对组 \((40, 70)\) 进行插入排序，结果为 \((40, 70)\)
对组 \((95, 60)\) 进行插入排序，结果为 \((60, 95)\)
对组 \((20, 45)\) 进行插入排序，结果为 \((20, 45)\)
得到一趟排序后的序列为 \((15, 40, 60, 20, 50, 70, 95, 45)\)
因此，一趟希尔排序结束后前 \(4\) 条记录关键字为 \((15, 40, 60, 20)\)
- 下列算法中，没有用到贪心思想的算法为（ ）
A. 计算无向图最小生成树的 \(Kruskal\) 算法。
B. 计算无向图点中每对节点之间最短路的 \(Floyd\) 算法。
C. 计算无向图单源最短路路径的 \(Dijkstra\) 算法。
D. 以上算法均使用了贪心的思想。
题解
选项 \(B\) 是没有用到贪心思想的算法。\(Floyd\) 算法是一种动态规划算法，通过对所有节点对进行遍历和更新，计算出每对节点之间的最短路径。它不涉及贪心选择，而是通过迭代计算和比较来确定最短路径，因此不属于贪心算法
组合题
已知两个长度均为 \(n\) 的有序数组 \(a1\) 和 \(a2\) (均为递增序，但不保证严
格单调递增），并且给定正整数 \(k\)（\(1 \le k \le 2n\)），求数组 \(a1\) 和 \(a2\) 归并排序后的数组里第k小的数值。试补全程序。
#include <bits/stdc++.h>
using namespace std;
int solve(int *al, int *a2, int n, int k){
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2){
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ①;
if (②){
if (cnt < k)
left1 = m1＋1;
else
right2 = m2 - 1;
}
else{
if (cnt < k)
left2 = m2 + 1;
else
right1 = m1 - 1;
}
}
if (③){
if (left1 == 0){
return a2[k - 1];
}
else{
int x = a1[left1 - 1],④;
return std::max(x, y);
}
}
else{
if (left2 == 0){
return a1[k - 1];
}
else{
x = a2[left2 - 1],⑤;
return std::max(x, y);
}
}
}
- ①处应填（ ）
A. (m1＋m2)*2
B. (m1-1) +(m2 - 1)
C. m1+m2
D. (m1+1)+(m2+1)
你的答案 D
正确答案 C
题解
在第10处填入选项C. m1 + m2 是正确的选择。
这是因为我们需要计算归并排序后的数组中，前m1 + m2个元素的个数，以确定我们当前的划分是否包含了第k小的数值。因为a1和a2都是递增的有序数组，我们可以通过比较m1和m2所对应的元素来确定划分的位置。
第10处的代码应该是 int cnt = m1 + m2;
- ②处应填（ ）
A. a1[m1]== a2[m2]
B. al[m1]<= a2[m2]
C. al[m1] >= a2[m2]
D. al[m1] != a2[m2]
你的答案 B
正确答案 B
题解
填入选项B. al[m1] <= a2[m2] 是正确的选择。
我们需要比较a1[m1]和a2[m2]的大小来判断当前的划分情况。如果a1[m1]小于等于a2[m2]，则意味着a1[m1]及其左侧的元素都不会是第k小的数值，我们需要将划分向右移动，即将left1更新为m1+1。否则，我们将划分向上移动，即将right2更新为m2-1。因此，选项B是正确的选择
- ③处应填（ ）
A. left1 == right1
B. left1< right1
C. left1 > right1
D. left1 I= right1
你的答案 C
正确答案 C
题解
当left1 > right1时，意味着数组a1的区间已经全部被排除，剩下的第k小的数值必然在数组a2中。因此，我们需要在a2中找到第k小的数值。选项C是正确的选择
- ④处应填（ ）
A. y=al[k-left2-1]
B. y = al[k - left2]
C. y = a2[k - left1 - 1]
D. y=a2[k - left1]
你的答案 C
正确答案 C
题解
选项C. y = a2[k - left1 - 1] 是正确的选择。
如果left1 == 0，意味着数组a1的所有元素都被排除了，剩下的第k小的数值必然在数组a2中。由于a2是递增序列，第k小的数值就是a2中的第k个元素，即a2[k - left1 - 1]
- ⑤处应填（ ）
A. y=a1[k - left2 - 1]
B. y = a1[k - left2]
C. y = a2[k - left1 - 1]
D. y = a2[k - left1]
你的答案 A
正确答案 A
题解
填入选项A. y = a1[k - left2 - 1] 是正确的选择。
如果left2 == 0，意味着数组a2的所有元素都被排除了，剩下的第k小的数值必然在数组a1中。由于a1是递增序列，第k小的数值就是a1中的第k个元素，即a1[k - left2 - 1]。选项A是正确的选择
给定一个长度为1,000,000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。
1.#include <stdlib.h>
2.#include <stdio.h>
3.
4.int a[1000001],n,ans = -1;
5.
6.void swap(int *a,int *b) {
7. int c;
8. c = *a;
9. *a = *b;
10. *b = c;
11.}
12.int FindKth(int left, int right, int n) {
13. int tmp,value,i,j;
14. if (left == right) return left;
15. tmp = rand()% (right - left) + left;
16. swap( &a[tmp], &a[left] );
17. value = ① ;
18. i = left;
19. j = right;
20. while (i < j) {
21.
22. while (i < j && ② ) j --;
23. if (i < j) {
24. a[i] = a[j];
25. i ++;
26. } else break;
27. while (i < j && ③ ) i ++;
28. if (i < j) {
29. a[j] = a[i];
30. j - -;
31. } else break;
32. }
33. a[i] = value;
34. if (i < n) return FindKth( ④ );
35. if (i > n) return FindKth( ⑤ );
36. return i;
37.}
38.
39.int main() {
40. int i;
41. int m = 1000000;
42. for (i = 1; i <= m; i ++) scanf("%d", &a[i]);
43. scanf("%d", &n);
44. ans = FindKth(1,m,n);
45. printf("%d\n", a[ans]);
46. return 0;
47.}
- ①处应填（ ）
A. a[tmp]
B. a[left]
C. a[right]
D. a[1]
你的答案 A
正确答案 B
- ②处应填（ ）
A. a[j]<value
B. a[j]>value
C. a[i]<a[j]
D. a[i]>a[j]
你的答案 B
正确答案 A
- ③处应填（ ）
A. a[i]<value
B. a[i]>value
C. a[i]<a[j]
D. a[i]>a[j]
你的答案 A
正确答案 B
- ④处应填（ ）
A. left,i,n
B. left,i-1,n
C. i+1,right,n
D. i,right,n
你的答案 C
正确答案 C
- ⑤处应填（ ）
A. left,i,n
B. left,i-1,n
C. i+1,right,n
D. i,right,n
你的答案 B
正确答案 B