NOIP提高組初賽C格式格式

1、第二十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提咼組C+語(yǔ)言試題（2小時(shí)）選手注意： 不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等?；虿殚喨魏螘Y料。 一、單項(xiàng)選擇題（共15題，每題 分，1. 以下不是微軟公司出品的軟件是（A. PowerpointB . Word2. 如果開始時(shí)計(jì)算機(jī)處于小寫輸入狀態(tài)，共計(jì)分；每題有且僅有一個(gè)正確選項(xiàng)） 。C . ExcelD . Acrobat Reader現(xiàn)在有一只小老鼠反復(fù)按照CapsLock、字母鍵A、字母鍵S和字母鍵D的順序來回按鍵，即CapsLock、A、S、D S、A、CapsLock、 A S、D S、A、CapsLock、A、S、D S、

2、A ，屏幕上輸出的第 81個(gè)字符是字 母（。A. AB . SC . D3. 二進(jìn)制數(shù)00101100和01010101異或的結(jié)果旦/A.001010004. 與二進(jìn)制小數(shù)相等的八進(jìn)進(jìn)制數(shù)是（A.B .5. 以比較作為基本運(yùn)算，在 N個(gè)數(shù)中找最小數(shù)的最少運(yùn)算次數(shù)為（A. NB . N-16. 表達(dá)式a*（b+c）-d 的后綴表達(dá)形式為（A. abcd*+-B . abc+*d-+*abcd7. 一棵二叉樹如右圖所示，若采用二叉樹鏈表存儲(chǔ)該二叉（各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針）如果沒有左孩子或者右孩子，則對(duì)應(yīng)的為空指針。那么該鏈 表中空指針的數(shù)目為（）。A. 6B. 7C. 12

3、8. G是一個(gè)非連通簡(jiǎn)單無向圖，共有 28條邊，則該圖至少有（A. 10B . 9C .8D .79. 某計(jì)算機(jī)的CPU和內(nèi)存之間的地址總線寬度是 32位（bit ），這臺(tái)計(jì)算機(jī)最多可 以使用（。的內(nèi)存。A. 2GBB. 4GBC. 8GBD. 16GB10. 有以下程序：#i nclude using n amespace std;int mai n（） int k = 4, n = 0;while （n k） n+;if （n % 3 != 0） con ti nue;k-;B . 01111001是（）。C.01000100。D. 00111000C . N2D . log N。C. a

4、bc*+d-D . 14 。個(gè)頂點(diǎn)。cout k , n en dl; return 0;程序運(yùn)行后的輸出結(jié)果是()。A. 2,2B . 2,3C . 3,2D . 3,311. 有7個(gè)一模一樣的蘋果，放到3個(gè)一樣的盤子中，一共有()種放法。A. 7B . 8C . 21D . 3712. Lucia和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊(cè)了賬號(hào)。下圖是他們之間的關(guān)系圖，兩個(gè)人之間有邊相連代表這兩個(gè)人是朋友，沒有邊相連代表不是朋友。這個(gè)社交網(wǎng)站的規(guī)則是：如果某人 A向他(她)的朋友B分享了某張照片，那么B 就可以對(duì)該照片進(jìn)行評(píng)論；如果 B評(píng)論了該照片，那么他 (她)的所有朋友都可以 看見這

5、個(gè)評(píng)論以及被評(píng)論的照片，但是不能對(duì)該照片進(jìn)行評(píng)論(除非 A也向他(她) 分享了該照片)?，F(xiàn)在Lucia已經(jīng)上傳了一張照片，但是她不想讓Jacob看見這張照片，那么她可以向以下朋友()分享該照片。A. Dana, Michael, EveB . Dana, Eve, MonicaC . Michael, Eve, JacobD . Micheal, Peter, Monica13. 周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé)切菜、 媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜 10分鐘，然后切 菜10分鐘，最 后炒菜10分鐘。那么做一道菜需要30分鐘。注意：兩道不 同的菜

6、的相同步驟不可 以同時(shí)進(jìn)行。例如第一道菜和第二道的菜不能同時(shí)洗，也不能同時(shí)切。那么做完三道 菜的最短時(shí)間需要()分鐘。A. 90 B. 60 C. 50 D. 4014假設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T(n) = 2T( -)+、. n4T(1) = 1則算法的時(shí)間復(fù)雜度為()。(n) B. 0( n) C. O( -n logn) D. O(n2)1. 給定含有n個(gè)不同的數(shù)的數(shù)組L=。如果L中存在Xi (1 i n) 使得 X1 X2 . Xi-1 xi+1 . Xn， 則稱 L 是單峰的，并稱 xi是L的“峰頂”現(xiàn)在已知L是單峰的，請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中使得算法正確找到L的峰頂

7、。a. Search(k+1, n)b. Search(1, k-1)c. return LkSearch(1, n)1. kJ n/22. if Lk Lk-1 a nd Lk Lk+13. the n4. else if Lk Lk-1 a nd Lk Lk+15. the n6. else正確的填空順序是()。A. c, a, b B. c, b, a C. a, b, c D. b, a, c分；每題有一個(gè)或多個(gè)正確 選項(xiàng),二、不定項(xiàng)選擇題（共5題，每題 分，共計(jì) 多選或少選均不得分）1. 以下屬于無線通信技術(shù)的有（）。A.藍(lán)牙 B. WiFi C. GPRS D.以太網(wǎng)2. 可以將單

8、個(gè)計(jì)算機(jī)接入到計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有（）A.3.A.4.上網(wǎng)卡 B.光驅(qū) C.鼠標(biāo) 下列算法中運(yùn)用分治思想的有（ 快速排序 B.歸并排序 C. 下圖表示一個(gè)果園灌溉系統(tǒng)，有D. 顯卡）冒泡排序A、B C所有管道粗細(xì)相同，以下設(shè)置閥門的方法中, 有水D.計(jì)數(shù)排序D四個(gè)閥門，每個(gè)閥門可以打開或關(guān)可以讓果樹澆上水的有（）有水A.C.5.A.B打開，其他都關(guān)上 A打開，其他都關(guān)上參加NOI比賽，以下能鋼筆 B.適量的衣服問題求解（共2題，每題15果樹AB都打開，CD都關(guān)上 D打開，其他都關(guān)上鉛筆B.D.入考場(chǎng)的有（V答對(duì)得5分，沒有部分分）1.方格只能填涂一種顏色，且不允許兩個(gè)黑格相鄰，共有

9、廠_種填涂方案。2.某中學(xué)在安排期末考試時(shí)發(fā)現(xiàn)，有 7個(gè)學(xué)生要參加7門課程的考試，下表列 出 了哪些學(xué)生參加哪些考試（用V表示要參加相應(yīng)的考試）。最少要安排 不一個(gè)1X 8的方格圖形（不可旋轉(zhuǎn)）用色填涂每個(gè)方格。如果每個(gè)種填涂方案同的考試時(shí)間段才能避免沖突?考試學(xué)生1學(xué)生2學(xué)生3學(xué)生4學(xué)生5學(xué)生6學(xué)生7通用技術(shù)VVV物理VVV化學(xué)VV生物VVV歷史VVV地理VVV政治 V V 四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. #i nclude using n amespace std; int mai n() int a6 = 1,2, 3, 4, 5, 6;int pi = 0;in

10、t pj = 5;int t , i;while (pi pj) t = api; api = apj; apj = t;pi+;pj-;for (i = 0; i 6; i+)cout ai ,;cout endl; return 0;輸出 ： 2. #include using namespace std;int main() char a100100, b100100;string c100;string tmp;int n, i = 0, j = 0, k = 0, total_len100, length1003; cin n;getline(cin, tmp);for (i = 0

11、; i n; i+) getline(cin, ci); total_leni = ci.size(); for (i = 0; i n; i+) j = 0;while (cij != :) aik = cij;k = k + 1; j+; lengthi1 = k - 1; aik = 0; k = 0;for (j = j + 1; j total_leni; j+) bik = cij;k = k + 1;lengthi2 = k - 1;bik = 0;k = 0;for (i = 0; i = lengthi2)cout NO,;else k = 0; for (j = 0; j

12、lengthi1) break; if (j = lengthi2) cout NO,;elsecout YES,;cout endl; return 0;輸入 ：3 AB:ACDEbFBkBD AR:ACDBrT SARS:Severe Atypical Respiratory Syndrome 輸 出 ： (注：輸入各行前后均無空格)3. #include using namespace std;int lps(string seq, int i, int j) int len1, len2; if (i = j) return 1; if (i j)return 0;if (seqi =

13、 seqj) return lps(seq, i + 1, j - 1) + 2;len1 = lps(seq, i, j - 1);len2 = lps(seq, i + 1, j);if (len1 len2) return len1; return len2;int main() string seq = acmerandacm; int n = ();cout lps(seq, 0, n - 1) endl; return 0;輸出 ： 4. #include #include using namespace std;int map100100;int sum100, weight10

14、0;int visit100;int n;void dfs(int node) visitnode = 1; sumnode = 1; int v, maxw = 0;for (v = 1; v maxw)maxw = sumv;if (n - sumnode maxw)maxw = n - sumnode;weightnode = maxw;int main() memset(map, 0, sizeof(map); memset(sum, 0, sizeof(sum); memset(weight, 0, sizeof(weight); memset(visit, 0, sizeof(vi

15、sit); cin n; int i, x, y;for (i = 1; i x y; mapxy = 1; mapyx = 1; dfs(1);int ans = n, ansN = 0;for (i = 1; i = n; i+) if (weighti ans) ans = weighti; ansN = i;cout ansN ans endl;return 0;輸入 ：113 77 87 116 99 10輸出：五、完善程序(共2題，每題14分，共計(jì)28分)1. (交朋友)根據(jù)社會(huì)學(xué)研究表明，人們都喜歡找和自己身高相近的人做朋友?，F(xiàn)在 有n名身高兩兩不相同的同學(xué)依次走入教室，調(diào)查人員

16、想預(yù)測(cè)每個(gè)人在走入教室的瞬間最想和已經(jīng)進(jìn)入教室的哪個(gè)人做朋友。當(dāng)有兩名同學(xué)和這名同學(xué)的身高差一樣時(shí),這名同學(xué)會(huì)更想和高的那個(gè)人做朋友。比如一名身高為米的同學(xué)進(jìn)入教室時(shí)，有一名身高為米的同學(xué)和一名身高為米的同學(xué)在教室里，那么這名身高為米的同學(xué)會(huì)更想和身高為米的同學(xué)做朋友。對(duì)于第一個(gè)走入教室的同學(xué)我們不做預(yù)測(cè)。由于我們知道所有人的身高和走進(jìn)教室的次序，所以我們可以采用離線的做法來解決 這樣的問題，我們用排序加鏈表的方式幫助每一個(gè)人找到在他之前進(jìn)入教室的并且和他身高最相近的人。(第一空2分，其余3分)#i nclude using n amespace std;#defi ne MAXN 20000

17、0int an swerMAXN, heightMAXN, previousMAXN, nextMAXN;int ran kMAXN;int n;void sort(i nt l, i nt r) int x = heightra nk(l + r) / 2, i = l, j = r, temp;while (i = j)while (heightra nki x)j-;if (1L) temp = ran ki; ran ki = ran kj;ra nkj = temp;i+;j-;if (i r) sort(i, r);if (l n;int i, higher, shorter;fo

18、r (i = 1; i heighti;ran ki = i;sort(1, n);for (i = 1; i = 2; i_)higher = shorter = infin ity;if (previousi !=0)shorter = heighti - heightpreviousi;if (n exti != 0) ;if ()an sweri = previousi;elsean sweri = n exti;n extpreviousi = n exti; ;for (i = 2; i = n; i+)cout i : 1)個(gè)城市因地震而導(dǎo)致交通中斷時(shí)，首都到多少個(gè)城市的最短路徑

19、長(zhǎng)度會(huì)發(fā)生改變。如果因?yàn)闊o法通過 第i個(gè)城市而導(dǎo)致從首都出發(fā)無法到達(dá)某個(gè)城市，也認(rèn)為到達(dá)該城市的最短路徑長(zhǎng)度 改變。對(duì)于每一個(gè)城市i ,假定只有第i個(gè)城市與外界交通中斷，輸出有多少個(gè)城市會(huì)因此 導(dǎo)致到首都的最短路徑長(zhǎng)度改變。我們采用鄰接表的方式存儲(chǔ)圖的信息，其中headx 表示頂點(diǎn)x的第一條邊的編號(hào)，nexti表示第i條邊的下一條邊的編號(hào)，pointi 表示第i條邊的終點(diǎn)，weighti表示第i條邊的長(zhǎng)度。(第一空2分，其余3分) #i nclude #in clude using n amespace std;#defi ne MAXN 6000#defi ne MAXM 100000int headMAXN, nextMAXM, poi ntMAXM, weightMAXM;int que