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

2019信息學(xué)奧賽普及組第一輪測試2019CCF非專業(yè)級(jí)別軟件能力認(rèn)證第一輪（CSP-J）入門級(jí)C++語言試題A卷

認(rèn)證時(shí)間：2019年10月19日14:30~16:30考生注意事項(xiàng)：?試題紙滿分100分，請?jiān)诖痤}紙上作答，在試題紙上的一律無效。?不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單選題，（共15題，每小題2分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）中國的國家頂級(jí)域名是（）.cn（正確答案）.ch.chn.china答案解析：網(wǎng)絡(luò)域名中，頂級(jí)國家\地區(qū)域名有.cn（中國），.uk（英國），.jp（日本），.hk（香港），.tw（臺(tái)灣）等，典型的通用頂級(jí)域名有.edu（教育）,.com（商業(yè)組織），.net（網(wǎng)絡(luò)組織），.gov（政府機(jī)構(gòu)）,.org（非盈利組織）等。二進(jìn)制數(shù)11101110010111和01011011101011進(jìn)行邏輯與運(yùn)算的結(jié)果是（）。A.01001010001011B.01001010010011C.01001010000001D.01001010000011（正確答案）答案解析：按位運(yùn)算基本操作一個(gè)32位整型變量占用（）個(gè)字節(jié)。32128C.4（正確答案）D.8答案解析：8位是1字節(jié)，因此32位是4字節(jié)。在C++語言中，int是最常用的帶符號(hào)32位整型變量，可表示數(shù)值［-2八31,2八31-1］,unsignedint是最常用的無符號(hào)32位整型變量，可表示數(shù)值［0,2八32-1］。若有如下程序段，其中s、a、b、c均已定義為整型變量，且a、c均已賦值（c大于0）s=afor（b=1;b<=c;b++）s=s-1;則與上述程序段功能登記的賦值語句是（）s=a-c;（正確答案）TOC\o"1-5"\h\zs=a—b;s=s—c;s=b-c;答案解析：解析:s初始化為a,緊接著for循環(huán)c次，每次s減1，因此該程序段相當(dāng)于s=a-c.5.設(shè)有100個(gè)已排好序的數(shù)據(jù)元素，采用折半查找時(shí)，最大比較次數(shù)為（）7（正確答案）1068答案解析：對(duì)100個(gè)有序元素進(jìn)行折半查找，每次查找可將檢索范圍縮小一半。由2八6-1<100<=2八7-1可知，最大比較次數(shù)為7。鏈表不具有的特點(diǎn)是（）插入刪除不需要移動(dòng)元素不必事先估計(jì)存儲(chǔ)空間所需空間與線性表長度成正比可隨機(jī)訪問任一元素（正確答案）答案解析：鏈表是通過記錄每個(gè)元素的后繼位置來實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，所需空間與元素個(gè)數(shù)成正比，優(yōu)點(diǎn)是不必事先估計(jì)存儲(chǔ)空間、插入或刪除指定位置元素的時(shí)間復(fù)雜度為0（1）；但缺點(diǎn)是由于其元素的內(nèi)存地址不連續(xù)，無法進(jìn)行0（1）的隨機(jī)訪問。把8個(gè)同樣的球放在5個(gè)同樣的袋子里，允許有的袋子空著不放，問共有多少種不同的分法?（）提示:如果8個(gè)球都放在一個(gè)袋子里，無論是哪個(gè)袋子，都只算同一種分法2224C.18（正確答案）20答案解析：枚舉法求解，8個(gè)同樣的球分1個(gè)袋子共1種方案，分2個(gè)袋子共4種方案，分3個(gè)袋子共5種方案，分4個(gè)袋子共5種方案，分5個(gè)袋子共3種方案，合計(jì)18種。一棵二叉樹如右圖所示，若采用順序存儲(chǔ)結(jié)構(gòu)，即用一維數(shù)組元素存儲(chǔ)該二叉樹中的結(jié)點(diǎn)（根結(jié)點(diǎn)的下標(biāo)為1,若某結(jié)點(diǎn)的下標(biāo)為i,則其左孩子位于下標(biāo)2i處、右孩子位于下標(biāo)2i+1處），則該數(shù)組的最大下標(biāo)至少為（）。TOC\o"1-5"\h\z61015（正確答案）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ù)是（）。8997（正確答案）9193答案解析：98-100均為合數(shù)，97為素?cái)?shù)。10.319和377的最大公約數(shù)是（）。273329（正確答案）31答案解析：使用輾轉(zhuǎn)相除法可得GCD（319,377）=GCD（319,58）=GCD（58,29）=29?；?qū)蓴?shù)分解質(zhì)因數(shù)后，提取公共部分亦可求解。11.新學(xué)期開學(xué)了，小胖想減肥，健身教練給小胖制定了兩個(gè)訓(xùn)練方案。方案一：每次連續(xù)跑3公里可以消耗300千卡（耗時(shí)半小時(shí)）；方案二：每次連續(xù)跑5公里可以消耗600千卡（耗時(shí)丨小時(shí)）。小胖每周周一到周四能抽出半小時(shí)跑步，周五到周日能抽出一小時(shí)跑步。另外，教練建議小胖每周最多跑21公里，否則會(huì)損傷膝蓋。請問如果小胖想嚴(yán)格執(zhí)行教練的訓(xùn)練方案，并且不想損傷膝蓋，每周最多通過跑步消耗多少千卡?（）TOC\o"1-5"\h\z300025002400（正確答案）2520答案解析：設(shè)方案1執(zhí)行x天，方案2執(zhí)行y天，則有3x+5y<=21、x+y<=7、y<=3。要求300x+600y的最大值，枚舉可得最優(yōu)方案為x=2、y=3，此時(shí)300x+600y為2400?；蚴褂镁€性規(guī)劃亦可求解。2.一副紙牌除掉大小王有52張牌，四種花色，每種花色13張。假設(shè)從這52張牌中隨機(jī)抽取13張紙牌，則至少（A）張牌的花色一致。4（正確答案）235答案解析：最壞情況，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位數(shù)字組，每一位都可以取0到9。請問這個(gè)城市最多有多少個(gè)車牌倒過來恰好還是原來的車牌?（）A.60B.125C.75（正確答案）D.100答案解析：前2位有0、1、8、6、9共5種選擇，第3位只能放0、1、8，后2位由前2位決定，因此總方案數(shù)為55311=75。假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA,中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為（）。ABCDEFGHIJABDEGHJCFI（正確答案）ABDEGJHCFIABDEGHJFIC答案解析：后序遍歷的規(guī)則是“左右根”、中序遍歷的規(guī)則是“左根右”，因此可知，A是樹根、DBGEHJ是A左子樹的中序遍歷（對(duì)應(yīng)后續(xù)遍歷DGJHEB）、CIF是A右子樹的中序遍歷（對(duì)應(yīng)后續(xù)遍歷IFC），遞歸畫出對(duì)應(yīng)的二叉樹，再根據(jù)前序遍歷規(guī)則“根左右”即可求出答案。以下哪個(gè)獎(jiǎng)項(xiàng)是計(jì)算機(jī)科學(xué)領(lǐng)域的最高獎(jiǎng)?（）圖靈獎(jiǎng)（正確答案）魯班獎(jiǎng)諾貝爾獎(jiǎng)普利策獎(jiǎng)答案解析：圖靈獎(jiǎng)由美國計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立，其名稱取自計(jì)算機(jī)科學(xué)之父圖靈，專門獎(jiǎng)勵(lì)對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人，被譽(yù)為“計(jì)算機(jī)界的諾貝二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填y,錯(cuò)誤填X;除特殊說明外，判斷題1.5分，選擇題4分，共計(jì)40分）程序一：ffinclude<cstdio>^include<cstring>nanie^pacestdjcharst[100};intmain(){scan-F(''%sh±st)：intn=strien(st);Sfor(intip2;L<=n;十i){if(n%i==0){charc=5t[i-1];if(c>**a*)st[i-1]-匚■*'A1;嗎}X)printff'Xs-,st);return0;□}?判斷題1）輸入的字符串只能由小寫字母或大寫字母組成。（）對(duì)錯(cuò)（正確答案）答案解析：輸入的字符串也可以包含數(shù)字等其他字符。2）若將第8行的“i=1”改為“i二0”，程序運(yùn)行時(shí)會(huì)發(fā)生錯(cuò)誤。（）對(duì)（正確答案）錯(cuò)答案解析：若i可以為0,則第9行的if語句條件“n%i==O”將發(fā)生運(yùn)行時(shí)錯(cuò)誤RE。3）若將第8行的“i〈二n”改為“ii〈二n”，程序運(yùn)行結(jié)果不會(huì)改變。（）對(duì)錯(cuò)（正確答案）答案解析：當(dāng)?shù)?行的循環(huán)條件為“i〈二n”時(shí)，字符串的末尾字符會(huì)被程序加工，但若改為“ii<二n”，字符串的末尾字符將不會(huì)被程序加工（除非字符串長度為1）。4）若輸入的字符串全部由大寫字母組成，那么輸出的字符串就跟輸入的字符串一樣。（）對(duì)錯(cuò)（正確答案）答案解析：大寫字母的ASCII編碼值小于小寫字母的。若輸入的字符串全部由大寫字母組成，則程序不會(huì)對(duì)其進(jìn)行加工。?選擇題5）若輸入的字符串長度為18，那么輸入的字符串跟輸出的字符串相比，至多有（）個(gè)字符不同。TOC\o"1-5"\h\z186（正確答案）101答案解析：18的正約數(shù)共有6個(gè)，因此程序至多修改輸入字符串中的6個(gè)字符，即輸出字符串與輸入字符串至多有6個(gè)字符不同。6）若輸入的字符串長度為（），那么輸入的字符串跟輸出的字符串相比，至多有36個(gè)字符不同。36100000（正確答案）1128答案解析：根據(jù)程序的作用可知，要使輸出字符串和輸入字符串之間至多有36個(gè)字符不同，36應(yīng)當(dāng)是字符串長度n的約數(shù)個(gè)數(shù)。本題選項(xiàng)中，僅有100000滿足要求，將其分解質(zhì)因數(shù)得100000=2八55八5,得其的正約數(shù)共有(5+1)(5+1)=36個(gè)。

程序二1^include<cstdia>2usingnAmesp^c^-std;3inin,nj4lhta[ae&]rb[we]j56intmsin(){7scanf(^d%d,\伽)：8for(int1=1;ivrt；卄i)ga[i]=b[i]=0;10^or(inti=1;i<=卄町｛11inty；12MmrvF(”％;ay);13if(3[x]<y&&b[y]<x){14if<a[x]>g)15t>[a[x]]■fli16訐(b[y]>0}17鞏b￡y]J=0；ISafx]=y;19b[yl=x;20}21}22intan^-0;23for(inti=1：i<-nj卄i){24if(a[i]==創(chuàng)25+*ans;26if(b[i]ke)27++ans;2S}29printf("^d\n",ans);30return0;31}假設(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>0時(shí)，一定存在某個(gè)數(shù)對(duì)被我們選中，此時(shí)ans<2n2）執(zhí)行完第27行的“++ans”時(shí)，ans一定是偶數(shù)。（）對(duì)錯(cuò)（正確答案）答案解析：由于數(shù)對(duì)是一個(gè)左值與一個(gè)右值相匹配，因此ans最終一定是偶數(shù)。但第27行的“++ans”在第23行的for循環(huán)的內(nèi)部，其中間結(jié)果可能為奇數(shù)。3）a[i]和b[i]不可能同時(shí)大于0。（）對(duì)錯(cuò)（正確答案）答案解析：a[i]用于記錄與左值i相匹配的右值，不存在則為0;b[i用于記錄與右值i相匹配的左值，不存在則為0。當(dāng)存在數(shù)對(duì)（i,y）和（x,i）都被我們選中時(shí)，a[i]和b[i]就會(huì)同時(shí)大于0。4）若程序執(zhí)行到第13行時(shí)，x總是小于y,那么第15行不會(huì)被執(zhí)行。（）對(duì)錯(cuò)（正確答案）答案解析：存在反例——依次考慮數(shù)對(duì)（1,2）（1,3）時(shí)，第15行程序會(huì)被執(zhí)行。?選擇題5）若m個(gè)x兩兩不同，且m個(gè)y兩兩不同，則輸出的值為（）2n-2m（正確答案）TOC\o"1-5"\h\z2n+22n-22n答案解析：此時(shí)，輸入的數(shù)對(duì)兩兩互不沖突，因此程序會(huì)將它們?nèi)窟x中，根據(jù)上述ans的意義可知，其結(jié)果為2n-2m。6）若m個(gè)x兩兩不同，且m個(gè)y都相等，則輸出的值為（）2n-2（正確答案）2n2m2n-2m答案解析：此時(shí)，輸入的數(shù)對(duì)兩兩存在沖突，因此程序最終只會(huì)選用一個(gè)數(shù)對(duì)，根據(jù)上述ans的意義可知，其結(jié)果為2n-2。

程序三1^include7ri￡nflmpsp^rpstd;3constintmaxn=10000;4-intn;Sinta[maxn];6intbfmaxn];7intf(int1jintr,intdepth){8if(1>r)9return0;1&intmin=maxrijmink;11for(inti-lji<=rj++i){12i-f(mir>){13min=a[I];14mink=i;15}16}17irit=€(1;mink-ltdepth+1);18intrres=■f(mink+1,r>d^pth+1);19retnrnlrms+rres十depth*b[minkj;23}21intmain(){22cin>>n;23for(inti=i<n;++i)24>>a[i];25for(inti0;i<n;++i)26cin?b[i];27cout?f?1上1)<<endlj23r^twrri8；29}?判斷題1）如果a數(shù)組有重復(fù)的數(shù)字，則程序運(yùn)行時(shí)會(huì)發(fā)生錯(cuò)誤。（）對(duì)錯(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ù)最接近的是：（）。5000（正確答案）600c.6D.100答案解析：最壞情況下，程序所構(gòu)造的二叉樹的每個(gè)結(jié)點(diǎn)至多僅有一個(gè)子結(jié)點(diǎn)，此時(shí)，程序?qū)⑦f歸100層，其中第i層進(jìn)行100-i+l次第12行的比較運(yùn)算，總執(zhí)行次數(shù)為100+99+98+???+15000。4）當(dāng)n=100時(shí)，最好情況下，與第12行的比較運(yùn)算執(zhí)行的次數(shù)最接近的是：（）。TOC\o"1-5"\h\z10065000600（正確答案）答案解析：最佳情況下，程序構(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ù)約為nlogn~600。5）當(dāng)n=10時(shí)，若b數(shù)組滿足，對(duì)任意0Wi<n,都有b[i]=i+1，那么輸出最大為（）。386383384D.385（正確答案）答案解析：此時(shí)，要使輸出的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ì)任意0Wi<n,都有b[i]=1，那么輸出最小為（）。TOC\o"1-5"\h\z582580（正確答案）579581答案解析：此時(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。三、完善程序（單選題，每題3分，共計(jì)30分）程序一（矩陣變幻）有一個(gè)奇幻的矩陣，在不停的變幻，其變幻方式為:數(shù)字0變成知孵什眾數(shù)影變成初陣:］。加初腳陣只有一個(gè)冗紐蠻幻I】次后.矩陣念變成什么樣？例如.矩陣圮初為：［0］；矩陣變幻丨伙后；什即矩陣變幻2次后：［0000'01010011p0110輸入一行一個(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。#include"stdio>lusingnamespacestdjintn;intmaxsize=1<<10;5intre5[max_5ize][max_size];7voidrecursive(irrtx」inty」intnjirrtt){if5==0>{ieres[x][y]=①；11yturr;12}13intst^p=31<<(n-1);14recursivef②*n-ijt)j.15rerursiv&fxjy+stepjn」ht)J16recursive(x+&tep,n-1.t)；17recurs!③#n-ltIt);18}19intmain(){21scanfCM'^&n);22recursive{0j0,?);23intsize=⑥；24for(inti=e；i<size;亠*i〉{25far(intj=9;j<sizeji-+j)26printf("Xd",res[i][j]);27p2S}29return0;39}1）①處應(yīng)填（）n%20t（正確答案）1答案解析：此處為遞歸邊界，當(dāng)需要計(jì)算的是單位矩陣時(shí)，相應(yīng)元素應(yīng)賦值為t,即無需再經(jīng)任何變換。2）②處應(yīng)填（）x-step,y-stepx,y-stepx-step,yx,y（正確答案）答案解析：左上角（x,y），且大小2L2八n的矩陣，可以分成4個(gè)2nT2八n-1的矩陣分別計(jì)算。此處需要計(jì)算的是4個(gè)矩陣中位于左上方的矩陣,該矩陣的左上角坐標(biāo)為（x,y）o3）③處應(yīng)填（）x-step,y-stepX+step,y+step（正確答案）x,y-stepx-step,y答案解析：左上角（x,y）,且大小2L2八n的矩陣，可以分成4個(gè)2nT2八n-1的矩陣分別計(jì)算。此處需要計(jì)算的是4個(gè)矩陣中位于右下方的矩陣，該矩陣的左上角坐標(biāo)為（x+2八n-1,y+2八nT）。4）④處應(yīng)填（）n-1，n%2n,0（正確答案）c.n,n%2n-1，0答案解析：此處是遞歸計(jì)算的入口，即題目最終所求的是大小2L2L,由單個(gè)數(shù)字0變幻而來的矩陣，因此遞歸函數(shù)的后兩個(gè)參數(shù)應(yīng)設(shè)為n和0。5）⑤處應(yīng)填（）1<<（n+1）1<<n（正確答案）n+11<<（n-1）答案解析：此處是計(jì)算最終所求的矩陣大小，即邊長size為2L,位運(yùn)算寫做“1<<n”。程序二（計(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ù)a[i]和b[i],分別表示第i對(duì)整數(shù)的第一關(guān)鍵字和第二關(guān)鍵字。從小到大排序后輸出。數(shù)據(jù)范圍1WnW10八7,1Wa[i],b[i]W10八4。提示：應(yīng)先對(duì)第二關(guān)鍵字排序，再對(duì)第一關(guān)鍵字排序。數(shù)組ord口存儲(chǔ)第二關(guān)鍵字排序的結(jié)果，數(shù)組res[]存儲(chǔ)雙關(guān)鍵字排序的結(jié)果。試補(bǔ)全程序。ffinclude<cstdio》#iriclude^citring>Jusingnamespacestd;constintmaxn=10000^30;conwtiirtmaxs=10000;6intn;Sunsigneda[maxn],b[maxn]fres[maxn],ord[maxn];unsignedcnt[max5+1];10intmain(){swnff'Xd",&n);'for(int1=0;i<n;++i)scanf(HXdXdnffiflemset(cnt,比sizeo-F(cnt))?for(int1=0;ten;<-bi)①；//利用ent葩組統(tǒng)計(jì)數(shù)雖for(intie；1<帕xs;++i)ent[i+1]2cnt[i];for(int1=0;1<n;++1)②；//記最初步恂怦結(jié)果meFnsetfcnt,0,sizeof(ent));for(inti?0;icn;i-+i)H利用ent數(shù)爼統(tǒng)計(jì)數(shù)皿for(inti=6;i<++i)ent[i+1]*二cnt[i];for(inti=n-1;5a