ID: 1432

客观题

尝试: 9

已通过: 1

难度: 10

上传者:

Teacher_chen

CSP-J1 第一期综合卷

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

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

第 1 题

假设 unsigned char 占 8 位。执行以下程序，输出为。

unsigned char x = 250;
x = x + 10;
cout << (int)x;

（ {{ select(1) }} ）

$260$
$0$
$4$
$6$

第 2 题

表达式 $(101101_2\oplus 33_{10})\mathbin{\&}31_{10}$ 的十进制结果为（ {{ select(2) }} ），其中 $\oplus$ 表示按位异或。

$8$
$12$
$28$
$44$

第 3 题

下面程序段中语句 cnt++ 的执行次数关于 $n$ 的时间复杂度是。

for (int i=1; i<=n; i*=2)
    for (int j=0; j<i; ++j) cnt++;

（ {{ select(3) }} ）

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

第 4 题

执行下面程序后，x 和 y 的值分别为。

void f(int a,int &b){ a+=b; b=a-b; }
int x=7,y=4; f(x,y);

（ {{ select(4) }} ）

11 7
7 7
7 4
11 4

第 5 题

执行下面代码后，a.size() 和 it-a.begin() 分别为。

vector<int> a={5,1,5,2,2,4};
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
auto it=upper_bound(a.begin(),a.end(),3);

（ {{ select(5) }} ）

4 1
4 2
5 2
4 3

第 6 题

执行下面代码，输出为。

map<int,int> m;
m[3]++;
m[1]=m[3]+2;
int x=m[2];
cout<<m.size()<<" "<<m[1]+x;

（ {{ select(6) }} ）

2 3
3 2
3 3
2 2

第 7 题

元素 1,2,3,4,5,6 依次入栈，入栈过程中可以随时出栈。下列不可能的出栈序列是（ {{ select(7) }} ）。

2 1 4 3 6 5
3 2 1 6 5 4
3 1 2 6 5 4
1 2 6 5 4 3

第 8 题

长度为 8 的数组实现循环队列，并规定必须始终空出一个位置来区分“队空”和“队满”。该队列最多能保存（ {{ select(8) }} ）个元素。

第 9 题

用插入排序将 4,1,3,2 升序排列。若每次把一个较大元素向后移动一格记作一次移动，共移动（ {{ select(9) }} ）次。

第 10 题

有序数组 1,2,2,2,4,7 下标从 0 开始。对数值 2 调用 lower_bound 和 upper_bound，所得下标及 2 的出现次数分别为（ {{ select(10) }} ）。

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

第 11 题

一棵完全二叉树按 1 开始编号，共 42 个结点。编号 21 的结点（ {{ select(11) }} ）。

没有子结点
只有编号 42 的左子结点
只有编号 42 的右子结点
有编号 42、43 的两个子结点

第 12 题

某二叉树前序遍历为 MBADCFQPR，中序遍历为 ABCDFMPQR，其后序遍历为（ {{ select(12) }} ）。

ACFDBPRQM
ACFDBRPQM
ACFBDPRQM
ABCFDPRQM

第 13 题

大根堆按数组表示为 50,30,40,10,20,35。插入 45 并完成向上调整后，数组为（ {{ select(13) }} ）。

50,45,40,10,20,35,30
50,30,45,10,20,35,40
50,30,40,10,20,35,45
45,30,50,10,20,35,40

第 14 题

用权值 3,7,8,12,20 构造哈夫曼树，其带权路径长度 WPL 为（ {{ select(14) }} ）。

$88$
$98$
$108$
$118$

第 15 题

有向图的边为 (1,2),(1,3),(3,2),(2,4),(4,3)。顶点 2 的入度、出度以及邻接矩阵中非零元素个数分别为（ {{ select(15) }} ）。

1 2 5
2 1 5
2 1 10
1 2 10

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

阅读程序（1）：词频排序

假设每个字符的出现次数均不超过 9。

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

int main(){
    string s;
    cin>>s;
    map<char,int> cnt;
    for(char c:s) cnt[c]++;

    vector<pair<int,char>> v;
    for(auto p:cnt) v.push_back({-p.second,p.first});
    sort(v.begin(),v.end());

    string t;
    for(auto p:v){
        t+=p.second;
        t+=char('0'-p.first);
    }
    cout<<t<<" "<<cnt.size();
}

第 16 题

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

第 17 题

pair 默认先比较 first，再比较 second，所以程序按出现次数降序排列，次数相同时按字符升序排列（ {{ input(17) }} ）。

第 18 题

若把 {-p.second,p.first} 改为 {p.second,p.first}，则字符会按出现次数升序排列，次数相同时仍按字符升序排列（ {{ input(18) }} ）。

第 19 题

输入 ABRACADABRA 时，程序输出的字符串部分为（ {{ select(19) }} ）。

A5B2R2C1D1
A5R2B2D1C1
C1D1B2R2A5
A5B2C1D1R2

第 20 题

设输入长度为 $n$ ，不同字符数为 $k$ 。不计输出字符串所占时间，该程序时间复杂度最准确的是（ {{ select(20) }} ）。

$O(1)$
$O(n)$
$O(n\log k+k\log k)$
$O(nk)$

阅读程序（2）：插入排序与二分定位

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

int main(){
    int n,x;
    cin>>n>>x;
    vector<int> a(n);
    for(int &v:a) cin>>v;

    long long moves=0;
    for(int i=1;i<n;i++){
        int key=a[i],j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1]=a[j];
            j--; moves++;
        }
        a[j+1]=key;
    }

    int l=0,r=n;
    while(l<r){
        int mid=l+(r-l)/2;
        if(a[mid]<x) l=mid+1;
        else r=mid;
    }
    cout<<moves<<" "<<l<<" "<<(l<n?a[l]:-1);
}

第 21 题

输入 7 4 5 2 4 2 8 1 4 时，程序输出 11 3 4（ {{ input(21) }} ）。

第 22 题

变量 moves 的最终值等于原数组中的逆序对数量（ {{ input(22) }} ）。

第 23 题

把条件 a[j]>key 改成 a[j]>=key，可能改变 moves，但最终数值序列仍然非降序（ {{ input(23) }} ）。

第 24 题

该程序最坏时间复杂度为（ {{ select(24) }} ）。

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

第 25 题

若输入 8 5 8 7 6 5 4 3 2 1，程序输出为（ {{ select(25) }} ）。

28 4 5
28 5 5
27 4 5
28 4 4

第 26 题

若删除整个插入排序循环，而输入数组不保证有序，则后面的二分部分（ {{ select(26) }} ）。

仍总能找到第一个大于等于 x 的元素
可能得到错误结果，因为二分所需的单调性被破坏
一定产生编译错误
一定陷入死循环

阅读程序（3）：用数组下标表示二叉搜索树

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

const int N=20;
int key[N],cnt[N],lc[N],rc[N],tot=0,root=0;

int newNode(int x){
    ++tot;
    key[tot]=x;
    cnt[tot]=1;
    return tot;
}

void insertNode(int x){
    if(root==0){ root=newNode(x); return; }
    int u=root;
    while(true){
        if(x==key[u]){ cnt[u]++; return; }
        if(x<key[u]){
            if(lc[u]==0){ lc[u]=newNode(x); return; }
            u=lc[u];
        }else{
            if(rc[u]==0){ rc[u]=newNode(x); return; }
            u=rc[u];
        }
    }
}

int height(int u){
    return u==0?0:1+max(height(lc[u]),height(rc[u]));
}
int leaves(int u){
    if(u==0) return 0;
    if(lc[u]==0&&rc[u]==0) return 1;
    return leaves(lc[u])+leaves(rc[u]);
}
long long weighted(int u,int d){
    if(u==0) return 0;
    return 1LL*cnt[u]*d+weighted(lc[u],d+1)+weighted(rc[u],d+1);
}

int main(){
    int a[]={8,3,10,1,6,14,4,7,13,6};
    for(int x:a) insertNode(x);
    cout<<height(root)<<" "<<leaves(root)<<" "<<weighted(root,0);
}

第 27 题

程序输出 4 4 19（ {{ input(27) }} ）。

第 28 题

数组中第二次出现的 6 不会创建新结点，只会使相应结点的 cnt 增加（ {{ input(28) }} ）。

第 29 题

若对这棵树进行中序遍历并且每个结点只输出一次 key，所得序列严格递增（ {{ input(29) }} ）。

第 30 题

程序执行完毕后，实际创建了（ {{ select(30) }} ）个结点。

$8$
$9$
$10$
$11$

第 31 题

在该树中查找 13，依次需要与（ {{ select(31) }} ）个结点的 key 比较。

第 32 题

若将 $n$ 个严格递增的不同整数依次插入一棵空二叉搜索树，则最终树高和全部插入操作的最坏时间复杂度分别为（ {{ select(32) }} ）。

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

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

完善程序（1）：有序数组分段计数

给定 $n$ 个整数，将它们从小到大排序，然后统计每个不同整数的出现次数，并按“数值:次数”的形式依次输出。相邻两项之间用一个空格分隔。例如，数组 3,1,3,2,1,1 应输出 1:3 2:1 3:2。已知 a 为长度 $n$ 的 vector<int>。试补全程序。

// 输入 n 个整数，排序后依次输出“数值:出现次数”。
sort(a.begin(),a.end());
vector<int> value,times;
for(int i=0;i<n;){
    int j=i;
    while(j<n && a[j]==a[i]) j++;
    value.push_back(____①____);
    times.push_back(____②____);
    i=____③____;
}
for(int k=0;k<(int)____④____;k++)
    cout<<value[k]<<":"<<times[k]<<____⑤____;

第 33 题

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

a[j]
a[i]
i
j-i

第 34 题

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

j-i
i-j
j
1

第 35 题

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

i+1
j
j+1
n

第 36 题

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

a.size()
times[k]
value.size()
n-1

第 37 题

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

" "
value[k]
times.size()
endl()

完善程序（2）：由前序和中序输出后序

一棵二叉树的所有结点用互不相同的大写英文字母表示。给定该树的前序遍历字符串 pre 和中序遍历字符串 in，两者长度相等且描述同一棵树。程序利用两个序列唯一还原二叉树，并直接输出其后序遍历。初次调用为 printPost(0, pre.size()-1, 0, in.size()-1)。试补全程序。

string pre,in;

void printPost(int pl,int pr,int il,int ir){
    if(____①____) return;
    int k=il;
    while(in[k]!=____②____) k++;
    int left=____③____;
    printPost(pl+1,____④____,il,k-1);
    printPost(pl+left+1,pr,k+1,ir);
    cout<<____⑤____;
}

第 38 题

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

pl>pr
pl<pr
il<ir
k==il

第 39 题

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

pre[pr]
pre[pl]
in[il]
in[ir]

第 40 题

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

ir-k
k-il
pr-pl
k+il

第 41 题

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

pl+left
pr-left
k-1
pl+left+1

第 42 题

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

in[il]
pre[pr]
pre[pl]
in[ir]

#P1429. CSP-J1 第一期综合卷

CSP-J1 第一期综合卷

CSP-J1 第一期综合卷

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

第 1 题

第 2 题

第 3 题

第 4 题

第 5 题

第 6 题

第 7 题

第 8 题

第 9 题

第 10 题

第 11 题

第 12 题

第 13 题

第 14 题

第 15 题

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

阅读程序（1）：词频排序

第 16 题

第 17 题

第 18 题

第 19 题

第 20 题

阅读程序（2）：插入排序与二分定位

第 21 题

第 22 题

第 23 题

第 24 题

第 25 题

第 26 题

阅读程序（3）：用数组下标表示二叉搜索树

第 27 题

第 28 题

第 29 题

第 30 题

第 31 题

第 32 题

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

完善程序（1）：有序数组分段计数

第 33 题

第 34 题

第 35 题

第 36 题

第 37 题

完善程序（2）：由前序和中序输出后序

第 38 题

第 39 题

第 40 题

第 41 题

第 42 题

登录