CSP-J1 2026 预测综合卷（范围控制版·B卷）

考试时间：2 小时　满分：100 分

命题定位：强化位运算、数据结构状态模拟、程序不变量和图的矩阵表示。判断题正确填 A，错误填 B。

范围：Day1～Day5 全部内容及 Day6 模块一“图的基本概念与存储”。

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

---

第 1 题

下列存储设备中，断电后原有内容通常会丢失的是（ {{ select(1) }} ）。

• ROM
• RAM
• 固态硬盘
• 光盘

---

第 2 题

十进制数 $-37$ 的 8 位补码表示是（ {{ select(2) }} ）。

• 00100101
• 10100101
• 11011010
• 11011011

---

第 3 题

执行下面代码，输出为。

int x=3,y=0;
bool z=(x++>3)&&(++y>0)||(x==4);
cout<<x<<" "<<y<<" "<<z;

（ {{ select(3) }} ）

• 3 0 0
• 4 0 1
• 4 1 1
• 4 0 0

---

第 4 题

执行下面代码，输出为。

int x=44,y=x,cnt=0;
while(y){ y&=y-1; cnt++; }
cout<<(x&-x)+cnt;

（ {{ select(4) }} ）

• $4$
• $6$
• $7$
• $8$

---

第 5 题

函数定义如下，f(6) 的返回值为。

int f(int n){
    if(n<=1) return n;
    return f(n/2)+f(n-2)+1;
}

（ {{ select(5) }} ）

• $7$
• $8$
• $9$
• $10$

---

第 6 题

执行下面代码后，字符串 s 为。

string s="algorithm";
s.erase(1,3);
s.insert(2,"OJ");

（ {{ select(6) }} ）

• aOJrithm
• arOJithm
• algoOJrithm
• arOJthm

---

第 7 题

执行下面代码，s.size() 和 *it 分别为。

set<int> s={4,1,4,2};
s.insert(3); s.erase(4);
auto it=s.lower_bound(2);

（ {{ select(7) }} ）

• 3 1
• 3 2
• 4 2
• 2 2

---

第 8 题

队列初始为 1,2,3,4。重复 3 次：取出队首 $x$；若 $x$ 为奇数，则把 $x+4$ 加入队尾。操作结束后队首、队尾和队列长度分别为（ {{ select(8) }} ）。

• 3 7 3
• 4 7 3
• 4 5 2
• 5 7 2

---

第 9 题

依次处理记录 (2,A),(1,B),(2,C),(1,D)，用稳定的插入排序按第一个数升序排列，结果为（ {{ select(9) }} ）。

• (1,B),(1,D),(2,A),(2,C)
• (1,D),(1,B),(2,C),(2,A)
• (1,B),(1,D),(2,C),(2,A)
• (2,A),(2,C),(1,B),(1,D)

---

第 10 题

有序数组 1,3,3,3,6,9 下标从 0 开始，第一个严格大于 3 的元素下标为（ {{ select(10) }} ）。

• $1$
• $3$
• $4$
• $5$

---

第 11 题

在任意非空二叉树中，若度为 2 的结点有 17 个，则叶子结点有（ {{ select(11) }} ）个。

• $16$
• $17$
• $18$
• 无法确定

---

第 12 题

一棵有 100 个结点的完全二叉树按 1 开始编号。最后一个结点的父结点编号和整棵树的层数分别为（ {{ select(12) }} ）。

• 49 7
• 50 6
• 50 7
• 51 7

---

第 13 题

小根堆数组为 2,5,4,9,7,8。插入 3 并完成向上调整后，数组为（ {{ select(13) }} ）。

• 2,3,4,9,7,8,5
• 2,5,3,9,7,8,4
• 3,5,2,9,7,8,4
• 2,5,4,9,7,8,3

---

第 14 题

下列二进制编码集合中，不是前缀编码的是（ {{ select(14) }} ）。

• {0,10,110,111}
• {00,01,10,11}
• {0,01,11}
• {10,11,000,001}

---

第 15 题

含 7 个顶点的简单无向完全图，其邻接矩阵中值为 0 的元素共有（ {{ select(15) }} ）个。

• $0$
• $7$
• $21$
• $42$

---

二、阅读程序（共计 40 分）

---

阅读程序（1）：格雷码与二进制位

#include <bits/stdc++.h>
using namespace std;

int gray(int x){ return x^(x>>1); }
int bits(int x){
    int c=0;
    while(x){ x&=x-1; c++; }
    return c;
}

int main(){
    int n;
    cin>>n;
    int last=0,changes=0,even=0;
    for(int i=0;i<(1<<n);i++){
        int g=gray(i);
        if(i) changes+=bits(g^last);
        if(bits(g)%2==0) even++;
        last=g;
    }
    cout<<last<<" "<<changes<<" "<<even;
}

第 16 题

输入 3 时，程序输出 4 7 4（ {{ input(16) }} ）。

---

第 17 题

循环中相邻两次得到的 g 恰好只有一个二进制位不同（ {{ input(17) }} ）。

---

第 18 题

若把循环条件改为 i<(1<<n)-1，输入 3 时，输出的第一个数变为 5（ {{ input(18) }} ）。

---

第 19 题

输入 4 时，程序输出（ {{ select(19) }} ）。

• 8 15 8
• 15 15 8
• 8 16 8
• 8 15 16

---

第 20 题

以 $n$ 表示输入，按 bits 函数的最坏执行次数估计，程序的时间复杂度为（ {{ select(20) }} ）。

• $O(n)$
• $O(2^n)$
• $O(n2^n)$
• $O(4^n)$

---

阅读程序（2）：后缀表达式求值

假设输入是合法后缀表达式，操作数均为一位非负整数，并且除法不会除以 0。

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    stack<int> st;
    int mx=0;
    for(char c:s){
        if(isdigit(c)) st.push(c-'0');
        else{
            int b=st.top(); st.pop();
            int a=st.top(); st.pop();
            if(c=='+') st.push(a+b);
            if(c=='-') st.push(a-b);
            if(c=='*') st.push(a*b);
            if(c=='/') st.push(a/b);
        }
        mx=max(mx,(int)st.size());
    }
    cout<<st.top()<<" "<<mx;
}

第 21 题

输入 82/3-42*+ 时，程序输出 9 3（ {{ input(21) }} ）。

---

第 22 题

计算减法和除法时，弹出的第一个数必须作为右操作数（ {{ input(22) }} ）。

---

第 23 题

若一个合法后缀表达式只含二元运算符，并且有 $k$ 个运算符，则它恰有 $k+1$ 个操作数（ {{ input(23) }} ）。

---

第 24 题

输入 52+83-* 时，程序输出的第一个数为（ {{ select(24) }} ）。

• $15$
• $25$
• $35$
• $45$

---

第 25 题

若错误地把减法写成 st.push(b-a)，输入 82/3-42*+ 时，程序输出的第一个数变为（ {{ select(25) }} ）。

• $-9$
• $-7$
• $7$
• $9$

---

第 26 题

输入 1234+++ 时，程序运行过程中栈的最大长度为（ {{ select(26) }} ）。

• $2$
• $3$
• $4$
• $7$

---

阅读程序（3）：邻接矩阵中的两步路径

#include <bits/stdc++.h>
using namespace std;

int main(){
    const int n=4;
    int g[5][5]={0},two[5][5]={0};
    vector<pair<int,int>> e={{1,2},{1,3},{2,3},{2,4},{3,1},{4,3}};
    for(auto [u,v]:e) g[u][v]=1;

    int in[5]={0},out[5]={0};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            out[i]+=g[i][j];
            in[j]+=g[i][j];
        }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                two[i][j]+=g[i][k]*g[k][j];

    int diag=0;
    for(int i=1;i<=n;i++) diag+=two[i][i];
    cout<<out[1]<<" "<<in[3]<<" "<<two[1][4]<<" "<<diag;
}

第 27 题

程序输出 2 3 1 2（ {{ input(27) }} ）。

---

第 28 题

数组 g 关于主对角线对称（ {{ input(28) }} ）。

---

第 29 题

two[i][j] 表示从顶点 $i$ 出发，恰好经过两条有向边到达顶点 $j$ 的不同走法数（ {{ input(29) }} ）。

---

第 30 题

two[2][1] 的值为（ {{ select(30) }} ）。

• $0$
• $1$
• $2$
• $3$

---

第 31 题

若再加入有向边 (3,4)，重新计算后 two[1][4] 的值为（ {{ select(31) }} ）。

• $1$
• $2$
• $3$
• $4$

---

第 32 题

把顶点数记为 $n$，程序计算整个 two 数组的时间复杂度和 g、two 两个矩阵合计的空间复杂度分别为（ {{ select(32) }} ）。

• $O(n^2)$、$O(n)$
• $O(n^2)$、$O(n^2)$
• $O(n^3)$、$O(n)$
• $O(n^3)$、$O(n^2)$

---

三、完善程序（每小题 3 分，共计 30 分）

---

完善程序（1）：大根堆插入

整数数组 a 从下标 1 开始存储一个含 $n$ 个元素的大根堆，即每个结点的值均不小于其子结点。现在把整数 $x$ 插入堆尾，并不断与父结点比较、交换，使插入后的 a[1..n] 仍为大根堆。数组空间足够，插入过程中需要同步把 $n$ 增加 1。试补全程序。

// a[1..n] 已经是一个大根堆，把 x 插入堆中。
a[____①____]=x;
int i=n;
while(____②____){
    int p=____③____;
    if(____④____) break;
    swap(a[p],a[i]);
    i=____⑤____;
}

第 33 题

①处应填（ {{ select(33) }} ）。

• n++
• ++n
• n-1
• 1

---

第 34 题

②处应填（ {{ select(34) }} ）。

• i>1
• i<n
• i<=1
• a[i]>0

---

第 35 题

③处应填（ {{ select(35) }} ）。

• i*2
• i*2+1
• i/2
• (i-1)/2

---

第 36 题

④处应填（ {{ select(36) }} ）。

• a[p]>=a[i]
• a[p]<a[i]
• p>i
• a[p]==0

---

第 37 题

⑤处应填（ {{ select(37) }} ）。

• i+1
• i-1
• p
• n

---

完善程序（2）：检查简单无向图的邻接矩阵

给定一个 $n imes n$ 的 01 矩阵 g。简单无向图不允许自环，因此主对角线必须全为 0；每条无向边需要在矩阵的两个对称位置同时出现，因此矩阵必须关于主对角线对称。若 g 满足这些条件，输出图的边数；否则输出 -1。程序只枚举主对角线上方的元素，使每条边只统计一次。试补全程序。

// g[1..n][1..n] 中每个元素均为 0 或 1。
// 若 g 是简单无向图的邻接矩阵，输出边数；否则输出 -1。
bool ok=true;
int m=0;
for(int i=1;i<=n;i++){
    if(____①____) ok=false;
    for(int j=____②____;j<=n;j++){
        if(g[i][j]!=____③____) ____④____;
        if(g[i][j]) ____⑤____;
    }
}
cout<<(ok?m:-1);

第 38 题

①处应填（ {{ select(38) }} ）。

• g[i][i]!=0
• g[i][i]==0
• g[i][1]!=0
• i==n

---

第 39 题

②处应填（ {{ select(39) }} ）。

• 1
• i
• i+1
• n

---

第 40 题

③处应填（ {{ select(40) }} ）。

• g[i][i]
• g[j][i]
• g[j][j]
• 0

---

第 41 题

④处应填（ {{ select(41) }} ）。

• m++
• ok=true
• ok=false
• break

---

第 42 题

⑤处应填（ {{ select(42) }} ）。

• m++
• m+=2
• ok=false
• i++

---