2024年12月真题

一、单选题（每题2分，共30分）

正确答案：D
解析：考察字符类型和ASCII码值。
字符类型参与运算，是它所对应的ASCII码值在参与运算，运算结果为整数值。小写字母 b 的ASCII码为98，a+1结果为99，答案为D。

正确答案：A
解析：a为int类型变量，p为int 类型变量，即p是指向int类型的指针。
选项 A：在 C/C++ 中，+a这种写法是错误的。通常只有++a（前置自增）或a++（后置自增）这种用法，这里的+a没有意义，不符合语法。
选项 B：这里p表示解引用指针p，+a虽然看起来有点奇怪，但a本身是int类型，+a等同于a，所以这个赋值语句是合法的。
选项 C：p是指向int类型的指针。这里(p+a)相当于从地址p往后移动 a*4个地址(之所以乘4，是因为int类型需要4个字节存储)，a = *(p + a);，将新地址存储的值赋值给变量a。符合语法
选项 D：同选项3，给新地址赋值为a。

正确答案：A
解析：下标范围：0~长度减1。下标越界并不会产生编译错误和运行错误。但下标越界可能导致程序访问不属于该数数组的内存区域。这可能会读取或修改其他变量的值，甚至可能导致程序崩溃。不正确的选项是A

正确答案：C
解析：
选项 A：构造函数是在对象创建时调用，不存在多态的概念，而析构函数在对象销毁时调用，为了保证正确的析构顺序，特别是在继承关系中，析构函数可以是虚函数。A正确
选项 B：当函数参数是引用类型时，传递的是对象的引用，而不是对象的副本，所以不会调用复制构造函数。B正确
选项 C：虽然静态方法属于类，但在 C++ 中是可以使用对象来调用静态方法的，不过这种做法不推荐，通常使用类名::方法名 () 的形式调用静态方法。C错误
选项 D：在 C++ 中，当派生类对象被销毁时，首先会调用派生类的析构函数，然后自动调用基类的析构函数，以保证资源的正确释放。D正确

正确答案：C
解析：
选项 A：弱连通有向图是指将有向图的所有边变成无向边后得到的无向图是连通的。对于一个弱连通有向图，其最少边数的情况是一个生成树，边数为 n-1。A正确。
选项 B：强连通有向图是指任意两个顶点 u 和 v，都存在从 u 到 v 和从 v 到 u 的路径。一个 n 个顶点的强连通有向图最少有 n 条边（例如一个有 n 个顶点的环）。B正确。
选项 C：对于有向图，每个顶点都可以有 n-1 条出边（指向其他 n-1 个顶点），所以 n 个顶点最多有 n(n-1) 条边。C正确。
选项 D：有向完全图是指任意两个顶点 u 和 v 之间都有两条有向边 <u, v> 和 <v, u>，边数应该是 n(n-1)。D正确。
个人认为本题没有正确答案，官方答案给的C，强行解释一下的话，本题所说的图可能不是以简单图为基础的。不限制是简单图的话，那边的数目没有上线。

正确答案：B
解析：对于任何一个二叉树，假设度为 2 的结点数目为 n2，度为 1 的结点数目为 n1，度为 0 的结点数目为n0，存在可证明的结论：n0=n2+1。
本题中一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在，也就是只存在度为 2 的结点和度为 0 的叶子结点。n2+n0=197，n0=n2+1，可算得n0为99，答案为B。

正确答案：B
解析：二叉排序树是一种特殊的二叉树。它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
选项 A：二叉排序树（二叉搜索树）的中序遍历结果是一个递增序列。
选项 B：二叉排序树在最坏情况下会退化成一条链，此时高度为n-1，而不是 $\lfloor lo{g}_{2}n\rfloor$。只有在平衡二叉排序树（如 AVL 树）的情况下，高度才接近$\lfloor lo{g}_{2}n\rfloor$。
选项 C：AVL 树是一种特殊的二叉排序树，它在插入和删除节点时通过旋转操作保持树的高度平衡。
选项 D：森林可以通过左子右兄弟表示法转换为二叉树。

正确答案：C
解析：n个结点的无向连通图至少有n-1条边。最好的情况下，10个结点6条边，再增加3条即可使其联通。
但本题是问的最差情况下，也就是要用6条边连接最少的结点，完全图情况下满足这个要求，也就是6条边连接4个结点。剩下6个结点，至少需要5条边才能形成连通图，加上一条和4个结点组成的完全图的连接，一共需要6条边，答案选C。

正确答案：D
解析：哈希表是一种数据结构，它提供了快速的插入和查找操作。它的核心思想是使用一个哈希函数，将数据元素的键值映射到一个固定大小的数组（哈希表）中的索引位置。
选项A：当哈希函数取值范围为 0～(n - 1)，且发生碰撞时循环向后找空位，在最坏情况下，每个位置都被占用，需要遍历 n 个位置才能找到空位，查询操作的时间复杂度为 O (n)。A正确。
选项B：每次发生碰撞只需要检查下一个位置，时间复杂度为 O (1)。B正确
选项C：当哈希函数取值范围为 0～(m - 1)，且碰撞时只在 m～(n - 1) 范围内找空位，在最坏情况下，需要遍历 (n - m) 个位置才能找到空位，查询操作的时间复杂度为 O (n - m)。C正确。
选项D：如果哈希函数对应的位置为空位，说明该位置没有存储元素，那么该查询元素不可能出现在哈希表内。D错误。

正确答案：D
解析：动态规划（Dynamic Programming，简称 DP）是一种用于解决优化问题的算法策略。它将一个复杂的问题分解成一系列相互关联的子问题，并通过求解子问题来逐步构建原问题的解。
选项A：动态规划的核心思想就是把原问题分解成多个重叠子问题，通过解决子问题来解决原问题。
选项B：动态规划通常会基于子问题的关系列出递推公式，用于计算问题的解。
选项C：动态规划既可以用递推（自底向上）的方式实现，也可以用递归（自顶向下，通常配合记忆化）的方式实现。
选项D：通常情况下，递推实现（自底向上）的动态规划时间复杂度和空间复杂度会更优，因为它避免了递归调用的开销，而且可以更好地控制计算顺序，减少重复计算。递归实现如果不使用记忆化技术，可能会有大量重复计算，导致时间复杂度较高。D错误

正确答案：B
解析：exp(2) 表示自然常数e的平方，即$e^2$。
自然常数 $e\approx 2.71828$，则$exp(2)\approx 7.38906$，强制转化成int类型进行输出，结果为7，答案为B。

正确答案：A
解析：直接代入逐步计算
$h[0]=h[1]=1$
$h[2]=h[0]\ast h[1]+h[1]\ast h[0]=1\ast 1+1\ast 1=2$
$h[3]=h[0]\ast h[2]+h[1]\ast h[1]+h[2]\ast h[0]=1\ast 2+1\ast 1+2\ast 1=5$
$h[4]=h[0]\ast h[3]+h[1]\ast h[2]+h[2]\ast h[1]+h[3]\ast h[0]=1\ast 5+1\ast 2+2\ast 1+5\ast 1=14$
$h[5]=h[0]\ast h[4]+h[1]\ast h[3]+h[2]\ast h[2]+h[3]\ast h[1]+h[4]\ast h[0]=1\ast 14+1\ast 5+2\ast 2+5\ast 1+14\ast 1=42$
$h[6]=h[0]\ast h[5]+h[1]\ast h[4]+h[2]\ast h[3]+h[3]\ast h[2]+h[4]\ast h[1]+h[5]\ast h[0]=1\ast 42+1\ast 14+2\ast 5+5\ast 2+14\ast 1+42\ast 1=132$
答案是A

正确答案：D
解析：时间复杂度是用来衡量算法运行时间随着输入规模增长而增长的速度。在分析时间复杂度时，通常只考虑算法执行次数的数量级，忽略常数系数和低阶项。
程序中有两层嵌套的for循环。
外层循环从n = 2开始，到n<N结束，每次循环n增加 1。
内层循环从j = 0开始，到j < n结束，每次循环j增加 1。
$n=2,j$ 范围：0~1
$n=3,j$ 范围：0~2
$...$
$n=N-1,j$ 范围：0~(N-2)
累加起来：2+3+…+(N-1) = (N-2)(N+1)/2，忽略常数系数和低阶项，时间复杂度为$O(N^2)$，答案是D。
直接推其实也可以，本题两层嵌套的for循环，且循环变量直接任何关系，时间复杂度是两层for循环的循环次数乘起来忽略常数系数和低阶项。

正确答案：B
解析：时间复杂度是用来衡量算法运行时间随着输入规模增长而增长的速度。在分析时间复杂度时，通常只考虑算法执行次数的数量级，忽略常数系数和低阶项。
第 3-4 行一层for循环，执行次数为n；
第 5-7 行两次for循环嵌套：
$i=2$ 内层循环执行n/2次
$i=3$ 内层循环执行n/3次
$...$
$i=n$ 内层循环执行n/n=1次
累加起来：${\sum }_{i=2}^n\frac{n}{i}$，而${\sum }_{i=2}^n\frac{1}{i}=logn$，${\sum }_{i=2}^n\frac{n}{i}=nlogn$
程序总执行次数 $n+nlogn$，忽略常数系数和低阶项，时间复杂度为$O(nlogn)$，答案为B。

正确答案：A
解析：深度优先遍历是一种用于遍历或搜索图（包括有向图和无向图）、树等数据结构的算法。它的基本思想是从图中的某个顶点开始，沿着一条路径尽可能深地探索下去，直到无法继续或者达到目标，然后回溯到前一步，继续探索下一条路径。
四个选项中只有A不可能，1、2、3、5、7、8，接下来该访问9号结点，而不是6号结点。

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

正确答案：错误，正确，正确
解析：
第1题错误：在 C++ 等编程语言中，^ 通常是按位异或运算符，异或运算规则：相同为0，不同为1。5^3，也即:$(101{)}_2$^$(011{)}_2$=$(110{)}_2$。结果为十进制数6
第2题正确：在 C++ 中，可以通过头文件和链接过程实现函数定义和函数调用在不同文件中。通常将函数声明放在头文件（.h 或 .hpp）中，函数定义放在源文件（.cpp）中，然后在需要调用函数的文件中包含头文件即可。
第3题正确：二分查找的前提是数据已经有序，其每次查找都能将搜索范围缩小一半，时间复杂度为 $O(logn)$。

正确答案：错误，错误
解析：
第4题错误：unsigned long long 在 C++ 中通常占用 8 个字节（64 位），其表示范围是 0 到 2^64 - 1，即 0 到 18446744073709551615。超出这个范围使用long long进行运算会导致溢出。不过更大的数可以使用高精度运算来做，并不是无法使用C++语言进行计算。
第5题错误：在 C++ 中， 头文件中的 log2 函数返回值类型是 double。log2(32) 的结果是 5，但类型是 double，而不是 int。

正确答案：错误，正确
解析：
第6题错误：C++ 是面向对象编程语言，它支持类、对象、继承、多态和封装等面向对象特性。
C 语言是一种过程式编程语言，它本身没有直接的继承机制。然而，在 C 语言中可以通过结构体和函数指针来模拟实现类似继承的功能，但这种方式不如 C++ 中的继承机制那么直接和方便。
第7题正确：邻接表存储图时，对于每个顶点，它存储了一个链表来表示与该顶点相连的边。遍历单个顶点的所有边时，只需要遍历该顶点对应的链表，时间复杂度为 O (d)，其中 d 是该顶点的度。
邻接矩阵是一个二维数组，判断两个顶点是否有边只需要查看矩阵中对应的元素，时间复杂度为 O (1)。。

正确答案：正确
解析：MD5 确实可以将任意长度的数据映射为 128 位的哈希值，并且曾广泛用于数据完整性校验。
中国的王小云教授在密码学领域有突出贡献，她的研究成果包括对 MD5 等哈希函数碰撞问题的破解，这使得 MD5 的安全性受到质疑，逐渐被弃用。

正确答案：正确，错误
解析：
第9题正确：递归调用会占用系统栈空间，如果递归层数过深，可能会导致栈溢出（Stack Overflow）错误，使程序崩溃。
可以通过使用循环和手动模拟栈操作来实现与递归类似的功能，这种方式可以更灵活地控制栈空间的使用，避免栈溢出问题。
第10题错误：用图来表示交通网络是合理的，顶点表示城市，边表示交通方式。
如果两个城市之间的交通方式是有方向的（例如单行道），那么这个图就是有向图。如果不存在自环（一个城市到自己的交通方式）和重边（两个城市之间存在多种相同的交通方式只算一条边），那么它就是简单有向图。但现实情况往往更复杂，不太可能是简单有向图。

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

购买一些武器，满足这些武器的总强度不小于p，总花费不超过q。

标准0/1背包问题，开销控制在不超过q的情况下计算最大武器总强度。

本题要求满足条件的最小花费。 如果武器总强度大于等于p，拿此时的花费和最小花费比较，如果此时的更小，更新最小花费。

洛谷测了下，没做状态压缩竟然也没有超存储。

#include<bits/stdc++.h> //万能头文件 
using namespace std;
#define ll long long
const int N=5e4+5;
struct weapon{int p, c; //武器的强度和花费
}arr[105]; 
int dp[105][N];
int main() {int t, n, p, q, res;cin>>t;while(t--){cin>>n>>p>>q;for(int i=1; i<=n; i++) cin>>arr[i].p>>arr[i].c;memset(dp, 0, sizeof(dp));res = -1; for(int i=1; i<=n; i++){for(int j=0; j<=q; j++){if(arr[i].c > j) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i].c]+arr[i].p);if(dp[i][j] >= p){if(res==-1 || j < res) res = j;}}}cout<<res<<endl;}return 0;
}

//状态压缩代码，二维变一维，减少存储使用
#include<bits/stdc++.h> //万能头文件 
using namespace std;
#define ll long long
const int N=5e4+5;
struct weapon{int p, c; //武器的强度和花费
}arr[105]; 
int dp[N];
int main() {int t, n, p, q, res;cin>>t;while(t--){cin>>n>>p>>q;for(int i=1; i<=n; i++) cin>>arr[i].p>>arr[i].c;memset(dp, 0, sizeof(dp));res = -1; for(int i=1; i<=n; i++){//0-1背包问题的状压，花费必须从大到小遍历 for(int j=q; j>=arr[i].c; j--){ dp[j] = max(dp[j], dp[j-arr[i].c]+arr[i].p);if(dp[j] >= p){if(res==-1 || j < res) res = j;}}}cout<<res<<endl;}return 0;
}

也不难，题目虽然说是一棵包含 $n$ 个节点的树，但没有明确指出树根是那个结点，因此节点之间的访问不限制方向，既然不限制方向，可以使用图的存储方式存储结点之间的关系，鉴于树中的边比较少，用邻接表进行存储。

选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃，火焰会在节点间扩散直到不会有新的节点被引燃。问最多可以燃烧多少个节点。

很明显的搜索，从某个结点出发进行搜索，如果满足条件（权值更小）继续搜索，否则停止。

但纯搜索只能得40分，60分的样例会超时。超时原因是重复搜索，比如从结点1出发进行搜索，可以搜到2、4，那从结点2、4出发进行搜索可以访问到的节点数必然不可能超过结点1，因此不必从2、4出发进行搜索；另外，再搜索过程中，可能会遇到已经搜索过的结点，比如从结点3出发会搜到2，如果从结点2可以引燃的节点数已经记下来，这里就可以直接使用。因此要使用记忆化搜索。在搜索过程中记录下从某个结点出发可以引燃的节点数目。同时，结点数目如果为0，也标识这个结点还没有被搜索过。

#include<bits/stdc++.h> //万能头文件 
using namespace std;
const int N=1e5+5;
int weight[N];
vector<int> mp[N];
int cnt[N];
int dfs(int id) {if(cnt[id]>0) return cnt[id];cout<<id<<"...."<<endl;cnt[id]=1;for(int i=0; i<mp[id].size(); i++) {int j=mp[id][i];if(weight[id] > weight[j]) {if(cnt[j]>0) cnt[id]+=cnt[j];else cnt[id]+=dfs(j);}}return cnt[id];
}
int main() {int n, u, v;cin>>n;for(int i=1; i<=n; i++) cin>>weight[i];for(int i=1; i<n; i++) {cin>>u>>v;mp[u].push_back(v);mp[v].push_back(u);}int res=0;for(int i=1; i<=n; i++) {if(cnt[i]==0) {cnt[i] = dfs(i);res = max(res, cnt[i]);}}cout<<res;return 0;
}