初賽問題求解專練VIP

1、2006年南海區(qū)信息學(xué)夏令營OI3班練習(xí)題（二）（問題解答專練）一、問題求解：1、平面上有7個(gè)點(diǎn)，共有3個(gè)點(diǎn)共線，其余再也沒有3點(diǎn)共線，每兩點(diǎn)連成一條直線，一共可以連成 （1） 條不同直線。以這些點(diǎn)為頂點(diǎn)可以連成 （2） 個(gè)不同的三角形。2、某省的地圖如下圖，共有A,B,C,D,E,F,G七個(gè)縣區(qū)，如果用紅、黃、藍(lán)、綠、紫這五種顏色給地圖染色，要求相鄰區(qū)縣的顏色不能相同，那么共有_種不同的染色方法。3、馬路上有編號為1，2，3，10的十盞路燈，為既節(jié)約用電，又能看清路面（不影響走路照明），可以把其中的三只燈關(guān)掉，但不能同時(shí)關(guān)掉相鄰的兩盞或兩盞以上的燈。在兩端的燈也不能關(guān)掉的情況下，求滿足條件的

2、關(guān)燈辦法有_種？4、若一個(gè)棧中有5個(gè)元素，另一個(gè)棧中有4個(gè)元素，則他們出棧的的方法共有多少種？ 5、如下圖,有一個(gè)無窮大的的棧S,在棧的右邊排列著1,2,3,4,5共五個(gè)車廂。其中每個(gè)車廂可以向左行走,也可以進(jìn)入棧S讓后面的車廂通過?，F(xiàn)已知第一個(gè)到達(dá)出口的是3號車廂，請寫出所有可能的到達(dá)出口的車廂排列總數(shù)(不必給出每種排列)。 出口 1 2 3 4 5 S6、將N個(gè)紅球和M個(gè)黃球排成一行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅問題:當(dāng)N=4,M=3時(shí)有多少種不同排法?(不用列出每種排法) 7、平面上有三條平行直線，每條直線

3、上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？ 8、已知，按中序遍歷二叉樹的結(jié)果為：abc 問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。 9、字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成哪些不同的字符串？_10、將數(shù)組32,74,25,53,28,43,86,47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換_ _次。11、有3個(gè)課外小組：物理組，化學(xué)組和生物組。今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組

4、成員。如果要在3個(gè)小組分別選出3位組長，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長，共有_ _種選擇方案。12、無向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少有_個(gè)頂點(diǎn)。13、在磁盤的目錄結(jié)構(gòu)中，我們將與某個(gè)子目錄有關(guān)聯(lián)的目錄數(shù)稱為度例如左圖： 該圖表達(dá)了A盤的目錄結(jié)構(gòu)：DI，Dll，D2均表示子目錄的名字.在這里，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D12，D2，D111，D112，D113的度均為1。又不考慮子目錄的名字，則可簡單的圖示為如下的樹結(jié)構(gòu)： 若知道一個(gè)磁盤的目錄結(jié)構(gòu)中，度為2的子目錄有2個(gè)，度為3的子目錄有1個(gè)，度為4的子目錄有3

5、個(gè)。 試問：度為1的子目錄有幾個(gè)？ 14、已知公式： 則f(f(f(3)+2)div 2)的值是( )。15、在某工廠裝配30輛汽車，可供選擇的設(shè)備是收音機(jī)，空調(diào)和對講機(jī)。已知其中15輛汽車有收音機(jī)，8輛有空調(diào)，6輛有對講機(jī)，而且其中3輛汽車這三樣設(shè)備都有。請問至少有多少輛汽車沒有提供任何設(shè)備？ 16、某班有30個(gè)同學(xué)報(bào)名參加100、400、800m3個(gè)運(yùn)動(dòng)項(xiàng)目比賽。已知有6人獲100m參賽資格，8人獲400m參賽資格，15人獲800m參賽資格，且其中有3個(gè)獲全部3項(xiàng)參賽資格，則至少有_人沒有獲任何項(xiàng)目參賽資格。17、某律師事務(wù)所共有15名工作人員，如果以下判斷只有一個(gè)是真的，那么該律師事務(wù)所

6、會使用計(jì)算機(jī)的人數(shù)是_人。（1） 有人會使用計(jì)算機(jī)（2） 有人不會使用計(jì)算機(jī)（3） 所長不會使用計(jì)算機(jī)18、現(xiàn)在市場上有一款汽車A很熱銷，售價(jià)是2萬美元。汽車A每加侖汽油可以行駛20英里。普通汽車每年大約行駛12000英里。油價(jià)是每加侖1美元。不久我公司就要推出新款節(jié)油汽車B，汽車B每加侖汽油可以行駛30英里。現(xiàn)在我們要為B制定價(jià)格(它的價(jià)格略高于A)：我們預(yù)計(jì)如果用戶能夠在兩年內(nèi)通過節(jié)省油錢把B高出A的價(jià)錢彌補(bǔ)回來，則他們就會購買B，否則就不會購買B。那么B的最高價(jià)格應(yīng)為 萬美元。19、一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子

7、要用16個(gè)單位的木材，售價(jià)是20元。使用已有的木材生產(chǎn)桌椅（不一定要用光木材）做多可以買_元錢。20、75名兒童去游樂場玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩一樣的費(fèi)用為5元，游樂場總共收入700，可知有_名兒童沒有玩過其中任何一種。21、  某班有50名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫a，b，c三本書的書名，將讀過的書打V，結(jié)果統(tǒng)計(jì)數(shù)字如下：只讀a者8人；只讀b者4人；只讀c者4人；全部讀過的有2人；讀過a，b兩本書的有4人；讀過a，c兩本書的有2人；讀過b，c兩本書的有3人；（1）讀過a的人數(shù)是（ 

8、     ）   （2）一本書也沒有讀過的人數(shù)是（      ）22、 已知一串明文與對應(yīng)的密碼如下:明文: home 密碼: fmkc若采用與上述相同的加密算法,則明文pen的密碼是 。23、在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是： (1)a,b兩樣至少有一樣 (2)a,d不能同時(shí)取 (3)a,e,f中必須有2樣 (4)b,c要么都選，要么都不選 (5)c,d兩樣中選一樣 (6)若d不選，則e也不選24、某信息學(xué)競賽，A、B、C、D、E、F、G、H八位同學(xué)獲得

9、了前八名，老師讓他們猜一下誰是第一名。A說：“或者F是第一名，或者H是第一名?！盉說：“我是第一名。”C說：“G是第一名?！盌說：“B不是第一名?！盓說：“A說的不對?！盕說：“我不是第一名?！盙說：“C不是第一名?！盚說：“我同意A的意見?！崩蠋熤赋觯巳酥杏腥瞬聦α?，那么，試問第一名是誰？ 25、N皇后問題要求在N*N的棋盤上放置N個(gè)皇后，使其不能互相攻擊，即任意2個(gè)皇后不能處于棋盤上的同一行、同一列或同一斜線上。則當(dāng)N=4時(shí)，擺放方法有哪兩種？（答案寫成“a b c d”的形式 ，表示擺放在第一行的第a列、第二行的第b列、第三行的第c列和第四行的第d列） 26、莎士比亞在威尼斯商人中，

10、寫富家少女鮑細(xì)婭品貌雙全，貴族子弟、公子王孫紛紛向她求婚。鮑細(xì)婭按照其父遺囑，由求婚者猜盒訂婚。鮑細(xì)婭有金、銀、鉛三個(gè)盒子，分別刻有三句話，其中只有一個(gè)盒子，放有鮑細(xì)婭肖像。求婚者通過這三句話，猜中鮑細(xì)婭的肖像放在哪只盒子里，就嫁給誰。三個(gè)盒子上刻的三句話分別是：（1）金盒子：“肖像不在此盒中?！?（2）銀盒子：“肖像在鉛盒中。”（3）鉛盒子：“肖像不在此盒中。”鮑細(xì)婭告訴求婚者，上述三句話中，最多只有一句是真的。請你猜鮑細(xì)婭的肖像究竟放在哪一個(gè)盒子里？ 。27、甲乙丙丁四人猜年齡，甲說：“我最大，乙最小，丁第三大”；乙說：“我最大，甲最小，丁第二大，丙第三大”；丙說：“乙最小，甲第三大”；丁

11、說：“我最大，丙最小，乙第二大，甲第三大”。四個(gè)人中每個(gè)人只說對了一個(gè)結(jié)果，請按從大到小的順序?qū)懗稣_結(jié)果。1、 2、 3、 4、 28、小王、小張和小李中一位是工人，一位是教師，一位是律師?，F(xiàn)在知道小李比律師年齡大，小王和教師不同歲，教師比小張年齡小。問： 是工人、 是教師、 是律師。29、現(xiàn)在的時(shí)間為12點(diǎn)正，再過N個(gè)小時(shí)（N為整數(shù)）為幾點(diǎn)鐘？ 30、編號為1到13的紙牌順時(shí)鐘排成一圈，有人從編號為1的牌從數(shù)字1開始順時(shí)鐘數(shù)下去，1、2、3、20、21、，一圈又一圈。問：當(dāng)數(shù)到數(shù)字N時(shí)，所在紙牌的編號為 。31、“鼠算遺題”。這是日本數(shù)學(xué)家吉田光在1627年提出來的。他是這樣說的：“正月里

12、，鼠父鼠母生了12只小鼠，于是大小鼠共14只。二月里，兩代鼠全部配對，每對鼠又各生了12只小鼠。因此共有98只。如這樣下去，每月所有的鼠全部配對，每對鼠又各生了12只小鼠。十二個(gè)月后，鼠的總數(shù)是多少呢？”假設(shè)每月都按這樣的規(guī)律生，而所生的鼠又全部成活，十二個(gè)月后，鼠的總數(shù)是27682574402只。你能找出計(jì)算此數(shù)的公式嗎？此公式為 。32、有2×n的一個(gè)長方形方格，用一個(gè)1×2的骨牌鋪滿方格。例如n=3時(shí)，為2×3方格。此時(shí)用一個(gè)1×2的骨牌鋪滿方格，共有3種鋪法： 試對給出的任意一個(gè)n(n0)，求出鋪法總數(shù)的遞推公式。 33、公式推導(dǎo)： 根據(jù)Noco

13、machns定理，任何一個(gè)正整數(shù)n的立方一定可以表示成n個(gè)連續(xù)的奇數(shù)的和。 例如： 13 1 23 3 5 33 7 9 11 43=13十15+17+19在這里，若將每一個(gè)式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請寫出X與n之間的關(guān)系表達(dá)式： 34、“兔子繁殖”。小兔子出生一個(gè)月后便可長成大兔子，大兔子每月都可以繁殖，生出一對小免子。假設(shè)月份有對小兔子，月份便會有對大兔子和對小兔子共對兔子，依此繁殖速度，則m月份兔子的對數(shù)F(m) 的值為。練習(xí)題（二）（問題解答專練）答案1、(1) 19 (2) 34 2、5x4x3x3x3x3x3=4860(種)   3、 或20 4、126 5、8 6、35 7、7518、答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為：9、ABC ACB BAC BCA CBA 10、答： 5 11、答： 11 12、11 13、9個(gè) 14、55 15、7 16、7 17、15 18、2.04 19、160 20、10 21、(1)讀過a的人數(shù)是12人。(2)一本書也沒讀過的人數(shù)是30人。22、ncl 23、a,b,c,f 24、C是第一名25、 2 4 1 3 和 3 1 4 2 26、金 27、丁甲丙乙28、 小張 是工人、 小李 是教師、 小王 是律師29