CSP-S 初赛2022-09

2022年 CSP-S 第一轮（提高级）

题量

43 题

客观题

43 题

建议时长

120 分钟

卷面总分

100 分

开始整卷模拟计时作答 · 交卷即时判分 · 错题自动进错题本（需登录）

// questions

题目预览

单项选择题

单选题2 分

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

ls

cp

all

cd

单选题2 分

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

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

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

18s

6s

24s

30s

单选题2 分

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

dcebfa

cbdaef

bcaefd

afedcb

单选题2 分

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

插入排序

快速排序

冒泡排序

归并排序

单选题2 分

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

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

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

移除受影响的数据后，最终序列基本无序

移除受影响的数据后，最终序列是有序序列

单选题2 分

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

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

DE、EF

DE、DE

EF、EF

EF、DE

单选题2 分

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

单选题2 分

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

每个顶点的度数至少为 1

每个顶点至少都连有一条边

任意两个顶点之间都有路径相连

任意两个顶点之间都有边相连

单选题2 分

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

$(n - 1)!$

$n!2\frac{n!}{2}$

$n!$

$(n−1)!2\frac{(n-1)!}{2}$

单选题2 分

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

$32$

$56$

$64$

$28$

单选题2 分

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

$20280$

$52000$

$1757600$

$676000$

单选题2 分

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

$0$

$1$

$9$

$2$

单选题2 分

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

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

O(n)

O(n√n)

$O(n2)\mathcal{O}(n^{2})$

O(n log n)

单选题2 分

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

$n2\frac{n}{2}$

$n$

$n + 1$

$n - 1$

单选题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)); 
}

5

9

13

7

阅读程序

判断题1 分

阅读程序代码（共 16-21 题共用）

#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 可见字符组成，当输入为“abcde fg”时，输出为 -1。( )

错误

正确

判断题1 分

正确

错误

判断题1 分

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

错误

正确

单选题3 分

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

$+m)\mathcal{O}(n + m)$

$O(mlog⁡n)\mathcal{O}(m\log{n})$

$O(nlog⁡m)\mathcal{O}(n\log{m})$

$O(nm)\mathcal{O}(nm)$

单选题3 分

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

a.rfind(b)

a.substr(b)

a.compare(b)

a.find(b)

单选题3 分

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

$9$

$11$

$12$

$10$

判断题1 分

阅读程序代码（共 22-27 题共用）

#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 表示范围内，这是一个不稳定的排序算法。( )

正确

错误

判断题1 分

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，该算法的空间复杂度仅与 $n$ 有关。( )

正确

错误

判断题1 分

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，该算法的时间复杂度为 $+k))\mathcal{O}(m (n + k))$ 。( )

错误

正确

单选题3 分

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行， val[] 数组的内容依次为( )。

91 46 37 26 98

98 26 46 91 37

91 26 46 37 98

91 37 46 98 26

单选题3 分

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，若 val[i] 的最大值为 $100$ ， $k$ 取（）时算法运算次数最少。

$3$

$2$

$10$

不确定

单选题3 分

假设输入的 $n$ 为不大于 $100$ 的正整数， $k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，当输入的 $k$ 比 val[i] 的最大值还大时，该算法退化为（）算法。

冒泡排序

桶排序

选择排序

计数排序

判断题1 分

阅读程序代码（共 28-33 题共用）

#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$ 的正整数，该算法的时间复杂度为 $O(log⁡kn)\mathcal{O}(\log_{k}{n})$ 。( )

错误

正确

判断题1 分

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，删除第 23 行的强制类型转换，程序的行为不变。( )

正确

错误

判断题1 分

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，除非输入的 $n$ 为 $0$ ，否则程序输出的字符数为 $Θ(⌊log⁡k∣n∣⌋+1)\Theta(\lfloor\log_{k}{|n|}\rfloor + 1)$ 。( )

错误

正确

单选题3 分

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“100 7”时，输出为( )

$1515$

$244$

$1754$

$202$

单选题3 分

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“-255 8”时，输出为“( )”。

$417$

$400$

$1400$

$1401$

单选题3 分

假设输入的 $n$ 在 int 范围内， $k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“1000000 19”时，输出为“（）”。

BG939

7CF1B

1CD428

87GIB

完善程序

单选题3 分

阅读程序代码（共 34-38 题共用）

#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);
        }
    }
}

(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ( $1≤k≤2n1\leq k\leq 2n$ )，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。

试补全程序。

①处应填（）

(m1 + m2) * 2

(m1 - 1) + (m2 - 1)

m1 + m2

(m1 + 1) + (m2 + 1)

单选题3 分

试补全程序。

②处应填( )

a1[m1] == a2[m2]

a1[m1] != a2[m2]

a1[m1] >= a2[m2]

a1[m1] <= a2[m2]

单选题3 分

试补全程序。

③处应填( )

left1 == right1

left1 != right1

left1 < right1

left1 > right1

单选题3 分

试补全程序。

④处应填( )

y = a1[k - left2 - 1]

y = a1[k - left2]

y = a2[k - left1]

y = a2[k - left1 - 1]

单选题3 分

试补全程序。

⑤处应填( )

y = a1[k - left2]

y = a2[k - left1 - 1]

y = a2[k - left1]

y = a1[k - left2 - 1]

单选题3 分

阅读程序代码（共 39-43 题共用）

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int f[N][N];
int ans;
int a, b, c;
int init;

int dfs(int x, int y) {
    if (f[x][y] != init)
        return f[x][y];
    if (x == c || y == c)
        return f[x][y] = 0;
    f[x][y] = init - 1;
    f[x][y] = min(f[x][y], dfs(a, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, b) + 1);
    f[x][y] = min(f[x][y], dfs(0, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, 0) + 1);
    int t = min(a - x, y);
    f[x][y] = min(f[x][y], ①);
    t = min(x, b - y);
    f[x][y] = min(f[x][y], ②);
    return f[x][y];
}

void go(int x, int y) {
    if (③)
        return;
    if (f[x][y] == dfs(a, y) + 1) {
        cout << "FILL(1)" << endl;
        go(a, y);
    } else if (f[x][y] == dfs(x, b) + 1) {
        cout << "FILL(2)" << endl;
        go(x, b);
    } else if (f[x][y] == dfs(0, y) + 1) {
        cout << "DROP(1)" << endl;
        go(0, y);
    } else if (f[x][y] == dfs(x, 0) + 1) {
        cout << "DROP(2)" << endl;
        go(x, 0);
    } else {
        int t = min(a - x, y);
        if (f[x][y] == ④) {
            cout << "POUR(2,1)" << endl;
            go(x + t, y - t);
        } else {
            t = min(x, b - y);
            if (f[x][y] == ⑤) {
                cout << "POUR(1,2)" << endl;
                go(x - t, y + t);
            } else
                assert(0);
        }
    }
}

int main() {
    cin >> a >> b >> c;
    ans = 1 << 30;
    memset(f, 127, sizeof f);
    init = **f;
    if ((ans = dfs(0, 0)) == init - 1)
        cout << "impossible";
    else {
        cout << ans << endl;
        go(0, 0);
    }
}