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

1、資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝1已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。的骨牌鋪滿方格。 例如 n=3 時(shí)，為 2 3 方格。2 有 2 n 的一個(gè)長(zhǎng)方形方格， 用一個(gè) 1 2此時(shí)用一個(gè)12 的骨牌鋪滿方格，共有3 種鋪法：試對(duì)給出的任意一個(gè)n（n0 ），求出鋪法總數(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 兩樣中選一樣(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)都不在同一條直線上。問用這

3、些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？8.如下圖 ,有一個(gè)無窮大的的棧S,在棧的右邊排列著1,2,3,4,5 共五個(gè)車廂。其中每個(gè)車廂可以向左行走 ,也可以進(jìn)入棧S 讓后面的車廂通過?，F(xiàn)已知第一個(gè)到達(dá)出口的是3 號(hào)車廂，請(qǐng)精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝寫出所有可能的到達(dá)出口的車廂排列總數(shù)(不必給出每種排列)。出口12345S9.將 N 個(gè)紅球和 M 個(gè)黃球排成一行。例如:N=2,M=3 可得到以下6 種排法 :紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅問題 :當(dāng) N=4,M=3 時(shí)有多少種不同排法 ?(不用列出每種排法 )10 在書架上放有編號(hào)為1

4、， 2 ， n 的 n 本書?，F(xiàn)將n 本書全部取下然后再放回去，當(dāng)放回去時(shí)要求每本書都不能放在原來的位置上。例如：n = 3 時(shí)：原來位置為：123放回去時(shí)只能為：312或231這兩種問題：求當(dāng)n = 5 時(shí)滿足以上條件的放法共有多少種？（不用列出每種放法）11. 現(xiàn)在市場(chǎng)上有一款汽車 A 很熱銷，售價(jià)是 2 萬美元。汽車 A 每加侖汽油可以行駛 20 英里。 普通汽車每年大約行駛 12000 英里。 油價(jià)是每加侖 1 美元。 不久我公司就要推出新款節(jié)油汽車B，汽車 B 每加侖汽油可以行駛30 英里?，F(xiàn)在我們要為B 制定價(jià)格 ( 它的價(jià)格略高于 A) ：我們預(yù)計(jì)如果用戶能夠在兩年內(nèi)通過節(jié)省油錢

5、把B 高出 A 的價(jià)錢彌補(bǔ)回來，則他們就會(huì)購(gòu)買B，否則就不會(huì)購(gòu)買B。那么 B的最高價(jià)格應(yīng)為萬美元。12.某年級(jí)學(xué)生共選修6 門課程， 期末考試前， 必須提前將這6 門課程考完， 每人每天只在下午至多考一門課程，設(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) ，問至少安排 _天才能考完這 6 門課程。13、一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)有113 個(gè)單位的木材。每張桌子要使用20 個(gè)單位的木材，售價(jià)是30 元；

6、每張椅子要用16 個(gè)單位的木材，售價(jià)是20 元。使用已有的木材生精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝產(chǎn)桌椅（不一定要用光木材）做多可以買_元錢。14、 75 名兒童去游樂場(chǎng)玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55 人至少 玩過其中兩種。若每玩一樣的費(fèi)用為5 元，游樂場(chǎng)總共收入 700，可知有 _名兒童沒有玩過其中任何一種。15. 已知 a, b, c, d, e, f, g 七個(gè)人中， a 會(huì)講英語； b 會(huì)講英語和漢語； c 會(huì)講英語、意大利語和俄語； d 會(huì)講漢語和日語； e 會(huì)講意大利語和德語； f 會(huì)講俄語、日語和法語； g 會(huì)講

7、德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請(qǐng)以“ a b”開頭寫出你的安排方案：。16. 將數(shù)組 32, 74, 25, 53, 28, 43, 86, 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 兩人輪流取出。每

8、人每次可以取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次的稱重方法。請(qǐng)寫出你的結(jié)果：_ 。20（取石子游戲） 現(xiàn)有 5 堆石子 , 石子數(shù)依次為 3 ，5， 7， 19， 50，甲乙兩人輪流從任一堆中任?。看?/p>

9、只能取自一堆，不能不?。?, 取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論 乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫出你的結(jié)果：。21將 2006個(gè)人分成若干不相交的子集，每個(gè)子集至少有3個(gè)人，并且：（ 1）在每個(gè)子集中，沒有人認(rèn)識(shí)該子集的所有人。精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝（ 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)分別做另外兩邊的平行線，得到若干

10、個(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)

11、，(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)行分析。）24、（最短路線）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有 7 條南北向的縱街， 5 條東西向的橫街?，F(xiàn)要從西南角的 A 走到東北角的 B，最短的走法共有多少種？_、25. 書架上有 4 本不同的書 A、 B、C、 D。其中 A 和 B 是紅皮的， C 和 D 是黑皮的。把這 4本書擺在書架上，滿足

12、所有黑皮的書都排在一起的擺法有_種。滿足A 必須比C精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有_ 種擺法。26有 6 個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6 個(gè)城市兩兩之間的距離如下表所示，則城市 1到城市 6 的最短距離為 _ 。城市1城市2城市3城市4城市5城市 6城市 102311215城市 22025312城市 3320365城市 4153079城市 51236702城市 61512592 027. 給定 n 個(gè)有標(biāo)號(hào)得球，標(biāo)號(hào)依次為1， 2， ，n。將這 n 個(gè)球放入 r 個(gè)相同得盒子里，不允許有空盒，其不同放置

13、方法得總數(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)，然后，從第一個(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

14、 進(jìn)行分析（0=r0），用 F（ n）表示其鋪法的總數(shù)的遞推公式為:F（ 1） =1F（2） =2F（ n） =F （ n-2） +F （ n-1）（ n 3）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. 2.0412. 413. 16014. 1015. a b d f g