NOIP2017全國青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽精彩試題問題詳解

1、NOIP 2017全國青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽試題答案一、單項選擇題(共 15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項)1. 從()年開始，NOIP競賽將不再支持 Pascal語言。A. 2020 B.2021 C.2022 D.20232. 在8位二進制補碼中，10101011表示的數(shù)是十進制下的()。A. 43B. -85C. -43D.-843. 分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為 ()。A. 2812.5KBB. 4218.75KBC. 4320KBD.2880KB4. 2017年10月1日是星期日，1949年10月1日是()

2、。A.星期三B.星期日C.星期六D.星期二5. 設(shè)G是有n個結(jié)點、m條邊(n =3)枚硬幣中有一枚質(zhì)量不合格的硬幣(質(zhì)量過輕或質(zhì)量過重)，如果只有一架 天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請把 a-c三行代碼補全到算法中。a. AXUYb. AZc. n|A|算法 Coin(A,n)1. kn/32. 將A中硬幣分成X,Y,Z三個集合，使得|X|=|Y|=k, |Z|=n-2k3. if W(X) 工 W(Y) /W(X), W(Y) 分別為 X 或 Y 的重量4. then5. else6. 7. if n2 then goto 18. if n=2 t

3、hen 任取A中1枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，則A中剩下的硬幣不合格9. if n=1 then A中硬幣不合格正確的填空順序是()。A. b,c,aB. c,b,aC. c,a,bD.a,b,c13. 在正實數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示，第一行的數(shù)為a11;第二行的數(shù)從左到右依次為a21,a22;第n行的數(shù)為an 1,an2,，ann。從a11開始，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個數(shù)a(i+1)j和a(i+1)(j+1)。用動態(tài)規(guī)劃算法找出一條從 all向下通到an 1,an2,ann中某個數(shù)的路徑，使得該路徑上的數(shù)之和達到最大。令Ci,j是從a

4、ll到aij的路徑上的數(shù)的最大和， 并且Ci,O=CO,j=O,則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. 小明要去南美洲旅游，一共乘坐三趟航班才能到達目的地，其中第1個航班準點的概率是0.9，第2個航班準點的概率為 0.8,第3個航班準點的概率為0.9。如果存在第i個(i=1,2 )航班晚點，第i+1個航班準點，則小明將趕不上第i+1個航班，旅行失??；除了這種情況，其他情況下旅行都能成功。請問小明此次旅行成功的概率是()。A. 0.5

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

6、5分；每題有一個或多個正確選項，多選 或少選均不得分)1.以下排序算法在最壞情況下時間復(fù)雜度最優(yōu)的有()A.冒泡排序B.快速排序C.歸并排序D.堆排序2.對于入棧順序為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,c,b,a()是穩(wěn)定的排序算法。B.堆排序D.插入排序3. 下列算法中,A.快速排序C.希爾排序4. 以下是面向?qū)ο蟮膯J級語言的是 （）。A.匯編語言B. C+C. Fortan D. Java5. 以下和計算機領(lǐng)域密切相關(guān)的獎項是 （）

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

8、acestd;int g（i nt m, intn, int x）int ans = 0;int i;if（ n = 1）return 1;for （i=x; i m n;cout g（m, n, 0） en dl;return 0;輸入：84輸出:152.#i ncludeusing n amespacestd;int mai n() 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*n-1;for (i = 1; i = n*n; i+)ayx =i;ny

9、 = (y-1+ n)%n;nx = (x+1)% n;if (y = 0 & x = n-1) | anynx !=0)y= y+1;else y = ny; x = n x;for (j = 0; j n; j+)cout a0jcout en dl;return 0;輸入:3輸出：17 24 1 8 153.#i ncludeusing n amespacestd;int n, s,a100005, t100005, i;void mergesort(i ntl, int r)if (l = r)return;int mid = (l + r) / 2;int p = l;int i =

10、 l;int j = mid + 1;mergesort (l, mid); mergesort (mid + 1, r); while (i = mid & j= r)if (aj ai)i+1;aj;P+；j+； else ai;s += midtp=tp=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, n);cout s n m;int x = 1;int y = 1;int dx = 1;int dy = 1;in

11、t ent = 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 n;for （i = 0; i c;pi = c - 0;cin q;rest = p0;i = 1;while （rest q & i n）rest = rest * 10 + pi;i+;if (rest q)else cout 0 e ndl;cout rest / q; while (i n)rest % q * 10 + p

12、i;rest / q;cout rest % q en dl;return 0;cout en dl;rest =i+;cout n m;for (i = 0; i n; i+)for (j = 0;j n; j+)/記錄每個結(jié)點的入度/記錄以各結(jié)點為終點的最長路徑長度存放拓撲排序結(jié)果graphij= 0;for (i = 0; i n; i+)degreei =0;for (i = 0; i a b;graphab= 1; degreeb+;tail = 0;for (i = 0; i n; i+)if (degreei = 0)queuetail= i;tail+;head = 0;while (tail n-1)for (i = 0;i n; i+)if(graphqueuehea