珅泽教育CSP-J第一轮模拟考第二十四套

本卷共 43 题，满分 100 分。题面已去除与作答无关的信息。

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

1. $(1047)_8 =（\quad）$。

{{ select(1) }}

• $(1011011101)_2$
• $(11010)_5$
• $(20213)_4$
• $(308)_{16}$

2. 若逻辑变量 A、C 为真，B、D 为假，以下逻辑表达式的值为假的是（ ）。

{{ select(2) }}

• $(B\lor C\lor D)\lor D\land A$
• $((\lnot A\land B)\lor C)\land\lnot B$
• $(A\land B)\lor\lnot(C\land D\lor\lnot A)$
• $A\land(D\lor\lnot C)\land B$

3. 小恺希望用下列函数计算斐波那契数列第 $n$ 项对 10000 取余：

int f(int x) {
    if (x <= 2)
        return 1;
    int ans = f(x - 1) + f(x - 2);
    ans %= 10000;
    return ans;
}

在运行空间限制 128 MB、栈空间不超过空间限制、运行时限 1 秒的情况下，在主函数中运行 f(12345)，最有可能首先发生什么问题？

{{ select(3) }}

• 运行时间超时
• 栈溢出
• 访问无效内存
• 返回错误的答案

4. 表达式 a+b*(c-d)/e-f 的后缀表达式为（ ）。

{{ select(4) }}

• -+a/*b-c-cdef
• abcd-*e/+f-
• +ab*-cd/e-f
• f-e/d-d*b+a

5. 某 MV 时长 4 分钟，每秒 10 帧，每帧 2048×1152 像素、32 位真彩色，画面不压缩且没有音频，文件约占多大空间？

{{ select(5) }}

• 21 GiB
• 27 GiB
• 168 GiB
• 2 GiB

6. 下图是一棵二叉树，它的后序遍历是（ ）。

        A
       / \
      B   C
     / \
    D   E
         \
          F

{{ select(6) }}

• ABDEFC
• DBEFAC
• DFEBCA
• ABCDEF

7. 五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是（ ）？

{{ select(7) }}

• 10
• 1024
• 15
• 120

8. 元素 a,b,c,d,e,f 依次入栈，下列不合法的出栈序列为（ ）？

{{ select(8) }}

• d,c,b,e,f,a
• f,e,d,c,b,a
• c,d,f,e,b,a
• e,d,b,a,f,c

9. 同时扔出 3 枚完全相同的六面骰子，将点数排序后，有（ ）种不同结果？

{{ select(9) }}

• 208
• 56
• 216
• 120

10. 从磁盘文件输入一个很大的二维数组，按行读与按列读相比，在输入效率上（ ）。

{{ select(10) }}

• 没有区别
• 按行读的方式更高
• 按列读的方式更高
• 取决于数组的存储方式

11. 不考虑稳定性，下列排序方法中平均时间复杂度最大的是（ ）。

{{ select(11) }}

• 插入排序
• 希尔排序
• 归并排序
• 快速排序

12. 将数组 12,23,-1,19,117,-103,79,602 按从大到小排列，每次可以交换任意两个元素，最少需要交换（ ）次。

{{ select(12) }}

• 4
• 5
• 6
• 7

13. 3 名男生和 3 名女生围成一个圈，男女必须交替；旋转后可重合视为同一种方案。共有几种方案？

{{ select(13) }}

• 18
• 15
• 12
• 9

14. 以下关于 C++ 字符串的说法，错误的是（ ）。

{{ select(14) }}

• 定义 string 类型的字符串时，不需要预先确定最大长度
• 字符数组和 string 类型的字符串可以相互转化
• 定义 char a[100] 并从键盘读入字符串时，字符串长度不能超过 99
• 定义 string s 后，获得长度的方式就是 strlen(s)

15. 中国计算机学会成立于（ ）年。

{{ select(15) }}

• 1961
• 1962
• 1971
• 1972

二、阅读程序（判断题正确填 A、错误填 B；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序一：两种排序输出

#include <iostream>
using namespace std;

const int MAXN = 1000050;
int n, a[MAXN], a1[MAXN], b[MAXN], lim;

void solve1() {
    for (int i = 1; i <= n; i++)
        b[a[i]]++; // ①
    for (int i = 1; i <= lim; i++) {
        if (b[i]) // ②
            cout << i << " ";
    }
    cout << endl;
}

void solve2() {
    int cnt = 0, flag;
    for (int i = 1; i <= n; i++) {
        flag = false;
        for (int j = 1; j <= n - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                cnt++;
                flag = true;
            }
        }
        //if (flag == false)
        //    break;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a1[i] = a[i]; // ③
        lim = max(a[i], lim); // ④
    }
    solve1();
    for (int i = 1; i <= n; i++)
        a[i] = a1[i];
    solve2();
    return 0;
}

已知 $1\le n\le10^6$，$1\le a_i\le10^6$。

16. solve2 函数实现了选择排序。

{{ select(16) }}

• 正确
• 错误

17. solve1 函数的时间复杂度为 $O(n+V)$，其中 $V$ 是 $a_i$ 的最大值。

{{ select(17) }}

• 正确
• 错误

18. 输入 7 2 3 5 7 1 4 6 时，solve2 中变量 cnt 的最终值为 9。

{{ select(18) }}

• 正确
• 错误

19. 将 solve2 函数中的双斜杠全部移除，不会影响输出结果。

{{ select(19) }}

• 正确
• 错误

20. 假设已经输入 $n=8$，哪组数据会使 solve1 与 solve2 的输出不同？

{{ select(20) }}

• 1 10 100 1000 10000 888 8888 88888
• 6321 158987 16305 68486 50556 847 156505 15610
• 777 888 999 888 777 888 999 666
• 999993 999994 999995 999996 999997 999998 999999 1000000

21. 若要使 solve1 和 solve2 的输出结果相同，应修改程序中的哪一处？

{{ select(21) }}

• ①
• ②
• ③
• ④

二、阅读程序（判断题正确填 A、错误填 B；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序二：字符串处理

#include <cstdio>
#include <cstring>

const int maxn = 1003;

int type, n, m;
char s[maxn], t[maxn];

int main() {
    scanf("%d %s %s", &type, t, s);
    n = strlen(s); m = strlen(t);
    if (type < 2) {
        for (int i = 0; i < m; ++i) s[i] = t[i];
    } else if (type == 2) {
        strcpy(s, t);
        // 提示：如果此时调用 printf("%s\n", s)，则本次输出结果为整个 t 字符串和换行，没有其他字符。
    } else {
        for (int i = 0; i < m; i += 4) {
            unsigned int code = 0, pos = i;
            for (int j = 1; pos < i + 4; j *= 100, ++pos) {
                if (pos == m) break;
                code += t[pos] * j;
            }
            pos = i;
            while (code != 0) {
                s[pos++] = code % 100;
                code /= 100;
            }
        }
    }
    for (int i = 0; i < n; ++i) printf("%c", s[i]);
    printf("\n");
}

输入保证 t 的长度不大于 s，两个字符串均只含大小写字母且非空，type 为 1、2 或 3。

22. 将程序中所有比较运算符 < 改为 !=，程序对所有合法输入的输出不变。

{{ select(22) }}

• 正确
• 错误

23. 输入 1 xyz abcd 时，程序输出 xyzd。

{{ select(23) }}

• 正确
• 错误

24. 输入 1 xyz abcd 与输入 2 xyz abcd 的输出相同。

{{ select(24) }}

• 正确
• 错误

25. 将第 25～28 行的 while 循环替换为条件和循环体相同的 do-while 循环，程序对同一合法输入的输出一定不变。

{{ select(25) }}

• 正确
• 错误

26. 若第 13 行改为 for (int i=0; i<strlen(t); ++i) s[i]=t[i];，且 type 一定为 1，用 n 表示 s 的长度、m 表示 t 的长度，程序时间复杂度为（ ）。

{{ select(26) }}

• $\Theta(n+m)$
• $\Theta(n+m^2)$
• $\Theta(n^2+m)$
• $\Theta(n^2+m^2)$

27. 分别输入哪一选项的两组数据，得到的输出不同？

{{ select(27) }}

• 1 ab abc 和 3 ab abc
• 1 AB ABC 和 3 AB ABC
• 1 de fgh 和 3 de fgh
• 1 DE FGH 和 3 DE FGH

二、阅读程序（判断题正确填 A、错误填 B；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序三：立方体滚动动态规划

#include <iostream>
using namespace std;

const int INF = 1000000000;
#define Front 0
#define Back 1
#define Left 2
#define Right 3
#define Up 4
#define Down 5
int w[6], a[1003][1003];
const int way1[] = {Up, Right, Down, Left};
const int way2[] = {Up, Front, Down, Back};
const int way3[] = {Left, Front, Right, Back};

int get_max(int &a, int b) {
    return a = max(a, b);
}

int right_rotate(int &u) {
    for (int i = 0; i < 4; ++i)
        if (u == way1[i])
            return u = way1[(i + 1) % 4];
    return u;
}

int front_rotate(int &u) {
    for (int i = 0; i < 4; ++i)
        if (u == way2[i])
            return u = way2[(i + 1) % 4];
    return u;
}

const int anchorX = Up;
const int anchorY = Front;
const int anchorZ = Right;

int find_down(int u, int v) {
    if (u == Down || u == Up) return anchorX ^ (u == Up);
    if (v == Down || v == Up) return anchorY ^ (v == Up);
    for (int i = 0; i < 4; ++i)
        if (u == way3[i])
            return anchorZ ^ (v == way3[(i + 1) % 4]);
    return -1;
}

int n, m, dp[1003][1003][6][6];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    for (int i = 0; i < 6; ++i)
        cin >> w[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            for (int a = 0; a < 6; ++a)
                for (int b = 0; b < 6; ++b)
                    dp[i][j][a][b] = -INF;
    dp[0][0][anchorX][anchorY] = a[0][0] * w[Down];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            for (int p = 0; p < 6; ++p)
                for (int q = 0; q < 6; ++q)
                    if (dp[i][j][p][q] != -INF) {
                        int x = dp[i][j][p][q];
                        int u1 = p, v1 = q;
                        right_rotate(u1);
                        right_rotate(v1);
                        get_max(dp[i][j + 1][u1][v1],
                                x + w[find_down(u1, v1)] * a[i][j + 1]);
                        int u2 = p, v2 = q;
                        front_rotate(u2);
                        front_rotate(v2);
                        get_max(dp[i + 1][j][u2][v2],
                                x + w[find_down(u2, v2)] * a[i + 1][j]);
                    }
    int ans = -INF;
    for (int p = 0; p < 6; ++p)
        for (int q = 0; q < 6; ++q)
            ans = max(ans, dp[n - 1][m - 1][p][q]);
    printf("%d\n", ans);
    return 0;
}

输入数据的绝对值均不超过 $10^3$。

28. 存在一种合法输入，使程序运行时某次 find_down 的返回值为 -1。

{{ select(28) }}

• 正确
• 错误

29. 该程序的时间复杂度为 $\Theta(n^2m^2)$。

{{ select(29) }}

• 正确
• 错误

30. 对任意 $u\in[0,6)$，先执行 front_rotate(u) 再执行 right_rotate(u)，与相反次序得到的 u 一定相同。

{{ select(30) }}

• 正确
• 错误

31. 将 anchorX、anchorY、anchorZ 依次更换为哪组值时，对全部合法数据的输出不变？

{{ select(31) }}

• Left、Front、Down
• Left、Up、Front
• Left、Down、Back
• Down、Right、Front

32. 对于下列输入，输出为（ ）。

5 5
2 8 15 1 10
5 19 19 3 5
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1 1

{{ select(32) }}

• 95
• 97
• 94
• 103

33. 对于下列输入，输出为（ ）。

2 5
2 8 15 3 10
5 19 19 3 5
1 2 3 4 5 6

{{ select(33) }}

• 194
• 157
• 193
• 201

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

程序一：支付问题

有 n 种纸币，第 i 种面值为 $a_i$ 元，每种纸币只有一张。求能支付多少种金额（不包括 0 元）。$n\le200$，$a_i$ 总和不超过 5000。

#include <iostream>
using namespace std;

const int MAXN = 210;
const int MAXM = 5010;
int n, m;
int f[MAXM], a[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ①;
    }
    ②;
    for (int i = 1; i <= n; i++)
        ③
            f[j] = ④;
    int ans = 0;
    for (int i = 1; i <= m; i++)
        if (⑤) ans++;
    cout << ans;
    return 0;
}

34. ①处应填（ ）。

{{ select(34) }}

• n += a[i]
• m += a[i]
• n = a[i]
• m = a[i]

35. ②处应填（ ）。

{{ select(35) }}

• f[0] = 1
• f[1] = 1
• a[0] = 1
• a[1] = 1

36. ③处应填（ ）。

{{ select(36) }}

• for (int j=a[i]; j<=n; j++)
• for (int j=n; j>=a[i]; j--)
• for (int j=a[i]; j<=m; j++)
• for (int j=m; j>=a[i]; j--)

37. ④处应填（ ）。

{{ select(37) }}

• f[j-1]+1
• f[j-a[i]]+1
• f[j] || f[j-a[i]]
• f[j] && f[j-a[i]]

38. ⑤处应填（ ）。

{{ select(38) }}

• f[i]
• f[i-1]
• f[i] == f[i+1]
• f[i] == f[i-1]

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

程序二：凑出 17

给定 $n(1\le n\le20)$ 个互不相同的正整数 $a_1,\ldots,a_n(1\le a_i\le10^9)$，在每个数前添加加号或减号，判断算式的值能否为 17；存在输出 Yes，否则输出 No。

#include <cstdio>

using namespace std;

const int maxn = 25;
const int aim = 17;

int n;
int a[maxn];
bool ans;

int getBit(const int s, int p) {
    return ①;
}

int main() {
    scanf("%d", &n);
    for (②) scanf("%d", a + i);
    for (int s = 0, upperBound = ③; s <= upperBound; ++s) {
        ④;
        for (int j = 0; j < n; ++j) if (getBit(s, j) == 1) {
            sum += a[j];
        } else {
            ⑤;
        }
        if (int(sum) == aim) {
            ans = true;
            break;
        }
    }
    printf("%s\n", ans ? "Yes" : "No");
}

39. ①处应填（ ）。

{{ select(39) }}

• (s >> p) & 1
• (s << p) & 1
• s & (1 << p) & 1
• s & (1 >> p) & 1

40. ②处应填（ ）。

{{ select(40) }}

• int i=0; i<=n; ++i
• int i=1; i<=n; ++i
• int i=0; i<n; ++i
• int i=1; i<n; ++i

41. ③处应填（ ）。

{{ select(41) }}

• 1 << n
• (1 << n) | 1
• (1 << n) + 1
• (1 << n) - 1

42. ④处应填（ ）。

{{ select(42) }}

• int sum = 0
• unsigned long long sum = 0
• unsigned short sum = 0
• unsigned int sum = 0

43. ⑤处应填（ ）。

{{ select(43) }}

• sum = a[j] + sum
• sum = a[j] - sum
• sum = -a[j] + sum
• sum = -a[j] - sum