當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

CSP-J2021原题目及答案

發(fā)布時間：2023/12/8 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了 CSP-J2021原题目及答案小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

一、單項(xiàng)選擇題（共15題，共計30分）

1.以下不屬于面向?qū)ο蟪绦蛟O(shè)計語言的是（）。

A.C++
B.Python
C.Java
D.C

正確答案是：?D

2.以下獎項(xiàng)與計算機(jī)領(lǐng)域最相關(guān)的是（）。

A.奧斯卡獎
B.圖靈獎
C.諾貝爾獎
D.普利策獎

正確答案是：?B

3.目前主流的計算機(jī)儲存數(shù)據(jù)最終都是轉(zhuǎn)換成（）數(shù)據(jù)進(jìn)行存儲。

A.二進(jìn)制
B.十進(jìn)制
C.八進(jìn)制
D.十六進(jìn)制

正確答案是：?A

4.以比較作為基本運(yùn)算，在N個數(shù)中找出最大數(shù)，最壞情況下所需要的最少的比較次數(shù)為（）。

A.N2
B.N
C.N-1
D.N+1

正確答案是：?C

5.對于入棧順序?yàn)閍,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

正確答案是：?D

6.對于有n個頂點(diǎn)，m條邊的無向連通圖（m>n），需要刪掉（）條邊才能使其稱為一棵樹。

A.n-1
B.m-n
C.m-n-1
D.m-n+1

正確答案是：?D

7.二進(jìn)制數(shù)101.11對應(yīng)的十進(jìn)制數(shù)是（）。

A.6.5
B.5.5
C.5.75
D.5.25

正確答案是：?C

8.如果一棵二叉樹只有根結(jié)點(diǎn)，那么這棵二叉樹高度為1。請問高度為5的完全二叉樹有（）種不同的形態(tài)？

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

正確答案是：?A

9.表達(dá)式a*(b+c)*d的后綴表達(dá)式為（），其中“*”和“+”是運(yùn)算符。

A.**a+bcd
B.abc+*d*
C.abc+d**
D.*a*+bcd

正確答案是：?B

10.6個人，兩個人組一隊(duì)，總共組成三隊(duì)，不區(qū)分隊(duì)伍的編號，不同的組隊(duì)情況有（）。

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

正確答案是：?B

11.在數(shù)據(jù)壓縮編碼種的哈夫曼編碼方法，在本質(zhì)是一種（）的策略。

A.枚舉
B.貪心
C.遞歸
D.動態(tài)規(guī)劃

正確答案是：?B

12.由1，1，2，2，3這五個數(shù)字組成不同的三位數(shù)有（）種。

A.18
B.15
C.12
D.24

正確答案是：?A

13.考慮如下遞歸算法

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

則調(diào)用solve(7)得到的返回結(jié)果為（）。

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

正確答案是：?C

14.以a為起點(diǎn)，對右邊的無向圖進(jìn)行深度優(yōu)先遍歷，則b,c,d,e四個點(diǎn)中有可能作為最后一個遍歷到的點(diǎn)的個數(shù)為（）。

正確答案是：?B

15.有四個人要從A點(diǎn)坐一條船過河到B點(diǎn)，船一開始在A點(diǎn)。該船一次最多可坐兩個人。已知這四個人中每個人獨(dú)自坐船的過河時間分別為1，2，4，8，且兩個人坐船的過河時間為兩人獨(dú)自過河時間的較大者。則最短（）時間可以讓四個人過河到B點(diǎn)（包括從B點(diǎn)把船開回A點(diǎn)的時間）。

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

正確答案是：?B

二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍，共計40分）

PS:因?yàn)闊o法清晰打出√與×號，所以判斷題用選擇的方式呈現(xiàn)（和洛谷一樣）

（一）

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時，程序不會發(fā)生下標(biāo)越界。這句話描述是否正確？

A.正確
B.錯誤

正確答案是：?B

17.輸入的a[i]必須全為正整數(shù)，否則程序?qū)⑾萑胨姥h(huán)。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

18.當(dāng)輸入為“5 2 11 9 16 10”時，輸出為“3 4 3 17 5”。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

19.當(dāng)輸入為“1 511998”時，輸出為“18”。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?A

20.將源代碼中g(shù)函數(shù)的定義（13-16行）移到main函數(shù)的后面，程序可以正常編譯運(yùn)行。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

21.當(dāng)輸入為“2 -65536 2147483647”時，輸出為（）

A."65532 33"
B."65552 32"
C."65535 34"? ??
D."65554 33"

正確答案是：?B

（二）

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.輸出的第二行一定是由小寫字母、大寫字母、數(shù)字和“+”、“/”、“=”構(gòu)成的字符串。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

23.可能存在輸入不同，但輸出的第二行相同的情形。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?A

24.輸出的第一行為“-1”。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?A

25.設(shè)輸入字符串長度為n，decode函數(shù)的時間復(fù)雜度為（）

正確答案是：?B

26.當(dāng)輸入為“Y3Nx”時，輸出的第二行為（）

A.“csp”
B.“csq”
C.“CSP”
D.“Csp”

正確答案是：?B

27.當(dāng)輸入為“Y2NmIDIwMjE=”時，輸出的第二行為（）

A.“ccf2021”
B.“ccf2022”
C.“ccf 2021”
D.“ccf 2022”

正確答案是：?C

（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行刪去不會影響輸出的結(jié)果。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?A

29.第24行的“f[i] / c[i * k]”可能存在無法整除而向下取整的情況。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

30.在執(zhí)行完init（）后，f數(shù)組不是單調(diào)遞增的，但g數(shù)組是單調(diào)遞增的。這句話的描述是否正確？

A.正確
B.錯誤

正確答案是：?B

31.init函數(shù)的時間復(fù)雜度為（）。

A.
??
B.
C.
?
D.

正確答案是：?A

32.在執(zhí)行完init（）后，f[1]，f[2]，f[3] …… f[100]中有（）個等于2。

A.
23
B.
24
C.
25
D.
26

正確答案是：?C

33.當(dāng)輸入為“1000”時，輸出為（）

A.
”15 1340”
B.
”15 2340”
C.
”16 2340”
D.
”16 1340”

正確答案是：?C

三、完善程序

（一）

（Josephus 問題）有n個人圍成一個圈，一次標(biāo)號0至n-1，從0號開始，依次0，1，0，1，. . . . 交替報數(shù)，報道1 的人會離開，直至圈中只剩下一個人，求最后剩下人的編號。

試補(bǔ)全模擬程序

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

正確答案是：?D

35.②處填（）

A.i%2==0
B.i%2==1
C.p
D.!p

正確答案是：?C

36.③處填（）

A.i++
B. i=(i+1)%n
C.c++
D.p^=1

正確答案是：?C

37.④處填（）

A.i++
B.i=(i+1)%n
C. c++
D.p^=1

正確答案是：?D

38.⑤處填（）

A.i++
B.i=(i+1)%n
C.c++
D.p^=1

正確答案是：?B

（二）

（矩形計數(shù)）平面上有n個關(guān)鍵點(diǎn)，求有多少個四條邊都和x軸或者y軸平行的矩形，滿足四個頂點(diǎn)都是關(guān)鍵點(diǎn)。給出的關(guān)鍵點(diǎn)可能有重復(fù)，但完全重合的矩形只計一次。

試補(bǔ)全枚舉算法。

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.①處應(yīng)填（）

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)

正確答案是：?B

40.【單選】3 分

②處應(yīng)填（）

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])

正確答案是：?D

41.【單選】3 分

③處應(yīng)填（）

A.b – (b – a) / 2 + 1
B.(a + b + 1) >> 1
C.(a + b) >> 1
D.a + (b – a + 1) / 2

正確答案是：?C

42.④處應(yīng)填（）

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

正確答案是：?B

43.⑤處應(yīng)填（）

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

正確答案是：?D

總結(jié)

以上是生活随笔為你收集整理的CSP-J2021原题目及答案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Ping原理Linux,ping实现原理
下一篇： CSS学习笔记——精灵图(sprite)