noip2017提高組初賽試題及答案

1、NOIP2017提高組初賽試題及答案提高組初賽試題及答案一、單項(xiàng)選擇題（共一、單項(xiàng)選擇題（共15題，每題題，每題1.5分，共計(jì)分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）分；每題有且僅有一個(gè)正確選項(xiàng)）1.從()年開始，NOIP競賽將不再支持Pal語言。CA.2020B.2021C.2022D.20232.在8位二進(jìn)制補(bǔ)碼中，10101011表示的數(shù)是十進(jìn)制下的()。BA.43B.85C.43D.843.分辨率為1600x900、16位

2、色的位圖，存儲圖像信息所需的空間為()。AA.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2017年10月1日是星期日，1949年10月1日是()。CA.星期三B.星期日C.星期六D.星期二5.設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊(n≤m)的連通圖，必須刪去G的()條邊，才能使得G變成一棵樹。AA.m–n1B.mnC.mn1D.n–m16.若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式：T(N)=2T(N2)NlogNT(1)=1

3、則該算法的時(shí)間復(fù)雜度為()。CA.O(N)B.O(NlogN)C.O(Nlog2N)D.O(N2)7.表達(dá)式a(bc)d的后綴形式是()。BA.abcdB.abcdC.abcdD.bcad8.由四個(gè)不同的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是()。CA.32B.35C.38D.419.將7個(gè)名額分給4個(gè)不同的班級，允許有的班級沒有名額，有()種不同的分配方案。DA.60B.84C.96D.12010.若f[0]=0f[1]=1f[n1]=(f[

4、n]f[n1])2，則隨著i的增大，f[i]將接近與()。BA.12B.23D.111.設(shè)A和B是兩個(gè)長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組，請問任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做()次比較。DA.n2B.NlognC.2nD.2n112.在n(n=3)枚硬幣中有一枚質(zhì)量不合格的硬幣（質(zhì)量過輕或質(zhì)量過重），如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請把a(bǔ)c

5、三行代碼補(bǔ)全到算法中。2.將A中硬幣分成XYZ三個(gè)集合，使得|X|=|Y|=k|Z|=n2k3.ifW(X)≠W(Y)W(X)W(Y)分別為X或Y的重量4.then_______5.else_______6.__________7.ifn2thengoto18.ifn=2then任取A中1枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，則A中剩下的硬幣不合格9.ifn=1thenA中硬幣不合格正確的填空順序是()。DA.bcaB.cb

6、aC.cabD.abc13.在正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示，第一行的數(shù)為a11；第二行的數(shù)從左到右依次為a21a22…第n行的數(shù)為an1an2…，ann。從a11開始，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個(gè)數(shù)a(i1)j和a(i1)(j1)。用動(dòng)態(tài)規(guī)劃算法找出一條從a11向下通到an1an2…ann中某個(gè)數(shù)的路徑，使得該路徑上的數(shù)之和達(dá)到最大。令C[ij]是從a11到aij的路徑上的數(shù)的最大和，并且C[i0]=C[

7、0j]=0，則C[ij]=()。AA.maxC[i1j1]C[i1j]aijB.C[i1j1]c[i1j]C.maxC[i1j1]C[i1j]1D.maxC[ij1]C[i1j]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=12）航班晚點(diǎn)，第i1個(gè)航班準(zhǔn)點(diǎn)，則小明將趕不上第i1個(gè)航班，旅行失??；除了這種情況

8、，其他情況下旅行都能成功。請問小明此次旅行成功的概率是()。D輸出:172418153.#includeusingnamespacestdintnsa[100005]t[100005]ivoidmergest(intlintr)if(l==r)returnint=(lr)2intp=linti=lintj=1；mergest(l)mergest(1r)while(inf(i=1ia[i]mergest(1n)coutusingnames