Dotcpp  >  试卷列表  >  CSP-J1入门级初赛试卷[2021]

CSP-J1入门级初赛试卷[2021]

自由练习

模拟考试

我的成绩

第1题

以下不属于面向对象程序设计语言的是（ ）。

共 2 分　

第2题

以下奖项与计算机领域最相关的是（ ）。

共 2 分　

第3题

目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。

共 2 分　

第4题

以比较作为基本运算，在N个数中找出最大数， 最坏情况下所需要的最少的比较次数为（ ）。

共 2 分　

第5题

对于入栈顺序为a,b,c,d,e的序列，下列（ ）不是合法的出栈序列。

共 2 分　

第6题

对于有n个顶点m条边的无向连通图(m>n)，需要删掉（ ）条边才能使其成为一棵树。

共 2 分　

第7题

二进制数101.11对应的十进制数是（ ）。

共 2 分　

第8题

如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（ ）种不同的形态?

共 2 分　

第9题

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

共 2 分　

第10题

6个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ）。

共 2 分　

第11题

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

共 2 分　

第12题

由1,1,2,2,3这五个数字组成不同的三位数有（ ）种。

共 2 分　

第13题

考虑如下递归算法：

1
2
3
4
solve(n)
    if n<=1  return 1
    else if n>=5   return  n*solve(n-2)
    else return n*solve(n-1)

则调用solve(7)得到的返回结果为（ ）。



共 2 分　

第14题

以a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e四个点中有可能作为最后一个遍历到的点的个数为（ ）。

CSP-J1入门级初赛试卷[2021]

共 2 分　

第15题

有四个人要从A点坐一条船过河到B点，船开始在A点，该船一次最多可坐两个人。己知这四个人中每个人独自坐船的过河时间分别为1,2,4,8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到B点（包括从B点把船开回A点的时间）。

共 2 分　

第16题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

输入的n等于1001时，程序不会发生下标越界。

共 1.5 分　

第17题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

输入的a[i]必须全为正整数，否则程序将陷入死循环。

共 1.5 分　

第18题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

当输入“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。

共 1.5 分　

第19题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

当输入为“1 511998”时，输出为“18”。

共 1.5 分　

第20题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

将源代码中g函数的定义（13-16行）移到main函数的后面，程序可以正常编译运行。

共 1.5 分　

第21题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}
int g(int x)
{
    return x & -x;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        printf("%d",f(a[i])+g(a[i]));
    printf("\n");
    return 0;
}

当输入为“2 -65536 2147483647”时，输出为（ ）。

共 3 分　

第22题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。

共 1.5 分　

第23题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

可能存在输入不同，但输出的第二行相同的情形。

共 1.5 分　

第24题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

输出的第一行为“-1”。

共 1.5 分　

第25题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

设输入字符串长度为n，decode函数的时间复杂度为（ ）。

共 3 分　

第26题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

当输入为“Y3Nx”时，输出的第二行为（ ）。

共 3 分　

第27题

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
#include <stdio.h>
#include <string.h>
char base[64];
char table[256];
char str[256];
char ans[256];
void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';
    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}
void decode(char *str)
{
    char *ret = ans;
    int i, len = strlen(str);
    for (i = 0; i < len; i += 4) {
        (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
    }
}
int main()
{
    init();
    printf("%d\n",(int)table[0]);
    scanf("%s",str);
    decode(str);
    printf("%s\n",ans)
    return 0;
}

当输入为“Y2NmIDIwMjE=”时，输出的第二行为（ ）。

共 3.5 分　

第28题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，若输入不为"1"，把第12行删去不会影响输出的结果。

共 1.5 分　

第29题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，第24行的"f[i]/c[i*k]"可能存在无法整除而向下取整的情况。

共 2 分　

第30题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，在执行完init()后，f数组不是单调递增的，但g数组是单调递增的。

共 2 分　

第31题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，init函数的时间复杂度为（ ）。

共 3 分　

第32题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，在执行完init()后，f[1], f[2], f[3] ...... f[100]中有（ ）个等于2。

共 3 分　

第33题

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
#include <stdio.h>
#define n 100000
#define N n + 1
int m;
int a[N], b[N], c[N], d[N];
int f[n], g[N];
void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}
int main()
{
    init();
    int x;
    scanf("%d", &x);
    printf("%d %d\n", f[x], g[x]);
    return 0;
}

假设输入的x是不超过1000的自然数，当输入"1000"时，输出为（ ）。

共 4 分　

第34题

（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 1000000;
int F[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    int i =0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
}

①处应填（ ）

共 3 分　

第35题

（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 1000000;
int F[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    int i =0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
}

②处应填（ ）

共 3 分　

第36题

（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 1000000;
int F[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    int i =0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
}

③处应填（ ）

共 3 分　

第37题

（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 1000000;
int F[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    int i =0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
}

④处应填（ ）

共 3 分　

第38题

（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 1000000;
int F[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    int i =0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
}

⑤处应填（ ）

共 3 分　

第39题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

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
#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

①处应填（ ）

共 3 分　

第40题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

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
#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

②处应填（ ）

共 3 分　

第41题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

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
#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

③处应填（ ）

共 3 分　

第42题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

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
#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

④处应填（ ）

共 3 分　

第43题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

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
#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

⑤处应填（ ）

共 3 分　

试卷信息

题量: 43 道
总分: 100 分 
一、选择题（1-15 共 15 题）；
二、阅读程序（16-33 共 18 题）；
三、完善程序（34-43 共 10 题）。
第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题