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

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

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

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

---

第 1 题

冯·诺依曼计算机的核心思想之一是（ ）。

{{ select(1) }}

• 数据只能存放在寄存器
• 程序和数据都存放在存储器中
• 输入设备直接执行机器指令
• 操作系统等同于编译器

---

第 2 题

16 位有符号整数采用补码表示时，最小值是（ ）。

{{ select(2) }}

• $-32768$
• $-32767$
• $0$
• $32768$

---

第 3 题

程序 int x=40,c=0; while(x){x&=x-1;c++;} cout<<c; 输出（ ）。

{{ select(3) }}

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

---

第 4 题

执行 string s="cspj2026"; cout<<s.substr(4,4);，输出（ ）。

{{ select(4) }}

• j202
• 2026
• spj2
• 026

---

第 5 题

函数 f(n) 在 $n\le0$ 时返回，否则先输出 n，递归调用 f(n-2)，再输出 n。调用 f(4) 输出（ ）。

{{ select(5) }}

• 42
• 424
• 422
• 4224

---

第 6 题

有序数组 1,2,2,4,7 下标从 0 开始，lower_bound 查找 2 返回（ ）。

{{ select(6) }}

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

---

第 7 题

队列初始为 1,2,3。重复两次：弹出队首 x，再把 x+3 加入队尾。最终队首和队尾分别是（ ）。

{{ select(7) }}

• 2 4
• 2 5
• 3 5
• 3 6

---

第 8 题

下面通常稳定的排序算法是（ ）。

{{ select(8) }}

• 选择排序
• 快速排序
• 插入排序
• 堆排序

---

第 9 题

对 64 个有序元素使用标准闭区间二分，最坏比较次数至多为（ ）。

{{ select(9) }}

• $5$
• $6$
• $7$
• $64$

---

第 10 题

某非空二叉树有 9 个叶子结点，则度为 2 的结点数为（ ）。

{{ select(10) }}

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

---

第 11 题

大根堆数组 20,15,18,8,10,12,17 删除根并下沉后为（ ）。

{{ select(11) }}

• 18 15 17 8 10 12
• 18 17 15 8 10 12
• 17 15 18 8 10 12
• 15 18 17 8 10 12

---

第 12 题

权值 4,5,9,12,13 构造哈夫曼树，WPL 是（ ）。

{{ select(12) }}

• $86$
• $90$
• $95$
• $100$

---

第 13 题

使用邻接矩阵存储含 n 个顶点的图，空间复杂度通常为（ ）。

{{ select(13) }}

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

---

第 14 题

无向图有边 (1,2),(2,3),(4,5) 和孤立点 6，共有几个连通块？

{{ select(14) }}

• $2$
• $3$
• $4$
• $6$

---

第 15 题

一个简单无向完全图有 6 个顶点，它的边数是（ ）。

{{ select(15) }}

• $6$
• $12$
• $15$
• $30$

---

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

---

第 1 组：字符串行程长度编码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t="";cin>>s;
    for(int i=0;i<(int)s.size();){
        int j=i;
        while(j<(int)s.size()&&s[j]==s[i])j++;
        int cnt=j-i;t+=s[i];
        if(cnt>1)t+=to_string(cnt);
        i=j;
    }
    cout<<t<<" "<<t.size();
}

第 16 题

输入 AAABCCCCDD 时，程序输出 A3BC4D2 7。

{{ input(16) }}

---

第 17 题

某字符只连续出现一次时，编码结果中不会附加数字 1。

{{ input(17) }}

---

第 18 题

若把条件 cnt>1 改为 cnt>=1，输入 AAABCCCCDD 时编码串变为 A3B1C4D2。

{{ input(18) }}

---

第 19 题

输入 ZZZZXY 时，编码串是（ ）。

{{ select(19) }}

• Z4XY
• ZZZZXY
• Z4X1Y1
• 4ZXY

---

第 20 题

若输入长度为 n，该程序的时间复杂度是（ ）。

{{ select(20) }}

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

---

第 2 组：栈与队列组合模拟

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[]={7,5,8,3,1,4,2}; stack<int> st; queue<int> q;
    for(int x:a){
        if(x%2)st.push(x);
        else if(!st.empty()){q.push(st.top()+x);st.pop();}
    }
    while(!q.empty()){cout<<q.front()<<" ";q.pop();}
    cout<<"|";
    while(!st.empty()){cout<<st.top()<<" ";st.pop();}
}

第 21 题

程序输出 13 5 5 |7。

{{ input(21) }}

---

第 22 题

处理完数组后，输出前栈中只剩一个元素。

{{ input(22) }}

---

第 23 题

若遇到偶数时栈为空，该偶数不会进入队列。

{{ input(23) }}

---

第 24 题

第一次进入队列的数是（ ）。

{{ select(24) }}

• $5$
• $8$
• $12$
• $13$

---

第 25 题

若把入队值改成偶数 x 本身，队列输出将变为（ ）。

{{ select(25) }}

• 8 4 2
• 7 3 1
• 13 5 5
• 2 4 8

---

第 26 题

若在数组末尾再添加偶数 6，最终队列和栈的状态是（ ）。

{{ select(26) }}

• 队列多一个13，栈为空
• 队列多一个7，栈为空
• 队列不变，栈剩7
• 程序访问空栈

---

第 3 组：由前序和中序还原二叉树

#include <bits/stdc++.h>
using namespace std;
struct Node{char c;Node*l,*r;Node(char x):c(x),l(nullptr),r(nullptr){}};
string pre="ABDECF",in="DBEACF";
Node* build(int pl,int pr,int il,int ir){
    if(pl>pr)return nullptr; char root=pre[pl]; int k=il;
    while(in[k]!=root)k++; int left=k-il; Node*u=new Node(root);
    u->l=build(pl+1,pl+left,il,k-1);u->r=build(pl+left+1,pr,k+1,ir);return u;
}
void post(Node*u){if(!u)return;post(u->l);post(u->r);cout<<u->c;}
int height(Node*u){return !u?0:1+max(height(u->l),height(u->r));}
int leaf(Node*u){return !u?0:(!u->l&&!u->r?1:leaf(u->l)+leaf(u->r));}

第 27 题

程序构造出的树后序遍历为 DEBFCA。

{{ input(27) }}

---

第 28 题

构造出的树高为 3。

{{ input(28) }}

---

第 29 题

构造出的树共有 3 个叶子结点。

{{ input(29) }}

---

第 30 题

整棵树的根结点是（ ）。

{{ select(30) }}

• A
• B
• C
• D

---

第 31 题

只给出前序序列时，对一般二叉树（ ）。

{{ select(31) }}

• 一定能唯一还原
• 通常不能唯一还原
• 一定是完全二叉树
• 一定是 BST

---

第 32 题

当前程序每次在线性区间查找根在中序中的位置，最坏时间复杂度是（ ）。

{{ select(32) }}

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

---

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

---

第 1 组：第一个大于等于 x 的位置

int lowerPos(int a[],int n,int x){
    int l=0,r=____①____;
    while(____②____){
        int mid=____③____;
        if(a[mid]<x) ____④____;
        else ____⑤____;
    }
    return l;
}

第 33 题

①处应填（ ）。

{{ select(33) }}

• n-1
• n
• 0
• x

---

第 34 题

②处应填（ ）。

{{ select(34) }}

• l<=r
• l<r
• l>r
• a[l]==x

---

第 35 题

③处应填（ ）。

{{ select(35) }}

• l+r
• (r-l)/2
• l+(r-l)/2
• r/2

---

第 36 题

④处应填（ ）。

{{ select(36) }}

• l=mid+1
• l=mid
• r=mid-1
• r=mid

---

第 37 题

⑤处应填（ ）。

{{ select(37) }}

• l=mid+1
• l=mid
• r=mid-1
• r=mid

---

第 2 组：哈夫曼 WPL

priority_queue<int,vector<int>,____①____> q;
for(int x:w)q.push(x);
int ans=0;
while(____②____){
    int x=q.top();q.pop();int y=q.top();q.pop();
    int z=____③____;
    ans+=z;
    ____④____;
}
cout<<____⑤____;

第 38 题

①处应填（ ）。

{{ select(38) }}

• less<int>
• greater<int>
• vector<int>
• queue<int>

---

第 39 题

②处应填（ ）。

{{ select(39) }}

• q.empty()
• q.size()>1
• q.size()==1
• ans==0

---

第 40 题

③处应填（ ）。

{{ select(40) }}

• x-y
• max(x,y)
• x+y
• 1

---

第 41 题

④处应填（ ）。

{{ select(41) }}

• q.pop()
• q.push(z)
• q.push(ans)
• break

---

第 42 题

⑤处应填（ ）。

{{ select(42) }}

• q.size()
• w.size()
• ans
• z-x

---