【202609】C++六级

从PDF导入：【202609】C++六级

C++ 120分钟 总分 100.0 27 题
试卷题目预览
第1题 中级 2.0分 单选
下列代码执行后的输出结果是（　　）。

A. Animal
B. Cat
C. Animal Cat
D. 编译错误
第2题 中级 2.0分 单选
下列代码中，横线处应填写（　　），才能正确调用基类的带参数构造函数。

A. Machine(s)
B. Machine::id(s)
C. super(s)
D. id(s)
第3题 中级 2.0分 单选
下列代码执行后的输出顺序是（　　）。

A.
B.
C. ~
D. ~D
第4题 中级 2.0分 单选
下列代码执行后的输出结果是（　　）。

A. 2 4
B. 4 4
C. 4 6
D. 6 2
第5题 中级 2.0分 单选
下面循环队列采用"空出一个位置"的方式区分队空和队满。横线处应填写（　　）。

A. rear == front
B. (front + 1) % MAXN == rear
C. (rear + 1) % MAXN == front
D. rear == MAXN - 1
第6题 中级 2.0分 单选
下列函数实现了二叉树的哪种遍历方式（　　）。

A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
第7题 中级 2.0分 单选
已知一棵二叉树的先序遍历序列为 A B D E C F，中序遍历序列为 D B E A C F，则其后序遍历序列是（　　）。
A. D E B F C A
B. D B E F C A
C. E D B F C A
D. D E B C F A
第8题 中级 2.0分 单选
下面函数用于计算二叉树的高度，横线处应填写（　　）。

A. leftH + rightH
B. min(leftH, rightH) + 1
C. max(leftH, rightH)
D. max(leftH, rightH) + 1
第9题 中级 2.0分 单选
以下代码实现二叉树左子树优先的深度优先搜索算法，则横线上应填写（　　）。

A.
B.
C.
D.
第10题 中级 2.0分 单选
下面函数在二叉搜索树中查找值 x。横线处应填写（　　）。

A. searchBST(root->left, x)
B. searchBST(root->right, x)
C. searchBST(root, x + 1)
D. root->right
第11题 中级 2.0分 单选
有 5 个字符，其出现频率分别为 2、4、5、9、12。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（　　）。
A. 68
B. 69
C. 71
D. 75
第12题 中级 2.0分 单选
下面代码用反射法生成 n 位格雷编码，横线处应填写（　　）。

A. ans[i] + "1"
B. "0" + ans[i]
C. "1" + ans[i]
D. ans[oldSize - i - 1]
第13题 中级 2.0分 单选
下面代码计算走到第 n 级台阶的方法数，每次可以走 1 级或 2 级。横线处应填写（　　）。

A. dp[i - 1] + 1
B. dp[i - 1] + dp[i - 2]
C. dp[i - 2] + 2
D. 2 * dp[i - 1]
第14题 中级 2.0分 单选
下面代码求从包含非负元素的数组中选择若干个互不相邻元素所能得到的最大和。横线处应填写（　　）。

A. dp[i - 1] + a[i]
B. dp[i - 2] + a[i]
C. max(dp[i - 1], dp[i - 2] + a[i])
D. max(dp[i - 1], a[i])
第15题 中级 2.0分 单选
下面是一维数组实现的 0/1 背包。内层循环必须从大到小枚举容量，主要原因是（　　）。

A. 保证每件物品最多被选择一次
B. 保证物品必须按照重量从大到小选择
C. 降低时间复杂度
D. 防止数组 dp 发生越界
第16题 中级 2.0分 判断
下列代码可以正常编译，因为编译器会自动为 Student 类生成一个无参数构造函数。

T. 正确
F. 错误
第17题 中级 2.0分 判断
下列代码合法，因为派生类可以直接访问基类的私有成员 value。

T. 正确
F. 错误
第18题 中级 2.0分 判断
下列代码执行后，输出结果为 30。

T. 正确
F. 错误
第19题 中级 2.0分 判断
一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组 tree[1]、tree[2]、……中。若节点 tree[i] 存在左孩子，则其左孩子存储在 tree[2 * i] 中。
T. 正确
F. 错误
第20题 中级 2.0分 判断
对任意一棵二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。

T. 正确
F. 错误
第21题 中级 2.0分 判断
若使用下列代码从节点 start 开始访问一棵树，则第一次到达某个节点时所经过的边数，一定是从 start 到该节点的最少边数。

T. 正确
F. 错误
第22题 中级 2.0分 判断
哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。
T. 正确
F. 错误
第23题 中级 2.0分 判断
在 n 位格雷码中，任意两个编码之间都只相差一个二进制位。
T. 正确
F. 错误
第24题 中级 2.0分 判断
下列一维动态规划代码实现的是完全背包问题，因为在处理第 i 种物品时，同一种物品可能被重复选择。

T. 正确
F. 错误
第25题 中级 2.0分 判断
下列递归程序能得到正确的斐波那契数，其时间复杂度和空间复杂度都是<img src="/static/uploads/images/6034bc1bd94a.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />。

T. 正确
F. 错误
第26题 中级 25.0分 编程
：数组划分

试题名称：数组划分
时间限制：1.0 s
内存限制：512.0 MB
给定 n 个整数构成的数组 A。
你需要将数组 A 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。

【输入格式】
第一行，一个正整数 n，表示数组 A 的长度。
第二行，n 个整数 a1, a2, …, an，表示数组 A。
【输出格式】
一行，一个整数，表示划分方案偏差值的最小值。
【输入样例 1】
<img src="/static/uploads/images/57c8d2b77d19.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 1】
6
【输入样例 2】
<img src="/static/uploads/images/3733553ca716.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 2】
0
【数据范围】
<img src="/static/uploads/images/51d2b9ee1749.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
第27题 中级 25.0分 编程
分树规划

试题名称：分树规划
时间限制：1.0 s
内存限制：512.0 MB
老师有一棵有 n 个结点的树，结点依次以 1, 2, …, n 编号。
老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。
如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。

【输入格式】
<img src="/static/uploads/images/a0c529d187c6.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出格式】
输出一行，一个整数，表示答案。
【输入样例 1】
4
1 2
2 3
3 4
【输出样例 1】
0
【输入样例 2】
6
1 2
1 3
1 4
1 5
5 6
【输出样例 2】
2
【数据范围】
<img src="/static/uploads/images/b34067959a33.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
💬