NOIP2022提高組C++初賽試題

1、第14頁 共14頁NOIP2022進(jìn)步組C+初賽試題第二十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽 進(jìn)步組 C+語言試題 競賽時(shí)間：2022 年 10 月 22 日 14:3016:30 選手注意: 試題紙共有 13 頁，答題紙共有 2 頁，總分值 100 分。請?jiān)诖痤}紙上作答，寫 在試題紙上的一律無效。 不得使用任何電子設(shè)備如計(jì)算器、手機(jī)、電子詞典等或查閱任何書籍資料。 一、單項(xiàng)選擇題共 15 題，每題 1.5 分，共計(jì) 22.5 分；每題有且僅有一個(gè)正確 選項(xiàng) 1. 以下不是微軟公司出品的軟件是 。 . Powerpoint . Word . Excel . Acrobat Reader 2.

2、 假如開場時(shí)計(jì)算機(jī)處于小寫輸入狀態(tài)，如今有一只小老鼠反復(fù)按照 CapsLock、字母鍵 A、字母鍵 S 和字母鍵 D 的順序來回按鍵，即 CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、，屏幕上輸出的第 81 個(gè)字符是字母 。 . A . S . D . A 3. 二進(jìn)制數(shù) 00100 和 00 異或的結(jié)果是 。 . 00000 . 01111001 . 01000100 . 00111000 4. 與二進(jìn)制小數(shù) 0.1 相等的八進(jìn)進(jìn)制數(shù)是 。 . 0.8 . 0.4 . 0.2 . 0.1 5. 以比擬作為根本運(yùn)算，在 N 個(gè)

3、數(shù)中找最小數(shù)的最少運(yùn)算次數(shù)為 。 . N . N-1 . N2 . log N 6. 表達(dá)式 a*(b+c)-d 的后綴表達(dá)形式為 。 . abcd*+- . abc+*d- . abc*+d- . -+*abcd 7. 一棵二叉樹如右圖所示，假設(shè)采用二叉樹鏈表存儲(chǔ)該二叉 樹各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指 針。假如沒有左孩子或者右孩子，那么對應(yīng)的為空指針。 那么該鏈表中空指針的數(shù)目為 。 A. 6 B. 7 C. 12 . 14 8. G 是一個(gè)非連通簡單無向圖，共有 28 條邊，那么該圖至少有 個(gè)頂點(diǎn)。 . 10 . 9 .8 .7 CCF NOIP2022 初賽進(jìn)步組 C+語

4、言試題 第 1 頁，共 13 頁 9. 某計(jì)算機(jī)的 CPU 和內(nèi)存之間的地址總線寬度是 32 位bit，這臺(tái)計(jì)算機(jī)最 多可以使用 的內(nèi)存。 A. 2GB B. 4GB C. 8GB D. 16GB 10. 有以下程序： #include iostream using namespace std; int main int k = 4, n = 0; while (n k) n+; if (n % 3 != 0) continue; k-; cout k “,“ n endl; return 0; 程序運(yùn)行后的輸出結(jié)果是 。 . 2,2 . 2,3 . 3,2 . 3,3 11. 有 7 個(gè)一模

5、一樣的蘋果，放到 3 個(gè)一樣的盤子中，一共有 種放法。 . 7 . 8 . 21 . 37 12. Lucia 和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊了賬號(hào)。以下圖是他們 之間的關(guān)系圖，兩個(gè)人之間有邊相連代表這兩個(gè)人是朋友，沒有邊相連代表 不是朋友。這個(gè)社交網(wǎng)站的規(guī)那么是：假如某人 A 向他她的朋友 B 分享了 某張照片，那么 B 就可以對該照片進(jìn)展評論；假如 B 評論了該照片，那么他 她的所有朋友都可以看見這個(gè)評論以及被評論的照片，但是不能對該照 CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 2 頁，共 13 頁 片進(jìn)展評論除非 A 也向他她分享了該照片。如今 Lucia 已

6、經(jīng)上傳了 一張照片，但是她不想讓 Jacob 看見這張照片，那么她可以向以下朋友 分享該照片。 . Dana, Michael, Eve . Dana, Eve, Monica . Michael, Eve, Jacob . Micheal, Peter, Monica 13. 周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé) 切菜、媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜 10 分鐘，然后切 菜 10 分鐘，最后炒菜 10 分鐘。那么做一道菜需要 30 分鐘。注意：兩道不 同的菜的一樣步驟不可以同時(shí)進(jìn)展。例如第一道菜和第二道的菜不能同時(shí)洗， 也不能同時(shí)切。那么做完三道菜

7、的最短時(shí)間需要 分鐘。 A. 90 B. 60 C. 50 D. 40 14. 假設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式 T(n) = 2T+ T(1) = 1 那么算法的時(shí)間復(fù)雜度為 。 A.O(n) B. O C. O( logn) D. O(n2) 1. 給定含有 n 個(gè)不同的數(shù)的數(shù)組 L=x1, x2, ., xn。假如 L 中存在 x i1 i n 使得 x1 x2 . xi-1 xi xi+1 . xn， 那么稱 L 是單峰的，并稱 xi 是 L 的 “峰頂”。如今 L 是單峰的，請把 a-c 三行代碼補(bǔ)全到算法中使得算法 正確找到 L 的峰頂。 a. Search(k+1, n) b

8、. Search(1, k-1) c. return Lk Search(1, n) 1. k n/2 2. if Lk Lk-1 and Lk Lk+1 3. then _ 4. else if Lk Lk-1 and Lk Lk+1 5. then _ 6. else _ 正確的填空順序是 。 A. c, a, b B. c, b, a C. a, b, c D. b, a, c 二、不定項(xiàng)選擇題共 5 題，每題 1.5 分，共計(jì) 7.5 分；每題有一個(gè)或多個(gè)正確 選項(xiàng)，多項(xiàng)選擇或少選均不得分 CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 3 頁，共 13 頁 1. 以下屬于無線

9、通信技術(shù)的有 。 A. 藍(lán)牙 B. WiFi C. GPRS D. 以太網(wǎng) 2. 可以將單個(gè)計(jì)算機(jī)接入到計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有 。 A. 網(wǎng)卡 B. 光驅(qū) C. 鼠標(biāo) D. 顯卡 3. 以下算法中運(yùn)用分治思想的有 。 A. 快速排序 B. 歸并排序 C. 冒泡排序 D. 計(jì)數(shù)排序 4. 以下圖表示一個(gè)果園灌溉系統(tǒng)，有 A、B、C、D 四個(gè)閥門，每個(gè)閥門可以翻開 或關(guān)上，所有管道粗細(xì)一樣，以下設(shè)置閥門的方法中，可以讓果樹澆上水的 有水 有水 果樹 有 。 A. B 翻開，其他都關(guān)上 B. AB 都翻開，CD 都關(guān)上 C. A 翻開，其他都關(guān)上 D. D 翻開，其他都關(guān)上 5. 參加 N

10、OI 比賽，以下能帶入考場的有 。 A. 鋼筆 B. 適量的衣服 C. U 盤 D. 鉛筆 三、問題求解共 2 題，每題 5 分，共計(jì) 10 分；每題全部答對得 5 分，沒有局部分 1. 一個(gè) 18 的方格圖形不可旋轉(zhuǎn)用黑、白兩種顏色填涂每個(gè)方格。假如 每個(gè)方格只能填涂一種顏色，且不允許兩個(gè)黑格相鄰，共有_種填 涂方案。 2. 某中學(xué)在安排期末考試時(shí)發(fā)現(xiàn)，有 7 個(gè)學(xué)生要參加 7 門課程的考試，下表列 出了哪些學(xué)生參加哪些考試用表示要參加相應(yīng)的考試。 最少要安排_(tái)個(gè)不同的考試時(shí)間段才能防止沖突？ CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 4 頁，共 13 頁 考試 學(xué)生 1 學(xué)生

11、 2 學(xué)生 3 學(xué)生 4 學(xué)生 5 學(xué)生 6 學(xué)生 7 通用技術(shù) 物理 化學(xué) 生物 歷史 地理 政治 四、閱讀程序?qū)懡Y(jié)果共 4 題，每題 8 分，共計(jì) 32 分 1. #include iostream using namespace std; int main int a6 = 1, 2, 3, 4, 5, 6; int pi = 0; int 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

12、; 輸出：_ 2. #include iostream using namespace std; int main char a100100, b100100; string c100; string tmp; int n, i = 0, j = 0, k = 0, total_len100, length1003; CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 5 頁，共 13 頁 cin n; getline(cin, tmp); for (i = 0; i n; i+) getline(cin, ci); total_leni = ci.size; for (i = 0; i

13、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 n; i+) if (lengthi1 = lengthi2) cout “NO,“; else k = 0; for (j = 0; j lengthi2; j+) if (aik = bij) k = k

14、+ 1; if (k lengthi1) break; if (j = lengthi2) cout “NO,“; else cout “YES,“; cout endl; return 0; CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 6 頁，共 13 頁 輸入：3 AB:ACDEbFBkBD AR:ACDBrT SARS:Severe Atypical Respiratory Syndrome 輸出：_ 注：輸入各行前后均無空格 3. #includeiostream using namespace std; int lps(string seq, int i, int j)

15、int len1, len2; if (i = j) return 1; if (i j) return 0; if (seqi = 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 = seq.size; cout lps(seq, 0, n - 1) endl; return 0; 輸出

16、：_ 4. #include iostream #include cstring using namespace std; int map100100; int sum100, weight100; int visit100; CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 7 頁，共 13 頁 int n; void dfs(int node) visitnode = 1; sumnode = 1; int v, maxw = 0; for (v = 1; v = n; v+) if (!mapnodev | visitv) continue; dfs(v); sumnode +=

17、sumv; if (sumv 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(visit); cin n; int i, x, y; for (i = 1; i n; i+) cin x y; mapxy = 1; mapyx = 1; df

18、s(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; 輸入：11 CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 8 頁，共 13 頁 1 2 1 3 2 4 2 5 2 6 3 7 7 8 7 11 6 9 9 10 輸出：_ 五、完善程序共 2 題，每題 14 分，共計(jì) 28 分 1. 交朋友根據(jù)社會(huì)學(xué)研究說明，人們都喜歡找和自己身高相近的人做朋友。 如今有 n 名身高兩兩不一樣的同

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

20、clude iostream using namespace std; #define MAXN 200000 #define infinity 2147483647 int answerMAXN, heightMAXN, previousMAXN, nextMAXN; int rankMAXN; int n; void sort(int l, int r) int x = heightrank(l + r) / 2, i = l, j = r, temp; while (i = j) while (heightranki x) i+; while (heightrankj x) j-; if

21、 ( (1) ) temp = ranki; ranki = rankj; rankj = temp; CCF NOIP2022 初賽進(jìn)步組 C+語言試題 第 9 頁，共 13 頁 i+; j-; if (i r) sort(i, r); if (l j) sort(l, j); int main cin n; int i, higher, shorter; for (i = 1; i = n; i+) cin heighti; ranki = i; sort(1, n); for (i = 1; i = n; i+) previousranki = ranki - 1; (2) ; for

22、(i = n; i = 2; i-) higher = shorter = infinity; if (previousi !=0) shorter = heighti - heightpreviousi; if (nexti != 0) (3) ; if ( (4) ) answeri = previousi; else answeri = nexti; nextpreviousi = nexti; (5) ; for (i = 2; i = n; i+) cout i “:“ answeri; return 0; 2. (交通中斷有一個(gè)小國家，國家內(nèi)有 n 座城市和 m 條雙向的道路，每條

23、道路連接著兩座不同的城市。其中 1 號(hào)城市為國家的首都。由于地震頻繁可能導(dǎo)致某一個(gè)城市與外界交通全部中斷。這個(gè)國家的首腦想知道，假如只有第i(i1)個(gè)城市因地震而導(dǎo)致交通中斷時(shí)，首都到多少個(gè)城市的最短途徑長度會(huì)發(fā)生改變。假如因?yàn)闊o法通過第 i 個(gè)城市而導(dǎo)致從首都出發(fā)無法到達(dá)某個(gè)城 CCF NOIP2022 初賽進(jìn)步組C+語言試題 第 10 頁，共 13 頁 市，也認(rèn)為到達(dá)該城市的最短途徑長度改變。 對于每一個(gè)城市 i，假定只有第 i 個(gè)城市與外界交通中斷，輸出有多少個(gè) 城市會(huì)因此導(dǎo)致到首都的最短途徑長度改變。 我們采用鄰接表的方式存儲(chǔ)圖的信息，其中 headx表示頂點(diǎn) x 的第一條 邊的編號(hào)，

24、nexti表示第 i 條邊的下一條邊的編號(hào)，pointi表示第 i 條邊的終點(diǎn)，weighti表示第 i 條邊的長度。第一空 2 分，其余 3 分 #include iostream #include cstring using namespace std; #define MAXN 6000 #define MAXM 100000 #define infinity 2147483647 int headMAXN, nextMAXM, pointMAXM, weightMAXM; int queueMAXN, distMAXN, visitMAXN; int n, m, x, y, z, total = 0, answer; void link(int x,int y,int z) total+; nexttotal = headx; headx = total; pointtotal = y; weighttotal = z; total+; nexttotal = heady; heady = total; pointtotal = x; weighttotal = z; int main int i,