第一講：計算機的基礎知識

第三講信息學競賽基礎知識

初賽試題結構第一部分基礎知識(20*1.5=30)第二部分問題求解(2*5=10)第三部分閱讀程序(4*8=32)第四部分完善程序(2*14=28)一、計算機發(fā)展及應用1、第一臺電子計算機的誕生1946年，世界上第一臺數字式電于計算機是由美固賓夕法尼亞大學的物理學家約翰·莫克利（JohnMauchly）和工程師普雷斯伯·埃克特（J.hesper.Eckert）領導研制的取名為ENIAC（ElecotmnicNurnericalIntegratorAndCalculator）的計算杌。

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

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

）。(NOIP9)

A）美國人

B）英國人

C）德國人

D）匈牙利人

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

）。(NOIP9)

A）AlanMathisonTuring

B）AdaLovelace

C）JohnvonNeumannD）JohnMc-Carthy

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

。第二章軟件著作權第八條

軟件著作權人享有下列各項權利：（一）發(fā)表權（二）署名權（三）修改權（四）復制權；（五）發(fā)行權（六）出租權（七）信息網絡傳播權（八）翻譯權（九）應當由軟件著作權人享有的其他權利。①計算機軟件保護法是用來保護軟件()的（NOIP7）A)編寫權B)復制權C)使用權D)著作權三、計算機病毒計算機病毒是一種功能較特殊的計算機程序，計算機病毒的特征可以歸納為下面兩點：⑴能夠將自身復制到其他程序中。⑵不獨立以文件形式存在，僅附加在別的程序上。失去這兩個特征中的任何一個，都不成其為病毒。D①計算機病毒是()(NOIP7)A)通過計算機傳播的危害人體健康的一種病毒B)人為制造的能夠侵入計算機系統(tǒng)并給計算機帶來故障的程序或指令集合C)一種由于計算機元器件老化而產生的對生態(tài)環(huán)境有害的物質D)利用計算機的海量高速運算能力而研制出來的用于疾病預防的新型病毒②計算機病毒的特點是（）(NOIP6)

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

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

③計算機病毒傳染的必要條件是：（）。(NOIP8)A）在內存中運行病毒程序B）對磁盤進行讀寫操作C）在內存中運行含有病毒的可執(zhí)行的程序D）復制文件BCB四、計算機的組成1、計算機的硬件系統(tǒng)由五個基本部分組成：運算器控制器存儲器（有內存儲器和外存儲器之分）輸人設備輸出設備①CPU訪問內存的速度比訪問下列哪個（些）存儲設備要慢（

）。（NOIP9）

A）寄存器

B）硬盤

C）軟盤

D）高速緩存

E）光盤②微型計算機中，（）的存取速度最快。(NOIP8)A）高速緩存B）外存儲器C）寄存器D）內存儲器③在計算機硬件系統(tǒng)中，cache是()存儲器(NOIP7)A)只讀B)可編程只讀C)可擦除可編程只讀D)高速緩沖ADAD2、三總線結構：

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

A.地址信號與控制信號B.數據信號、控制信號與地址信號

C.控制信號與數據信號D.數據信號與地址信號

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

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

）。(NOIP9)

A）0100000111

B）10000011

C）110000111

D）11111010011

E）1111010011②十進制書11/128可用二進制數碼序列表示為:()。(NOIP8)A）1011/1000000B）1011/100000000C）0.001011D）0.0001011③算式（2047）10－（3FF）16＋（2000）8的結果是（）。(NOIP8NOIP7)A）（2048）10B）（2049）10C）（3746）8D）（1AF7）16④64KB的存儲器用十六進制表示，它的最大的地址碼是()(NOIP7)A)10000B)FFFFC)1FFFFD)EFFFFDDAB⑤十進制算術表達式3*512+7*64+4*8+5的運算結果，用二進制表示為().(NOIP5)A·10111100101B·11111100101C·11110100101D·11111101101⑥下列無符號數中，最小的數是（）(NOIP6)

A.（11011001）2B.(75)10C.(37)8D.(2A)16⑦運算式(2008)10-(3723)8的結果是（

）。NOIP9

A）(-1715)10

B)(5)10

C)(5)16

D)(101)2

E)(3263)8

BCBCD七、在計算機中帶符號數的表示法原碼在用二進制原碼表示的數中，符號位為0表示正數，符號位為1表示負數，其余各位表示數值部分。如：10000010，00000010補碼正數的補碼就是該正數本身。[01100100]補＝01000100對于負數:兩頭的1不變，中間取反。[10100100]補＝11011100

[+0]補＝[-0]補＝00…0。反碼〈0ne’sComplement〉反碼的定義如下:⑴對于正數，它的反碼表示與原碼相同。即[x]反=[x]原⑵對于負數，則除符號位仍為“1”外，其余各位“1”換成”0”，”0”換成1”，即得到反碼[X]反。例如[-1101001]反=10010110。⑶對于0，它的反碼有兩種表示:[+0]反=00…0[-0]反=11…1BCD碼（8421碼）BCD碼就是用二進制代碼表示的十進制數，也稱BCD數。它是用二進制代碼0000—1001來表示十進制數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)011001111B)11101000C)11100110D)01100101CB八、信息存儲單位⑴位（bit，縮寫為b）：度量數據的最小單位，表示一位二進制信息。⑵字節(jié)(byte，縮寫為B)：一個字節(jié)由八位二進制數字組成（lbyte＝8bit）。字節(jié)是信息存儲中最常用的基本單位。計算機存儲器（包括內存與外存）通常也是以多少字節(jié)來表示它的容量。常用的單位有：KB1K=1024MB1M=1024KGB1G=1024MTB1t=1024G機器字（word）：字是位的組合，并作為一個獨立的信息單位處理。字又稱為計算機字，它取決于機器的類型、字長以及使用者的要求。常用的固定字長有8位、16位、32位等。九、計算機網絡知識1、計算機網絡的拓撲結構網絡中各個站點相互連接的方法和形式稱之為網絡拓撲總線拓撲星型拓撲

環(huán)型拓撲

樹型拓撲

2、計算機網絡體系結構的核心是OSI模型國際標準化組織（ISO）提出的開放系統(tǒng)互聯參考模型（OSI）已成為網絡體系結構的標準在這些層中，除了最高的第7層沒有需要服務的上一層、最低的第1層沒有可利用服務的下一層外，其它的每一層都建立在下一層的基礎上，利用下一層來實現自己的功能，并向上一級提供服務。主機A與主機B進行通信時，通信協(xié)議是在對等層之間進行的。其中，物理層與物理層之間的通信協(xié)議是直接的，其他對等層之間的通信協(xié)議都是間接的。3、Internet網絡地址(IP地址)A類網絡為大型網絡；B類網絡為中型網絡；C類網絡為小型網絡。這三類網絡的地址特征為⑴A類網絡以0開頭，網絡號碼是7位，主機號碼是24位⑵B類網絡以10開頭，網絡號碼是14位，主機號碼是16位⑶C類網絡以110開頭，C類網絡的網絡號碼是21位，主機號碼是8位D類地址以1110開頭，E類地址以11110開頭。八、邏輯運算：與/\、或：\/,運算優(yōu)先級：/\>\/①假設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的結果是：（）。(NOIP8)A）30HB）05HC）35HD）53HAC

九、其他

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

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

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

A.奇數B.偶數C.可奇可偶D.數目固定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信息學競賽中的數學知識從n個不同元素中,任取m個元素,按照一定的順序排成一列,叫做從n個不同元素中取出m個元素的一個排列.2.組合的定義:從n個不同元素中,任取m個元素,并成一組,叫做從n個不同元素中取出m個元素的一個組合.3.排列數公式:4.組合數公式:1.排列的定義:排列與組合的區(qū)別與聯系:與順序有關的為排列問題,與順序無關的為組合問題.加法原理和乘法原理從A到C共有多少中走法？ABC例1

學校師生合影，共8個學生，4個老師，要求老師在學生中間，且老師互不相鄰，共有多少種不同的合影方式？解先排學生共有種排法,然后把老師插入學生之間的空檔，共有7個空檔可插,選其中的4個空檔,共有種選法.根據乘法原理,共有的不同坐法為種.結論1插入法:對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.分析此題涉及到的是不相鄰問題,并且是對老師有特殊的要求,因此老師是特殊元素,在解決時就要特殊對待.所涉及問題是排列問題.例25個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法?

解

因為女生要排在一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有種排法,其中女生內部也有種排法,根據乘法原理,共有種不同的排法.結論2捆綁法:要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內部也可以作排列.分析此題涉及到的是排隊問題,對于女生有特殊的限制,因