NOIP初賽知識(shí)點(diǎn)復(fù)習(xí)總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、，計(jì)算212先轉(zhuǎn)換為二進(jìn)制21 = (10101)22 = (10)2101011010111(10111)2=23位運(yùn)算練習(xí)題：23|25的值是多少？2323|25 = 23|7 = 23這個(gè)內(nèi)容比較重要，至少會(huì)占1分，請(qǐng)大家務(wù)必學(xué)透！邏輯真真假假很容易判斷的，總之復(fù)賽前要看一下！需要結(jié)合C語言的邏輯判斷！設(shè)A = true，B = false，C = false，D = true，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。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 的正確的條件表達(dá)式是（ ）BA. PQC. (PQ)B. PQD. (QP )需要注意優(yōu)先級(jí)邏輯12. 命題“PQ”可讀做P蘊(yùn)含Q， 其中P、Q是兩個(gè)獨(dú)立的命題. 只有當(dāng)命題P成立而命題Q不成立時(shí)， 命題PQ的值為false， 其它情況均為true. 與命題PQ等價(jià)的邏輯關(guān)系式是（ ）。AD

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

18、數(shù)學(xué)書上略有不同。需要學(xué)會(huì)的運(yùn)算：交集，并集，補(bǔ)集，差集建議學(xué)會(huì) “鴿巢原理”差集符號(hào)： (就是減號(hào))A B 就相當(dāng)于去掉A中(AB)的元素。集合論A. c, e B. d, e C. eD. c, d, e E. d, f設(shè)全集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集合論設(shè)全集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儲(chǔ)存單位的計(jì)算bit 位Byte 比特，字節(jié) KB 千字節(jié)MB，兆字節(jié)其它單位：GB TB速率單位（聲音，視頻，網(wǎng)絡(luò)）：bps bit per second bit/sKbps Kbit per second Kbit/sMbps Mbit per second Mbit/s儲(chǔ)存單位的計(jì)算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ū)別的，一個(gè)是bit，一個(gè)是Byte，所以KB和Kb是不一樣的，比如說“ADSL寬帶512Kb”當(dāng)然，現(xiàn)在很多人都混著用了但是考試還是要嚴(yán)格點(diǎn)。儲(chǔ)存單位的計(jì)算聲音文件的大小等于：速率*長度（注意單位）下載時(shí)間與網(wǎng)絡(luò)速度的關(guān)系：下載時(shí)間 = 文件大小 / 下載速率注意下載速率的基本單位是bit/s，而文件大小的單位是Byte，所以要乘以8。公式不用死記，用物理的量綱理論就可以了。由單位確定公式。(bit/s) * (s) = bit下載速率*時(shí)間 = 文件大小儲(chǔ)存單位的計(jì)算例題：一個(gè)音樂愛好

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

22、將這些圖像以位圖形式保存在CD 光盤上（一張CD 光盤的容量按600M計(jì)算），大約需要（ ）張CD光盤。1024*768*20000*32bit/600MB = 100C棧和隊(duì)列類比火車站。一個(gè)是這樣的另一個(gè)是這樣的棧和隊(duì)列某個(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)?1，2，3，則車輛出站的順序?yàn)椋?）。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個(gè)數(shù)排序，最少需要比較多少次？for(i=1; i=n; i+)for(j=1; j aj+1) /這就是比較.公式：最少比較次數(shù) =A. 6B. 7C. 8D. 9E. 1010將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。B排序思考:最壞情況下最少需要交換多少次?n-11. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換_次。5排序穩(wěn)定排序包括：插入排序、冒泡排序不穩(wěn)定排序包括：選擇排序、希爾排序、快速排序、堆排序時(shí)

24、間復(fù)雜度：冒泡排序O(n2)，選擇排序O(n2)，快速排序O(nlog2n)，堆排序O(nlog2n)二叉樹定義：n個(gè)結(jié)點(diǎn)的有限集，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，子樹也是二叉樹。每個(gè)結(jié)點(diǎn)可以有左孩子和右孩子，順序不可顛倒。概念：度：某個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)葉子：度為0的結(jié)點(diǎn)深度：二叉樹的層數(shù)滿二叉樹：深度為n且結(jié)點(diǎn)數(shù)為2n-1的二叉樹完全二叉樹：深度為k，1k-1層為滿二叉樹，第k層葉子節(jié)點(diǎn)集中在左邊的二叉樹二叉樹二叉樹的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹的形態(tài)以及另一種遍歷。二叉樹知識(shí)點(diǎn)補(bǔ)充n個(gè)結(jié)點(diǎ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個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1 2 45 6 3 7(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)， 后根遍歷是4 6 5 2 7 3 1， 則該二

26、叉樹的可能的中根遍歷是（ ）只知道前根遍歷和后根遍歷是無法確定一棵二叉樹的，所以這題采用反推驗(yàn)證ABDA. 2 * NB. 2 * N - 1二叉樹4. 完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(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* *葉子結(jié)點(diǎn)數(shù)葉子結(jié)點(diǎn)數(shù)-1 -1，這不是滿二叉樹的結(jié)點(diǎn)數(shù)，這不是滿二叉樹的結(jié)點(diǎn)數(shù)嗎嗎？A. 10 B. 11C. 12 D. 13E. 210 1二叉樹8高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)

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

28、B B之間有一條邊相連，則稱之間有一條邊相連，則稱A A和和B B是是關(guān)聯(lián)的關(guān)聯(lián)的頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，有奇點(diǎn)、頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，有奇點(diǎn)、偶點(diǎn)之分偶點(diǎn)之分對(duì)于有向圖：有入度和出度之分對(duì)于有向圖：有入度和出度之分圖大家記住定義，然后就見招拆招了。圖論的題目考得比較少，而且大家知道定義，運(yùn)用各種方法應(yīng)該不難得到答案。下面就簡單地講一下幾道出現(xiàn)過的題目。圖假設(shè)我們用d=(a1,a2,.,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(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òu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫成）。在以下各個(gè)描述中, 不一定是歐拉圖的是：（ ）。A. 圖G中沒有度為奇數(shù)的頂點(diǎn)B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑)C. 包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑)D. 存在一條回路, 通過每個(gè)頂點(diǎn)恰好一次E. 本身為閉跡的圖D 解釋：閉跡，一條路徑，起點(diǎn)和終點(diǎn)是一個(gè)點(diǎn)圖A.8 B.7+ 5 C.9 D.6+ 5 E.4+2 2+ 55. 平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以這五點(diǎn)

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

31、依次拿出三個(gè)，可能的排列有多少種2.有五種不同顏色的球，從中依次拿出三個(gè)，可能的排列有多少種3.有五個(gè)不同顏色的球，從中拿出三個(gè)，可能的組合有多少種4.有五種不同顏色的球，從中拿出三個(gè)，可能的組合有多少種排列組合A. 40320 B. 39600 C. 840 D. 780E. 60由3個(gè)a，5個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（ ）個(gè)。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個(gè)個(gè)a a，4 4個(gè)個(gè)b b和和1 1個(gè)個(gè)c c和和abcabc構(gòu)成字符串的構(gòu)成字符串的數(shù)目。一共有數(shù)目。一共有 有有2+5+1+1=82+5+1+1=8個(gè)位置，任取個(gè)位置，任取1 1個(gè)給個(gè)給abcabc，方，方法數(shù)是法數(shù)是C(8,1)C(8,1)，剩下，剩下7 7個(gè)取個(gè)取2 2個(gè)給個(gè)給a a，方法數(shù)，方法數(shù)C(7,2)C(7,2)，剩下，剩下5 5個(gè)取個(gè)取4 4個(gè)放個(gè)放b b，以此類推。但是要考慮，以此類推。但是要考慮abcabcabcabc出現(xiàn)兩次重出現(xiàn)兩次重復(fù)計(jì)算的情況，所以要減去，怎么減大家自己思考一下。復(fù)計(jì)算的情況，所以要減去，怎么減大家自己思考一下。D

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

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

35、19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。? 取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論 乙怎樣取，甲只要不失誤，都能獲勝）？T=3571950=32T=3571950=32，取掉，取掉3232后后T=0T=0，面對(duì)，面對(duì)T=0T=0的狀態(tài)時(shí)，先取者必?cái)〉臓顟B(tài)時(shí)，先取者必?cái)∑占敖M的題目。第一次在第五堆里面取第一次在第五堆里面取3232枚石子。枚石子。1將 2006 個(gè)人分成若干不相交的子集，每個(gè)子集至少有 3 個(gè)人，并且：（1）在每個(gè)子集中，沒有人認(rèn)識(shí)該子集的所有人。（2）同一子集的任何 3 個(gè)人中，至少有 2 個(gè)人互不認(rèn)識(shí)。（3）對(duì)同一子集中任何

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

37、 時(shí)一條通路的例 子）。設(shè) n=10，則該正三角形的不同的通路的總數(shù)為_。362880嚴(yán)格證明挺復(fù)雜，找規(guī)律可以知道總數(shù)為(n-1)!1給定n個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為1，2，n。將這n個(gè)球放入r個(gè)相同的盒子里，不允許有空盒，其不同放置方法的總數(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=7，r=4時(shí)，S(7,4)=_。289S(n,r)=S(n-1,r-1)+r*S(n-1,r)

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

39、離開了操場。依次做下去，直到操場只剩下一個(gè)人，記這個(gè)人的編號(hào)為J(N)，例如，J(5)=3，J(10)=5，等等。則J(400)= _。（提示：對(duì)J(N)=2m+r進(jìn)行分析，其中0r2m）。289，找規(guī)律，數(shù)學(xué)好的智商分?jǐn)?shù)的比較占優(yōu)勢(shì)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問題求解總結(jié)1、要耐心地尋找規(guī)律2、要冷靜的分析問題3、不到萬不得已決不輕言放棄4、不懂就蒙一個(gè)！閱讀程序1、認(rèn)真計(jì)算2、耐心分析3、分析不下去就函數(shù)（語句作用）4、千萬記得第一個(gè)閱讀程序要檢查5、多多練習(xí)，熟能生巧6、列出變量變化表程序填空這種題與編程經(jīng)驗(yàn)和算法學(xué)習(xí)的程度有關(guān)，拿得一分是一分。不過對(duì)于編程經(jīng)驗(yàn)不足和算法練習(xí)少的人來說也不是沒分可拿。比如說程序填空總結(jié)1、分析語句是干什么的，回到開頭講的內(nèi)容：初始化 一些明顯的動(dòng)作：a.結(jié)果沒有儲(chǔ)存在需要的地方。b.累加器沒有做加法c.輸出 關(guān)鍵動(dòng)作。2、不懂就根據(jù)上下文猜3、不寫白不寫，蒙一下總是好的。4、千萬注意開頭和結(jié)尾，

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