初賽復(fù)習(xí)一、計(jì)算機(jī)的兩位重要人物圖靈：被稱為“人工智能之父”，1966年設(shè)立的圖靈獎(jiǎng)是計(jì)算機(jī)界最負(fù)盛名的獎(jiǎng)項(xiàng)，有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱馮·諾依曼：被稱為“計(jì)算機(jī)之父”，他的精髓貢獻(xiàn)是2點(diǎn)：2進(jìn)制思想與程序內(nèi)存思想。1.在下面各世界頂級(jí)的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（

）（2006）

A.沃爾夫獎(jiǎng)

B.

諾貝爾獎(jiǎng)

C.菲爾茲獎(jiǎng)

D.圖靈獎(jiǎng)

E.

南丁格爾獎(jiǎng)2.美籍匈牙利數(shù)學(xué)家馮·諾依曼對(duì)計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)包括（）（2004）A.提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。B.提出存儲(chǔ)程序工作原理，對(duì)現(xiàn)代電子計(jì)算機(jī)的發(fā)展產(chǎn)生深遠(yuǎn)影響。C.設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC。D.采用集成電路作為計(jì)算機(jī)的主要功能部件。E.指出計(jì)算機(jī)性能將以每?jī)赡攴环乃俣认蚯鞍l(fā)展。DBC二、計(jì)算機(jī)的組成

馮·諾依曼提出的計(jì)算機(jī)系統(tǒng)由五大部分組成，并一直沿用至今：①運(yùn)算器：完成運(yùn)算的算術(shù)邏輯單元（ALU）和存放操作數(shù)和運(yùn)算結(jié)果的寄存器②控制器：全機(jī)的指揮中心，負(fù)責(zé)象整個(gè)電腦各個(gè)部分發(fā)出命令

③存儲(chǔ)器：內(nèi)存儲(chǔ)器（只讀存儲(chǔ)器ROM和隨機(jī)存儲(chǔ)器RAM）和外存儲(chǔ)器（硬盤，u盤，光盤）④輸入設(shè)備：鼠標(biāo)，鍵盤，麥克風(fēng)，數(shù)碼相機(jī)，掃描儀⑤輸出設(shè)備：顯示器，打印機(jī)，音箱，投影儀等1、在以下各項(xiàng)中（

）不是CPU的組成部分。（2006）

A.控制器

B.運(yùn)算器

C.寄存器

D.ALU

E.RAM2.BIOS（基本輸入輸出系統(tǒng)）是一組固化在計(jì)算機(jī)內(nèi)（

）上一個(gè)ROM芯片上的程序（2006）

A.控制器

B.CPU

C.主板

D.內(nèi)存條

E.硬盤3.以下斷電之后將不能保存數(shù)據(jù)的有（

）（2006）

A.硬盤

B.ROM

C.顯存

D.RAM

4.以下哪個(gè)（些）不是計(jì)算機(jī)的輸出設(shè)備（）（2005）

A.鼠標(biāo)B.顯示器C.鍵盤D.掃描儀E.繪圖儀5.以下斷電之后將不能保存數(shù)據(jù)的有（）（2005）

A.硬盤B.寄存器C.顯存D.內(nèi)存E.高速緩存6.下列哪個(gè)（些）不是計(jì)算機(jī)的存儲(chǔ)設(shè)備（）（2004）

A.文件管理器B.內(nèi)存C.顯卡D.硬盤E.U盤ECCDACDEBCDEAC三、進(jìn)制轉(zhuǎn)換①二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)：按權(quán)展開求和例：將二進(jìn)制數(shù)1011.01轉(zhuǎn)換成十進(jìn)制數(shù)（1011.01）2=（1×23+0×22+1×21+1×20+0×2-1+1×2-2）10②二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)：由于一位八進(jìn)制數(shù)對(duì)應(yīng)位二進(jìn)制數(shù)，所以二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)時(shí)，只要以小數(shù)點(diǎn)為界，整數(shù)部分向左，小數(shù)部分向右每3位分為一組，各組用對(duì)應(yīng)的1位八進(jìn)制數(shù)字表示，即可得到對(duì)應(yīng)的八進(jìn)制數(shù)值。最左最右端分組不足3位時(shí)，可用0補(bǔ)足。例：將二進(jìn)制數(shù)1101101.10101轉(zhuǎn)換為對(duì)應(yīng)的八進(jìn)制數(shù)

001

101

101.101

01015552所以（1101101.10101）2=（155.52）8③二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)：和二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)類似，只不過分組的時(shí)候是四位為一組。例：將二進(jìn)制數(shù)1101101.10101轉(zhuǎn)換為對(duì)應(yīng)的十六進(jìn)制數(shù)

0110

1101.1010

10006DA8所以（1101101.10101）2=（6D.A8）16注：八、十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)過程與此兩過程相反①十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：對(duì)于整數(shù)部分，用被除數(shù)反復(fù)除以2，除第一次外，每次除以2均取前一次商的整數(shù)部分作為被除數(shù)并依次記下每次的余數(shù)。另外，所得到的商的最后一位余數(shù)是所求二進(jìn)制數(shù)的最高位。例：將十進(jìn)制數(shù)117.625轉(zhuǎn)換成二進(jìn)制數(shù)整數(shù)部分：除2取余，逆序輸出58291177141302222222…………1…………1…………1…………1…………1…………0…………0小數(shù)部分：乘2取整，順序輸出0.62520.2520.500.521.01.250…………1…………0…………1×××所以（117.625）10=（1110101.101）21、以下二進(jìn)制數(shù)的值與十進(jìn)制數(shù)23.456的值最接近的是（）。（2005）

A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.11112、(3725)8+(B)16的運(yùn)算結(jié)果是（）。（2005）

A.(3736)8B.(2016)10C.(11111100000)2D.(3006)10E.(7E0)163.與十進(jìn)制數(shù)1770.625對(duì)應(yīng)的八進(jìn)制數(shù)是（

）(2006)A.3352.5

B.3350.5

C.3352.1161

D.3350.1151

E.前4個(gè)答案都不對(duì)4.

(2010)16+(32)8的結(jié)果是（

）(2006)

A.(8234)10

B.(202A)16

C.(100000000110)2

D.(2042)16DBCEABA四、邏輯運(yùn)算①與運(yùn)算：運(yùn)算符號(hào)通常為And，∩，或∧0∧0=00∧1=01∧0=01∧1=1

假∧假=假假∧真=假真∧假=假真∧真=真②或運(yùn)算：運(yùn)算符號(hào)通常為Or，∪，或∨0∨0=00∨1=11∨0=11∨1=1

假∨假=假假∨真=真真∨假=真真∨真=真③非運(yùn)算：運(yùn)算符號(hào)通常為Not，－，或~

－0=1－1=0－假=真－真=假④異或運(yùn)算：運(yùn)算符號(hào)通常為Xor0xor0=00xor1=01xor0=01xor1=1

假xor假=假假xor真=真真xor假=真真xor真=假邏輯運(yùn)算中運(yùn)算符號(hào)的優(yōu)先級(jí)為：

not>and>or1.設(shè)A=B=D=true，C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（

）（2006）

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

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

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

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

2.設(shè)A=true，B=false，C=false，D=true，以下邏輯運(yùn)算表達(dá)式值為真的有（

）。（2005）

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

D.(A∧(B∨C))∨DE.(A∨B)∧(C∨D)3.在Pascal語言中，表達(dá)式(21xor2)的值是（

）（2006）

A.441

B.42

C.23

D.24

E.25ABCCDEC棧的定義：棧是一種特殊的表這種表只在表頭進(jìn)行插入和刪除操作。因此，表頭對(duì)于棧來說具有特殊的意義，稱為棧頂。相應(yīng)地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的邏輯結(jié)構(gòu)：假設(shè)一個(gè)棧S中的元素為an,an-1,..,a1，則稱a1為棧底元素，an為棧頂元素。棧中的元素按a1,a2,..,an-1,an的次序進(jìn)棧。在任何時(shí)候，出棧的元素都是棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的，如圖1所示。因此，棧又稱為后進(jìn)先出(LastInFirstOut)表，簡(jiǎn)稱為L(zhǎng)IFO表。所以，只要問題滿足LIFO原則，就可以使用棧。

四、棧歷年奧賽試題（2006,2004）7．某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(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)椋╟）。

A.1,2,3,4,5

B.1,2,4,5,7

C.1,4,3,7,6

D.1,4,3,7,2

E.1,4,3,7,5（2006）13.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有（

）。

A.a,b,c,e,d

B.b,c,a,e,d

C.a,e,c,b,d

D.d,c,e,b,a

(2005)（多項(xiàng)）14.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現(xiàn)的有（

）。

A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,g

D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a（2003）19．已知元素(8，25，14，87，5l，90，6，19，20)，問這些元素以怎樣的順序進(jìn)入棧，才能使出棧的順序滿足：8在5l前面；90在87后面；20在14后面；25在6前面；19在90后面。()

A)20，6，8，51，90，25，14，19，87

B)51，6，19，20，14，8，87，90，25

C)19，20，90，7，6，25，5l，14，87

D)6，25，51，8，20，19，90，87，14

E)25，6，8，51，87，90，19，14，20隊(duì)列的定義：隊(duì)列是一種特殊的線性表，對(duì)這種線性表，刪除操作只在表頭(稱為隊(duì)頭)進(jìn)行，插入操作只在表尾(稱為隊(duì)尾)進(jìn)行。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的，所以隊(duì)列又稱為先進(jìn)先出(FirstInFirstOut)表，簡(jiǎn)稱FIFO表。隊(duì)列的數(shù)學(xué)性質(zhì)：假設(shè)隊(duì)列為a1,a2,..,an，那么a1就是隊(duì)頭元素，an為隊(duì)尾元素。隊(duì)列中的元素是按a1,a2,..,an的順序進(jìn)入的，退出隊(duì)列也只能按照這個(gè)次序依次退出。也就是說，只有在a1離開隊(duì)列之后，a2才能退出隊(duì)列，只有在a1,a2,..,an-1都離開隊(duì)列之后，an才能退出隊(duì)列。圖1是隊(duì)列的示意圖。五、隊(duì)列歷年奧賽試題(2003)6．已知隊(duì)列(13，2，11，34，4l，77，5，7，18，26，15)，第一個(gè)進(jìn)入隊(duì)列的元素是13，則第五個(gè)出隊(duì)列的元素是()。

A)5B)41C)77D)13E)18（2002）20.設(shè)找棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)閑2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該為(

)。

A)2

B)3

C)4

D)51.樹的概念樹的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹1.樹的度——也即是寬度，簡(jiǎn)單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

2.樹的深度——組成該樹各結(jié)點(diǎn)的最大層次，如上圖，其深度為4；六、樹2.二叉樹二叉樹的基本形態(tài)：

二叉樹也是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：

(1)空二叉樹——(a)；

(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹——(b)；

(3)右子樹為空的二叉樹——(c)；

(4)左子樹為空的二叉樹——(d)；

(5)完全二叉樹——(e)3.兩種重要的樹(1)完全二叉樹——只有最下面的兩層結(jié)點(diǎn)度小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹；

(2)滿二叉樹——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子女且葉結(jié)點(diǎn)都處在最底層的二叉樹,。

如下圖4.二叉樹的性質(zhì)(1)在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1)；(2)深度為h的二叉樹最多有2h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；

(3)對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，

則N0=N2+1；歷年奧塞試題（2006）8．高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。

在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，

則該樹的樹高為（

）。

A.10

B.11

C.12

D.13

E.2–1(2005)

4.完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4*N+3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（

）

A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2(2004)滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（）NB.2*NC.2*N–1D.2*N+1E.2N–1(2002)17.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有(

)種。

A)3

B)4

C)5

D)6CCBE5.樹的遍歷第一種分法：前序遍歷