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

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

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

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

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

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

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

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

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

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

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

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

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