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

2、日是()。A.星期三B.星期日C.星期六D.星期二5 .設G是有n個結點、m條邊(n w m)的連通圖，必須刪去G的()條邊，才能使得G變 成一棵樹。A.m- n+1B. m-nC. m+n+1D.n - m+16.若某算法的計算時間表示為遞推關系式：T(N)=2T(N/2)+NlogNT(1)=1則該算法的時間復雜度為()。A.O(N) B.O(NlogN)C.O(N log2N) D.O(N2)7.表達式 a * (b + c) * d的后綴形式是()。A. abcd*+* B. abc+*d*C. a*bc+*d D. b+c*a*d8 .由四個不同的點構成的簡單無向連通圖的個數是()。

3、A. 32B. 35C. 38D. 419 .將7個名額分給4個不同的班級，允許有的班級沒有名額，有 ()種不同的分配方案。A. 60B. 84C. 96D.12010 .若 f0=0, f1=1, fn+1=(fn+fn-1)/2，則隨著 i 的增大，fi 將接近與()，A. 1/2B. 2/3D. 111.設A和B是兩個長為n的有序數組，現在需要將A和B合并成一個排好序的數組，請問任何以元素比較作為基本運算的歸并算法最壞情況下至少要做()次比較。A. n2B. nlogn C. 2n D.2n-112.在n(n>=3)枚硬幣中有一枚質量不合格的硬幣(質量過輕或質量過重)，如果只有一架

4、 天平可以用來稱重且稱重的硬幣數沒有限制，下面是找出這枚不合格的硬幣的算法。請把 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 或丫 的重量4. then5. else6. 7. if n>2 then goto 18. if n=2 then任取A中1枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，則 A中剩下的硬幣不合格9. if n=1 then A 中硬幣不合格正確的填空

5、順序是()。A. b,c,aB. c,b,aC. c,a,bD.a,b,c13 .在正實數構成的數字三角形排列形式如圖所示，第一行的數為 a11;第二行的數從左到 右依次為a21,a22。第n行的數為an1,an2,，ann。從a11開始，每一行的數aij只有兩條邊可以分別通向下一行的兩個數a(i+1)j和a(i+1)(j+1)。用動態規劃算法找出一條從a11向下通到an1,an2,ann中某個數的路徑，使得該路徑上的數之和達到最大。令Ci,j是從a11到aij的路徑上的數的最大和，并且Ci,0=C0,j=0,則Ci,j=()。A. maxCi-1,j-1,Ci-1,j+aijB. Ci-1,

6、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.5B. 0.648 C. 0.72D.0.7415 .歡樂噴球：兒童游樂場有個游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓 球，以場

7、地中心為圓心還有一個圓軌道，軌道上有一列小火車在勻速運動，火車有六節車廂。假設乒乓球等概率落到正方形場地的每個地點，包括火車車廂。小朋友玩這個游戲時，只能坐在同一個火車車廂里， 可以在自己的車廂里撿落在該車廂內的所有乒乓球，每個人每次游戲有三分鐘時間，則一個小朋友獨自玩一次游戲期望可以得到()個乒乓球。假設乒乓球噴出的速度為2個/秒，每節車廂的面積是整個場地面積的1/20。A. 60B. 108C. 18D. 20二、不定項選擇題（共 5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選 或少選均不得分）1.以下排序算法在最壞情況下時間復雜度最優的有（）A.冒泡排序B.快速排序C.

8、歸并排序D.堆排序2.對于入棧順序為a, b, c, d, e, f, g的序列，下列（）不可能是合法的出棧序歹U。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,a7 / 113.下列算法中,A.快速排序C.希爾排序（）是穩定的排序算法。B.堆排序D.插入排序4 .以下是面向對象的高級語言的是（）。A.匯編語言 B. C+ C. Fortan D. Java5 .以下和計算機領域密切相關的獎項是（）。A.奧斯卡獎B.圖靈獎 C.諾貝爾獎D.王選獎三、問題求解（共 2題，每題5分，共計10分）1 .如圖所示，共有13個

9、格子。對任何一個格子進行一次操作，會使得它自己以及與它上 下左右相鄰的格子中的數字改變 （由1變0,或由0變1）。現在要使得所有的格子中的數字都變為0,至少需要3次操作。2 .如圖所示，A到B是連通的。假設刪除一條細白邊的代價是 1 ,刪除一條粗的邊的代價是2,要讓A B不連通，最小代價是4 （2分），最小代價的不同方案數是9（3分）。（只要有一條刪除的邊不同，就是不同的方案）四、閱讀程序寫結果(共 4題，每題8分，共計32分)1.#includeusingnamespacestd 。int g(int m, intn, int x)intans = 0 inti if( n = 1)retu

10、rn 1for (i=xi <=m/no i+)ans += g(m - i, n-1, i)returnans 。int main() int t, m, n cin >> m >> n cout << g(m, n, 0) << endl return 0輸入：8 輸出：152.#include usingnamespacestd 。int main() int n, i, j, x, y, nx, ny。int a4040。for (i = 0。 i< 40 。 i+)for (j = 0。j< 40 o j+)aij=

11、0。cin >> 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 << endl 。return 0 。輸入：3輸出：17 24 1 8 153.#includeusingnamespacestd 。int n, s,a10000

12、5, t100005, i。voidmergesort(intl, int r)if (l = r)int mid = (l + r) / 2。int p = l 。inti = l 。cout << a0j<<return 。int j = mid + 1;mergesort (l, mid) 。mergesort (mid + 1, r) 。while (i <= mid && j<= r)if (aj < ai)s += mid-i+1 otp= aj。p+。j + + oelse tp= ai。p+。i+ owhile (i &

13、lt;= mid)tp = ai 。p+。i+ owhile (j <= r)tp = aj 。p+。j + + ofor (i = l 。i <= r 。 i+ )ai = ti 。int main() cin >> n 。for (i = 1。 i <= n 。 i+)cin>> ai 。mergesort (1, n) 。cout« s « endl 。return 0 。)輸入：6263451輸出：84.#includeusingnamespacestd 。int main() int n, m 。cin » n

14、» m 。int x = 1oint y = 1ointdx = 1ointdy = 1。intent = 0。while (ent != 2) ent = 0 ox = x + dx oy = y + dy 。if (x = 1 | x = n) +cnt odx = -dx o)if (y = 1 | y = m) +cnt ody = -dy 。)cout « x « "" « y« endl return 0 。)輸出1:1 3(2分)輸入 2: 2017 1014輸出 2: 2017 1 (3 分)輸入 3: 98

15、7 321輸出3: 1 321 (3分)五、完善程序(共 2題，每題14分，共計28分)1.大整數除法：給定兩個正整數p和q,其中p不超過10100, q不超過100000,求p除以q的商和余數。(第一空2分，其余3分)輸入：第一行是p的位數n,第二行是正整數 p,第三行是正整數 q。輸出：兩行，分別是 p除以q的商和余數。#includeusingnamespacestd 。int p100。int n, i, q,rest 。charc 。int main()cin >> n 。for (i = 0。 i < n 。 i+)cin >> c 。pi = c -

16、'0'cin >> q 。rest = p0。i = 1 。while (rest< q && i < n)rest = rest * 10 + pi 。i+ oif (rest < q)cout << 0 <<endl 。else cout << rest / q 。while (i < n)rest =rest % q * 10 + pi 。i+ ocout<< rest / q 。cout << endl 。cout << rest % q<&

17、lt; endl 。return 0 。2.最長路徑：給定一個有向五環圖，每條邊長度為1,求圖中的最長路徑長度。（第五空2分，其余3分）輸入：第一行是結點數 n （不超過100）和邊數日接下來m行，每行兩個整數 a,b ,表示從 結點a至ij結點b有一條有向邊。結點標號從0至iJ（n-1）。輸出：最長路徑長度。提示：先進行拓撲排序，然后按照拓撲排序計算最長路徑。#include usingnamespacestd 。int n, m, i, j,a, b, head, tail, ansint graph100100int degree100intlen100。int queue100。int

18、 main() cin >> n >> m 。/用鄰接矩陣存儲圖/記錄每個結點的入度/記錄以各結點為終點的最長路徑長度/存放拓撲排序結果for (i = 0。 i < n 。 i+)for (j = 0。j < n 。 j+)graphij= 0for (i = 0。 i < n。 i+)degreei =0。for (i = 0。 i < m 。 i+)cin>> a >>b 。graphab= 1degreeb+ 。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