NOIP初賽問(wèn)題求解專練

1、12006年南海區(qū)信息學(xué)夏令營(yíng)013班練習(xí)題（二）（問(wèn)題解答專練）-、問(wèn)題求解：1、 平面上有 7 個(gè)點(diǎn)，共有 3 個(gè)點(diǎn)共線，其余再也沒(méi)有 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)掉相鄰的兩盞或兩盞以上的燈。在兩端的燈也不能

2、關(guān)掉的情況下，求滿足條件的關(guān)燈辦法有_種？4、若一個(gè)棧中有 5 個(gè)元素，另一個(gè)棧中有 4 個(gè)元素，則他們出棧的的方法共有多少種？_5、 如下圖，有一個(gè)無(wú)窮大的的棧 S,在棧的右邊排列著 1,2,3,4,5 共五個(gè)車廂。其中每個(gè)車廂可以向左 行走,也可以進(jìn)入棧S 讓后面的車廂通過(guò)?，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 種排法：紅紅黃黃黃紅黃紅黃黃紅黃黃紅黃黃紅紅黃黃黃紅黃紅黃黃黃黃紅紅問(wèn)題：當(dāng) N=4,M=3 時(shí)有多少種不

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

4、同學(xué)，已知張、王為2物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員。如果要在3 個(gè)小組分別選出 3位組長(zhǎng)，一位同學(xué)最多只能擔(dān)任一個(gè)小組的組長(zhǎng)，共有種選擇方案。12、無(wú)向圖 G 有 16 條邊，有 3 個(gè) 4 度頂點(diǎn)、4 個(gè) 3 度頂點(diǎn)，其余頂點(diǎn)的度均小于 3，則 G 至少有_個(gè)頂點(diǎn)。313、在磁盤的目錄結(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 , D

5、111 , D112 , D113 的度均為 1。又不考慮子目 錄的名字，則可簡(jiǎn)單的圖示為如下的樹(shù)結(jié)構(gòu)：若知道一個(gè)磁盤的目錄結(jié)構(gòu)中，度為2 的子目錄有 2 個(gè)，度為 3 的子目錄有 1 個(gè)，度為 4 的子目錄有 3 個(gè)。試問(wèn)：度為 1 的子目錄有幾個(gè)？_14、已知公式：則 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)問(wèn)至少有多少輛汽車沒(méi)有提供任何設(shè)備？_16、 某班有 30 個(gè)同學(xué)報(bào)名參加 100、400、800m3 個(gè)運(yùn)動(dòng)

6、項(xiàng)目比賽。已知有 6 人獲 100m 參賽資格， 8 人獲 400m參賽資格，15 人獲 800m 參賽資格，且其中有 3 個(gè)獲全部 3 項(xiàng)參賽資格，則至少有人沒(méi)有獲任何項(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 萬(wàn)美元。汽車 A 每加侖汽油可以行駛 20 英里。普通汽車每年大約行駛 12000 英里。油價(jià)是每加侖 1 美元。不久我公司就要推出新款節(jié)油汽車B,汽車 B 每加侖汽油可以行駛 30

7、 英里?，F(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)買 B。那么 B 的最高價(jià)格應(yīng)為_(kāi)萬(wàn)美元。19、 一個(gè)家具公司生產(chǎn)桌子和椅子?，F(xiàn)有113 個(gè)單位的木材。每張桌子要使用20 個(gè)單位的木材，售價(jià)是 30 元；每張椅子要用 16 個(gè)單位的木材，售價(jià)是 20 元。使用已有的木材生產(chǎn)桌椅(不一定 要用光木材)做多可以買_元錢。20、 75 名兒童去游樂(lè)場(chǎng)玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行軌道，乘宇宙飛船。已知其中20 人這三種東西都玩過(guò)，55 人至少玩過(guò)其中兩種。若每玩一樣的費(fèi)用為5 元，游樂(lè)場(chǎng)

8、總共收入 700,可知有_名兒童沒(méi)有玩過(guò)其中任何一種。21、某班有 50 名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫a, b, c 三本書的書名，將讀過(guò)的書打V,結(jié)果統(tǒng)計(jì)數(shù)字如下：只讀 a 者 8 人；只讀 b 者 4 人；只讀 c 者 4 人；全部讀過(guò)的有 2 人；讀過(guò) a, b 兩本書的有 4 人；讀過(guò) a, c 兩本書的有 2 人；讀過(guò) b, c 兩本書的有 3 人；f(n)-f(n1)+ n(n =1)(n 1)4(1)讀過(guò) a 的人數(shù)是()(2) 本書也沒(méi)有讀過(guò)的人數(shù)是()22、已知一串明文與對(duì)應(yīng)的密碼如下：明文:home密碼:fmkc若采用與上述相同的加密算法，則明文 pen 的密碼是_。

9、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é)獲得了前八名，老師讓他們猜一下誰(shuí)是 第一名。A 說(shuō)：或者 F 是第一名，或者 H 是第一名?！盉 說(shuō)：“我是第一名。”C 說(shuō)：“G 是第一名。”D 說(shuō)：“B 不是第一名。”E 說(shuō)：“A 說(shuō)的不對(duì)。”F 說(shuō)：“我不是第一名。”G 說(shuō)：“C 不是第一名?！盚 說(shuō)：“我同意 A 的意見(jiàn)?！崩蠋?/p>

10、指出，八人中有三人猜對(duì)了，那么，試問(wèn)第一名是誰(shuí)？_25、 N 皇后問(wèn)題要求在 N*N 的棋盤上放置 N 個(gè)皇后，使其不能互相攻擊，即任意2 個(gè)皇后不能處 于棋盤上的同一行、同一列或同一斜線上。則當(dāng) N=4 時(shí)，擺放方法有哪兩種？（答案寫成“a b c d”的形式，表示擺放在第一行的第 a 列、第二行的第 b 列、第三行的第 c 列和第四行的第d 列）_26、莎士比亞在威尼斯商人中，寫富家少女鮑細(xì)婭品貌雙全，貴族子弟、公子王孫紛紛向她求 婚。鮑細(xì)婭按照其父遺囑，由求婚者猜盒訂婚。鮑細(xì)婭有金、銀、鉛三個(gè)盒子，分別刻有三句 話，其中只有一個(gè)盒子，放有鮑細(xì)婭肖像。求婚者通過(guò)這三句話，猜中鮑細(xì)婭的肖像放

11、在哪只 盒子里，就嫁給誰(shuí)。三個(gè)盒子上刻的三句話分別是：（1）金盒子：“肖像不在此盒中?！保?）銀盒子：“肖像在鉛盒中?！保?）鉛盒子：“肖像不在此盒中?！滨U細(xì)婭告訴求婚者，上述三句話中，最多只有一句是真的。請(qǐng)你猜鮑細(xì)婭的肖像究竟放在哪一 個(gè)盒子里？。27、 甲乙丙丁四人猜年齡，甲說(shuō)：“我最大，乙最小，丁第三大”；乙說(shuō)：“我最大，甲最小，丁第 二大，丙第三大”；丙說(shuō)：“乙最小，甲第三大” ；丁說(shuō)：“我最大，丙最小，乙第二大，甲第三 大”。四個(gè)人中每個(gè)人只說(shuō)對(duì)了一個(gè)結(jié)果，請(qǐng)按從大到小的順序?qū)懗稣_結(jié)果。1、2、3、4、28、小王、小張和小李中一位是工人，一位是教師，一位是律師。現(xiàn)在知道小李比律師年

12、齡大，小 王和教師不同歲，教師比小張年齡小。問(wèn)：_是工人、_是教師、_是律師。29、現(xiàn)在的時(shí)間為 12 點(diǎn)正，再過(guò) N 個(gè)小時(shí)（N 為整數(shù)）為幾點(diǎn)鐘？_30、 編號(hào)為 1 到 13 的紙牌順時(shí)鐘排成一圈，有人從編號(hào)為1 的牌從數(shù)字 1 開(kāi)始順時(shí)鐘數(shù)下去，1、2、3、20、21、，一圈又一圈。問(wèn)：當(dāng)數(shù)到數(shù)字 N 時(shí)，所在紙牌的編號(hào)為_(kāi)。31、 “鼠算遺題”。這是日本數(shù)學(xué)家吉田光在1627 年提出來(lái)的。他是這樣說(shuō)的：“正月里，鼠父鼠母生了 12 只小鼠，于是大小鼠共 14 只。二月里，兩代鼠全部配對(duì)，每對(duì)鼠又各生了12 只小鼠。因此共有 98 只。如這樣下去，每月所有的鼠全部配對(duì)，每對(duì)鼠又各生了1

13、2 只小鼠。十二個(gè)月后，鼠的總數(shù)是多少呢？”假設(shè)每月都按這樣的規(guī)律生，而所生的鼠又全部成活，十二個(gè)月后，鼠的總數(shù)是 402 只。你能找出計(jì)算此數(shù)的公式嗎？此公式為_(kāi)。32、 有 2 h 的一個(gè)長(zhǎng)方形方格，用一個(gè) 1 2 的骨牌鋪滿方格。例如 n=3 時(shí)，為 2X3 方格。此時(shí)用一 個(gè) 1X的骨牌鋪滿方格，共有 3 種鋪法：5試對(duì)給出的任意一個(gè) n(n0)，求出鋪法總數(shù)的遞推公式。_33、公式推導(dǎo)： 根據(jù) Nocomachns 定理，任何一個(gè)正整數(shù) n 的立方一定可以表示成 n 個(gè)連續(xù)的奇數(shù)的和。例如：3“1 = 12= 3+ 533= 7+ 9 +113.4 =13 十 15+17+19在這里

14、，若將每一個(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)的值為_(kāi)。練習(xí)題(二)(問(wèn)題解答專練)答案7、751&答：有 5 種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果；可畫出的這些二叉樹(shù)為:33、關(guān)系表達(dá)式:N*N-N+11、(1)193432、5x4x3x3x3x3x3=4860(種)3、C6或 204、1266、359、 ABCACB BACBCACBA10、答：511、答：1112、 1113、9個(gè)14、5515、716、717、1518、2.0419、 16020、1021、(1