2022 CSP-J1题目
发表于：2023-08-11 | 分类： CSP
字数统计: 4k | 阅读时长: 18分钟 | 阅读量：

一、单项选择题

第1题

以下哪种功能没有涉及C++语言的面向对象特性支持：（ ）。

A. C++ 中调用 printf 函数

B. C++ 中调用用户定义的类成员函数

C. C++ 中构造一个 class 或 struct

D. C++ 中构造来源于同一基类的多个派生类

选A。其他三个选项都有类。

第 2 题

有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。

A. 5 4 3 6 1 2

B. 4 5 3 1 2 6

C. 3 4 6 5 2 1

D. 2 3 4 1 5 6

选C。

graph LR A("3 4 5 6") -->|弹出3| B("4 5 6") -->|弹出4| C("5 6") -->|弹出6| D[6出不来] style D fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5 
1
2
3
4
5
6
7
8
9
10
graph LR
      A("3
            4
            5
            6") -->|弹出3| B("4
            5
            6") -->|弹出4| C("5
            6") -->|弹出6| D[6出不来]

 style D fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5

第 3 题

运行以下代码片段的行为是（ ）。

1
2
3
4
5
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

A. 将 x 的值赋为 201

B. 将 y 的值赋为 101

C. 将 q 指向 x 的地址

D. 将 p 指向 y 的地址

选D。

第 4 题

链表和数组的区别包括（ ）。

A. 数组不能排序，链表可以

B. 链表比数组能存储更多的信息

C. 数组大小固定，链表大小可动态调整

D. 以上均正确

选C。A错误，数组可以排序。B错误，没有上下文，不能确定。

第 5 题

对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5和 e1 出队列。则栈 S 的容量至少是（ ）个数据。

A. 2

B. 3

C. 4

D. 6

选B。出队列的顺序跟进队列的顺序一样，跟第2题差不多，出队列Q的顺序看作出栈S的顺序即可。
栈容量最多为3。

graph LR A("e2 e1") -->|弹出e2| B("e4 e3 e1") -->|弹出e4| C("e3 e1") -->|弹出e3, e5 e6进栈| D("e6 e5 e1") -->|依次弹出e6 e5 e1| empty 
1
2
3
4
5
6
7
8
graph LR
      A("e2
            e1") -->|弹出e2| B("e4
            e3
            e1") -->|弹出e4| C("e3
            e1") -->|弹出e3, e5 e6进栈| D("e6
            e5
            e1") -->|依次弹出e6 e5 e1| empty

第 6 题

对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。

A. *+a-bcd

B. +a*-bcd

C. abc-d*+

D. abc-+d

选B。

方法1：按照运算顺序，把运算符放前面。

1
2
3
4
5
6
7
8
第一个算 b - c
把 - 放前面，变成 - b c

然后乘d，(- b c) * d
* 放前面，变成 * (- b c) d

最后加a，a + * (- b c) d
+ 放前面，变成 + a * (- b c) d

方法二：根据表达式画一个二叉树，然后先序遍历。
得到+ a * - b c d

flowchart TB + --> a & * * --> - & d - --> b & c 
1
2
3
4
flowchart TB
    + --> a & *
    * --> - & d
    - --> b & c

第 7 题

假设字母表 ｛a,b,c,d,e｝ 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度（ ）位。

A. 1

B. 2

C. 2 或 3

D. 3

选B。构造哈夫曼树，每次选最小的两个数，合成一个新节点。

image-20230819120436295

到达d节点的路径为0 0，长度为2。

第 8 题

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

A. 8、18

B. 10、18

C. 8、19

D. 10、19

选C。

  • 9是奇数，是右子节点，兄弟节点在左边。
  • 左子2 * x，右子2 * x + 1，9的右子节点位置为2 * 9 + 1 = 19。

第 9 题

考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

A. N − 1

B. N

C. N+1

D. $N^2$

选B。边最少的情况，就是每个顶点只有一条入边和一条出边，连成一个圈，即连通图。

第 10 题

以下对数据结构的表述不恰当的一项为：（ ）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。

选D。虽然本质不同，但是勉强能用，比较麻烦，用两个栈就能实现。

  • 入第1个栈，变成倒序。
  • 入第2个栈，倒序反过来，就变回原来的顺序。

第 11 题

以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

B. P->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C. s->prev=p; s->next=p->next; P->next=s; p->next->prev=s;

D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

选D。

  • s->next = p->next;在p->next = s; 前，否则就变成s->next = s
  • p->next->prev = s;在p->next = s;前，否则变成s->prev = s

第 12 题

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A. 冒泡排序算法是稳定的

B. 简单选择排序是稳定的

C. 简单插入排序是稳定的

D. 归并排序算法是稳定的

选B。
image-20230819120918006

  • 稳定排序：
    • 插入排序，基数排序，归并排序，冒泡排序，计数排序。
  • 不稳定排序：
    • 快速排序，希尔排序，简单选择排序，堆排序

第 13 题

八进制数 32.1 对应的十进制数是（ ）。

A. 24.125

B. 24.250

C. 26.125

D. 26.250

选C。$38^1 + 38^0 + 1*8^{-1} = 26.125$

第 14 题

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。

A. 12

B. 13

C. 14

D. 15

选B。注意是子串，得连续，不是子序列。

  • 长度0：空串
  • 长度1: a、b、c
  • 长度2：ab、bc、ca
  • 长度3：abc、bca、cab
  • 长度4：abca、bcab
  • 长度5：abcab

第 15 题

以下对递归方法的描述中，正确的是：（ ）。

A. 递归是允许使用多组参数调用函数的编程技术

B. 递归是通过调用自身来求解问题的编程技术

C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型

D. 递归是将用某种高级语言转换为机器代码的编程技术

选B。

二、阅读程序

2.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
include <iostream>

using namespace std；

int main()
{
    unsigned short x, y；
    cin >> x >> y；
    x = (x | x << 2)& 0x33；
    x = (x | x << 1)& 0x55；
    y = (y | y << 2)& 0x33；
    y = (y | y << 1)& 0x55；
    unsigned short z = x | y << 1；
    cout << z << endl；
    return 0；
}

假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题：

判断题

1）删去第 7 行与第 13 行的 unsigned，程序行为不变。（√）

2）将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（×）

3）程序总是输出一个整数“0”。（×）

4）当输入为“2 2”时，输出为“10”。（×）

5）当输入为“2 2”时，输出为“59”。（×）

单选题

6）当输入为“13 8” 时，输出为（ ）。

A. “0”

B. “209”

C. “197”

D. “226”

选B。

image-20230819121455261

2.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;
const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m)
{
    if (m == 1) return n;
    if (n == 0) return 0;

    int ret = numeric_limits<int>::max();
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
    return ret;
}

int g(int n, int m)
{
    for (int i = 1;i <= n; i++)
        h[i][1]= i;
    for (int j = 1;j<= m; j++)
        h[0][j]= 0;

    for (int i= 1; i <= n; i++){
        for (int j= 2; j <= m; j++){
            h[i][j] = numeric_limits<int>::max();
            for (int k = 1;k <= i;k++)
                h[i][j]= min(
                h[i][j],
                max(h[i - k][j],h[k - 1][j - 1]) +1);
        }
    }

    return h[n][m];
}

int main()
{
    int n,m;
    cin >> n>> m;
    cout << f(n, m) << endl << g(n, m)<< endl;
    return 0;
}

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

判断题

1）当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ × ）

2）输出的两行整数总是相同的。（ √ ）

3）当 m 为 1 时，输出的第一行总为 n。（ √ ）

单选题

4）算法 g(n,m) 最为准确的时间复杂度分析结果为（ ）。

A. O($n^{3/2}m$)

B. O(nm)

C. O($n^2m$)

D. O($nm^2$)

选C。

5）当输入为“20 2”时，输出的第一行为（ ）。

A. “4”

B. “5”

C. “6”

D. “20”

选C。

6）当输入力“100 100”时，输出的第一行为（ ）。

A. “6”

B. “7”

C. “8”

D. “9”

选B。

2.3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>

using namespace std;

int n,k;

int solve1()
{
    int l = 0, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if (mid * mid <= n) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

double solve2(double x)
{
    if (x == 0) return x;
    for (int i = 0; i < k; i++)
        x = (x + n / x) / 2;
    return x;
}

int main()
{
    cin >> n >> k;
    double ans = solve2(solve1());
    cout << ans << ' ' << (ans * ans == n) << endl;
    return 0;
}

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

solve1函数用二分答案，找到小于等于根号n的最大整数。
solve2函数中用到了牛顿迭代法求根号。如何通俗易懂地讲解牛顿迭代法求开方（数值分析）？ - 知乎

判断题

1）该算法最准确的时间复杂度分析结果为 O(logn+k)。（ √ ）

正确，solve1二分法，时间复杂度为logn，solve2循环k次，时间复杂度为k，总的时间复杂度就为logn + k。

2）当输入为“9801 1”时，输出的第一个数为“99”。（ √ ）

正确，99的平方就是9081。

3）对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ × ）

错误。double类型有误差。

4）该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ × ）

错误，n不超过47000，mid最大47000 / 2 = 23500，int类型最大值为2147483647，开根号46341，比mid最大值大。

单选题

5）当输入为“2 1”时，输出的第一个数最接近（ ）。

A. 1

B. 1.414

C. 1.5

D. 2

选C。solve1返回1，solve2返回(1 + 2 / 1) / 2 = 1.5

6）当输入为“3 10”时，输出的第一个数最接近（ ）。

A. 1.7

B. 1.732

C. 1.75

D. 2

选B。1.732，次数越多，越接近根号3。

7）当输入为 “256 11” 时，输出的第一个数（ ）。

A. 等于 16

B. 接近但小于 16

C. 接近但大于 16

D. 前三种情况都有可能

选A。16的平方为256，solve1二分能找出来。

三、完善程序

3.1 枚举因数

从小到大打印正整数 n 的所有正因数。

试补全枚举程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> fac;
    fac.reserve((int)ceil(sqrt(n)));

    int i;
    for (i = 1; i * i < n; ++i){
        if (①){
            fac.push_back(i);
        }
    }

    for (int k = 0; k < fac.size(); ++k){
        cout << ② << "";
    }
    if (③) {
        cout << ④ << "";
    }
    for (int k = fac.size() - 1; k >= 0; --k){
        cout << ⑤ << "";
    }
}

image-20230819122914881

  1. A。判断i是否因数。
  2. B。下标访问。
  3. C。循环中运行了 1 到 根号n - 1 的数，此时 i 为根号n，没有判断是否因数，需要判断一下。
  4. D。打印i。
  5. A。打印大于根号n的数，用 n 除以 前面得到的因数 得到结果。

3.2 洪水填充

现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。
试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;

const int ROWS = 8;
const int COLS = 8;

struct Point {
    int r, c;
    Point(int r, int c): r(r), c(c) {}
};

bool is_valid(char image[ROWS][COLS], Point pt,
              int prev_color, int new_color) {
    int r = pt.r;
    int c = pt.c;
    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
            ① && image[r][c] != new_color);
}

void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;
    queue.push(cur);

    int prev_color = image[cur.r][cur.c];
    ②;

    while (!queue.empty()) {
        Point pt = queue.front ();
        queue.pop ();

        Point points[4] = {③, Point(pt.r - 1, pt.c),
                           Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        for (auto p ; points) {
            if (is_valid(image, p, prev_color, new_color)) {
                ④;
                ⑤;
            }
        }
    }
}

int main() {
    char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
                              {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
                              {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
                              {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
                              {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
                              {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
                              {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
                              {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};

    Point cur(4, 4);
    char new_color = 'y';

    flood_fill(image, cur, new_color);

    for (int r = -; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            cout << image[r][c] << '';
        }
        cout << endl;
    }
//输出:
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y g

    return 0;
}

image-20230819123011193

  1. A。与新颜色一样已经有了，还要与起点的颜色相同。
  2. B。 存完了旧颜色，起点换成新颜色。
  3. C。方向上下左右，还差方向下。
  4. D。新位置更新为新颜色。
  5. A。新位置入队列。

参考文章及视频

2022CSP-J1
上一篇:
hexo文章插入本地图片
下一篇:
17 动态规划入门

    • Copyright © 2023 - now SleepWalker | Powered by Hexo | Theme Bamboo

    本站总访问量： 次 |