第一講：計(jì)算機(jī)的基礎(chǔ)知識(shí)

第三講信息學(xué)競(jìng)賽基礎(chǔ)知識(shí)

初賽試題結(jié)構(gòu)第一部分基礎(chǔ)知識(shí)(20*1.5=30)第二部分問題求解(2*5=10)第三部分閱讀程序(4*8=32)第四部分完善程序(2*14=28)

一、計(jì)算機(jī)發(fā)展及應(yīng)用1、第一臺(tái)電子計(jì)算機(jī)的誕生1946年，世界上第一臺(tái)數(shù)字式電于計(jì)算機(jī)是由美固賓夕法尼亞大學(xué)的物理學(xué)家約翰·莫克利（JohnMauchly）和工程師普雷斯伯·?？颂兀↗.hesper.Eckert）領(lǐng)導(dǎo)研制的取名為ENIAC（ElecotmnicNurnericalIntegratorAndCalculator）的計(jì)算杌。

馮·諾依曼依據(jù)存儲(chǔ)程序的工作原理設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC（離散變量自動(dòng)電子計(jì)算機(jī)）。EDVAC由運(yùn)算器、控制器、存儲(chǔ)器、輸人設(shè)備和輸出設(shè)備這五部分組成，輸入設(shè)備運(yùn)算器存儲(chǔ)器控制器輸出設(shè)備輸入輸出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC2、計(jì)算機(jī)發(fā)展的幾個(gè)階段

第一代（1946～1958）第二代（1958～1964）第三代（1964～1975）第四代（1975～至今）主要電子器件電子管晶體管中小規(guī)模集成電路大規(guī)模／超大規(guī)模集成電路①微型計(jì)算機(jī)的問世是由于（）的出現(xiàn)。(NOIP8)A）中小規(guī)模集成電路B）晶體管電路C）（超）大規(guī)模集成電路D）電子管電路C3、計(jì)算機(jī)應(yīng)用⑴科學(xué)計(jì)算（數(shù)值計(jì)算）：利用計(jì)算機(jī)解決科學(xué)研究和工程技術(shù)中所提出的復(fù)雜的數(shù)學(xué)問題。⑵數(shù)據(jù)處理（信息處理）：利用計(jì)算機(jī)對(duì)所獲取的信息進(jìn)行記錄、整理、加工、存儲(chǔ)和傳輸?shù)?。⑶人工智能：利用?jì)算機(jī)來模仿人類的智力活動(dòng)。⑷自動(dòng)控制：利用計(jì)算機(jī)對(duì)動(dòng)態(tài)的過程進(jìn)行控制、指揮和協(xié)調(diào)。⑸計(jì)算機(jī)輔助設(shè)計(jì)和制造：利用計(jì)算機(jī)來輔助工程師們?cè)O(shè)計(jì)和制造產(chǎn)品。CAI（計(jì)算機(jī)輔助教學(xué)）CAM（計(jì)算機(jī)輔助制造）CAT（計(jì)算機(jī)輔助測(cè)試）CAD（計(jì)算機(jī)輔助設(shè)計(jì)）CAE(計(jì)算機(jī)輔助教育)CIMS（計(jì)算機(jī)集成制造系統(tǒng)）①圖靈(AlanTuring)是（

）。(NOIP9)

A）美國(guó)人

B）英國(guó)人

C）德國(guó)人

D）匈牙利人

艾倫·麥席森·圖靈（AlanMathisonTuring，1912年6月23日-1954年6月7日），英國(guó)數(shù)學(xué)家1931年圖靈進(jìn)入劍橋大學(xué)國(guó)王學(xué)院，畢業(yè)后到美國(guó)普林斯頓大學(xué)攻讀博士學(xué)位，二戰(zhàn)爆發(fā)后回到劍橋，后曾協(xié)助軍方破解德國(guó)的著名密碼系統(tǒng)Enigma，幫助盟軍取得了二戰(zhàn)的勝利。圖靈對(duì)于人工智能的發(fā)展有諸多貢獻(xiàn)，例如：圖靈曾寫過一篇名為《機(jī)器會(huì)思考嗎？》（CanMachineThink?）的論文，其中提出了一種用于判定機(jī)器是否具有智能的試驗(yàn)方法，即圖靈試驗(yàn)。圖靈獎(jiǎng)是美國(guó)計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立的，又叫"A.M.圖靈獎(jiǎng)"，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人。其名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國(guó)科學(xué)家艾倫·圖靈，這個(gè)獎(jiǎng)設(shè)立目的之一是紀(jì)念這位科學(xué)家。其他知識(shí)點(diǎn)：B②第一個(gè)給計(jì)算機(jī)寫程序的人是（

）。(NOIP9)

A）AlanMathisonTuring

B）AdaLovelace

C）JohnvonNeumannD）JohnMc-Carthy

E）EdsgerWybeDijkstr1、英國(guó)著名詩(shī)人拜倫的女兒AdaLovelace曾設(shè)計(jì)了巴貝奇分析機(jī)上解伯努利方程的一個(gè)程序。她甚至還建立了循環(huán)和子程序的概念。由于她在程序設(shè)計(jì)上的開創(chuàng)性工作，AdaLovelace被稱為世界上第一位程序員。2、董鐵寶是“中國(guó)第一個(gè)程序員”。董鐵寶1945年赴美國(guó)學(xué)習(xí)，在伊利諾伊大學(xué)學(xué)習(xí)、研究時(shí)，他參與了第一代電子計(jì)算機(jī)伊利亞克機(jī)的設(shè)計(jì)、編程和使用。董鐵寶于1956年回到中國(guó)并任教于北京大學(xué)，成為王選（計(jì)算數(shù)學(xué)專業(yè)院士）的老師。董鐵寶在1968年文化大革命期間自殺身亡。B二、保護(hù)知識(shí)產(chǎn)權(quán)：《計(jì)算機(jī)軟件保護(hù)條例》最早是1991年6月4日國(guó)務(wù)院發(fā)布的<<計(jì)算機(jī)軟件保護(hù)條例>>，現(xiàn)已廢止?，F(xiàn)公布《計(jì)算機(jī)軟件保護(hù)條例》，自2002年1月1日起實(shí)施

。第二章軟件著作權(quán)第八條

軟件著作權(quán)人享有下列各項(xiàng)權(quán)利：（一）發(fā)表權(quán)（二）署名權(quán)（三）修改權(quán)（四）復(fù)制權(quán)；（五）發(fā)行權(quán)（六）出租權(quán)（七）信息網(wǎng)絡(luò)傳播權(quán)（八）翻譯權(quán)（九）應(yīng)當(dāng)由軟件著作權(quán)人享有的其他權(quán)利。①計(jì)算機(jī)軟件保護(hù)法是用來保護(hù)軟件()的（NOIP7）

A)編寫權(quán)B)復(fù)制權(quán)C)使用權(quán)D)著作權(quán)三、計(jì)算機(jī)病毒計(jì)算機(jī)病毒是一種功能較特殊的計(jì)算機(jī)程序，計(jì)算機(jī)病毒的特征可以歸納為下面兩點(diǎn)：⑴能夠?qū)⒆陨韽?fù)制到其他程序中。⑵不獨(dú)立以文件形式存在，僅附加在別的程序上。失去這兩個(gè)特征中的任何一個(gè)，都不成其為病毒。D①計(jì)算機(jī)病毒是()(NOIP7)

A)通過計(jì)算機(jī)傳播的危害人體健康的一種病毒

B)人為制造的能夠侵入計(jì)算機(jī)系統(tǒng)并給計(jì)算機(jī)帶來故障的程序或指令集合

C)一種由于計(jì)算機(jī)元器件老化而產(chǎn)生的對(duì)生態(tài)環(huán)境有害的物質(zhì)

D)利用計(jì)算機(jī)的海量高速運(yùn)算能力而研制出來的用于疾病預(yù)防的新型病毒②計(jì)算機(jī)病毒的特點(diǎn)是（）(NOIP6)

A.傳播性、潛伏性、易讀性與隱蔽性B.破壞性、傳播性、潛伏性與安全性

C.傳播性、潛伏性、破壞性與隱蔽性D.傳播性、潛伏性、破壞性與易讀性

③計(jì)算機(jī)病毒傳染的必要條件是：（）。(NOIP8)A）在內(nèi)存中運(yùn)行病毒程序B）對(duì)磁盤進(jìn)行讀寫操作

C）在內(nèi)存中運(yùn)行含有病毒的可執(zhí)行的程序D）復(fù)制文件BCB四、計(jì)算機(jī)的組成1、計(jì)算機(jī)的硬件系統(tǒng)由五個(gè)基本部分組成：運(yùn)算器控制器存儲(chǔ)器（有內(nèi)存儲(chǔ)器和外存儲(chǔ)器之分）輸人設(shè)備輸出設(shè)備①CPU訪問內(nèi)存的速度比訪問下列哪個(gè)（些）存儲(chǔ)設(shè)備要慢（

）。（NOIP9）

A）寄存器

B）硬盤

C）軟盤

D）高速緩存

E）光盤②微型計(jì)算機(jī)中，（）的存取速度最快。(NOIP8)A）高速緩存B）外存儲(chǔ)器C）寄存器D）內(nèi)存儲(chǔ)器③在計(jì)算機(jī)硬件系統(tǒng)中，cache是()存儲(chǔ)器(NOIP7)

A)只讀B)可編程只讀C)可擦除可編程只讀D)高速緩沖ADAD2、三總線結(jié)構(gòu)：

地址總線、數(shù)據(jù)（包括指令）總線和控制總線，分別傳送地址信號(hào)、數(shù)據(jù)信號(hào)和控制信號(hào)。①中央處理器（CPU）能訪問的最大存儲(chǔ)器容量取決于（）。(NOIP8NOIP7)A）地址總線B）數(shù)據(jù)總線C）控制總線D）實(shí)際內(nèi)存容量②計(jì)算機(jī)系統(tǒng)總線上傳送的信號(hào)有（）(NOI6)

A.地址信號(hào)與控制信號(hào)B.數(shù)據(jù)信號(hào)、控制信號(hào)與地址信號(hào)

C.控制信號(hào)與數(shù)據(jù)信號(hào)D.數(shù)據(jù)信號(hào)與地址信號(hào)

AB五、計(jì)算機(jī)指令系統(tǒng)計(jì)算機(jī)能直接識(shí)別和執(zhí)行的命令稱為指令。指令本身是二進(jìn)制代碼。是要計(jì)算機(jī)執(zhí)行某種操作的命令。用機(jī)器指令編寫的程序稱之為機(jī)器語言程序。一條指令通常由操作碼和地址碼兩部分組成。六、計(jì)算機(jī)的數(shù)字系統(tǒng)數(shù)值信息在計(jì)算機(jī)內(nèi)的表示方法就是用二進(jìn)制數(shù)來表示。一般說來，如果數(shù)制只采用R個(gè)基本符號(hào)，則稱為基R數(shù)值，R稱為數(shù)制的基數(shù)，而數(shù)制中每一固定位置對(duì)應(yīng)的單位值稱為權(quán)。進(jìn)制基數(shù)R基本符號(hào)二進(jìn)制20，1八進(jìn)制80,1,2,3,4,5,6,7十進(jìn)制100,1,2,3,4,5,6,7,8,9十六進(jìn)制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（對(duì)應(yīng)十進(jìn)制數(shù)的10—15。）進(jìn)位計(jì)數(shù)制的編碼符合“逢R進(jìn)位”的規(guī)則，各位的權(quán)是以R為底的冪，一個(gè)數(shù)可按權(quán)展開成為多項(xiàng)式。例如，一個(gè)十進(jìn)制數(shù)256.47可按權(quán)展開為256.47=2×102＋5×101＋6×10°十4×10-1＋7×10-21、R進(jìn)制轉(zhuǎn)換為十進(jìn)制基數(shù)為R的數(shù)字，只要將各位數(shù)字與它的權(quán)相乘，其積相加,和數(shù)就是十進(jìn)制數(shù)例:3506.28=6×8°+0×81+5×82+3×83+2×8-1=1862.25

例:0.2A16=2×16-1+10×16-2

=0.16406252、十進(jìn)制轉(zhuǎn)換為R進(jìn)制將＋進(jìn)制數(shù)轉(zhuǎn)換為基數(shù)為R的等效表示時(shí)，可將此數(shù)分成整數(shù)與小數(shù)兩部分分別轉(zhuǎn)換，然后再拼接起來即可實(shí)現(xiàn)。＋進(jìn)制整數(shù)轉(zhuǎn)換成R進(jìn)制的整數(shù)，可用十進(jìn)制數(shù)連續(xù)地除以R，其余數(shù)即為R系統(tǒng)的各位系數(shù)。此方法稱之除R取余法。十進(jìn)制小數(shù)轉(zhuǎn)換成R進(jìn)制時(shí)，可連續(xù)地乘以R，直到小數(shù)部分為0，或達(dá)到所要求的精度為止（小數(shù)部分可能永不為零），得到的整數(shù)即組成R進(jìn)制的小數(shù)部分，此法稱為“乘R取整”例：將0.312510轉(zhuǎn)換成二進(jìn)制數(shù)0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0所以0.312510=0.010123、二、八、十六進(jìn)制的相互轉(zhuǎn)換二、八、十六進(jìn)制的相互轉(zhuǎn)換在應(yīng)用中占有重要的地位。由于這三種數(shù)制的權(quán)之間有內(nèi)在的聯(lián)系，即23=8，24=16，因而它們之間的轉(zhuǎn)換比較容易.即每位八進(jìn)制數(shù)相當(dāng)于三位二進(jìn)制數(shù)，每位十六進(jìn)制數(shù)相當(dāng)于四位二進(jìn)制數(shù)。在轉(zhuǎn)換時(shí)，位組劃分是以小數(shù)點(diǎn)為中心向左右兩邊延伸，中間的0不能省略，兩頭不夠時(shí)可以補(bǔ)0。例如：將1011010.102轉(zhuǎn)換成八進(jìn)制和十六進(jìn)制數(shù)001011010.1001011010.102＝132.48132.401011010.10001011010.102=5A.816

5A.8

將十六進(jìn)制數(shù)F7.28變?yōu)槎M(jìn)制數(shù)F7.28F7.2816=11110111.00101211110111.00101000①十進(jìn)制數(shù)2003等值于二進(jìn)制數(shù)（

）。(NOIP9)

A）0100000111

B）10000011

C）110000111

D）11111010011

E）1111010011②十進(jìn)制書11/128可用二進(jìn)制數(shù)碼序列表示為:()。(NOIP8)A）1011/1000000B）1011/100000000C）0.001011D）0.0001011③算式（2047）10－（3FF）16＋（2000）8的結(jié)果是（）。(NOIP8NOIP7)A）（2048）10B）（2049）10C）（3746）8D）（1AF7）16④64KB的存儲(chǔ)器用十六進(jìn)制表示，它的最大的地址碼是()(NOIP7)

A)10000

B)FFFF

C)1FFFF

D)EFFFFDDAB⑤十進(jìn)制算術(shù)表達(dá)式3*512+7*64+4*8+5的運(yùn)算結(jié)果，用二進(jìn)制表示為().(NOIP5)A·10111100101B·11111100101C·11110100101D·11111101101⑥下列無符號(hào)數(shù)中，最小的數(shù)是（）(NOIP6)

A.（11011001）2

B.(75)10

C.(37)8

D.(2A)16⑦運(yùn)算式(2008)10-(3723)8的結(jié)果是（

）。NOIP9

A）(-1715)10

B)(5)10

C)(5)16

D)(101)2

E)(3263)8

BCBCD七、在計(jì)算機(jī)中帶符號(hào)數(shù)的表示法原碼在用二進(jìn)制原碼表示的數(shù)中，符號(hào)位為0表示正數(shù)，符號(hào)位為1表示負(fù)數(shù)，其余各位表示數(shù)值部分。如：10000010，00000010補(bǔ)碼正數(shù)的補(bǔ)碼就是該正數(shù)本身。

[01100100]補(bǔ)＝01000100

對(duì)于負(fù)數(shù):兩頭的1不變，中間取反。

[10100100]補(bǔ)＝11011100

[+0]補(bǔ)＝[-0]補(bǔ)＝00…0。反碼〈0ne’sComplement〉反碼的定義如下:⑴對(duì)于正數(shù)，它的反碼表示與原碼相同。即[x]反=[x]原⑵對(duì)于負(fù)數(shù)，則除符號(hào)位仍為“1”外，其余各位“1”換成”0”，”0”換成1”，即得到反碼[X]反。例如[-1101001]

反=10010110。⑶對(duì)于0，它的反碼有兩種表示:[+0]

反=00…0[-0]

反=11…1BCD碼（8421碼）BCD碼就是用二進(jìn)制代碼表示的十進(jìn)制數(shù)，也稱BCD數(shù)。它是用二進(jìn)制代碼0000—1001來表示十進(jìn)制數(shù)0---9。如：39的BCD碼為00111001。①已知x=（0.1011010）2

，則[x/2]補(bǔ)=（）2。(NOIP8)A）0.1011101B）11110110C）0.0101101D）0.100110②[x]補(bǔ)碼=10011000，其原碼為()(NOIP7)

A)011001111

B)11101000

C)11100110

D)01100101CB八、信息存儲(chǔ)單位⑴位（bit，縮寫為b）：度量數(shù)據(jù)的最小單位，表示一位二進(jìn)制信息。⑵字節(jié)(byte，縮寫為B)：一個(gè)字節(jié)由八位二進(jìn)制數(shù)字組成（lbyte＝8bit）。字節(jié)是信息存儲(chǔ)中最常用的基本單位。計(jì)算機(jī)存儲(chǔ)器（包括內(nèi)存與外存）通常也是以多少字節(jié)來表示它的容量。常用的單位有：KB1K=1024MB1M=1024KGB1G=1024MTB1t=1024G機(jī)器字（word）：字是位的組合，并作為一個(gè)獨(dú)立的信息單位處理。字又稱為計(jì)算機(jī)字，它取決于機(jī)器的類型、字長(zhǎng)以及使用者的要求。常用的固定字長(zhǎng)有8位、16位、32位等。九、計(jì)算機(jī)網(wǎng)絡(luò)知識(shí)1、計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中各個(gè)站點(diǎn)相互連接的方法和形式稱之為網(wǎng)絡(luò)拓?fù)淇偩€拓?fù)湫切屯負(fù)?/p>

環(huán)型拓?fù)?/p>

樹型拓?fù)?/p>

2、計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)的核心是OSI模型國(guó)際標(biāo)準(zhǔn)化組織（ISO）提出的開放系統(tǒng)互聯(lián)參考模型（OSI）已成為網(wǎng)絡(luò)體系結(jié)構(gòu)的標(biāo)準(zhǔn)

在這些層中，除了最高的第7層沒有需要服務(wù)的上一層、最低的第1層沒有可利用服務(wù)的下一層外，其它的每一層都建立在下一層的基礎(chǔ)上，利用下一層來實(shí)現(xiàn)自己的功能，并向上一級(jí)提供服務(wù)。主機(jī)A與主機(jī)B進(jìn)行通信時(shí)，通信協(xié)議是在對(duì)等層之間進(jìn)行的。其中，物理層與物理層之間的通信協(xié)議是直接的，其他對(duì)等層之間的通信協(xié)議都是間接的。3、Internet網(wǎng)絡(luò)地址

(IP地址)A類網(wǎng)絡(luò)為大型網(wǎng)絡(luò)；B類網(wǎng)絡(luò)為中型網(wǎng)絡(luò)；C類網(wǎng)絡(luò)為小型網(wǎng)絡(luò)。這三類網(wǎng)絡(luò)的地址特征為⑴A類網(wǎng)絡(luò)以0開頭，網(wǎng)絡(luò)號(hào)碼是7位，主機(jī)號(hào)碼是24位⑵B類網(wǎng)絡(luò)以10開頭，網(wǎng)絡(luò)號(hào)碼是14位，主機(jī)號(hào)碼是16位⑶C類網(wǎng)絡(luò)以110開頭，C類網(wǎng)絡(luò)的網(wǎng)絡(luò)號(hào)碼是21位，主機(jī)號(hào)碼是8位D類地址以1110開頭，E類地址以11110開頭。八、邏輯運(yùn)算：與/\、或：\/,運(yùn)算優(yōu)先級(jí)：/\>\/①假設(shè)A=true,B=false,C=ture,D=ture,邏輯運(yùn)算表達(dá)式A/\B\/C/\D的值是（

）。(NOIP9)

A）true

B）false

C）0

D）1

E）NULL②已知A=35H，A/\05H\/A/\30H的結(jié)果是：（）。(NOIP8)A）30HB）05HC）35HD）53HAC

九、其他

①(NOIP6)電線上停著兩種鳥：A，B，可以看出兩只相鄰的鳥就將電線分為了一個(gè)線段。這些線段可分為兩類；

一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同。

已知：電線兩個(gè)頂點(diǎn)上正好停著相同的小鳥，試問兩端為不同小鳥的線段數(shù)目一定是（）。

A.奇數(shù)B.偶數(shù)C.可奇可偶D.數(shù)目固定B②(NOIP8)要使1．．．8號(hào)格字的訪問順序?yàn)椋?、2、6、5、7、3、1、4，則下圖中的空格中應(yīng)填入（）。12345678461-17

32A）6B）0C）5D）3③(NOI2003)32只球隊(duì)參加比賽，要想最后決出冠亞軍，至少進(jìn)行（）場(chǎng)比賽。（A）31(B)33(C)34(D)35CD信息學(xué)競(jìng)賽中的數(shù)學(xué)知識(shí)從n個(gè)不同元素中,任取m個(gè)元素,按照一定的順序排成一列,叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列.2.組合的定義:從n個(gè)不同元素中,任取m個(gè)元素,并成一組,叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合.3.排列數(shù)公式:4.組合數(shù)公式:1.排列的定義:排列與組合的區(qū)別與聯(lián)系:與順序有關(guān)的為排列問題,與順序無關(guān)的為組合問題.加法原理和乘法原理從A到C共有多少中走法？ABC例1

學(xué)校師生合影，共8個(gè)學(xué)生，4個(gè)老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同的合影方式？解先排學(xué)生共有種排法,然后把老師插入學(xué)生之間的空檔，共有7個(gè)空檔可插,選其中的4個(gè)空檔,共有種選法.根據(jù)乘法原理,共有的不同坐法為種.結(jié)論1

插入法:對(duì)于某兩個(gè)元素或者幾個(gè)元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.分析此題涉及到的是不相鄰問題,并且是對(duì)老師有特殊的要求,因此老師是特殊元素,在解決時(shí)就要特殊對(duì)待.所涉及問題是排列問題.例25個(gè)男生3個(gè)女生排成一排,3個(gè)女生要排在一起,有多少種不同的排法?

解

因?yàn)榕旁谝黄?所以可以將3個(gè)女生看成是一個(gè)人,與5個(gè)男生作全排列,有種排法,其中女生內(nèi)部也有種排法,根據(jù)乘法原理,共有種不同的排法.結(jié)論2

捆綁法:要求某幾個(gè)元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個(gè)元素,再與其它元素一起作排列,同時(shí)要注意合并元素內(nèi)部也可以作排列.分析此題涉及到的是排隊(duì)問題,對(duì)于女生有特殊的限制,因此,女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個(gè)元素來解決問題.例3

袋中有不同年份生產(chǎn)的5分硬幣23個(gè),不同年份生產(chǎn)的1角硬幣10個(gè),如果從袋中取出2元錢,