初赛梳理IIII 算法常识

常规
1

1、使用快速排序算法对序列进行排序，最坏时间复杂度为（ ）。
A、O(n) B、O(n log n) C、O(n*n) D、O(n log n log n)
\color{green}{正解：C}

2、某算法计算时间表示为递推关系式：T(N)=N+T(N/2)，则该算法时间复杂度为（ ）。
A、O(n*n) B、O(N log N) C、O(N) D、O(1)
\color{green}{正解：C}
\color{red}{题解}

根据递推关系式 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)。

3、对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
A、O(mn+n^3) B、O(n^2） C、O((m+n)logn) D、((m+n^2)logn)
\color{green}{正解：B}
\color{red}{题解}

在每次迭代中，Dijkstra算法需要找到当前未访问的顶点中距离起始点最近的顶点，这个操作的时间复杂度是O(n)。
需要进行n次这样的操作，每次迭代中都会更新与当前顶点相邻的顶点的距离。
对于每个顶点，我们需要检查它的所有邻居，因此总共需要进行m次更新操作。

4、在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。
A、贪心 B、分治 C、递推 D、回溯
\color{green}{正解：A}
\color{red}{题解}

在哈夫曼编码中，根据字符出现的频率，通过构建一棵哈夫曼树来实现编码。
在构建哈夫曼树的过程中，每次选择频率最低的两个字符进行合并，生成新的节点，并更新频率。
这种选择策略是基于贪心思想，每次选择当前频率最低的字符进行合并，以期望获得整体上的最优编码。

5、从1到2018这2018个数中，共有( )个包含8的数。
A、543 B、544 C、545 D、546
\color{green}{正解：B}

6、在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（ ）。
A、程序运行时理论上所占的内存空间 B、程序运行时理论上所占的数组空间
C、程序运行时理论上所占的硬盘空间 D、程序源文件理论上所占的硬盘空间
\color{green}{正解：A}

7、已知有序表{13,18,24,35,47,50,62,83,90,115,134)，当折半查找值为90的元素时，查找成功的比较次数为（ ）。
A、3 B、5 C、2 D、4
\color{green}{正解：C}
\color{red}{题解}

第一次查找：
左边界left = 0，右边界right = 10，中间位置mid = (0 + 10) / 2 = 5
中间元素arr[mid] = arr[5] = 50
由于目标值90大于中间元素50，所以将左边界更新为mid + 1 = 6

第二次查找：
左边界left = 6，右边界right = 10，中间位置mid = (6 + 10) / 2 = 8
中间元素arr[mid] = arr[8] = 90
由于目标值90等于中间元素90，查找成功，返回比较次数
因此，查找成功的顺序为：5-8，共进行了2次比较

8、下列算法中，没有用到贪心思想的算法为（ ）。
A、计算无向图最小生成树的Kruskal算法。 B、计算无向图点中每对节点之间最短路的Floyd算法。
C、计算无向图单源最短路路径的Dijkstra算法。 D、以上算法均使用了贪心的思想。
\color{green}{正解：B}
\color{red}{题解}

Floyd算法是一种动态规划算法，通过对所有节点对进行遍历和更新，计算出每对节点之间的最短路径。
它不涉及贪心选择，而是通过迭代计算和比较来确定最短路径，因此不属于贪心算法。

#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);
		}
	}
}

1、①处应填（ ）。
A、(m1＋m2)*2 B、(m1-1) +(m2 - 1) C、m1+m2 D、(m1+1)+(m2+1)
\color{green}{正解：C}
\color{red}{题解}

我们需要计算归并排序后的数组中，前m1 + m2个元素的个数，以确定我们当前的划分是否包含了第k小的数值。
因为a1和a2都是递增的有序数组，我们可以通过比较m1和m2所对应的元素来确定划分的位置。

2、②处应填（ ）。
A、a1[m1]== a2[m2] B、al[m1]<= a2[m2] C、al[m1] >= a2[m2] D、al[m1] != a2[m2]
\color{green}{正解：B}
\color{red}{题解}

我们需要比较a1[m1]和a2[m2]的大小来判断当前的划分情况。
如果a1[m1]小于等于a2[m2]，则意味着a1[m1]及其左侧的元素都不会是第k小的数值，我们需要将划分向右移动，即将left1更新为m1+1。
否则，我们将划分向上移动，即将right2更新为m2-1。

#include <stdlib.h>  
#include <stdio.h>  
  
int a[1000001],n,ans = -1;  
  
void swap(int *a,int *b) {  
    int c;  
    c = *a;  
    *a = *b;  
    *b = c;  
}  
int FindKth(int left, int right, int n) {  
    int tmp,value,i,j;  
    if (left == right) return left;  
    tmp = rand()% (right - left) + left;  
    swap( &a[tmp], &a[left] );  
    value = ① ; 
    i = left;  
    j = right;  
    while (i < j) {  
  
        while (i < j && ② ) j --;  
        if (i < j) {  
            a[i] = a[j];  
            i ++;  
        } else break;  
        while (i < j &&  ③ ) i ++;  
        if (i < j) {  
            a[j] = a[i];  
            j - -;  
        } else break;  
    }  
    a[i] = value;  
    if (i < n) return  FindKth(  ④  );  
    if (i > n) return FindKth(  ⑤  );  
    return i;  
}  
  
int main() {  
    int i;  
    int m = 1000000;  
    for (i = 1; i <= m; i ++) scanf("%d", &a[i]);  
    scanf("%d", &n);  
    ans = FindKth(1,m,n);  
    printf("%d\n", a[ans]);  
    return 0;  
}

1、①处应填（ ）。
A、a[tmp] B、a[left] C、a[right] D、a[1]
\color{green}{正解：B}

2 个赞