第 1 题 在 C++中，下面哪个关键字用于声明一个变量，其值不能被修改? ( )

第 2 题 八进制数 $12345678_8$ 和 $07654321_8$ 的和为( )。

第 3 题 阅读下述代码，请问修改 data 的 value 成员以存储 3.14，正确的方式是( )

union Data {
int num;
float value;
char symbol;
};
union Data data;

第 4 题 假设有一个链表的节点定义如下:

struct Node{
  int data;
  Node* next; 

};

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新的节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）

第 5 题 根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为( )

第 6 题 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有( ) 种选择时间段的方案

第 7 题 以下关于高精度运算的说法错误的是( )。

第 8 题 后缀表达式“6 2 3 + - 3 8 2 / + * 2 3 +”对应的中缀表达式是( )。

第 9 题 数 $101010_2$ 和 $166_8$的和为( )

第 10 题 假设有一组字符{a,b,c,d,e,f}，对应的频率分别为 5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码?( )

第 11 题 给定一棵二叉树，其前序遍历结果为: ABDECFG，中序遍历结果为: DEBACFG。请问这棵树的正确后序遍历结果是什么?( )

第 12 题 考虑一个有向无环图，该图包含 4 条有向边:(1,2), (1,3), (2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序?( )

第 13 题 在计算机中，以下哪个选项描述的数据存储容量最小?( )

第 14 题 一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合?( )

第 15 题 以下哪个不是操作系统?( )

二、判断题（每题 2 分，共 20 分）

第 16 题

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

double f(double a, double b, double c) {
    double s = (a + b + c) / 2;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    cout.flags(ios::flxed);
    cout.precision(4);

    int a, b, c;
    cin >> a >> b >> c;
    cout << f(a, b, c) << endl;
    return 0;
}

假设输入的所有数都为不超过 1000 的正整数，完成下面的判断题和单选题判断题：

第 16 题 (2 分) 当输入为“2 2 2”时，输出为“1.7321”。( )

第 17 题 (2 分) 将第 7 行中的“(s - b)*(s - c)”改为“(s - c)*(s - b)” 不会影响程序运行的结果。( )

第 18 题 (2 分) 程序总是输出四位小数。( )

第 19 题 当输入为“3 4 5”时，输出为( )。

第 20 题 当输入为“5 12 13”时，输出为( )

第 22 题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int f(string x, string y) {
    int m = x.size();
    int n = y.size();
    vector<vector<int>> v(m+1,vector<int>(n+1,0));
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(x[i-1] == y[j-1]) {
                v[i][j] = v[i-1][j-1] + 1;
            } else {
                v[i][j] = max(v[i-1][j], v[i][j-1]);
            }
        }
    }
    return v[m][n];
}

bool g(string x, string y) {
    if(x.size() != y.size()) {
        return false;
    }
    return f(x + x, y) == y.size();
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << g(x, y) << endl;
    return 0;
}

第 22 题 f 函数的返回值小于等于 min(n,m)。( )

第 23 题 f 函数的返回值等于两个输入字符串的最长公共子串的长度。( )

第 24 题 当输入两个完全相同的字符串时，g 函数的返回值总是 true.( )

第 25 题 将第 19 行中的“v[m][n]” 替换为 “v[n][m]”，那么该程序( )。

第 26 题 当输入为“csp-j p-jcs”时，输出为( )。

第 27 题 当输入为“csppsc spsccp”时，输出为( )。

第 29 题

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

int solve1(int n) {
    return n * n;
}

int solve2(int n) {
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if(n % i == 0) {
            if(n/i == i) {
                sum += i*i;
            } else {
                sum += i*i + (n/i)*(n/i);
            }
        }
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout<<solve2(solve1(n))<<" "<<solve1(solve2(n))<< endl;
    return 0;
}

假设输入的 n 是绝对值不超过 1000 的整数，完成下面的判断题和单选题:

第 29 题 如果输入的 n 为正整数，solve2 函数的作用是计算 n 所有的因子的平方和。( )

第 30 题 第 13-14 行的作用是避免 n 的平方根因子(或 n/i)进入第 16 行而被计算两次。( )

第 31 题 如果输入的 n 为质数，solve2(n)的返回值为 n^2+1。( )

第 32 题 (4 分)如果输入的 n 为质数 p 的平方，那么 solve2(n)的返回值为( )。

第 33 题 当输入为正整数时，第一项减去第二项的差值一定( )。

第 34 题 当输入为“5”时，输出为( )。

三、编程题（每题 25 分，共 50 分）

第 36 题 （寻找被移除的元素）问题：原有长度为 n+1、公差为 1 的等差升序数列；将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。 需要在数组不连续时， 找出被移除的元素。 试补全程序。

#include <iostream>
#include <vector>

using namespace std;

int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + __(1)__ ) {
            __(2)__ ;
        } else {
            __(3)__ ;
        }
    }
    return __(4)__ ;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == __(5)__) {
        cout << "Sequence is consecutive" << endl;
    } else {
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

第 36 题 ⑴处应填( )。

第 37 题 ⑵处应填( )。

第 38 题 ⑶处应填( )。

第 39 题 ⑷处应填( )。

第 40 题 ⑸处应填( )。

第 42 题 (编辑距离)给定两个字符串，每次操作可以选择删除(Delete)、插入(insert)替换(Replace)个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。 试补全动态规划算法。

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

int min(int x, int y, int z) {
    return min(min(x, y), z);
}

int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = __(1)__ ;
            else if (j == 0)
                dp[i][j] = __(2)__ ;
            else if (__(3)__)
                dp[i][j] = __(4)__ ;
            else
                dp[i][j]=1+min(dp[i][j - 1],dp[i - 1][j], __(5)__ );
        }
    }
    return dp[m][n];
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:"
         << edit_dist_dp(str1, str2) << endl;
    return 0;
}

第 42 题 ⑴处应填( )。

第 43 题 ⑵处应填( )。

第 44 题 ⑶处应填( )。

第 45 题 ⑷处应填( )。

第 46 题 ⑸处应填( )。