最新NOIP普及組試題精選

1、NOIP 普及組(初賽)試題精選一、計(jì)算機(jī)系統(tǒng)1. 在以下各項(xiàng)中，()不是CPU的組成部分。(NOIP2007)A. 控制器B運(yùn)算器C 寄存器D 主板【答案】Do CPU由控制器、運(yùn)算器和寄存器組成。2. 在下列各項(xiàng)中，只有( )不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。(NOIP2007)A. Byte B . KB C . UB D . TB【答案】C。存儲(chǔ)容量： Byte=8 bit (位)、1KB=1024B、1MB=1024KB 1GB=1024MB 1TB=1024G Bo3. 與十進(jìn)制數(shù) 1770 對應(yīng)的八進(jìn)制數(shù)是( )。( NOIP2007)A . 3350 B . 3351 C . 33

2、52 D . 3540【答案】C?？疾檫M(jìn)制轉(zhuǎn)換，掌握十進(jìn)制、二進(jìn)制、八進(jìn)制和十六進(jìn)制互換，以及多個(gè)不同進(jìn)制 數(shù)的運(yùn)算(轉(zhuǎn)換為同一進(jìn)制數(shù)進(jìn)行計(jì)算)。4. 與十進(jìn)制數(shù) 28.5625 相等的四進(jìn)制數(shù)是()。( NOIP2008)A. 123.21B. 131.22 C . 130.22 D . 130.21【答案】D。熟練掌握進(jìn)制轉(zhuǎn)換的知識(shí)。5. 計(jì)算機(jī)在工作過程中，若突然停電，()中的信息不會(huì)丟失。(NOIP2008)A. ROM和 RAM B . CPU C . ROM D . RAM【答案】Co ROM(只讀存儲(chǔ)器)斷電后信息不丟失，RAM(隨機(jī)存儲(chǔ)器，內(nèi)存)斷電后信息全部丟失。6. 在 3

3、2*32 點(diǎn)陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是()。( NOIP2008)A512B256 C384D128【答案】Bo 32*32點(diǎn)陣的字庫，每個(gè)字占字節(jié)數(shù)為32*32/8=128字節(jié)（1個(gè)字節(jié)等于8個(gè)二進(jìn)制位， 1Byte=8bits ，而 1 位對應(yīng)點(diǎn)陣中的 1 個(gè)點(diǎn)）。所以 2 個(gè)漢字共要 256 個(gè)字節(jié)。7. 在下面各世界頂級(jí)的獎(jiǎng)項(xiàng)中， 為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng) 是（）o（ NOIP2006）A. 沃爾夫獎(jiǎng)B.諾貝爾獎(jiǎng)C. 菲爾茲獎(jiǎng)D. 圖靈獎(jiǎng)【答案】D。沃爾夫獎(jiǎng)主要是獎(jiǎng)勵(lì)對推動(dòng)人類科學(xué)與藝術(shù)文明做岀杰岀貢獻(xiàn)的人士；諾貝爾獎(jiǎng)有生理或醫(yī)

4、學(xué)獎(jiǎng)、 文學(xué)獎(jiǎng)、 物理學(xué)獎(jiǎng)、 化學(xué)獎(jiǎng)、 經(jīng)濟(jì)學(xué)獎(jiǎng)和和平獎(jiǎng)； 菲爾茲獎(jiǎng)數(shù)學(xué)界的諾貝爾獎(jiǎng)； 圖靈獎(jiǎng)計(jì)算機(jī)界的諾貝爾獎(jiǎng)， 2000 年姚期智獲得“圖靈獎(jiǎng)”，也是迄今為止獲得此項(xiàng)殊榮的 唯一華裔計(jì)算機(jī)科學(xué)家。二、網(wǎng)絡(luò)和數(shù)據(jù)庫1. 在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。（ NOIP2007）A.二叉樹B.多叉樹 C .哈希表D .二維表【答案】D。關(guān)系數(shù)據(jù)庫是用二維表表示邏輯結(jié)構(gòu)，類似于Excel o2. LAN的含義是（）。（NOIP2007）A.因特網(wǎng)B局域網(wǎng)C 廣域網(wǎng)D 城域網(wǎng)【答案】Bo Internet （因特網(wǎng)）、LAN （局域網(wǎng)）、 WAN（廣域網(wǎng)）、 MAN（城域網(wǎng)）

5、3. Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（ ）是典型的 Web 2.0 應(yīng)用。（ NOIP2008）A. SinaB. Flicker C. Yahoo D . Google【答案】Bo Web2.0最大的特點(diǎn)就是任何人可以參與、發(fā)布網(wǎng)頁信息，如博客、播客（土豆、優(yōu) 酷等）、維基百科等。4. 常見的郵件傳輸服務(wù)器使用（ ）協(xié)議接收郵件。（ NOIP2005）A. HTTP B. SMTP C. TCP D. FTP E. POP3【答案】Eo SMTP-發(fā)送郵件協(xié)議；POP3-接收郵件協(xié)議；HTTP-超文本傳輸協(xié)議；FTP-文件傳輸協(xié) 議； TCP

6、/IP- 傳輸控制協(xié)議 /因特網(wǎng)互聯(lián)協(xié)議，它是 Internet 最基本的協(xié)議。）。（ NOIP2004）5. 下列網(wǎng)絡(luò)中常用的名字縮寫對應(yīng)的中文解釋錯(cuò)誤的是（A、WWW(World Wide Web):萬維網(wǎng)B 、 URL(Uinform Resource Locator )：統(tǒng)一資源定位器）：超文本傳輸協(xié)議：快速傳輸協(xié)議）：傳輸控制協(xié)議C 、 HTTP(Hypertext Transfer ProtocolD 、 FTP (File Transfer Protocol)E 、 TCP ( T ransfe r Control Protocol【答案】Do FTP:文件傳輸協(xié)議。 URL統(tǒng)一

7、資源定位器（網(wǎng)址）6. 下列哪個(gè)不是數(shù)據(jù)庫軟件的名稱（ ）A 、 MYSQLB 、 SQL SeverC 、 OracleD 、金山影霸【答案】D。數(shù)據(jù)庫軟件常用的有：MYSQL SQLServer、Access、Foxpro、Oracle、Sybase 等。三、編程語言1. 一個(gè)無法靠自身的控制終止的循環(huán)成為“死循環(huán)”，例如，在C語言程序中，語句“ while（1） printf（“ * ”）；"就是一個(gè)死循環(huán)，運(yùn)行時(shí)它將無休止地打印*號(hào)。下面關(guān)于死循環(huán)的說法中，只有（）是正確的。（NOIP2007）A. 不存在一種算法，對任何一個(gè)程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會(huì)岀現(xiàn)死循環(huán)，

8、因而， 任何編譯系統(tǒng)都不做死循環(huán)檢查B. 有些編譯系統(tǒng)可以檢測岀死循環(huán)C. 死循環(huán)屬于語法錯(cuò)誤，既然編譯系統(tǒng)能檢查各種語法錯(cuò)誤，當(dāng)然也應(yīng)該能檢查岀死循環(huán)D. 死循環(huán)與多進(jìn)程中岀現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也可以檢測的【答案】 Ao2. 在 Pascal 語言中，表達(dá)式 （23 or 2 xor 5 ）的值是（ ）o（ NOIP2007）學(xué)習(xí)-好資料A . 18B. 1C23D32【答案】A。本題考查進(jìn)制轉(zhuǎn)換和邏輯運(yùn)算(and、or、not和xor )。對于本題首先將十進(jìn)制整數(shù)轉(zhuǎn)換二進(jìn)制數(shù)，然后再按位進(jìn)行邏輯運(yùn)算。16842110111(=23)(or)00010(=2)

9、10111(xor)00101(=5)10010(=18)7. (2070) 16 + (34) 8 的結(jié)果是()。(NOIP2007)A.( 8332) ioB.( 208A) 16 C .( ) 2 D . (20212) 8【答案】A。本題兩個(gè)數(shù)分別是十六進(jìn)制和八進(jìn)制，故先將它們轉(zhuǎn)換為二進(jìn)制，然后再進(jìn)行計(jì)算和轉(zhuǎn)換。 (2070) 16=(0010,0000,0111,0000) (每位展開為 4 位二進(jìn)制數(shù)) (34) 8= (11,100) 2(每位展開為3位二進(jìn)制數(shù)) 利用二進(jìn)制數(shù)的運(yùn)算法則，得到兩者相加為(0010,0000,0001 ) 2=( 8332) 108. (2008)

10、10+(5B)16 的結(jié)果是()。(NOIP2008)A.( 833)16B.( 2089) 10C.( 4163)8 D .( ) 2)o( NOIP2007)【答案】Ao9. 設(shè)A=B=True, C=D=False，下面邏輯運(yùn)算表達(dá)式值為假的有(A . (AA B) V (C A DV A)B. (A A B) V C) A D)C. AA (B V CV D) V DD. (A A (D V C) A B【答案】D?！啊北硎緉ot，“A”表示and (與，并且)，“V”表示 or (或者)。10. 在下列關(guān)于計(jì)算機(jī)語言的說法中，不正確的是()。( NOIP2006)A. Pascal和

11、C都是編譯執(zhí)行的高級(jí)語言B. 高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D. 與匯編語言相比，高級(jí)語言程序更容易閱讀【答案】C。第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言是Smalltalk 。四、數(shù)據(jù)結(jié)構(gòu)1. 地面上有標(biāo)號(hào)為 A、B C的三根柱，在 A柱上放有10個(gè)直徑相同中間有孔的圓盤，從上到下依次編號(hào)為 1，2，3，將A柱上的部分盤子經(jīng)過 B柱移入C柱，也可以在 B柱上暫 存。如果 B 柱上的操作記錄為“進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、進(jìn)、出、出”。那么，在C柱上，從下到上的編號(hào)為（）。（NOIP2007）A2 4 3

12、6 5 7B2 4 1 2 5 7 C2 4 3 1 7 6D2 4 36 7 5【答案】D。棧，后進(jìn)先岀。2. 某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的岀入記錄為： “進(jìn)，岀，進(jìn)，進(jìn)，進(jìn)，岀，岀，進(jìn)，進(jìn)，進(jìn)，岀 , 岀” 假設(shè)車輛入站的 順序?yàn)?，2，3，則車輛岀站的順序?yàn)椋ǎ?。（NOIP2006）A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 4, 3, 7,6D. 1, 4, 3, 7, 2【答案】C。棧操作。)。( NOIP2008)3. 完全二叉樹共有 2*N-1 個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（A

13、N-1BNC2*N D2N-1答案】 B。在二叉樹中，結(jié)點(diǎn)的度數(shù)有0、 1、 2 三種情況，其中度為0 的結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。設(shè)D0 表示度為 0 的結(jié)點(diǎn)個(gè)數(shù)，D1表示度為1的結(jié)點(diǎn)個(gè)數(shù)，D2表示度為2的結(jié)點(diǎn)個(gè)數(shù),則有二叉樹結(jié)點(diǎn) =D0+D1+D2。在完全二叉樹中，若除去最下面一層的結(jié)點(diǎn)，則此時(shí)的二叉樹構(gòu)成一個(gè)滿二叉樹，其結(jié)點(diǎn)個(gè)數(shù)為 （奇數(shù)），而題目中的二叉樹共有 2*N-1 （奇數(shù)）個(gè)結(jié)點(diǎn)，所以可以知道完全二叉樹最下面一層的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)個(gè)，得知D仁0。這樣我們只要求岀 D2,就可以得到 D0的值了。接下來，我們來看二叉樹邊的個(gè)數(shù)，由于“邊數(shù)=結(jié)點(diǎn)數(shù) -1 ”（除去根結(jié)點(diǎn)，因?yàn)橹挥兴纳厦鏇]有邊

14、），D0結(jié)點(diǎn)（葉節(jié)點(diǎn)）無發(fā)岀的邊，D1結(jié)點(diǎn)個(gè)數(shù)為0 , D2發(fā)岀的邊數(shù)為 D2*2，所以得到：邊數(shù)=結(jié)點(diǎn)數(shù)-1=D2*2 f 結(jié)點(diǎn)數(shù)=D2*2+1 fD2=(結(jié)點(diǎn)數(shù)-1 ) -2=(2*N-2) - 2=N-14.D0+D2=2*N-1D0=2*N-1-(N-1)=N完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為1 1 ，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（NOIP2005)E. 6A. 4 B.3 C.5 D. 2 【答案】E。用上題的結(jié)論。5. 高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1 的滿二叉樹。 在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0 ，如果某個(gè)均衡的二叉樹共有 2381

15、個(gè)結(jié)點(diǎn)， 則該樹的樹高為（）。A. 10 B. 11 C. 12 D. 13【答案】B。滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為（根結(jié)點(diǎn)的深度為1）,而這棵二叉樹共有2381個(gè)結(jié)點(diǎn)，可以算出上面滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)是 =2048-1=2047 ，故這棵樹有 11+1（最下面 1 層） =12。由 于題目中根結(jié)點(diǎn)的深度是從 0（一般從 1）開始的，所以該樹高 12-1=11 。6. 遞歸過程或函數(shù)調(diào)用時(shí)， 處理參數(shù)和返回地址， 通常使用一種稱為 （ ）的數(shù)據(jù)結(jié)構(gòu)NOIP2008)A隊(duì)列B.多維數(shù)組C.線性表D .?！敬鸢浮緿。7.設(shè) T 是一棵有n 個(gè)頂點(diǎn)的樹，下列說法不正確的是（)。( NOIP2008)A. T有

16、n 條邊B. T 是連通的C. T 是無環(huán)的D. T 有 n-1 條邊【答案】 A。 n 個(gè)頂點(diǎn)的樹，除了根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)上方都連接一條邊，所以一共有n-1 條邊。8. 已知 7 個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點(diǎn)的編號(hào)， 以下同） ，中根遍歷是 4 2 6 5 1 7 3 ，則該二叉樹的后根遍歷是（ ）。（ NOIP2007）A4 6 5 2 7 3 1B4 6 5 2 1 3 7 C 4 2 3 1 5 4 7 D4 6 53 1 7 2【答案】A。先根遍歷=先序遍歷（根-左-右），中根遍歷=中序遍歷（左-根-右），后根遍歷=后序遍歷（左-右-根）。中

17、序遍歷保證了左子樹的所有結(jié)點(diǎn)在它左邊，右子樹的結(jié)點(diǎn)在它右邊。過程如下：后用先序遍歷結(jié)果，找到父結(jié)點(diǎn)， 然后按照中序遍歷結(jié)果將其左右子樹分開；然后再從先序遍歷結(jié)果中再找到左子樹的根結(jié)點(diǎn)，再重復(fù)以上操作直到所有結(jié)點(diǎn)歸位。先序： 1 2 4 5 6 3 7中序：4 2 6 5 1 7 3 先序第 1個(gè)數(shù)字是 1（二叉樹根），將中序中 1的左半段與右半段分開，即得到 1 的左子樹 是 4 2 6 5 ，右子樹是 7 3 ，表示為（ 4 2 6 5 ）1（7 3 ）。圖1 再看 1 的左子樹 4 2 6 5 ，其對應(yīng)的先序 2 4 5 6 ，此時(shí)先序第 1 個(gè)數(shù)字是 2（左子樹的根） 將中序以 2再次劃

18、分為左子樹 4，右子樹 6 5 ，表示為（ 4）2（6 5 ），如圖 2所示。圖 2 圖 3 圖 4 2 的右子樹中序?yàn)?6 5 ，先序?yàn)?5 6 ，則 2 的右子樹的根是 5，再看中序，得到（ 6）5，到這 里完成結(jié)點(diǎn) 1 左子樹的結(jié)構(gòu)，如圖 3 所示。 同樣方法構(gòu)建 1 右子樹，得到（ 7）3，如圖 4 所示。 依照后序遍歷的特點(diǎn)（左t右t根），得到結(jié)果：4 6 5 2 7 3 1 ，故答案為Ao【思考】（ 1 ）已知中序和后序，如何求先序？（2）已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清，試構(gòu)造出該二叉樹。先序序列：_BC_EF_中序序列： BDE_AG_H后序序列

19、： _DC_GH_A數(shù)字為節(jié)點(diǎn)的編號(hào)，下同），中根遍)o( NOIP2008)9. 二叉樹T,已知其先根遍歷是1 2 4 3 5 7 6歷 2 4 1 5 7 3 6 ，則該二叉樹的后根遍歷是（A4 2 5 7 6 3 1 B4 2 7 5 6 3 1 C7 4 2 5 6 3 1 D4 2 7 6 5 31【答案】 Bo10. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是 3 2 5 6 4 1 ，則該二叉樹的可能的中根遍歷是（)o( NOIP2006)A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 1 3 5 4 6

20、 D. 2 3 1 4 6 5【答案】B。先序遍歷和后序遍歷不能確定唯一中序遍歷，對于本題的結(jié)果可以是：2 3 1 5 46 或者 3 2 1 5 4 6。11. 二叉樹T的寬度優(yōu)先遍歷序列為 A B C D E F G H I ，已知A是C的父結(jié)點(diǎn)，D是G的父 結(jié)點(diǎn)， F 是 I 的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為 0），可知 F 的父結(jié)點(diǎn)是（ ）。（ NOIP2005）A. 無法確定 B. B C. C D. D E. E【答案】 C。12. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e依次入棧，以下岀棧序列不可能岀現(xiàn)的有（）。（ NOIP2006）A. a, b

21、, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e,b, a【答案】C。選項(xiàng)C中的岀棧序列：a,e,c,b,d ，a,e岀棧，則棧中必是 b,c,d （從下往上），岀 棧序列只能是 d,c,b ，而不是 c,b,d 。13. 滿二叉樹的葉節(jié)點(diǎn)為N,則它的節(jié)點(diǎn)總數(shù)為（）（NOIP2004）A、NB、2N C、2N-1 D、2N+1 E、2AN-1【答案】C。滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為（根結(jié)點(diǎn)的深度為1），其葉子節(jié)點(diǎn)的個(gè)數(shù)為，所以“結(jié)點(diǎn)個(gè)數(shù)” =“葉子節(jié)點(diǎn)” *2-1=2N-1 。五、算法1. 近 20年來，許多計(jì)算機(jī)專家都大力推崇遞歸算法，認(rèn)為它

22、是解決較復(fù)雜問題的強(qiáng)有力的 工具。在下列關(guān)于遞歸算法的說法中，正確的是（）。（ NOIP2007）A. 在1977年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級(jí)語言“F0RTRAN7”禁止在程序使用遞歸，原因之 一是該方法可能會(huì)占用更多的內(nèi)存空間B. 和非遞歸算法相比，解決同一個(gè)問題，遞歸算法一般運(yùn)行得更快一些C. 對于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些D. 對于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)sin（x）,應(yīng)用程序中的語句"y=sin（sin（x）;”就是-種遞歸調(diào)用。【答案】 A。2. 在下列各種排序算法中， 不是以“比較” 作為主要操作的算法是 （）（NOIP2006）A. 選擇排序B.

23、 冒泡排序C. 插入排序D. 基數(shù)排序【答案】0基于“比較”的排序：冒泡、選擇、插入、快速、歸并、堆、希爾等；而“非比較” 的排序：計(jì)數(shù)排序、桶排序、基數(shù)排序等。3. 設(shè)字符串S="Olympic" ，S的非空子串的數(shù)目是（）。（NOIP2008）A. 28B. 29 C . 16 D . 17【答案】A。串長為1的子串有7個(gè)，串長為2的子串有6個(gè)，串長為 7的子串有1個(gè), 共 7+6+5+2+1=28。4. 將數(shù)組 8， 23， 4， 16， 77， -5， 53， 100中的元素按從小到大的順序排列，每次可以交 換任意兩個(gè)元素，最少需要交換（）次。（ NOIP2008）

24、A. 4 B . 5 C . 6 D . 7【答案】B。選擇排序，第1次是將第1個(gè)元素與右邊7個(gè)元素中最小的一個(gè)交換，第 2次是將 第 2 個(gè)元素與右邊 6 個(gè)元素中最小的一個(gè)交換， 。 若當(dāng)前元素已是其余元素中最小的， 則不 需要交換。5. 對有序數(shù)組 5 ， 13， 19， 21， 37， 56，元素 19 的查找長度（比較次數(shù)）是（）。64， 75， 88， 92， 100 進(jìn)行二分查找，成功查找NOIP2008）A. 1B【答案】B。首先與中間元素56 比較，比 56 小，則繼續(xù)在56 左側(cè)的 5 個(gè)元素中查找；與這個(gè)元素的中間元素 19 比較，相等，則找到，所以只需要比較 2次6.

25、由3個(gè)a, 1個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc ”的共有（）個(gè)。（NOIP2004）A 、 20 B 、 8 C 、 16 D 、 12 E 、 24【答案】D。把"abc "看成一個(gè)整體，記為 d。本題轉(zhuǎn)換為2個(gè)a、1個(gè)c、1個(gè)d進(jìn)行全排列，由于有2個(gè)a，所以要除以a的全排列個(gè)數(shù)，即。六、問題求解1. 書架上有4本不同的書A、B、C D。其中A和B是紅皮的，C和D是黑皮的。把這 4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有 種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有種擺法。（NOIP2OO8）【答案】12,4。

26、由于要求黑皮的書排在一起，所以把C和D做為一個(gè)排列的對象，故3個(gè)對象的全排列為，而C和D可以互換位置，所以第一空的解為：=12。 紅皮書要擺在一起，黑皮書要擺在一起，所以我們將A和B作為一個(gè)排列對象， C和D作為一個(gè)排列對象，另外 A必須比C靠左，則必然是 AB空，由于A和B可以互換（=2），C和D 可以互換（=2），所以擺法有 2X 2=4種。2. 有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為 。（ NOIP2008）城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市415307

27、9城市51236702城市615125920【答案】7(1->2->5->6)。參考圖的單源最短路徑( Dijkstra 算法)3. NOIP2007第1題：子集劃分將n個(gè)數(shù)(1，2,，n)劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的劃分方法依次為(1),(234),(2),(134),(3),(124), (4),(123), (12),(34)，(13),(24), (14),(23)。當(dāng) n=6, r=3 時(shí)，S(6,3)=。(提示：先固定一個(gè)數(shù)，對于其余

28、的 5個(gè)數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對原固 定的數(shù)進(jìn)行分析。)【答案】90。 組合：將6分成3個(gè)集合，只有3種分法：4個(gè)、1個(gè)、1個(gè)；3個(gè)、2個(gè)、1個(gè)；2個(gè)、2 個(gè)、2個(gè)，所以利用組合數(shù)學(xué)知識(shí)，可以得到。說明：最后一種可能性是分成2個(gè)、2個(gè)、2個(gè),從6個(gè)數(shù)取岀2個(gè)的組合數(shù)為，再從余下的4個(gè)數(shù)中取岀2個(gè)的組合數(shù)為，最后余下的2個(gè)數(shù)作為一個(gè)集合，但這種方法會(huì)岀現(xiàn)重復(fù)的情況，如(12),(34),(56)、(12),(56),(34)、(34),(12),(56)、(34),(56),(12)、(56),(12),(34)、 (56),(34),(12) 即卩=6 種。 遞推：s

29、(n,r)=s(n-1,r)*r+s(n-1,r-1)，其中s(n,r)表示n個(gè)數(shù)分為r個(gè)集合的方法種數(shù)。先可以固定一個(gè)數(shù)，如k，則接下來有兩種方法：一種是將余下的n-1個(gè)數(shù)分成r-1個(gè)集合，即數(shù)k獨(dú)占一個(gè)集合；另一種是將余下的 n-1個(gè)數(shù)分成r個(gè)集合，再將前面固定的那個(gè)數(shù)， 任意放 在r個(gè)集合的任一個(gè)中，則方法有s(n-1,r-1)*r 種。利用加法原理，得到這個(gè)遞推式。由于它是二維的，所以我們可以用填表的方法來求解岀答案，每個(gè)單元格中的數(shù)等于它左下方數(shù)+下方數(shù)x r。r=1r=2r=3n=613190n=511525n=4176n=3131n=2110n=11004. NOIP2007 第

30、 2 題（最短路線）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有7條南北向的縱街,5條東西向的橫街。現(xiàn)要從西南角的 A走到東北角的B,最短的走法共有多少種？ BA【答案】210。遞推：設(shè)f（i,j）表示到達(dá)第i行（橫街）、第j列（縱街）時(shí)的最短走法，故可以寫岀遞推式:(i,j)=f(i,j-1)+f(i-1,j)f(i,j-1)f(i,j)f(i-1,j)15153570126210141020355684136101521281234567A1111111組合:無論怎么走法，每種走法最終均是由向上走 4 步，向右走 6 步組成，一共 10 步，所以全部 走法是從 10 步里選出其中的 4

31、 步向上走（其余 6 步向右走），即 （種）。5. （尋找假幣） 現(xiàn)有 80 枚硬幣， 其中有一枚是假幣， 其重量稍輕， 所有真幣的重量都相同， 如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第 1 次的稱重 方法。請寫出你的結(jié)果： 。（ NOIP2006）【答案】 4，第一步：分成 3 組： 27， 27，26，將前 2 組放到天平上。若第 1 組與第 2組相等，則假幣在第 3 組中；若第 1組比第 2組輕，則假幣在第 1組中，否則就 在第 2 組中。以此類推，第 2 步： 9 9 927 枚）或 9 9 8 （26 枚）；第 3 步： 3 3 39 枚）或 3 3

32、2 （ 8 枚）第 4 步： 1 1 13 枚）或 1 1 （2 枚）6. （取石子游戲） 現(xiàn)有 5 堆石子，石子數(shù)依次為 3 ， 5， 7， 19，50，甲乙兩人輪流從任一 堆中任?。看沃荒苋∽砸欢眩荒懿蝗。?, 取最后一顆石子的一方獲勝。甲先取，問甲有沒有 獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取 多少？請寫出你的結(jié)果： 。（ NOIP2006）【答案】從 50 中取走 32 粒剩余 18 粒是正確的。算法： 從其中一堆中取 n 個(gè)，使得剩余的所有數(shù)目正好是“必負(fù)局（此時(shí)先取必輸?shù)木置妫薄?所謂“必負(fù)局”是指把剩余的每一堆的數(shù)目都轉(zhuǎn)化成二進(jìn)制的數(shù)， 然后把它們相加，規(guī)定做不進(jìn)位的加法（也就是異或運(yùn)算），即 0+0 = 0, 1+0 = 0, 0+1 = 1,1+1 = 0 （不進(jìn)位），如果所 得和是 0（多個(gè) 0）