NOIP2022提高組C++初賽試題

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

2、 Reader 2.如果開(kāi)始時(shí)計(jì)算機(jī)處于小寫(xiě)輸入狀態(tài)，現(xiàn)在有一只小老鼠反復(fù)按照 CapsLock、字母鍵 A、字母鍵 S 和字母鍵 D 的順序來(lái)回按鍵，即 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è)數(shù)中找

3、最小數(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ù)如右圖所示，若采用二叉樹(shù)鏈表存儲(chǔ)該二叉 樹(shù)（各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指 針）。如果沒(méi)有左孩子或者右孩子，則對(duì)應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為（ ）。A. 6 B.7 C. 12 .14 8.G 是一個(gè)非連通簡(jiǎn)單無(wú)向圖，共有 28 條邊，則該圖至少有（ ）個(gè)頂點(diǎn)。.10 .9 .8 .7 CCF NOIP20_ 初賽提高組 C+語(yǔ)言試題 第 1 頁(yè)，共 13 頁(yè)

4、9.某計(jì)算機(jī)的 CPU 和內(nèi)存之間的地址總線寬度是 32 位（bit），這臺(tái)計(jì)算機(jī)最 多可以使用（ ）的內(nèi)存。A.2GB B.4GB C.8GB D.16GB 10.有以下程序：#include using namespace std; int main int k = 4, n = 0; while (n 。如果 L 中存在 _ i（1 _i+1 . _n， 則稱(chēng) L 是單峰的，并稱(chēng) _i 是 L 的 “峰頂”。現(xiàn)在已知 L 是單峰的，請(qǐng)把 a-c 三行代碼補(bǔ)全到算法中使得算法 正確找到 L 的峰頂。a.Search(k+1, n) b.Search(1, k-1) c.return Lk

5、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 using namespace std; int main int a6 = 1, 2, 3, 4, 5, 6; int pi = 0; int pj = 5; int t , i; while (pi using namespace std; int main char a100100, b100100; string c100; string tmp; int n, i = 0, j = 0, k = 0, total_len100,

6、 length1003; CCF NOIP20_ 初賽提高組 C+語(yǔ)言試題 第 5 頁(yè)，共 13 頁(yè) cin n; getline(cin, tmp); for (i = 0; i = lengthi2) cout lengthi1) break; if (j = lengthi2) cout 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 = seqj) return lps(seq, i + 1, j

7、 - 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 #include using namespace std; int map100100; int sum100, weight100; int visit100; CCF NOIP20_ 初賽提高組 C+語(yǔ)言試題 第 7 頁(yè)，共 13 頁(yè) int n; void df

8、s(int node) visitnode = 1; sumnode = 1; int v, ma_w = 0; for (v = 1; v ma_w) ma_w = sumv; if (n - sumnode ma_w) ma_w = n - sumnode; weightnode = ma_w; 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, _, y

9、; for (i = 1; i _ y; map_y = 1; mapy_ = 1; dfs(1); int ans = n, ansN = 0; for (i = 1; i using namespace std; #define MA_N 20_000 #define infinity 2147483647 int answerMA_N, heightMA_N, previousMA_N, ne_tMA_N; int rankMA_N; int n; void sort(int l, int r) int _ = heightrank(l + r) / 2, i = l, j = r, t

10、emp; while (i _) j-; if ( (1) ) temp = ranki; ranki = rankj; rankj = temp; CCF NOIP20_ 初賽提高組 C+語(yǔ)言試題 第 9 頁(yè)，共 13 頁(yè) i+; j-; if (i n; int i, higher, shorter; for (i = 1; i heighti; ranki = i; sort(1, n); for (i = 1; i = 2; i-) higher = shorter = infinity; if (previousi !=0) shorter = heighti - heightpre

11、viousi; if (ne_ti != 0) (3) ; if ( (4) ) answeri = previousi; else answeri = ne_ti; ne_tpreviousi = ne_ti; (5) ; for (i = 2; i 1)個(gè)城市因地震而導(dǎo)致交通中斷時(shí)，首都到多少個(gè)城市的最短路徑長(zhǎng)度會(huì)發(fā)生改變。如果因?yàn)闊o(wú)法通過(guò)第 i 個(gè)城市而導(dǎo)致從首都出發(fā)無(wú)法到達(dá)某個(gè)城 CCF NOIP20_ 初賽提高組C+語(yǔ)言試題 第 10 頁(yè)，共 13 頁(yè) 市，也認(rèn)為到達(dá)該城市的最短路徑長(zhǎng)度改變。對(duì)于每一個(gè)城市 i，假定只有第 i 個(gè)城市與外界交通中斷，輸出有多少個(gè) 城市會(huì)因此導(dǎo)致到首都

12、的最短路徑長(zhǎng)度改變。我們采用鄰接表的方式存儲(chǔ)圖的信息，其中 head_表示頂點(diǎn) _ 的第一條 邊的編號(hào)，ne_ti表示第 i 條邊的下一條邊的編號(hào)，pointi表示第 i 條邊的終點(diǎn)，weighti表示第 i 條邊的長(zhǎng)度。（第一空 2 分，其余 3 分）#include #include using namespace std; #define MA_N 6000 #define MA_M 100000 #define infinity 2147483647 int headMA_N, ne_tMA_M, pointMA_M, weightMA_M; int queueMA_N, distMA

13、_N, visitMA_N; int n, m, _, y, z, total = 0, answer; void link(int _,int y,int z) total+; ne_ttotal = head_; head_ = total; pointtotal = y; weighttotal = z; total+; ne_ttotal = heady; heady = total; pointtotal = _; weighttotal = z; int main int i, j, s, t; cin n m; for (i = 1; i _ y z; link(_, y, z)

14、; for (i = 1; i = n; i+) disti = infinity; (1) ; queue1 = 1; visit1 = 1; s = 1; CCF NOIP20_ 初賽提高組 C+語(yǔ)言試題 第 11 頁(yè)，共 13 頁(yè) t = 1; / 使用 SPFA 求出第一個(gè)點(diǎn)到其余各點(diǎn)的最短路長(zhǎng)度 while (s = t) _ = queues % MA_N; j = head_; while (j != 0) if ( (2) ) distpointj = dist_ + weightj; if (visitpointj = 0) t+; queuet % MA_N = pointj; visitpointj = 1; j = ne_tj; (3) ; s+; for (i = 2; i = n; i+) queue1 = 1; memset(visit, 0, sizeof(visit); visit1 = 1; s = 1; t = 1; while (s = t) / 判斷最短路長(zhǎng)度是否不變 _ = queues; j = head_; while (j != 0) if (pointj != i (4)