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

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

2、位二進制補碼中，10101011表示的數(shù) 是十進制下的（）。A. 43 B. -85 C. -43 D.-843. 分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為（）。A. 2812.5KB B. 4218.75KB C.4320KB D. 2880KB4. 2017 年10月1日是星期日，1949年10月1日是（）。A.星期三 B. 星期日 C. 星期六 D.星期二5. 設(shè)G是有n個結(jié)點、m條邊（n w m）的連通圖，必須刪去G的（）條邊，才能使得G變成一棵樹。A. m- n + 1 B. m - nC. m + n+ 1 D. n - m + 16. 若某算法的計算時間

3、表示為遞推關(guān)系式：T（N） = 2T（N / 2） + N log NT（1） = 1則該算法的時間復雜度為()。A. 0(N) B. 0(N log N) C.O(Nlog2N)D. O(N 2 )7. 表達式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òu)成的簡單無向連通圖的個 數(shù)是（）。A. 32 B. 35 C. 38 D. 419將7個名額分給4個不同的班級，允許有 的班級沒有名額，有（）種不同的分配方案。A. 60 B. 84

4、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是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，請 問任何以元素比較作為基本運算的歸并算法最 壞情況下至少要做()次比較。2A. n B. n log n C. 2n D.2n-112. 在n (n 3 )枚硬幣中有一枚質(zhì)量不合格的硬幣(質(zhì)量過輕或質(zhì)量過重)，如果只有一架 天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算

5、法。請把a-c三行代碼補全到算法中。a. A J X U Yb. A J Zc. n J |A|算法 Coi n(A, n)1. k J?i/3?2. 將A中硬幣分成X，丫，Z三個集合，使 得| ?= | ?= ? ?= ?- 2?3. if ?半?W(X), W(Y) 分別為X或Y的重量4. the n5. else6. 7. if n2 then goto 18. if n=2 then任取A中1枚硬幣與拿走 硬幣比較，若不等，貝陀不合格；若相等，貝V A 中剩下的硬幣不合格.9. if n=1 then A中硬幣不合格正確的填空順序是()。A. b, c, a B. c, b, a C.

6、 c, a,b D. a, b, c13. 有正實數(shù)構(gòu)成的數(shù)字三角形排列形式如圖 所示。第一行的數(shù)為a 11 ;第二行的數(shù)從左到 右依次為a21 , a 22 ;第n行的數(shù)為a m , an2 ,ann。從a11開始，每一行的數(shù)a ij只 有兩條邊可以分別通向下一行的兩個數(shù)a (i+1)j 和a (i+1)(j+1) 。用動態(tài)規(guī)劃算法找 出一條從a 11向下通到a nl , a n2 ,a nn中某 個數(shù)的路徑，使得該路徑上的數(shù)之和達到最大。令Ci,j 是從a 11到aij的路徑上的數(shù)的最大 和，并且 Ci,O=CO,j=O, 則 Ci,j=（ ）。Gd i a a fe V 4 9 日則ij

7、A. maxCi-1,j-1, Ci-1,j + aB. Ci-1,j-1 + Ci-1,jC. maxCi-1,j-1, Ci-1,j + 1D. maxCi,j-1,Ci-1,j + a14. 小明要去南美洲旅游，一共乘坐三趟航班才 能到達目的地，其中第1個航班準點的概率是0.9，第2個航班準點的概率為0.8,第3個 航班準點的概率為0.9。如果存在第i個（i=1,2 ）航班晚點，第i+1個航班準點，則小 明將趕不上第i+1個航班，旅行失?。怀诉@ 種情況，其他情況下旅行都能成功。請問小明此 次旅行成功的概率是（）。A. 0.5B. 0.648C. 0.72D. 0.7415. 歡樂噴球：

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

9、，多選或少選均不得分）1. 以下排序算法在最壞情況下時間復雜度最優(yōu) 的有（）。A.冒泡排序B.快速排序C.歸并排序D.堆排序2. 對于入棧順序為 列，下列（A. a, b, c, d, e, f, ge, g, fC. a, d, b, c, g, f, ec, b, a3. 下列算法中，（A.快速排序 爾排序D.a, b, c, d, e, f, g的序）不可能是合法的出棧序列。B. a, d, c, b,D. g, f, e, d,）是穩(wěn)定的排序算法。B.堆排序插入排序C.希4. 以下是面向?qū)ο蟮母呒壵Z言的有（）A.匯編語言B. C+C. FortranD. Java5. 以下和計算機領(lǐng)域

10、密切相關(guān)的獎項有 （I ）。A.奧斯卡獎B.圖靈獎C.諾貝爾獎D.王選獎三、問題求解（共2 題，每題題5 分，共 計10 分）1. 如右圖所示，共有13個格子。對任何一個 格子進行一次操作，會使得它自己以及與它上下 左右相鄰的格子中的數(shù)字改變（由 1變0,或 由0變1）?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?0,至 少需要操作。T010100U11a2. 如下圖所示，A到B是連通的。假設(shè)刪除一 條細的邊的代價是1，刪除一條粗的邊的代價是2，要讓A、B不連通，最小代價是 （2分），最小代價的不同方案數(shù)是 （3分）。（只要有一條刪除的邊不同，就是不同 的方案）閱讀程序?qū)懡Y(jié)果（共4題，每題8 分，共計

11、32分）1.#in elude using n amespace std;int g(i nt 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, x, y, nx, ny;int a4040;for (i = 0; i 40; i+)for (j = 0; j n;y = 0; x = n - 1;n = 2 *

12、 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輸出： #include using namespace std; int n, s, a100005, t100005, i; void mergesort(int l, int r) if (l

13、= 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 = ai;p+;i+;while (j = r) tp = aj;p+;j+;for (i = l; i n;for (i = 1; i ai;mergesort(1,

14、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 = n） +cnt; dx = -dx;if （y = 1 | y = m） +cnt; dy = -dy;cout x y endl; return 0;

15、輸入 1： 4 3 輸出 1：（2 分）輸入 2： 2017 1014 輸出 2：（3 分）輸入 3： 987 321 輸出 3：（3 分）五、完善程序 （共 共 2 題，每題 14 分 ， 共計 28 分 ）1.（大整數(shù)除法）給定兩個正整數(shù)p和q, 其中p不超過10100 , q不超過100000,求p除 以q的商和余數(shù)。（第一空2分，其余3分） 輸入：第一行是p的位數(shù)n，第二行是正整數(shù) P，第三行是正整數(shù)q。輸出：兩行，分別是p除以q的商和余數(shù)。#in elude using n amespace std;int p100;int n, i, q, res t;char c;int mai

16、 n() cin n;for (i = 0; i c;pi = c - O;cin q;rest =(1);i = 1;while (2)& i n) rest = rest * 10 + pi;i+；if (rest q)cout 0 en dl;else cout (3);while (i n) rest =(4);i+;cout rest / q;cout en dl;cout (5) en dl;return 0;2.（最長路徑）給定一個有向無環(huán)圖，每條邊長度為1，求圖中的最長路徑長度。（第五空 2 分，其余 3 分）輸入：第一行是結(jié)點數(shù)n （不超過100 ）和邊數(shù) m接下來m行，每行

17、兩個整數(shù)a , b,表示從 結(jié)點 a 到結(jié)點 b 有一條有向邊。 結(jié)點標號從 0 到（n-1）。輸出：最長路徑長度。 提示：先進行拓撲排序， 然后按照拓撲序計算最 長路徑。#include using namespace std;int n, m, i, j, a, b, head, tail, ans;int graph100100; /用鄰接矩陣存儲圖記錄每個結(jié)點的入度記錄以各結(jié)點為終點的最長int degree100; / int len100; / 路徑長度int queue100; /存放拓撲排序結(jié)果int main() cin n m;for (i = 0; i n; i+)for

18、 (j = 0; j n; j+) graphij = 0；for (i = 0; i n; i+)degreei = 0;for (i = 0; i a b;graph ab = 1;Itail = 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 (graphqueuehead i = 1) (3)Iif (degreei = 0) queuetail = i;tail+;(4)1ans = 0;for (i = 0; i n; i+) a = queuei;len a = 1;for (j = 0; j len a)lena = len j + 1;if ( _(5)ans = len a;cout ans rest3(3)rest div qrest / q3(4)rest mod q * 10 + pirest %