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

1、1已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。2有2n的一個(gè)長方形方格，用一個(gè)12的骨牌鋪滿方格。例如n=3時(shí)，為23方格。此時(shí)用一個(gè)12的骨牌鋪滿方格，共有3種鋪法：試對給出的任意一個(gè)n（n0），求出鋪法總數(shù)的遞推公式。3設(shè)有一個(gè)共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即111

2、12213。4.在abcdef六件物品中，按下面的條件能選出的物品是：(1)ab兩樣至少有一樣(2)ad不能同時(shí)取(3)aef中必須有2樣(4)bc要么都選，要么都不選(5)cd兩樣中選一樣(6)若d不選，則e也不選5.平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？6.已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFH

3、DIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序?yàn)椋?.平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？8.如下圖有一個(gè)無窮大的的棧S在棧的右邊排列著12345共五個(gè)車廂。其中每個(gè)車廂可木材，售價(jià)是30元；每張椅子要用16個(gè)單位的木材，售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買_____元錢。14、75名兒童去游樂場玩。他

4、們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩一樣的費(fèi)用為5元，游樂場總共收入700，可知有_____名兒童沒有玩過其中任何一種。15.已知abcdefg七個(gè)人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請以“

5、ab”開頭寫出你的安排方案：。16.將數(shù)組3274255328438647中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換次。17.有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3個(gè)小組中分別選出3位組長，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長，共有多少種選擇方案。18.取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩

6、人輪流取出。每人每次可以取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次的稱重方法。請寫出你的

7、結(jié)果：_________________________________________________。20（取石子游戲）現(xiàn)有5堆石子石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。┤∽詈笠活w石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請寫出你的結(jié)果：_______________________________