歷屆NOIP問(wèn)題求解及答案

歷屆問(wèn)題求解NOIP1998普及二、問(wèn)題求解：（20%）已知一個(gè)數(shù)列U,U,U，…，U，…往往可以找到一個(gè)最小的K1值和K個(gè)數(shù)a,a,…，a使得數(shù)1 2 k列從某項(xiàng)開(kāi)始都滿足：U=aU+aU+ +aUN+K1N+K-1 2N+K-2 kN（A）例如對(duì)斐波拉契數(shù)列1，1，2,3,5，…可以發(fā)現(xiàn)：當(dāng)K=2,a1=1,a2=1時(shí)，從第3項(xiàng)起（即N>=1）都滿足U；=Un+1+U：。試對(duì)數(shù)列12,22,32,…，n2,…求K和a1,na2,"…，aK使得（A）式成立。{7%} 12 '某班有50名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫(xiě)a,b,c三本書(shū)的書(shū)名，將讀過(guò)的書(shū)打，結(jié)果統(tǒng)計(jì)數(shù)字如下：只讀a者8人；只讀b者4人；只讀c者3人；全部讀過(guò)的有2人；讀過(guò)a,b兩本書(shū)的有4人；讀過(guò)a,c兩本書(shū)的有2人；讀過(guò)b,c兩本書(shū)的有3人；{6%}（1）讀過(guò)a的人數(shù)是 （2）一本書(shū)也沒(méi)有讀過(guò)的人數(shù)是任給自然數(shù)n,k,1WKW9，按如下計(jì)算步驟求序列XX1……X0的步驟：{8%}JJt3j=0NOIP1999普及二、回答問(wèn)題（10分）(2)如果N>=K則轉(zhuǎn)第3步，否則轉(zhuǎn)第7步(3)X=NMODK {div表示整數(shù)除法，結(jié)果取整數(shù)；(4)N =N DIV Kmod表示整除取余數(shù)}(5)j=j+1(6)回第2步(7)X=N(8)結(jié)束試求當(dāng)：N=1998,K=3時(shí)，XX]……X。之值。TOC\o"1-5"\h\zNOIP1998提高 JJ-1 0二、問(wèn)題求解：（21%）1、已知一個(gè)數(shù)列U,U,U，…U，…往往可以找到1 2 3 n一個(gè)最小的k值和k個(gè)數(shù)a,a，…，a，使得數(shù)列從某項(xiàng)開(kāi)始都滿足： 1 2ku=au+au +???+au （A）n+k1n+k—12n+k—2 kn例如對(duì)斐波拉契數(shù)列1,1,2,3,5,…可以發(fā)現(xiàn)：當(dāng)k=2,a1=1,a2=1時(shí)，從第3項(xiàng)起（即nN1）都滿足u2=u1+uo試對(duì)數(shù)列13,23,33,…，n3,…求k和a,a，…，氣使得（A）成立。 （8%） 1 2k2、給出一棵二叉樹(shù)的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA畫(huà)出此二叉樹(shù)。（8%）在磁盤(pán)的目錄結(jié)構(gòu)中，我們將與某個(gè)子目錄有關(guān)聯(lián)的目錄數(shù)稱為度。例如下圖該圖表達(dá)了A盤(pán)的目錄結(jié)構(gòu)：D1,Dll,…，D2均表示子目錄的名字。在這里，根目錄的度為2,D1子目錄的度為3,D11子目錄的度為4,D12,D2,D111,D112,D113的度均為1。不考慮子目錄的名字，則可簡(jiǎn)單的圖示為如下所示的樹(shù)結(jié)構(gòu)：若知道一個(gè)磁盤(pán)的目錄結(jié)構(gòu)中，度為2的子目錄有2個(gè)，度為3的子目錄有1個(gè)，度為4的子目錄有3個(gè)。試問(wèn)：度為1的子目錄有幾個(gè)？三、公式推導(dǎo)（10分）根據(jù)Nocomachns定理，任何一個(gè)正整數(shù)n的立方一定可以表示成n個(gè)連續(xù)的奇數(shù)的和。例如：13=123=3+533=7+9+1143=13+15+17+19在這里，若將每一個(gè)式中的最小奇數(shù)稱為X,那么當(dāng)給出n之后，請(qǐng)寫(xiě)出X與n之間的關(guān)系表達(dá)式：NOIP1999提高二、回答問(wèn)題（10分）將Ln定義為求在一個(gè)平面中用n條直線所能確定的最大區(qū)域數(shù)目。例如：當(dāng)n=1時(shí)，L=2，進(jìn)一步考慮，用n條折成角的直線（角度任意），放在平面上，能確定的最大區(qū)域數(shù)目Zn是多少？例如：當(dāng)n=1時(shí)，Z1=2（如下圖所示）/ 當(dāng)給出n后，請(qǐng)寫(xiě)出以下的表達(dá)式：Ln= 2 Zn=

NOIP2000普及二、問(wèn)題解答：（每題7分，共14分）已知，按中序遍歷二叉樹(shù)的結(jié)果為：abc問(wèn)：有多少種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果，并畫(huà)出這些二叉樹(shù)。有2Xn的一個(gè)長(zhǎng)方形方格，用一個(gè)1X2的骨牌鋪滿方格。例如n=3時(shí)，為2X3方格。此時(shí)用一個(gè)1X2的骨牌鋪滿方格，共有3種鋪法：試對(duì)給出的任意一個(gè)n（n〉0），求出鋪法總數(shù)的遞推公式。NOIP2000提高二.問(wèn)題求解：（6+6=12分）已知，按中序遍歷二叉樹(shù)的結(jié)果為：abc問(wèn)：有多少種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果，并畫(huà)出這些二叉樹(shù)。設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走1級(jí)，也可走2級(jí)，也可走3級(jí)，用遞推公式給出某人從底層開(kāi)始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即1+1+1，1+2，2+1，3。NOIP2001普及在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是：（1） a,b兩樣至少有一樣（2） a,d不能同時(shí)取NOIP2002普及二.問(wèn)題求解：如下圖，有一個(gè)無(wú)窮大的的棧S,在棧的右邊排列著1,2,3,4,5共五個(gè)車(chē)廂。其中每個(gè)車(chē)廂可以向左行走，也可以進(jìn)入棧S讓后面的車(chē)廂通過(guò)?，F(xiàn)已知第一個(gè)到達(dá)出口的是3號(hào)車(chē)廂，請(qǐng)寫(xiě)出所有可能的到達(dá)出口的車(chē)廂排列總數(shù)（不必給出每種排列）。將N個(gè)紅球和M個(gè)黃球排成一行。例如:N=2,M=3可得到以下6種排法：紅紅黃黃黃紅黃紅黃黃紅黃黃紅黃黃紅紅黃黃黃紅黃紅黃黃黃黃紅紅問(wèn)題：當(dāng)N=4,M=3時(shí)有多少種不同排法？（不用列出每種排法）NOIP2003普及二.問(wèn)題求解（每題5分，共10分）.現(xiàn)在市場(chǎng)上有一款汽車(chē)A很熱銷(xiāo)，售價(jià)是2萬(wàn)美元。汽車(chē)A每加侖汽油可以行駛20英里。普通汽車(chē)每年大約行（3） a,e,f中必須有2樣（4） b,c要么都選，要么都不選（5） c,d兩樣中選一樣（6） 若d不選，則e也不選平面上有三條平行直線，每條直線上分別有7,5,6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？NOIP2001提高二、問(wèn)題求解（5+7=12分）已知一棵二叉樹(shù)的結(jié)點(diǎn)名為大寫(xiě)英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹(shù)的先序遍歷的順序?yàn)椋浩矫嫔嫌腥龡l平行直線，每條直線上分別有7,5,6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？駛12000英里。油價(jià)是每加侖1美元。不久我公司就要推出新款節(jié)油汽車(chē)B，汽車(chē)B每加侖汽油可以行駛30英里?，F(xiàn)在我們要為B制定價(jià)格（它的價(jià)格略高于A）:我們預(yù)計(jì)如果用戶能夠在兩年內(nèi)通過(guò)節(jié)省油錢(qián)把B高出A的價(jià)錢(qián)彌補(bǔ)回來(lái)，則他們就會(huì)購(gòu)買(mǎi)B，否則就不會(huì)購(gòu)買(mǎi)B。那么B的最高價(jià)格應(yīng)為萬(wàn)美元。無(wú)向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3,則G至少有個(gè)頂點(diǎn)。NOIP2004普及一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)在有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子要使用16個(gè)單位的木材，售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要把木材用光），最多可以賣(mài) 元錢(qián)。75名兒童到游樂(lè)場(chǎng)去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過(guò)，55人至少玩過(guò)其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂(lè)場(chǎng)總共收入700,可知有—名兒童沒(méi)有玩過(guò)其中任何一種。NOIP2005普及將數(shù)組｛32,74,25,53,28,43,86,47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換 次。2.2.有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3個(gè)小組中分別選出3位組長(zhǎng)，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長(zhǎng)，共有種選擇方案。NOIP2006普及1.(尋找假幣)現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同如果使用不帶砝碼的天平稱重最少需要稱幾次就可以找出假幣？你還要指出第1次的稱重方法請(qǐng)寫(xiě)出你的結(jié)果 2.(取石子游戲)現(xiàn)有5堆石子石子數(shù)依次為3,5,7，19，50，甲乙兩人輪流從任一堆中任取(每次只能取自一堆不能不取)，取最后一顆石子的一方獲勝。甲先取問(wèn)甲有沒(méi)有獲勝策略(即無(wú)論乙怎樣取甲只要不失誤都能獲勝)？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫(xiě)出你的結(jié)果 O城市51236702城市615125920NOIP2007普及二、問(wèn)題求解(共2題，每題5分，共計(jì)10分)。1、 (子集劃分)將n個(gè)數(shù)(1，2,…，n)劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒(méi)有共同的數(shù)，也沒(méi)有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的劃分方法依次為｛(1),(234)｝，｛(2),(134)｝，｛(3),(124)｝，｛(4),(123)｝，｛(12),(34)｝，｛(13),(24)｝， ｛(14),(23)｝。當(dāng)n=6，r=3時(shí)，S(6,3)=。(提示：先固定一個(gè)數(shù)，對(duì)于其余的5個(gè)數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對(duì)原固定的數(shù)進(jìn)行分析。)2、 (最短路線)某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)(見(jiàn)下圖)，有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？NOIP2008普及1.書(shū)架上有4本不同的書(shū)A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書(shū)擺在書(shū)架上，滿足所有黑皮的書(shū)都排在一起的擺法有種。滿足A必須比C靠左，所有紅皮的書(shū)要擺在一起，所有黑皮的書(shū)要擺放在一起，共有種擺法。2.有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為。城市1城市2城市3城市4城市5城市6TOC\o"1-5"\h\z城市10 2 3 1 12 15城市22 0 2 5 3 12城市33 2 0 3 6 5城市41 5 3 0 7 9NOIP2009普及小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a1->a2->a3，B=b1-〉b2-〉b3-〉b4-〉b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如……a2-〉b2-〉a3-〉b3 是合法的，而 a2-〉b3-〉a3-〉b2……是不合法的。小陳從B任務(wù)的b1步驟開(kāi)始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。使計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有 種。有如下的一段程序：a:=1;b:=a;d:=-a;e:=a+d;c:=2*d;f:=b+e-d;g:=a*f+c;現(xiàn)在要把這段程序分配到若干臺(tái)(數(shù)量充足)用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)行其中的某幾個(gè)語(yǔ)句，并可隨時(shí)通過(guò)電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺(tái)PC每單位時(shí)間可以執(zhí)行一個(gè)語(yǔ)句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在 單位時(shí)間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái)PC上已經(jīng)得到，才可以被其他PC引用。例如若語(yǔ)句4和6被分別分配到兩臺(tái)PC上執(zhí)行，則因?yàn)檎Z(yǔ)句6需要引用語(yǔ)句4的計(jì)算結(jié)果，語(yǔ)句6必須在語(yǔ)句4之后執(zhí)行。

答案：NOIP1998普及1.當(dāng)K=_3 ,a,a，…，a為a=3,a=-3,a=1時(shí)，, 1 2 k1 2 3對(duì)數(shù)列 122232,…，n2,… (A)成立。{3%+3%)2.(1)讀過(guò)a的人數(shù)是12人。(2)一本書(shū)也沒(méi)讀過(guò)的人數(shù)F(1)=1F(2)=2F(3)=4F(N)=F(N-3)+F(N-2)+F(N-1) (NN4)NOIP2001普及二、問(wèn)題解答(5+7分，兩題共12分)答：在a,b,c,d,e,f六件物品中，按條件能選出的物品是:a,b,c,f是30人。 {3%+4%}答：用這些點(diǎn)為頂點(diǎn)，能組成751個(gè)不同三角形??氣之值為NOIP2003普及問(wèn)題解答(每??氣之值為NOIP2003普及問(wèn)題解答(每題53.當(dāng)n=1998,k=3時(shí)，xx.{7%} JJ-1NOIP1998提高二、問(wèn)題求解：共20分當(dāng)K=_4，a,a，…，a為a=4,a=6,a=4，a=-1對(duì)數(shù)列.一一 1,2ki2 3 4132333,…，n3,?"（A）成立。{3%+5%）.此二叉樹(shù)為：{7%}/XD/E八.表示該無(wú)向H圖的［鄰接矩陣為{6%}0100000101100001010000110111000100100010010001110NOIP1999普及二、回答問(wèn)題：(10分)NOIP2001提高二、問(wèn)題解答(5+7分，兩題共12分)答：該二叉樹(shù)先序遍歷的順序?yàn)椋篈BCEGDFHIJ答：用這些點(diǎn)為頂點(diǎn)，能組成2250個(gè)不同四邊形NOIP2002普及二、問(wèn)題解答1、82、35分，共10分)答：2.04TOC\o"1-5"\h\z答：11NOIP2004普及二.問(wèn)題解答(每題5分，共10分)答： 160答： 10NOIP2005普及二.問(wèn)題解答(每題5分，共10分)答：52.答：11NOIP20