2025CCF 提高级 CSP-S 初赛

分類：CSP-S 提高组
來源：https://lib.nbdp.net/paper/148.html

一、单选题（每题 2 分，共 30 分）查看答案

第 1 题有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这10个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法?( )

A. 25
B. 30
C. 6
D. 120

答案： C. 6

第 2 题在KMP算法中，对于模式串 P=abacaba，其next数组(next[i]定义为模式串P[0..i]最长公共前后缀的长度，且数组下标从0开始)的值是什么?( )

A. {0,0,1,0,1,2,3}
B. {0, 1,2, 3, 4, 5,6}
C. {0,0,1,1,2, 2,3}
D. {0,0,0,0,1,2,3}

答案： A. {0,0,1,0,1,2,3}

第 3 题对一个大小为16(下标0~15)的数组上构建满线段树。查询区间[3,11]时，最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?( )

A. 7
B. 8
C. 9
D. 10

答案： B. 8

第 4 题将字符串“cat”, “car”, “cart”, “case”, “dog”, “do”插入一个空的Trie树(前缀树)中。构建完成的Trie树(包括根结点)共有多少个结点?( )

A. 8
B. 9
C. 10
D. 11

答案： D. 11

第 5 题对于一个包含n个顶点和m条边的有向无环图(DAG)，其拓扑排序的结果有多少种可能?( )

A. 只有1种
B. 最多n种
C. 等于 n-m 种
D. 以上都不对

答案： D. 以上都不对

第 6 题在一个大小为13的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为H(key)=key mod 13。依次插入关键字18,26,35,9,68,74。插入74后，它最终被放置在哪个索引位置?( )

A. 5
B. 7
C. 9
D. 11

答案： D. 11

第 7 题一个包含8个顶点的完全图(顶点的编号为1到8)，任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点3和7之间的边权重为|7-3|=4。该图的最小生成树的总权重是多少?( )

A. 7
B. 8
C. 9
D. 10

答案： A. 7

第 8 题如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6,那么该树的前序遍历序列是什么?( )

A. 6,4,2,5,10,8,12
B. 6,4,5,2,10,12,8
C. 2,4,5,6,8,10,12
D. 12,8,10,5, 2,4,6

答案： A. 6,4,2,5,10,8,12

第 9 题一个0-1背包问题，背包容量为20。现有5个物品，其重量和价值分别为7，5，4，3，6和15，12，9，7，13。装入背包的物品能获得的最大总价值是多少?( )

A. 43
B. 41
C. 45
D. 44

答案： D. 44

第 10 题在一棵以结点1为根的树中，结点12和结点18的最近公共祖先(LCA)是结点4。那么下列哪个结点的LCA组合是不可能出现的?( )

A. LCA(12,4) = 4
B. LCA(18,4)=4
C. LCA(12,18,4) =4
D. LCA(12,1)=4

答案： D. LCA(12,1)=4

第 11 题递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少?( )

答案： 3

A. $O(n)$

答案： 3

B. $O(n \log n)$

答案： 3

C. $O(n^2)$

答案： 3

D. $O(n^2 \log n)$

第 12 题在一个初始为空的最小堆(min-heap)中，依次插入元素20,12,15,8,10,5。然后连续执行两次“删除最小值”(delete-min)操作。请问此时堆顶元素是什么?( )

A. 10
B. 12
C. 15
D. 20

答案： A. 10

第 13 题 1到1000之间，不能被2、3、5中任意一个数整除的整数有多少个?( )

A. 266
B. 267
C. 333
D. 734

答案： A. 266

第 14 题斐波那契数列的定义为F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算F(n)的时间复杂度是指数级的。而使用动态规划(或迭代)方法的时间复杂度是线性的。造成这种巨大差异的根本原因是?( )

A. 递归函数调用栈开销过大
B. 操作系统对递归深度有限制
C. 朴素递归中存在大量的重叠子问题未被重复利用
D. 动态规划使用了更少的数据存储空间

答案： C. 朴素递归中存在大量的重叠子问题未被重复利用

第 15 题有5个独立的、不可抢占的任务A1,A2,A3,A4,A5 需要在一台机器上执行(从时间0开始执行)，每个任务都有对应的处理时长和截止时刻，按顺序分别为3,4,2,5,1和5,10,3,15,11。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务?( )

A. 处理时间最短的任务A5
B. 截止时间最早的任务A3
C. 处理时间最长的任务A4
D. 任意一个任务都可以

答案： B. 截止时间最早的任务A3

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

第 16 题

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1]+ 1) continue;
        p[k] = i;
        flag[i] = true;        
		dfs(k + 1);
        flag[i]= false;
    }
    return;
}
int main() {
    scanf("%d",&n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

判断题

第 16 题 (1分)当输入的n=3的时候，程序输出的答案为3。( )

A.正确
B.错误

答案： A.正确

第 17 题在dfs函数运行过程中，k的取值会满足1≤k≤n+1。( )

A.正确
B.错误

答案： A.正确

第 18 题删除第19行的“f1ag[i]=false;”对答案不会产生影响。

A.正确
B.错误

答案： 2

第 19 题当输入的n =4的时候,程序输出的答案为( )。

A. 11
B. 12
C. 24
D. 9

答案： A. 11

第 20 题如果因为某些问题，导致程序运行第25行的dfs函数之前，数组p的初值并不全为0，则对程序的影响是( )。

A. 输出的答案比原答案要小
B. 无法确定输出的答案
C. 程序可能陷入死循环
D. 没有影响

答案： D. 没有影响

第 21 题假如删去第14行的“if(flag[i]) continue;”，输入3，得到的输出答案是( )

A. 27
B. 3
C. 16
D. 12

答案： C. 16

第 23 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int cnt_broken = 0;
int cnt_check = 0;
inline bool check(int h) {
    printf("now check:%d\n",h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are right using %d checks\n",cnt_check);
        return true;
    } else {
        printf("wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i<= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w =0;
    for (w = 1; w * (w+1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w;; --ti,nh += ti, nh = std::min(nh,n)) {
        if (check(nh)) {
            for (int j= nh - ti +1; j< nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d",&t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}

判断题

第 23 题当输入为“6 5 1”时，猜测次数为5;当输入为“6 5 2”时，猜测次数为3。

A.正确
B.错误

答案： A.正确

第 24 题不管输入的n和k具体为多少，t=2时的猜测数总是小于等于t=1时的猜测数。

A.正确
B.错误

答案： 2

第 25 题不管t=1或t=2，程序都一定会猜到正确结果。

A.正确
B.错误

答案： A.正确

第 26 题函数 guess1在运行过程中，cnt_broken的值最多为( )。

A. 0
B. 1
C. 2
D. n

答案： B. 1

第 27 题函数 guess2 在运行过程中，最多使用的猜测次数的量级为()。

答案： 3

A. $O(n)$

答案： 3

B. $O(n^2)$

C. $O(\sqrt(n))

答案： C. $O(\sqrt(n))

D. $O(\log n)$

第 28 题当输入的n=100时，代码中t=1和t=2分别需要的猜测次数最多分别为( )。

A. 100,14
B. 100,13
C. 99,14
D. 99,13

答案： A. 100,14

第 30 题

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#define ll long long
int n, m;
std::vector<int> k,p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k = k >> 1,x =x*x) {
        if (k & 1)
            ans = ans *x;
    }
    return ans;
}
std::vector<int> ans1,ans2;
int cnt1,cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l+1, r,v + k[l] * mpow(i,p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d",&n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2,(n >> 1) + 1, n,0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1=1;
    cntans1.push_back(1);
    for (int i = 1; i <cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 - 1]) {
            ++cntans1[newcnt1- 1];
        } else {
            ans1[newcnt1++]= ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i=cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ans1[las] + ans2[i] <0; ++las)
            ;
        if (las < cnt1 && ans1[las] + ans2[i]==0)
            ans += cntans1[las];
    }
    printf("%lld\n", ans);
    return 0;
}

判断题

第 30 题删除第51行的“std::sort(ans2.begin()，ans2.end());”后，代码输出的结果不会受到影响。

A.正确
B.错误

答案： 2

第 31 题假设计算过程中不发生溢出，函数mpow(x,k)的功能是求出 $x^k$ 。

A.正确
B.错误

答案： A.正确

第 32 题代码中第39行到第50行的目的是为了将ans1数组进行“去重”操作。

A.正确
B.错误

答案： A.正确

第 33 题当输入为“3 15 1 2 -1 2 1 2”时，输出结果为()。

A. 4
B. 8
C. 0
D. 10

答案： B. 8

第 34 题记程序结束前p数组元素的最大值为P，则该代码的时间复杂度是( )。

答案： 4

A. $O(n)$

答案： 4

B. $O(m^n log m^n)$

答案： 4

C. $O(m^{n/2} log m^{n/2})$

答案： 4

D. $O(m^n (log m^{n/2} + log P))$

第 35 题本题所求出的是()。

答案： 4

A. 满足 $a, b, c \\in [1, m]$ 的整数方程 $a^3 + b^3 = c^3$ 的解的数量 ","

答案： 4

B. 满足 $a, b, c \\in [1, m]$ 的整数方程 $a^2 + b^2 = c^2$ 的解的数量

答案： 4

C. 满足 $x_i \\in [0, m]$ 的整数方程 $\\sum_{i=1}^{n} k_i \\cdot x_i^{p_i} = 0$ 的解的数量

答案： 4

D. 满足 $x_i \\in [1, m]$ 的整数方程 $\\sum_{i=1}^{n} k_i \\cdot x_i^{p_i} = 0$ 的解的数量

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

第 37 题程序填空第一题(特殊最短路) 给定一个含 $N$ 个点、 $N$ 条边的带权无向图，边权非负。起点为 $S$ ，终点为 $T$ 。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为“免费边”:当第一次经过这条被选中的边时，费用视为0;如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。以下代码求解了上述问题。试补全程序。

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

const long long INF = 1e18;

struct Edge {
    int to;
    int weight;
};

struct State {
    long long dist;
    int u;
    int used_freebie;//0 for not used,1 for used
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};

int main() {
    int n,m,s,t;
    cin >> n >> m >> s >> t;

    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    vector<vector<long long>> d(n + 1,vector<long long>(2,INF));
    priority_queue<State,vector<State>, greater<State>> pq;

    d[s][0]= 0;
    pq.push({0, s, ___(1)___ });

    while(!pq.empty()) {
        State current = pq.top();
        pq.pop();

        long long dist = current.dist;
        int u= current.u;
        int used = current.used_freebie;

        if(dist > a) {
            continue;
        }

        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            if(d[u][used] + w < ___(2)___ ) {
                ___(3)___ = d[u][used] +w;
                pq.push({ ___(3)___ ,v ,used});
            }

            if(used == 0) {
                if( ___(4)___ < d[v][1]) {
                    d[v][1]= ___(4)___;
                    pq.push({d[v][1],v,1});
                }
            }
        }
    }
    
    cout <<	___(5)___ << endl;
	return 0;
}

第 37 题 ⑴处应填( )。

A. 0
B. 1
C. -1
D. false

答案： A. 0

第 38 题 ⑵处应填( )。

A. d[u][!used]
B. d[u][used]
C. d[t][used]
D. INF

答案： B. d[u][used]

第 39 题 ⑶处应填( )。

A. d[u][1]
B. d[v][used]
C. d[u][used]
D. d[u][0]

答案： B. d[v][used]

第 40 题 ⑷处应填( )。

A. d[v][0]
B. d[v][1]
C. d[u][0]
D. d[u][1]

答案： C. d[u][0]

第 41 题 ⑸处应填( )。

A. d[t][1]
B. d[t][0]
C. min(d[t][0],d[t][1])
D. d[t][0] + d[t][1]

答案： C. min(d[t][0],d[t][1])

第 43 题 (最优测试) 工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线(编号0~n-1)，已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货(结果记为1)，否则正常收货(记为0)。受售后压力限制，在所有发货批次中，最多只能有k次退货(即结果为1的次数≤k)。工厂的目标是，设计最少的间接测试轮数w(发货总批次)，保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分: i)确定w的最小值，并设计最优测试方案; ii)根据测试结果推断存在缺陷的生产线。该程序确定w最小值的方法为:由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。 test_subset()函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现不在此处给出。试补全程序。

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

long long comb(int w, int i) {
    if (i <0 ||i>w) {
        return 0;
    }
    long long res = 1;
    for (int t = 1; t <= i; ++t) {
        res = res * (w - t+1) /t;
    }
    return res;
}

// 计算长度为 w、1 的个数 ≤k的码字总数
long long count_patterns(int w, int k) {
    long long total =0;
    for (int t = 0; t <= min(w,k); ++t) {
        total += comb(w,t);
    }
    return total;
}

// 抽象测试接口	
int test_subset(const vector<vector<int>>& plan);

int solve(int n, int k) {
    // === 第 1 步:求最小w===
    int w = 1;
    while( ___(1)___ ) {
        ++w;
    }
    cout << w << endl;

    // ===第2步:生成测试方案===
    vector<vector<int>> code(n,vector<int>(w,0));
    int idx =0;
    for (int ones = 0; ones <= k && idx < n; ++ones) {
        vector<int> bits(w,0);
        fill(bits.begin(),bits.begin() + ones,1);
        do {
            for (int b = 0; b < w; ++b) {
                code [idx][b] = bits[b];
            }
            ++idx;
            if (idx >= n) {
                break;
            }
        } while ( std:: ___(2)___ );
    }

    vector<vector<int>>plan(w);
    for (int i =0; i<w; ++i) {
        for (int j= 0; j< n; ++j) {
            if( ___(3)___ ) {
                plan[i].push_back(j);
            }
        }
    }

    // ===第3步;调用测试接口 --=
    int signature = test_subset(plan);

    // === 第4步:结果解码 ===
    vector<int> sig_bits(w,0);
    for (int i = 0; i <w; ++i) {
        if( ___(4)___ ) {
            sig_bits[i] = 1;
        }
    }
    
    for (int j = 0; j < n; ++j) {
        if( ___(5)___ ) return j;
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    int ans = solve(n,k);
    cout << ans << end1;
    return 0;
}

第 43 题 ⑴处应填( )。

A. (1 << w) < n
B. count_patterns(w, k) < n
C. count_patterns(k, w) < n
D. comb(w, k) < n

答案： B. count_patterns(w, k) < n

第 44 题 ⑵处应填( )。

A. next_permutation(bits.begin(), bits.end())
B. prev_permutation(bits.begin(), bits.end())
C. next_permutation(bits.begin(), bits.begin()+ones)
D. prev_permutation(bits.begin(), bits.begin()+ones)

答案： B. prev_permutation(bits.begin(), bits.end())

第 45 题 ⑶处应填( )。

答案： 4

i) & 1" lay-filter="filter">

答案： 4

j) & 1" lay-filter="filter">

C. code[i][j] == 1
D. code[j][i] == 1

答案： D. code[j][i] == 1

第 46 题 ⑷处应填( )。

答案： 1

i) & 1" lay-filter="filter">

答案： 1

i) ^ 1" lay-filter="filter">

C. signature | (1 << i)

答案： 1

i) | 1" lay-filter="filter">

第 47 题 ⑸处应填( )。

A. is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
B. code[j] == sig_bits
C. plan[j] == sig_bits
D. code[j][i] == sig_bits[i]

答案： B. code[j] == sig_bits

2025CCF 提高级 CSP-S 初赛

Links to this page: