GESP 八级 · 2023 真题

⼩杨要从 $A$ 城到 $B$ 城，⼜想顺路游览⼀番。他有两个选项：$1$、坐⾼铁路到 $C$ 城游览，再坐⾼铁或飞机到 $B$ 城；$2$、坐船到 $D$ 城游览，再坐船、⾼铁或飞机到 $B$ 城。请问⼩杨从 $A$ 城到 $B$ 城共有⼏种交通⽅案可以选择？（ ）

以下哪个函数声明是符合语法的 ，且在调⽤时可以将⼆维数组的名字作为实际参数传递给形式参数 $a$ ？ ( ) 。

下⾯有关 C++ 类和对象的说法 ，错误的是（ ）

使⽤邻接矩阵表达 $n$ 个顶点的有向图 ，则该矩阵的大小为（ ）

$5$ 位同学排队，其中⼀位同学不能排在第⼀，则共有多少种可能的排队⽅式？

⼀个⽆向图包含 $n$ 个顶点 ，则其最⼩⽣成树包含多少条边？（ ）

已知三个 double 类型的变量 $a、b$ 和 $theta$ 分别表⽰⼀个三角形的两条边长及⼆者的夹角（弧度），则下列哪个表达式可以计算这个三角形的⾯积？（ ）。

对有 $n$ 个元素的⼆叉排序树进⾏中序遍历，其时间复杂度是（ ）

假设输⼊参数 $m$ 和 $n$ 满⾜ $m≤n$，则下⾯程序的最差情况的时间复杂度为（ ）

01int gcd(int m, int n){
02    while (m > 0){
03        int t = m;
04        m = n % m;
05        n = t;
06    }
07    return n;
08}

下⾯程序的时间复杂度为（ ）。

01long long power_mod(long long a, long long n, long long mod){
02    if (n == 0)
03        return 1;
04    a = a % mod;
05    if (n == 1)
06        return a;
07    long long pw = power_mod(a, n / 2, mod);
08    long long pw2 = pw * pw % mod;
09    if (n % 2 == 0)
10        return pw2;
11    return pw2 * a % mod;
12}

下⾯程序的时间复杂度为（ ）

01int record_choose[MAXN][MAXN];
02int choose(int n, int m){
03    if (m == 0 || m == n)
04        return 1;
05    if (record_choose[n][m] == 0)
06        return record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
07    return record_choose[n][m];
08}

下⾯的程序使⽤出边的邻接表表达有向图，则下列选项中哪个是它表达的
图？（ ）。

01#include <iostream>
02
03struct Edge {
04    int e;
05    Edge * next;
06};
07struct Node {
08    Edge * first;
09}
10
11int main() {
12    Edge e[5] = {{1, nullptr}, {2, &e[2]}, {3, nullptr}, {3, nullptr}, {0, nullptr}};
13    Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
14    ; // 其他处理
15}

下⾯程序的输出为（ ）

01#include <iostream>
02using namespace std;
03
04int main(){
05    int cnt = 0;
06    for (int a = 1; a <= 10; a++)
07        for (int b = 1; b <= 10; b++)
08            for (int h = 1; h <= 10; h++)
09                if ((a + b) * h == 20)
10                    cnt++;
11    cout << cnt << endl;
12    return 0;
13}

下⾯程序的输出为（ ）

01#include <iostream>
02using namespace std;
03
04int main() {
05    const int N = 30;
06    int cnt = 0;
07    for (int a = 1; a <= N; a++)
08        for (int b = a; a + b <= N; b++)
09            for (int c = b; a + b + c <= N; c++)
10                if (a * a + b * b == c * c)
11                    cnt++;
12    cout << cnt << endl;
13    return 0;
14}

下⾯的程序中 ，⼆维数组 $h$ 和 $v$ 分别代表如下图所⽰的⽹格中的⽔平边的时间消耗和垂直边的时间消耗。 程序使⽤动态规划计算从左下角到右上角的最⼩时间消耗 ，则横线处应该填写下列哪个选项的代码？（ ）。

C++ 语⾔⾮常强⼤ ，可以⽤来求解⽅程的解 。例如 ，如果变量 $x$ 为 double 类型的变量，则执⾏语句 x * 2 - 4 = 0; 后，变量 $x$ 的值会

⼀个袋⼦中有 $3$ 个完全相同的红⾊⼩球、$2$ 个完全相同的蓝⾊⼩球 。每次从中取出 $1$ 个 ，且不放回袋⼦ ，这样 进⾏ $3$ 次后 ，将取出的⼩球依次排列 ，则可能的颜⾊顺序有 $7$ 种

杨辉三角 ，是⼆项式系数的⼀种三角形排列 ，在中国南宋数学家杨辉 $1261$ 年所著的《详解九章算法》⼀书中 出现 ，是中国数学史上的⼀项伟⼤成就

$N$ 个顶点的有向完全图（不带⾃环）有 $N \times (N-1)/2$ 条

如果待查找的元素确定 ，只要哈希表的⼤⼩不⼩于查找元素的个数 ，就⼀定存在不会产⽣冲突的哈希函数。

动态规划算法的时间复杂度⼀般为：必要状态的数量 ，乘以计算⼀次状态转移⽅程的时间复杂度。

已知 int 类型的变量 $a 、 b$ 和 $h$ 中分别存储着⼀个梯形的顶边长、底边长和⾼ ，则这个梯形的⾯积可以通 过表达式 $(a + b) \times h/2$ 求得

判断图是否连通只能⽤⼴度优先搜索算法实现

在 $N$ 个元素的⼆叉排序树中查找⼀个元素 ，最好情况的时间复杂度是 $O(\log N)$。

给定 double 类型的变量 $x$，且其值⼤于等于 ，我们可以通过⼆分法求出的 $\sqrt{x}$ 近似值