NOIP2017提高組初賽試題與答案

1、.專業(yè).專注 .NOIP2017 提高組初賽試題及答案一、單項選擇題 (共15 題，每題1.5 分，共計22.5 分；每題有且僅有一個正確選項 )1. 從( )年開始， NOIP 競賽將不再支持 Pascal 語言。CA. 2020 B. 2021 C. 2022 D. 20232. 在 8 位二進制補碼中 ， 10101011 表示的數(shù)是十進制下的 ( )。BA. 43 B. -85 C. -43 D.-843. 分辨率為 1600x900 、16 位色的位圖 ，存儲圖像信息所需的空間為 ( )。A A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB4.

2、 2017 年10月 1日是星期日 ，1949 年10月 1日是( )。CA. 星期三 B. 星期日 C. 星期六 D. 星期二5. 設(shè)G 是有n 個結(jié)點、m 條邊(n m的) 連通圖，必須刪去 G 的( )條邊，才能使得 G 變成一棵樹 。A A.m n+1 B. m-n C. m+n+1D.nm+16. 若某算法的計算時間表示為遞推關(guān)系式 ： T(N)=2T(N/2)+NlogN T(1)=1 則該算法的時間復(fù)雜度為( )。CA.O(N)B.O(NlogN)C.O(N log2N) D.O(N2)7. 表達式 a * (b + c) * d的后綴形式是()。BA. abcd*+*B. ab

3、c+*d*C. a*bc+*dD. b+c*a*d8. 由四個不同的點構(gòu)成的簡單無向連通圖的個數(shù)是( )。CA. 32 B. 35 C. 38D. 419. 將 7 個名額分給 4 個不同的班級 ，允許有的班級沒有名額 ，有( )種不同的分配方案 。DA. 60 B. 84 C. 96 D.12010. 若 f0=0, f1=1, fn+1=(fn+fn-1)/2，則隨著 i 的增大 ， fi將接近與 ( )。BA. 1/2 B. 2/3 D. 111. 設(shè) A和 B是兩個長為 n的有序數(shù)組 ，現(xiàn)在需要將 A和 B合并成一個排好序的數(shù)組 ，請問任何以元素比較作為基本運算的歸并算法 最壞情況下至

4、少要做 ( )次比較 。DA. n2B. NlognC. 2nD.2n-112. 在 n(n=3) 枚硬幣中有一枚質(zhì)量不合格的硬幣 (質(zhì)量過輕或質(zhì)量過重 )， 如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限 制， 下面是找出這枚不合格的硬幣的算法 。請把 a-c 三行代碼補全到算法中 。2. 將 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 then 任取 A中1枚硬幣與拿走硬幣比較

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

6、大 。令 Ci,j是從 a11 到 aij 的路徑上的數(shù)的最大和 ，并且 Ci,0=C0,j=0 ，則 Ci,j=( ) 。AA. maxCi-1,j-1,Ci-1,j+aijB. Ci-1,j-1+ci-1,j C. maxCi-1,j-1,Ci-1,j+1 D. maxCi,j-1,Ci-1,j+aijword 可編輯.專業(yè).專注 .14. 小明要去南美洲旅游 ， 一共乘坐三趟航班才能到達目的地 ，其中第 1 個航班準點的概率是 0.9，第 2 個航班準點的概率為 0.8，第3 個航班準點的概率為 0.9。如果存在第 i 個（ i=1,2 ）航班晚點 ，第 i+1 個航班準點 ，則小明將趕

7、不上第 i+1 個航班 ，旅行失敗 ；除了 這種情況 ，其他情況下旅行都能成功 。請問小明此次旅行成功的概率是 （ ）。DA. 0.5 B. 0.648 C. 0.72 D.0.7415. 歡樂噴球 ：兒童游樂場有個游戲叫 “歡樂噴球 ”，正方形場地中心能不斷噴出彩色乒乓球 ，以場地中 心為圓心還有一個圓軌道 ， 軌道上有一列小火車在勻速運動 ，火車有六節(jié)車廂 。假設(shè)乒乓球等概率落 到正方形場地的每個地點 ， 包括火車車廂 。小朋友玩這個游戲時 ，只能坐在同一個火車車廂里 ，可以 在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球 ，每個人每次游戲有三分鐘時間 ，則一個小朋友獨自玩 一次游戲期望可以得到

8、 （ ）個乒乓球 。假設(shè)乒乓球噴出的速度為 2 個/秒，每節(jié)車廂的面積是整個場地面 積的 1/20 。 CA. 60 B. 108 C. 18 D. 20二、不定項選擇題 （共 5 題，每題 1.5 分 ，共計 7.5 分；每題有一個或多個正確選項 ，多選或少選均不得分 ）1. 以下排序算法在最壞情況下時間復(fù)雜度最優(yōu)的有（ ）。CDA. 冒泡排序 B. 快速排序 C. 歸并排序 D. 堆排序2. 對于入棧順序為 a, b, c, d, e, f, g 的序列 ，下列 （）不可能是合法的出棧序列 。CA. a,b,c,d,e,f,gB. a,d,c,b,e,g,fC. a,d,b,c,g,f,e

9、D.g,f,e,d,c,b,a3. 下列算法中 ，（ ）是穩(wěn)定的排序算法 。D A. 快速排序B.堆排序 C.希爾排序 D. 插入排序4. 以下是面向?qū)ο蟮母呒壵Z言的是 （ ）。BDA. 匯編語言 B. C+ C. Fortan D. Java5. 以下和計算機領(lǐng)域密切相關(guān)的獎項是（ ）。BDA. 奧斯卡獎 B. 圖靈獎 C. 諾貝爾獎 D. 王選獎三、問題求解 （共 2 題 ，每題 5 分 ，共計 10 分 ）1. 如圖所示 ， 共有 13 個格子 。對任何一個格子進行一次操作 ，會使得它自己以及與它上下左右相鄰 的格子中的數(shù)字改變 （由 1 變 0， 或由 0 變 1）?，F(xiàn)在要使得所有的格

10、子中的數(shù)字都變?yōu)?，至少需要3 次操作 。 答案 3 2. 如圖所示 邊的代價是 是 9（3 分 ）。四、閱讀程序?qū)懡Y(jié)果 （共 4 題，每題 8 分，共計 32 分）1.輸入: 8 4#include輸出 :15using namespacestd;2.int g(int m, intn, int x)#includeint ans = 0;using namespacestd;int i;int main() if( n = 1)int n, i, j, x, y, nx, ny;return 1;int a4040;for (i=x; i =m/n; i+)for (i = 0; i 40

11、; i+)ans += g(m i, n-1, i);for (j = 0;j n;int t, m, n;y = 0; x = n-1;cin m n;n = 2*n-1;cout g(m, n, 0) endl;for (i = 1; i = n*n; i+)return 0; ayx =i;word 可編輯，A 到 B是連通的 。假設(shè)刪除一條細的邊的代價是 1，刪除一條粗的 2，要讓 A、B不連通 ，最小代價是 4 （2 分），最小代價的不同方案數(shù) （ 只要有一條刪除的邊不同 ，就是不同的方案 ）答案 4, 9.專業(yè).專注 .ny = (y-1+n)%n;cout a0j “”;nx =

12、 (x+1)%n;cout endl;if (y = 0 & x = n-1) | anynx !=0)return 0; y= y+1;輸入: 3else y = ny; x = nx;輸出:17 24 1 8 15for (j = 0; j n; j+)3.cout s endl;#includereturn 0;using namespacestd;int n, s,a100005, t100005, i;輸入:void mergesort(intl, int r)6if (l= r)2 6 3 4 5 1return;輸出 :8int mid = (l+ r) / 2;4.int p

13、= l;#includeint i = l;using namespacestd;int j = mid + 1 ；int main() mergesort (l, mid);int n, m;mergesort (mid + 1, r);cin n m;while (i = mid & j= r)int x = 1;if (aj ai)int y = 1;s += mid i+1;int dx = 1;tp = aj;int dy = 1;p+;int cnt = 0;j+; while (cnt != 2) else cnt = 0;tp = ai;x = x + dx;p+;y = y

14、+ dy;i+; if (x = 1 | x = n) while (i = mid)+cnt;tp = ai;dx = -dx; p+;if (y = 1 | y = m) i+; +cnt;while (j = r)dy = -dy; tp = aj;cout x y endl;p+;return 0;j+; for (i = l; i n;輸出 2: 2017 1(3 分 )for (i = 1; i ai;輸出 3: 1 321(3 分)mergesort (1, n);五、 完善程序 （共 2 題 ，每題 14 分， 共計 28 分）word 可編輯.專業(yè).專注 .1.大整數(shù)除法 ：

15、給定兩個正整數(shù) p和q，其中p不超過 10100 ，q不超過 100000 ，求p除以 q的商和余數(shù) 。（第一空 2分，其余3分） 輸入 ：第一行是 p 的位數(shù) n，第二行是正整數(shù) p ， 第三行是正整數(shù) q。輸出：兩行，分別是 p 除以 q的商和余數(shù) #include using namespacestd;int p100;int n, i, q,rest;char c;int main()cin n;for (i = 0; i c;pi = c 0 ；cin q;rest = p0;i = 1;rest = rest * 10 + pi;i+; if (rest q)cout 0 endl

16、;else cout rest / q;while (i n)rest = rest % q * 10 + pi; i+;cout rest / q;cout endl; cout rest % q endl; return 0; while (rest q& i n) 2.最長路徑 ：給定一個有向五環(huán)圖 ，每條邊長度為 1，求圖中的最長路徑長度 。（ 第五空 2 分，其余 3 分）輸入 ：第一行是結(jié)點數(shù) n（不超過 100 ）和邊數(shù) m，接下來 m 行，每行兩個整數(shù) a,b ，表示從結(jié)點 a 到結(jié)點 b 有一條有向邊 。結(jié)點標 號從 0 到（n-1）。輸出：最長路徑長度 。提示：先進行拓撲排

17、序 ，然后按照拓撲排序計算最長路徑 。#include tail+; head = 0;using namespacestd;int n, m, i, j,a, b, head, tail, ans;int graph100100; / 用鄰接矩陣存儲圖int degree100; / 記錄每個結(jié)點的入度int len100; / 記錄以各結(jié)點為終點的最長路徑長度int queue100; / 存放拓撲排序結(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;degreeb+; tail = 0;for (i = 0; i n; i+)if (degreei = 0) queuetail=