C/C++编程六级 题库
共 6 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
深度优先搜索通常使用哪种数据结构实现?( )
A
栈
B
队列
C
数组
D
链表
答案与解析
正确答案:A
深度优先搜索在遍历图或树时,从起始节点出发,沿着一条路径尽可能深入地访问未访问节点。当无法继续向下时,回溯到上一个存在未访问邻接节点的节点继续遍历。该过程要求后访问的节点先被处理,符合后进先出的顺序特性。栈结构支持这种后进先出的操作模式,通过压入当前节点并弹出最近节点实现路径探索与回溯。队列遵循先进先出原则,适用于按层级展开的遍历方式。数组和链表作为线性存储结构,不直接提供访问顺序控制,需依赖其他机制实现遍历逻辑。
3
判断题
偏易
DFS 剪枝操作一定会改变最终求解答案。( )
A
对
B
错
答案与解析
正确答案:错
分析DFS剪枝操作的作用机制。剪枝是在搜索过程中提前排除不符合条件的分支,减少无效遍历。剪枝分为可行性剪枝、最优性剪枝等类型,其本质是利用约束条件或目标函数性质跳过部分状态空间。剪枝不改变问题本身的解空间定义,仅影响搜索路径与访问节点数量。是否影响最终求解答案取决于剪枝条件是否正确保留了可达解。若剪枝条件严格保证不删除合法解,则最终答案不变;若剪枝误删可行解,则结果可能发生变化。因此剪枝操作与答案变化之间不存在必然因果关系。
5
简答题
偏难
星际探险
题目描述
星际探险队计划从 n 名候选者中挑选队员组成小队,每名候选者只能入选一次。
飞船上有 m 个关键系统,第 i 名候选者的加入会对第 j 个系统的状态值产生 (ai, j) 的影响,影响可正可负。
探险安全条例要求,最终小队组成后,每个系统的状态值总和都必须不低于 0,否则飞船无法维持安全航行。
在满足该要求的前提下,希望小队的人数尽可能多,请输出这个最大人数。若不存在任何满足条件的选人方案,输出0。
输入格式
第一行:两个整数表示 n 与 m;
第二行到第 n+1 行:第 i+1 行有 m 个整数,表示 (ai,1)、(ai,2)、……、(ai,m)。
输出格式
单个整数:表示答案。
输入样例
4 3 1 1 -2 1 -2 1 -2 1 1 2 2 2
输出样例
4
说明提示:
1≤n、m≤16,1,000,000≤ (ai, j) ≤1,000,000。
限制:
时间限制:1000ms,内存限制:256MiB
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
// 存储每个人对m个系统的贡献
vector<vector<long long>> a(n, vector<long long>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int max_people = 0;
// 枚举所有子集:mask 二进制第i位=1表示选第i个人
for (int mask = 1; mask < (1 << n); ++mask) {
int cnt = __builtin_popcount(mask); // 选中的人数
if (cnt <= max_people) continue; // 剪枝:人数更少直接跳过
vector<long long> sum(m, 0);
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) { // 选了第i个人
for (int j = 0; j < m; ++j) {
sum[j] += a[i][j];
}
}
}
// 检查所有系统是否都 ≥ 0
bool ok = true;
for (long long s : sum) {
if (s < 0) {
ok = false;
break;
}
}
if (ok) {
max_people = cnt;
}
}
cout << max_people << endl;
return 0;
}
6
简答题
偏难
括号
给定一个整数 n。生成所有长度为 n 的合法括号序列,并按字典序升序输出。合法括号序列定义:
(1)空字符串是合法的;
(2)若字符串 s 合法,则 (+s+) 合法;
(3)若字符串 s 和 t 合法,则 s+t 合法。
时间限制:1000ms内存限制:256MB
输入格式
输入一个整数n。
输出格式
每行输出一个合法括号序列(按字典序升序)。若无解则不输出。
输入样例#1
2
输出样例#1
()
输入样例#2
4
输出样例#2
(()) ()()
输入样例#3
6
输出样例#3
((())) (()()) (())() ()(()) ()()()
数据范围:
1≤N≤20,N 是偶数。
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 回溯函数:生成所有合法括号序列
// res:存储结果的向量
// path:当前构建的括号序列
// left:已使用的左括号数量
// right:已使用的右括号数量
// n:目标序列长度
void backtrack(vector<string>& res, string& path, int left, int right, int n) {
// 当当前序列长度达到n时,加入结果集
if (path.size() == n) {
res.push_back(path);
return;
}
// 优先添加左括号(保证字典序),左括号数量不超过n/2
if (left < n / 2) {
path.push_back('(');
backtrack(res, path, left + 1, right, n);
path.pop_back(); // 回溯,移除最后添加的左括号
}
// 再添加右括号,右括号数量不能超过左括号数量(保证合法性)
if (right < left) {
path.push_back(')');
backtrack(res, path, left, right + 1, n);
path.pop_back(); // 回溯,移除最后添加的右括号
}
}
int main() {
int n;
cin >> n;
vector<string> result;
string path;
backtrack(result, path, 0, 0, n);
// 输出所有合法序列
for (const string& s : result) {
cout << s << endl;
}
return 0;
}