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

1、 1已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。 2有2×n的一個(gè)長方形方格，用一個(gè)1×2的骨牌鋪滿方格。例如n=3時(shí)，為2×3方格。 此時(shí)用一個(gè)1×2的骨牌鋪滿方格，共有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六件物品中，按下面的條件能選出的物品是：

2、(1)a,b兩樣至少有一樣(2)a,d不能同時(shí)取(3)a,e,f中必須有2樣(4)b,c要么都選，要么都不選(5)c,d兩樣中選一樣(6)若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è)無窮

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

4、：1 2 3 放回去時(shí)只能為：3 1 2 或 2 3 1 這兩種 問題：求當(dāng)n = 5時(shí)滿足以上條件的放法共有多少種？（不用列出每種放法）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ǔ)回來，則他們就會(huì)購買B，否則就不會(huì)購買B。那么B的最高價(jià)格應(yīng)為萬美元。 12. 某年級學(xué)生共選修6門課程，期末考試前，必須提前將這6門課程考完，每人

5、每天只在下午至多考一門課程，設(shè)6門課程為C1，C2，C3，C4，C5，C6，S(Ci)為學(xué)習(xí)Ci 的學(xué)生集合。已知S(Ci)S(C6)，i=1，2，.，5，S(Ci)S(Ci+1)，i=1，2，3，4，S(C5)S(C1)，問至少安排_(tái)天才能考完這6門課程。13、一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子要用16個(gè)單位的木材，售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買_元錢。14、75名兒童去游樂場玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩

6、一樣的費(fèi)用為5元，游樂場總共收入700，可知有_名兒童沒有玩過其中任何一種。15. 已知a, b, c, d, e, f, g七個(gè)人中，a會(huì)講英語；b會(huì)講英語和漢語；c會(huì)講英語、意大利語和俄語；d會(huì)講漢語和日語；e會(huì)講意大利語和德語；f會(huì)講俄語、日語和法語；g會(huì)講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請以“a b”開頭寫出你的安排方案： 。16. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換次。17. 有3 個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、

7、趙、陳5 名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3 個(gè)小組中分別選出3 位組長，一位同學(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 枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同

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

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

10、。設(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)，(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ī)整

11、的矩形網(wǎng)絡(luò)（見下圖），有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？_、25.書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有_種擺法。 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 城市3 3 2 0

12、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)號得球，標(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),(23)。當(dāng)n=7，r=4時(shí)，s(7,4)=_。28.N個(gè)人在操場里圍成一圈，將這N個(gè)人安順時(shí)針方向從1到N編號，然后，從第一個(gè)人起，每隔一個(gè)人讓下一個(gè)人離開操場，顯然，第一輪

13、過后，具有偶數(shù)編號的人都離開了操場。依次做下去，直到操場只剩一個(gè)人，記這個(gè)人的編號為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é)果；可畫出的這些二叉樹為: a b a c c / / / b a c c a b / / c b b a 2對給出的任意一個(gè)n（n>0），用F（n）表示其鋪法的總數(shù)的遞推公式為: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（n3） 3用遞推公式給出的某人從底層開始走完全部樓梯的走法為（用F（N）記錄不同方案數(shù)）： F（1）1 F（2）2 F（3）4F（N）F（N3）F（N2）F（N1）（N4）4.答：在a,b,c,d,e,f六件物品中，按條件能選出的物品是：a,b,c,f5.答：用這些點(diǎn)為頂點(diǎn)，能組成751個(gè)不同三角形6、答：該二叉樹先序遍歷的順序?yàn)椋篈BCEGDFHIJ  7、答：這些點(diǎn)為頂點(diǎn)，能組成2250個(gè)不同四邊形8. 99. 3510. 4411. 2.0412. 413. 1601