2021 CCF非專業級別軟體能力認證第一輪
中山市認證點：中山市紀念中學
（CSP-J）入門級C++語言試題
認證時間：2021年9月19日14:30-16:30
一、單項選擇題（共15題，每題2分，共計30分：每題有且僅有一個正確選項）
1. 以下不屬於面向對象程序設計語言的是（D）。
A. C++
B. Python
C. Java
D. C
2. 以下獎頊與計算機領域最相關的是（B）。
A. 奧斯卡獎
B. 圖靈獎
C. 諾貝爾獎
D. 普立茲獎
3. 目前主流的計算機儲存數據最終都是轉換成（A）數據進行存儲。
A. 二進位
B. 十進位
C. 八進位
D. 十六進位
4. 以比較作為基本運算，在N個數中找出最大數，最壞情況下所需要的最少的比較次數為（C）。
A. N^2
B. N
C. N-1
D. N+1
5. 對於入棧順序為a,b,c,d,e的序列，下列（D）不是合法的出棧序列。
A. a,b,c,d,e
B. e,d,c,b,a
C. b,a,c,d,e
D. c,d,a,e,b
6. 對於有n個頂點、m條邊的無向聯通圖（m>n）,需要刪掉（D）條邊才能使其成為一棵樹。
A. n-1
B. m-n
C. m-n-1
D. m-n+1
7. 二進位數101.11對應的十進位數是（C）。
A. 6.5
B. 5.5
C. 5.75
D. 5.25
8. 如果一棵二叉樹只有根結點，那麼這棵二叉樹高度為1。請問高度為5的完全二叉樹有（A）種不同形態？
A. 16
B. 15
C. 17
D. 32
9. 表達式a*(b+c)*d的後綴表達式為（B），,其中」*」和」+」是運算符。
A. **a+bcd
B. abc+*d*
C. abc+d**
D. *a*+bcd
10. 6個人，兩個人組一隊，總共組成三隻，不區分隊伍的編號，不同的組隊情況有（B）種。
A. 10
B. 15
C. 30
D. 20
11. 在數據壓縮編碼中的哈夫曼編碼方法，在本質是一種（B）的策略。
A. 枚舉
B. 貪心
C. 遞歸
D. 動態規劃
12. 由1, 1, 2, 2, 3這五個數字組成不同的三位數有（A）種。
A. 18
B. 15
C. 12
D. 24
13. 考慮如下遞歸算法
solve(n)
if n<=1 return 1
else if n>=5 return n*solve(n-2)
else return n*solve(n-1)
則調用solve(7)得到的返回結果為（C）。
A. 105
B. 840
C. 210
D. 420
14. 以a為起點，對右邊的無向圖進行深度優先遍歷，則b、c、d、e四個點中有可能作為最後一個遍歷到的點個數為（B）。
A. 1
B. 2
C. 3
D. 4
15. 有四個人要從A點做一條船過河到B點，船一開始在A點。該船一次最多可坐兩個人。已知這四個人中每個人獨自坐船的過河時間分別為1, 2, 4, 8, 且兩個人坐船的過河時間為兩人獨自過河時間的較大者。則最短（B）時間可以讓四個人都過河到B點（包括從B點把船開回A點時間）。
A. 14
B. 15
C. 16
D. 17
二、閱讀程序（程序輸入不超過數組或字符串定義的範圍；判斷題正確填 √，錯誤填X；除特殊說明外，判斷題1.5分，選擇題3分，共計40分）
(1)
判斷題
16. 輸入的n等於1001時，程序不會發生下標越界。（X）
17. 輸入的a[i]必須全為正整數，否則程序將陷入死循環。（X）
18. 當輸入」5 2 11 9 16 10」時，輸出為」3 4 3 17 5」 。（X）
19. 當輸入為」1 511998「時，輸出為」18」 。（√）
20. 將原始碼中g函數的定義（13-16行）移到main函數的後面，程序可以正常編譯運行。（X）
單選題
21. 當輸入為」2 -65536 2147483647」時，輸出為（B）。
A. "65532 33」
B. "65552 32"
C. "65535 34"
D. "65554 33"
(2)
判斷題
22. 輸出的第二行一定是由小寫字母、大寫字母、數字和「+」、「/」、「=」構成的字符串。（X）
23. 可能存在輸入不同，但輸出的第二行相同的情形。（√）
24. 輸出的第一行為「-1」。（ √）
單選題
25. 設輸入字符串長度為n，decode函數的時間複雜度為（B）。
A. θ(√n)
B. θ(n)
C. θ(nlogn)
D. θ(n^2)
26. 當輸入為「Y3Nx」時，輸出的第二行為（B）。
A. 「csp」
B. 「csq」
C. 「CSP」
D. 「Csp」
27. （3.5分）當輸入為「Y2NmIDIwMjE=」時，輸出的第二行為（C）。
A. 「ccf2021」
B. 「ccf2022」
C. 「ccf 2021」
D. 「ccf 2022」
(3)
假設輸入的x是不超過1000的自然數，完成下面的判斷題和單選題：
判斷題
28. 若輸入不為"1"，把第12行刪去不會影響輸出的結果。（√）
29. （2分）第24行的" f[i]/c[i*k]"可能存在無法整除而向下取整的情況。（X）
30. （2分）在執行完init()後，f數組不是單調遞增的，但g數組是單調遞增的。（X）
單選題
31. init函數的時間複雜度為（A）。
A. θ(n)
B. θ(nlogn)
C. θ(n√n)
D. θ(n^2)
32. 在執行完init()後，f[1], f[2], f[3] ...... f[100]中有（C）個等於2。
A. 23
B. 24
C. 25
D. 26
33. （4分）當輸入"1000"時，輸出為（C）。
A. "15 1340"
B. "15 2340"
C. "16 2340"
D. "16 1340"
三、完善程序（單選題，每小題3分，共計30分）
(1)（Josephus 問題）有 n 個人圍城一個圈，依次標號 0 至 n-1。從 0 號開始，依次 0, 1, 0, 1, ... 交替報數，報到 1 的人會離開，直至圈中只剩下一個人。求最後剩下人的編號。
試補全模擬程序。
34. ①處應填（D）
A. i < n
B. c < n
C. i < n - 1
D. c < n - 1
35. ②處應填（C）
A. i % 2 == 0
B. i % 2 == 1
C. p
D. !p
36. ③處應填（C）
A. i++
B. i = (i + 1) % n
C. c++
D. p ^= 1
37. ④處應填（D）
A. i++
B. i = (i + 1) % n
C. c++
D. p ^= 1
38. ⑤處應填（B）
A. i++
B. i = (i + 1) % n
C. c++
D. p ^= 1
(2)（矩形計數）平面上有n個關鍵點，求有多少個四條邊都和x軸或者y軸平行的矩形，滿足四個頂點都是關鍵點。給出的關鍵點可能有重複，但完全重合的矩形只計一次。
試補全枚舉算法。
39. ①處應填（B）
A. a.x != b.x ? a.x < b.x : a.id < b.id
B. a.x != b.x ? a.x < b.x : a.y < b.y
C. equals(a,b) ? a.id < b.id : a.x < b.x
D. equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)
40. ②處應填（D）
A. i == 0 || cmp(A[i], A[i - 1])
B. t == 0 || equals(A[i], A[t - 1])
C. i == 0 || !cmp(A[i], A[i - 1])
D. t == 0 || !equals(A[i], A[t - 1])
41. ③處應填（C）
A. b - (b - a) / 2 + 1
B. (a + b + 1) >> 1
C. (a + b) >> 1
D. a + (b - a + 1) / 2
42. ④處應填（B）
A. !cmp(A[mid], p)
B. cmp(A[mid], p)
C. cmp(p, A[mid])
D. !cmp(p, A[mid])
43. ⑤處應填（D）
A. A[i].x == A[j].x
B. A[i].id < A[j].id
C. A[i].x == A[j].x && A[i].id < A[j].id
D. A[i].x < A[j].x && A[i].y < A[j].y
（CSP-S）提高級C++語言試題
認證時間：2021年9月19日09:30-11:30