CSPJ2022初賽試題及參考答案-1

2022CCF非專業(yè)級別軟件能力認(rèn)證第一輪

（CSP-J1）入門級C++語言試題

認(rèn)證時(shí)間：2022年9月18日09:30~11:30

考生注意事項(xiàng)：

試題紙共有12頁，答題紙共有1頁，滿分100分。請?jiān)诖痤}紙上作答，寫在試題紙上的

一律無效。

不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。

一、單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）

1.以下哪種功能沒有涉及C++語言的面向?qū)ο筇匦灾С郑?/p>

（）

。

A.C++中調(diào)用printf函數(shù)

B.C++中調(diào)用用戶定義的類成員函數(shù)

C.C++中構(gòu)造一個(gè)class或struct

D.C++中構(gòu)造來源于同一基類的多個(gè)派生類

2.有6個(gè)元素，按照6、5、4、3、2、1的順序進(jìn)入棧S，請問下列哪個(gè)出棧序列是非法的

（

）。

A.543612

B.453126

C.346521

D.234156

3.運(yùn)行以下代碼片段的行為是（

intx=101;

inty=201;

int*p=&x;

int*q=&y;

p=q;

A.將x的值賦為201

B.將y的值賦為101

CCFCSP-J2022第一輪C++語言試題

第1頁，共12頁

）。

C.將q指向x的地址

D.將p指向y的地址

4.鏈表和數(shù)組的區(qū)別包括（

）。

A.數(shù)組不能排序，鏈表可以

B.鏈表比數(shù)組能存儲更多的信息

C.數(shù)組大小固定，鏈表大小可動態(tài)調(diào)整

D.以上均正確

5.對假設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空。存在e1~e6六個(gè)互不相同的數(shù)據(jù)，每個(gè)數(shù)據(jù)按照

進(jìn)棧S、出棧S、進(jìn)隊(duì)列Q、出隊(duì)列Q的順序操作，不同數(shù)據(jù)間的操作可能會交錯(cuò)。已知

棧S中依次有數(shù)據(jù)e1、e2、e3、e4、e5和e6進(jìn)棧，隊(duì)列Q依次有數(shù)據(jù)e2、e4、e3、

e6、e5和e1出隊(duì)列。則棧S的容量至少是（

A.2

B.3

C.4

D.6

）個(gè)數(shù)據(jù)。

6.對表達(dá)式a+(b-c)*d的前綴表達(dá)式為（

A.*+a-bcd

B.+a*-bcd

C.abc-d*+

D.abc-+d

），其中+、-、*是運(yùn)算符。

7.假設(shè)字母表{a,b,c,d,e}在字符串出現(xiàn)的頻率分別為10%,15%,30%,16%,

29%。若使用哈夫曼編碼方式對字母進(jìn)行不定長的二進(jìn)制編碼，字母d的編碼長度為

（

）位。

A.1

B.2

CCFCSP-J2022第一輪C++語言試題

第2頁，共12頁

C.2或3

D.3

8.一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹用數(shù)組進(jìn)行存儲與表示，已知根結(jié)點(diǎn)存儲在數(shù)組的第1個(gè)位

置。若存儲在數(shù)組第9個(gè)位置的結(jié)點(diǎn)存在兄弟結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)，則它的兄弟結(jié)點(diǎn)和右子

結(jié)點(diǎn)的位置分別是（

A.8、18

B.10、18

C.8、19

D.10、19

）。

9.考慮由N個(gè)頂點(diǎn)構(gòu)成的有向連通圖，采用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)表示時(shí)，該矩陣中至少存在

（

）個(gè)非零元素。

A.N-1

B.N

C.N+1

D.N2

10.以下對數(shù)據(jù)結(jié)構(gòu)的表述不恰當(dāng)?shù)囊豁?xiàng)為：（

）。

A.圖的深度優(yōu)先遍歷算法常使用的數(shù)據(jù)結(jié)構(gòu)為棧。

B.棧的訪問原則為后進(jìn)先出，隊(duì)列的訪問原則是先進(jìn)先出。

C.隊(duì)列常常被用于廣度優(yōu)先搜索算法。

D.棧與隊(duì)列存在本質(zhì)不同，無法用棧實(shí)現(xiàn)隊(duì)列。

11.以下哪組操作能完成在雙向循環(huán)鏈表結(jié)點(diǎn)p之后插入結(jié)點(diǎn)s的效果（其中，next域?yàn)榻Y(jié)

點(diǎn)的直接后繼，prev域?yàn)榻Y(jié)點(diǎn)的直接前驅(qū)）：（

A.p->next->prev=s;

B.p->next->prev=s;

C.s->prev=p;

s->prev=p;

p->next=s;

）。

s->next=p->next;

s->next=p->next;

p->next->prev=s;

p->next=s;

s->prev=p;

p->next=s;

s->next=p->next;

CCFCSP-J2022第一輪C++語言試題

第3頁，共12頁

D.s->next=p->next;

p->next->prev=s;

s->prev=p;

p->next=s;

12.以下排序算法的常見實(shí)現(xiàn)中，哪個(gè)選項(xiàng)的說法是錯(cuò)誤的：（

A.冒泡排序算法是穩(wěn)定的

B.簡單選擇排序是穩(wěn)定的

C.簡單插入排序是穩(wěn)定的

D.歸并排序算法是穩(wěn)定的

）。

13.八進(jìn)制數(shù)32.1對應(yīng)的十進(jìn)制數(shù)是（

A.24.125

B.24.250

C.26.125

D.26.250

）。

14.一個(gè)字符串中任意個(gè)連續(xù)的字符組成的子序列稱為該字符串的子串，則字符串a(chǎn)bcab有

（

）個(gè)內(nèi)容互不相同的子串。

A.12

B.13

C.14

D.15

15.以下對遞歸方法的描述中，正確的是：（

）

A.遞歸是允許使用多組參數(shù)調(diào)用函數(shù)的編程技術(shù)

B.遞歸是通過調(diào)用自身來求解問題的編程技術(shù)

C.遞歸是面向?qū)ο蠛蛿?shù)據(jù)而不是功能和邏輯的編程語言模型

D.遞歸是將用某種高級語言轉(zhuǎn)換為機(jī)器代碼的編程技術(shù)

二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填

，錯(cuò)誤填×；除特

殊說明外，判斷題1.5分，選擇題3分，共計(jì)40分）

CCFCSP-J2022第一輪C++語言試題

第4頁，共12頁

(1)

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

#include<iostream>

usingnamespacestd;

intmain()

{

unsignedshortx,y;

cin>>x>>y;

x=(x|x<<2)&0x33;

x=(x|x<<1)&0x55;

y=(y|y<<2)&0x33;

y=(y|y<<1)&0x55;

unsignedshortz=x|y<<1;

cout<<z<<endl;

return0;

}

假設(shè)輸入的x、y均是不超過15的自然數(shù)，完成下面的判斷題和單選題：

判斷題

16.刪去第7行與第13行的unsigned，程序行為不變。（

）

）

17.將第7行與第13行的short均改為char，程序行為不變。（

18.程序總是輸出一個(gè)整數(shù)"0"。（

）

）

）

19.當(dāng)輸入為"22"時(shí)，輸出為"10"。（

20.當(dāng)輸入為"22"時(shí)，輸出為"59"。（

單選題

21.當(dāng)輸入為"138"時(shí)，輸出為（

A."0"

B."209"

（2）

01

02

03

04

05

06

07

）。

C.

"197"

D.

"226"

#include<algorithm>

#include<iostream>

#include<limits>

usingnamespacestd;

constintMAXN=105;

CCFCSP-J2022第一輪C++語言試題

第5頁，共12頁

08

09

10

11

12

13

14

15

16

18

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

constintMAXK=105;

inth[MAXN][MAXK];

intf(intn,intm)

{

if(m==1)returnn;

if(n==0)return0;

for(inti=1;i<=n;i++)

returnret;

}

intg(intn,intm)

{

for(inti=1;i<=n;i++)

h[i][1]=i;

for(intj=1;j<=m;j++)

h[0][j]=0;

for(inti=1;i<=n;i++){

for(intj=2;j<=m;j++){

h[i][j]=numeric_limits<int>::max();

for(intk=1;k<=i;k++)

h[i][j]=min(

h[i][j],

max(h[i-k][j],h[k-1][j-1])+1);

}

}

returnh[n][m];

}

intmain()

{

intn,m;

cin>>n>>m;

cout<<f(n,m)<<endl<<g(n,m)<<endl;

return0;

}

假設(shè)輸入的n、m均是不超過100的正整數(shù)，完成下面的判斷題和單選題：

CCFCSP-J2022第一輪C++語言試題

第6頁，共12頁

判斷題

22.當(dāng)輸入為"73"時(shí)，第19行用來取最小值的min函數(shù)執(zhí)行了449次。（

23.輸出的兩行整數(shù)總是相同的。（

）

）

）

24.當(dāng)m為1時(shí)，輸出的第一行總為n。（

單選題

25.算法g(n,m)最為準(zhǔn)確的時(shí)間復(fù)雜度分析結(jié)果為（

A.

????????/2????

(3

)

）。

D.

????????????

(2)

B.

????????????

()

C.

????????????

(2)

26.當(dāng)輸入為"202"時(shí)，輸出的第一行為（

A.

"4"

）。

"6"

B.

"5"

C.

D.

"20"

27.（4分）當(dāng)輸入為"100100"時(shí)，輸出的第一行為（

A.

"6"

）。

D.

"9"

B.

"7"

C.

"8"

（3）

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

#include<iostream>

usingnamespacestd;

intn,k;

intsolve1()

{

intl=0,r=n;

while(l<=r){

intmid=(l+r)/2;

if(mid*mid<=n)l=mid+1;

elser=mid-1;

}

returnl-1;

}

doublesolve2(doublex)

{

if(x==0)returnx;

for(inti=0;i<k;i++)

x=(x+n/x)/2;

returnx;

}

intmain()

CCFCSP-J2022第一輪C++語言試題

第7頁，共12頁

27{

28

29

30

31

32}

cin>>n>>k;

doubleans=solve2(solve1());

cout<<ans<<''<<(ans*ans==n)<<endl;

return0;

假設(shè)int為32位有符號整數(shù)類型，輸入的n是不超過47000的自然數(shù)、k是不超過int

表示范圍的自然數(shù)，完成下面的判斷題和單選題：

判斷題

28.該算法最準(zhǔn)確的時(shí)間復(fù)雜度分析結(jié)果為????log????????。（）

(

+)

29.當(dāng)輸入為"98011"時(shí)，輸出的第一個(gè)數(shù)為"99"。（

）

）

30.對于任意輸入的n，隨著所輸入k的增大，輸出的第二個(gè)數(shù)會變成"1"。（

31.該程序有存在缺陷。當(dāng)輸入的n過大時(shí)，第12行的乘法有可能溢出，因此應(yīng)當(dāng)將

mid強(qiáng)制轉(zhuǎn)換為64位整數(shù)再計(jì)算。（）

單選題

32.當(dāng)輸入為"21"時(shí)，輸出的第一個(gè)數(shù)最接近（

A.

1

B.

1.414

C.

1.5

）。

D.

2

33.當(dāng)輸入為"310"時(shí)，輸出的第一個(gè)數(shù)最接近（

A.

1.7

）。

D.

2

B.

1.732

C.

1.75

34.當(dāng)輸入為"25611"時(shí)，輸出的第一個(gè)數(shù)（

A.

C.

等于16

接近但大于16

B.

D.

接近但小于16

前三種情況都有可能

）。

三、完善程序（單選題，每小題3分，共計(jì)30分）

（1）（枚舉因數(shù)）從小到大打印正整數(shù)n的所有正因數(shù)。

試補(bǔ)全枚舉程序。

01#include<bits/stdc++.h>

02usingnamespacestd;

03

04intmain(){

05

intn;

06

cin>>n;

CCFCSP-J2022第一輪C++語言試題

第8頁，共12頁

07

08

09

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27}

vector<int>fac;

fac.reserve((int)ceil(sqrt(n)));

inti;

for(i=1;i*i<n;++i){

if(①){

fac.push_back(i);

}

}

for(intk=0;k<fac.size();++k){

cout<<②<<"";

}

if(③){

cout<<④<<"";

}

for(intk=fac.size()-1;k>=0;--k){

cout<<⑤<<"";

}

35.①處應(yīng)填（）

A.

C.

n%i==0

n%(i-1)==0

B.

D.

n%i==1

n%(i-1)==1

36.②處應(yīng)填（

A.

C.

）

B.

D.

fac[k]

n/(fac[k]-1)

n/fac[k]

fac[k]-1

37.③處應(yīng)填（

A.

C.

）

B.

D.

(i-1)*i==n

i*(i-1)==n

(i-1)*(i-1)==n

i*i==n

38.④處應(yīng)填（

A.

C.

n-i

i-1

）

B.

D.

n-i+1

I

39.⑤處應(yīng)填（

A.

C.

）

B.

D.

fac[k]

n/(fac[k]-1)

n/fac[k]

fac[k]-1

（2）（洪水填充）現(xiàn)有用字符標(biāo)記像素顏色的8x8圖像。顏色填充的操作描述如下：給

定起始像素的位置和待填充的顏色，將起始像素和所有可達(dá)的像素（可達(dá)的定義：經(jīng)過

CCFCSP-J2022第一輪C++語言試題

第9頁，共12頁

一次或多次的向上、下、左、右四個(gè)方向移動所能到達(dá)且終點(diǎn)和路徑上所有像素的顏色

都與起始像素顏色相同）

，替換為給定的顏色。

試補(bǔ)全程序。

01

02

03

04

05

06

07

08

09

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

#include<bits/stdc++.h>

usingnamespacestd;

constintROWS=8;

constintCOLS=8;

structPoint{

intr,c;

Point(intr,intc):r(r),c(c){}

};

boolis_valid(charimage[ROWS][COLS],Pointpt,

intprev_color,intnew_color){

intr=pt.r;

intc=pt.c;

return(0<=r&&r<ROWS&&0<=c&&c<COLS&&

①&&image[r][c]!=new_color);

}

voidflood_fill(charimage[ROWS][COLS],Pointcur,intnew_color){

queue<Point>queue;

queue.push(cur);

intprev_color=image[cur.r][cur.c];

②;

while(!queue.empty()){

Pointpt=queue.front();

queue.pop();

Pointpoints[4]={③,Point(pt.r-1,pt.c),

Point(pt.r,pt.c+1),Point(pt.r,pt.c-1)};

for(autop:points){

if(is_valid(image,p,prev_color,new_color)){

④;

⑤;

}

}

}

CCFCSP-J2022第一輪C++語言試題

第10頁，共12頁

40}

41

42intmain(){

43

charimage[ROWS][COLS]={{'g','g','g','g','g','g','g','g'},

44

{'g','g','g','g','g','g','r','r'},

45

{'g','r','r','g','g','r','g','g'},

46

{'g','b','b','b','b','r','g','r'},

47

{'g','g','g','b','b','r','g','r'},

48

{'g','g','g','b','b','b','b','r'},

49

{'g','g','g','g','g','b','g','g'},

50

{'g','g','g','g','g','b','b','g'}};

51

52

Pointcur(4,4);

53

charnew_color='y';

54

55

flood_fill(image,cur,new_color);

56

57

for(intr=0;r<ROWS;r++){

58

for(intc=0;c<COLS;c++){

59

cout<<image[r][c]<<"";

60

}

61

cout<<endl;

62

}

63

//輸出：

64

//gggggggg

65

//ggggg