CCF 2022 初賽——CSP-J閱讀程序1解析

白二娃

中國計算機學會（CCF）推出的CSP認證（Certified Softwmare Professional Junior/Senior，非專業軟件能力認證，簡稱CSP-J/S），目的是評價計算機專業人士或準專業人士計算機科學的基礎能力——算法和編程能力。CSP-J面向初中以下，CSP-S面向高中生。進入CSP-J復賽獲獎有助于升入更好的中學。

自2020年以來全國青少年信息學奧林匹克聯賽（NOIP）僅面向高中生，CSP代替了NOIP的位置。升級路線就成了CSP-J/S初賽→CSP-J/S復賽→全國青少年信息學奧林匹克聯賽（NOIP）→省內選拔（省選）→全國青少年信息學奧林匹克競賽 （NOI國賽）。

全國青少年信息學奧林匹克競賽（NOI），是全國最高水平的信息學大賽。所有選手前50名將參加國家集訓隊，集訓隊隊員可以獲得保送、自主招生、降檔錄取等政策優待。

集訓隊選出5名隊員組成國家隊，參加亞太信息學奧林匹克（APIO）、國際信息學奧林匹克競賽（IOI）為國爭光。

參加CSP與學習少兒編程是有一些區別的，CSP的學習目的是競賽和升學，學習的內容是系統的計算機知識，選用的是大學教材，將大學計算機專業課程里面基礎性的和思維性的，下沉到青少年階段進行學習。信息學競賽相對于數學競賽的數學要求要低一些，對數學天分的要求相對較低，適合思維靈活、動手能力強，有較好編程基礎學生從初中開始正式學習，到高一開始正式參賽到高三獲獎，幫助升學。而少兒編程的學習更多是以培養編程思維和編程能力為目標。

我們已經在第39期完成了第一部分的選擇題，下面進入第二部分難度更高的閱讀程序題。

本次考試的閱讀程序題難度高于第三大題的完善程序題，同學們在實際考試時可以先做第三部分完善程序。

今天來分析閱讀程序的第一題，該題含有6小問

閱讀程序（程序輸入不超過數組或字符串定義的范圍;判斷題正確填√，錯誤填×;除特殊說明外，判斷題1.5分，選擇題3分，共計40分）

假設輸入的x、y均是不超過15的自然數，完成下面的判斷題和單選題。

16. 刪去第7行與第13行的unsigned，程序行為不變。（ ）

17. 將第7行與第13行的short均改為char，程序行為不變。（ ）

18. 程序總是輸出一個整數“0”。（ ）

19. 當輸入為“2 2”時，輸出為“10”。（ ）

20. 當輸入為“2 2”時，輸出為“59”。（ ）

21. 當輸入為“13 8”時，輸出為（ ）

A.“0” B.“209” C.“197” D.“226”

本題主要考查位運算，要求掌握C++的6個位操作運算符的基本知識，并能讀懂代碼。這道題有兩種解法。

第一是筆算，因為數據最大的是13和8，計算量不算太大，筆算可以出結果。

第二種是用dcba和DCBA代替4位的x、y，根據程序得到規律性的結果是DdCcBbAa，然后去計算題目要求的2 2和13 8。

位運算是指按二進制進行的運算。在系統軟件中，常常需要處理二進制位的問題。C語言提供了6個位操作運算符。這些運算符只能用于整型操作數，即只能用于帶符號或無符號的char、short、int與long類型。這里的與、或、非與邏輯運算的規則一致，需要將對象轉換為二進制后按位進行運算，如下表。

本題中用到了左移<<、右移>>、按位與&、按位或|，4個位運算符。

按位與&：參加運算的兩個數據，按二進制位進行“與”運算。如果兩個相應的二進制位都為1，則該位的結果值為1;否則為0。

按位或|：兩個相應的二進制位中只要有一個為1，該位的結果值為1。借用邏輯學中或運算的話來說就是，一真為真。

左移<<：左移運算符是用來將一個數的各二進制位左移若干位，移動的位數由右操作數指定（右操作數必須是非負值），其右邊空出的位用0填補，高位左移溢出則舍棄該高位。例如15<<2，即00001111（2），左移2位得00111100（2）。

右移>>：右移運算符是用來將一個數的各二進制位右移若干位，移動的位數由右操作數指定（右操作數必須是非負值），移到右端的低位被舍棄，對于無符號數，高位補0。對于有符號數，某些機器將對左邊空出的部分用符號位填補（即“算術移位”），如果原來符號位為0（該數為正），則左邊也是移入0。如果符號位原來為1（即負數），則左邊移入的是1。而另一些機器則對左邊空出的部分用0填補（即“邏輯移位”）。這取決于所用的計算機系統。本題中由于數字不超過15，所以不會產生影響。

首先注意到程序第7行：unsigned short x，y;

unsigned 表示無符號整型數據類型取值范圍是大于等于0的整數。數據類型包括：字符型（char）、整形（short、int、long）、浮點型（float， double），字節數如下表。說明xy是2個字節的非負整數，2個字節16位。

題目給出了x、y均不超過15，15轉為二進制為1111（2），因此x和y的二進制最多4位。

解法一就是將2、2帶入硬算。

從代碼第9行 x = （x | x << 2） & 0x33; 開始計算。2轉為二進制00000010。0x33為十六進制轉為二進制00110011。計算結果為00000010，十進制2。

結果00000010帶入第10行。0x55為十六進制轉為二進制01010101。結果為00000100，十進制4。

y也是2，代碼11和12行運算結果一樣為00000010，十進制為2。

結果帶入代碼13行，計算結果z=00001100，十進制為12。所以19和20題都應該是錯誤的。

解法二是用代數的方法找到適用于各種情況的規律。根據題意最大為15，占用4位，用dcba代替x，用DCBA代替y。

帶入代碼9行運算，（d|b）表示這一位是db的或運算結果，在和0x33進行與運算之后結果必然是0。這樣x的二進制就從原來的dcba變成了dc00ba。

帶入第10行x = （x | x << 1） & 0x55;計算。結果變成0d0c0b0a。

把y設為DCBA，經過同樣的計算，11、12行最終結果為0D0C0B0

A。那么13行的結果如圖，Z=DdCcBbAa。

16. 刪去第7行與第13行的unsigned，程序行為不變。（√）

解析：unsigned short占16位，刪掉unsigned以后只要能保證在非符號位的后15位以內進行操作都沒問題。通過上述分析可以看到z的位數最多是8位，沒有超過15位。因此程序行為不變。

17. 將第7行與第13行的short均改為char，程序行為不變。（×）

解析︰這題的重點不在13行，而是在14行。改為字符型之后，cout<<z;會因為z是char類型而輸出字符，不再輸出整數。

18. 程序總是輸出一個整數“0”。（×）

解析：通過上述分析可以看到如果x是dcba，y是DCBA，那么z是DdCcBbAa，并不是0。

19. 當輸入為“2 2”時，輸出為“10”。（×）

20. 當輸入為“2 2”時，輸出為“59”。（×）

當輸入為“2 2”時，我們筆算的結果為12。

再用z是DdCcBbAa來驗算一下，x：0010，y：0010。帶入得到z：00001100，即12，說明我們得到的規律正確。所以兩題都打叉。

21.當輸入為“13 8”時，輸出為（B）

A.“0” B.“209” C.“197” D.“226”

可以重復用筆算的方法，但有了之前總結的規律能更快得到結果。x=13=1101，y=8=1000。z=DdCcBbAa=11010001（下劃線的數字來自y）。二進制轉十進制結果為209，選B。

小結，跟隨我們的解題思路完成這道題之后你有什么感覺？這些題對于小學生、初中生來說難度很高了。

說信奧賽簡單也只是相對于數理化奧賽來說的，每一位能獲得高校青睞的選手都是萬里挑一，天分、特長、恒心、經濟實力缺一不可。所以要慎重選擇競賽這條路，如果不是真有頂尖的實力，還不如選擇學習普通編程為將來的學習和生活提供有效的幫助。