CSP 2022 提高级第一轮

ID: 408

客观题

尝试: 1

已通过: 0

难度: 10

上传者:

kayn

标签>

初赛

CSP 2022 提高级第一轮（2022 CCF 非专业级别软件能力认证第一轮，提高级 C++ 语言试题）满分 100 分，时长 120 分钟。

一、单项选择题

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

第 1 题（2 分）

在 Linux 系统终端中，用于切换工作目录的命令为（）。

ls
cd
cp
all

第 2 题（2 分）

你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：

real   0m30.721s 
user   0m24.579s 
sys    0m6.123s

以下最接近秒表计时的时长为（）。

第 3 题（2 分）

若元素 $a,b,c,d,e,f$ 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（）。

dcebfa
cbdaef
bcaefd
afedcb

第 4 题（2 分）

考虑对 $n$ 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（）。

插入排序
冒泡排序
归并排序
快速排序

第 5 题（2 分）

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（）。

移除受影响的数据后，最终序列是有序序列
移除受影响的数据后，最终序列是前后两个有序的子序列
移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
移除受影响的数据后，最终序列基本无序

第 6 题（2 分）

计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++ 代码段表示的程序，将分别输出什么结果？（）

unsigned x = 0xDEADBEEF; 
unsigned char *p = (unsigned char *)&x; 
printf("%X", *p);

EF、EF
EF、DE
DE、EF
DE、DE

第 7 题（2 分）

一个深度为 $5$ （根结点深度为 $1$ ）的完全 3 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 $100$ 号结点的父结点是第（）号。

第 8 题（2 分）

强连通图的性质不包括（）。

每个顶点的度数至少为 1
任意两个顶点之间都有边相连
任意两个顶点之间都有路径相连
每个顶点至少都连有一条边

第 9 题（2 分）

每个顶点度数均为 $2$ 的无向图称为“2 正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为（）。

$n!$
$(n-1)!$
$\dfrac{n!}{2}$
$\dfrac{(n-1)!}{2}$

第 10 题（2 分）

共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（）

第 11 题（2 分）

小明希望选到形如“省 A·LLDDD”的车牌号。车牌号在“·”之前的内容固定的 5 位号码中，前 2 位必须是大写英文字母，后 3 位必须是阿拉伯数字（L 代表 A 至 Z，D 表示 0 至 9，两个 L 和三个 D 之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。（）

20280
52000
676000
1757600

第 12 题（2 分）

给定地址区间为 $0\sim 9$ 的哈希表，哈希函数为 $h(x)=x\%10$ ，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储 (71, 23, 73, 99, 44, 79, 89) 后，请问 89 存储在哈希表哪个地址中。（）

第 13 题（2 分）

对于给定的 $n$ ，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 1; j < n; j*=2) {
        k = k + n / 2;
    }
}

$O(n)$
$O(n \log n)$
$O(n\sqrt{n})$
$O(n^2)$

第 14 题（2 分）

以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（）次运算。

$n/2$
$n-1$
$n$
$n+1$

第 15 题（2 分）

ack 函数在输入参数 (2,2) 时的返回值为（）。

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}

二、阅读程序

（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int f(const string &s, const string &t)
{
    int n = s.length(), m = t.length();

    vector<int> shift(128, m + 1);

    int i, j;

    for (j = 0; j < m; j++)
        shift[t[j]] = m - j;

    for (i =0; i<= n - m; i += shift[s[i + m]]){
        j =0;
        while(j < m && s[i +j] == t[j]) j++;
        if (j == m) return i;
    }

    return -1;
}

int main()
{
    string a ,b;
    cin >> a >> b;
    cout << f(a, b) << endl;
    return 0;
}

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

判断题

第 16 题（1 分）

当输入为“abcde fg”时，输出为 -1。（）

正确
错误

第 17 题（1.5 分）

当输入为“abbababbbab abab”时，输出为 4。（）

正确
错误

第 18 题（1.5 分）

当输入为“GoodLuckCsp2022 22”时，第 $20$ 行的“j++”语句执行次数为 2。（）

正确
错误

单选题

第 19 题（3 分）

该算法最坏情况下的时间复杂度为（）。

$O(n+m)$
$O(n \log m)$
$O(m \log n)$
$O(nm)$

第 20 题（3 分）

f(a, b) 与下列（）语句的功能最类似。

a.find(b)
a.rfind(b)
a.substr(b)
a.compare(b)

第 21 题（3 分）

当输入为“baaabaaabaaabaaaa aaaa”，第 $20$ 行的“j++”语句执行次数为（）。

（2）

#include <iostream>

using namespace std;

const int MAXN = 105;

int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];

void init()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> val[i];
    int maximum = val[0];
    for (int i = 1; i < n; i++)
        if (val[i] > maximum) maximum = val[i];
    m = 1;
    while (maximum >= k) {
        maximum /= k;
        m++;
    }
}

void solve()
{
    int base = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) cnt[j] = 0;
        for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
        for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
        for (int j = n - 1; j >= 0; j--) {
            temp[cnt[val[j] / base % k] - 1] = val[j];
            cnt[val[j] / base % k]--;
        }
        for (int j = 0; j < n; j++) val[j] = temp[j];
        base *= k;
    }
}

int main()
{
    init();
    solve();
    for (int i = 0; i < n; i++) cout << val[i] << ;
    cout << endl;
    return 0;
}

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， $val[i]$ 在 int 表示范围内，完成下面的判断题和单选题：

判断题

第 22 题（1.5 分）

这是一个不稳定的排序算法。（）

正确
错误

第 23 题（1.5 分）

该算法的空间复杂度仅与 $n$ 有关。（）

正确
错误

第 24 题（1.5 分）

该算法的时间复杂度为 $O(m(n+k))$ 。（）

正确
错误

单选题

第 25 题（3 分）

当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 $36$ 行，val[] 数组的内容依次为（）。

91 26 46 37 98
91 46 37 26 98
98 26 46 91 37
91 37 46 98 26

第 26 题（3 分）

若 val[i] 的最大值为 $100$ ， $k$ 取（）时算法运算次数最少。

2
3
10
不确定

第 27 题（3 分）

当输入的 $k$ 比 val[i] 的最大值还大时，该算法退化为（）算法。

选择排序
冒泡排序
计数排序
桶排序

（3）

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXL = 1000;

int n, k, ans[MAXL];

int main(void)
{
    cin >> n >> k;
    if (!n) cout << 0 << endl;
    else
    {
        int m = 0;
        while (n)
        {
            ans[m++] = (n % (-k) + k) % k;
            n = (ans[m - 1] - n) / k;
        }
        for (int i = m - 1; i >= 0; i--)
            cout << char(ans[i] >= 10 ?
                         ans[i] + 'A' - 10 :
                         ans[i] + '0');
        cout << endl;
    }
    return 0;
}

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，完成下面的判断题和单选题：

判断题

第 28 题（1.5 分）

该算法的时间复杂度为 $O(\log_k n)$ 。（）

正确
错误

第 29 题（1.5 分）

删除第 $23$ 行的强制类型转换，程序的行为不变。（）

正确
错误

第 30 题（1.5 分）

除非输入的 $n$ 为 $0$ ，否则程序输出的字符数为 $\lfloor \log_k|n|\rfloor+1$ 。（）

正确
错误

单选题

第 31 题（3 分）

当输入为“100 7”时，输出为（）。

202
1515
244
1754

第 32 题（3 分）

当输入为“-255 8”时，输出为（）。

1400
1401
417
400

第 33 题（3 分）

当输入为“1000000 19”时，输出为（）。

BG939
87GIB
1CD428
7CF1B

三、完善程序

（单选题，每小题 3 分，共计 30 分）

（1）（归并第 $k$ 小）

已知两个长度均为 $n$ 的有序数组 $a_1$ 和 $a_2$ （均为递增序，但不保证严格单调递增），并且给定正整数 $k$ （ $1\le k\le 2n$ ），求数组 $a_1$ 和 $a_2$ 归并排序后的数组里第 $k$ 小的数值。

试补全程序。

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

int solve(int *a1, int *a2, int n, int k) {
    int left1 = 0, right1 = n - 1;
    int left2 = 0, right2 = n - 1;
    while (left1 <= right1 && left2 <= right2) {
        int m1 = (left1 + right1) >> 1;
        int m2 = (left2 + right2) >> 1;
        int cnt = ①;
        if (②) {
            if (cnt < k) left1 = m1 + 1;
            else right2 = m2 - 1;
        } else {
            if (cnt < k) left2 = m2 + 1;
            else right1 = m1 - 1;
        }
    }
    if (③) {
        if (left1 == 0) {
            return a2[k - 1];
        } else {
            int x = a1[left1 - 1], ④;
            return std::max(x, y);
        } 
    } else {
            if (left2 == 0) {
                return a1[k - 1];
            } else {
                int x = a2[left2 - 1], ⑤;
                return std:: max(x, y);
            }
    }
}

第 34 题（3 分）

①处应填（）

(m1 + m2) * 2
(m1 - 1) + (m2 - 1)
m1 + m2
(m1 + 1) + (m2 + 1)

第 35 题（3 分）

②处应填（）

a1[m1] == a2[m2]
a1[m1] <= a2[m2]
a1[m1] >= a2[m2]
a1[m1] != a2[m2]

第 36 题（3 分）

③处应填（）

left1 == right1
left1 < right1
left1 > right1
left1 != right1

第 37 题（3 分）

④处应填（）

y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]

第 38 题（3 分）

⑤处应填（）

y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]

（2）（容器分水）

有两个容器，容器 1 的容量为 $a$ 升，容器 2 的容量为 $b$ 升；同时允许下列的三种操作，分别为：

FILL(i)：用水龙头将容器 $i\ (i\in\{1,2\})$ 灌满水；
DROP(i)：将容器 $i$ 的水倒进下水道；
POUR(i,j)：将容器 $i$ 的水倒进容器 $j$ （完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 $c$ 升水的最少操作数和操作序列。上述 $a,b,c$ 均为不超过 $100$ 的正整数，且 $c\le\max\{a,b\}$ 。