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

(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

題目分析：基礎題目，數據類型和運算符優先順序。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. 二進制數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

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

11 1011 1001 0111

01 0110 1110 1011

11 1111 1111 1111

4.編譯器的功能是( )

A.將源程序重新組合

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

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

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

答案：B

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

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

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. 由數字1，1，2，4，8，8所組成的不同的4位數的個數是( )

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

答案：B

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

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

(1)只有2個相同的數構成的4位數，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個不同的數構成，只有1、2、4、8組成,有A(4,4)=4×3×2×1=24(種)

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

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

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

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

答案：C

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

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

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

答案：B

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

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

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

答案：B

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

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

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

答案：A

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

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

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

答案：D

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

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

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

答案：D

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

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

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

C.Prim算法          D.Kruskal算法

答案：B

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

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

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

答案：B

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

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

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

令C[i][j]是從a1,1到ai,j的路徑上的數的最大和，并且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基礎題：數塔，基礎講過，路徑只能從左上方和上方過來。

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

1.

概述：基礎題，大家模擬即可，可以帶入幾組數據執行。例如：

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)當程序執行到第16行時，若ans-i>2，則a[i+1]≦a[i]。( )

答案：√

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

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

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

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

答案：D

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

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

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

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

答案：A

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

2.

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

判斷題

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表示集合數量。

選擇題

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函數沒有路徑壓縮，單次查找最壞為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數組和suf數組的內容。Pre數組保存的是前面匹配了多少個字符，suf保存的是從后面比較匹配了多少個字符。ans是匹配字符之間的距離最大值。

例如 abca ac

判斷題

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

答案：√

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

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

答案：×

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

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

答案：×

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

4 (2分)當t時s的子序列時，pre數組和suf數組滿足：對任意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.(匠人的自我修養)一個匠人決定要學習n個新技術，要想成功學習一個新技術，他不僅要擁有一定的經驗值，而且還必須要先學會若干個相關的技術。學會一個新技術之后，他的經驗值會增加一個對應的值。給定每個技術的學習條件和習得后獲得的經驗值，給定他已有的經驗值，請問他最多能學會多少個新技術。

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

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

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

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

分析：學技術有先后，經驗值還得夠，根據已有的經驗值選擇新技術，也可以用有向圖分析理解。可以用二維數組實現。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

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

3) ③處應填( )

A. target = -1

B. --cnt[target]

C. bbonus[target]

D. points += bonus[target]

答案：D

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

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

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

5) ⑤處應填( )

A. unlock[i] = cnt[i]

B. unlock[i] =m

C. unlock[i] = 0

D. unlock[i] =-1

答案：B

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

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

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

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

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

提示：

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

status是勝負狀態的二進制壓縮，trans是狀態轉移的二進制壓縮。

試補全程序。

代碼說明:

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

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

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

題目分析：博弈論類的問題，講過。位運算，考前專門復習過。題目里說了，用動態規劃實現，并且用位運算代替數組實現。

1)①處應填( )

A.0

B .~0ull

C.~0ull^1

D.1

答案：C

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

2)處應填( )

A.a[j]< i

B.a[j]==i

C.a[j] !=i

D.a[j] >i

答案：B

題目分析：n個條件范圍內，符合題目要求的石子個數，即可發生狀態轉移，選B。并且根據代碼，狀態轉移到trans變量。增加狀態，位運算|實現加的功能，下一個選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的值。先手必勝，對當前狀態和以前狀態做判斷。

5)⑤處應填( )

A. trans = status | trans ^win

B. status = trans >> 1^win

C. trans = status ^trans |win

D. status =status <<1^win

答案：D

更新status狀態值，將當前win值記錄到status中。

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

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

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