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

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

2、1) a,b兩樣至少有一樣(2) a,d不能同時取(3) a,e,f中必須有2樣(4) b,c要么都選，要么都不選(5) c,d兩樣中選一樣若d不選，則e也不選5. 平面上有三條平行直線，每條直線上分別有7, 5, 6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同三角形？6. 已知一棵二叉樹的結(jié)點名為大寫英文字母，其中序與后序遍歷的順序分別為:CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序為：7. 平面上有三條平行直線，每條直線上分別有7, 5, 6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？8.

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

4、的位置上。例如：原來位置為：12 3放回去時只能為：312或 231 這兩種問題：求當(dāng)n = 5時滿足以上條件的放法共有多少種？(不用列出每種放法)11. 現(xiàn)在市場上有一款汽車 A很熱銷，售價是2萬美元。汽車 A每加侖汽油可以行駛 20 英里。普通汽車每年大約行駛 12000英里。油價是每加侖1美元。不久我公司就要推出新款 節(jié)油汽車B,汽車B每加侖汽油可以行駛 30英里?，F(xiàn)在我們要為 B制定價格(它的價格略高 于A):我們預(yù)計如果用戶能夠在兩年內(nèi)通過節(jié)省油錢把B高出A的價錢彌補回來，則他們就會購買B,否則就不會購買 B。那么B的最高價格應(yīng)為 萬美元。12. 某年級學(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、一個家具公司生產(chǎn)桌子和椅子。現(xiàn)有113個單位的木材。每張桌子要使用20個單位的木材，售價是30元；每張椅子要用16個單位的木材，售價是 20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買 元錢。14、

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

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

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

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

10、的通路的總數(shù)為。23. (子集劃分)將 n個數(shù)(1, 2,，n)劃分成r個子集。每個數(shù)都恰好屬于一個子 集，任何兩個不同的子集沒有共同的數(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 時，S(6,3)=。(提示：先固定一個數(shù)，對于其余的5個數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對原固定的數(shù)進(jìn)行分析。)7條南北向的縱24、(最短路線)某城市的街道是一個很規(guī)

11、整的矩形網(wǎng)絡(luò)(見下圖)，有街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的 B,最短的走法共有多少種?25. 書架上有4本不同的書 A B、C 0其中A和B是紅皮的，C和D是黑皮的。把這 4 本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有 種。滿足 A必須比C種擺法?？孔?，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有26有 6 個城市，任何兩個城市之間都有一條道路連接， 6 個城市兩兩之間的距離如下表 所示，則城市 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個有標(biāo)號得球，標(biāo)號依次為1, 2,，n。將這n個球放入r個相同得盒子里，不允許有空盒，其不同放置方法得總數(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 時， s(7,4)= 。28. N個人在操場里圍成一圈，將這N個人安順時針方向從1到N編號，

13、然后，從第一個人起，每隔一個人讓下一個人離開操場，顯然， 第一輪過后，具有偶數(shù)編號的人都離開了操 場。依次做下去， 直到操場只剩一個人， 記這個人的編號為 J(N) ，例如， J(5)=3 ， J(10)=5 ， 等等。則 J(400)= 。對 N=2m+r 進(jìn)行分析(0<=r<2m)29. 書架上有 21 本書，編號從 1 到 21 從中選 4 本，其中每兩本的編號都不相鄰的選法一共 有。1.答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為ab a c c/ /baccab/cbba2 .對給出的任意一個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答：用這些點為頂點，能組成751個不同三角形6、答：該二叉樹先序遍歷的順序為：ABCEGDFHIJ7、答：這些點為頂點，能組成 2250個不同四邊形8. 99.3510.4411.12.2.0413.414.16015.16.1