信息學(xué)奧賽題目求解(帶答案)

1、1. 已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。2. 有2Xn的一個(gè)長方形方格，用一個(gè)1X2的骨牌鋪滿方格。例如n=3時(shí)，為2X3方格。此時(shí)用一個(gè)1X2的骨牌鋪滿方格，共有3種鋪法：試對給出的任意一個(gè)n(n>0)，求出鋪法總數(shù)的遞推公式。3. 設(shè)有一個(gè)共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即1+1+1,1+2,2+1,3。4.在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是:(1) a,b兩樣至少有一樣(2) a

2、,d不能同時(shí)取(3) a,e,f中必須有2樣(4) b,c要么都選，要么都不選(5) c,d兩樣中選一樣若d不選，則e也不選5. 平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？6. 已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，其中序與后序遍歷的順序分別為CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序?yàn)椋?. 平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？8如下圖,有一個(gè)無窮大的的棧S,在棧的右邊排列著1,

3、2,3,4,5共五個(gè)車廂。其中每個(gè)車廂可以向左行走,也可以進(jìn)入棧S讓后面的車廂通過?，F(xiàn)已知第一個(gè)到達(dá)出口的是3號車廂，請寫出所有可能的到達(dá)出口的車廂排列總數(shù)(不必給出每種排列)。出口123459.將N個(gè)紅球和M個(gè)黃球排成一行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃紅黃紅黃黃紅黃黃紅黃黃紅紅黃黃黃紅黃紅黃黃黃黃紅紅問題:當(dāng)N=4,M=3時(shí)有多少種不同排法?(不用列出每種排法)10在書架上放有編號為1，2，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時(shí)要求每本書都不能放在原來的位置上。例如：n=3時(shí)：原來位置為：123放回去時(shí)只能為：312或231這兩種問題：求當(dāng)n=5時(shí)滿足以

4、上條件的放法共有多少種？(不用列出每種放法)11. 現(xiàn)在市場上有一款汽車A很熱銷，售價(jià)是2萬美元。汽車A每加侖汽油可以行駛20英里。普通汽車每年大約行駛12000英里。油價(jià)是每加侖1美元。不久我公司就要推出新款節(jié)油汽車B，汽車B每加侖汽油可以行駛30英里?，F(xiàn)在我們要為B制定價(jià)格(它的價(jià)格略高于A):我們預(yù)計(jì)如果用戶能夠在兩年內(nèi)通過節(jié)省油錢把B高出A的價(jià)錢彌補(bǔ)回來，則他們就會購買B，否則就不會購買B。那么B的最高價(jià)格應(yīng)為萬美元。12. 某年級學(xué)生共選修6門課程，期末考試前，必須提前將這6門課程考完，每人每天只在下午至多考一門課程，設(shè)6門課程為Cl,C2，C3,C4,C5,C6,S(Ci)為學(xué)習(xí)C

5、i的學(xué)生集合。已知S(Ci)nS(C6)工巾，i=1,2,.,5,S(Ci)nS(Ci+1)工巾，i=1,2,3,4,S(C5)nS(C1)工巾，問至少安排天才能考完這6門課程。13、一個(gè)家具公司生產(chǎn)桌子和椅子。現(xiàn)有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材,售價(jià)是30元；每張椅子要用16個(gè)單位的木材,售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買元錢。14、75名兒童去游樂場玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩一樣的費(fèi)用為5元，游樂場總共收入700，可知有名兒童沒有玩過其中任何一種。15.已

6、知a,b,c,d,e,f,g七個(gè)人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以請以“ab”開頭寫出你的安排方案：。16.將數(shù)組32,74,25,53,28,43,86,47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換次。17. 有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3個(gè)小組中分別選出3位組長

7、，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長，共有多少種選擇18. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1根或2根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當(dāng)N分別為100,200，300,400,500時(shí)，先取者有無必勝策略的標(biāo)記順序?yàn)椋ɑ卮饝?yīng)為一個(gè)由0和/或1組成的字符串）。19. （尋找假幣）現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請寫出你的結(jié)果：20. （取石子游戲）現(xiàn)有5堆石子,石子數(shù)

8、依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。?取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請寫出你的結(jié)果：21. 將2006個(gè)人分成若干不相交的子集，每個(gè)子集至少有3個(gè)人，并且（1）在每個(gè)子集中，沒有人認(rèn)識該子集的所有人。(2) 同一子集的任何3個(gè)人中，至少有2個(gè)人互不認(rèn)識。(3) 對同一子集中任何2個(gè)不相識的人，在該子集中恰好只有1個(gè)人認(rèn)識這兩個(gè)人。則滿足上述條件的子集最多能有幾個(gè)？22. 將邊長為n的正三角形每邊n等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若

9、干個(gè)正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上(圖中是n=5時(shí)一條通路的例子)。設(shè)n=10,則該正三角形的不同的通路的總數(shù)為_。/23. (子集劃分)將n個(gè)數(shù)(1,2,，n)劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7,這7種不同的劃分方法依次為(1),(234),(2),(134),(

10、3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。當(dāng)n=6,r=3時(shí)，S(6,3)=。(提示：先固定一個(gè)數(shù)，對于其余的5個(gè)數(shù)考慮S(5,3)與S(5,2),再分這兩種情況對原固定的數(shù)進(jìn)行分析。)24、(最短路線)某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)(見下圖)，有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B,最短的走法共有多少種？25.書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在

11、一起，共有種擺法。26有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市61512592027給定n個(gè)有標(biāo)號得球，標(biāo)號依次為1,2,n。將這n個(gè)球放入r個(gè)相同得盒子里，不允許有空盒，其不同放置方法得總數(shù)記為s(n,r)。例如，s(4,2)=7,這7種不同的放置方法依次為(1),(234)，(2),(134)，(3),(124)，(4),(123)，(12),(34)，(13),(24),(14),(

12、23)。當(dāng)n=7,r=4時(shí)，s(7,4)=。28. N個(gè)人在操場里圍成一圈，將這N個(gè)人安順時(shí)針方向從1到N編號，然后，從第一個(gè)人起，每隔一個(gè)人讓下一個(gè)人離開操場，顯然，第一輪過后，具有偶數(shù)編號的人都離開了操場。依次做下去，直到操場只剩一個(gè)人，記這個(gè)人的編號為J(N),例如，J(5)=3,J(10)=5,等等。則J(400)=。對N=2"m+r進(jìn)行分析(0<=r<2m)29. 書架上有21本書，編號從1到21從中選4本，其中每兩本的編號都不相鄰的選法一共有。1.答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為：abacc/baccab/cbba2. 對給出的任意一個(gè)n(n>0)，用F(n)表示其鋪法的總數(shù)的遞推公式為：F(1)=1F(2)=2F(n)=F(n-2)+F(n-l)(n±3)3. 用遞推公式給出的某人從底層開始走完全部樓梯的走法為(用F(N)記錄不同方案數(shù)):F(1)=1F(2)=2F(3)=4F(N)=F(N-3)+F(N-2)+F(N-l)(N24)4. 答：在a,b,c,d,e,f六件物品中，按條件能選出的物品是：a,b,c,f5. 答：用這些點(diǎn)為頂點(diǎn)，能組成751個(gè)不同三角形6. 答：該二叉樹先序遍歷的順序?yàn)椋篈BCEGDFHIJ7. 答：這些點(diǎn)為頂點(diǎn)，能組成