noip2022年初賽提高組試題及答案(c語(yǔ)言)

1、1/6NOIP2022試題及答案第十一屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題提高組C語(yǔ)言 二小時(shí)完成)全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效 一、單項(xiàng)選擇題(共10題，每題L5分，共計(jì)15分。每題有且僅有一個(gè)正確答案1、字符串“ababacbab”和字符串“abcba”的最長(zhǎng)公共子串是(A. abcba B. cba C. abc D. ab E. bcba2、設(shè)全集 I=a,b,c,d,e,fgh,集合 A=a,b,c,d,e,f, B=c,d,e, C=a,d,那么集合 ACBCC 為()。A.c,e B.d,e C.e D.c,d,e E.d,f3、以下二進(jìn)制數(shù)的值與十進(jìn)制

2、數(shù)23.456的值最接近的是(。A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.11114、完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4* N +3,那么它的葉結(jié)點(diǎn)個(gè)數(shù)為)。A2*N B. 2*N - 1C2*N+1D,2*N-2E2*N + 25、平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖G的頂點(diǎn)，每?jī)牲c(diǎn)之間的 直線距離是圖G中對(duì)應(yīng)邊的權(quán)值。圖G的最小生成樹中的全部邊的權(quán)值綜合為)。A. 8B.7+J? C. 9 D.6+J7 E. 4+2+ 41 +

3、石6、以下設(shè)備中沒(méi)有計(jì)算功能的是A.筆記本電腦B.掌上電腦 C.智能手機(jī) D.電子計(jì)算器E.液晶顯示器7、Intel的首顆64位處理器是(A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium8、常見(jiàn)的郵件傳輸效勞器使用()協(xié)議發(fā)送郵件。A.B. SMTP C. TCP D. FTP E. POP39、不能在Linux上使用的網(wǎng)頁(yè)掃瞄器是()oA. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla10、一位藝術(shù)史學(xué)家有20220幅1024 * 768的真彩色圖像，假設(shè)將這些圖像以位圖形式保存

4、在CD光盤上 (一張CD光盤的容量按600M計(jì)算)，大約需要()張CD光盤。A. 1 B. 10 C. 100 D. 1000 E. 10000二、不定項(xiàng)選擇題(共10題，每題1.5分，共計(jì)15分。多項(xiàng)選擇或少選均不得分)。11、設(shè)A=true, B = false, C = false, D = true,以下規(guī)律運(yùn)算表達(dá)式值為真的有)。A、(AAB)V(CAD) B、(AAB)VC)AD C、AA(BVC)VD)D、AA(BVC)VD E、(AVB)A(CVD)12、(3725)8 + (B)16 的運(yùn)算結(jié)果是13、二叉樹T的寬度優(yōu)先遍歷序列為ABCDEFGHL A是C的父結(jié)點(diǎn)，D是G的父

5、結(jié)點(diǎn)，F(xiàn)是I的父結(jié)點(diǎn)，樹中全部結(jié)點(diǎn)的最大深度為3 (根結(jié)點(diǎn)深度設(shè)為0),可知E的父結(jié)點(diǎn)可能是)。A. A B. B C. C D. D E. F14、設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e, f,g依次入棧，以下出棧序列不行能消滅的有()。A. a, b, c, e, d, f, gB. b, c, a, f, e, g, dC. a, e, c, b, d, f, gD. d, c, f, e, b, a, gE. g, e, f, d, c, b, a15、以下外設(shè)接口中可以通過(guò)無(wú)線連接的方式連接設(shè)備的是A. USB 2.0高速版 B.紅外 C.藍(lán)牙 D.串口 E. IEEE 802

6、.11g無(wú)線網(wǎng)卡16、處理器A每秒處理的指令數(shù)是處理器B的2倍。某一特定程序P分別編譯為處理器A和處理器B的指令，編譯結(jié)果處理器A的指令數(shù)是處理器B的4倍。程序P的算法時(shí)間簡(jiǎn)單度為O(n2),假設(shè)處理2/62/62/6NOIP2022試題及答案器A執(zhí)行程序P時(shí)能在一小時(shí)內(nèi)完成的輸入規(guī)模為小那么處理器B執(zhí)行程序P2/6NOIP2022試題及答案A. 4*nB.2*n C. n D. n / 2 E. n / 417、以下哪個(gè)些)不是計(jì)算機(jī)的輸出設(shè)備)。A.鼠標(biāo)B.顯示器C.鍵盤D.掃描儀 E.繪圖儀18、以下斷電之后將不能保存數(shù)據(jù)的有(JoA.硬盤B.存放器C.顯存D.內(nèi)存E.高速緩存19、以下

7、活動(dòng)中屬于信息學(xué)奧賽系列活動(dòng)的是)。A. N01P B. NOI C. 101 D.冬令營(yíng) E.國(guó)家隊(duì)選拔賽20、以下關(guān)于高級(jí)語(yǔ)言的說(shuō)法正確的有)。A. Ada是歷史上的第一個(gè)高級(jí)語(yǔ)言B. Pascal和C都是編譯執(zhí)行的高級(jí)語(yǔ)言C. C+是歷史上的第一個(gè)支持面對(duì)對(duì)象的語(yǔ)言D.編譯器將高級(jí)語(yǔ)言程序轉(zhuǎn)變?yōu)槟繕?biāo)代碼E.高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更簡(jiǎn)潔從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上三.問(wèn)題求解(請(qǐng)?jiān)诳崭裉幪钌洗鸢福靠?分，共計(jì)10分)1、將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的挨次排列，每次可以交換任意兩個(gè)元素， 最少需要交換次。2、取火柴玩耍的規(guī)章如

8、下：一堆火柴有N根，A、B兩人輪番取出。每人每次可以取1根或2根，最先沒(méi) 有火柴可取的人為敗方，另一方為勝方。假設(shè)先取者有必勝策略那么記為1,先取者沒(méi)有必勝策略記為0o 當(dāng)N分別為100, 200, 300, 400, 500時(shí)，先取者有無(wú)必勝策略的標(biāo)記挨次為 (回同意為一個(gè)由0和/或1組成的字符串)。四,閱讀程序(共4題，每題8分，共計(jì)32分)#includeint main int a, b, c, p, q, r3;scanf(d%d%d，&a, &b, &c);p = a / b / c;q = b- c + a + p; r0= a*p/q*q;rl = r0 * (r0 - 300

9、);if(3*q-p%3= r0 & r2 = r2)rl = rr0/p%2;elserl = q%p;printf(dn”, r0 - rl);return 0;)輸入：10073輸出：#include#includeint a50;void work(int p, int r)if(Pr)int i = p - 1, j, temp;for (j = p; j = ar) i+;temp = ai; ai = ajl; aj = temp;)temp = ai + 1; ai + 1 = ar; ar = temp;work(p, i);work(i + 2, r);3/6NOIP202

10、2試題及答案int main int n, i, sum = 0;scanf(d“，&n);for (i = 0; i n; i+) scanf(%d“，&(ai);work(0, n - 1);for (i = 0; i = 1; i)if (stri - 1 stri) break;if (i = 0) printffNo result!W);return 0;)for (j = 0; j i - 1; j+) putchar(strj);memset(chr, 0, sizeof(chr);for (j = i； j strfi - 1 & strfj mmin)mmin - strj;

11、chrstrj 1+;chrmmin - a-;chrstri - 1 /+;putchar(mmin);for(i = 0; i 26; i+)for(j = 0; j chrij; j+)putchar(i + a);putchar(n”)；return 0;)輸入：zzyzcccbbbaaa輸出:#includelong g(long k) if (k = 1) return k;return (2022 * g(k - 1) + 2022 * g(k - 2) % 2022;)int main longn；scanf(“l(fā)d“，&n);prin氓ldn, g(n);return 0;輸

12、入:20224/6NOIP2022試題及答案輸出:五.完善程序(前5空，每空2分，后6空，每空3分，共28分)1.木材加工題目描述：木材廠有一些原木，現(xiàn)在想把這些木頭切割成一些長(zhǎng)度一樣的小段木頭木頭有可能有剩余1需要得 到的小段的數(shù)目是給定了的。固然，我們期望得到的小段越長(zhǎng)越好，你的任務(wù)是計(jì)算能夠得到的小段木頭 的最大長(zhǎng)度。木頭長(zhǎng)度的單位是cm。原木的長(zhǎng)度都是正整數(shù)，我們要求切割得到的小段木頭的長(zhǎng)度也是正整數(shù)。輸入：第一行是兩個(gè)正整數(shù)N和K(1 W N W 1000(), 1 W K ( 10000), N是原木的數(shù)目，K是需要得到 的小段的數(shù)目。接下來(lái)的N行，每行有一個(gè)1到10000之間的正

13、整數(shù)，表示一根原木的長(zhǎng)度。輸出：輸出能夠切割得到的小段的最大長(zhǎng)度。假設(shè)連1cm長(zhǎng)的小段都切不出來(lái)，輸出0。輸入樣例：37232124456輸出樣例：114程序：#includeint n, k, len 10000;int isok(int t) int num = 0, i;for (i = 0; i = k) break;num =;)if ( )return 1;else return 0;)int main int i, left, right, mid;scanf(d%d“，&n, &k);right = 0;for (i = 0; i n; i+) scanf(d“，&(leni)

14、;if (right leni) right = leni;)right+;；while ( right)mid = (left + right) / 2;if ( )right = mid;else left = mid;printf C4%dn6 left);return 0;)2. N叉樹 題目描述:5/6NOIP20225/6NOIP2022試題及答案我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當(dāng)知道先根遍歷的結(jié)果和中根遍歷結(jié)果的時(shí)候， 我們可以唯一確實(shí)定二叉樹；同樣的，假設(shè)知道了后根遍歷的結(jié)果和中根遍歷結(jié)果，二叉樹也是唯一確定 的。但是假設(shè)只知道先根遍歷和后根遍歷的結(jié)果，二叉樹就

15、不是唯一的了。但是我們可以計(jì)算滿足條件的 不同二叉樹的一共有多少個(gè)。這不是一個(gè)很困難的問(wèn)題，略微簡(jiǎn)單一點(diǎn)，我們把這個(gè)問(wèn)題推廣到N 叉樹。我們用小寫英文字母來(lái)表示N叉樹的結(jié)點(diǎn)，不同的結(jié)點(diǎn)用不同的字母表示。比方，對(duì)于4叉樹，假設(shè) 先根遍歷的結(jié)果是abdefgc,后根遍歷的結(jié)果是defgbca,那么我們可以得到6個(gè)不同的4叉樹如以下 圖)。輸入：輸入數(shù)據(jù)包括3行。第一行是一個(gè)正整數(shù)N(1 W N W 20),表示我們要考慮N叉樹。其次行和第三行分別是兩個(gè)字符串序列，分別表示先根遍歷和后根遍歷的結(jié)果。輸出：輸出不同的N叉樹的數(shù)目。題目中給的數(shù)據(jù)保證得到的結(jié)果小于231。輸入樣例：4abdefgcdefgbca輸出樣例：6程序：#include#includechar strl100, str2100;int N;long com100100;long getcom(int x, int y) if (y = 0 | x = y) (D ;else if (comxy != 0) return comxy;else comxjyj = getcom(x - 1, y)+ ;return comxy; )long count(int a, int b, intc