NOIP2017初賽普及組C++試題

1、普與組語(yǔ)言試題競(jìng)賽時(shí)間：2017 年10月14日14:3016:30選手注意：試題紙共有7頁(yè)，答題紙共有2頁(yè)，滿分100分。請(qǐng)?jiān)诖?題紙上作答，寫在試題紙上的一律無(wú)效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或 查閱任何書籍資料。一、單項(xiàng)選擇題（共 20題，每題1.5分，共計(jì)30分；每題 有且僅有一個(gè)正確選項(xiàng)）1. 在8位二進(jìn)制補(bǔ)碼中，表示的數(shù)是十進(jìn)制下的（）。A. 43B. -85C. -43D. -842. 計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)的基本單位是（）。A.B.C.D.3. 下列協(xié)議中與電子郵件無(wú)關(guān)的是（）。A. 3B.C.D.4. 分辨率為800x600 、16位色的位圖，存儲(chǔ)圖像信息所需的

2、 空間為（）D.2880A. 937.5B. 4218.75 C. 43205. 計(jì)算機(jī)應(yīng)用的最早領(lǐng)域是（）A.數(shù)值計(jì)算 B.人工智能C.機(jī)器人D.過(guò)程控制6. 下列不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的是（）。A. CB.C.D.7. 的中文意思是（ ）。 中國(guó)信息學(xué)聯(lián)A. 賽 中國(guó)青少年信息學(xué)奧林匹C. 克競(jìng)賽2017 年 10 月 1 日是星8. 10 月 1 日是（A. 星期三 B. 星期日全國(guó)青少年信息學(xué)奧林匹B. 克競(jìng)賽中國(guó)計(jì)算機(jī)協(xié)D. 會(huì)1999 年）。C. 星期五 D. 星期二9. 甲、乙、丙三位同學(xué)選修課程，從 4 門課程中，甲選修 2 門，乙、丙各選修3 門，則不同的選修方案共有（

3、）種。2017 初賽普與組 語(yǔ)言試題第 1 頁(yè)，共 7 頁(yè)10設(shè)G是有n個(gè)結(jié)點(diǎn)、m條m ) 的【勺連通圖，必須刪去G ).邊（n w的（條邊，才能使得G變成一棵樹。A. m - n +C.m + n +D. n1B. m -n1m + 111.對(duì)于給定的序列,我們稱為逆序?qū)Ξ?dāng)且僅當(dāng)i < j且>把(i, j)那么序列 1, 7, 2, 3, 5, 4的逆序?qū)?shù)為（）個(gè)。A、C4B. 56D. 712 表達(dá)式 a * (b + c) * d的后綴.形式是（）。A. a b c d *B.a b c + *+ *d *C. a * b c +D.b + c * a* d* d36B.

4、4896D. 19213.向一個(gè)棧頂指針為的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)指針S指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）A.>=s;B.>=；=s;C.>=>；> =s;D.>=;=>.若串S = “”，其子串的個(gè)數(shù)是（）。DA. 72B. 45C. 463615十進(jìn)制小數(shù)13.375 對(duì)應(yīng)的二進(jìn).制數(shù)是（）。B.1101.DA. 1101.0111011.011C.101. 1010.0116對(duì)于入棧順序?yàn)?a, b, c, d, e, f, g的序）不可能是合法的.列，下列（出棧序列。a, b, c, d,a, d, c,b, e,A. e, f, gB.g, fa, d, b

5、, c,g, f, e, d, c,C. g, f, eD.b, a17. 設(shè) A 和 B 是兩個(gè)長(zhǎng)為 n 的有序數(shù)組，現(xiàn)在需要將 A 和 B 合并成一個(gè)排好序的數(shù)組，任何以元素比較作為基本運(yùn)算的 歸并算法在最壞情況下至少要做（）次比較。ABCD2n. n 2n n. 2n- 118從.（）年開始，競(jìng)賽將不再支持 語(yǔ)言。A 20BCD202. 202021. 2022319. 一家四口人，至少兩個(gè)人生日屬于同一月份的概率是（ ）（假定每個(gè)人生日屬于每個(gè)月份的概率相同且不同人之間相 互獨(dú)立）。A. 1/12 B. 1/144 C. 41/96D. 3/42017 初賽普與組 語(yǔ)言試題第 2 頁(yè)，

6、共 7 頁(yè)20.以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)是（）。A.奧斯卡獎(jiǎng)B.圖靈獎(jiǎng) C.諾貝爾獎(jiǎng) D.普利策獎(jiǎng)二、問(wèn)題求解（共2題，每題5分，共計(jì)10分）1. 一個(gè)人站在坐標(biāo)（0, 0 ）處，面朝 x軸正方向。第輪，他向前走1單位1 11J距離，然后右轉(zhuǎn)；第二輪，他向前走2單位距離，然后右轉(zhuǎn)；第三輪，他向前*a-11 1走3單位距離，然后右轉(zhuǎn)他一直 這么走下去。請(qǐng)問(wèn)第 2017輪后，他 的坐標(biāo)是：（,）。（請(qǐng)?jiān)诖痤}紙上用逗號(hào)隔開兩空答案）2.如右圖所示，共有13個(gè)格子。對(duì)任何一個(gè) 格子進(jìn)行一次操作，會(huì)使得它自己以與與 它上下左右相鄰的格子中的數(shù)字改變（由三、閱讀程序?qū)懡Y(jié)果（共 4題，每題8分，共計(jì)3

7、2分）1變0 ,或由0變1 ）o現(xiàn)在要使得所有的 格子中的數(shù)字都變?yōu)?0,至少需要次操 作。1. <>() t256;s； i；>> s;(i = 0; i < 256; ) ti=0；(i = 0; i < (); ) tsi;(i = 0; i < (); ) (tsi 1) << si << ; 0;<< "" << ; 0;2017 初賽普與組 語(yǔ)言試題 第 3 頁(yè)，共 7 頁(yè)輸入：輸出：2. <> ；g( m, n, x) = 0;i；(n 1) 1；(i = x

8、; i <= m / n; ) g(m - i, n - 1, i);() t, m, n;>> m >> n;<< g(m, n, 0) << ; 0;輸入：7 3輸出：3.<>();a200;b200;n, i, t,; >> ;n =();(i = 0; i < 200; ) bi=0;(i = 1; i <= n; ) ai = i- 1 - '0' bi = bi -1 + ai;= bn;2017 初賽普與組 語(yǔ)言試題 第 4 頁(yè)，共 7 頁(yè)t = 0;(i = n; i &g

9、t; 0; ) (ai0)(bi -1 + t < ) = bi -1 + t;<< << ;0;輸入：111001輸出：4.<>() n, m;>> n >> m;x = 1;y = 1;=1; = 1;=0;(2) = 0;x = X + ;y = y + ;(x 1 x n) ;一 5(y 1 y m) ;<< x << " " << y << ; 0;輸入 1 ：4 32017 初賽普與組 語(yǔ)言試題 第 5 頁(yè)，共 7頁(yè)輸出1 : （3分）輸入 2 :

10、2017 1014輸出2 : （5分）四、完善程序（共2題，每題14分，共計(jì)28分）1.（快速冪）請(qǐng)完善下面的程序，該程序使用分治法求m的值。（第一空2分，其余3分）輸入：三個(gè)不超過(guò) 10000 的正整數(shù)x， p， m。輸出：m的值。提示：若p為偶數(shù)，（x2）2;若p為奇數(shù)，*（x2）/2。<> ；x, p, m, i,；（）>> x >> p >> m;(1);(2)(p % 21)=(3)；p 2;x = (4)1 51 << ;0；2.（切割繩子）有n條繩子，每條繩子的長(zhǎng)度已知且均為正整 數(shù)。繩子可以以任意正整數(shù)長(zhǎng)度切割，但不可以連接?，F(xiàn)在 要從這些繩子中切割出 m條長(zhǎng)度相同的繩段，求繩段的最大長(zhǎng)度是多少。（第一、二空 2.5分，其余3分）輸入：第一行是一個(gè)不超過(guò) 100 的正整數(shù) n ，第二行 是 n 個(gè)不超過(guò) 10 6 的正整數(shù)，表示每條繩子的長(zhǎng)度，第三 行是一個(gè)不超過(guò) 10 8 的正整數(shù) m 。輸出：繩段的最大長(zhǎng)度，若無(wú)法切割，輸出 。<> ;n, m, i, , , , ; 100;繩子長(zhǎng)度2017 初賽普與組 語(yǔ)言試題第 6 頁(yè)，共 7 頁(yè)() >> n;=0；(i