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

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

1. 下列关于排序的说法，正确的是(  )。

{{ select(1) }}

• 冒泡排序是最快的排序算法之一。
• 快速排序通常是不稳定的。
• 最差情况，N个元素做归并排序的时间复杂度为 O(N)。
• 以上均不正确。

2. 下面的程序属于哪种算法(  )。

int pos[8];
void queen(int n)
{
    for (int i = 0; i < 8; i++)
    {
        pos[n] = i;
        bool attacked = false;
        for (int j = 0; j < n; j++)
            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j)
            {
                attacked = true;
                break;
            }
        if (attacked)
            continue;
        if (n == 7)
        {
            return;
        }
        else
        {
            queen(n + 1);
        }
    }
}

{{ select(2) }}

• 贪心算法
• 动态规划
• 深度优先搜索
• 广度优先搜索

3. 下面有关C++类的说法，错误的是（  ）。

{{ select(3) }}

• C++类对象销毁时，会执行析构函数。
• C++类可以通过定义构造函数实现自动类型转换。
• C++类可以通过重载 [ ] 运算符实现通过给定下标访问数组成员的元素。
• C++类可以包含任意类型的成员变量。

4. 一个连通的简单无向图，共有28条边，则该图至少有(  )个顶点。

{{ select(4) }}

• 6
• 7
• 8
• 9

5. 以下哪个方案不能合理解决或缓解哈希表冲突（  ）。

{{ select(5) }}

• 在每个哈希表项处，使用单链表管理该表项的冲突元素。
• 建立额外的单链表，用来管理所有发生冲突的元素。
• 使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。
• 用新元素覆盖发生冲突的哈希表项。

6. 已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正确的是(  )。

{{ select(6) }}

• 该树是平衡二叉树。
• 该树的高为4。
• 该树有4个叶节点。
• 以上说法都不对。

7. 以下关于二叉排序树的说法，正确的是（  ）。

{{ select(7) }}

• 二叉排序树的中序遍历序列一定是有序的。
• 在含n个节点的二叉排序树中查找元素，最差情况的时间复杂度为 O(log(n))。
• 二叉排序树一定是二叉平衡树。
• 以上说法都不对。

8. 已知 x 为double类型的变量，且值大于0，则下列表达式的值一定大于0的是(  )。

{{ select(8) }}

• sin(x) / x
• exp(x) - x
• log(x) - x
• x * x - x

9. 一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（  ）

{{ select(9) }}

• 60
• 70
• 15
• 20

10. 下列选项中，哪个可能是下图的深度优先遍历序列（  ）。

{{ select(10) }}

• 8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
• 7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。
• 8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
• 7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。

11. 下面schedule函数的时间复杂度为(  )。

#include <algorithm>
using namespace std;
struct activity
{
    int id, start, end;
};
bool compare(activity a, activity b)
{
    return a.end < b.end;
}
int schedule(int n, activity *p)
{
    sort(p, p + n, compare);
    int cnt = 0, end = 0;
    for (int i = 0; i < n; i++)
    {
        if (p[i].start >= end)
        {
            end = p[i].end;
            cnt++;
        }
    }
    return cnt;
}

{{ select(11) }}

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

12. 下面search函数的平均时间复杂度为(  )。

int search(int n, int *p, int target)
{
    int low = 0, high = n;
    while (low <= high)
    {
        int middle = (low + high) / 2;
        if (target == p[middle])
        {
            return middle;
        }
        else if (target > p[middle])
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }
    return -1;
}

{{ select(12) }}

• O(n)
• O( log(n) )
• O(1)
• 可能无法返回

13. 下面count_triple函数的时间复杂度为(  )。

int count_triple(int n)
{
    int cnt = 0;
    for (int a = 1; a <= n; a++)
        for (int b = a; a + b <= n; b++)
            for (int c = b; a + b + c <= n; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    return cnt;
}

{{ select(13) }}

• O(N)
• O(N²)
• O(N³)
• O(N⁴)

14. 下面程序的输出为（  ）。

#include <iostream>
using namespace std;
int down(int n)
{
    if (n <= 1)
        return n;
    return down(n - 1) + down(n - 2) + down(n - 3);
}
int main()
{
    cout << down(6) << endl;
    return 0;
}

{{ select(14) }}

• 6
• 13
• 20
• 无法正常结束。

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

int weight[4][4] = {
    {0, 2, 5, 8},
    {2, 0, 1, 7},
    {5, 1, 0, 4},
    {8, 7, 4, 0}};

{{ select(15) }}

• 6
• 7
• 8
• 9