GESP 八级 · 2024 真题

为丰富⾷堂菜谱，炒菜部进⾏头脑风暴。⾁类有鸡⾁、⽜⾁、⽺⾁、猪⾁$4$种，切法有⾁排、⾁块、⾁末$3$种，配菜有圆⽩菜、油菜、⾖腐$3$种，辣度有⿇辣、微辣、不辣$3$种。不考虑⼝感的情况下，选$1$种⾁、$1$种切法、$1$种配菜、$1$种辣度产⽣⼀道菜（例如：⿇辣⽜⾁⽚炒⾖腐），这样能产⽣多少道菜？（ ）。

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

以下⼆维数组的初始化，哪个是符合语法的？（ ）。

下⾯有关C++拷贝构造函数的说法，错误的是（ ）。

使⽤邻接表表达⼀个⽆向简单图，图中包含 v 个顶点、e 条边，则该表中边节点的个数为（ ）。

关于⽣成树的说法，错误的是（ ）。

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

在有 $n$ 个元素的⼆叉排序树中进⾏查找，其最好、最差时间复杂度分别为（ ）。

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

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

01int fib(int n) {
02    if (n <= 1)
03        return 1;
04    return fib(n - 1) + fib(n - 2);
05}

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

01int choose(int n, int m) {
02    if (m == 0 || m == n)
03        return 1;
04    return choose(n - 1, m - 1) + choose(n - 1, m);
05}

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

01int primes[MAXP], num = 0;
02bool isPrime[MAXN] = {false};
03void sieve() {
04    for (int n = 2; n <= MAXN; n++) {
05        if (!isPrime[n])
06            primes[num++] = n;
07        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
08            isPrime[n * primes[i]] = true;
09            if (n % primes[i] == 0)
10                break;
11        }
12    }
13}

下⾯程序的输出为（ ）。

01#include <iostream>
02using namespace std;
03
04int a[10][10];
05int main() {
06    int m = 5, n = 4;
07    for (int x = 0; x <= m; x++)
08        a[x][0] = 1;
09    for (int y = 1; y <= n; y++)
10        a[0][y] = 1;
11    for (int x = 1; x <= m; x++)
12        for (int y = 1; y <= n; y++)
13            a[x][y] = a[x - 1][y] + a[x][y - 1];
14    cout << a[m][n] << endl;
15    return 0;
16}

下⾯程序的输出为（ ）。

01#include <iostream>
02using namespace std;
03
04int main() {
05    int cnt = 0;
06    for (int x = 0; x <= 10; x++)
07        for (int y = 0; y <= 10; y++)
08            for (int z = 0; z <= 10; z++)
09                if (x + y + z == 15)
10                    cnt++;
11    cout << cnt << endl;
12    return 0;
13}

下⾯的程序使⽤邻接矩阵表达的带权⽆向图，则从顶点0到顶点3的最短距离为（ ）。

01int weight[4][4] = {
02    {  0,   1,   7, 100},
03    {  1,   0,   5,  15},
04    {  7,   5,   0,   6},
05    {100,  15,   6,   0}};

已知 int 类型的变量 $a$ 和 $b$ ，则执⾏语句 a, b = b, a; 后，变量 $a$ 和 $b$ 的值会互换。

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

孙⼦定理是求解⼀次同余⽅程组的⽅法，最早见于中国南北朝时期（公元5世纪）的数学著作《孙⼦算经》。⼜称中国余数定理，是中国数学史上的⼀项伟⼤成就。

$N$ 个顶点的⽆向完全图有 $N\times (N-1)$ 条边。

为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为 $O(1)$。

求⼀个包含 $v$ 个顶点、$e$ 条边的带权连通⽆向图的最⼩⽣成树，Prim算法的时间复杂度为 $O(v\times e)$ 。

已知int类型的变量 $a$ 、$b$ 和 $c$ 中分别存储着⼀个三角形的三条边长，则这个三角形的⾯积可以通过表达式 sqrt((a + b + c) * (b + c - a) * (a + c - b) * (a + b - c)) / 4 求得。

可以使⽤深度优先搜索算法判断图的连通性。

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

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