首页 › 题库 › C/C++编程考级 › 3 搜索算法

C/C++编程六级 题库

共 6 道题 · 按题型筛选,点「查看答案」核对解析
章节 3 搜索算法 清除
1 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法
深度优先搜索通常使用哪种数据结构实现?( )
A
栈
B
队列
C
数组
D
链表
答案与解析
正确答案:A
深度优先搜索在遍历图或树时,从起始节点出发,沿着一条路径尽可能深入地访问未访问节点。当无法继续向下时,回溯到上一个存在未访问邻接节点的节点继续遍历。该过程要求后访问的节点先被处理,符合后进先出的顺序特性。栈结构支持这种后进先出的操作模式,通过压入当前节点并弹出最近节点实现路径探索与回溯。队列遵循先进先出原则,适用于按层级展开的遍历方式。数组和链表作为线性存储结构,不直接提供访问顺序控制,需依赖其他机制实现遍历逻辑。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

广度优先搜索(BFS)通常使用哪种数据结构实现?( )

A
栈
B
队列
C
链表
D
数组
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

DFS 剪枝操作一定会改变最终求解答案。( )

A
对
B
错
答案与解析
正确答案:错
分析DFS剪枝操作的作用机制。剪枝是在搜索过程中提前排除不符合条件的分支,减少无效遍历。剪枝分为可行性剪枝、最优性剪枝等类型,其本质是利用约束条件或目标函数性质跳过部分状态空间。剪枝不改变问题本身的解空间定义,仅影响搜索路径与访问节点数量。是否影响最终求解答案取决于剪枝条件是否正确保留了可达解。若剪枝条件严格保证不删除合法解,则最终答案不变;若剪枝误删可行解,则结果可能发生变化。因此剪枝操作与答案变化之间不存在必然因果关系。
题目详情
4 判断题 偏易 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

DFS 中的剪枝操作,目的是减少不必要的搜索分支,提高搜索效率。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
5 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

星际探险

题目描述

星际探险队计划从 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 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

括号

给定一个整数 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;
}
题目详情