NOIP2022提高組C++初賽試題.doc

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

2、今有一只小老鼠反復(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 .0001 .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ù)中找最小數(shù)的最少運(yùn)算次數(shù)為 。.N .N-1 .N2 .log N 6.表達(dá)式

3、a_(b+c)-d 的后綴表達(dá)形式為 。.abcd_+- .abc+_d- .abc_+d- .-+_abcd 7.一棵二叉樹如右圖所示，假設(shè)采用二叉樹鏈表存儲(chǔ)該二叉 樹各個(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_ 初賽進(jìn)步組 C+語(yǔ)言試題 第 1 頁(yè)，共 13 頁(yè) 9.某計(jì)算機(jī)的 和內(nèi)存之間的地址總線寬度是 32 位bit，這臺(tái)計(jì)算機(jī)最 多可以使用 的內(nèi)存。

4、A.2GB B.4GB C.8GB D.16GB 10.有以下程序：#include using namespace std; int main int k = 4, n = 0; while (n 。假如 L 中存在 _ i1 _i+1 > > _n， 那么稱 L 是單峰的，并稱 _i 是 L 的 “峰頂”。如今 L 是單峰的，請(qǐng)把 a-c 三行代碼補(bǔ)全到算法中使得算法 正確找到 L 的峰頂。a.Search(k+1, n) b.Search(1, k-1) c.return Lk Search(1, n) 1.k n/2 2.if Lk > Lk-1 and Lk >

5、; 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, length1003; CCF NOIP20_ 初賽進(jìn)步組 C+語(yǔ)

6、言試題 第 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 - 1) + 2; len1 = lp

7、s(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_ 初賽進(jìn)步組 C+語(yǔ)言試題 第 7 頁(yè)，共 13 頁(yè) int n; void dfs(int node) vis

8、itnode = 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_00 #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 =

10、 l, j = r, temp; while (i _) j-; if ( (1) ) temp = ranki; ranki = rankj; rankj = temp; CCF NOIP20_ 初賽進(jìn)步組 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

11、 = heighti - heightpreviousi; 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_ 初賽進(jìn)步組C+語(yǔ)言試題 第 10 頁(yè)，共 13 頁(yè) 市，也認(rèn)為到達(dá)該城市的最短途徑長(zhǎng)度改變。對(duì)于每一個(gè)城市 i，假定只有第 i 個(gè)城市與外界

12、交通中斷，輸出有多少個(gè) 城市會(huì)因此導(dǎo)致到首都的最短途徑長(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; i

13、nt queueMA_N, distMA_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 >>

14、 m; for (i = 1; i > _ >> y >> z; link(_, y, z); for (i = 1; i <= n; i+) disti = infinity; (1) ; queue1 = 1; visit1 = 1; s = 1; CCF NOIP20_ 初賽進(jìn)步組 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) ) distpoint

15、j = 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) visitpointj = 0) (5) ; t+; queuet = pointj; j