2022年CCF非專業(yè)級別軟件能力認(rèn)證第一輪CSP-J入門級第一輪試題答案與解析

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

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

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

一、單項(xiàng)選擇題（每題2分，共計(jì)30分）

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

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

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

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

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

【答案】A

【解析】printf函數(shù)是C語言中的函數(shù)，C語言是面向過程的語言，因此選A。

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

()O

A.543612

B.453126

C.346521

D.234156

【答案】C

【解析】模擬入棧出棧，C選項(xiàng)中“65”不可能實(shí)現(xiàn)。

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

intX=lei；

inty=201；

int*p=&x;

int*q=&y;

P=q;

A.將x的值賦為201

B.將y的值賦為101

C.將q指向x的地址

D.將p指向y的地址

［答案］D

【章析】初始時P指向x的地址，q指向y的地址，執(zhí)行第5行程序后，將p指向y的地址。

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

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

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

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

D.以上均正確

【答案】C

【解析】A選項(xiàng)，數(shù)組可以排序；B選項(xiàng)，鏈表不能存儲比數(shù)組更多的信息；C選項(xiàng)正確。

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

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

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

e6、e5和el出隊(duì)列。則棧S的容量至少是()個數(shù)據(jù)。

A.2

B.3

C.4

D.6

［答案］B

【章析】棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。依題意模擬過程，括號中表示棧中數(shù)據(jù)的個

數(shù)：e1入棧⑴，e2入棧⑵,e2出棧⑴，e3入棧⑵，e4入棧(3),e4出棧⑵，e3出棧⑴，e5入

棧(2),e6入棧(3),e6出棧(2),e5出棧(1),e1出棧(0)。棧的容量至少為3。

6.對表達(dá)式a+(b-c)*d的前綴表達(dá)式為()，其中+、-、*是運(yùn)算符。

A.*+a-bcd

B.+a*-bcd

C.abc-d*+

D.abc-+d

［答案］B

【藍(lán)析】中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法：

①將所有運(yùn)算按照優(yōu)先級加上小括號，(a+((b-c)*d))

②將運(yùn)算符移到對應(yīng)小括號前，+(a*(-(bc)d)

③去掉小括號，+a*-bcd

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

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

（）位。

A.1

B.2

C.2或3

D.3

【答案】B

【解析】按照哈夫曼編碼規(guī)則畫出哈夫曼樹，如下圖結(jié)點(diǎn)d到根節(jié)點(diǎn)的邊數(shù)即編碼長度為2。

1015

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

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

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

A.8、18

B.10、18

C.8、19

D.10>19

［答案］Q

【章析】9的父結(jié)點(diǎn)是4,兄弟結(jié)點(diǎn)是8,左兒子結(jié)點(diǎn)是18,右兒子結(jié)點(diǎn)是19

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

（）個非零元素。

A.N-1

B.N

C.N+1

D.N2

［答案］B

【血析】n個點(diǎn)有向連通圖，至少有n條邊，連成一圈，鄰接矩陣中非零元素即為邊數(shù)最少為n。

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ì)列。

【答案】D

【解析】使用兩個棧，一個棧存放入隊(duì)的操作，另一個棧用來出隊(duì)，即可用棧實(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;s->prev=p;p->next=s;s->next=p->next;

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

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

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

［答案］D

【章析】畫圖模擬，選項(xiàng)D正確。

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

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

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

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

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

【答案】B

【解析】選擇排序是不穩(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

【答案】C

【解析】按權(quán)展開，3x8+2x1+1x1/8=26.125

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

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

A.12

B.13

C.14

D.15

【章析】所有子串共有16個，刨去重復(fù)的子串“a“,”b“,“ab"，余下13個不重復(fù)的子串。

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

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

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

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

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

［答案］B

【章析】遞歸是通過調(diào)用自身來求解問題的編程技術(shù)，B選項(xiàng)正確。

二、閱讀程序題（除特殊說明外，判斷題每題1.5分，選擇題每題3分，共計(jì)40分）

01

程序（1）

01#include<iostream>

02

03usingnamespacestd;

04

05intmain()

06{

07unsignedshortx,y;

08cin>>x>>y;

09X=(Xx?2)&0x33；

10X=(X1X<<1)&0x55；

11y=(y1y?2)&0x33；

12y=(y1y<<i)&0X55；

13unsignedshortz=x|y<<1;

14cout<<z<<endl;

15return0;

16}

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

【解析】本程序考查位運(yùn)算的知識點(diǎn)。unsignedshort表示無符號短整型，數(shù)據(jù)范圍為0~

65535,占2個字節(jié)。|為按位或運(yùn)算，&為按位與運(yùn)算，vv為左移運(yùn)算。需要注意的是vv運(yùn)

算優(yōu)先級高于|o0x33表示十六進(jìn)制的33,即十進(jìn)制的51;0x55表示十六機(jī)制的55,即十進(jìn)

制的85。

【答案】4

【解析】short為16位，刪除unsigned,相當(dāng)于少了一位最高位。0x55=01010101B,少一位

不影響運(yùn)算結(jié)果。

17.將第7行與第13行的short均改為char,程序行為不變。()

【答案】X

【解析】輸入為不超過15的自然數(shù)，改為char以后，當(dāng)輸入為兩位數(shù)時，x,y分別讀入的是第

一個數(shù)的十位和個位，改變了程序的行為和結(jié)果。

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

【答案】X

【解析】代入“22”，輸出結(jié)果為“12”。

19.當(dāng)輸入為“22”時，輸出為“10”o()

【答案】X

【解析】代入“22”，輸出結(jié)果為“12”。

20.當(dāng)輸入為“22”時，輸出為“59”o()

【答案】X

【解析】代入“22”，輸出結(jié)果為“12”。

?單選題

21.當(dāng)輸入為“138”時，輸出為()。

A.“0”B.“209”C."197”D."226

［答案］B

【解析】代入‘138”,輸出結(jié)果為“209”。

02

程序(2)

01#include<algorithm>

02#include<iostream>

03#include<limits>

04

05usingnamespacestd;

06

07constintMAXN=105;

08constintMAXK=105;

09

10inth[MAXN][MAXK]；

11

12intf(intn,intm)

13{

14if(m==1)returnn;

15if(n==0)return0;

16

17intret=numeric_limits<int>::max();

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

19ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);

20returnret;

21}

22

23intg(intn,intm)

24{

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

26h[i][l]=i;

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

28h[0][j]=0;

29

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

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

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

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

34h[i][j]=min(

35h[i][j],

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

37}

38}

39

40returnh[n][m];

41}

42

43intmain()

44{

45intn,m;

46cin>>n>>m;

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

48return0;

49}

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

【解析】本程序中f函數(shù)和g函數(shù)的計(jì)算結(jié)果是一樣的，f函數(shù)通過遞歸實(shí)現(xiàn)，g函數(shù)通過循環(huán)實(shí)

現(xiàn)。因此，在計(jì)算結(jié)果時，可以代入任意函數(shù)列表進(jìn)行計(jì)算得到結(jié)果。

?判斷題

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

【答案】X

【解析】代入模擬計(jì)算，共執(zhí)行了448次。亦可通過遞推式根據(jù)奇偶性快速判斷。

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

【答案】Y

【解析】兩個函數(shù)的計(jì)算結(jié)果是一樣的。

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

【答案】q

【解析】代入f函數(shù)，當(dāng)m==1時，計(jì)算結(jié)果為n。

?單選題

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

A.O(n3^2m)B.O(nm)C.O(n2m)D.O(nm2)

【答案】C

【解析】i=1時，內(nèi)層兩重循環(huán)重復(fù)(m-1)次;

i=2時，內(nèi)層兩重循環(huán)重復(fù)2(m-1)次；

i=n時，內(nèi)層兩重循環(huán)重復(fù)n(m-1)次；

累加求和，可得”(m-1)=n(n+1)(m+1)/2,時間復(fù)雜度為0()。

【答案】C

【解析】代入模擬，可以發(fā)現(xiàn)m=2時，列舉出門為1~20的計(jì)算結(jié)果為1個1,2個2,3個3,4

個4,5個5,5個6,因此結(jié)果為6。

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

A.“6"B.“7"C.“8"D.“9”

【答案】B

【薛析】代入模擬，先計(jì)算出m=1,m=2,m=3的情況，找出規(guī)律，可以發(fā)現(xiàn)當(dāng)m=100的時

候，列舉出n從1~100的結(jié)果，為1個1,2個2,4個3,8個4,16個5,32個6,37個7,

因此結(jié)果為7。

032

程序(3)

01#include<iostream>

02

03usingnamespacestd;

04

05intn,k;

06

07intsolvel()

08{

09int1=0,r=n;

10while(1<=r){

11intmid=(1+r)/2;

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

13elser=mid-1;

14}

15return1-1;

16}

17

18doublesolve2(doublex)

19{

20if(x==0)returnx;

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

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

23returnx;

24}

25

26intmain()

27{

28cin>>n>>k;

29doubleans=solve2(solvel());

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

31return0;

32)

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

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

【解析】本程序考查二分法及牛頓迭代法求算術(shù)平方根。solvel函數(shù)用二分法求出近似的算術(shù)平方

根，然后用solve2函數(shù)進(jìn)行牛頓迭代法，求出n的算術(shù)平方根。k為迭代的次數(shù)。

?判斷題

28.該算法最準(zhǔn)確的時間復(fù)雜度分析結(jié)果為O(log7i+k)。()

【答案】Y

【解析】solvel函數(shù)是二分O(logn),solve2函數(shù)是0(k),都只執(zhí)行一次，是O(logn+k)。

29.當(dāng)輸入為“98011”時，輸出的第一個數(shù)為“99”。()

【答案】?

【解析】9801=99x99,算術(shù)平方根為99o

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

【答案】X

【解析】如果算術(shù)平方根是無理數(shù)，則第二個數(shù)輸出為0。

【答案】X

【解析】n<=47000,mid<=n/2<=23500,mid*mid<=552,250,000,不會溢出。

?單選題

32.當(dāng)輸入為“2r時，輸出的第一個數(shù)最接近()。

A.1B.1.414C.1.5D.2

【答案】C

【解析】代入計(jì)算，solvel函數(shù)的計(jì)算結(jié)果為1,solve2函數(shù)的計(jì)算結(jié)果為1.5。

33.當(dāng)輸入為“310”時，輸出的第一個數(shù)最接近()。

A.1.7B.1.732C.1.75D.2

【答案】B

【解析】43=1.732...,k=10,迭代次數(shù)越多精度越高，因此接近B。

34.當(dāng)輸入為“25611”時，輸出的第一個數(shù)（)O

A.等于16B.接近但小于16

C.接近但大于16D.前三種情況都有可能

【答案】A

【解析】256=16x16,輸出的第一個數(shù)等于16。

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

01

程序（1）

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

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

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

02usingnamespacestd;

03

04intmain(){

05intn;

06cin>>n;

07

08vector<int>fac;

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

10

11inti;

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

13if(①){

14fac.push_back(i);

15}一

16}

17

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

19cout<<②<<"

20}

21if(③){

22cout<<(4)<<"

23}

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

25cout<<⑤<<"

26}

27)

【解析】本程序先從小到大輸出小于算術(shù)平方根的因數(shù)，再特判算術(shù)平方根，最后輸出大于算術(shù)平

方根的因數(shù)。

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

A.n%i==0B.n%i==1

C.n%（i-1）==0D.n%（i-1）==1

【答案】A

【解析】判斷i是n的一個因數(shù)，則加入數(shù)組fac中，因此判斷條件為Ao

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

A.n/fac[k]B.fac[k]

C.fac[k]-1D.n/(fac[k]-l)

【答案】B

【解析】當(dāng)前數(shù)組fac存儲的是小于平方根的所有因數(shù)，按順序輸出即可。

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

A.(i-1)*(i-1)==nB.(i-1)*i==n

C.i*i==nD.i*(i-1)==n

[答案]c

【漏析】特判，如果是完全平方數(shù)i*i==n,則輸出算術(shù)平方根io

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

A.n-iB.n-i+1

C.i-1D.I

【答案】D

【解析】如果是完全平方數(shù)i*i==n,則輸出算術(shù)平方根io

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

A.n/fac[k]B.fac[k]

C.fac[k]-lD.n/(fac[k]-l)

【答案】A

【解析】從小到大輸出大于算術(shù)平方根的因數(shù)，因此需要倒序枚舉小于算術(shù)平方根的因數(shù)fac[k],

輸出對應(yīng)的另一個因數(shù)n/fac[k]o

021

程序（2）

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

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

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

都與起始像素顏色相同），替換為給定的顏色。

試補(bǔ)全程序。

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

02usingnamespacestd;

03

04constintROWS=8;

05constintCOLS=8;

06

07structPoint{

08intr,c;

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

10}；

11

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

13intprev_color,intnew_color){

14intr=pt.r;

15intc=pt.c;

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

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

18}

19

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

21queue<Point>queue;

22queue.push(cur);

23

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

25②；

26

27while('queue.empty()){

28Pointpt=queue.front();

29queue.pop();

30

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

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

33for(autop:points){

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

35④；

36⑤；

37)

38)

39}

40)

41

42intmain(){

43charimage[ROWS][COLS]{{'g','g','g",'g',‘gl'g','gl'g'},

44{'g','g'."g'>'g'>'g','g','r',

45{'g','r','r','g','g',’g','g'},

46{'g','b','b','b','r','g','r'}t

47{'g','g'.'g','b：'b','r','g','r'},

48{'g','g','g','b]，b',，b',，b',，r，},

'g'：'b'：'g'：'g'}：

49{‘gl'g','g'>'g',

50{'g','g','g','g',g','b','b','g')}；

51

52Pointcur(4,4);

53charnew_color='y';

54

55flood_fill(image,cur,new_color);

56

57for(intr=0;r<ROWS