(noip2017)二十三屆全國(guó)青少年信息學(xué)奧賽初賽試題及答案c++

1、第二十三屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組 C+語(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ǔ)碼中，10101011 表示的數(shù)是十進(jìn)制下的（ ）。A. 43      B. -85      C. -43   &#

2、160;  D. -842. 計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)的基本單位是（ ）。A. bit      B. Byte      C. GB      D. KB3.下列協(xié)議中與電子郵件無(wú)關(guān)的是（ ）。A. POP3      B. SMTP      C. WTO      D. IMAP4. 分辨率為 800x600、16 位色的位圖，存儲(chǔ)圖像信息所需的空間為（ ）。A. 937.5KB     &

3、#160;B. 4218.75KB      C. 4320KB      D. 2880KB5. 計(jì)算機(jī)應(yīng)用的最早領(lǐng)域是（ ）。A. 數(shù)值計(jì)算      B. 人工智能      C. 機(jī)器人      D. 過(guò)程控制6.下列不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的是（ ）。A. C      B. C+      C. Java      D. C#7. NOI 的

4、中文意思是（ ）。A. 中國(guó)信息學(xué)聯(lián)賽      B. 全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽C. 中國(guó)青少年信息學(xué)奧林匹克競(jìng)賽      D. 中國(guó)計(jì)算機(jī)協(xié)會(huì)8. 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。A. 星期三      B. 星期日      C. 星期五      D. 星期二9.甲、乙、丙三位同學(xué)選修課程，從 4 門課程中，甲選修 2 門，乙、丙各選修3門，則不同的選修方案共有（ ）種。A. 36 &#

5、160;    B. 48      C. 96      D. 19210. 設(shè) G 是有 n 個(gè)結(jié)點(diǎn)、m 條邊（n m）的連通圖，必須刪去 G 的（ ）條邊，才能使得 G 變成一棵樹。A. m n + 1      B. m - n      C. m + n + 1      D. n m + 111. 對(duì)于給定的序列ak，我們把 (i, j) 稱為逆序?qū)Ξ?dāng)且僅當(dāng) i < j 且 ai > aj。那么序列 1

6、, 7, 2, 3, 5, 4 的逆序?qū)?shù)為（ ）個(gè)。A. 4      B. 5      C. 6      D. 712. 表達(dá)式 a * (b + c) * d 的后綴形式是（ ）。A. a b c d * + *      B. a b c + * d *C. a * b c + * d      D. b + c * a * d13.向一個(gè)棧頂指針為 hs 的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)指針 s 指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（ ）。A.hs->ne

7、xt = s;B.s->next = hs; hs = s;C.s->next = hs->next; hs->next = s;D.s->next = hs; hs = hs->next;14. 若串 S = “copyright”，其子串的個(gè)數(shù)是（ ）。A. 72      B. 45      C. 46      D. 3615. 十進(jìn)制小數(shù) 13.375 對(duì)應(yīng)的二進(jìn)制數(shù)是（ ）。A. 1101.011      B. 1011.0

8、11      C. 1101.101      D. 1010.0116. 對(duì)于入棧順序?yàn)?a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出棧序列。A. a, b, c, d, e, f, g      B. a, d, c, b, e, g, fC. a, d, b, c, g, f, e      D. g, f, e, d, c, b, a17.設(shè) A 和 B 是兩個(gè)長(zhǎng)為 n 的有序數(shù)組，現(xiàn)在需要將 A 和 B 合并成一個(gè)排好序的數(shù)組，任何以

9、元素比較作為基本運(yùn)算的歸并算法在最壞情況下至少要做（ ）次比較。A.n2      B. n log n      C. 2n      D. 2n - 118. 從（ ）年開始，NOIP 競(jìng)賽將不再支持 Pascal 語(yǔ)言。A. 2020      B. 2021      C. 2022      D. 202319. 一家四口人，至少兩個(gè)人生日屬于同一月份的概率是（ ）（假定每個(gè)人生日屬于每個(gè)月份的概率相同且不

10、同人之間相互獨(dú)立）。A. 1/12      B. 1/144      C. 41/96      D. 3/420. 以下和計(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 單位距離，然后右轉(zhuǎn)；第二輪，他向前走

11、 2 單位距離，然后右轉(zhuǎn)；第三輪，他向前走 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ù)字改變（由 1 變 0，或由 0 變 1）?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?0，至少需要_次操作。三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1.#include using namespace std;int main() int t256; string s; int i;cin >>

12、s;for (i = 0; i < 256; i+) ti = 0;for (i = 0; i < s.length(); i+) tsi+;for (i = 0; i < s.length(); i+) if (tsi = 1) cout << si << endl; return 0;cout << "no" << endl; return 0;輸入：xyzxyw輸出：_2.#include using namespace std;int g(int m, int n, int x) int ans =

13、0;int i;if (n = 1) return 1;for (i = x; i <= m / n; i+) ans += g(m - i, n - 1, i); return ans; int main() int t, m, n; cin >> m >> n;cout << g(m, n, 0) << endl; return 0;輸入：7 3輸出：_3.#include using namespace std;int main() string ch; int a200; int b200;int n, i, t, res; cin

14、 >> ch;n = ch.length();for (i = 0; i < 200; i+) bi = 0;for (i = 1; i <= n; i+) ai = chi - 1 - '0' bi = bi - 1 + ai;res = bn;t = 0;for (i = n; i > 0; i-) if (ai = 0)t+;if (bi - 1 + t < res) res = bi - 1 + t;cout << res << endl; return 0;輸入：10011010110011011010111

15、10001輸出：_4.#include using namespace std;int main() int n, m;cin >> n >> m; int x = 1;int y = 1; int dx = 1; int dy = 1; int cnt = 0;while (cnt != 2) cnt = 0;x= x + dx;y= y + dy;if (x = 1 | x = n) +cnt;dx = -dx;if (y = 1 | y = m) +cnt;dy = -dy;cout << x << " " <&l

16、t; y << endl; return 0;輸入 1：4 3輸出 1：_（3 分）輸入 2：2017 1014輸出 2：_（5 分）四、完善程序（共 2 題，每題 14 分，共計(jì) 28 分）1.（快速冪）請(qǐng)完善下面的程序，該程序使用分治法求xp mod m 的值。（第一空 2 分，其余 3 分）輸入：三個(gè)不超過(guò) 10000 的正整數(shù) x，p，m。輸出：xp mod m 的值。提示：若 p 為偶數(shù)，xp=(x2)p/2；若 p 為奇數(shù)，xp=x*(x2)(p-1)/2。#include using namespace std;int x, p, m, i, re

17、sult;int main() cin >> x >> p >> m;result =          (1)         while (          (2)         ) if (p % 2 = 1)result =          (3)  

18、60;     p /= 2;x =          (4)         cout <<          (5)         << endl;return 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ò)106的正整數(shù)，表示每條繩子的長(zhǎng)度，第三行是一個(gè)不超過(guò)108的正整數(shù) m。輸出：繩段的最大長(zhǎng)度，若無(wú)法切割，輸出 Failed。#include using namespace std;int n, m, i, lbound, ubound, mid, count;int len100; / 繩子長(zhǎng)度int main() cin >> n; count = 0;for (i = 0; i < n; i+) cin &