信息學(xué)競賽真題

1、一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）1.從()年開始，NOIP競賽將不再支持Pal語言。A.2020B.2021C.2022D.20232.在8位二進(jìn)制補(bǔ)碼中，10101011表示的數(shù)是十進(jìn)制下的()。A.43B.85C.43D.843.分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為()。A.2812.5KBB.4218.75KBC.4320KBD.2880KB4.201

2、7年10月1日是星期日，1949年10月1日是()。A.星期三B.星期日C.星期六D.星期二5.設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊(n≤m)的連通圖，必須刪去G的()條邊，才能使得G變成一棵樹。A.m–n1B.mnC.mn1D.n–m16.若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式：T(N)=2T(N2)NlogNT(1)=1則該算法的時(shí)間復(fù)雜度為()。A.O(N)B.O(NlogN)C.O(Nlog2N)D.O(N2)7.表達(dá)式a(bc)d的后綴形式是

3、()。A.abcdB.abcdC.abcdD.bcad8.由四個(gè)不同的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是()。A.32B.35C.38D.419.將7個(gè)名額分給4個(gè)不同的班級，允許有的班級沒有名額，有()種不同的分配方案。A.60B.84C.96D.12010.若f[0]=0f[1]=1f[n1]=(f[n]f[n1])2，則隨著i的增大，f[i]將接近與()。A.12B.23D.111.設(shè)A和B是兩個(gè)長為n的有序數(shù)組，現(xiàn)在需要將A和B合并

4、成一個(gè)排好序的數(shù)組，請問任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做()次比較。A.n2B.nlognC.2nD.2n1A.60B.108C.18D.20二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）1.以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有()。A.冒泡排序B.快速排序C.歸并排序D.堆排序2.對于入棧順序?yàn)閍bcdefg的序列，下列()不可能是合法的出棧序列。A.a

5、bcdefgB.adcbegfC.adbcgfeD.gfedcba3.下列算法中，()是穩(wěn)定的排序算法。A.快速排序B.堆排序C.希爾排序D.插入排序4.以下是面向?qū)ο蟮母呒壵Z言的是()。A.匯編語言B.CC.FtanD.Java5.以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎項(xiàng)是()。A.奧斯卡獎B.圖靈獎C.諾貝爾獎D.王選獎三、問題求解（共2題，每題5分，共計(jì)10分）1.如圖所示，共有13個(gè)格子。對任何一個(gè)格子進(jìn)行一次操作，會使得它自己以及與它上

6、下左右相鄰的格子中的數(shù)字改變(由1變0，或由0變1)?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?，至少需要3次操作。2.如圖所示，A到B是連通的。假設(shè)刪除一條細(xì)的邊的代價(jià)是1，刪除一條粗的邊的代價(jià)是2，要讓A、B不連通，最小代價(jià)是4(2分)，最小代價(jià)的不同方案數(shù)是9(3分)。（只要有一條刪除的邊不同，就是不同的方案）四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1.#includeusingnamespacestdintg(intmint