第二十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽含答案重新整理排版

1、第二十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組 C+語言試題競賽時(shí)間：2017 年 10 月 14 日 14:3016:30(WORD重新整理排版)選手注意：試題紙共有 10 頁，答題紙共有 2 頁，滿分 100 分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共 15 題，每題 1.5 分，共計(jì) 22.5 分 ； 每題有且僅有一個(gè)正確選項(xiàng)）1. 從（ ）年開始，NOIP 競賽將不再支持 Pascal 語言。A. 2020 B. 2021 C. 2022 D. 20232. 在 8 位二進(jìn)制補(bǔ)碼中，10101

2、011 表示的數(shù)是十進(jìn)制下的（ ）。A. 43 B. -85 C. -43 D. -843. 分辨率為 1600 x900、16 位色的位圖，存儲(chǔ)圖像信息所需的空間為（ ）。A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB4. 2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。A. 星期三 B. 星期日 C. 星期六 D. 星期二5. 設(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 +

3、16. 若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式：T(N) = 2T(N / 2) + N log NT(1) = 1則該算法的時(shí)間復(fù)雜度為（ ）。A. O(N) B. O(N log N) C. O(Nlog2N) D. O(N2 )7. 表達(dá)式 a * (b + c) * d 的后綴形式是（ ）。A. a b c d * + * B. a b c + * d * C. a * b c + * d D. b + c * a * d8. 由四個(gè)不同的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是（ ）。A. 32 B. 35 C. 38 D. 419. 將 7 個(gè)名額分給 4 個(gè)不同的班級(jí)，允許有的班級(jí)沒有名額，有

4、（ ）種不同的分配方案。A. 60 B. 84 C. 96 D. 12010. 若 f0 = 0, f1 = 1, fn + 1 = (fn + fn - 1) / 2，則隨著 i 的增大，fi將接近于（ ）。A. 1/2 B. 2/3 C.(sqrt(5) 1)/2 D. 111. 設(shè) A 和 B 是兩個(gè)長為 n 的有序數(shù)組，現(xiàn)在需要將 A 和 B 合并成一個(gè)排好序的數(shù)組，請(qǐng)問任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做（ ）次比較。A. n2 B. n log n C. 2n D. 2n-112. 在 n（n 3）枚硬幣中有一枚質(zhì)量不合格的硬幣（質(zhì)量過輕或質(zhì)量過重），如果只有一架

5、天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請(qǐng)把 a-c 三行代碼補(bǔ)全到算法中。a. A XYb. A Zc. n |A|算法 Coin(A, n)1. kn/32. 將 A 中硬幣分成 X，Y，Z 三個(gè)集合，使得| = | = ,| = 23. if () () /W(X), W(Y)分別為 X 或 Y 的重量4. then _5. else _6. _7. if n2 then goto 18. if n=2 then 任取 A 中 1 枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，則 A 中剩下的硬幣不合格.9. if n=1 then A 中硬幣不合格

6、正確的填空順序是（ ）。A. b, c, a B. c, b, a C. c, a, b D. a, b, c13. 有正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示。第一行的數(shù)為 a 11 ；第二行的數(shù)從左到右依次為a21 , a22 ；第 n 行的數(shù)為 an1 , an2 , , ann 。從 a11開始，每一行的數(shù) aij 只有兩條邊可以分別通向下一行的兩個(gè)數(shù) a (i+1)j 和 a (i+1)(j+1) 。用動(dòng)態(tài)規(guī)劃算法找出一條從 a11 向下通到 an1 , an2 , , ann 中某個(gè)數(shù)的路徑，使得該路徑上的數(shù)之和達(dá)到最大。令 Ci,j是從 a11 到 aij 的路徑上的數(shù)的最大和，并

7、且 Ci,0=C0,j=0,則 Ci,j=（ ）。A. maxCi-1,j-1, Ci-1,j + aijB. Ci-1,j-1 + Ci-1,jC. maxCi-1,j-1, Ci-1,j + 1D. maxCi,j-1,Ci-1,j + aij14. 小明要去南美洲旅游，一共乘坐三趟航班才能到達(dá)目的地，其中第 1 個(gè)航班準(zhǔn)點(diǎn)的概率是 0.9，第 2 個(gè)航班準(zhǔn)點(diǎn)的概率為 0.8, 第 3 個(gè)航班準(zhǔn)點(diǎn)的概率為0.9。如果存在第 i 個(gè)（i=1,2）航班晚點(diǎn)，第 i+1 個(gè)航班準(zhǔn)點(diǎn)，則小明將趕不上第 i+1 個(gè)航班，旅行失?。怀诉@種情況，其他情況下旅行都能成功。請(qǐng)問小明此次旅行成功的概率是（

8、）。A. 0.5 B. 0.648 C. 0.72 D. 0.7415. 歡樂噴球：兒童游樂場有個(gè)游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一個(gè)圓形軌道，軌道上有一列小火車在勻速運(yùn)動(dòng)，火車有六節(jié)車廂。假設(shè)乒乓球等概率落到正方形場地的每個(gè)地點(diǎn)，包括火車車廂。小朋友玩這個(gè)游戲時(shí)，只能坐在同一個(gè)火車車廂里，可以在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球，每個(gè)人每次游戲有三分鐘時(shí)間，則一個(gè)小朋友獨(dú)自玩一次游戲期望可以得到（ ）個(gè)乒乓球。假設(shè)乒乓球噴出的速度為 2 個(gè)/秒，每節(jié)車廂的面積是整個(gè)場地面積的 1/20。A. 60 B. 108 C. 18 D. 20二 、 不

9、定項(xiàng)選擇題（共 5 題，每題 1.5 分，共計(jì) 7.5 分 ；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分 ）1. 以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有（ ）。A. 冒泡排序 B. 快速排序 C. 歸并排序 D. 堆排序2. 對(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, a3. 下列算法中，（ ）是穩(wěn)定的排序算法。A. 快速排序 B. 堆排序 C. 希爾排序 D

10、. 插入排序4. 以下是面向?qū)ο蟮母呒?jí)語言的有（ ）。A. 匯編語言 B. C+ C. Fortran D. Java5. 以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)有（ ）。A. 奧斯卡獎(jiǎng) B. 圖靈獎(jiǎng) C. 諾貝爾獎(jiǎng) D. 王選獎(jiǎng)三、 問題求解（共 2 題，每題 題 5 分，共計(jì) 10 分）1. 如右圖所示，共有 13 個(gè)格子。對(duì)任何一個(gè)格子進(jìn)行一次操作，會(huì)使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變（由 1 變 0，或由 0 變 1）。現(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?0，至少需要_次操作。2. 如下圖所示，A 到 B 是連通的。假設(shè)刪除一條細(xì)的邊的代價(jià)是 1，刪除一條粗的邊的代價(jià)是 2，要讓

11、 A、B 不連通，最小代價(jià)是_（2 分），最小代價(jià)的不同方案數(shù)是_（3 分）。（只要有一條刪除的邊不同，就是不同的方案）四 、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1.#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;cout g(m, n, 0) endl;return 0;輸入：8 4輸出：_2.#include using namespace std;int main() int n, i, j,

12、x, y, nx, ny;int a4040;for (i = 0; i 40; i+)for (j = 0; j n;y = 0; x = n - 1;n = 2 * n - 1;for (i = 1; i = n * n; i+) ayx = i;ny = (y - 1 + n) % n;nx = (x + 1) % n;if (y = 0 & x = n - 1) | anynx != 0)y = y + 1;else y = ny; x = nx; for (j = 0; j n; j+)cout a0j ;cout endl;return 0;輸入： 3輸出：_3.#include

13、using namespace std;int n, s, a100005, t100005, i;void mergesort(int l, int r) if (l = r)return;int mid = (l + r) / 2;int p = l;int i = l;int j = mid + 1;mergesort(l, mid);mergesort(mid + 1, r);while (i = mid & j = r) if (aj ai) s += mid - i + 1;tp = aj;p+;j+;else tp = ai;p+;i+;while (i = mid) tp =

14、ai;p+;i+;while (j = r) tp = aj;p+;j+;for (i = l; i n;for (i = 1; i ai;mergesort(1, n);cout s endl;return 0;輸入：62 6 3 4 5 1輸出：_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

15、= n) +cnt;dx = -dx;if (y = 1 | y = m) +cnt;dy = -dy;cout x y endl;return 0;輸入1： 4 3輸出1：_（2分）輸入2：2017 1014輸出2：_（3分）輸入3： 987 321輸出3：_（3分）五、完善程序 （共 共 2 題，每題 14 分 ， 共計(jì) 28 分 ）1. （ 大整數(shù)除法） ）給定兩個(gè)正整數(shù)p和q，其中p不超過10100 ，q不超過100000，求 p 除以 q 的商和余數(shù)。（第一空 2 分，其余 3 分）輸入：第一行是 p 的位數(shù) n，第二行是正整數(shù) p，第三行是正整數(shù) q。輸出：兩行，分別是 p 除以

16、q 的商和余數(shù)。#include using namespace std;int p100;int n, i, q, rest;char c;int main() cin n;for (i = 0; i c;pi = c - 0;cin q;rest = (1) ;i = 1;while ( (2) & i n) rest = rest * 10 + pi;i+;if (rest q)cout 0 endl;else cout (3) ;while (i n) rest = (4) ;i+;cout rest / q;cout endl;cout (5) endl;return 0;2. （

17、最長路徑 ）給定一個(gè)有向無環(huán)圖，每條邊長度為 1，求圖中的最長路徑長度。（第五空 2 分，其余 3 分）輸入：第一行是結(jié)點(diǎn)數(shù) n（不超過 100）和邊數(shù) m，接下來 m 行，每行兩個(gè)整數(shù) a，b，表示從結(jié)點(diǎn) a 到結(jié)點(diǎn) b 有一條有向邊。結(jié)點(diǎn)標(biāo)號(hào)從 0 到(n-1)。輸出：最長路徑長度。提示：先進(jìn)行拓?fù)渑判颍缓蟀凑胀負(fù)湫蛴?jì)算最長路徑。#include using namespace std;int n, m, i, j, a, b, head, tail, ans;int graph100100; / 用鄰接矩陣存儲(chǔ)圖int degree100; / 記錄每個(gè)結(jié)點(diǎn)的入度int len100;

18、 / 記錄以各結(jié)點(diǎn)為終點(diǎn)的最長路徑長度int queue100; / 存放拓?fù)渑判蚪Y(jié)果int main() cin n m;for (i = 0; i n; i+)for (j = 0; j n; j+)graphij = 0;for (i = 0; i n; i+)degreei = 0;for (i = 0; i a b;graphab = 1; (1) ;tail = 0;for (i = 0; i n; i+)if ( (2) ) queuetail = i;tail+;head = 0;while (tail n - 1) for (i = 0; i n; i+)if (graphq

19、ueuehead i = 1) (3) ;if (degreei = 0) queuetail = i;tail+; (4) ;ans = 0;for (i = 0; i n; i+) a = queuei;lena = 1;for (j = 0; j lena)lena = lenj + 1;if ( (5) )ans = lena;cout ans endl;return 0;第二十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組參考答案一、單項(xiàng)選擇題（共15 題，每題1.5 分，共計(jì)22.5 分）12345678CBACACBC9101112131415DBDDADC二、不定項(xiàng)選擇題（共5 題，