第一講：計算機的基礎(chǔ)知識

第三講信息學競賽基礎(chǔ)知識

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

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

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

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

）。(NOIP9)

A）美國人

B）英國人

C）德國人

D）匈牙利人

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

）。(NOIP9)

A）AlanMathisonTuring

B）AdaLovelace

C）JohnvonNeumannD）JohnMc-Carthy

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

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

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

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

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

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

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

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

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

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

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

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

）。（NOIP9）

A）寄存器

B）硬盤

C）軟盤

D）高速緩存

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

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

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

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

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

AB五、計算機指令系統(tǒng)計算機能直接識別和執(zhí)行的命令稱為指令。指令本身是二進制代碼。是要計算機執(zhí)行某種操作的命令。用機器指令編寫的程序稱之為機器語言程序。一條指令通常由操作碼和地址碼兩部分組成。六、計算機的數(shù)字系統(tǒng)數(shù)值信息在計算機內(nèi)的表示方法就是用二進制數(shù)來表示。一般說來，如果數(shù)制只采用R個基本符號，則稱為基R數(shù)值，R稱為數(shù)制的基數(shù)，而數(shù)制中每一固定位置對應的單位值稱為權(quán)。進制基數(shù)R基本符號二進制20，1八進制80,1,2,3,4,5,6,7十進制100,1,2,3,4,5,6,7,8,9十六進制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（對應十進制數(shù)的10—15。）進位計數(shù)制的編碼符合“逢R進位”的規(guī)則，各位的權(quán)是以R為底的冪，一個數(shù)可按權(quán)展開成為多項式。例如，一個十進制數(shù)256.47可按權(quán)展開為256.47=2×102＋5×101＋6×10°十4×10-1＋7×10-21、R進制轉(zhuǎn)換為十進制基數(shù)為R的數(shù)字，只要將各位數(shù)字與它的權(quán)相乘，其積相加,和數(shù)就是十進制數(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、十進制轉(zhuǎn)換為R進制將＋進制數(shù)轉(zhuǎn)換為基數(shù)為R的等效表示時，可將此數(shù)分成整數(shù)與小數(shù)兩部分分別轉(zhuǎn)換，然后再拼接起來即可實現(xiàn)。＋進制整數(shù)轉(zhuǎn)換成R進制的整數(shù)，可用十進制數(shù)連續(xù)地除以R，其余數(shù)即為R系統(tǒng)的各位系數(shù)。此方法稱之除R取余法。十進制小數(shù)轉(zhuǎn)換成R進制時，可連續(xù)地乘以R，直到小數(shù)部分為0，或達到所要求的精度為止（小數(shù)部分可能永不為零），得到的整數(shù)即組成R進制的小數(shù)部分，此法稱為“乘R取整”例：將0.312510轉(zhuǎn)換成二進制數(shù)0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0所以0.312510=0.010123、二、八、十六進制的相互轉(zhuǎn)換二、八、十六進制的相互轉(zhuǎn)換在應用中占有重要的地位。由于這三種數(shù)制的權(quán)之間有內(nèi)在的聯(lián)系，即23=8，24=16，因而它們之間的轉(zhuǎn)換比較容易.即每位八進制數(shù)相當于三位二進制數(shù)，每位十六進制數(shù)相當于四位二進制數(shù)。在轉(zhuǎn)換時，位組劃分是以小數(shù)點為中心向左右兩邊延伸，中間的0不能省略，兩頭不夠時可以補0。例如：將1011010.102轉(zhuǎn)換成八進制和十六進制數(shù)001011010.1001011010.102＝132.48132.401011010.10001011010.102=5A.816

5A.8

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

）。(NOIP9)

A）0100000111

B）10000011

C）110000111

D）11111010011

E）1111010011②十進制書11/128可用二進制數(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的存儲器用十六進制表示，它的最大的地址碼是()(NOIP7)

A)10000

B)FFFF

C)1FFFF

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

A.（11011001）2

B.(75)10

C.(37)8

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

）。NOIP9

A）(-1715)10

B)(5)10

C)(5)16

D)(101)2

E)(3263)8

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

[01100100]補＝01000100

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

[10100100]補＝11011100

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

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

反=00…0[-0]

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

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

A)011001111

B)11101000

C)11100110

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

環(huán)型拓撲

樹型拓撲

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

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

(IP地址)A類網(wǎng)絡為大型網(wǎng)絡；B類網(wǎng)絡為中型網(wǎng)絡；C類網(wǎng)絡為小型網(wǎng)絡。這三類網(wǎng)絡的地址特征為⑴A類網(wǎng)絡以0開頭，網(wǎng)絡號碼是7位，主機號碼是24位⑵B類網(wǎng)絡以10開頭，網(wǎng)絡號碼是14位，主機號碼是16位⑶C類網(wǎng)絡以110開頭，C類網(wǎng)絡的網(wǎng)絡號碼是21位，主機號碼是8位D類地址以1110開頭，E類地址以11110開頭。八、邏輯運算：與/\、或：\/,運算優(yōu)先級：/\>\/①假設(shè)A=true,B=false,C=ture,D=ture,邏輯運算表達式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，可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類；

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

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

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

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

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

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

解

因為女生要排在一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有種排法,其中女生內(nèi)部也有種排法,根據(jù)乘法原理,共有種不同的排法.結(jié)論2

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

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