2023-12-Level-7

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

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
    double x;
    cin >> x;
    cout << log10(x) - log2(x) << endl;
    cout << endl;
    return 0;
}

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

int s[MAX_N], f[MAX_N][MAX_N];
int stone_merge(int n, int a[]) {
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                f[i][j] = 0;
        else
            f[i][j] = MAX_F;
        for (int l = 1; l < n; l++)
            for (int i = 1; i <= n - 1; i++)
            int j = i + 1;
        for (int k = i; k < j; k++)
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
    }
    return f[1][n];
}

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

int a[2023], f[2023];
int main()
{
    int n, i, j, ans = -1;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    for (i = 1; i <= n; i++) {
        ans = max(ans, f[i]);
        cout << f[i] << " ";
    }
    cout << ans << endl;
    return 0;
}

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

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

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

#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

const int N=31;
int htab[N], flag[N];
int main()
{
    int n, x, i, j, k;
    
        cin >> n;
        for (i=0; i<n; i++) {
            cin >> x;
            k=x%13;
            while (flag[k]) k = (k+1)%13;
            htab[k]=x;
            flag[k]=1;
        }
        for (i=0; i<N; i++)
            cout << htab[i] << " ";
        cout << endl;
    
    return 0;
}

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

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

while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n1][n2] << endl;
}

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

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

#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

typedef struct Node{
    int data;
    struct Node *next;
} Node;

Node* hTab[7];
int key[] = {44, 36, 23, 35, 52, 73, 90, 58, 0};

void Insert()
{
    int i, j;
    Node *x;
    for (i = 0; key[i]; i++) {
        j = key[i] % 7;
        x = new Node;
        x->data = key[i];
        x->next = hTab[j];
        hTab[j] = x;
    }
}

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

一棵完全二叉树有 2023 个结点，则叶结点有多少个？()

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

typedef struct ArcNode{
    int     adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
    InfoType *info; // 该弧相关信息的指针
} ArcNode;
typedef struct VNode{
    VertexType data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
    AdjList vertices;
    int     vexnum, arcnum;
    int     kind; // 图的种类标志
} 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级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。（）

int main()
{
    double x;
    do {
        cin >> x;
        x = x / 180 * 3.14;
    } while (int(sin(x) * sin(x) + cos(x) * cos(x)) == 1);
    cout << " // " << sin(x) << " " << cos(x);
    cout << endl;
    return 0;
}

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

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

给定一个数字序列 A1, A2, A3, ..., An，要求 i 和 j （1<=i<=j<=n），使 A1+...+Aj 最大，可以使用动态规划方法来求解。（）

若变量 x 为 double 类型正数，则 $\log(\exp(x)) > \log_{10}(x)$ 。（）

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

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

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

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

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