NOIP初賽問題求解專練

1、2006年南海區(qū)信息學(xué)夏令營 013班練習(xí)題（二）（問題解答專練）-、問題求解：1、 平面上有7個(gè)點(diǎn)，共有3個(gè)點(diǎn)共線，其余再也沒有 3點(diǎn)共線，每?jī)牲c(diǎn)連成一條直線，一共可以連成（1）條不同直線。以這些點(diǎn)為頂點(diǎn)可以連成（2）個(gè)不同的三角形。2、某省的地圖如下圖，共有 A,B,C,D,E,F,G七個(gè)縣區(qū)，如果用紅、黃、藍(lán)、綠、紫這五種顏色給地圖染色，要求相鄰區(qū)縣的顏色不能相同，那么共有 種不同的染色方法。3、 馬路上有編號(hào)為 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號(hào)車廂，請(qǐng)寫出所有可能的到達(dá)出口的車廂排列總數(shù)（不必給出每種排列）。出口- 口 2旦仁L UI SJ |6、將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位組長(zhǎng)，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長(zhǎng)，共有種選擇方案。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ù)稱為度.Iinn訊 12A A | DI _ 臚 I J 13例如左圖：該圖表達(dá)了 A盤的目錄結(jié)構(gòu)：DI , Dll ,D2均表示子目錄的名字在這里，根目錄的度為 2, D1 子目錄的度為3, D11子目錄的度為4, D12 , D2 , D111 , D112 , D113的度均為1。又不考慮子目 錄的名字，則可簡(jiǎn)單的圖示為如下的樹結(jié)構(gòu)：5若知

5、道一個(gè)磁盤的目錄結(jié)構(gòu)中，度為2的子目錄有2個(gè)，度為3的子目錄有1個(gè)，度為4的子目錄有3個(gè)。試問：度為1的子目錄有幾個(gè)？ 14、已知公式：f(n)-f(n1)+ n(n =1)(n 1)則 f(f(f(3)+2)div 2)的值是()。15、在某工廠裝配30輛汽車，可供選擇的設(shè)備是收音機(jī)，空調(diào)和對(duì)講機(jī)。已知其中15輛汽車有收音機(jī)，8輛有空調(diào)，6輛有對(duì)講機(jī)，而且其中 3輛汽車這三樣設(shè)備都有。請(qǐng)問至少有多少輛汽車沒有提供任何設(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è)

6、獲全部3項(xiàng)參賽資格，則至少有 人沒有獲任何項(xiàng)目參賽資格。17、 某律師事務(wù)所共有15名工作人員，如果以下判斷只有一個(gè)是真的，那么該律師事務(wù)所會(huì)使用計(jì)算機(jī)的人數(shù)是人。(1) 有人會(huì)使用計(jì)算機(jī)(2) 有人不會(huì)使用計(jì)算機(jī)(3) 所長(zhǎng)不會(huì)使用計(jì)算機(jī)18、 現(xiàn)在市場(chǎng)上有一款汽車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ǔ)回來，則他們就會(huì)購買B,否

7、則就不會(huì)購買B。那么B的最高價(jià)格應(yīng)為萬美元。19、 一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)有113個(gè)單位的木材。每張桌子要使用20個(gè)單位的木材，售價(jià)是30元；每張椅子要用16個(gè)單位的木材，售價(jià)是 20元。使用已有的木材生產(chǎn)桌椅(不一定 要用光木材)做多可以買 元錢。20、 75名兒童去游樂場(chǎng)玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中兩種。若每玩一樣的費(fèi)用為5元，游樂場(chǎng)總共收入 700,可知有名兒童沒有玩過其中任何一種。21、某班有50名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫a, b, c三本書的書名，將讀過的書打V,結(jié)果統(tǒng)計(jì)數(shù)字如下：只讀a者8人；只讀

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

9、師讓他們猜一下誰是 第一名。A說：或者F是第一名，或者 H是第一名?！盉說：“我是第一名?！盋說：“G是第一名。”D說：“B不是第一名?！盓說：“A說的不對(duì)?！盕說：“我不是第一名。”G說：“C不是第一名?！盚說：“我同意A的意見。”老師指出，八人中有三人猜對(duì)了，那么，試問第一名是誰？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）金盒子：“肖像不在此盒中?！保?）銀盒子：“肖像在鉛盒中?！保?）鉛盒子：“肖像不在此盒中?！滨U細(xì)婭告訴求婚者，上述三句話中，最多只有一句是真的。請(qǐng)你猜鮑細(xì)婭的肖像究竟放在哪一 個(gè)盒子里？ 。27、 甲乙丙丁四人猜年齡，甲說：“我最大，乙最小，丁第三大”；乙說：“我最大，甲最小，丁第 二大，丙第三大”；丙說：“乙最小，甲第三大

11、” ；丁說：“我最大，丙最小，乙第二大，甲第三 大”。四個(gè)人中每個(gè)人只說對(duì)了一個(gè)結(jié)果，請(qǐng)按從大到小的順序?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、 編號(hào)為1到13的紙牌順時(shí)鐘排成一圈，有人從編號(hào)為1的牌從數(shù)字1開始順時(shí)鐘數(shù)下去，1、2、3、20、21、，一圈又一圈。問：當(dāng)數(shù)到數(shù)字N時(shí)，所在紙牌的編號(hào)為 。31、 “鼠算遺題”。這是日本數(shù)學(xué)家吉田光在1627年提出來的。他是這樣說的：“正月

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

13、方一定可以表示成 n個(gè)連續(xù)的奇數(shù)的和。例如：3“1 = 12= 3+ 533= 7+ 9 +113.4 =13 十 15+17+19在這里，若將每一個(gè)式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請(qǐng)寫出X與n之間的關(guān)系表達(dá)式：34、兔子繁殖”。小兔子出生一個(gè)月后便可長(zhǎng)成大兔子，大兔子每月都可以繁殖， 生出一對(duì)小免子。假設(shè)1月份有1對(duì)小兔子，2月份便會(huì)有1對(duì)大兔子和1對(duì)小兔子共2對(duì)兔子，依此繁殖速度，則 m月份兔子的對(duì)數(shù) F(m) 的值為。練習(xí)題(二)(問題解答專練)答案1、(1)193432、5x4x3x3x3x3x3=4860(種)3、C6 或 204、1266、357、751&答：有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果；可畫出的這些二叉樹為:9、 ABCACB BACBCACBA10、答：511、答：1112、1113、9 個(gè)14 、5515、716、717、 1518、2.0419、16020、1021、(1)讀過a的人數(shù)是12人。(2) 一本書也沒讀過的人數(shù)是30人。22、ncl23、a,b,c,f24、C是第一名25、2413 和3 14 226、金27、丁甲丙乙28、小張是工人、是教師、是律師29、 1+(N-1