CSP-J 2024 初赛模拟01

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

1. 文件型病毒传染的主要对象是（ ） {{ select(1) }}

• 文本文件
• 可执行文件
• 系统文件
• .EXE 和 .COM文件

2. 字母在计算机中是以编码形式表示的，通用的编码是 ASCII 码，字母 “A” 的 ASCII 码是 $65$ ，字母 E 的 ASCII 码是 ( )。

{{ select(2) }}

• 69
• 68
• 05
• 52

3. 两个十进制数 $(1111)_{10}$ 和 $(1010)_{10}$的异或运算结果用十进制表示是（ ）

{{ select(3) }}

• 5
• 3
• 101
• 1957

4. 用某种排序方法对线性表$25,84,21,47,15,27,68,35,20$ 进行排序，结点变化如下:

• (1) 25,84,21,47,15,27,68,35,20;

• (2) 20,15,21,25,47,27,68,35,84;

• (3) 15,20,21,25,35,27,47,68,84;

• (4) 15,20,21,25,27,35,47,68,84。

那么排序方法是（） {{ select(4) }}

• 希尔排序
• 快速排序
• 选择排序
• 归并排序

5. 以下关于 CSP 非专业级认证与 NOIP 竞赛关系的说法最恰当的是（ ）。

{{ select(5) }}

• 完全无关
• 组织者相同
• 举办目标相同
• 从属关系，CSP从属于NOIP

6. 一棵完全二叉树，共有 $1234$ 个节点，其叶子结点的个数为 ( )

{{ select(6) }}

• 616
• 615
• 617
• 210

7. Linux下可执行文件的默认扩展名为( )

{{ select(7) }}

• exe
• chm
• dll
• 都不是

8. 二叉树T，已知其先根遍历是 1 2 4 3 5 7 6 （数字为结点的编号，以下同），中根遍历是 2 4 1 5 7 3 6 ，则该二叉树的后根遍历是（ ）。

{{ select(8) }}

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

9. $2021$ 年 $7$ 月 $1$ 日是星期四，我们热烈庆贺了中国共产党成立一百周年，完成了两个一百年中的第一个。我们将在 $2049$ 年 $10$ 月 $1$ 日欢庆建国一百年，这一天是星期几？（ ）。

{{ select(9) }}

• 星期四
• 星期五
• 星期六
• 星期日

10. 八进制数 $(15264)_8$ 转换成的二进制数是（ ）。

{{ select(10) }}

• $(001101010110100)_2$
• $(101101011010101)_2$
• $(001011000110100)_2$
• $(001101010100110)_2$

11. 逻辑表达式（ ）的值与变量 $A$ 的真假无关。

{{ select(11) }}

• (A ^ B) ∨ (¬A ^ B)
• (A v B) ^ ¬A
• (A v B) ^ ¬B
• (A v B) ^ ¬A ^ B

12. 以下关于图的不正确说法是( )。

{{ select(12) }}

• 任意一个图一定有偶数个奇点
• 所有顶点的度数之和等于边数的2倍
• 所有顶点的度数之和不一定等于边数的2倍
• 在有向图中顶点的入度之和等于出度之和

13. 设变量 x 为 float 型且已赋值,则以下语句中能将 x 中的数值保留到小数点后两位,并将第三位四舍五入的是( )。

{{ select(13) }}

• x = (x / 100 + 0.5) * 100.0;
• x = (int)(x * 100 + 0.5) / 100.0;
• x = (x * 100 + 0.5) / 100.0;
• x = (x * 100) + 0.5 / 100.0;

14. 前缀表达式 + 3 * 2 + 5 12 的值是( )

{{ select(14) }}

• 37
• 65
• 23
• 25

15. 下列关于CPU存取速度的比较中，正确的是 ( )

{{ select(15) }}

• Cache > 内存 > 寄存器
• Cache > 寄存器 > 内存
• 寄存器 > Cache > 内存
• 寄存器 > 内存 > Cache

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

第一题

#include<iostream>
#include<cstdio>
using namespace std;
int daytab [2][13] = {
    {0, 31, 28, 31, 30，31, 30，31, 31, 30，31, 30，31 },
    {0, 31, 29，31, 30，31, 30，31, 31, 30，31, 30，31 }
};
bool IsLeapYear(int year) {
    return (year % 4 ==0 && year % 100 != 0) || (year % 400 == 0);
}
int main（ ） {
    int year, month, day;
    scanf("%d %d %d", &year, &month, &day);
    int number = 0;
    int row = IsLeapYear(year);
    for(int j = 0; j < month; ++j){
        number += daytab[row][j];
    }
    number += day;
    printf("%d\n", number);
    return 0;
}

1. 输入的三个数中，第二个数应是 [0, 11] 上的整数，否则会出现数组越界的问题。（ ）

{{ select(16) }}

• 正确
• 错误

2. 输入 1900 3 2 和输入 2000 3 1 ，输出结果是相同的。（ ）

{{ select(17) }}

• 正确
• 错误

3. 将第 9 行改成 return (year - 2000) % 4 == 0 ,其他地方不做改动，对程序最终的输出结果没有影响。（ ）

{{ select(18) }}

• 正确
• 错误

4. 将第 9 行改成如下四行语句:

if(year % 400 == 0) return 1;
if(year % 100 == 0) return 0;
if(year % 4 == 0) return 1;
return 0;

其他地方不做改动，对程序最终的输出结果没有影响。( )

{{ select(19) }}

• 正确
• 错误

5. 若输入的三个数为 1990 9 20，则输出为( )

{{ select(20) }}

• 253
• 263
• 273
• 283

6. 若输入的三个数为 2000 5 1,则输出为( )

{{ select(21) }}

• 122
• 123
• 124
• 125

第二题

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

const int Maxn = 10005;
int n, b[Maxn];

inline void mergesort(int * a, int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    mergesort(a, 1, mid), mergesort(a, mid + 1, r);
    int i = l, j = mid + 1, cnt = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) b[++cnt] = a[i++];
        else b[++cnt] = a[j++];
    }
    while (i <= mid) b[++cnt] = a[i++];
    while (j <= r) b[++cnt] = a[j++];
    for (i = l; i <= r; i++) a[i] = b[i - l + 1];
}

int a[Maxn];

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    mergesort(a, 1, n);
    for (int i = 1; i <= n; i++) cout << a[i] << (i == n ? '\n' : ' ');
    return 0;
}

1. 该算法中 int *a 没有传值。( )

{{ select(22) }}

• 正确
• 错误

2. 该算法会的输出换行。( )

{{ select(23) }}

• 正确
• 错误

3. 该算法中 mergesort 函数时间复杂度为 $O(nlogn)$。( )

{{ select(24) }}

• 正确
• 错误

4. 如果输入为 5 4 3 9 7 8 则输出为 3 4 7 8 9 \n。( )

{{ select(25) }}

• 正确
• 错误

5. 该算法的最劣复杂度与哪个排序算法相同( )

{{ select(26) }}

• 快速排序
• 选择排序
• 计数排序
• 堆排序

6. 下面哪句与 i==n?'\n':' ' 相同( )

{{ select(27) }}

• i!=1?'\n':' '
• 若 i == n,则 '\n',否则为' '
• 若 i != n,则 \n'，否则为' '
• ' '

第三题

#include <bits/stdc++.h>
using namespace std;
int t, x[100], a[100];
void work(int d, int i, int n) {
    int k;
    if (n == 1) {
        for (k = 0; k < d; k++) printf("%3d", a[k]);
        printf("\n");
    } else
        for (k = i; k < t; k++)
            if (n % x[k] == 0) {
                a[d] = x[k];
                work(d + 1, k, n / x[k]);
            }
}
int main（ ） {
    int i, k, n;
    cin >> n;
    for (i = n; i > 1; i--)
        if (n % i == 0) x[t++] = i;
    work(0, 0, n);
}

1. for (int i = n; i > 1; i--) if (n % i == 0) x[t++] = i; 的作用是求出 n 的所有因数。( )

{{ select(28) }}

• 正确
• 错误

2. 该程序的作用是对 n 进行质因数分解。( )

{{ select(29) }}

• 正确
• 错误

3. printf("%3d" ,a[k]); 中去掉 3 对程序没有影响。( )

{{ select(30) }}

• 正确
• 错误

4. 去掉 if(n%x[k]==0) 对程序有影响。( )

{{ select(31) }}

• 正确
• 错误

5. 如果输入为 2 ，那么输出为。( )

{{ select(32) }}

• 2
• 2 1
• 1 2
• 2 2

6. 如果输入为 72 ，那么输出有多少非空行。（ ）

{{ select(33) }}

• 14
• 15
• 16
• 17

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

第一题

田忌赛马，田忌每赢一次齐王的马就得 $200$ 金币，当然输了就扣 $200$ 金币，平局则金币数不变。

#include<bits/stdc++.h>
using namespace std;
int main（ ） {
    int n;
    while (cin >> n && n != 0) {
        int tj[1001], king[1001], count = 0;
        int tj_min = 0, tj_max = n - 1;
        int king_min = 0, king_max = n - 1;
        for (int i = 0; i < n; i++) cin >> tj[i];
        for (int i = 0; i < n; i++) cin >> king[i];
        sort(tj, tj + n);
        sort(king, king + n);
        while (n--) {
            if (tj[___(1)___] > king[___(2)___]) {
                count++;
                tj_max--;
                king_max--;
            } else if (tj[___(3)___] < king[___(4)___]) {
                count--;
                tj_min++;
                king_max--;
            } else {
                if (tj[tj_min] > king[king_min]) {
                    count++;
                    ___(5)___;
                    ___(6)___;
                } else {
                    if (___(7)___)
                        count--;
                    tj_min++;
                    ___(8)___;
                }
            }
        }
        cout << count * 200 << endl;
    }
    return 0;
}

1. (1) 和 (2) 处填（ ）

{{ select(34) }}

• tj_max和king_max
• tj_min和king_max
• tj_min和king_min
• tj_max和king_min

2. (3) 和 (4) 处填（ ）

{{ select(35) }}

• tj_min和king_max
• tj_max和king_max
• tj_min和king_min
• tj_max和king_min

3. (5) 和 (6) 处填（ ）

{{ select(36) }}

• tj_min++和king_min++
• tj_max++和king_min++
• tj_min--和king_min++
• tj_max++和king_min--

4. (7) 处填（ ）

{{ select(37) }}

• tj[tj_min] < king[king_max]
• tj[tj_min] > king[king_min]
• tj[tj_min] > king[king_max]
• tj[tj_max] < king[king_max]

5. (8) 处填（ ）

{{ select(38) }}

• king_min++
• king_max--
• king_min--
• king_max++

第二题

给出一堆长度各异的木棍，这些木棍能否头尾相连形成一个正方形? 输入: 第一行包含一个整数 $N$,为数据组数。接下来 $N$ 行，每行第一个数 $M$ 代表木棍的数量,第 $2$ 至 $M+1$ 个数为每个木棍的长度。 输出: 对每组数据，输出 yes 或 no 表示这组木棍是否能拼成正方形。 样例输入

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

样例输出

yes
no
yes

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 25;

int side;
int m;
int sticks[MAXN];
bool visit[MAXN];

bool DFS(int sum, int number, int position) {
    if(___(1)___){
        return true;
    }
    int sample = 0;
    for (int i = position; i < m; ++i) {
        if (visit[i] || sum + sticks[i] > side || ___(2)___ ) {
            continue;
        }
        visit[i] = true;
        if (___(3)___) {
            if (DFS(0, number + 1, 0)) {
                return true;
            } else {
                sample = sticks[i];
            }
        } else {
            if (DFS(sum + sticks[i], number, i + 1)) {
                return true;
            } else {
                sample = sticks[i]; 
            }
        }
        visit[i] = false;
    }
    return false;
}

bool compares(int x，int y) {
    return x > y;
}

int main（ ） {
    int n;
    scanf("%d", &n);
    while (n--) {
        int length = 0
        scanf("%d", & m);
        for(int i = 0; i < m; i++){
            scanf ("%d", &sticks[i]);
            length += sticks[i] ;
        }
        memset(visit, false, sizeof(visit));
        if(length % 4 != 0){
            printf("no\n");
            continue;
        }
        side = length / 4;
        sort(sticks, sticks + m, Compare);
        if(___(4)___){
            printf("no\n");
            continue;
        }
        if(___(5)___){
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
    return 0;
}

1. (1) 处应填（ ）。

{{ select(39) }}

• number == 0
• number == 1
• number == 2
• number == 3

2. (2) 处应填（ ）。

{{ select(40) }}

• sticks[i] < sample
• sticks[i] == sample
• sticks[i] > sample
• sticks[i] != sample

3. (3)处应填（ ）。

{{ select(41) }}

• sum + sticks[i] < side
• sum + sticks[i] == side
• sum + sticks[i] > side
• sum + sticks[i] != side

4. (4) 处应填（ ）。

{{ select(42) }}

• sticks[0] < side
• sticks[0] == side
• sticks[0] < side
• sticks[0] != side

5. (5) 处应填（ ）。

{{ select(43) }}

• DFS(0, 0, 1)
• DFS(0, 0, m)
• DFS(0, 0 ,0)
• DFS(length/4,0,0)