CSP-J 初赛模拟卷12

一、单项选择题（共15题，每题2分，共计30分;每题有且仅有一个正确选项）

1. 一棵完全二叉树的结点总数为 $41$ ，其叶结点数为( )。

{{ select(1) }}

• 18个
• 20个
• 21个
• 19个

2. C++ 程序运行时，是在哪个存储器上进行的?( )

{{ select(2) }}

• RAM
• ROM
• CACHE
• 硬盘

3. 下列不同进制的数中，最大的一个数是( )。

{{ select(3) }}

• 八进制数 $(334.1)_8$
• 二进制数 $(11011011)_2$
• 十进制数 $(220.1)_{10}$
• 十六进制数 $(D-1)_{16}$

4. 一棵树 $T$ 有 $2$ 个度数为 $2$ 的结点、有 $1$ 个度数为 $3$ 的结点、有 $3$ 个度数为 $4$ 的结点，那么树 $T$ 有( )个树叶。

{{ select(4) }}

• 18
• 14
• 6
• 7

5. 定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 “BCA” 可以将 “A” 移到 “B” 之前，变字符串 “ABC”，如果要将字符串“DACHEBGIF” 变成 “ABCDEFGHI” 最少需要( )次操作。

{{ select(5) }}

• 6
• 5
• 4
• 7

6. 计划展出 $10$ 幅不同的画，其中 $1$ 幅水彩画、 $4$ 幅油画、 $5$ 幅国画，排成一行陈列，要求同一品种的画必须连在一起，并且水彩画不放在两端，那么不同的陈列方式有( )种。

{{ select(6) }}

• 5760
• 2880
• 17280
• 8640

7. 在高速缓存系统中，主存容量为 $12MB$，Cache 容量为 $400KB$，则该存储系统的容量为()

{{ select(7) }}

• 12 MB + 400 KB
• 12 MB
• 12 MB - 12MB + 400 KB
• 12 MB - 400 KB

8. 在非空的双向链表中由 $q$ 所指向的结点右边插入一个由 $p$ 所指向的结点，其动作依次为: p->left = q; p->right = q->right; q->right=p; ()。

{{ select(8) }}

• q->left = p
• q->right->left = p
• p->right->left = p
• p->left->left = p

9. 一个自然数在十进制下有 $n$ 位，则它在二进制下的位数与() 最接近。

{{ select(9) }}

• $5n$
• $n*\text {log}_210$
• $10*\text {log}_2n$
• $n^n\text {log}_210$

10. 十进制表达式 $(3∗512+7∗64+4∗8+3)+1$ 的结果以二进制形式表示为（）。

{{ select(10) }}

• $(10111100101)_2$
• $(11111100100)_2$
• $(111110100011)_2$
• $(11111101101)_2$

11. 以下关于个人计算机操作系统的说法正确的是（ ）。

{{ select(11) }}

• Bill Gates ，他创办的 Microsoft 公司开发了 Linux 系列系统
• Steve Jobs，他的苹果公司开发了 IOS 系统
• 目前 Linux 和 Windows 系统都是开源的，网上都能搜索并下载
• Unix 不是操作系统

12. 一篇文章有 $200$ 个中文字符，$50$ 个英文字符， $20$ 个半角空格，如果只考虑存储这些文字本身需要( )个字节。

{{ select(12) }}

• 470 字节
• 270 字节
• 400 字节
• 320 字节

13. 计算机直接识别和执行的语言是（）。

{{ select(13) }}

• C++
• 汇编语言
• 高级语言
• 机器语言

14. 现代普通计算机的网关不能设置为( )。

{{ select(14) }}

• 168.10.7.100
• 10.16.13.100
• 234.123.6.5
• 127.0.0.1

15. 假设我们用 d=(a1,a2....,a5), 表示无向图 G 的 $5$ 个顶点的度数，下面给出的哪组 d 值合理（ ）。

{{ select(15) }}

• {1, 2, 2, 1, 1}
• {5, 4, 3, 2, 1}
• {2, 2, 2, 2, 2}
• {3, 3, 3, 2, 2}

二、阅读程序（程序输入不超过数组或字符串定义的范围;其中判断题1.5分，第5题分别为3,3,4分，第6题分别为4,4,4分，共计40分）

第一题

#include <iostream>
using namespace std;
int main() {
    const int SIZE = 100;
    int height[SIZE], num[SIZE], n, ans;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> height[i];
        num[i] = 1;
        for (int j = 0; j < i; j++) {
            if ((height[j] < height[i]) && (num[j] >= num[i]))
            num[i] = num[j] + 1;
        }
    }
    ans = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] > ans) ans = num[i];
    }
    cout << ans << endl;
    return 0;
}

1. n 最大可以为 99 才能保证程序不会出错误。( )

{{ select(16) }}

• 正确
• 错误

2. 程序功能：输入长度为 n 的整数序列，求最长上升子序列的长度。( )

{{ select(17) }}

• 正确
• 错误

3. 若将第 10 行的 j < i 改为 j <= i ，程序运行时会发生错误。( )

{{ select(18) }}

• 正确
• 错误

4. 本程序的时间复杂度为 $O(n^2)$ 。( )

{{ select(19) }}

• 正确
• 错误

5. 若输入

6
2 5 3 11 12 4

则输出为( )

{{ select(20) }}

• 3
• 4
• 2
• 5

6. 若输入

5
2 3 4 5 6

则第 12 行 num[i] = num[j] + 1; 执行( )次。

{{ select(21) }}

• 6
• 8
• 10
• 12

第二题

#include<bits/stdc++.h>
using namespace std;
const int mod = 2048;
long long c, n;
long long kasumi(long long x, long long mi) {
    long long res = 1;
    while (mi) {
        if (mi & 1) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        mi >>= 1;
    }
    return res;
}
int main() {
    cin >> n >> c;
    if (n == 3) {
        printf("%lld", c * (c - 1));
        return 0;
    }
    long long ans = ((kasumi(c - 1, n) + (c - 1) * kasumi(-1, n)) 
                    % mod + mod) % mod;
    cout << ans;
    return 0;
}

1. 将第 9 行 res = (res * x) % mod; 和第 11 行 x = (x * x) % mod; 的括号去掉，程序输出结果一定不变。（ ）

{{ select(22) }}

• 正确
• 错误

2. 将第 12 行的 mi >>= 1 改为 mi /= 2 ，程序输出结果一定不变。（ ）

{{ select(23) }}

• 正确
• 错误

3. 若输入为 4 4 ，则输出为 78 。（ ）

{{ select(24) }}

• 正确
• 错误

4. 此程序的时间复杂度为 $O(\text {log }n)$ 。

{{ select(25) }}

• 正确
• 错误

5. 若输入为 3 4 ，则输出为（ ）。

{{ select(26) }}

• 18
• 19
• 12
• 8

6. kasumi(2046, 13) 的返回值为（ ）。

{{ select(27) }}

• 2024
• 2
• 0
• 2022

第三题

#include<cstdio>
int n, r, num[10000];
bool mark[10000];
void print() {
    for (int i = 1; i <= r; i++)
        printf("%d ", num[i]);
    printf("\n");
}
void search(int x) {
    for (int i = 1; i <= n; i++)
        if (!mark[i]) {
            num[x] = i;
            mark[i] = true;
            if (x == r) print();
            search(x + 1);
            mark[i] = false;
        }
}
int main() {
    scanf("%d%d", & n, & r);
    search(1);
    return 0;
}

1. 若 n < r ，则程序无输出。（ ）

{{ select(28) }}

• 正确
• 错误

2. 程序结束时，对任意 $1≤i≤n$ ， mark[i] == 0 。（ ）

{{ select(29) }}

• 正确
• 错误

3. 此程序的时间复杂度为 $O(n)$ 。（ ）

{{ select(30) }}

• 正确
• 错误

4. 若输入为 4 3 ，则输出中数字 1 和 2 的个数不同。（ ）

{{ select(31) }}

• 正确
• 错误

5. 若输入为 6 3 ，则函数 print 的执行次数为（ ）。

{{ select(32) }}

• 60
• 120
• 6
• 720

6. 若输入为 7 4 ，则输出的最后一行为（ ）。

{{ select(33) }}

• 1 2 3 4
• 4 5 6 7
• 4 3 2 1
• 7 6 5 4

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

第一题

给定一个字符串 $S$，有 $q$ 组询问，每次给定一个字符串 $T$，求字符串 $T$ 是否是 $S$ 中的一个子序列。 数据保证 $1≤|S|≤10^5 ,1≤∑|T|≤10^6$，所有字符串仅包含小写字母。

#include <iostream>
using namespace std;

const int BASE = 26;

string S, T;
int q, Pos[100005][BASE];

int main(){
    cin >> S;
    int n = S.size();
    for (int i = 0; i < BASE; i++)
        ___(1)___ = -1;
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < BASE; j++)
            ___(2)___;
        ___(3)___;
    }
    cin >> q;
    while (q--){
        cin >> T;
        int len = T.size(), now = 0;
        for (int i = 0; ___(4)___; i++)
            now = ___(5)___;
        if (now != -1)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

1. (1) 处应填（）

{{ select(34) }}

• Pos[i][n - 1]
• Pos[i][n]
• Pos[n - 1][i]
• Pos[n][i]

2. (2) 处应填（）

{{ select(35) }}

• Pos[i][j] = Pos[i - 1][j]
• Pos[i][j] = Pos[i + 1][j]
• Pos[i][j] = Pos[i][j - 1]
• Pos[i][j] = Pos[i][j + 1]

3. (3) 处应填（）

{{ select(36) }}

• Pos[i][S[i] - 'a'] = i
• Pos[i][S[i] - 'A'] = i
• Pos[i][S[i]] = i
• Pos[i][i] = S[i]

4. (4) 处应填（）

{{ select(37) }}

• i < len
• now != -1
• i < len && now != n
• i < len && now != -1

5. (5) 处应填（）

{{ select(38) }}

• Pos[now][T[i] - 'a']
• Pos[now][S[i] - 'a']
• Pos[now + 1][T[i] - 'a']
• Pos[now + 1][S[i] - 'a']

第二题

(排列数)输输入两个正整数 $n,m(1<n<20.1<m<n)$ , 在 $1\sim n$ 中任取 $m$ 个数,按字典序从小到大输出所有这样的排列。

例如: 输入: 3 2 输出:

1 2
1 3
2 1
2 3
3 1
3 2

#include <iostream>
#include <cstring>
using namespace std;

const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;

int main() {
    cin >> n >> m;
    memset(used, false, sizeof(used));
    for (i = 1; i <= m; i++) {
        data[i] = i;
        used[i] = true;
    }
    flag = true;
    while (flag) {
        for (i = 1; i <= m - 1; i++) cout << data[i] << " ";
        cout << data[m] << endl;
        flag = ___(1)___;
        for (i = m; i >= 1; i--) {
            ___(2)___;
            for (j = data[i] + 1; j <= n; j++)
                if (!used[j]) {
                    used[j] = true;
                    data[i] = ___(3)___;
                    flag = true;
                    break;
                }
        if (flag) {
            for (k = i + 1; k <= m; k++)
                for (j = 1; j <= ___(4)___; j++)
                    if (!used[j]) {
                        data[k] = j;
                        used[j] = true;
                        break;
                    }
                ___(5)___;
            }
        }
    }
    return 0;
}

1. (1) 处应填( )

{{ select(39) }}

• false
• true
• 1
• -1

2. (2) 处应填( )

{{ select(40) }}

• used[i] = true
• data[i] = i
• used[data[i]] = true
• used[data[i]] = false

3. (3) 处应填( )

{{ select(41) }}

• j
• i
• true
• false

4. (4) 处应填( )

{{ select(42) }}

• n
• m
• i
• j

5. (5) 处应填( )

{{ select(43) }}

• return 0
• exit
• continue
• break