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

初賽試題形式

●初賽：初賽全部為筆試，滿分100分。試題由四部分組成：

1、選擇題：共20題，每題1.5分，共計(jì)30分。提高組每題有5個(gè)備選答案，前10個(gè)題為單選題(即每題有且只有一個(gè)正確答案，選對(duì)得分)，后10題為不定項(xiàng)選擇題(即每題有1至5個(gè)正確答案，只有全部選對(duì)才得分)。普及組4個(gè)備選答案，全為單選題。

2、問題求解題：共2題，每題5分，共計(jì)10分。試題給出一個(gè)敘述較為簡單的問題，要求學(xué)生對(duì)問題進(jìn)行分析，找到一個(gè)合適的算法，并推算出問題的解?？忌o出的答案與標(biāo)準(zhǔn)答案相同，則得分：否則不得分。

3、程序閱讀理解題：共4題，每題8分，共計(jì)32分。題目給出一段程序(不一定有關(guān)于程序功能的說明)，考生通過閱讀理解該段程序給出程序的輸出。輸出與標(biāo)準(zhǔn)答案一致，則得分；否則不得分。

4、程序完善題：共2題，每題14分，共計(jì)28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個(gè)語句或語句的一部分并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對(duì)則得分；否則不得分。

大家好知識(shí)范圍內(nèi)容與要求

1、計(jì)算機(jī)的基本常識(shí)●計(jì)算機(jī)和信息社會(huì)(信息社會(huì)的主要特征、計(jì)算機(jī)的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化)●信息輸入輸出基本原理(信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式)●信息的表示與處理(信息編碼、微處理部件MPU、內(nèi)存儲(chǔ)結(jié)構(gòu)、指令，程序，和存儲(chǔ)程序原理、程序的三種基本控制結(jié)構(gòu))●信息的存儲(chǔ)、組織與管理(存儲(chǔ)介質(zhì)、存儲(chǔ)器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理)●信息系統(tǒng)組成及互連網(wǎng)的基本知識(shí)(計(jì)算機(jī)構(gòu)成原理、槽和端口的部件間可擴(kuò)展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP／IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點(diǎn))●人機(jī)交互界面的基本概念(窗口系統(tǒng)、人和計(jì)算機(jī)交流信息的途徑(文本及交互操作))●信息技術(shù)的新發(fā)展、新特點(diǎn)、新應(yīng)用等。大家好2、計(jì)算機(jī)的基本操作●WINDOWS和LINUX的基本操作知識(shí)●聯(lián)網(wǎng)的基本使用常識(shí)(網(wǎng)上瀏覽、搜索和查詢等)●常用的工具軟件使用(文字編輯、電子郵件收發(fā)等)3、程序設(shè)計(jì)的基本知識(shí)數(shù)據(jù)結(jié)構(gòu)●程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點(diǎn))●浮點(diǎn)運(yùn)算中的精度和數(shù)值比較●一維數(shù)組(串)與線性表●記錄類型(PASCAL)／結(jié)構(gòu)類型(C)

程序設(shè)計(jì)●結(jié)構(gòu)化程序設(shè)計(jì)的基本概念●閱讀理解程序的基本能力●具有將簡單問題抽象成適合計(jì)算機(jī)解決的模型的基本能力●具有針對(duì)模型設(shè)計(jì)簡單算法的基本能力●程序流程描述(自然語言／偽碼／NS圖／其他)●程序設(shè)計(jì)語言(PASCAL／C／C++，)

基本算法處理●初等算法(計(jì)數(shù)、統(tǒng)計(jì)、數(shù)學(xué)運(yùn)算等)●排序算法(冒泡法、插入排序、合并排序、快速排序)●查找(順序查找、二分法)●回溯算法大家好課程大綱NOIP初賽情況的簡單分析基礎(chǔ)知識(shí)二叉樹圖排列組合程序閱讀題程序填空題總結(jié)4大家好初賽試卷題型分析(提高組)單項(xiàng)選擇

15分(提高組)不定項(xiàng)選擇

15分（多選少選均不得分）問題求解

10分閱讀程序

32分完善程序

28分5大家好初賽試卷題型分析初賽考的知識(shí)點(diǎn)，大綱說：計(jì)算機(jī)基本常識(shí)，基本操作和程序設(shè)計(jì)基本知識(shí)。選擇題考查的是知識(shí)，而問題解決題、填空更加重視能力的考查。一般說來，選擇題是不需要單獨(dú)準(zhǔn)備的

，也無從準(zhǔn)備。只要多用心積累就可以了。到是問題解決題目比較固定，大家應(yīng)當(dāng)多做以前的題目。寫運(yùn)行結(jié)果需要多做題目，培養(yǎng)良好的程序閱讀和分析能力，而完善程序最好總結(jié)一下以前題目常常要你填出來的語句類型。6大家好初賽試卷題型分析1.選擇題

一般它們是比較容易得分的，一共30分，不可錯(cuò)過！

近幾年來，初賽的考查范圍有了很大的變化，越來越緊跟潮流，需要大家有比較廣泛的知識(shí)，包括計(jì)算機(jī)硬件，軟件，網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)（例如棧，隊(duì)列，排序算法），程序設(shè)計(jì)語言以及一些基本的數(shù)學(xué)知識(shí)和技巧（例如排列組合等）。2.填空、問題解決

這部分題目對(duì)數(shù)學(xué)要求要高一點(diǎn)，往往考查的是代數(shù)變形、集合論、數(shù)列（一般是考遞推），也考查

一些算法和數(shù)據(jù)結(jié)構(gòu)知識(shí)。建議大家多花一點(diǎn)時(shí)間做，盡量做對(duì)。7大家好初賽試卷題型分析3.

閱讀程序?qū)懗鲞\(yùn)行結(jié)果占的分?jǐn)?shù)多，但得分率卻不高，較易失分，一旦結(jié)果不正確，將丟失全分。這種題型主要考察選手：①

程序設(shè)計(jì)語言的掌握能力②

數(shù)學(xué)運(yùn)算能力

③

耐心、細(xì)心的心理品質(zhì)一般做這類題目的關(guān)鍵在于能夠分析程序的結(jié)構(gòu)及程序段的功能，找出程序目的，即這個(gè)程序想干什么。8大家好初賽試卷題型分析完成這類題目的一般方法和步驟是：①

從頭到尾通讀程序，大致掌握程序的算法；②

通過給程序分段，清理程序的結(jié)構(gòu)和層次，達(dá)到讀懂程序的目的；

③

閱讀程序中特別注意跟蹤主要變量值的變化，也可以用列表的方法，了解變量變化和程序運(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é)往往做得慢的多，而且容易失誤。9大家好初賽試卷題型分析4.完善程序這部分題目得分率似乎不高。盡量把一些簡單的填好就行了。建議大家把以前的初賽題目都做一下。常常讓大家填的是：①初始化

②一些明顯的動(dòng)作：

a.結(jié)果沒有儲(chǔ)存在需要的地方。

b.累加器沒有做加法

c.輸出

③關(guān)鍵動(dòng)作。

在算法描述中出現(xiàn)的比較關(guān)鍵的步驟。例如交換排序程序的“交換”操作等很明顯需要完成的操作。分析方法和寫運(yùn)行結(jié)果類似，注意分析變量和程序結(jié)構(gòu)，理解變量和模塊的作用是解題的關(guān)鍵。10大家好進(jìn)制轉(zhuǎn)換1．二進(jìn)制與十進(jìn)制間的相互轉(zhuǎn)換：（1）二進(jìn)制轉(zhuǎn)十進(jìn)制方法：“按權(quán)展開求和”例：（1011.01）2

＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10＝（8＋0＋2＋1＋0＋0.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)換成有限位的二進(jìn)制數(shù)。11大家好進(jìn)制轉(zhuǎn)換12大家好進(jìn)制轉(zhuǎn)換1．二進(jìn)制與十進(jìn)制間的相互轉(zhuǎn)換：（1）二進(jìn)制轉(zhuǎn)十進(jìn)制方法：“按權(quán)展開求和”例：（1011.01）2

＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10＝（8＋0＋2＋1＋0＋0.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ù)。13大家好進(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把下面的數(shù)轉(zhuǎn)換為10進(jìn)制數(shù)再進(jìn)行比較14大家好位運(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、只有1^0和0^1為真，其余為假5、優(yōu)先級(jí)~>&

>

^

>

|6、~(00001001)2=(11110110)2

切記：2^5不是25而是2異或515大家好位運(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。16大家好位運(yùn)算比如，計(jì)算21^2先轉(zhuǎn)換為二進(jìn)制21

=

(10101)22

=

(10)2

10101^10

10111(10111)2=2317大家好位運(yùn)算練習(xí)題：23|2^5的值是多少？2323|2^5

=

23|7

=

23這個(gè)內(nèi)容比較重要，至少會(huì)占1分，請(qǐng)大家務(wù)必學(xué)透！18大家好邏輯真真假假很容易判斷的，總之復(fù)賽前要看一下！需要結(jié)合C語言的邏輯判斷！

設(shè)A

=

true，B

=

false，C

=

false，D

=

true，以下邏輯運(yùn)算表達(dá)式值為真的有（

）。A.

(A∧B)∨(C∧D)B.

((A∧B)∨C)∧DC.

A∧((B∨C)∨D)D.

(A∧(B∨C))

∨DE.

(A∨B)∧(C∨D)CDE19大家好邏輯A.

!

((a!=0)

||

(b!=0)

||

(c!=0))B.

!

((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á)式是（

）B20大家好A.

﹁

P∨QC.

﹁

(P∨Q)

B.

P∧QD.

﹁(﹁Q∧P

)需要注意優(yōu)先級(jí)邏輯

12.

命題“P→Q”可讀做P蘊(yùn)含Q，

其中

P、Q是兩個(gè)獨(dú)立的命題.

只有當(dāng)命題P成

立而命題Q不成立時(shí)，

命題"P→Q"的值為

false，

其它情況均為true.

與命題"P→Q"

等價(jià)的邏輯關(guān)系式是（）。AD21大家好邏輯22大家好集合論集合我們剛剛學(xué)過，但是我們學(xué)的東西還是少了點(diǎn)。另外，注意信息學(xué)競賽中的一些符號(hào)和數(shù)學(xué)書上略有不同。需要學(xué)會(huì)的運(yùn)算：交集，并集，補(bǔ)集，差集23大家好集合論集合我們剛剛學(xué)過，但是我們學(xué)的東西還是少了點(diǎn)。另外，注意信息學(xué)競賽中的一些符號(hào)和數(shù)學(xué)書上略有不同。需要學(xué)會(huì)的運(yùn)算：交集，并集，補(bǔ)集，差集建議學(xué)會(huì)

“鴿巢原理”差集符號(hào)：－

(就是減號(hào))A

—

B

就相當(dāng)于去掉A中(A∩B)的元素。24大家好集合論A.

{c,

e}

B.

{d,

e}

C.

{e}D.

{c,

d,

e}

E.

{d,

f}設(shè)全集I

=

{a,

b,

c,

d,

e,

f,

g,

h}，集合B∪A

=

{a,

b,

c,

d,

e,

f}，

C∩A=

{c,

d,

e}，~B

∩A=

{a,

d}，那么集合C∩B∩A為（）。A25大家好集合論設(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}

C.

{b,

d,

e}D.

{b,

c,

d,

e}

E.

{d,

f,

g}合(A

—

B)∪(~C∩B)為（）。A26大家好儲(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/s27大家好儲(chǔ)存單位的計(jì)算1

Byte

=

8

bit1

KB

=

1024

Byte1

MB

=

1024

KB

=

10242Byte

=

8*10243

bit1

GB

=

1024

MB

=

10242

KB

=

10243

Byte=......自己去推了1Mbps

=

1024

Kbps

=

10242bpsAttention，大B小b有區(qū)別的，一個(gè)是bit，一個(gè)是Byte，所以KB和Kb是不一樣的，比如說“ADSL寬帶512Kb”當(dāng)然，現(xiàn)在很多人都混著用了……但是考試還是要嚴(yán)格點(diǎn)。28大家好儲(chǔ)存單位的計(jì)算聲音文件的大小等于：速率*長度（注意單位）下載時(shí)間與網(wǎng)絡(luò)速度的關(guān)系：下載時(shí)間

=

文件大小

/

下載速率注意下載速率的基本單位是bit/s，而文件大小的單位是Byte，所以要乘以8。公式不用死記，用物理的量綱理論就可以了。由單位確定公式。(bit/s)

*

(s)

=

bit下載速率*時(shí)間

=

文件大小29大家好儲(chǔ)存單位的計(jì)算例題：一個(gè)音樂愛好者收藏有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切記要換算單位?。?！30大家好儲(chǔ)存單位的計(jì)算A.

1

B.

10

C.

100

D.

1000

E.

10000Hint：真彩色通常指每像素32位的圖形10.

一位藝術(shù)史學(xué)家有20000

幅1024

*768

的真彩色圖像，如果將這些圖像以位圖形式保存在CD

光盤上（一張CD

光盤的容量按600M計(jì)算），大約需要（

）張CD光盤。1024*768*20000*32bit/600MB

=

100C31大家好棧和隊(duì)列類比火車站。一個(gè)是這樣的——另一個(gè)是這樣的——32大家好棧和隊(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)?/p>

1，2，3，……，則車輛出站的順序?yàn)椋?/p>

）。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,

3,

7,

5C33大家好log

n

!┓┏2排序

n個(gè)數(shù)排序，最少需要比較多少次？

for(i=1;

i<=n;

i++)

for(j=1;

j<=n-i;

j++)

if(a[j]

>

a[j+1])

//這就是比較

....公式：最少比較次數(shù)

=34大家好A.

6B.

7C.

8D.

9E.

1010．將

5

個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的排序。B35大家好排序思考:最壞情況下最少需要交換多少次?n-11.

將數(shù)組{32,

74,

25,

53,

28,

43,

86,

47}中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換_____次。536大家好排序穩(wěn)定排序包括：插入排序、冒泡排序不穩(wěn)定排序包括：選擇排序、希爾排序、快速排序、堆排序時(shí)間復(fù)雜度：冒泡排序O(n2)，選擇排序O(n2)，快速排序O(nlog2n)，堆排序O(nlog2n)37大家好二叉樹定義：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，1~k-1層為滿二叉樹，第k層葉子節(jié)點(diǎn)集中在左邊的二叉樹38大家好二叉樹二叉樹的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹的形態(tài)以及另一種遍歷。39大家好二叉樹知識(shí)點(diǎn)補(bǔ)充n個(gè)結(jié)點(diǎn)所組成的不同形態(tài)的二叉樹數(shù)目為：C(2n,n)/(n+1)40大家好二叉樹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，則其后序遍歷序列為（）。B41大家好A.

4

2

6

5

1

7

3C.

4

2

3

1

5

4

7B.

4

2

5

6

1

3

7

D.

4

2

5

6

1

7

3二叉樹

已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1

2

4

5

6

3

7(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，

后

根遍歷是4

6

5

2

7

3

1，

則該二叉樹的可

能的中根遍歷是（

）只知道前根遍歷和后根遍歷是無法確定一棵二叉樹的，所以這題采用反推驗(yàn)證ABD42大家好A.

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

-

2

E.

2

*

N

+

2E4n+3=2*2(n+1)

-

1，熟悉的公式2*葉子結(jié)點(diǎn)數(shù)-1，這不是滿二叉樹的結(jié)點(diǎn)數(shù)嗎？43大家好A.

10

B.

11C.

12

D.

13E.

210

–

1

二叉樹

8．高度為

n

的均衡的二叉樹是指：如果

去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度

為

n-1

的滿二叉樹。在這里，樹高等于葉

結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為

0，如

果某個(gè)均衡的二叉樹共有

2381

個(gè)結(jié)點(diǎn)，

則該樹的樹高為（）。B211<2381<21244大家好二叉樹

5.

一個(gè)高度為h

的二叉樹最小元素?cái)?shù)目是（C）

2h-1

A）

2h+1D）

2h

B）

hE）

2h-1）。此時(shí)二叉樹退化成一條鏈B45大家好圖

圖是由頂點(diǎn)和邊所組成的數(shù)據(jù)結(jié)構(gòu)。分為

有向圖和無向圖。

帶權(quán)圖：權(quán)的含義，不加權(quán)的圖也可以認(rèn)為所

有邊上的權(quán)都是1。???階和度：一個(gè)圖的階是指圖中頂點(diǎn)的個(gè)數(shù)如果頂點(diǎn)A和B之間有一條邊相連，則稱A和B是關(guān)聯(lián)的頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，有奇點(diǎn)、偶點(diǎn)之分對(duì)于有向圖：有入度和出度之分46大家好圖大家記住定義，然后就見招拆招了。圖論的題目考得比較少，而且大家知道定義，運(yùn)用各種方法應(yīng)該不難得到答案。下面就簡單地講一下幾道出現(xiàn)過的題目。47大家好圖假設(shè)我們用d=(a1,a2,...,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d

值合理（

）。A）{5，4，4，3，1}B）{4，2，2，1，1}C）{3，3，3，2，2}D）{5，4，3，2，1}E）{2，2，2，2，2}BE48大家好圖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)49大家好圖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)作為完全圖G

的頂點(diǎn)，每兩點(diǎn)之間的直線距離是圖G

中對(duì)應(yīng)邊的權(quán)值。圖G

的最小生成樹中的所有邊的權(quán)值和為（

）講解：最小生成樹算法D50大家好圖1.

無向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少_______個(gè)頂點(diǎn)。1151大家好排列組合前置知識(shí)：乘法原理，加法原理，排列組合公式C(n,r)，A(n,r)的計(jì)算方法以及基本定理和推論。52大家好排列組合公式：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)53大家好排列組合練習(xí)：1.有五個(gè)不同顏色的球，從中依次拿出三個(gè)，可能的排列有多少種2.有五種不同顏色的球，從中依次拿出三個(gè)，可能的排列有多少種3.有五個(gè)不同顏色的球，從中拿出三個(gè)，可能的組合有多少種4.有五種不同顏色的球，從中拿出三個(gè)，可能的組合有多少種54大家好排列組合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(7,2)

*C(5,4)

*

C(1,1)

-

C(6,2)

*

C(4,1)

*C(3,3)取出

出abc，變成2個(gè)a，4個(gè)b和1個(gè)c和"abc"構(gòu)成字符串的數(shù)目。一共有

有2+5+1+1=8個(gè)位置，任取1個(gè)給"abc"，方法數(shù)是C(8,1)，剩下7個(gè)取2個(gè)給a，方法數(shù)C(7,2)，剩下5個(gè)取4個(gè)放b，以此類推。但是要考慮abcabc出現(xiàn)兩次重復(fù)計(jì)算的情況，所以要減去，怎么減大家自己思考一下。D55大家好排列組合練習(xí)字符串"success"重新排列，包括其本身，共可以組成多少個(gè)不同的字符串？C(7,2)*C(5,2)*A(3,3)

=

126056大家好問題求解75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂場總共收入700，可知有___名兒童沒有玩過其中任何一種。集合類問題，通?？梢赃\(yùn)用數(shù)學(xué)方法解決1057大家好已知a,

b,

c,

d,

e,

f,

g七個(gè)人中，a會(huì)講英語；b會(huì)講英語和漢語；c會(huì)講英語、意大利語和俄語；d會(huì)講漢語和日語；e會(huì)講意大利語和德語；f會(huì)講俄語、日語和法語；g會(huì)講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請(qǐng)以“a

b”開頭寫出你的安排方案：______。abdfgc58大家好59大家好2.

取火柴游戲的規(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ù)題60大家好

（取石子游戲）

現(xiàn)有

5

堆石子,石子數(shù)依

次為

3，5，7，19，50，甲乙兩人輪流從

任一堆中任?。看沃荒苋∽砸欢?，不能

不取）,

取最后一顆石子的一方獲勝。甲

先取，問甲有沒有獲勝策略（即無論

乙怎

樣取，甲只要不失誤，都能獲勝）？T=3^5^7^19^50=32，取掉32后T=0，面對(duì)T=0的狀態(tài)時(shí)，先取者必?cái)∑占敖M的題目。第一次在第五堆里面取32枚石子。61大家好1．將

2006

個(gè)人分成若干不相交的子集，每個(gè)子集至少有

3

個(gè)人，并且：（1）在每個(gè)子集中，沒有人認(rèn)識(shí)該子集的所有人。（2）同一子集的任何

3

個(gè)人中，至少有

2

個(gè)人互不認(rèn)識(shí)。（3）對(duì)同一子集中任何

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人62大家好2．將邊長為

n

的正三角形每邊

n

等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若干個(gè)正三角形，

我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最

下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同

一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上（圖中是

n=5

時(shí)一條通路的例

子）。設(shè)

n=10，則該正三角形的不同的通路的總數(shù)為_______。362880嚴(yán)格證明挺復(fù)雜，找規(guī)律可以知道總數(shù)為(n-1)!63大家好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)邊界條件自己找。難題，遞推類問題64大家好下面介紹一個(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è)初始條件推出來65大家好2．N個(gè)人在操場里圍成一圈，將這N個(gè)人按順時(shí)針方向從1到N編號(hào)，然后從第一個(gè)人起，每隔一個(gè)人讓下一個(gè)人離開操場，顯然，第一輪過后，具有偶數(shù)編號(hào)的人都離開了操場。依次做下去，直到操場只剩下一個(gè)人，記這個(gè)人的編號(hào)為J(N)，例如，J(5)=3，J(10)=5，等等。則J(400)=

_______。（提示：對(duì)J(N)=2m+r進(jìn)行分析，其中0≤r<2m）。289，找規(guī)律，數(shù)學(xué)好的智商分?jǐn)?shù)的比較占優(yōu)勢(shì)66大家好非常容易看出：J(N)=J(2m+r)=2r+1J(400)=J(28+144)=2*144+1=28967大家好問題求解總結(jié)1、要耐心地尋找規(guī)律2、要冷靜的分析問題3、不到萬不得已決不輕言放棄4、不懂就蒙一個(gè)！68大家好閱讀程序1、認(rèn)真計(jì)算2、耐心分析3、分析不下去就函數(shù)（語句作用）4、千萬記得第一個(gè)閱讀程序要檢查5、多多練習(xí)，熟能生巧6、列出變量變化表69大家好程序填空這種題與編程經(jīng)驗(yàn)和算法學(xué)習(xí)的程度有關(guān)，拿得一分是一分。不過對(duì)于編程經(jīng)驗(yàn)不足和算法練習(xí)少的人來說也不是沒分可拿。比如說——70大家好程序填空總結(jié)

1、分析語句是干什么的，回到開頭講的內(nèi)容：

①初始化

②一些明顯的動(dòng)作：

a.結(jié)果沒有儲(chǔ)存在需要的地方。b.累加器沒有做加法c.輸出

③關(guān)鍵動(dòng)作。2、不懂就根據(jù)上下文猜3、不寫白不寫，蒙一下總是好的。4、千萬注意開頭和結(jié)尾，常常有送分題目！71大家好幾個(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)于遞歸的說法中，

正確的是（

）。AC72大家好A.

gcc/g++

C.

Turbo

CB.

Turbo

Pascal

D.

free

pascal16.在下列各軟件中，屬于

NOIP

競賽（復(fù)賽）推薦使用的語言環(huán)境有（

）。

ABD73大家好A.

Pascal和C都是編譯執(zhí)行的高級(jí)語言B.

高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C.

C++是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D.

高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高18.

在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（

）。AB74大家好