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

(CSP-S)提高級C++語言試題A卷

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

認證時間：2019年10月19日

考生注意事項：

1、題紙共有10頁，答題紙共有1頁，滿分100分。請在答題紙上作答，寫在試題紙上的一律無效。

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

一、單項選擇題(共15題，每題2分，共計30分；每題有且僅有一個正確選項)

1.若有定義：int a=7； float x=2.5，y=4.7；則表達式x+a%3*(int)(x+y)%2的值是：( )

A.0.000000          B.2.750000          C.2.500000          D.3.500000

答案：D

題目分析：基礎題目，數(shù)據(jù)類型和運算符優(yōu)先順序。x+a%3*(int)(x+y)%2轉化為式子為：

2.5+7%3*(int)(2.5+4.7)%2

= 2.5+7%3*(int)(7.2)%2

= 2.5+1*7%2

= 2.5+7%2

= 3.5

2.下列屬于圖像文件格式的有( )

A.WMV          B.MPEG          C.JPEG          D.AVI

答案：C

題目分析：計算機基礎題目。考前準備的知識點中有，多注意一下電腦信息也能知道。WMV、MPEG、AVI是視頻格式，JPEG是圖像格式。

3. 二進制數(shù)11 1011 1001 0111 和 01 0110 1110 1011 進行邏輯或運算的結果是( )

A.11 1111 1111 1101          B.11 1111 1111 1101

C.10 1111 1111 1111          D.11 1111 1111 1111

答案：D

題目分析：考前單獨強調總結的知識點中有位運算的內容。逐位做或運算，兩個數(shù)字中有一個1即得1，選D。

11 1011 1001 0111

01 0110 1110 1011

11 1111 1111 1111

4.編譯器的功能是( )

A.將源程序重新組合

B.將一種語言(通常是高級語言)翻譯成另一種語言(通常是低級語言)

C.將低級語言翻譯成高級語言

D.將一種編程語言翻譯成自然語言

答案：B

題目分析：編譯成計算機能夠理解的語言，計算機識別二進制0和1。編譯器的主要工作流程：源代碼 → 編譯 → 目標代碼 → 鏈接(dll庫等) → 生成可執(zhí)行程序 。

5.設變量x為float型且已賦值，則以下語句中能將x中的數(shù)值保留到小數(shù)點后兩位，并將第三位四舍五入的是( )

A.X=(x*100+0.5)/100.0          B.x=(int)(x*100+0.5)/100.0;

C.x=(x/100+0.5)*100.0          D.x=x*100+0.5/100.0;

答案：B

題目分析：類型轉換題目，強制轉換，比較簡單，課堂練習過。B選項。

也可以假設x=3.141，然后帶入計算：

(int)(3.141*100+0.5)/100.0

= (int)(314.1+0.5)/100.0

= (int)(314.6)/100.0

= 314/100

= 3.14

6. 由數(shù)字1，1，2，4，8，8所組成的不同的4位數(shù)的個數(shù)是( )

A.104          B.102          C.98          D.100

答案：B

題目分析：排列組合題，最后專項講解中有類似的。

不能直接A(6,4)，要分情況討論：

(1)只有2個相同的數(shù)構成的4位數(shù)，1、1、2、4;1、1、2、8;1、1、4、8;1、2、8、8;1、4、8、8;2、4、8、8組成。

每種有A(4,4)/A(2,2)=4×3=12(種)

共有12×6=72種.

(2)4個不同的數(shù)構成，只有1、2、4、8組成,有A(4,4)=4×3×2×1=24(種)

(3)2個重復的數(shù)字構成，只有1、1、8、8,有C(4,2)=6(種)

所以,共有72+24+6=102(種)

7.排序的算法很多，若按排序的穩(wěn)定性和不穩(wěn)定性分類，則( )是不穩(wěn)定排序。

A.冒泡排序          B.直接插入排序          C.快速排序          D.歸并排序

答案：C

題目分析：上課和復習時講過。選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。

8. G是一個非連通無向圖(沒有重邊和自環(huán))，共有28條邊，則該圖至少有( )個頂點

A.10          B.9          C.11          D.8

答案：B

題目分析：圖的知識點。前幾天練習的題有相似的。也可以驗證答案。題目要求：沒有自環(huán)，而且是非連通圖。一個n 階的完全無向圖含有n*(n-1)/2 條邊，n=8的時候是8*7/2=28，意味著8個頂點最多有28條邊，第9個點可以單獨存在，不連通，可滿足條件。

9.一些數(shù)字可以顛倒過來看，例如0、1、8顛倒過來看還是本身，6顛倒過來是9，9顛倒過來看還是6，其他數(shù)字顛倒過來都不構成數(shù)字。類似的，一些多位數(shù)也可以顛倒過來看，比如106顛倒過來是901。假設某個城市的車牌只有5位數(shù)字，每一位都可以取0到9。請問這個城市有多少個車牌倒過來恰好還是原來的車牌，并且車牌上的5位數(shù)能被3整除？( )

A.40          B.25          C.30          D.20

答案：B

題目分析：排列組合題。枚舉每位數(shù)字的可能性。顛倒后還得是個數(shù)字，因此前2位有0,1,8,6,9，5種選擇，第3位只能放0,1,8，后2位由前2位決定。而0,1,8模3正好余0,1,2，所以給定其他4位，第3位有且僅有1種選擇，總數(shù)=5*5*1*1*1=25。

10.一次期末考試，某班有15人數(shù)學得滿分，有12人語文得滿分，并且有4人語、數(shù)都是滿分，那么這個班至少有一門得滿分的同學有多少人？( )

A.23          B.21          C.20          D.22

答案：A

題目分析：容斥原理，初賽課和沖刺課都講過。總滿分人數(shù)=數(shù)學滿分+語文滿分-語文數(shù)學滿分=15+12-4=23。

11.設A和B是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，請問任何以元素比較作為基本運算的歸并算法，在最壞情況下至少要做多少次比較？( )

A.n2           B.n㏒n          C.2n          D.2n-1

答案：D

題目分析：往年考過。也可枚舉n=1，一共2個數(shù)字，只需要比較1次，AD中選，n=2再驗證……

12.以下哪個結構可以用來存儲圖( )

A.棧          B.二叉樹          C.隊列          D.鄰接矩陣

答案：D

題目分析：可用排除法，講過數(shù)據(jù)結構的分類。

13.以下哪些算法不屬于貪心算法？( )

A.Di.jkstra算法          B.Floyd算法

C.Prim算法          D.Kruskal算法

答案：B

題目分析：提高組課上講過。Floyd是枚舉所有情況。

14.有一個等比數(shù)列，共有奇數(shù)項，其中第一項和最后一項分別是2和118098，中間一項是486，請問一下哪個數(shù)是可能的公比?( )

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

答案：B

題目分析：可以枚舉答案。等比數(shù)列，首項是2，公比是5，末項不可能是118098；

公比是4，486%4！=0；公比是2，可演算2的n次方不是118098。排除法，選B。

15.有正實數(shù)構成的數(shù)字三角形排列形式如圖所示。第一行的數(shù)為a1,1,第二行a2,1，a2,2，第n行的數(shù)為an,1，an,2，…，an,n。從a1,1開始，每一行的數(shù)ai,j只有兩條邊可以分別通向下一行的兩個數(shù)ai+1,j和ai+1,j+1。用動態(tài)規(guī)劃算法找出一條從a1,1向下通道an,1，an,2，…，an,n中某個數(shù)的路徑，使得該路徑上的數(shù)之和最大。

令C[i][j]是從a1,1到ai,j的路徑上的數(shù)的最大和，并且C[i][0]= C[0][j]=0，則C[i][j]=( )

A.max{C[i-1][j-1],C[i-1][j]}+ ai,j

B.C[i-1][j-1]+C[i-1][j]

C.max{C[i-1][j-1],c[i-1][j]}+1

D.max{C[i][j-1],C[i-1][j]}+ ai,j

答案：A

題目分析：dp基礎題：數(shù)塔，基礎講過，路徑只能從左上方和上方過來。

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

1.

概述：基礎題，大家模擬即可，可以帶入幾組數(shù)據(jù)執(zhí)行。例如：

5

1 2 3 4 5

判斷題

1)(1分)第16行輸出ans時，ans的值一定大于i。( )

答案：×

題目分析：第一次輸出，ans=i。(猜題小技巧：說“一定”的，很可能錯。)

2) 1分)程序輸出的ans小于等于n。( )

答案：√

題目分析：13行i<=n，15行ans<n才會自增，所以不會超過n。

3)若將第12行的“<”改為“!=”，程序輸出的結果不會改變。( )

答案：√

題目分析：最后結果不變。

4)當程序執(zhí)行到第16行時，若ans-i>2，則a[i+1]≦a[i]。( )

答案：√

題目分析：14行，由于ans是第一個大于a[i]的，所以a[i+1]..a[ans-1]都不超過a[i]，結論成立。

5)(3分)若輸入的a數(shù)組是一個嚴格單調遞增的數(shù)列，此程序的時間復雜度是( )。

A.0(logn)          B.0(n2)

C.0(nlog n)          D. 0(n)

答案：D

題目分析：根據(jù)舉例，單調增，復雜度為O(n)

6)最壞情況下，此程序的時間復雜度是( )。

A. 0(n2)          B. 0(logn)

C. 0(n)            D. 0(nlog n)

答案：A

題目分析：最壞情況下，while循環(huán)會一直執(zhí)行n，復雜度為1+2+..+n=O(n^2)

2.

分析：getroot函數(shù)是并查集中的find函數(shù)啊。下面就好辦了。

判斷題

1)(1分)輸入的a和b值應在[0，n-1]的范圍內。( )

答案：√

題目分析：找a、b的根結點，下標范圍為0到n-1，所以a、b范圍也在0到n-1。

2) (1分)第16行改成“fa[i]=0;”, 不影響程序運行結果。( )

答案：×

題目分析：初始化，標準寫法。

3) 若輸入的a和b值均在[0, n-1]的范圍內，則對于任意0≤i<n，都有0≤fa[i]<n。( )

答案：√

題目分析：并查集知識。

4) 若輸入的a和b值均在[0,n-1]的范圍內，則對于任意≤i<n，都有≤cnt[i] ≤n。( )

答案：×

題目分析：cnt表示集合數(shù)量。

選擇題

5)當n等于50時，若a、b的值都在[0,49]的范圍內，且在第25行時總是不等于y，那么輸出為( )

A.1276          B.1176          C.1225          D.1250

答案：C

題目分析：x和y都不同，每次都是單獨一個去和整體合并。此時cnt[y]增加cnt[x]的值，也就是加1。1*1+1*2+...1*49=50*49/2=1225。

6)此程序的時間復雜度是( )

A. O(n)          B. O(logn)          C. O(n)          D. O(nlogn)

答案：C

題目分析：并查集getroot函數(shù)沒有路徑壓縮，單次查找最壞為O(n)。總效率為O(n^2)。

3.本題t是s的子序列的意思是：從s中刪去若干個字符，可以得到t；特別的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

s[x..y]表示s[x]…s[y]共y-x+1個字符構成的字符串，若x>y則s[x..y]是空串。t[x..y]同理。

注意：是子序列，而不是子串。可以舉例輸入兩個字符串，進行驗證，即可模擬出pre數(shù)組和suf數(shù)組的內容。Pre數(shù)組保存的是前面匹配了多少個字符，suf保存的是從后面比較匹配了多少個字符。ans是匹配字符之間的距離最大值。

例如 abca ac

判斷題

1.(1分)程序輸出時，suf數(shù)組滿足：對任意0≤i<slen，suf[i] ≤suf[i+1].( )

答案：√

題目分析：15到19行程序中，循環(huán)變量初值是從大到小，從最后一個位置開始判斷，可以得出該結論。

2. (2分) 當t是s的子序列時，輸出一定不為0.( )

答案：×

題目分析：如果s==t時，結果是0。

3.(2分)程序運行到第23行時，“j-i-1”一定不小于0.( )

答案：×

題目分析：這個不一定，如果22行條件不成立,j=i=0，j-i-1就可能是負數(shù)。

4 (2分)當t時s的子序列時，pre數(shù)組和suf數(shù)組滿足：對任意0≤i<slen，pre[i]>suf[i+1]+1.( )

答案：×

題目分析：這個不一定。如果t==s='cc'代入檢驗，有的i可以pre[i]==suf[i+1]+1。

選擇題

5.若tlen=10，輸出為0，則slen最小為( )

A. 10          B. 12          C.0          D.1

答案：D

題目分析：求的是最小可能的長度。s的長度為1的時候，t=10，是空串，輸出是0。

6.若tlen=10，輸出為2，則slen最小為( )

A. 0          B.10          C.12          D.1

答案：C

題目分析：輸出是2說明存在子序列。s串刪去兩個元素后至少為10，因此刪前至少為12。

三、完善程序(單選題，每題3分，共計30分)

1.(匠人的自我修養(yǎng))一個匠人決定要學習n個新技術，要想成功學習一個新技術，他不僅要擁有一定的經(jīng)驗值，而且還必須要先學會若干個相關的技術。學會一個新技術之后，他的經(jīng)驗值會增加一個對應的值。給定每個技術的學習條件和習得后獲得的經(jīng)驗值，給定他已有的經(jīng)驗值，請問他最多能學會多少個新技術。

輸入第一行有兩個數(shù)，分別為新技術個數(shù)n(1≤n≤103)，以及已有經(jīng)驗值(≤10^7)。

接下來n行。第i行的兩個整數(shù)，分別表示學習第i個技術所需的最低經(jīng)驗值(≤10^7)，以及學會第i個技術后可獲得的經(jīng)驗值(≤10^4)。

接下來n行。第i行的第一個數(shù)mi(0≤mi<n)，表示第i個技術的相關技術數(shù)量。緊跟著m個兩兩不同的數(shù)，表示第i個技術的相關技術編號，輸出最多能學會的新技術個數(shù)。

下面的程序已O(n^2)的時間復雜完成這個問題，試補全程序。

分析：學技術有先后，經(jīng)驗值還得夠，根據(jù)已有的經(jīng)驗值選擇新技術，也可以用有向圖分析理解。可以用二維數(shù)組實現(xiàn)。n小于1000。

1) ①處應填( )

A. unlock[i]<=0

B. unlock[i]>=0

C. unlock[i]==0

D. unlock[i]==-1

答案：C

試題分析：學習新技術的條件之一。unlock判斷是否能解鎖任務。解鎖條件是需要0個前提任務。

2) ②處應填( )

A. threshold[i]>points

B. threshold[i]>=points

C. points>threshold[i]

D. points>=threshold[i]

答案：D

試題分析：學習新技術的條件之一。，經(jīng)驗點要夠，大于等于任務的需求點。

3) ③處應填( )

A. target = -1

B. --cnt[target]

C. bbonus[target]

D. points += bonus[target]

答案：D

題目分析：經(jīng)驗點增加。條件都滿足，可以學習新技術了。

4) ④處應填( )

A. cnt [child[target][i]] -=1

B. cnt [child[target][i]] =0

C. unlock[child[target][i]] -= 1

D. unlock[child[target][i]] =0

答案：C

題目分析：學習下一個技術需要解鎖的任務數(shù)，解鎖一個任務，unlock值都要減1。

5) ⑤處應填( )

A. unlock[i] = cnt[i]

B. unlock[i] =m

C. unlock[i] = 0

D. unlock[i] =-1

答案：B

題目分析：“開門”階段，讀入信息，由題意可知，m是任務依賴的任務數(shù)，當unlock[i]為-1時表示解鎖成功。其他選項沒有意義。

2.(取石子) Alice和Bob兩個人在玩取石子游戲，他們制定了n條取石子的規(guī)則，第i條規(guī)則為：如果剩余的石子個數(shù)大于等于a[i]且大于等于b[i]，那么她們可以取走b[i]個石子。他們輪流取石子。如果輪到某個人取石子，而她們無法按照任何規(guī)則取走石子，那么他就輸了，一開始石子有m個。請問先取石子的人是否有必勝的方法？

輸入第一行有兩個正整數(shù)，分別為規(guī)則個數(shù)n(1≤n≤64),以及石子個數(shù)m(≤10^7)。

接下來n行。第i行有兩個正整數(shù)a[i]和b[i]。(1≤a[i]≤10^7,1b[i]≤64)

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”。

提示：

可以使用動態(tài)規(guī)劃解決這個問題。由于b[i]不超過64，所以可以使用位無符號整數(shù)去壓縮必要的狀態(tài)。

status是勝負狀態(tài)的二進制壓縮，trans是狀態(tài)轉移的二進制壓縮。

試補全程序。

代碼說明:

“~”表示二進制補碼運算符，它將每個二進制位的0變成1、1變?yōu)?；

而“^”表示二進制異或運算符，它將兩個參與運算的數(shù)重的每個對應的二進制位一一進行比較，若兩個二進制位相同，則運算結果的對應二進制位為0，反之為1。

U11標識符表示它前面的數(shù)字是unsigned long long 類型。

題目分析：博弈論類的問題，講過。位運算，考前專門復習過。題目里說了，用動態(tài)規(guī)劃實現(xiàn)，并且用位運算代替數(shù)組實現(xiàn)。

1)①處應填( )

A.0

B .~0ull

C.~0ull^1

D.1

答案：C

題目分析：根據(jù)題目要求，狀態(tài)壓縮到64位，A和D默認是32位整數(shù)，所以B或者C。最開始石子是0個，應該是輸?shù)臓顟B(tài)，所以最低位不能是1，選C。

2)處應填( )

A.a[j]< i

B.a[j]==i

C.a[j] !=i

D.a[j] >i

答案：B

題目分析：n個條件范圍內，符合題目要求的石子個數(shù)，即可發(fā)生狀態(tài)轉移，選B。并且根據(jù)代碼，狀態(tài)轉移到trans變量。增加狀態(tài)，位運算|實現(xiàn)加的功能，下一個選A。

3)③處應填( )

A. trans |= 1ull <<(b[j] - 1)

B. status |= 1ull << (b[j]- 1)

C. status += 1ull << (b[j]-1)

D. trans += 1ull<< (b[j]-1)

答案：A

4)④處應填( )

A. ~status|trans

B. status&trans

B. status|trans

D. ~status&trans

答案：D

題目分析：判斷win的值。先手必勝，對當前狀態(tài)和以前狀態(tài)做判斷。

5)⑤處應填( )

A. trans = status | trans ^win

B. status = trans >> 1^win

C. trans = status ^trans |win

D. status =status <<1^win

答案：D

更新status狀態(tài)值，將當前win值記錄到status中。

以上是2019CSP-S(提高級)C++語言題目的解題分析，參加此次考試的學員們，你們都答對了嗎？另，關注童程童美微信公眾號，后臺回復【真題】即可免費領取“信息學奧賽歷年真題資料包”哦~

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

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