当前位置:首页题目 > 正文

2021年CSP-J组入门级初赛真题

作者:野牛程序员:2023-05-23 11:26:29题目阅读 9593

2021年CSP-J组入门级初赛真题

一、单项选择题(共15题,共计30分)

1.以下不属于面向对象程序设计语言的是(        )。

A.C++

B.Python

C.Java

D.C

----------------------------------------------------------------------------------------------------------------------

2.以下奖项与计算机领域最相关的是(        )。

A.奥斯卡奖

B.图灵奖

C.诺贝尔奖

D.普利策奖

---------------------------------------------------------------------------------------------------------------------------

3.目前主流的计算机储存数据最终都是转换成(        )数据进行存储。

A.二进制

B.十进制

C.八进制

D.十六进制

-----------------------------------------------------------------------------------------------------------------

4.以比较作为基本运算,在N个数中找出最大数,最坏情况下所需要的最少的比较次数为(        )。

A.N2

B.N

C.N-1

D.N+1

---------------------------------------------------------------------------------------------------------------

5.对于入栈顺序为a,b,c,d,e的序列,下列(        )不是合法的出栈序列。

A.a,b,c,d,e

B.e,d,c,b,a

C.b,a,c,d,e

D.c,d,a,e,b

-----------------------------------------------------------------------------------------------------

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

A.n-1

B.m-n

C.m-n-1

D.m-n+1

---------------------------------------------------------------------------------------------------------

7.二进制数101.11对应的十进制数是(         )。

A.6.5

B.5.5

C.5.75

D.5.25

-----------------------------------------------------------------------------------------------------------

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

A.16
B.15
C.17
D.32

---------------------------------------------------------------------------------------------------------------------------------

9.表达式a*(b+c)*d的后缀表达式为(        ),其中“*”和“+”是运算符。

A.**a+bcd

B.abc+*d*

C.abc+d**

D.*a*+bcd

---------------------------------------------------------------------------------------------------------

10.6个人,两个人组一队,总共组成三队,不区分队伍的编号,不同的组队情况有(        )。

A.10
B.15
C.30
D.20

----------------------------------------------------------------------------------------------------------

11.在数据压缩编码种的哈夫曼编码方法,在本质是一种(        )的策略。

A.枚举

B.贪心

C.递归

D.动态规划

----------------------------------------------------------------------------------------------------------

12.由1,1,2,2,3这五个数字组成不同的三位数有(        )种。

A.18

B.15

C.12

D.24

-----------------------------------------------------------------------------------------------------------

13.考虑如下递归算法

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

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

A.105
B.840
C.210
D.420

--------------------------------------------------------------------------------------------------------

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

A.1

B.2

C.3

D.4

-----------------------------------------------------------------------------------------------------------

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

A.14

B.15

C.16

D.17

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

二、阅读程序(程序输入不超过数组或字符串定义的范围,共计40分)

(一)

01 #include <stdio.h>
02 
03 int n;
04 int a[1000];
05 
06 int f(int x)
07 {
08         int ret = 0;
09         for(; x; x &= x - 1) ret ++;
10         return ret;
11 }
12 
13 int g(int x)
14 {
15         return x & - x;
16 }
17 
18 int main()
19 {
20         scanf("%d", &n);
21         for (int i = 0; i < n; i++) scanf("%d", &a[i]);
22         for (int i = 0; i < n; i++)
23             printf("%d ", f(a[i]) + g(a[i]));
24         printf("\\n");
25         return 0;
26 }

16.输入的n等于1001时,程序不会发生下标越界。这句话描述是否正确?

A.正确

B.错误

------------------------------------------------------------------------------------------------------

17.输入的a[i]必须全为正整数,否则程序将陷入死循环。这句话的描述是否正确?(        

A.正确

B.错误

----------------------------------------------------------------------------------------------------

18.当输入为“5 2 11 9 16 10”时,输出为“3 4 3 17 5”。这句话的描述是否正确?(        

A.正确

B.错误

----------------------------------------------------------------------------------------------------

19.当输入为“1 511998”时,输出为“18”。这句话的描述是否正确?(        

A.正确

B.错误

-------------------------------------------------------------------------------------------------

20.将源代码中g函数的定义(13-16行)移到main函数的后面,程序可以正常编译运行。这句话的描述是否正确?(        

A.正确

B.错误

-------------------------------------------------------------------------------------------------------

21.当输入为“2 -65536 2147483647”时,输出为(        

A."65532 33"

B."65552 32"

C."65535 34"    

D."65554 33"

------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------

(二)

01 #include <cstdio.h>
02 #include <string.h>
03 
04 char base[64];
05 char table[256];
06 char str[256];
07 char ans[256];
08 
09 void init()
10 {
11         for (int i = 0; i < 26; i++) base[i] = 'A' + i;
12        for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
13        for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
14        base[62] = '+', base[63] = '/';
15    
16        for (int i = 0; i < 256; i++) table[i] = 0xff;
17        for (int i = 0; i < 64; i++) table[base[i]] = i;
18        table['='] = 0;
19 }
20
21 void decode(char *str)
22 {
23        char *ret = ans;
24        int i, len = strlen(str);
25        for (i = 0; i < len; i += 4){
26            (*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
27            if(str[i + 2] != '=')
28                (*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
29            if(str[i + 3] != '=')
30                (*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
31         }
32 }
33
34 int main()
35 {
36        init();
37        printf("%d\\n", (int)table[0]);
38    
39        scanf("%s", str);
40        decode(str);
41        print("%s\\n", ans);
42        return 0;
43 }

22.输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。这句话的描述是否正确?(     

A.正确

B.错误

----------------------------------------------------------------------------------------------------

23.可能存在输入不同,但输出的第二行相同的情形。这句话的描述是否正确?(        

A.正确

B.错误

------------------------------------------------------------------------------------------


24.输出的第一行为“-1”。这句话的描述是否正确?(        


A.正确

B.错误



---------------------------------------------------------------------------------------------------------------------------------


25.设输入字符串长度为n,decode函数的时间复杂度为(        

————————————————

26.当输入为“Y3Nx”时,输出的第二行为(        


A.“csp”

B.“csq”

C.“CSP”

D.“Csp”



---------------------------------------------------------------------------------------------------------------------------------


27.当输入为“Y2NmIDIwMjE=”时,输出的第二行为(        


A.“ccf2021”

B.“ccf2022”

C.“ccf 2021”

D.“ccf 2022”



---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

(3)

01 #include<stdio.h>
02
03 #define n 100000
04 #define N n + 1
05
06 int m;
07 int a[N],b[N],c[N],d[N];
08 int f[N],g[N];
09
10 void init()
11 {
12        f[1] = g[1] = 1;
13        for(int i = 2;i <= n;i++){
14            if(!a[i]) {
15                b[m++] = i;
16                c[i] = 1,f[i] = 2;
17                d[i] = 1,g[i] = i + 1;
18            }
19            for(int j = 0;j < m && b[j] * i <= n;j++){
20                int k = b[j];
21                a[i * k] = 1;
22                if(i * k == 0){
23                    c[i * k] = c[i] + 1;
24                    f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
25                    d[i * k] = d[i];
26                    g[i * k] = g[i] * k + d[i];
27                    break;
28                    }
29                    else{
30                        c[i * k] = 1;
31                        f[i * k] = 2 * f[i];
32                        d[i * k] = g[i];
33                        g[i * k] = g[i] * (k + 1);
34                    }
35                }
36            }
37 }
38
39 int main()
40 {
41        init();
42        
43        int x;
44        scanf("%d",&x);
45        printf("%d %d\\n",f[x],g[x]);
46        return 0;
47 }

28.若输入不为“1”,把第12行删去不会影响输出的结果。这句话的描述是否正确?(        


A.正确

B.错误



---------------------------------------------------------------------------------------------------------------------------------


29.第24行的“f[i] / c[i * k]”可能存在无法整除而向下取整的情况。这句话的描述是否正确?(        


A.正确

B.错误



---------------------------------------------------------------------------------------------------------------------------------


30.在执行完init()后,f数组不是单调递增的,但g数组是单调递增的。这句话的描述是否正确?(        


A.正确

B.错误



---------------------------------------------------------------------------------------------------------------------------------


31.init函数的时间复杂度为(        )。

————————————————

32.在执行完init( )后,f[1],f[2],f[3] …… f[100]中有(        )个等于2。


A.23


B.24


C.25


D.26


---------------------------------------------------------------------------------------------------------------------------------


33.当输入为“1000”时,输出为(        


A.”15 1340”


B.”15 2340”


C.”16 2340”


D.”16 1340”


---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------


三、完善程序

(一)

 有n个人围成一个圈,一次标号0至n-1,从0号开始,依次0,1,0,1,. . . . 交替报数,报道1 的人会离开,直至圈中只剩下一个人,求最后剩下人的编号。

试补全模拟程序

01 #include<stdio.h>
02
03 const int MAXN=1000000;
04 int F[MAXN];
05 
06 int main(){
07    int n;
08    scanf("%d",&n);
09    int  i=0,p=0,c=0;
10    while( ① ){
11        if(F[i]==0){
12            if( ② ){
13                F[i]=1;
14                ③;
15            }
16            ④ ;
17        }
18        ⑤ ;
19    }
20    int ans=-1;
21    for(int i=0;i<n;i++)
22        if(F[i]==0)
23            ans=i;
24    printf("%d\\n",ans);
25    return 0;
26 }

34.①处填(        


A.i<n

B. c<n

C. i<n-1

D.c<n-1



---------------------------------------------------------------------------------------------------------------------------------


35.②处填(        

A.i%2==0

B.i%2==1

C.p

D.!p



---------------------------------------------------------------------------------------------------------------------------------


36.③处填(        

A.i++

B. i=(i+1)%n

C.c++

D.p^=1



---------------------------------------------------------------------------------------------------------------------------------


37.④处填(        


A.i++

B.i=(i+1)%n

C. c++

D.p^=1



---------------------------------------------------------------------------------------------------------------------------------


38.⑤处填(        


A.i++

B.i=(i+1)%n

C.c++

D.p^=1



---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------

(二)

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

试补全枚举算法。

01 #include <stdio.h>
02
03 struct point{
04       int x, y, id;
05 };
06
07 int equals(struct point a,struct point b){
08       return a.x == b.x && a.y == b.y;
09 }
10
11 int cmp(struct point a, struct point b){
12       return ①; 
13 }
14
15 void sort(struct point A[], int n){
16       for(int i = 0; i < n; i++)
17           for(int j = 1; j < n; j++)
18               if(cmp(A[j], A[j - 1])){
19                   struct point t=A[j];
20                   A[j] = A[j - 1];
21                   A[j - 1] = t;
22               }
23 }
24
25 int unique(struct point A[],int n){
25       int t=0;
25       for(int i = 0; i < n; i++)
25           if(②)
25               A[t++] = A[i];
30       return t;
31 }
32
32 int binary_search(struct point A[], int n, int x, int y){
32       struct point p;
32       p.x = x;
33       p.y = y;
32       p.id = n;
32       int a = 0, b = n - 1;
32       while(a < b){
40           int mid=③;
41           if(④)
42               a = mid + 1;
43           else 
44               b = mid; 
45       }
46       return equals(A[a], p);
47 }
48
49 #define MAXN 1000
50 struct point A[MAXN];
51 
52 int main(){
53     int n;
54    scanf("%d",&n);
55    for(int i = 0; i < n; i++){
56        scanf("%d %d", &A[i].x, &A[i].y);
57        A[i].id = i;
58    }
59    sort(A,n);
60    n = unique(A, n);
61    int ans = 0;
62    for(int i = 0; i < n; i++)
63        for(int j = 0; j < n; j++)
64            if(⑤&& binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
65                ans++;
66            }
67    printf("%d\\n", ans);
68    return 0;
69 }

39.①处应填(        


A.a.x != b.x ? a.x < b.x : a.id < b.id

B.a.x != b.x ? a.x < b.x : a.y< b.y

C.equals(a,b) ? a.id<b.id:a.x<b.x

D.equals(a,b) ? a.id<b.id: (a.x != b.x ? a.x < b.x : a.y< b.y)

 


---------------------------------------------------------------------------------------------------------------------------------


40.【 单选 】3 分


②处应填(        

A. i == 0 || cmp(A[i], A[i - 1])

B. t == 0 || equals(A[i], A[t - 1])

C.i == 0 || !cmp(A[i], A[i - 1])

D. t == 0 || !equals(A[i], A[t -1])

 


---------------------------------------------------------------------------------------------------------------------------------


41.【 单选 】3 分


③处应填(        


A.b – (b – a) / 2 + 1

B.(a + b + 1) >> 1

C.(a + b) >> 1

D.a + (b – a + 1) / 2

 


---------------------------------------------------------------------------------------------------------------------------------


42.④处应填(        


A.!cmp(A[mid], p)

B.cmp(A[mid], p)

C.cmp(p, A[mid])

D.!cmp(p, A[mid])

 


---------------------------------------------------------------------------------------------------------------------------------


43.⑤处应填(        

A.A[i].x == A[j].x

B.A[i].id < A[j].id

C.A[i].x == A[j].x && A[i].id < A[j].id

D.A[i].x<A[j].x && A[i].y < A[j].y

 


---------------------------------------------------------------------------------------------------------------------------------


野牛程序员教少儿编程与信息学奥赛-微信|电话:15892516892
野牛程序员教少儿编程与信息学竞赛-微信|电话:15892516892
相关推荐

最新推荐

热门点击