2019年10月19日CSP非專業(yè)級(jí)別第一輪能力認(rèn)證結(jié)束，全國31個(gè)省市共計(jì)106,344人參加！

參與的小伙伴們，測評(píng)結(jié)束了，分?jǐn)?shù)評(píng)估了嗎？趁著現(xiàn)在記憶仍在，趕緊對(duì)著答案來看看吧！童程童美NOI教研部門第一時(shí)間為廣大學(xué)員整理了2019CSP-J 題目解析，以供參考。

關(guān)注童程童美公眾號(hào)，在歷史消息中可查看2019CSP-S試題解析！

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

(CSP-J)入門級(jí)C++語言試題A卷

(B卷與A卷僅順序不同)

認(rèn)證時(shí)間：2019年10月19日

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

1、題目紙共有9頁，答題紙共有1頁，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無效

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

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

1.中國的國家頂級(jí)域名是( )

A. .cn          B. .ch          C. .chn          D. .China

答案：A

題目分析：常識(shí)，詳情見普及組課程105課時(shí)。

2.二進(jìn)制數(shù)11 1011 1001 0111和01 0110 1110 1011進(jìn)行邏輯與運(yùn)算的結(jié)果是( )

A.01 0010 1000 1011          B.01 0010 1001 0011

C.0l 0010 1000 0001          D.01 0010 1000 0011

答案：D

題目分析：邏輯與運(yùn)算，當(dāng)且僅當(dāng)2個(gè)數(shù)對(duì)應(yīng)位都為1的，答案才為1，詳情見普及組課程63課時(shí)。

3.一個(gè)32位整型變量占用()個(gè)字節(jié)。

A. 32          B.128          C. 4          D.8

答案：C

題目分析：1Byte(字節(jié)) = 8 bit(位) 32/8=4 詳情見普及組課程103課時(shí)。

4.若有如下程序段,其中s、a、b、c均已定義為整型變量,且a、c均已賦值(c大于0)

s=a

for(b= 1: b< c: b++)s=s-1

則與上述程序段功能等價(jià)的賦值語句是()

A.s=a-c;          B.s=a-b;          C.s=s-c;          D.s=b-c;

答案：A

題目分析：s初始化為a; for循環(huán)執(zhí)行c次，每次s減1，共減c，所以s=a-c

考察for循環(huán)的應(yīng)用，詳情見普及組課程16課時(shí)。

5.設(shè)有100個(gè)已排好序的數(shù)據(jù)元素，采用折半查找時(shí)，最大比較次數(shù)為()

A.7          B.10          C.6          D.8

答案：A

題目分析：折半查找，首先將待查記錄所在范圍縮小一半，然后再縮小一半，即對(duì)100個(gè)元素進(jìn)行折半查找，第一次比較范圍縮小到50，第二次縮小到25，第三次縮小到17，第四次縮小到7，第五次縮小到4，第六次縮小到2，最多七次就可以查找到所要元素。詳情見普及組課程第106課時(shí)。

6.鏈表不具有的特點(diǎn)是()

A.插入刪除不需要移動(dòng)元素          B.不必事先估計(jì)存儲(chǔ)空間

C.所需空間與線性表長度成正比          D.可隨機(jī)訪問任一元素

答案：D

題目分析：鏈表沒有下標(biāo)，不可隨機(jī)訪問詳情見普及組第108課時(shí)。

7.把8個(gè)同樣的球放在5個(gè)同樣的袋子里，允許有的袋子空著不放，問共有多少種不同的分法？( )提示：如果8個(gè)球都放在一個(gè)袋子里，無論是哪個(gè)袋子，都只算同一種分法。

A.22          B.24          C.18          D.20

答案：C

題目分析：把整數(shù)8拆分成5個(gè)數(shù)字之和，允許有0，我們可以按照非零數(shù)字個(gè)數(shù)進(jìn)行枚舉，1個(gè)：1種，2個(gè)：4種，3個(gè)：5種，4個(gè)：5種，5個(gè)：3種，累加起來一共18種。詳情見普及組課 程109課時(shí)。

8.一棵二叉樹如右圖所示，若采用順序存儲(chǔ)結(jié)構(gòu)，即用一維數(shù)組元素存儲(chǔ)該二叉樹中的結(jié)點(diǎn)(根結(jié)點(diǎn)的下標(biāo)為1，若某結(jié)點(diǎn)的下標(biāo)為i，則其左孩子位于下標(biāo)2i處、右孩子位于下標(biāo)2i+1處)，則該數(shù)組的最大下標(biāo)至少為()

A.6          B.10          C.15          D.12

答案：C

題目分析：根據(jù)題目描述直接計(jì)算就可以了，((1*2+1)*2+1)*2+1=15

詳情見普及組課程99課時(shí)。

9.100以內(nèi)最大的素?cái)?shù)是()。

A.89          B.97          C.91          D.93

答案：B

題目分析：97最大且為素?cái)?shù)，詳情見普及組課程123課時(shí)。

10.319和377的最大公約數(shù)是()。

A.27          B.33          C.29          D.31

答案：C

題目分析：使用輾轉(zhuǎn)相除法計(jì)算(319,377)=(319,58)=(58,29) = 29

詳情見普及組課程第121課時(shí)。

11.新學(xué)期開學(xué)了，小胖想減肥，健身教練給小胖制定了兩個(gè)訓(xùn)練方案。方案一：每次連續(xù)跑3公里可以消耗300千卡(耗時(shí)半小時(shí))；方案二：每次連續(xù)跑5公里可以消耗600千卡(耗時(shí)1小時(shí))。小胖每周周一到周四能抽出半小時(shí)跑步，周五到周日能抽出一小時(shí)跑步。另外，教練建議小胖每周最多跑21公里，否則會(huì)損傷膝蓋。請(qǐng)問如果小胖想嚴(yán)格執(zhí)行教練的訓(xùn)練方案，并且不想損傷膝蓋,每周最多通過跑步消耗多少千卡？()

A.3000          B.2500          C.2400          D.2520

答案：C

題目分析：設(shè)方案1,2各i,j天，由題意，3*i+5*j<=21,i+j<=7,i<=3.求300*i+600*j的最大值。枚舉所有情況當(dāng)i=2,j=3時(shí)，最大值2400。

12.一副紙牌除掉大小王有52張牌，四種花色，每種花色13張。假設(shè)從這52張牌中隨機(jī)抽取13張紙牌，則至少( )張牌的花色一致

A.4          B.2          C.3          D.5

答案：A

題目分析：抽屜原理，13張牌最壞情況就是4種花色分別為3,3,3,4張，也就是至少4張一樣花色。

13.一些數(shù)字可以顛倒過來看，例如0、1、8顛倒過來還是本身，6顛倒過來是9，顛倒過來看還是6，其他數(shù)字顛倒過來都不構(gòu)成數(shù)字。類似的，一些多位數(shù)也可以顛倒過來看，比如106顛倒過來是901。假設(shè)某個(gè)城市的車牌只由5位數(shù)字組成，每一位都可以取0到9。請(qǐng)問這個(gè)城市最多有多少個(gè)車牌倒過來恰好還是原來的車牌？()

A.60          B.125          C.75          D.100

答案：C

題目分析：考察乘法原理，第1，2位有5種選法(0，1，6，8，9)，第三位有三種0，1，8，第4，5位由前兩位決定，所以答案位5*5*3=75。

14.假設(shè)一棵二叉樹的后序遍歷序列為 DGJHEBIFCA，中序遍歷序列為 DBGEHJACIF，則其前序遍歷序列為( )。

A. ABCDEFGHIJ          B. ABDEGHJCFI

C. ABDEGJHCFI          D. ABDEGHJFIC

答案：B

題目分析：考察二叉樹的遍歷，后序遍歷決定根是A，中序遍歷中看A的左邊DBGEH是左子樹，右邊CIF是右子樹，依次類推可畫出完整的樹，再求先序遍歷，詳情見普及組課程100課時(shí)。

15.以下哪個(gè)獎(jiǎng)項(xiàng)是計(jì)算機(jī)科學(xué)領(lǐng)域的最高獎(jiǎng)？()

A.圖靈獎(jiǎng)          B.魯班獎(jiǎng)          C.諾貝爾獎(jiǎng)          D.普利策獎(jiǎng)

答案：A

題目分析：考察常識(shí)問題，并且是一道原題。詳情見普及組課程102課時(shí)。

二、閱讀程序(程序輸入不超過數(shù)組或字符串定義的范圍：判斷題正確填√，錯(cuò)誤填×：除特殊說明外，判斷題1.5分，選擇題3分，共計(jì)40分)

1.

判斷題

1)輸入的字符串只能由小寫字母或大寫字母組成。()

答案：×

題目分析：題目沒說，可以輸入包含其他字符的字符串。

2)若將第8行的“i=1”改為“i=0”,程序運(yùn)行時(shí)會(huì)發(fā)生錯(cuò)誤()

答案：√

題目分析：不能對(duì)0取余操作，錯(cuò)誤。

3)若將第8行的“i<=n”改為“i*i<=n”,程序運(yùn)行結(jié)果不會(huì)改變()

答案：×

題目分析：求約數(shù)不是判斷質(zhì)數(shù)，i*i<=n只能取到n的前半部分約數(shù)。

4)若輸入的字符串全部由大寫字母組成,那么輸出的字符串就跟輸入的字符串一樣。()

答案：√

題目分析：按題意說明即可判斷。

選擇題

5)若輸入的字符串長度為18,那么輸入的字符串跟輸出的字符串相比至多有()個(gè)字符不同。

A.18           B.6           C.10           D.1

答案：B

題目分析：約數(shù)個(gè)數(shù)定理求約數(shù)個(gè)數(shù)。18的約數(shù)是：1，2，3，6，9，18。所以最多判定6次。

6)若輸入的字符串長度為(),那么輸入的字符串跟輸出的字符申相比,至多有36個(gè)字符不同。

A.36           B.100000           C.1           D.128

答案：B

題目分析：和上題同理。枚舉4個(gè)選項(xiàng)。36有9個(gè)約數(shù)，1有1個(gè)約數(shù)，128有8個(gè)約數(shù)。選B。100000有36個(gè)約數(shù)。

2.

假設(shè)輸入的n和m都是正整數(shù),x和y都是在[1,n]的范圍內(nèi)的整數(shù)，完成下面的判斷題和單選題

判斷題

1)當(dāng)m>0時(shí),輸出的值一定小于2n。()

答案：√

題目分析：按照題意，a數(shù)組和b數(shù)組賦值為0，a[x] < y && b[y] < x成立，累計(jì)計(jì)算求和，最終結(jié)果肯定小于2n。

2)執(zhí)行完第27行的“++ans”時(shí),ans一定是偶數(shù)。()

答案：×

題目分析：不一定，可以舉例求出ans不是偶數(shù)的情況。

3) a[i]和b[i]不可能同時(shí)大于0。()

答案：×

題目分析：舉例即可找到反例。

4)若程序執(zhí)行到第13行時(shí),x總是小于y,那么第15行不會(huì)被執(zhí)行。()

答案：×

題目分析：同樣舉例可以實(shí)現(xiàn)。

選擇題

5)若m個(gè)x兩兩不同,且m個(gè)y兩兩不同,則輸出的值為()

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

答案：A

題目分析：根據(jù)題意，m次循環(huán)中會(huì)有2m個(gè)位置的值會(huì)變化，ans=2n-2m。

6)若m個(gè)x兩兩不同,且m個(gè)y都相等,則輸出的值為()

A.2n-2           B.2n           C.2m           D.2n-2m

答案：A

題目分析：如果m個(gè)x各不相同，循環(huán)里面的if都不會(huì)執(zhí)行。對(duì)數(shù)組a，b賦值，只修改了2個(gè)位置。也可舉例

3 3

3 3

2 3

1 3

答案是4。

3.

分析：分治算法。左右兩邊找答案，然后求運(yùn)算。

判斷題

1)如果a數(shù)組有重復(fù)的數(shù)字,則程序運(yùn)行時(shí)會(huì)發(fā)生錯(cuò)誤。()

答案：×

題目分析：分析代碼，有重復(fù)的數(shù)字不會(huì)導(dǎo)致程序運(yùn)行出錯(cuò)。

2)如果b數(shù)組全為0，則輸出為0.()

答案：√

題目分析：如果b數(shù)組是0，遞歸推出條件l>r返回0，根據(jù)return lres + rres + depth * b[mink];返回結(jié)果總是0。

選擇題

3)當(dāng)n=100時(shí)，最壞情況下，與第12行的比較運(yùn)算執(zhí)行的次數(shù)最接近的是()

A.5000           B.6000           C.6           D.100

答案：A

題目分析：最壞情況下a有序，總是求mink和min最小值，需要判斷100+99+98+...+2+1 =5050，選A。

4)當(dāng)n=100時(shí),最好情況下,與第12行的比較運(yùn)算執(zhí)行的次數(shù)最接近的是()

A.100           B.6           C.5000           D.600

答案：D

題目分析：最好情況每次都二分，總次數(shù)為100，層數(shù)為 6<log2100<7，總次數(shù)約為[6*100,7*100]，選D。

5)當(dāng)n=10時(shí),若b數(shù)組滿足,對(duì)任意0≤i<n,都有b[i]=i+1,那么輸出最大為()

A.386           B.383           C.384           D.385

答案：D

題目分析：n=10，深度最大是10，根據(jù)代碼：1*b[0]+2*b[1]+...+10*b[9]=1*1+2*2+3*3+...+10*10=385。

6)(4分)當(dāng)n=100時(shí),若b數(shù)組滿足,對(duì)任意0≤i<n,都有b[i]=1, 那么輸出最小為()

A.582           B.580           C.579           D.581

答案：B

題目分析：b[i]=1,即求一個(gè)100節(jié)點(diǎn)的完全二叉樹，節(jié)點(diǎn)深度之和最小為多少。畫圖后，計(jì)算為1*1+2*2+4*3+8*4+16*5+32*6+37*7=580

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

1.

① 處應(yīng)填( )

A.n%2          B.0          C.t          D.1

答案：C

題目分析：(猜的話，變量t沒有用過。)遞歸退出判斷，參數(shù)t的賦值能發(fā)現(xiàn)是經(jīng)常做取反操作。賦值和n沒有必然聯(lián)系，錯(cuò)誤。選C。

② 處應(yīng)填( )

A.x-step,y-step           B.x,y-step

C.x-step,y           D.x,y

答案：D

題目分析：四個(gè)方向，x，y是當(dāng)前坐標(biāo)。根據(jù)下面參數(shù)，參數(shù)分別是x,y;x,y+step;x+step,y;x+step,y+step。

③ 處應(yīng)填( )

A. x-step,y-step           B. x+step,y+step

C. x-step,y           D. x,y-step

答案：B

④ 處應(yīng)填( )

A.n-1,n%2           B.n,0           C.n,n%2           D.n-1,0

答案：B

題目分析：第一次調(diào)用recursive函數(shù)，n是矩陣規(guī)模，初始為n，t是取反次數(shù)，所以t初始為0或者1。

1)⑤ 處應(yīng)填( )

A.i<<(n+1)           B.1<<n           C.n+1           D.1<<(n-1)

答案：B

題目分析：size是輸出矩陣的邊長，2^n,位運(yùn)算是1<<n。

2. (計(jì)數(shù)排序)計(jì)數(shù)排序是一個(gè)廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計(jì)數(shù)排序，對(duì) n 對(duì) 10000 以內(nèi)的整數(shù)，從小達(dá)到排序。

例如有三對(duì)整數(shù)(3，4)、(2，4)、(3，3)，那么排序之后應(yīng)該是(2，4)、(3，3)、(3，4)。

輸入第一行為 n，接下來 n 行，第 i 行有兩個(gè)數(shù) a[i] 和 b[i]，分別表示第 i 對(duì)整數(shù)的第一關(guān)鍵字和第二關(guān)關(guān)鍵字。

從小到大排序后輸出。

提示：應(yīng)先對(duì)第二關(guān)鍵字排序，再對(duì)第一關(guān)鍵字排序。數(shù)組 ord[]存儲(chǔ)第二關(guān)鍵字排序的結(jié)果，數(shù)組 res[]存儲(chǔ)雙關(guān)鍵字排序的結(jié)果。

試補(bǔ)全程序

1)①處應(yīng)填()

A. ++cnt[1]

B. ++cnt[b[1]]

C. ++cnt[a[i]*maxs+b[i]]

D. ++cnt[a[i]]

答案：B

題目分析：提示：應(yīng)先對(duì)第二關(guān)鍵字排序，再對(duì)第一關(guān)鍵字排序。排序的題做了很多，認(rèn)真讀題，不是特別難的事。先對(duì)第二關(guān)鍵字進(jìn)行排序，選B。

2)②處應(yīng)填()

A. ord[--cnt[a[i]]]=i

B, ord[--cnt[b[i]]]=a[i]

C. ord[--cnt[a[i]]]=b[i]

D. ord[--cnt[b[i]]]=i

答案：D

題目分析：cnt[b[i]]表示第i個(gè)數(shù)按第二關(guān)鍵字排的位。ord[i]表示第i個(gè)數(shù)在原位置。

3)③處應(yīng)填()

A. ++cnt[b[i]]

B. ++cnt[a[i]*maxs+ b[i]]

C, ++cnt[a[il]

D. ++cnt[i]

答案：C

題目分析：對(duì)第一關(guān)鍵字進(jìn)行計(jì)數(shù)。

4)④處應(yīng)填()

A. res[--cnt[a[ord[i]]]]=ord[i]

B. res[--cnt[b[ord[i]]]]=ord[i]

C. res[--cnt[b[i]]]=ord[i]

D. res[--cnt[a[i]]]=ord[i]

答案：A

題目分析：對(duì)應(yīng)填空②，此處res[i]記錄第一關(guān)鍵字第i的數(shù)的原位置。

5) ⑤處應(yīng)填()

A. a[i],b[i]

B. a[res[i]], b[res[i]]

C. a[ord[res[i]]], b[ord[res[i]]]

D. a[res[ord[i]]], b[res[ord[i]]]

答案：B

題目分析：res[i]記錄第i個(gè)數(shù)的原位置。

以上是2019CSP-J(入門級(jí))C++語言試題的題目分析，參加此次測評(píng)的學(xué)員們，你們都答對(duì)了嗎？另，關(guān)注童程童美微信公眾，在后臺(tái)回復(fù)【真題】即可免費(fèi)領(lǐng)取“信息學(xué)奧賽歷年真題資料包”哦~

CSP-J/S是CCF創(chuàng)辦的CSP(軟件能力認(rèn)證)中面向非專業(yè)級(jí)的軟件能力認(rèn)證，也就是我們熟知的信息學(xué)奧賽，含金量高。

童程童美信息學(xué)奧賽課程是由專業(yè)教研團(tuán)隊(duì)與北京知名學(xué)府聯(lián)合研發(fā)，課程內(nèi)容循序漸進(jìn)，指導(dǎo)學(xué)員圍繞每個(gè)考試階段的重點(diǎn)知識(shí)進(jìn)行學(xué)習(xí)；教研團(tuán)隊(duì)強(qiáng)大專業(yè)，授課老師經(jīng)驗(yàn)充足，確保準(zhǔn)確把握競賽方向和特點(diǎn)，保證學(xué)員學(xué)習(xí)進(jìn)度和質(zhì)量，助力學(xué)員在測評(píng)中取得優(yōu)異成績！