CSP-J 2020 入門級 第一輪（初賽） 答案及解析

1. 在內存儲器中每個存儲單元都被賦予一個唯一的序號，稱為（）。
   A. 地址
   B. 序號
   C. 下標
   D. 編號

答: A
計算機中每個存儲單元都是1字節，都有唯一的地址。

2. 編譯器的主要功能是（ ）。
   A. 將源程序翻譯成機器指令代碼
   B. 將源程序重新組合
   C. 將低級語言翻譯成高級語言
   D. 將一種高級語言翻譯成另一種高級語言

答: A
源程序是高級語言程序，如C++程序代碼、Java程序代碼。
編譯器將源程序翻譯成的是機器語言，也就是機器指令代碼。因此選A。
將源程序重新組合的是連接器。
將低級語言翻譯成高級語言的是反編譯器。
將一種高級語言翻譯成另一種高級語言的是轉譯器。

3. 設x=true,y=true,z=false，以下邏輯運算表達式值為真的是（ ）。
   A. (y∨z)∧x∧z
   B. x∧(z∨y)∧z
   C. (x∧y)∧z
   D. (x∧y)∨(z∨x)

答: D
A選項中最后有∧z，z為false，無論前面表達式的值為什么，任何值∧false的結果都為false，因此A的值為false。
B選項最后也有∧z，z為false，因此B的值為false。
C選項最后也有∧z，z為false，因此C的值為false。
D選項，x∧y值為true, z∨x值為true，true∨true結果為true，選D。

4. 現有一張分辨率為2048×1024像素的32位真彩色圖像。請問要存儲這張圖像，需要多大的存儲空間？（ ）。
   A. 16MB
   B. 4MB
   C. 8MB
   D. 2MB

答: C
已知存儲空間單位之間的關系
$1B=8b$
$1KB=1024B=2^{10}B$
$1MB=1024KB=2^{10}KB$
每個像素為32位，由于1字節=8位，32位即為4字節。
該圖像占用空間$2048?1024?4B=2^{11}?2^{10}?2^2=2^{23}B=2^{13}KB=2^{3}MB=8MB$。

5. 冒泡排序算法的偽代碼如下：
   輸入：數組L, n ≥ k。輸出：按非遞減順序排序的 L。
   算法 BubbleSort：

   1. FLAG ← n //標記被交換的最后元素位置2. while FLAG > 1 do3.     k ← FLAG -14.     FLAG ← 15.     for j=1 to k do6.         if L(j) > L(j+1) then do7.              L(j)  ? L(j+1)8.              FLAG ← j

對n個數用以上冒泡排序算法進行排序，最少需要比較多少次?（ ）。
A. $n^2$
B. $n?2$
C. $n?1$
D. $n$

答: C
該算法對冒泡排序做了優化，flag是上一次冒泡過程中，最后一次交換的數對的第一個數的位置。
因此在下一次進行冒泡排序前，可以保證從位置flag到位置n的元素都已經排好序了。
如果flag為1，則整個序列已經有序，排序結束。
否則進入while循環，由于從第flag個數到第n個數已經有序了，設k為flag-1，只需要對第1到第k個數進行排序。所以接下來j從1到k循環。
這是一趟冒泡過程，只要第j個數大于第j+1個數，二者交換。flag初值設為1，在冒泡過程中只要第j和第j+1個數，發生交換，將flag設為發生交換的數對中第一個數的位置。
該優化可以使得當數列接近有序時，減少冒泡過程中交換元素的次數。
當初始序列就是非遞減序列時，k被設為flag-1，也就是n-1。進入while循環，flag被設為1，接下來的for循環中，總共執行k次循環，也就是執行了$n?1$次比較。沒有任何一個位置j滿足L(j) > L(j+1)，flag的值還是1。下一次循環時，不滿足flag>1，跳出。
因此比較次數最少時，比較了$n?1次$

6. 設A是n個實數的數組，考慮下面的遞歸算法：

XYZ (A[1..n])if n=1 then return A[1]else temp ← XYZ (A[1..n-1])if temp < A[n]then return tempelse return A[n]

請問算法 XYZ 的輸出是什么？（）。
A. A 數組的平均
B. A 數組的最小值
C. A 數組的中值
D. A 數組的最大值

答: B
XYZ函數傳入一個數組A，下標1到n。
當n不為1時，使用XYZ處理A數組下標1到n-1，返回值為temp。接下來返回temp和A[n]的較小值。
不斷進行遞歸調用，縮小問題規模，直到n為1時，返回A[1]。
XYZ(A[1…2])這一次調用中，返回值temp為A[1]，A[n]為A[2]，返回的是A[1]和A[2]的較小值。
XYZ(A[1…3])這一次調用中，返回值temp為A[1…2]的最小值，A[n]為A[3]，求二者的最小值，返回的是A[1…3]的最小值小值。
依此類推，可知XYZ(A[1…n-1])返回值temp是A[1…n-1]的最小值，再和A[n]比較，返回的是A[1…n]的最小值，即A數組的最小值，選B。

7. 鏈表不具有的特點是（）。
   A. 可隨機訪問任一元素
   B. 不必事先估計存儲空間
   C. 插入刪除不需要移動元素
   D. 所需空間與線性表長度成正比

答: A
線性表是邏輯結構，鏈表是線性表的一種物理結構，是一種具體實現。另一種物理結構是順序表。
A. 隨機訪問指的是可以以$O(1)$復雜度取到線性表中的第i個元素，如果該線性表是順序表，是可以進行隨機訪問的。如果是鏈表，則必須從鏈表第1個頂點開始，通過第1個頂點找到第2個頂點，通過第2個頂點找到第3個頂點…重復執行直到找到第i個頂點，該過程的復雜度為$O(n)$，這樣的訪問過程不是隨機訪問。因此A是錯的，選A。
B. 如果實現的是動態鏈表，進行添加或插入結點時，從堆區動態申請內存空間。在進行刪除時，將申請的內存空間返還。這樣就不需要預估存儲空間。
C. 鏈表進行插入、刪除操作只需要改變結點之間的連接關系即可完成，復雜度為$O(1)$，不需要移動元素。而順序表進行插入、刪除操作需要移動元素。
D. 線性表的長度就是線性表中元素的數量。對于線性表中的每個元素，鏈表都要為其建立一個結點，每個結點占用內存空間大小相同。如果線性表中有n個元素，實際需要從內存申請n個結點的空間，所需空間與線性表長度是成正比的。

8. 有10個頂點的無向圖至少應該有（ ）條邊才能確保是一個連通圖。
   A. 9
   B. 10
   C. 11
   D. 12

答: A
連通圖邊最少時是一個樹（無環連通無向圖），樹有n個頂點時有n-1條邊。10個頂點的樹有9條邊，選A。

9. 二進制數1011轉換成十進制數是（ ）。
   A. 11
   B. 10
   C. 13
   D. 12

答: A
其它進制數字轉十進制的方法為按位權展開：$1?2^3+0?2^2+1?2^1+1?2^0=11$

10. 5個小朋友并排站成一列，其中有兩個小朋友是雙胞胎，如果要求這兩個雙胞胎必須相鄰，則有（）種不同排列方法?
    A. 48
    B. 36
    C. 24
    D. 72

答: A
捆綁法，將兩個雙胞胎小朋友“捆綁”在一起，形成一個元素，剩下每個小朋友是一個元素，共4個元素，先進行全排列，方案數為$P(4,4)$，這兩個小朋友內部的排列有$P(2,2)$種，根據乘法原理，最終有$P(4,4)?P(2,2)=4?3?2?1?2?1=48$種排列方法，選A。

11. 下圖中所使用的數據結構是（ )。
    
    A. 棧
    B. 隊列
    C. 二叉樹
    D. 哈希表

答: A
只在線性表的一端進行操作（包括插入、刪除，取數據）的數據結構是棧。

12. 獨根樹的高度為1。具有61個結點的完全二叉樹的高度為（ ）。
    A. 7
    B. 8
    C. 5
    D. 6

答: D
有n個結點的完全二叉樹的高度為$?{\log }_{2}n?+1$（原理見完全二叉樹的相關性質證明)
由于$32<61<64$
所以$2^5<61<2^6$
不等式取以2為底的對數
${\log }_2{2}^5<{\log }_{2}61<{\log }_2{2}^6$
$5<{\log }_{2}61<6$
$?{\log }_{2}61?+1=5+1=6$，選D。

13. 干支紀年法是中國傳統的紀年方法，由10個天干和12個地支組合成60個天干地支。由公歷年份可以根據以下公式和表格換算出對應的天干地支。
    

天干 =（公歷年份）除以10所得余數
地支 =（公歷年份）除以12所得余數
例如，今年是2020年，2020 除以10余數為0，查表為"庚”；
2020 除以12，余數為4，查表為“子” 所以今年是庚子年。
請問1949年的天干地支是（ ）
A. 己酉
B. 己亥
C. 己丑
D. 己卯

答: C
$1949\mathrm{mod}10=9$，查表為“己”
$1949\mathrm{mod}12=5$，查表為“丑”
所以1949年的天干地支是“己丑”，選C。

14. 10個三好學生名額分配到7個班級，每個班級至少有一個名額，一共有（ ）種不同的分配方案。
    A. 84
    B. 72
    C. 56
    D. 504

答: A
10個三好學生名額是完全相同的，將其分配到7個班級。這是將相同小球放入不同盒子的模型，可以使用插板法完成。
一共10個相同的小球放入7個不同的盒子，相當于把10個相同的小球放成一行，在10個小球之間的9個空隙中插入6個相同的板子，方案數為$C(9,6)=C(9,3)=(9?8?7)/(3?2?1)=84$，選A。

15. 有五副不同顏色的手套（共10只手套，每副手套左右手各1只），一次性從中取6只手套，請問恰好能配成兩副手套的不同取法有（ ）種。
    A. 120
    B. 180
    C. 150
    D. 30

答: A
方法1：6只手套中有兩副也就是4只手套完成了配對，還剩下2只手套無法完成配對。首先從5副手套中選擇2副完成配對的手套，有$C(5,2)$種情況，接下來要在3副手套中找兩只無法配對的手套：可以是兩只手套都是左手，或右手，有$2C(3,2)$種情況，或者兩只手套一只是左手，一只是右手。左手手套有3種選擇，左手手套確定后右手選與左手手套不是一副的手套有2種選擇，因此有$3?2$種，因此總取法有$C(5,2)?(2C(3,2)+3?2)=(5?4)/2?(2?3+3?2)=10?12=120$，選A。
方法2：使用補集轉化思路，首先在5副手套中選擇2副完成配對的手套，有$C(5,2)$種情況，而后要在3副手套中選出2只手套無法完成配對，我們先考慮在3副手套共6只手套中選出2只手套的所有情況，共有$C(6,2)$種情況，從中減去兩只手套能配對的3種情況，剩下的就是不能配對的情況。總取法數為$C(5,2)?(C(6,2)?3)=(5?4)/2?(6?5/2?3)=10?12=120$

二、閱讀程序

閱讀程序(1)
閱讀程序(2)
閱讀程序(3)

三、完善程序

完善程序(1)
完善程序(2)