noip提高組初賽歷年試題及答案求解題篇

1、NOIP提高組初賽歷年試題及答案求解題篇提高組初賽歷年試題及答案求解題篇問題求解題（每次問題求解題（每次2題，每題題，每題5分，共計(jì)分，共計(jì)10分。每題全部答對(duì)得分。每題全部答對(duì)得5分，沒有分，沒有部分分）注：答案在文末部分分）注：答案在文末提高組的問題求解題的知識(shí)點(diǎn)大多涉及計(jì)數(shù)問題、鴿巢原理、容斥問題、邏輯推理、遞推問題、排列組合問題等。NOIP20111平面圖可以畫在平面上，且它的邊僅在頂點(diǎn)上才能相交的簡(jiǎn)單無向圖。4個(gè)頂點(diǎn)的平面圖至

2、少有6條邊，如圖所示。那么，5個(gè)頂點(diǎn)的平面圖至多有_________條邊。NOIP20112定義一種字符串操作，一次可以將其中一個(gè)元素移到任意位置。舉例說明，對(duì)于字符串“BCA”可以將A移到B之前，變字符串“ABC”。如果要將字符串“DACHEBGIF”變成“ABCDEFGHI”最少需要_________次操作。NOIP20121.本題中，我們約定布爾表達(dá)式只能包含pqr三個(gè)布爾變量，以及“與”（∧）、“或”（∨）、“非”（）三種布爾運(yùn)

3、算。如果無論pqr如何取值，兩個(gè)布爾表達(dá)式的值總是相同，則稱它們等價(jià)。例如，(p∨q)∨r和p∨(q∨r)等價(jià)，p∨p和q∨q也等價(jià)；而p∨q和p∧q不等價(jià)。那么，兩兩不等價(jià)的布爾表達(dá)式最多有_________個(gè)。NOIP20122.對(duì)于一棵二叉樹，獨(dú)立集是指兩兩互不相鄰的節(jié)點(diǎn)構(gòu)成的集合。例如，圖1有5個(gè)不同的獨(dú)立集（1個(gè)雙點(diǎn)集合、3個(gè)單點(diǎn)集合、1個(gè)空集），葉為止。當(dāng)n=2時(shí)，平均一共跳2次；當(dāng)n=3時(shí)，平均一共跳2.5次。則當(dāng)n=5時(shí)

4、，平均一共跳_________次。NOIP20141.由數(shù)字112488所組成的不同的四位數(shù)的個(gè)數(shù)是_________。NOIP20142.如圖所示，圖中每條邊上的數(shù)字表示該邊的長(zhǎng)度，則從A到E的最短距離是_________。NOIP20151.在1和2015之間(包括1和2015在內(nèi))不能被4、5、6三個(gè)數(shù)任意一個(gè)數(shù)整除的數(shù)有_________個(gè)。NOIP20152.結(jié)點(diǎn)數(shù)為5的不同形態(tài)的二叉樹一共有_________種。(結(jié)點(diǎn)數(shù)為2