GESP 七级 · 2023 真题

定义变量 double x，如果下面代码输入为 100，输出最接近（ ）。

01#include <iostream>
02#include <string>
03#include <cmath>
04#include <vector>
05using namespace std;
06
07int main()
08{
09    double x;
10
11    cin >> x;
12    cout << log10(x) - log2(x) << endl;
13
14    cout << endl;
15    return 0;
16}

对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为（ ）。

01int s[MAX_N], f[MAX_N][MAX_N];
02int stone_merge(int n, int a[]) {
03    for (int i = 1; i <= n; i++)
04        s[i] = s[i - 1] + a[i];
05    for (int i = 1; i <= n; i++)
06        for (int j = 1; j <= n; j++)
07            if (i == j)
08                f[i][j] = 0;
09            else
10                f[i][j] = MAX_F;
11    for (int l = 1; l < n; l++)
12        for (int i = 1; i <= n - l; i++) {
13            int j = i + l;
14            for (int k = i; k < j; k++)
15                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
16        }
17    return f[1][n];
18}

下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是：5 1 7 3 5 9，则输出是（ ）。

01int a[2023], f[2023];
02int main()
03{
04    int n,i,j,ans = -1;
05
06    cin>>n;
07    for( i=1; i<=n; i++){
08        cin >> a[i];
09        f[i] = 1;
10    }
11
12    for( i=1; i<=n; i++)
13        for( j=1; j<i; j++)
14            if(a[j] < a[i])
15                f[i] = max(f[i], f[j]+1);
16    for( i=1; i<=n; i++){
17        ans = max(ans, f[i]);
18        cout << f[i] << "  ";
19    }
20
21    cout << ans << endl;
22    return 0;
23}

C++ 语言中，下列关于关键字 static 的描述不正确的是（ ）。

G 是一个非连通无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

哈希表长 $31$，按照下面的程序依次输入 4 17 28 30 4，则最后的 $4$ 存入哪个位置？（ ）

01#include <iostream>
02#include <string>
03#include <cmath>
04#include <vector>
05using namespace std;
06
07const int N=31;
08int htab[N],flag[N];
09int main()
10{
11    int n,x,i,j,k;
12
13    cin >> n;
14    for(i=0; i<n; i++){
15        cin >> x;
16        k=x%13;
17        while(flag[k]) k = (k+1)%13;
18        htab[k]=x;
19        flag[k]=1;
20    }
21
22    for(i=0; i<N; i++)
23        cout << htab[i] << "  ";
24
25    cout << endl;
26    return 0;
27}

某二叉树 T 的先序遍历序列为：{A B D F C E G H}，中序遍历序列为：{B F D A G E H C}，则下列说法中正确的是（ ）。

下面代码段可以求两个字符串 s1 和 s2 的最长公共子串（LCS），下列相关描述不正确的是（ ）。

01while (cin >> s1 >> s2)
02{
03    memset(dp, 0, sizeof(dp));
04    int n1 = strlen(s1), n2 = strlen(s2);
05    for (int i = 1; i <= n1; ++i)
06        for (int j = 1; j <= n2; ++j)
07            if (s1[i - 1] == s2[j - 1])
08                dp[i][j] = dp[i - 1][j - 1] + 1;
09            else
10                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
11    cout << dp[n1][n2] << endl;
12}

图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？（ ）

对关键字序列 {44, 36, 23, 35, 52, 73, 90, 58} 建立哈希表，哈希函数为 h(k)=k%7，执行下面的 Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为（ ）。

01#include <iostream>
02#include <string>
03#include <cmath>
04#include <vector>
05using namespace std;
06
07typedef struct Node{
08    int data;
09    struct Node *next;
10}Node;
11Node* hTab[7];
12int key[]={44, 36, 23, 35, 52, 73, 90, 58, 0};
13void Insert()
14{
15    int i,j;
16    Node *x;
17
18    for(i=0; key[i];i++){
19        j = key[i] % 7;
20        x=new Node;
21        x->data = key[i];
22        x->next = hTab[j];
23        hTab[j] = x;
24    }
25
26    return;
27}

学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 G，有向边 <U, V> 表示课程 U 是课程 V 的先修课，则要找到某门课程 C 的全部先修课下面哪种方法不可行？（ ）

一棵完全二叉树有 $2023$ 个结点，则叶结点有多少个？（ ）

用下面的邻接表结构保存一个有向图 G，InfoType 和 VertexType 是定义好的类。设 G 有 $n$ 个顶点、$e$ 条弧，则求图 G 中某个顶点 u（其顶点序号为 $k$）的度的算法复杂度是（ ）。

01typedef struct ArcNode{
02    int             adjvex;    // 该弧所指向的顶点的位置
03    struct ArcNode  *nextarc;  // 指向下一条弧的指针
04    InfoType        *info;     // 该弧相关信息的指针
05} ArcNode;
06typedef struct VNode{
07    VertexType data;      // 顶点信息
08    ArcNode    *firstarc; // 指向第一条依附该顶点的弧
09} VNode, AdjList[MAX_VERTEX_NUM];
10typedef struct{
11    AdjList vertices;
12    int     vexnum, arcnum;
13    int     kind;          // 图的种类标志
14} ALGraph;

给定一个简单有向图 G，判断其中是否存在环路的下列说法哪个最准确？（ ）

从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 $4$ 个序列中符合广度优先的序列有几个？（ ）

{v1 v2 v3 v4 v5}，{v1 v2 v4 v3 v5}，{v1 v4 v2 v3 v5}，{v1 v2 v4 v5 v3}

小杨这学期准备参加 GESP 的 $7$ 级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。（ ）

01int main()
02{
03    double x;
04
05    do{
06        cin >> x;
07        x=x/180*3.14;
08    }while(int(sin(x)*sin(x)+cos(x)*cos(x)) == 1);
09    cout << "//" << sin(x) << "  " << cos(x);
10
11    cout << endl;
12    return 0;
13}

小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。（ ）

假设一棵完全二叉树共有 $N$ 个节点，则树的深度为 $\log(N)+1$。（ ）

给定一个数字序列 $A_1, A_2, A_3, \ldots, A_n$，要求 $i$ 和 $j$（$1\le i\le j\le n$），使 $A_i+\ldots+A_j$ 最大，可以使用动态规划方法来求解。（ ）

若变量 x 为 double 类型正数，则 log(exp(x)) > log10(x)。（ ）

简单有向图有 n 个顶点和 e 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 u 的度的时间复杂度一样。（ ）

某个哈希表键值 x 为整数，为其定义哈希函数 H(x)=x%p，则 p 选择素数时不会产生冲突。（ ）

动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。（ ）

广度优先搜索（BFS）能够判断图是否连通。（ ）

在 C++ 中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。（ ）