NOIP初賽知識點復習總結

1、NOIP2014初賽指導初賽的目的初賽的目的進入復賽（本賽區(qū)前進入復賽（本賽區(qū)前15%）考察計算機基礎知識和編程的基本能力，并對知識面的廣考察計算機基礎知識和編程的基本能力，并對知識面的廣度進行測試度進行測試復賽排名重要依據(jù)復賽排名重要依據(jù)初賽試題形式初賽試題形式 初賽：初賽全部為筆試，滿分初賽：初賽全部為筆試，滿分100分。試題由四部分組成：分。試題由四部分組成： 1、選擇題：共、選擇題：共20題，每題題，每題1.5分，共計分，共計30分。提高組每題有分。提高組每題有5個備選答案，個備選答案，前前10個題為單選題個題為單選題(即每題有且只有一個正確答案，選對得分即每題有且只有一個正確答案，選

2、對得分)，后，后10題為不定項選題為不定項選擇題擇題(即每題有即每題有1至至5個正確答案，只有全部選對才得分個正確答案，只有全部選對才得分)。普及組。普及組4個備選答案，全為個備選答案，全為單選題。單選題。 2、問題求解題：共、問題求解題：共2題，每題題，每題5分，共計分，共計10分。試題給出一個敘述較為簡單的分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。考生問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。考生給出的答案與標準答案相同，則得分：否則不得分。給出的答案與標準答案相同，則得分：否則不得分。 3、程序閱讀理解題：

3、共、程序閱讀理解題：共4題，每題題，每題8分，共計分，共計32分。題目給出一段程序分。題目給出一段程序(不一不一定有關于程序功能的說明定有關于程序功能的說明)，考生通過閱讀理解該段程序給出程序的輸出。輸出與標，考生通過閱讀理解該段程序給出程序的輸出。輸出與標準答案一致，則得分；否則不得分。準答案一致，則得分；否則不得分。 4、程序完善題：共、程序完善題：共2題，每題題，每題14分，共計分，共計28分。題目給出一段關于程序功能分。題目給出一段關于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分

4、并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。去的語句。填對則得分；否則不得分。 知識范圍知識范圍內(nèi)容與要求內(nèi)容與要求 1、計算機的基本常識、計算機的基本常識 計算機和信息社會計算機和信息社會(信息社會的主要特征、計算機的主要特征、數(shù)信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡的主要特征、數(shù)字化字通信網(wǎng)絡的主要特征、數(shù)字化) 信息輸入輸出基本原理信息輸入輸出基本原理(信息交換環(huán)境、文字圖形多媒體信息的輸信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式入輸出方式

5、) 信息的表示與處理信息的表示與處理(信息編碼、微處理部件信息編碼、微處理部件MPU、內(nèi)存儲結構、指、內(nèi)存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構令，程序，和存儲程序原理、程序的三種基本控制結構) 信息的存儲、組織與管理信息的存儲、組織與管理(存儲介質(zhì)、存儲器結構、文件管理、數(shù)存儲介質(zhì)、存儲器結構、文件管理、數(shù)據(jù)庫管理據(jù)庫管理) 信息系統(tǒng)組成及互連網(wǎng)的基本知識信息系統(tǒng)組成及互連網(wǎng)的基本知識(計算機構成原理、槽和端口的計算機構成原理、槽和端口的部件間可擴展互連方式、層次式的互連結構、互聯(lián)網(wǎng)絡、部件間可擴展互連方式、層次式的互連結構、互聯(lián)網(wǎng)絡、TCPIP協(xié)議、協(xié)議、HTTP協(xié)議、

6、協(xié)議、WEB應用的主要方式和特點應用的主要方式和特點) 人機交互界面的基本概念人機交互界面的基本概念(窗口系統(tǒng)、人和計算機交流信息的途徑窗口系統(tǒng)、人和計算機交流信息的途徑(文本及交互操作文本及交互操作) 信息技術的新發(fā)展、新特點、新應用等。信息技術的新發(fā)展、新特點、新應用等。2、計算機的基本操作、計算機的基本操作 WINDOWS和和LINUX的基本操作知識的基本操作知識 聯(lián)網(wǎng)的基本使用常識聯(lián)網(wǎng)的基本使用常識 (網(wǎng)上瀏覽、搜索和查詢等網(wǎng)上瀏覽、搜索和查詢等) 常用的工具軟件使用常用的工具軟件使用(文字編輯、電子郵件收發(fā)等文字編輯、電子郵件收發(fā)等)3、程序設計的基本知識、程序設計的基本知識 數(shù)據(jù)結

7、構數(shù)據(jù)結構 程序語言中基本數(shù)據(jù)類型程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點字符、整數(shù)、長整數(shù)、浮點) 浮點運算中的精度和數(shù)值比較浮點運算中的精度和數(shù)值比較 一維數(shù)組一維數(shù)組(串串)與線性表與線性表 記錄類型記錄類型(PASCAL)結構類型結構類型(C) 程序設計程序設計 結構化程序設計的基本概念結構化程序設計的基本概念 閱讀理解程序的基本能力閱讀理解程序的基本能力 具有將簡單問題抽象成適合計算機解決的模型的基本能力具有將簡單問題抽象成適合計算機解決的模型的基本能力 具有針對模型設計簡單算法的基本能力具有針對模型設計簡單算法的基本能力 程序流程描述程序流程描述(自然語言偽碼自然語言偽碼N

8、S圖其他圖其他) 程序設計語言程序設計語言(PASCALCC+，) 基本算法處理基本算法處理 初等算法初等算法(計數(shù)、統(tǒng)計、數(shù)學運算等計數(shù)、統(tǒng)計、數(shù)學運算等) 排序算法排序算法(冒泡法、插入排序、合并排序、快速排序冒泡法、插入排序、合并排序、快速排序) 查找查找(順序查找、二分法順序查找、二分法) 回溯算法回溯算法課程大綱NOIP初賽情況的簡單分析基礎知識二叉樹圖排列組合程序閱讀題程序填空題總結初賽試卷題型分析(提高組)單項選擇 15分(提高組) 不定項選擇 15分（多選少選均不得分）問題求解 10分閱讀程序 32分完善程序 28分初賽試卷題型分析初賽考的知識點，大綱說：計算機基本常識，基本操

9、作和程序設計基本知識。選擇題考查的是知識，而問題解決題、填空更加重視能力的考查。一般說來，選擇題是不需要單獨準備的 ，也無從準備。只要多用心積累就可以了。到是問題解決題目比較固定，大家應當多做以前的題目。寫運行結果需要多做題目，培養(yǎng)良好的程序閱讀和分析能力，而完善程序最好總結一下以前題目常常要你填出來的語句類型。初賽試卷題型分析1.選擇題 一般它們是比較容易得分的，一共30分，不可錯過！ 近幾年來，初賽的考查范圍有了很大的變化，越來越緊跟潮流，需要大家有比較廣泛的知識，包括計算機硬件，軟件，網(wǎng)絡，數(shù)據(jù)結構（例如棧，隊列，排序算法），程序設計語言以及一些基本的數(shù)學知識和技巧（例如排列組合等）。2

10、.填空、問題解決這部分題目對數(shù)學要求要高一點，往往考查的是代數(shù)變形、集合論、數(shù)列（一般是考遞推），也考查 一些算法和數(shù)據(jù)結構知識。建議大家多花一點時間做，盡量做對。初賽試卷題型分析3. 閱讀程序?qū)懗鲞\行結果占的分數(shù)多，但得分率卻不高，較易失分，一旦結果不正確，將丟失全分。這種題型主要考察選手： 程序設計語言的掌握能力 數(shù)學運算能力 耐心、細心的心理品質(zhì)一般做這類題目的關鍵在于能夠分析程序的結構及程序段的功能，找出程序目的，即這個程序想干什么。初賽試卷題型分析完成這類題目的一般方法和步驟是： 從頭到尾通讀程序，大致掌握程序的算法； 通過給程序分段，清理程序的結構和層次，達到讀懂程序的目的； 閱讀

11、程序中特別注意跟蹤主要變量值的變化，也可以用列表的方法，了解變量變化和程序運行的結果，要注意發(fā)現(xiàn)規(guī)律。迄今為止考過的題目還沒有“亂寫”的，總有一點“寫作目的”的。抓住了它，得出答案就變得很容易了，而且對結果也會有信心。寫程序運行結果大綱規(guī)定是必考的。試卷中給出的程序并不復雜，語句的含義容易明白，因此悟性好的選手總是很快就能體會到程序的設計思路并得出正確的答案，而機械模仿計算機硬算出結果的同學往往做得慢的多，而且容易失誤。初賽試卷題型分析4.完善程序這部分題目得分率似乎不高。盡量把一些簡單的填好就行了。建議大家把以前的初賽題目都做一下。常常讓大家填的是：初始化 一些明顯的動作： a.結果沒有儲存

12、在需要的地方。 b.累加器沒有做加法 c.輸出 關鍵動作。在算法描述中出現(xiàn)的比較關鍵的步驟。例如交換排序程序的“交換”操作等很明顯需要完成的操作。分析方法和寫運行結果類似，注意分析變量和程序結構，理解變量和模塊的作用是解題的關鍵。進制轉(zhuǎn)換1二進制與十進制間的相互轉(zhuǎn)換：（1）二進制轉(zhuǎn)十進制方法：“按權展開求和”例：（1011.01）2 （123022121120021122）10（802100.25）10（11.25）10規(guī)律：個位上的數(shù)字的次數(shù)是0，十位上的數(shù)字的次數(shù)是1，.，依次遞增，而十分位的數(shù)字的次數(shù)是-1，百分位上數(shù)字的次數(shù)是-2，.，依次遞減。注意：不是任何一個十進制小數(shù)都能轉(zhuǎn)換成有

13、限位的二進制數(shù)。進制轉(zhuǎn)換進制轉(zhuǎn)換1二進制與十進制間的相互轉(zhuǎn)換：（1）二進制轉(zhuǎn)十進制方法：“按權展開求和”例：（1011.01）2 （123022121120021122）10（802100.25）10（11.25）10規(guī)律：個位上的數(shù)字的次數(shù)是0，十位上的數(shù)字的次數(shù)是1，.，依獎遞增，而十分位的數(shù)字的次數(shù)是-1，百分位上數(shù)字的次數(shù)是-2，.，依次遞減。注意：不是任何一個十進制小數(shù)都能轉(zhuǎn)換成有限位的二進制數(shù)。進制轉(zhuǎn)換以下二進制數(shù)與十進制數(shù)23.456最接近的是（）A 10111.0101 B 11011.1111C 11011.0111 D 10111.0111E.10111.1111D把下面的

14、數(shù)轉(zhuǎn)換為10進制數(shù)再進行比較位運算位運算主要有：按位與( & )，按位或( | )，按位異或( )，取反運算法則：1、先將兩邊的數(shù)轉(zhuǎn)化為二進制，右邊第一位對齊，對于每一位進行按位運算。2、只有1&1為真，其余情況為假3、只有0|0為假，其余為真4、只有10和01為真，其余為假5、優(yōu)先級& |6、(00001001)2=(11110110)2切記：25不是25而是2異或5位運算補充：負數(shù)在計算機內(nèi)的表示是取對應正數(shù)的補碼。補碼 = 反碼 + 1如1表示為(0001)2，那么-1就表示為：(1111)2。10表示為(1010)2，那么-10就表示為(0110)2。位運算比如

15、，計算212先轉(zhuǎn)換為二進制21 = (10101)22 = (10)2101011010111(10111)2=23位運算練習題：23|25的值是多少？2323|25 = 23|7 = 23這個內(nèi)容比較重要，至少會占1分，請大家務必學透！邏輯真真假假很容易判斷的，總之復賽前要看一下！需要結合C語言的邏輯判斷！設A = true，B = false，C = false，D = true，以下邏輯運算表達式值為真的有（ ）。A. (AB)(CD)B. (AB)C)DC. A(BC)D)D. (A(BC) DE. (AB)(CD)CDE邏輯A. ! (a!=0) | (b!=0) | (c!=0)B

16、. ! (a!=0) & (b!=0) & (c!=0)C. ! (a=0) & (b=0) | (c=0)D.(a=0) & (b=0) & (c=0)E. ! (a=0) | (b=0) | (c=0)6在 C語言中，判斷整數(shù)a 等于 0 或b等于 0或c等于0 的正確的條件表達式是（ ）BA. PQC. (PQ)B. PQD. (QP )需要注意優(yōu)先級邏輯12. 命題“PQ”可讀做P蘊含Q， 其中P、Q是兩個獨立的命題. 只有當命題P成立而命題Q不成立時， 命題PQ的值為false， 其它情況均為true. 與命題PQ等價的邏輯關系式是（ ）。AD

17、PQp=truep=falseq=truetruetrueq=falsefalsetruePQp=truep=falseq=truetruefalseq=falsefalsefalse(QP)p=truep=falseq=truetruetrueq=falsefalsetruePQp=truep=falseq=truetruetrueq=falsefalsetrue邏輯集合論集合我們剛剛學過，但是我們學的東西還是少了點。另外，注意信息學競賽中的一些符號和數(shù)學書上略有不同。需要學會的運算：交集，并集，補集，差集集合論集合我們剛剛學過，但是我們學的東西還是少了點。另外，注意信息學競賽中的一些符號和

18、數(shù)學書上略有不同。需要學會的運算：交集，并集，補集，差集建議學會 “鴿巢原理”差集符號： (就是減號)A B 就相當于去掉A中(AB)的元素。集合論A. c, e B. d, e C. eD. c, d, e E. d, f設全集I = a, b, c, d, e, f, g, h，集合BA = a, b, c, d, e, f， CA= c, d, e，B A= a, d，那么集合CBA為（ ）。A集合論設全集I = a, b, c, d, e, f, g，集合A = a,b, c，B = b, d, e，C = e, f, g，那么集A. a, b, c, d B. a, b, d, e

19、C. b, d, eD. b, c, d, e E. d, f, g合(A B)(CB)為（ ）。A儲存單位的計算bit 位Byte 比特，字節(jié) KB 千字節(jié)MB，兆字節(jié)其它單位：GB TB速率單位（聲音，視頻，網(wǎng)絡）：bps bit per second bit/sKbps Kbit per second Kbit/sMbps Mbit per second Mbit/s儲存單位的計算1 Byte = 8 bit1 KB = 1024 Byte1 MB = 1024 KB = 10242Byte = 8*10243 bit1 GB = 1024 MB = 10242 KB = 10243 B

20、yte=.自己去推了1Mbps = 1024 Kbps = 10242bpsAttention，大B小b有區(qū)別的，一個是bit，一個是Byte，所以KB和Kb是不一樣的，比如說“ADSL寬帶512Kb”當然，現(xiàn)在很多人都混著用了但是考試還是要嚴格點。儲存單位的計算聲音文件的大小等于：速率*長度（注意單位）下載時間與網(wǎng)絡速度的關系：下載時間 = 文件大小 / 下載速率注意下載速率的基本單位是bit/s，而文件大小的單位是Byte，所以要乘以8。公式不用死記，用物理的量綱理論就可以了。由單位確定公式。(bit/s) * (s) = bit下載速率*時間 = 文件大小儲存單位的計算例題：一個音樂愛好

21、者收藏有100首MP3格式的音樂，這些音樂的編碼率都是192Kbps，平均每首音樂的時長為3min，他要通過網(wǎng)絡將這些音樂傳送給另一個人，假設網(wǎng)絡速度恒定為512KB/s，則他傳送這些音樂大概需要（ ）。A. 72s B. 843s C. 112.5min D.3h48min16s E. 超過24小時100 * 192Kb/s * 3min / (512KB/s) = 843.75s切記要換算單位！儲存單位的計算A. 1 B. 10 C. 100 D. 1000 E. 10000Hint：真彩色通常指每像素32位的圖形10. 一位藝術史學家有20000 幅1024 *768 的真彩色圖像，如果

22、將這些圖像以位圖形式保存在CD 光盤上（一張CD 光盤的容量按600M計算），大約需要（ ）張CD光盤。1024*768*20000*32bit/600MB = 100C棧和隊列類比火車站。一個是這樣的另一個是這樣的棧和隊列某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出,出”。假設車輛入站的 順序為 1，2，3，則車輛出站的順序為（ ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2 E. 1, 4

23、, 3, 7, 5Clog n !2排序n個數(shù)排序，最少需要比較多少次？for(i=1; i=n; i+)for(j=1; j aj+1) /這就是比較.公式：最少比較次數(shù) =A. 6B. 7C. 8D. 9E. 1010將 5 個數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。B排序思考:最壞情況下最少需要交換多少次?n-11. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換_次。5排序穩(wěn)定排序包括：插入排序、冒泡排序不穩(wěn)定排序包括：選擇排序、希爾排序、快速排序、堆排序時

24、間復雜度：冒泡排序O(n2)，選擇排序O(n2)，快速排序O(nlog2n)，堆排序O(nlog2n)二叉樹定義：n個結點的有限集，每個結點至多只有兩棵子樹，子樹也是二叉樹。每個結點可以有左孩子和右孩子，順序不可顛倒。概念：度：某個結點孩子的個數(shù)葉子：度為0的結點深度：二叉樹的層數(shù)滿二叉樹：深度為n且結點數(shù)為2n-1的二叉樹完全二叉樹：深度為k，1k-1層為滿二叉樹，第k層葉子節(jié)點集中在左邊的二叉樹二叉樹二叉樹的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹的形態(tài)以及另一種遍歷。二叉樹知識點補充n個結點所組成的不同形態(tài)的二叉

25、樹數(shù)目為：C(2n,n)/(n+1)二叉樹A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 1二叉樹T，已知其前序遍歷序列為1 2 4 35 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（ ）。BA. 4 2 6 5 1 7 3C. 4 2 3 1 5 4 7B. 4 2 5 6 1 3 7D. 4 2 5 6 1 7 3二叉樹已知7個節(jié)點的二叉樹的先根遍歷是1 2 45 6 3 7(數(shù)字為結點的編號，以下同)， 后根遍歷是4 6 5 2 7 3 1， 則該二

26、叉樹的可能的中根遍歷是（ ）只知道前根遍歷和后根遍歷是無法確定一棵二叉樹的，所以這題采用反推驗證ABDA. 2 * NB. 2 * N - 1二叉樹4. 完全二叉樹的結點個數(shù)為4 * N + 3，則它的葉結點個數(shù)為（ ）。C. 2 * N + 1 D. 2 * N - 2E. 2 * N + 2E4n+3=24n+3=2* *2(n+1)2(n+1) - - 1 1，熟悉的公式，熟悉的公式2 2* *葉子結點數(shù)葉子結點數(shù)-1 -1，這不是滿二叉樹的結點數(shù)，這不是滿二叉樹的結點數(shù)嗎嗎？A. 10 B. 11C. 12 D. 13E. 210 1二叉樹8高度為 n 的均衡的二叉樹是指：如果去掉葉結

27、點及相應的樹枝，它應該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為 0，如果某個均衡的二叉樹共有 2381 個結點，則該樹的樹高為（ ）。B2112381212二叉樹5. 一個高度為h 的二叉樹最小元素數(shù)目是（C） 2h-1A） 2h+1D） 2hB） hE） 2h-1）。此時二叉樹退化成一條鏈B圖圖是由頂點和邊所組成的數(shù)據(jù)結構。分為有向圖和無向圖。帶權圖：權的含義，不加權的圖也可以認為所帶權圖：權的含義，不加權的圖也可以認為所有邊上的權都是有邊上的權都是1 1。階和度：一個圖的階是指圖中頂點的個數(shù)階和度：一個圖的階是指圖中頂點的個數(shù)如果頂點如果頂點A A和和

28、B B之間有一條邊相連，則稱之間有一條邊相連，則稱A A和和B B是是關聯(lián)的關聯(lián)的頂點的度：與該頂點相關聯(lián)的邊的數(shù)目，有奇點、頂點的度：與該頂點相關聯(lián)的邊的數(shù)目，有奇點、偶點之分偶點之分對于有向圖：有入度和出度之分對于有向圖：有入度和出度之分圖大家記住定義，然后就見招拆招了。圖論的題目考得比較少，而且大家知道定義，運用各種方法應該不難得到答案。下面就簡單地講一下幾道出現(xiàn)過的題目。圖假設我們用d=(a1,a2,.,a5),表示無向圖G的5個頂點的度數(shù)，下面給出的哪（些）組d 值合理（ ）。A）5，4，4，3，1B）4，2，2，1，1C）3，3，3，2，2D）5，4，3，2，1E）2，2，2，2，

29、2BE圖9. 歐拉圖G是指可以構成一個閉回路的圖，且圖G的每一條邊恰好在這個閉回路上出現(xiàn)一次（即一筆畫成）。在以下各個描述中, 不一定是歐拉圖的是：（ ）。A. 圖G中沒有度為奇數(shù)的頂點B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑)C. 包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑)D. 存在一條回路, 通過每個頂點恰好一次E. 本身為閉跡的圖D 解釋：閉跡，一條路徑，起點和終點是一個點圖A.8 B.7+ 5 C.9 D.6+ 5 E.4+2 2+ 55. 平面上有五個點A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以這五點

30、作為完全圖G 的頂點，每兩點之間的直線距離是圖G 中對應邊的權值。圖G 的最小生成樹中的所有邊的權值和為（ ）講解：最小生成樹算法D圖1. 無向圖G有16條邊，有3個4度頂點、4個3度頂點，其余頂點的度均小于3，則G至少_個頂點。11排列組合前置知識：乘法原理，加法原理，排列組合公式C(n,r)，A(n,r)的計算方法以及基本定理和推論。排列組合公式：1、不可重復的n個元素取r個的排列數(shù)為：A(n,r)2、可重復的n個元素取r個的排列數(shù)為：nr3、不可重復的n個元素取r個的組合數(shù)為：C(n,r)4、可重復的n個元素取r個的組合數(shù)為：C(n+r-1,r)排列組合練習：1.有五個不同顏色的球，從中

31、依次拿出三個，可能的排列有多少種2.有五種不同顏色的球，從中依次拿出三個，可能的排列有多少種3.有五個不同顏色的球，從中拿出三個，可能的組合有多少種4.有五種不同顏色的球，從中拿出三個，可能的組合有多少種排列組合A. 40320 B. 39600 C. 840 D. 780E. 60由3個a，5個b和2個c構成的所有字符串中，包含子串“abc”的共有（ ）個。C(8,1)C(8,1) * * C(7,2)C(7,2) * *C(5,4)C(5,4) * * C(1,1)C(1,1) - - C(6,2)C(6,2) * * C(4,1)C(4,1) * *C(3,3)C(3,3)取出取出 出出

32、abcabc，變成，變成2 2個個a a，4 4個個b b和和1 1個個c c和和abcabc構成字符串的構成字符串的數(shù)目。一共有數(shù)目。一共有 有有2+5+1+1=82+5+1+1=8個位置，任取個位置，任取1 1個給個給abcabc，方，方法數(shù)是法數(shù)是C(8,1)C(8,1)，剩下，剩下7 7個取個取2 2個給個給a a，方法數(shù)，方法數(shù)C(7,2)C(7,2)，剩下，剩下5 5個取個取4 4個放個放b b，以此類推。但是要考慮，以此類推。但是要考慮abcabcabcabc出現(xiàn)兩次重出現(xiàn)兩次重復計算的情況，所以要減去，怎么減大家自己思考一下。復計算的情況，所以要減去，怎么減大家自己思考一下。D

33、排列組合練習字符串success重新排列，包括其本身，共可以組成多少個不同的字符串？C(7,2)*C(5,2)*A(3,3) = 1260問題求解75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有_名兒童沒有玩過其中任何一種。集合類問題，通常可以運用數(shù)學方法解決10已知a, b, c, d, e, f, g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們

34、的座位安排在圓桌旁，使得每個人都能與他身邊的人交談？如果可以，請以“a b”開頭寫出你的安排方案：_。abdfgc英英漢漢意意俄俄日日德德法法aObOOcOOOdOOeOOfOOOgOO2. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1 根或2 根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當N 分別為100，200，300，400，500時，先取者有無必勝策略的標記順序為（回答應為一個由0 或1 組成的字符串）。11011，簡單的博弈論，小學奧數(shù)題（取石子游戲） 現(xiàn)有 5 堆石子,石子數(shù)依次為 3，5，7，

35、19，50，甲乙兩人輪流從任一堆中任取（每次只能取自一堆，不能不?。? 取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論 乙怎樣取，甲只要不失誤，都能獲勝）？T=3571950=32T=3571950=32，取掉，取掉3232后后T=0T=0，面對，面對T=0T=0的狀態(tài)時，先取者必敗的狀態(tài)時，先取者必敗普及組的題目。第一次在第五堆里面取第一次在第五堆里面取3232枚石子。枚石子。1將 2006 個人分成若干不相交的子集，每個子集至少有 3 個人，并且：（1）在每個子集中，沒有人認識該子集的所有人。（2）同一子集的任何 3 個人中，至少有 2 個人互不認識。（3）對同一子集中任何

36、2 個不相識的人，在該子集中恰好只有 1 個人認識這兩個人。 則滿足上述條件的子集最多能有_個？401，主要方法是根據(jù)(1)，(2)，(3)進行假設，發(fā)現(xiàn)至少需要5個人才能同時滿足(1)，(2)，(3)，于是2006/5，一個6人，其余5人2將邊長為 n 的正三角形每邊 n 等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形， 我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最 下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同 一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上（圖中是 n=5

37、 時一條通路的例 子）。設 n=10，則該正三角形的不同的通路的總數(shù)為_。362880嚴格證明挺復雜，找規(guī)律可以知道總數(shù)為(n-1)!1給定n個有標號的球，標號依次為1，2，n。將這n個球放入r個相同的盒子里，不允許有空盒，其不同放置方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的放置方法依次為(1) , (234) , (2) ,(134) , (3) , (124) , (4) , (123) , (12) ,(34) , (13) , (24) , (14) , (23)。當n=7，r=4時，S(7,4)=_。289S(n,r)=S(n-1,r-1)+r*S(n-1,r)

38、邊界條件自己找。難題，遞推類問題下面介紹一個簡單的遞推問題，好讓大家初步認識遞推。小明上樓，一步可以上一級，也可以上兩級，請問上n級有多少種上法？例如，上2級可以有1+1，也可以一次上2級。上3級可以是1+1+1，2+1,1+2三種。設f(n)表示上n級需要的步數(shù)，顯然只能夠從n-1級或n-2級上到第n級，所以方法總數(shù)適用加法原理，f(n)=f(n-1)+f(n-2)，斐波那契數(shù)列！其中f(1)=1，f(2)=2，后面的都可以根據(jù)這兩個初始條件推出來2N個人在操場里圍成一圈，將這N個人按順時針方向從1到N編號，然后從第一個人起，每隔一個人讓下一個人離開操場，顯然，第一輪過后，具有偶數(shù)編號的人都

39、離開了操場。依次做下去，直到操場只剩下一個人，記這個人的編號為J(N)，例如，J(5)=3，J(10)=5，等等。則J(400)= _。（提示：對J(N)=2m+r進行分析，其中0r2m）。289，找規(guī)律，數(shù)學好的智商分數(shù)的比較占優(yōu)勢N12345678910 11 12 13 14 15 16 17J(n)11313571357911 13 1513m20212122222222232323232323232324242r001012301234567012r+111313571357911 13 1513非常容易看出：J(N)=J(2m+r)=2r+1J(400)=J(28+144)=2*1

40、44+1=289問題求解總結1、要耐心地尋找規(guī)律2、要冷靜的分析問題3、不到萬不得已決不輕言放棄4、不懂就蒙一個！閱讀程序1、認真計算2、耐心分析3、分析不下去就函數(shù)（語句作用）4、千萬記得第一個閱讀程序要檢查5、多多練習，熟能生巧6、列出變量變化表程序填空這種題與編程經(jīng)驗和算法學習的程度有關，拿得一分是一分。不過對于編程經(jīng)驗不足和算法練習少的人來說也不是沒分可拿。比如說程序填空總結1、分析語句是干什么的，回到開頭講的內(nèi)容：初始化 一些明顯的動作：a.結果沒有儲存在需要的地方。b.累加器沒有做加法c.輸出 關鍵動作。2、不懂就根據(jù)上下文猜3、不寫白不寫，蒙一下總是好的。4、千萬注意開頭和結尾，

41、常常有送分題目！幾個小問題A. 在1977年前后形成標準的計算機高級語言FORTRAN77禁止在程序使用遞歸， 原因之一是該方法可能會占用更多的內(nèi)存空間.B. 和非遞歸算法相比， 解決同一個問題，遞歸算法一般運行得更快一些C. 對于較復雜的問題， 用遞歸方式編程往往比非遞歸方式更容易一些D. 對于已定義好的標準數(shù)學函數(shù)sin(x)， 應用程序中的語句“y=sin(sin(x);”就是一種遞歸調(diào)用20. 近20年來， 許多計算機專家都大力推崇遞歸算法，認為它是解決較復雜問題的強有力的工具. 在下列關于遞歸的說法中， 正確的是（ ）。ACA. gcc/g+C. Turbo CB. Turbo PascalD. free pascal16.在下列各軟件中，屬于 NOI