2019 信息學(xué)奧賽普及組第一輪測(cè)試

1、2019 信息學(xué)奧賽普及組第一輪測(cè)試2019 CCF 非專業(yè)級(jí)別軟件能力認(rèn)證第一輪（CSP-J）入門級(jí) C+ 語言試題A卷認(rèn)證時(shí)間：2019年10月19日 14:3016:30 考生注意事項(xiàng)：·試題紙滿分100分，請(qǐng)?jiān)诖痤}紙上作答，在試題紙上的一律無效。·不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單選題，（共15題，每小題2分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）1. 中國(guó)的國(guó)家頂級(jí)域名是（     ） A. .cn(正確答案)B. .chC. .chnD. .china答案解析：網(wǎng)絡(luò)域名中，頂級(jí)國(guó)家

2、地區(qū)域名有.cn（中國(guó)）,.uk（英國(guó)）,.jp（日本）,.hk（香港）,.tw（臺(tái)灣）等，典型的通用頂級(jí)域名有.edu（教育）,.com(商業(yè)組織)，.net（網(wǎng)絡(luò)組織），.gov（政府機(jī)構(gòu)）,.org（非盈利組織）等。2. 二進(jìn)制數(shù)11 1011 1001 0111和01 0110 1110 1011進(jìn)行邏輯與運(yùn)算的結(jié)果是（   ）。 A. 01 0010 1000 1011B. 01 0010 1001 0011C. 01 0010 1000 0001D. 01 0010 1000 0011(正確答案)答案解析：按位運(yùn)算基本操作3.一個(gè)32位整型變量占用（）個(gè)字節(jié)。

3、A. 32B. 128C. 4(正確答案)D.8答案解析：8位是1字節(jié)，因此32位是4字節(jié)。在C+語言中，int是最常用的帶符號(hào)32位整型變量，可表示數(shù)值-231，231-1，unsigned int是最常用的無符號(hào)32位整型變量，可表示數(shù)值0，232-1。4若有如下程序段，其中s、a、b、c均已定義為整型變量，且a、c均已賦值(c大于0）s=afor(b = 1; b <= c; b+) s = s 1;則與上述程序段功能登記的賦值語句是(  ) A. s = a c;(正確答案)B. s = a b;C. s = s c;D. s = b c;答案解析：解析:s初始化為a，

4、緊接著for循環(huán)c次，每次s減1，因此該程序段相當(dāng)于s=a-c .5設(shè)有100個(gè)已排好序的數(shù)據(jù)元素，采用折半查找時(shí)，最大比較次數(shù)為（） A. 7(正確答案)B. 10C. 6D. 8答案解析：對(duì)100個(gè)有序元素進(jìn)行折半查找，每次查找可將檢索范圍縮小一半。由26-1<100<=27-1可知，最大比較次數(shù)為7。6.鏈表不具有的特點(diǎn)是（） A. 插入刪除不需要移動(dòng)元素B. 不必事先估計(jì)存儲(chǔ)空間C. 所需空間與線性表長(zhǎng)度成正比D. 可隨機(jī)訪問任一元素(正確答案)答案解析：鏈表是通過記錄每個(gè)元素的后繼位置來實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，所需空間與元素個(gè)數(shù)成正比，優(yōu)點(diǎn)是不必事先估計(jì)存儲(chǔ)空間、插入或刪除指定位置

5、元素的時(shí)間復(fù)雜度為O(1)但缺點(diǎn)是由于其元素的內(nèi)存地址不連續(xù)，無法進(jìn)行O(1)的隨機(jī)訪問。7. 把8個(gè)同樣的球放在5個(gè)同樣的袋子里，允許有的袋子空著不放，問共有多少種不同的分法?（  ）提示:如果8個(gè)球都放在一個(gè)袋子里，無論是哪個(gè)袋子，都只算同一種分法 A. 22B. 24C. 18(正確答案)D. 20答案解析：枚舉法求解，8個(gè)同樣的球分1個(gè)袋子共1種方案，分2個(gè)袋子共4種方案，分3個(gè)袋子共5種方案，分4個(gè)袋子共5種方案，分5個(gè)袋子共3種方案，合計(jì)18種。8.一棵二叉樹如右圖所示，若采用順序存儲(chǔ)結(jié)構(gòu)，即用一維數(shù)組元素存儲(chǔ)該二叉樹中的結(jié)點(diǎn)（根結(jié)點(diǎn)的下標(biāo)為1，若某結(jié)點(diǎn)的下標(biāo)為i，則其左

6、孩子位于下標(biāo)2i處、右孩子位于下標(biāo)2i+1處），則該數(shù)組的最大下標(biāo)至少為（）。 A. 6B. 10C. 15(正確答案)D. 12答案解析：根據(jù)題目給定的規(guī)則可知，下標(biāo)最大的結(jié)點(diǎn)為樹中深度最大且最靠右的結(jié)點(diǎn)，其下標(biāo)為(12+1)2+1)2+1=15。9. 100以內(nèi)最大的素?cái)?shù)是（） 。 A. 89B. 97(正確答案)C. 91D. 93答案解析：98-100均為合數(shù)，97為素?cái)?shù)。10.319和377的最大公約數(shù)是（）。 A.27B. 33C.29(正確答案)D.31答案解析：使用輾轉(zhuǎn)相除法可得GCD(319,377)=GCD(319,58)=GCD(58,29)=29?；?qū)蓴?shù)分解質(zhì)因數(shù)后，

7、提取公共部分亦可求解。11. 新學(xué)期開學(xué)了，小胖想減肥，健身教練給小胖制定了兩個(gè)訓(xùn)練方案。方案一:每次連續(xù)跑3公里可以消耗300千卡（耗時(shí)半小時(shí)）方案二:每次連續(xù)跑5公里可以消耗600千卡（耗時(shí)小時(shí)）。小胖每周周一到周四能抽出半小時(shí)跑步，周五到周日能抽出一小時(shí)跑步。另外，教練建議小胖每周最多跑21公里，否則會(huì)損傷膝蓋。請(qǐng)問如果小胖想嚴(yán)格執(zhí)行教練的訓(xùn)練方案，并且不想損傷膝蓋，每周最多通過跑步消耗多少千卡?( )    A.3000B.2500C.2400(正確答案)D.2520答案解析：設(shè)方案1執(zhí)行x天，方案2執(zhí)行y天，則有3x+5y<=21、x+y<=

8、7、y<=3。要求300x+600y的最大值，枚舉可得最優(yōu)方案為x=2、y=3，此時(shí)300x+600y為2400?；蚴褂镁€性規(guī)劃亦可求解。12.一副紙牌除掉大小王有52張牌，四種花色，每種花色13張。假設(shè)從這52張牌中隨機(jī)抽取13張紙牌，則至少(A)張牌的花色一致。 A. 4(正確答案)B. 2C. 3D. 5答案解析：最壞情況，13張牌對(duì)應(yīng)四種花色的牌數(shù)為3、3、3、4。13. 一些數(shù)字可以顛倒過來看，例如0、1、8顛倒過來還是本身，6顛倒過來是9，9顛倒過來看還是6，其他數(shù)字顛倒過來都不構(gòu)成數(shù)字。類似的，一些多位數(shù)也可以顛倒過來看，比如106顛倒過來是901。假設(shè)某個(gè)城市的車牌只由5

9、位數(shù)字組，每一位都可以取0到9。請(qǐng)問這個(gè)城市最多有多少個(gè)車牌倒過來恰好還是原來的車牌?（ ） A. 60B. 125C. 75(正確答案)D. 100答案解析：前2位有0、1、8、6、9共5種選擇，第3位只能放0、1、8，后2位由前2位決定，因此總方案數(shù)為55311=75。14.假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為（） 。 A. ABCDEFGHIJB. ABDEGHJCFI(正確答案)C. ABDEGJHCFID. ABDEGHJFIC答案解析：后序遍歷的規(guī)則是“左右根”、中序遍歷的規(guī)則是“左根右”，因此可知，A是樹根、D

10、BGEHJ是A左子樹的中序遍歷(對(duì)應(yīng)后續(xù)遍歷DGJHEB)、CIF是A右子樹的中序遍歷(對(duì)應(yīng)后續(xù)遍歷IFC)，遞歸畫出對(duì)應(yīng)的二叉樹，再根據(jù)前序遍歷規(guī)則“根左右”即可求出答案。15.以下哪個(gè)獎(jiǎng)項(xiàng)是計(jì)算機(jī)科學(xué)領(lǐng)域的最高獎(jiǎng)?（） A. 圖靈獎(jiǎng)(正確答案)B. 魯班獎(jiǎng)C. 諾貝爾獎(jiǎng)D. 普利策獎(jiǎng)答案解析：圖靈獎(jiǎng)由美國(guó)計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立，其名稱取自計(jì)算機(jī)科學(xué)之父圖靈，專門獎(jiǎng)勵(lì)對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人，被譽(yù)為“計(jì)算機(jī)界的諾貝爾獎(jiǎng)”。二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍;判斷題正確填，錯(cuò)誤填×除特殊說明外，判斷題1.5分，選擇題4分，共計(jì)40分)程序一：· 判

11、斷題1)輸入的字符串只能由小寫字母或大寫字母組成。（） 對(duì)錯(cuò)(正確答案)答案解析：輸入的字符串也可以包含數(shù)字等其他字符。2)若將第8行的“i = 1”改為“i = 0”，程序運(yùn)行時(shí)會(huì)發(fā)生錯(cuò)誤。() A. 對(duì)(正確答案)B. 錯(cuò)答案解析：若i可以為0，則第9行的if 語句條件“n%i=O”將發(fā)生運(yùn)行時(shí)錯(cuò)誤RE。3)若將第8行的“i <= n”改為“i i <= n”，程序運(yùn)行結(jié)果不會(huì)改變。() A. 對(duì)B. 錯(cuò)(正確答案)答案解析：當(dāng)?shù)?行的循環(huán)條件為“i<=n”時(shí)，字符串的末尾字符會(huì)被程序加工，但若改為“ii&lt;=n”，字符串的末尾字符將不會(huì)被程序加工(除非字符串

12、長(zhǎng)度為1)。4)若輸入的字符串全部由大寫字母組成，那么輸出的字符串就跟輸入的字符串一樣。() A. 對(duì)B. 錯(cuò)(正確答案)答案解析：大寫字母的ASCII 編碼值小于小寫字母的。若輸入的字符串全部由大寫字母組成，則程序不會(huì)對(duì)其進(jìn)行加工。· 選擇題5)若輸入的字符串長(zhǎng)度為18，那么輸入的字符串跟輸出的字符串相比，至多有（）個(gè)字符不同。 A.18B.6(正確答案)C.10D.1答案解析：18的正約數(shù)共有6個(gè)，因此程序至多修改輸入字符串中的6個(gè)字符，即輸出字符串與輸入字符串至多有6個(gè)字符不同。6)若輸入的字符串長(zhǎng)度為（），那么輸入的字符串跟輸出的字符串相比，至多有36個(gè)字符不同。 A.36B

13、.100000(正確答案)C.1D.128答案解析：根據(jù)程序的作用可知，要使輸出字符串和輸入字符串之間至多有36個(gè)字符不同，36應(yīng)當(dāng)是字符串長(zhǎng)度n的約數(shù)個(gè)數(shù)。本題選項(xiàng)中，僅有100000滿足要求，將其分解質(zhì)因數(shù)得100000=2555，得其的正約數(shù)共有(5+1)(5+1)=36個(gè)。程序二假設(shè)輸入的n和m都是正整數(shù)，x和y都是在1，n的范圍內(nèi)的整數(shù)，完成下面的判斷題和單選題:· 判斷題1) 當(dāng)m>0時(shí)，輸出的值一定小于2n。（） A. 對(duì)(正確答案)B. 錯(cuò)答案解析：由限定條件0<x, y<=n可知，當(dāng)m>O時(shí)，一定存在某個(gè)數(shù)對(duì)被我們選中，此時(shí)ans<2n

14、2)執(zhí)行完第27行的“+ans”時(shí)，ans一定是偶數(shù)。（） A對(duì)B錯(cuò)(正確答案)答案解析：由于數(shù)對(duì)是一個(gè)左值與一個(gè)右值相匹配，因此ans最終一定是偶數(shù)。但第27行的“+ans”在第23行的for循環(huán)的內(nèi)部，其中間結(jié)果可能為奇數(shù)。3) ai和bi不可能同時(shí)大于0。（） A. 對(duì)B. 錯(cuò)(正確答案)答案解析：ai用于記錄與左值i相匹配的右值，不存在則為0; bi用于記錄與右值i相匹配的左值，不存在則為0。當(dāng)存在數(shù)對(duì)(i, y)和(x,i)都被我們選中時(shí)，ai和bi就會(huì)同時(shí)大于0。4)若程序執(zhí)行到第13行時(shí)，x總是小于y，那么第15行不會(huì)被執(zhí)行。() A. 對(duì)B. 錯(cuò)(正確答案)答案解析：存在反例依

15、次考慮數(shù)對(duì)(1,2)(1,3)時(shí)，第15行程序會(huì)被執(zhí)行。· 選擇題5)若m個(gè)x兩兩不同，且m個(gè)y兩兩不同，則輸出的值為（） A.2n-2m(正確答案)B.2n+2C.2n-2D.2n答案解析：此時(shí)，輸入的數(shù)對(duì)兩兩互不沖突，因此程序會(huì)將它們?nèi)窟x中，根據(jù)上述ans的意義可知，其結(jié)果為2n-2m。6)若m個(gè)x兩兩不同，且m個(gè)y都相等，則輸出的值為（） A.2n-2(正確答案)B.2nC.2mD.2n-2m答案解析：此時(shí)，輸入的數(shù)對(duì)兩兩存在沖突，因此程序最終只會(huì)選用一個(gè)數(shù)對(duì)，根據(jù)上述ans的意義可知，其結(jié)果為2n-2。程序三· 判斷題1)如果a數(shù)組有重復(fù)的數(shù)字，則程序運(yùn)行時(shí)會(huì)發(fā)生

16、錯(cuò)誤。（） A. 對(duì)B. 錯(cuò)(正確答案)答案解析：若a數(shù)組有重復(fù)數(shù)字，則程序在根據(jù)a數(shù)組遞歸構(gòu)造符合要求的二叉樹時(shí)，對(duì)于相同結(jié)點(diǎn)值，會(huì)優(yōu)先考慮位于左側(cè)的。2)如果b數(shù)組全為0，則輸出為0。（） A. 對(duì)(正確答案)B. 錯(cuò)答案解析：程序最終輸出的是各結(jié)點(diǎn)深度與b值的加權(quán)和，因此若b數(shù)組全為0，則加權(quán)和顯然為0。· 選擇題3)當(dāng)n=100時(shí)，最壞情況下，與第12行的比較運(yùn)算執(zhí)行的次數(shù)最接近的是:（）。 A.5000(正確答案)B. 600c.6D.100答案解析：最壞情況下，程序所構(gòu)造的二叉樹的每個(gè)結(jié)點(diǎn)至多僅有一個(gè)子結(jié)點(diǎn)，此時(shí)，程序?qū)⑦f歸100層，其中第i層進(jìn)行100-i+1次第12行

17、的比較運(yùn)算，總執(zhí)行次數(shù)為100+99+98+15000。4)當(dāng)n=100時(shí)，最好情況下，與第12行的比較運(yùn)算執(zhí)行的次數(shù)最接近的是:（）。 A.100B.6C.5000D.600(正確答案)答案解析：最佳情況下，程序構(gòu)造二叉樹時(shí)，對(duì)于每個(gè)結(jié)點(diǎn)會(huì)盡可能均分其左右子樹。定義根結(jié)點(diǎn)深度為1，則含n=100個(gè)結(jié)點(diǎn)的樹的深度最小為logn7，此時(shí)每選定一層結(jié)點(diǎn)，程序都需要執(zhí)行約n次的第12行的比較運(yùn)算，因此總執(zhí)行次數(shù)約為nlogn600。5)當(dāng)n=10時(shí)，若b數(shù)組滿足，對(duì)任意0i<n，都有bi= i1，那么輸出最大為（）。 A.386B.383C.384D.385(正確答案)答案解析：此時(shí)，要使輸出

18、的ans值盡可能大，程序所構(gòu)造的二叉樹的深度應(yīng)盡可能地大。定義根結(jié)點(diǎn)深度為1，則含10個(gè)結(jié)點(diǎn)的二叉樹的最大深度為10，因此 ans的最大值為11+22+33+1010=385。6)(4分)當(dāng)n=100時(shí)，若b數(shù)組滿足，對(duì)任意0i<n，都有bi=1，那么輸出最小為（） 。 A.582B.580(正確答案)C.579D.581答案解析：此時(shí)，要使輸出的ans值盡可能小，程序應(yīng)參照完全二叉樹構(gòu)造此樹，其中深度為1的結(jié)點(diǎn)共1個(gè)，深度為2的結(jié)點(diǎn)共2個(gè)，深度為3的結(jié)點(diǎn)共4個(gè)深度為6的結(jié)點(diǎn)共32個(gè)，剩余37個(gè)結(jié)點(diǎn)的深度為7，因此ans的最小值為(11+22+34+632)+737=580。三、完善程序

19、（單選題，每題3分，共計(jì)30分）程序一1.（矩陣變幻）有一個(gè)奇幻的矩陣，在不停的變幻，其變幻方式為:數(shù)字0變輸入一行一個(gè)不超過10的正整數(shù)n。輸出變幻n次后的矩陣。試補(bǔ)全程序。提示:“<<”表示二進(jìn)制左移運(yùn)算符，例如(11)2<<2=(1100)2;而“”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)中的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為0，反之為1。1)處應(yīng)填（） A.n % 2B.0C.t(正確答案)D.1答案解析：此處為遞歸邊界，當(dāng)需要計(jì)算的是單位矩陣時(shí)，相應(yīng)元素應(yīng)賦值為t，即無需再經(jīng)任何變換。2)處應(yīng)填（） A.x - s

20、tep, y - stepB.x,y - stepC.x - step, yD.x,y(正確答案)答案解析：左上角(x, y)，且大小2n2n的矩陣，可以分成4個(gè)2n-12n-1的矩陣分別計(jì)算。此處需要計(jì)算的是4個(gè)矩陣中位于左上方的矩陣，該矩陣的左上角坐標(biāo)為(x, y)。3)處應(yīng)填（） A.x - step, y - stepB.× + step, y + step(正確答案)D.x, y - stepC.x - step, y答案解析：左上角(x, y)，且大小2n2n的矩陣，可以分成4個(gè)2n-12n-1的矩陣分別計(jì)算。此處需要計(jì)算的是4個(gè)矩陣中位于右下方的矩陣，該矩陣的左上角坐標(biāo)

21、為(x+2n-1, y+2n-1)。4)處應(yīng)填（） A.n - 1，n % 2B.n, 0(正確答案)c.n, n % 2D.n - 1，0答案解析：此處是遞歸計(jì)算的入口，即題目最終所求的是大小2n2n，由單個(gè)數(shù)字0變幻而來的矩陣，因此遞歸函數(shù)的后兩個(gè)參數(shù)應(yīng)設(shè)為n和0。5)處應(yīng)填（） A.1 << (n +1)B.1 << n(正確答案)C.n +1D.1 << (n - 1)答案解析：此處是計(jì)算最終所求的矩陣大小，即邊長(zhǎng)size為2n，位運(yùn)算寫做“1<<n”。程序二2.（計(jì)數(shù)排序）計(jì)數(shù)排序是一個(gè)廣泛使用的排序方法。下面的程序使用雙關(guān)鍵字計(jì)數(shù)排序，將n對(duì)10000以內(nèi)的整數(shù)，從小到大排序。例如有三對(duì)整數(shù)（3,4）、（2,4)、（3,3），那么排序之后應(yīng)該是（2,4）、(3,3) 、(3,4)。輸入第一行為n，接下來n行，第i行有兩個(gè)數(shù)ai和bi，分別表示第i對(duì)整數(shù)的第一關(guān)鍵字和第二關(guān)鍵字。從小到大排序后輸出。數(shù)據(jù)范圍1n 107,1ai,bi104。提示:應(yīng)先對(duì)第二關(guān)鍵字排序，再對(duì)第一關(guān)鍵字排序。數(shù)組ord存儲(chǔ)第二關(guān)鍵字排序的結(jié)果，數(shù)組res存儲(chǔ)雙關(guān)鍵字排序的結(jié)果。試補(bǔ)