GESP C++ 八 级 2024年3月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 2 分，共 30 分）

1. 为丰富食堂菜谱，炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉4种，切法有肉排、肉块、肉末3种，配菜有圆白菜、油菜、豆腐3种，辣度有麻辣、微辣、不辣3种。不考虑口感的情况下，选1种肉、1种切法、1种配菜、1种辣度产生一道菜（例如：麻辣牛肉片炒豆腐），这样能产生多少道菜？

{{ select(1) }}

• 13
• 42
• 63
• 108

2. 已知袋中有2个相同的红球、3个相同的绿球、5个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列？

{{ select(2) }}

• 6
• 1440
• 2520
• 3628800

3. 以下二维数组的初始化，哪个是符合语法的？

{{ select(3) }}

• int a[][] = {{1, 2}, {3, 4}};
• int a[][2] = {};
• int a[2][2] = {{1, 2, 3}, {4, 5, 6}};
• int a[2][] = {{1, 2, 3}, {4, 5, 6}};

4. 下面有关C++拷贝构造函数的说法，错误的是？

{{ select(4) }}

• 必须实现拷贝构造函数，否则一定会出现编译错误。
• 对象作为函数参数、以值传递方式传入函数时，会自动调用拷贝构造函数。
• 对象作为函数返回值、以值传递方式从函数返回时，会自动调用拷贝构造函数。
• 使用一个对象初始化另一个对象时，会自动调用拷贝构造函数。

5. 使用邻接表表达一个无向简单图，图中包含v个顶点、e条边，则该表中边节点的个数为？

{{ select(5) }}

• v x (v-1)
• v x v
• 2 x e
• e

6. 关于生成树的说法，错误的是？

{{ select(6) }}

• 一个无向连通图可以有多个生成树。
• 一个无向图，只要连通，就一定有生成树。
• n个顶点的无向完全图，有 n^n-2 棵生成树。
• n个顶点的无向图，生成树包含n - 1条边。

7. 已知三个double类型的变量a、b和theta分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的周长？

{{ select(7) }}

• a * b * sin(theta) / 2
• a + b + (a + b) * sin(theta) / 2
• a * b * cos(theta) / 2
• a + b + sqrt(a * a + b * b - 2 * a * b * cos(theta))

8. 在有n个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为？

{{ select(8) }}

• O(1)、O(n)
• O(1)、O(log n)
• O(log n)、O(log n)
• O(log n)、O(n)

9. 如下图所示，半径为r、圆心角为t（弧度）的扇形，下面哪个表达式能够求出顶部阴影部分的面积？

{{ select(9) }}

• r * r * sin(t) / 2
• r * r * t / 2
• r * r * (t - sin(t))
• r * r * (t - sin(t)) / 2

10. 下面程序的时间复杂度为？

int fib(int n)
{
    if (n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

{{ select(10) }}

• O( 2ⁿ )
• $O(\phi^n), \text{ 其中 } \phi = \frac{\sqrt{5}+1}{2}$
• O(n)
• O(1)

11. 下面程序的时间复杂度为？

int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    return choose(n - 1, m - 1) + choose(n - 1, m);
}

{{ select(11) }}

• O( 2ⁿ )
• O( 2^m x (n-m) )
• O( C(n, m) )
• O( m x (n-m) )

12. 下面程序的时间复杂度为？

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve()
{
    for (int n = 2; n <= MAXN; n++)
    {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++)
        {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

{{ select(12) }}

• O(n)
• O(n x log n)
• O(n x log log n)
• O( n² )

13. 下面程序的输出为？

#include <iostream>
using namespace std;
int a[10][10];
int main()
{
    int m = 5, n = 4;
    for (int x = 0; x <= m; x++)
        a[x][0] = 1;
    for (int y = 1; y <= n; y++)
        a[0][y] = 1;
    for (int x = 1; x <= m; x++)
        for (int y = 1; y <= n; y++)
            a[x][y] = a[x - 1][y] + a[x][y - 1];
    cout << a[m][n] << endl;
    return 0;
}

{{ select(13) }}

• 4
• 5
• 126
• 3024

14. 下面程序的输出为？

#include <iostream>
using namespace std;
int main()
{
    int cnt = 0;
    for (int x = 0; x <= 10; x++)
        for (int y = 0; y <= 10; y++)
            for (int z = 0; z <= 10; z++)
                if (x + y + z == 15)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(14) }}

• 90
• 91
• 96
• 100

15. 下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为？

int weight[4][4] = {
    {0, 1, 7, 100},
    {1, 0, 5, 15},
    {7, 5, 0, 6},
    {100, 15, 6, 0}};

{{ select(15) }}

• 100
• 16
• 12
• 13