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

1、1 .,按中序遍歷二叉樹的結(jié)果為：abc問(wèn)：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果,并畫出這些二叉樹.例如n=3時(shí),為2X3方格.2 .有2Xn的一個(gè)長(zhǎng)方形方格,用一個(gè)1X2的骨牌鋪滿方格.此時(shí)用一個(gè)1X2的骨牌鋪滿方格,共有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六件物品中,按下面的條件能選出的物品是:(1)a,b兩樣至少有一樣(2)a,d不

2、能同時(shí)取(3)a,e,f中必須有2樣(4)b,c要么都選,要么都不選(5)c,d兩樣中選一樣(6)假設(shè)d不選,那么e也不選5 .平面上有三條平行直線,每條直線上分別有7,5,6個(gè)點(diǎn),且不同直線上三個(gè)點(diǎn)都不在同一條直線上.問(wèn)用這些點(diǎn)為頂點(diǎn),能組成多少個(gè)不同三角形？6 .一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母,其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA那么該二叉樹的先序遍歷的順序?yàn)椋? .平面上有三條平行直線,每條直線上分別有7,5,6個(gè)點(diǎn),且不同直線上三個(gè)點(diǎn)都不在同一條直線上.問(wèn)用這些點(diǎn)為頂點(diǎn),能組成多少個(gè)不同四邊形？8 .如下列圖,有一個(gè)無(wú)窮大的的棧S,在棧的右邊排列著

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

4、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)通過(guò)節(jié)省油錢把B高出A的價(jià)錢彌補(bǔ)回來(lái),那么他們就會(huì)購(gòu)置B,否那么就不會(huì)購(gòu)置Bo那么B的最高價(jià)格應(yīng)為萬(wàn)美元.12 .某年級(jí)學(xué)生共選修6門課程,期末測(cè)試前,必須提前將這6門課程考完,每人每天只在下午至多考一門課程,設(shè)6門課程為01,02,03,04,05,06,S(

5、Ci)為學(xué)習(xí)Ci的學(xué)生集合.S(0i)nS(06)w(i),i=1,2,.,5,S(0i)nS(0i+1)w力,i=1,2,3,4,S(05)nS(01)w(i),問(wèn)至少安排天才能考完這6門課程.13、一個(gè)家具公司生產(chǎn)桌子和椅子.現(xiàn)有113個(gè)單位的木材.每張桌子要使用20個(gè)單位的木材,售價(jià)是30元；每張椅子要用16個(gè)單位的木材,售價(jià)是20元.使用已有的木材生產(chǎn)桌椅不一定要用光木材做多可以買元錢.14、75名兒童去游樂(lè)場(chǎng)玩.他們可以騎旋轉(zhuǎn)木馬,坐滑行軌道,乘宇宙飛船.其中2人這三種東西都玩過(guò),55人至少玩過(guò)其中兩種.假設(shè)每玩一樣的費(fèi)用為5元,游樂(lè)場(chǎng)總共收入700,可知有名兒童沒(méi)有玩過(guò)其中任何一種

6、.15 .己知,人5&6,18七個(gè)人中,2會(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)以“ab開頭寫出你的安排方案：°16 .將數(shù)組32,74,25,53,28,43,86,47中的元素按從小到大的順序排列,每次可以交換任意兩個(gè)元素,最少需要交換次.17 .有3個(gè)課外小組：物理組,化學(xué)組和生物組.今有張、王、李、趙、陳5名同學(xué),已知張、王為物理組成員,張、李、趙為化學(xué)組成員,李、趙、陳為生物組成員.如果要在3個(gè)

7、小組中分別選出3位組長(zhǎng),一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長(zhǎng),共有多少種選擇方案.18 .取火柴游戲的規(guī)那么如下：一堆火柴有N根,A、B兩人輪流取出.每人每次可以取1根或2根,最先沒(méi)有火柴可取的人為敗方,另一方為勝方.如果先取者有必勝策略那么記為1,先取者沒(méi)有必勝策略記為0.當(dāng)N分別為100,200,300,400,500時(shí),先取者有無(wú)必勝策略的標(biāo)記順序?yàn)榛厝菰S為一個(gè)由0和/或1組成的字符串.19 .尋找假幣現(xiàn)有80枚硬幣,其中有一枚是假幣,其重量稍輕,所有真幣的重量都相同,如果使用不帶祛碼的天平稱重,最少需要稱幾次,就可以找出假幣？你還要指出第1次的稱重方法.請(qǐng)寫出你的結(jié)果：20 .取石子游戲

8、現(xiàn)有5堆石子,石子數(shù)依次為3,5,7,19,50,甲乙兩人輪流從任一堆中任取每次只能取自一-堆,不能不取,取最后一顆石子的一方獲勝.甲先取,問(wèn)甲有沒(méi)有獲勝策略即無(wú)論乙怎樣取,甲只要不失誤,都能獲勝？如果有,甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫出你的結(jié)果：21 .將2006個(gè)人分成假設(shè)干不相交的子集,每個(gè)子集至少有3個(gè)人,并且:1在每個(gè)子集中,沒(méi)有人熟悉該子集的所有人.(2)同一子集的任何3個(gè)人中,至少有2個(gè)人互不熟悉.(3)對(duì)同一子集中任何2個(gè)不相識(shí)的人,在該子集中恰好只有1個(gè)人熟悉這兩個(gè)人.那么滿足上述條件的子集最多能有幾個(gè)？22 .將邊長(zhǎng)為n的正三角形每邊n等分,過(guò)每個(gè)分點(diǎn)分別做另外兩邊的平

9、行線,得到假設(shè)干個(gè)正三角形,我們稱為小三角形.正三角形的一條通路是一條連續(xù)的折線,起點(diǎn)是最上面的一個(gè)小三角形,終點(diǎn)是最下面一行位于中間的小三角形.在通路中,只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形,并且每個(gè)小三角形不能經(jīng)過(guò)兩次或兩次以上(圖中是n=5時(shí)一條通路的例子).設(shè)n=10,那么該正三角形的不同的通路的總數(shù)為.23 .(子集劃分)將n個(gè)數(shù)(1,2,n)劃分成r個(gè)子集.每個(gè)數(shù)都恰好屬于一個(gè)子集,任何兩個(gè)不同的子集沒(méi)有共同的數(shù),也沒(méi)有空集.將不同劃分方法的總數(shù)記為S(n,r).例如,S(4,2)=7,這7種不同的劃分方法依次為(1),(234),(2),(1

10、34),(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條東西向的橫街.現(xiàn)要從西南角的A走到東北角的B,最短的走法共有多少種？25.書架上有4本不同的書A、B、CDb其中A和B是紅皮的,C和D是黑皮的.把這4本書擺在書架上,滿足所有黑皮的書都排在一起的擺法有種.滿足A必須比C靠左,所有紅皮的書要擺在一起,所有黑皮的

11、書要擺放在一起,共有種擺法.26 .有6個(gè)城市,任何兩個(gè)城市之間都有一條道路連接,6個(gè)城市兩兩之間的距離如下表所示,那么城市1到城市6的最短距離為.城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市61512592027 .給定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),(

12、24),(14),(23).當(dāng)n=7,r=4時(shí),s(7,4)=.28 .N個(gè)人在操場(chǎng)里圍成一圈,將這N個(gè)人安順時(shí)針?lè)较驈?到N編號(hào),然后,從第一個(gè)人起,每隔一個(gè)人讓下一個(gè)人離開操場(chǎng),顯然,第一輪過(guò)后,具有偶數(shù)編號(hào)的人都離開了操場(chǎng).依次做下去,直到操場(chǎng)只剩一個(gè)人,記這個(gè)人的編號(hào)為J(N),例如,J(5)=3,J(10)=5,等等.那么J(400)=.對(duì)N=2Am+r進(jìn)行分析(0<=r<2m)29 .書架上有21本書,編號(hào)從1到21從中選4本,其中每?jī)杀镜木幪?hào)都不相鄰的選法一共有.1.答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為abacc/baccab/cbba

13、2.對(duì)給出的任意一個(gè)n(n>0),用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(N3)+F(N2)+F(N1)(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.04