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

1、第二十三屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組 C+ 語(yǔ)言試題競(jìng)賽時(shí)間： 2017 年 10 月 14 日 14:3016:30選手注意：試題紙共有 7 頁(yè)，答題紙共有 2 頁(yè)，滿(mǎn)分 100 分。請(qǐng)?jiān)诖痤}紙上作答，寫(xiě) 在試題紙上的一律無(wú)效。不得使用任何電子設(shè)備 （如計(jì)算器、手機(jī)、電子詞典等） 或查閱任何書(shū)籍資料。一、單項(xiàng)選擇題（共 20 題，每題 1.5 分，共計(jì) 30 分；每題有且僅有一個(gè)正確選項(xiàng)）1. 在 8 位二進(jìn)制補(bǔ)碼中， 表示的數(shù)是十進(jìn)制下的（ ）。A. 43 B. -85 C. -43 D. -842. 計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)的基本單位是（ ）。A. bit B. ByteC. GBD.

2、 KB3. 下列協(xié)議中與電子郵件無(wú)關(guān)的是（ ）。A. POP3B. SMTPC. WTOD. IMAP4. 分辨率為 800x600 、16 位色的位圖，存儲(chǔ)圖像信息所需的空間為（ ）。A. 937.5KB B. 4218.75KBC. 4320KBD. 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. JavaD. C#7. NOI 的中文意思是（ ）。A. 中國(guó)信息學(xué)聯(lián)賽 B. 全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽C. 中國(guó)青少年信息學(xué)奧林匹克競(jìng)賽 D. 中國(guó)計(jì)算機(jī)協(xié)

3、會(huì)8. 2017 年 10 月 1 日是星期日， 1999 年 10 月 1 日是（ ）。A. 星期三 B. 星期日 C. 星期五 D. 星期二9. 甲、乙、丙三位同學(xué)選修課程，從 4 門(mén)課程中，甲選修 2 門(mén)，乙、丙各選修 3 門(mén)，則不同的選修方案共有（ ）種。A. 36B. 48 C. 96 D. 19210. 設(shè) G 是有 n 個(gè)結(jié)點(diǎn)、 m 條邊（ n m）的連通圖，必須刪去 G 的（ ） 條邊，才能使得 G 變成一棵樹(shù)。A. m n + 1B. m - nC. m + n + 1D. n m + 111. 對(duì)于給定的序列 ak，我們把 （i, j） 稱(chēng)為逆序?qū)Ξ?dāng)且僅當(dāng) i < j

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

5、. s->next = hs; hs = hs->next;14. 若串 S = “ copyrigh，t 其”子串的個(gè)數(shù)是（ ）。A. 72B. 45 C. 46 D. 3615. 十進(jìn)制小數(shù) 13.375 對(duì)應(yīng)的二進(jìn)制數(shù)是（ ）。A. 1101.011B. 1011.011C. 1101.101 D. 1010.0116. 對(duì)于入棧順序?yàn)?a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出棧 序列。A. a, b, c, d, e, f, gB. a, d, c, b, e, g, fC. a, d, b, c, g, f, eD. g, f, e, d

6、, c, b, a17. 設(shè) A 和 B 是兩個(gè)長(zhǎng)為 n 的有序數(shù)組，現(xiàn)在需要將 A 和 B 合并成一個(gè)排 好序的數(shù)組，任何以元素比較作為基本運(yùn)算的歸并算法在最壞情況下至少要做 （ ） 次比較。A.n2 B. n log nC. 2nD. 2n - 118. 從( )年開(kāi)始， NOIP 競(jìng)賽將不再支持 Pascal 語(yǔ)言假定每個(gè)人生A. 2020B. 2021 C. 2022D. 202319. 一家四口人，至少兩個(gè)人生日屬于同一月份的概率是（ 日屬于每個(gè)月份的概率相同且不同人之間相互獨(dú)立）。A. 1/12 B. 1/144 C. 41/96 D. 3/420. 以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)

7、是（ ）。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)；第二輪，他向前走 2 單位距離， 然后右轉(zhuǎn)；第三輪，他向前走 3 單位距離，然后右轉(zhuǎn) 他一直這么走下去。 請(qǐng)問(wèn)第 2017 輪后，他的坐標(biāo)是： （ ， ）。（請(qǐng)?jiān)诖痤}紙上用逗號(hào)隔開(kāi)兩空答案）2. 如下圖所示，共有 13 個(gè)格子。對(duì)任何一個(gè)格子進(jìn)行一次操作，會(huì)使得它自己 以及與它上下左右相鄰的格子中的數(shù)字改變（由 1 變 0，或由 0 變 1）?，F(xiàn) 在要使得所有的格子中

8、的數(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 >> 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;cou

9、t << "no" << endl; return 0;輸入： xyzxyw輸出： 2.#include using namespace std;int g(int m, int n, int x) int ans = 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,

10、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 >> 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 &g

11、t; 0; i-) if (ai = 0)t+;if (bi - 1 + t < res) res = bi - 1 + t;cout << res << endl; return 0;輸入： 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 +

12、 dy;if (x = 1 | x = n) +cnt; dx = -dx;if (y = 1 | y = m) +cnt; dy = -dy;cout << x << " " << 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，

13、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, result;int main() cin >> x >> p >> m;result =(1) ;while ( (2) ) if (p % 2 = 1)result =(3) ;p /= 2;x = (4) ;cout << (5) << endl;return 0; 2.(切割繩子)有 n 條繩子，每條

14、繩子的長(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 ; if (count < m) ubound = mid - 1; else lbound = mid; cout << lbound << endl; return 0; 的正整 數(shù)，表示每條繩子的長(zhǎng)度，第三行是一個(gè)不超過(guò) 10 的正整數(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;