CSP-J1 Day1-Day6 综合模拟卷（第一套）

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

范围：Day1～Day5 全部内容及 Day6 模块一“图的基本概念与存储”，不涉及 Day6 后续模块。判断题正确填 A，错误填 B。

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

---

第 1 题

32 位无符号整数能表示的最大值是（ ）。

{{ select(1) }}

• $2^{31}-1$
• $2^{31}$
• $2^{32}-1$
• $2^{32}$

---

第 2 题

计算 $(17_8+1011_2) imes A_{16}$ 的十进制结果是（ ）。

{{ select(2) }}

• $250$
• $260$
• $270$
• $280$

---

第 3 题

若 1KB=1024B、1MB=1024KB，则 2MB 等于多少 bit？

{{ select(3) }}

• $2^{21}$
• $2^{22}$
• $2^{23}$
• $2^{24}$

---

第 4 题

执行 int x=44; x&=x-1; x&=x-1; cout<<x;，输出是（ ）。

{{ select(4) }}

• $0$
• $32$
• $40$
• $42$

---

第 5 题

外层变量从 $n$ 开始每次除以 2，内层执行次数等于当前外层变量，总执行次数的复杂度是（ ）。

{{ select(5) }}

• $O(\log n)$
• $O(n\log n)$
• $O(n)$
• $O(n^2)$

---

第 6 题

表达式 (char)('A'+('d'-'a')) 的值是（ ）。

{{ select(6) }}

• 'C'
• 'D'
• 'd'
• '4'

---

第 7 题

执行 vector<int> a={4,1,4,2,1}; sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); 后，a.size() 为（ ）。

{{ select(7) }}

• $2$
• $3$
• $4$
• $5$

---

第 8 题

元素按 1,2,3,4,5 顺序入栈并可随时出栈，下面不可能的出栈序列是（ ）。

{{ select(8) }}

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

---

第 9 题

冒泡排序把 4,1,3,2 升序排列，共发生多少次元素交换？

{{ select(9) }}

• $2$
• $3$
• $4$
• $5$

---

第 10 题

数组 1,3,3,5,8 下标从 0 开始，lower_bound 查找 4 返回的下标是（ ）。

{{ select(10) }}

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

---

第 11 题

一棵有 100 个结点的完全二叉树共有多少个叶子结点？

{{ select(11) }}

• $49$
• $50$
• $51$
• $64$

---

第 12 题

权值 2,3,7,9 构造哈夫曼树，其 WPL 是（ ）。

{{ select(12) }}

• $33$
• $35$
• $38$
• $42$

---

第 13 题

无向图所有顶点的度数之和为 18，则图中边数为（ ）。

{{ select(13) }}

• $8$
• $9$
• $18$
• $36$

---

第 14 题

无向图中所有顶点的度数之和是边数的（ ）。

{{ select(14) }}

• 一半
• 相同
• 2 倍
• 4 倍

---

第 15 题

依次把 5,2,8,1,3,7,9 插入空 BST，所得前序遍历是（ ）。

{{ select(15) }}

• 5 2 1 3 8 7 9
• 1 2 3 5 7 8 9
• 1 3 2 7 9 8 5
• 5 8 9 7 2 3 1

---

二、阅读程序（判断题正确填 A，错误填 B，共计 40 分）

---

第 1 组：排序、去重与加权和

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int> a(n);
    for(int &x:a) cin>>x;
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    long long ans=0;
    for(int i=0;i<(int)a.size();i++) ans+=1LL*(i+1)*a[i];
    cout<<a.size()<<" "<<ans;
}

第 16 题

输入 8 5 2 5 3 2 8 1 3 时，程序输出 5 74。

{{ input(16) }}

---

第 17 题

删除 erase(unique(...)) 这一行后，对上述输入仍输出 5 74。

{{ input(17) }}

---

第 18 题

该程序的时间复杂度由排序主导，通常为 $O(n\log n)$。

{{ input(18) }}

---

第 19 题

输入 6 4 4 1 2 2 3 时，程序输出（ ）。

{{ select(19) }}

• 3 18
• 4 24
• 4 30
• 6 56

---

第 20 题

把排序改成从大到小，仍使用相同输入 8 5 2 5 3 2 8 1 3，程序输出（ ）。

{{ select(20) }}

• 5 35
• 5 40
• 5 74
• 8 167

---

第 2 组：邻接矩阵与顶点度数

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n=5, g[6][6]={0};
    vector<pair<int,int>> e={{1,2},{1,3},{2,3},{2,4},{4,5}};
    for(auto [u,v]:e) g[u][v]=g[v][u]=1;
    int sum=0, mx=0, cnt=0;
    for(int i=1;i<=n;i++){
        int deg=0;
        for(int j=1;j<=n;j++) deg+=g[i][j];
        sum+=deg; mx=max(mx,deg);
        if(deg==1) cnt++;
    }
    cout<<sum<<" "<<mx<<" "<<cnt<<" "<<g[3][4];
}

第 21 题

程序输出 10 3 1 0。

{{ input(21) }}

---

第 22 题

数组 g 关于主对角线对称。

{{ input(22) }}

---

第 23 题

该图是一棵树。

{{ input(23) }}

---

第 24 题

顶点 2 的度数是（ ）。

{{ select(24) }}

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

---

第 25 题

若删除边 (2,3)，所有顶点的度数之和变为（ ）。

{{ select(25) }}

• $6$
• $8$
• $9$
• $10$

---

第 26 题

若只把建边语句改为 g[u][v]=1，则程序表示的是（ ）。

{{ select(26) }}

• 有向图
• 无向图
• 完全图
• 一定是树

---

第 3 组：BST 插入与递归统计

#include <bits/stdc++.h>
using namespace std;
struct Node{int x;Node*l,*r;Node(int v):x(v),l(nullptr),r(nullptr){}};
Node* ins(Node*u,int x){if(!u)return new Node(x);if(x<u->x)u->l=ins(u->l,x);else if(x>u->x)u->r=ins(u->r,x);return u;}
int height(Node*u){return !u?0:1+max(height(u->l),height(u->r));}
int leaf(Node*u){if(!u)return 0;if(!u->l&&!u->r)return 1;return leaf(u->l)+leaf(u->r);}
void in(Node*u){if(!u)return;in(u->l);cout<<u->x<<" ";in(u->r);}
int main(){int a[]={5,3,8,2,4,7,9};Node*root=nullptr;for(int x:a)root=ins(root,x);cout<<height(root)<<" "<<leaf(root)<<" |";in(root);}

第 27 题

程序输出的树高为 3。

{{ input(27) }}

---

第 28 题

程序中序遍历输出的数值严格递增。

{{ input(28) }}

---

第 29 题

若把严格递增的 $n$ 个数依次插入空 BST，树高可能达到 $n$。

{{ input(29) }}

---

第 30 题

程序输出的叶子数是（ ）。

{{ select(30) }}

• $2$
• $4$
• $5$
• $7$

---

第 31 题

在该树中查找 7，需要依次比较多少个结点？

{{ select(31) }}

• $2$
• $3$
• $4$
• $5$

---

第 32 题

若把相等值规定插入左子树，并输入 5 5 5 5，最终树高为（ ）。

{{ select(32) }}

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

---

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

---

第 1 组：括号匹配

bool check(string s){
    stack<char> st;
    for(char c:s){
        if(c=='('||c=='['||c=='{') ____①____;
        else{
            if(____②____) return false;
            char t=____③____;
            if((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
            ____④____;
        }
    }
    return ____⑤____;
}

第 33 题

①处应填（ ）。

{{ select(33) }}

• st.push(c)
• st.pop()
• st.top()
• return false

---

第 34 题

②处应填（ ）。

{{ select(34) }}

• !st.empty()
• st.empty()
• st.size()>1
• c==t

---

第 35 题

③处应填（ ）。

{{ select(35) }}

• st.size()
• st.top()
• st.pop()
• c

---

第 36 题

④处应填（ ）。

{{ select(36) }}

• st.push(t)
• st.pop()
• return true
• st.empty()

---

第 37 题

⑤处应填（ ）。

{{ select(37) }}

• true
• false
• st.empty()
• !st.empty()

---

第 2 组：用邻接矩阵统计无向图的度

int g[105][105]={0};
for(int i=0;i<m;i++){
    int u,v; cin>>u>>v;
    g[u][v]=____①____;
    g[v][u]=____②____;
}
for(int i=1;i<=n;i++){
    int deg=____③____;
    for(int j=1;j<=n;j++)
        deg+=____④____;
    cout<<deg<<____⑤____;
}

第 38 题

①处应填（ ）。

{{ select(38) }}

• 0
• 1
• u
• v

---

第 39 题

②处应填（ ）。

{{ select(39) }}

• 0
• 1
• u
• v

---

第 40 题

③处应填（ ）。

{{ select(40) }}

• 0
• 1
• i
• n

---

第 41 题

④处应填（ ）。

{{ select(41) }}

• g[i][j]
• g[j][j]
• i+j
• m

---

第 42 题

⑤处应填（ ）。

{{ select(42) }}

• " "
• deg
• g[i][i]
• m

---