CSP初赛单选整理 - 无穷大？

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做（）次比较。

A. $n^2$ B. $n log n$ C. $2n$ D. $2n-1$

至少要做 $2n-1$ 次比较。下面是示例代码：

1
#include <iostream>
2
#include <vector>
3

4
int cnt = 0;
5

6
std::vector<int> mergeSortedArrays(const std::vector<int>& A, const std::vector<int>& B) {
7
    std::vector<int> result;
8
    int i = 0; // Index for array A
9
    int j = 0; // Index for array B
10

11
    while (i < A.size() && j < B.size()) {
12
        cnt++;
13
        if (A[i] <= B[j]) {
14
            result.push_back(A[i]);
15
            i++;
16
        } else {
17
            result.push_back(B[j]);
18
            j++;
19
        }
20
    }
21

22
    // Append remaining elements from A (if any)
23
    while (i < A.size()) {
24
        result.push_back(A[i]);
25
        i++;
26
    }
27

28
    // Append remaining elements from B (if any)
29
    while (j < B.size()) {
30
        result.push_back(B[j]);
31
        j++;
32
    }
33

34
    return result;
35
}
36

37
int main() {
38
    std::vector<int> A = {1, 3};
39
    std::vector<int> B = {2, 4};
40

41
    std::vector<int> merged = mergeSortedArrays(A, B);
42

43
    std::cout << "Merged Array: ";
44
    for (int num : merged) {
45
        std::cout << num << " ";
46
    }
47
    std::cout << std::endl;
48

49
    int comparisons = A.size() + B.size() - 1;
50
    std::cout << "Number of Comparisons: " << cnt << std::endl;
51

52
    return 0;
53
}

下面不属于贪心算法的是（）

A. 单源最短路径中的Dijkstra算法
B. 最小生成树的Prim算法
C. 最小生成树的Kruskal算法
D. 计算每对顶点最短路径的Floyd-Warshall算法

Disjsktra算法在松弛操作时用到了贪心的思想；Prim、Kruskal在生树时优先选择最小边；Floyd算法使用的是动态规划的操作。
一个深度为5（根节点深度为1）的完全3叉树，按前序遍历的顺序给节点从1开始编号，则第100号节点的父节点是第（）号。

A. $95$
B. $96$
C. $97$
D. $98$
- 前序遍历：根，左，右；
- 中序遍历：左，根，右；
- 后序遍历：左，右，根。
在三号节点下，一共有12个节点，故3号的兄弟节点为16号、29号。在二号节点下，一共有39个节点。故二号节点的兄弟节点为42号、82号。所以第100号节点在第二层的第三个节点下面。然后再多画几个节点，就能轻松得到答案为 C 了。
1. 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
2. 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）。
共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（）

A. $28$ B. $32$ C. $56$ D. $64$

题目有歧义，直接 $C_8^2$ 即可。
以下四种编程语言中，属于弱类型编程语言的是：

A. Java B. Go C. Rust D. C++
- 强类型：Java、C#、Python、Ruby、Erlang、GO、Rust……
- 弱类型：C、C++、Javascript、Perl、PHP、VB……
强类型语言是一种强制类型定义的语言，即一旦某一个变量被定义类型，如果不经强制转换，那么它永远就是该数据类型。而弱类型语言是一种弱类型定义的语言，某一个变量被定义类型，该变量可以根据环境变化自动进行转换，不需要经过现行强制转换。
竞赛图也叫有向完全图。每对顶点之间都有一条边相连的有向图称为竞赛图。5 个点的无标号竞赛图数是：（）。

A. $9$ B. $10$ C. $11$ D. $12$

答案为 D 。强联通，且大小为i的竞赛图个数为 $f_i=h_i-\Sigma_{j=1}^{i-1}h_j \times (_j^i) \times f_{i-j}$ 。
以下代码的输出结果是？
1 #include <iostream> 2 union U 3 { 4 bool flag1, flag2, flag3, flag4, flag5; 5 signed short a; 6 unsigned short b; 7 enum E 8 { 9 CardA = 0, 10 CardB = 1, 11 CardC = 2, 12 CardD = 142857 13 } e; 14 } u; 15 int main() 16 { 17 std::cout << sizeof(u) << std::endl; 18 return 0; 19 }
在这段C++代码中，定义了一个联合（union）类型 U，该联合包含了不同类型的成员变量，包括布尔型、有符号短整数、无符号短整数和枚举类型。联合类型允许在相同的内存位置存储不同类型的数据，但每次只能使用其中一个成员。

计算 sizeof(u) 将返回 u 这个联合类型的大小，即它所占用的内存字节数。在计算 sizeof 时，通常使用联合中最大成员的大小作为整个联合的大小。

在这个联合中，枚举类型 E 的最大值是 CardD，它是一个较大的整数，可能需要占用较多的内存。因此，整个联合 U 的大小将由 CardD 的大小决定。通常，int 类型占用4个字节，所以 CardD 的值为142857，占用4个字节。

因此，sizeof(u) 的输出结果应该是4，即联合 U 占用4个字节的内存空间。

输出结果是：
```
1
4
```
五个本质不同的店在没有重边或者自环的情况下，组成不同的无向图的个数是（）？

五个不同的点，最多可有 $4+3+2+1=10$ 条边。每条边有或没有，所以最终结果为 $2^{10}=1024$ 。

以下代码的输出结果为？

1
#include <iostream>
2
using namespace std;
3

4
int ans=0;
5
void dfs(int x){
6
    ++ans;
7
    if(x<=1) return;
8
    dfs(x/3);
9
    if(x/3+1<x) dfs(x/3+1);
10
    if(x/3+2<x) dfs(x/3+2);
11
}
12

13
int main(){
14
    dfs(10);
15
    cout<<ans<<endl;
16
    return 0;
17
}

中国计算机学会成立于（）年？1962年。
各种排序的比较：

支持与分享

评论区

目录