CSP-J2019初赛个人错题整理

程序员文章站 2022-06-03 13:26:47

...

CSP-J2019

5.设有100个已排好序的数据元素，采用折半查找时，最大比较次数为()
A.7 B.10 C.6 D.8
答案：A
试题分析：折半查找，首先将待查记录所在范围缩小一半，然后再缩小一半，即对100个元素进行折半查找，第一次比较范围缩小到50，第二次缩小到25，第三次缩小到17，第四次缩小到7，第五次缩小到4，第六次缩小到2，最多七次就可以查找到所要元素。
1.

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

判断题
1)输入的字符串只能由小写字母或大写字母组成。()
答案：×
试题分析：题目没说，可以输入包含其他字符的字符串。

2)若将第8行的“i=1”改为“i=0”,程序运行时会发生错误()
答案：√
试题分析：不能对0取余操作，错误。

3)若将第8行的“i<=n”改为“ii<=n”,程序运行结果不会改变()
答案：×
试题分析：求约数不是判断质数，ii<=n只能取到n的前半部分约数。

4)若输入的字符串全部由大写字母组成,那么输出的字符串就跟输入的字符串一样。()
答案：√
试题分析：按题意说明即可判断。

选择题
5)若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比至多有()个字符不同。
A.18 B.6 C.10 D.1
答案：B
试题分析：约数个数定理求约数个数。18的约数是：1，2，3，6，9，18。所以最多判定6次。

6)若输入的字符串长度为(),那么输入的字符串跟输出的字符申相比,至多有36个字符不同。
A.36 B.100000 C.1 D.128
答案：B
试题分析：和上题同理。枚举4个选项。36有9个约数，1有1个约数，128有8个约数。选B。100000有36个约数。
2.

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x] < y && b[y] < x) {
            if (a[x] > 0)
                b[a[x]] = 0;
            if (b[y] > 0)
                a[b[y]] = 0;
            a[x] = y;
            b[y] = x;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0)
            ++ans;
        if (b[i] == 0)
            ++ans;
    }
    printf("%d", ans);
    return 0;
}

假设输入的n和m都是正整数,x和y都是在[1,n]的范围内的整数，完成下面的判断题和单选题

判断题
1)当m>0时,输出的值一定小于2n。()
答案：√
试题分析：按照题意，a数组和b数组赋值为0，a[x] < y && b[y] < x成立，累计计算求和，最终结果肯定小于2n。

2)执行完第27行的“++ans”时,ans一定是偶数。()
答案：×
试题分析：不一定，可以举例求出ans不是偶数的情况。

a[i]和b[i]不可能同时大于0。()
答案：×
试题分析：举例即可找到反例。

4)若程序执行到第13行时,x总是小于y,那么第15行不会被执行。()
答案：×
试题分析：同样举例可以实现。

选择題
5)若m个x两两不同,且m个y两两不同,则输出的值为()
2n-2m B.2n+2 C.2n-2 D.2n
答案：A
试题分析：根据题意，m次循环中会有2m个位置的值会变化，ans=2n-2m。

6)若m个x两两不同,且m个y都相等,则输出的值为()
A.2n-2 B.2n C.2m D.2n-2m
答案：A
试题分析：如果m个x各不相同，循环里面的if都不会执行。对数组a，b赋值，只修改了2个位置。也可举例
3 3
3 3
2 3
1 3
答案是4。
CSP-J2019初赛个人错题整理
① 处应填( )
A.n%2 B.0 C.t D.1
答案：C
试题分析：(猜的话，变量t没有用过。)递归退出判断，参数t的赋值能发现是经常做取反操作。赋值和n没有必然联系，错误。选C。

② 处应填( )
A.x-step,y-step B.x,y-step
C.x-step,y D.x,y
答案：D
试题分析：四个方向，x，y是当前坐标。根据下面参数，参数分别是x,y;x,y+step;x+step,y;x+step,y+step。

③ 处应填( )
x-step,y-step B. x+step,y+step
x-step,y D. x,y-step
答案：B

④ 处应填( )
A.n-1,n%2 B.n,0 C.n,n%2 D.n-1,0
答案：B
试题分析：第一次调用recursive函数，n是矩阵规模，初始为n，t是取反次数，所以t初始为0或者1。

⑤ 处应填( )
A.i<<(n+1) B.1<<n C.n+1 D.1<<(n-1)
答案：B
试题分析：size是输出矩阵的边长，2^n,位运算是1<<n。

2、(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小达到排序。
例如有三对整数(3，4)、(2，4)、(3，3)，那么排序之后应该是(2，4)、(3，3)、(3，4)。
输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关关键字。
从小到大排序后输出。
数据范围 $1<n<10^7$ , $1<a[i],b[i]<10^4$

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[]存储第二关键字排序的结果，数组 res[]存储双关键字排序的结果。
试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i) 
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

1)①处应填（）
A. ++cnt[i]
B. ++cnt[b[i]]
C. ++cnt[a[i] * maxs + b[i]]
D. ++cnt[a[i]]
答案：B
解析：此处是对第二关键字进行计数排序。题目中给出提示，先按第二关键字排序。并且根据填空2对ord进行更改，可知此时是対第二关键字进行排序。

2)②处应填（）
A. ord[–cnt[a[i]]]=i
B. ord[–cnt[b[i]]]=a[i]
C. ord[–cnt[a[i]]]=b[i]
D. ord[–cnt[b[i]]]=i
答案：D
解析：cnt[b[i]]表示按第二关键字，第i个数排第几位。ord[i]表示第i小的数在原序列的位置

3)③处应填（）
A. ++cnt[b[i]]
B. ++cnt[a[i] * maxs + b[i]]
C. ++cnt[a[i]]
D. ++cnt[i]
答案：C
解析：对第一关键字计数，并做各关键词的数量统计工作，因此将a[i]对应的元素数量自增一。

4)④处应填（）
A. res[-cnt[a[ord[i]]]]=ord[i]
B. res[-cnt[b[ord[i]]]]=ord[i]
C. res[-cnt[b[i]]]=ord[i]
D. res[-cnt[a[i]]]=ord[i]
答案：A
解析：对应填空2 ord[i]记录了第二关键字第i小的数在原序列的位置。此时res[i]记录了第一关键字第i小的数在原序列的位置。

5)⑤处应填（）
A． a[i],b[i]
B. a[res[i]],b[res[i]]
C. a[ord[res[i]]],b[ord[res[i]]]
D. a[res[ord[i]]],b[res[ord[i]]]
答案：B
解析：此处是按顺序输出排序结果，由于之前已经按照第二、第一关键字进行计数排序，所以此时第i 个元素的原始下标为 res[i]。res[i]记录第i个数的原位置。