最新信息學(xué)奧賽問題求解(帶答案)

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

2、1) a,b兩樣至少有一樣(2) a,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.

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

4、的位置上。例如：原來位置為：12 3放回去時(shí)只能為：312或 231 這兩種問題：求當(dāng)n = 5時(shí)滿足以上條件的放法共有多少種？(不用列出每種放法)11. 現(xiàn)在市場(chǎng)上有一款汽車 A很熱銷，售價(jià)是2萬(wàn)美元。汽車 A每加侖汽油可以行駛 20 英里。普通汽車每年大約行駛 12000英里。油價(jià)是每加侖1美元。不久我公司就要推出新款 節(jié)油汽車B,汽車B每加侖汽油可以行駛 30英里。現(xiàn)在我們要為 B制定價(jià)格(它的價(jià)格略高 于A):我們預(yù)計(jì)如果用戶能夠在兩年內(nèi)通過節(jié)省油錢把B高出A的價(jià)錢彌補(bǔ)回來，則他們就會(huì)購(gòu)買B,否則就不會(huì)購(gòu)買 B。那么B的最高價(jià)格應(yīng)為 萬(wàn)美元。12. 某年級(jí)學(xué)生共選修 6門課程，期末考試

5、前，必須提前將這6門課程考完，每人每天只 在下午至多考一門課程，設(shè)6門課程為C1, C2, C3, C4, C5, C6, S(Ci)為學(xué)習(xí)Ci的學(xué)生集合。已知 S(Ci) n S(C6)豐 i=1 , 2, . , 5, S(Ci) n S(Ci+1)豐 © , i=1 , 2, 3, 4, S(C5) n S(C1)工© ,問至少安排 天才能考完這6門課程。13、一個(gè)家具公司生產(chǎn)桌子和椅子。現(xiàn)有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子要用16個(gè)單位的木材，售價(jià)是 20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買 元錢。14、

6、75名兒童去游樂場(chǎng)玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩一樣的費(fèi)用為5元，游樂場(chǎng)總共收入700，可知有名兒童沒有玩過其中任何一種。15. 已知a, b, c, d, e, f, g七個(gè)人中，a會(huì)講英語(yǔ)；b會(huì)講英語(yǔ)和漢語(yǔ)；c會(huì)講英語(yǔ)、意大利語(yǔ) 和俄語(yǔ)；d會(huì)講漢語(yǔ)和日語(yǔ)；e會(huì)講意大利語(yǔ)和德語(yǔ)；f會(huì)講俄語(yǔ)、日語(yǔ)和法語(yǔ)；g會(huì)講德語(yǔ) 和法語(yǔ)。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以， 請(qǐng)以"a b”開頭寫出你的安排方案： 。16. 將數(shù)組32, 74, 25, 53, 28, 43, 86,

7、47中的元素按從小到大的順序排列，每次可以交換任 意兩個(gè)元素，最少需要交換次。17. 有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3個(gè)小組中分別選出3位組長(zhǎng)，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長(zhǎng)，共有多少種選擇18. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1根或2根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為 0。當(dāng)N分別為100，200，300，400，500時(shí)，先取者有無必 勝策略的標(biāo)記順序?yàn)椋ɑ卮饝?yīng)

8、為一個(gè)由0和/或 1組成的字符串）。19. （尋找假幣）現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使 用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指1 次的稱重方法20. （取石子游戲）現(xiàn)有5堆石子，石子數(shù)依次為3 , 5, 7, 19, 50,甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢?，不能不取），取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論 乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一 堆里取多少？請(qǐng)寫出你的結(jié)果：21 將2006個(gè)人分成若干不相交的子集，每個(gè)子集至少有3個(gè)人，并且:（1）在每個(gè)子集中，沒有人

9、認(rèn)識(shí)該子集的所有人。(2) 同一子集的任何 3個(gè)人中，至少有2個(gè)人互不認(rèn)識(shí)。(3) 對(duì)同一子集中任何 2個(gè)不相識(shí)的人，在該子集中恰好只有 1個(gè)人認(rèn)識(shí)這兩個(gè)人。 則 滿足上述條件的子集最多能有幾個(gè)？22. 將邊長(zhǎng)為n的正三角形每邊n等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若 干個(gè)正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上(圖中是n=5時(shí)一條通路的例 子)。設(shè)n=10，則該正三角形的不同

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) , (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)行分析。)7條南北向的縱24、(最短路線)某城市的街道是一個(gè)很規(guī)

11、整的矩形網(wǎng)絡(luò)(見下圖)，有街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的 B,最短的走法共有多少種?25. 書架上有4本不同的書 A B、C 0其中A和B是紅皮的，C和D是黑皮的。把這 4 本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有 種。滿足 A必須比C種擺法?？孔螅屑t皮的書要擺在一起，所有黑皮的書要擺放在一起，共有26有 6 個(gè)城市，任何兩個(gè)城市之間都有一條道路連接， 6 個(gè)城市兩兩之間的距離如下表 所示，則城市 1 到城市 6 的最短距離為 。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6城市 1 0 2 3 1 12 15城市 2 2 0 2 5 3 12城市

12、 3 3 2 0 3 6 5城市 4 1 5 3 0 7 9城市 5 12 3 6 7 0 2城市 6 15 12 5 9 2 027. 給定n個(gè)有標(biāo)號(hào)得球，標(biāo)號(hà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),(23) 。當(dāng) n=7， r=4 時(shí)， s(7,4)= 。28. N個(gè)人在操場(chǎng)里圍成一圈，將這N個(gè)人安順時(shí)針方向從1到N編號(hào)，

13、然后，從第一個(gè)人起，每隔一個(gè)人讓下一個(gè)人離開操場(chǎng)，顯然， 第一輪過后，具有偶數(shù)編號(hào)的人都離開了操 場(chǎng)。依次做下去， 直到操場(chǎng)只剩一個(gè)人， 記這個(gè)人的編號(hào)為 J(N) ，例如， J(5)=3 ， J(10)=5 ， 等等。則 J(400)= 。對(duì) N=2m+r 進(jìn)行分析(0<=r<2m)29. 書架上有 21 本書，編號(hào)從 1 到 21 從中選 4 本，其中每?jī)杀镜木幪?hào)都不相鄰的選法一共 有。1.答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為ab a c c/ /baccab/cbba2 .對(duì)給出的任意一個(gè)n (n>0),用F ( n)表示其鋪法的總數(shù)的遞

14、推公式為：F (1) =1F (2) =2F (n) =F(n-2) +F (n-1)(n3)3 用遞推公式給出的某人從底層開始走完全部樓梯的走法為(用F(N )記錄不同方案數(shù))F ( 1)= 1F (2)= 2F (3)= 4F ( N )= F ( N 3)+ F (N 2)+ F (N 1)(N > 4)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)，能組成 2250個(gè)不同四邊形8. 99.3510.4411.12.2.0413.414.16015.16.1