信息學(xué)奧賽NOIP初賽復(fù)習(xí)知識點

1、信息學(xué)奧賽NOIP初賽復(fù)習(xí)知識點1計算機相關(guān)科學(xué)家：A :被西方人譽為計算機之父”的美籍匈牙利科學(xué)家、數(shù)學(xué)家馮諾依曼于1945年發(fā)表了一個 全新的”存儲程序通用電子計算機方案"一EDVAC 。 EDVAC方案提出了著名的 “馮諾依曼體系結(jié)構(gòu)理論：（1）采用二進制形式表示數(shù)據(jù)和指令（2）采用存儲程序方式（3）由運算器、存儲器、控制器、輸 入設(shè)備和輸出設(shè)備五大部件組成計算機系統(tǒng)B :圖靈機”與馮諾伊曼機齊名，被永遠載入計算機的發(fā)展史中。 1950年10月，圖靈又發(fā)表了另 一篇題為 機器能思考嗎”的論文，成為劃時代之作。也正是這篇文章，為圖靈贏得了 人工智能之父”的桂冠。 與計算機有關(guān)的最

2、高獎項“圖靈獎” 。2、與競賽有關(guān)的知識：A :信息學(xué)奧賽相關(guān)的軟件有：版；Red Hat 9.0 自帶了 版；版；free pascal 編譯器 版；gdb 6.3 版；RHIDE （ turbo pascal 淘汰）3、與計算機系統(tǒng)相關(guān)的知識：A :常見的操作系統(tǒng)有： DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、 LINUX、VISTA4、與計算機軟件相關(guān)的知識：無5、與計算機硬件相關(guān)的知識：A:斷電后能保存信息的有：ROM （只讀存儲器）、硬盤、軟盤、光盤、U盤、MP3、MP4等；不能保存的主要是RAM （讀寫存儲器）。B: C

3、PU又名中央處理器，它可以拆分成運算器、控制器中央蟲上理器儺盤 畫牛卒統(tǒng)L品示聖扌丁印機vj- 坯 in.攝作系饒救揖恵蘭理系統(tǒng)1I.叵Z,用f呈.號應(yīng)z用軟件i 工具裡序1其他6、病毒及防火墻：A :防火墻的作用是防止黑客攻擊。7、與編程語言相關(guān)的知識：A : 1972年P(guān)ARC發(fā)布了 Smalltalk的第一個版本。大約在此時，面向?qū)ο蟆边@一術(shù)語正式確定。Smalltalk被認為是第一個真正面向?qū)ο蟮恼Z言B :第一代語言：機器語言（0101001 ）；第二代語言：20世紀(jì)50年代，匯編語言，第三代語言： 高級語言、算法語言，女口 BASIC , FORTRAN , COBOL , PASC

4、AL , C;高級語言的特點是 可讀性強，編程方便；第四代語言：非過程化語言；SQL ;第五代語言：智能性語言,PROLOG （代表）；還有：LISP ,APL , SNOBOL , SIMULA。C:編程時讀入一個很大的二維數(shù)組，按行讀和按列讀相比，輸入效率上（取決于數(shù)組的存儲方式）。&計算機算法知識：A :算法特點：算法的改進，在很大程度上推動了計算機科學(xué)與技術(shù)的進步；判斷一個算法的好壞 的主要標(biāo)準(zhǔn)是算法的時間復(fù)雜性與空間復(fù)雜性；目前仍然存在許多涉及到國計民生的重大課題，還沒有找 到能夠在計算機上實施的有效算法；B :采用比較為主要操作的算法是：冒泡、插入、選擇排序9、函數(shù)或表達式

5、：A : PASCAL語言中，表達式（21 XOR 2 ）的值是（23）B : PASCAL語言，判斷a不等于0且b不等于0的正確的條件表達式是（a<>0）and（b<>0）10、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)：A :棧的出入順序是先進后出，隊列是先進先出；例如：某個車站呈狹長形，寬度只能容下一臺車， 并且出入口是一個。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為："進、出、進、進、進、出、出、進、進、出、出”。假設(shè)車輛入站的順序為 1，2，3，4，5，6，7則車輛出站的順序為（1，4, 3，7, 6）。B :高度為N的均衡的二叉樹是：如果去掉葉結(jié)點及相應(yīng)的樹枝， 它應(yīng)

6、該是高度為 N-1的滿二叉樹。 在這里，樹高等于葉結(jié)點的最大深度，根結(jié)點的深度為0,如果某個均衡的二叉樹共有 2381個結(jié)點，則該樹的樹高為（11）。C:（ 1）結(jié)點的度：一個結(jié)點的子樹數(shù)目稱為該結(jié)點的度（區(qū)分圖中結(jié)點的度）。圖中，結(jié)點i度為3，結(jié)點t的度為2，結(jié)點b的度為1。顯然，所有樹葉的度為 0。（2）樹的度：所有結(jié)點中最大的度稱為 該樹的度（寬度）。（3）樹的深度（高度）：樹是分層次的。結(jié)點所在的層次是從根算起的。根結(jié)點在第一 層，根的兒子在第二層，其余各層依次類推。圖中的樹共有五層。在樹中，父結(jié)點在同一層的所有結(jié)點構(gòu) 成兄弟關(guān)系。樹中最大的層次稱為樹的深度，亦稱高度。D :樹的表示除

7、自然界的樹形表示法 外（畫圖）還有 括號表示法：先將根結(jié)點放入一對圓括號中， 然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結(jié)點用 圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如圖可寫成如下形式（r（a（w，x（d（h），e），b（ f），c（ s，t（ i（ m，o，n ），j ），u）E:二叉樹的遞歸定義和基本形態(tài)：二叉樹是以結(jié)點為元素的有限集，它或者為空，或者滿足以下 條件：有一個特定的結(jié)點稱為根；余下的結(jié)點分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；F :二叉樹的兩個特殊形態(tài)：滿二叉樹：若深度為

8、K的二叉樹，共有2K-1個結(jié)點，即第I層有2I-1的結(jié)點，稱為滿二叉樹。完全二叉樹：如果一棵二叉樹最多只有最下面兩層結(jié)點度數(shù)可以小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹G :二叉樹的三個主要性質(zhì)：性質(zhì)1:在二叉樹的第i O 1）層上，最多有2i-1個結(jié)點 性質(zhì)2：在深度為k（k > 1）的二叉樹中最多有 2k-1個結(jié)點。性質(zhì)3:在任何二叉樹中，葉子結(jié)點數(shù)總比度為2的結(jié)點多1。n0=n2+1H :二叉樹的遍歷是不重復(fù)地訪問二叉樹中的每一個結(jié)點。在訪問到每個結(jié)點時，可以取出結(jié)點中 的信息，或?qū)Y(jié)點作其它的處理。如果用L、D、R分別表示遍歷左子樹、訪

9、問根結(jié)點、遍歷右子樹，限定先左后右的次序，三種組合DLR、LDR、 LRD ;這三種遍歷規(guī)則分別稱為先（前）序遍歷、中序遍歷和后序遍歷（以根為標(biāo)準(zhǔn)）。樣題：1、給出一棵二叉樹的先序遍歷：ABCDEFGH中序遍歷：CBEDAGHF并寫出后序遍歷結(jié)果。2、已知一棵二叉樹，其中序與后序遍歷為：中 序遍 歷:CBGEAFHDIJ 后序遍歷：CGEBHFJIDA 求先序前序遍歷前序遍歷的規(guī)則如下：若二叉樹為空，則退出。否則訪問處理根結(jié)點；前序遍歷左子樹；前序遍歷右子樹；a b d e h i c f g中序遍歷中序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則中序遍歷左子樹；訪問處理根結(jié)點；中序遍歷右子樹；

10、若中序遍歷上圖中的二叉樹，可以得到如下的中序序列：d b h e i a f c g后序遍歷后序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則后序遍歷左子樹；后序遍歷右子樹；訪問處理根結(jié)點；若后序遍歷上圖中的二叉樹，可以得到如下的后序序列d h i e b f g c a11、進制相關(guān)知識：見 小冊子2日備份 網(wǎng)站A : *進位計數(shù)制的基本概念將數(shù)字符號按序排列成數(shù)位，并遵照某種由低位到高位的進位方式計數(shù)表示數(shù)值的方法，稱作進位計數(shù)制。1.十進制十進制計數(shù)制由0、1、2、3、4、5、6、7、8、9共10個數(shù)字符號組成。相同數(shù)字符號 在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿十就向高位進一，即“逢十

11、進K.+.K覘一 KjKf. -KmlOj XX1 Qi+ KoX10°+K.jX104+ K,2 X1Q汪.+1(.詢次10*1代魁 ><10卞式中Kj (I=-叫/,丄0,1,2為0-9十個數(shù)字符號中的1仁B :八進制八進制計數(shù)制由0、1、2、3、4、5、6、7共8個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示 不同的數(shù)值，每個數(shù)位計滿八就向高位進一，即“逢八進一”。一個任意的十進制數(shù)都可以表示成：X +XX +K .：1 X 宙4K 吃 乂宙4+K 一曲 Xg*啊求皿 X 呂=丈心=即 式中口 < 1=一他.-2,丄0小)為0&八個數(shù)字符號中的一個-

12、i-nC :二進制二進制計數(shù)制由0和1共2個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù) 位計滿二就向高位進一，即“逢二進一”。 一個任意的二進制數(shù)都可以表示成：=KmX 27Kz x2ftl+.4Kj x2l+K0 x2° + Kx 2K .2 x2'. ,+K,1 x2 +1-HCx2*hl式中Kj( I=-呱,2丄0,1為0和1兩個數(shù)字符號中的一個-j4ftD :其他進制在日常生活和日常工作中還使用其他進制數(shù)如：十二進制數(shù)、十六進制數(shù)、百進制數(shù)和千進制數(shù)等。無論哪種進制數(shù)，表示的方法都是類似的。如：十六進制數(shù)由0、1、2、3、4、5、6、7、&

13、9、A B、C、D E和F共十六個符號組成，“逢十六進一”。不同的是用A、B、CD E和F分別表示10、11、12、13、14和15六個數(shù)字符號。E:基數(shù)與權(quán)某進制計數(shù)制允許選用的基本數(shù)字符號的個數(shù)稱為基數(shù)。一般而言，J進制數(shù)的基數(shù)為 J，可供選用的基本數(shù)字符號有 J個，分別為0到J 1，每個數(shù)位計滿J就向高位進一，即“逢 J進一”。某進制計數(shù)制中各位數(shù)字符號所表示的數(shù)值表示該數(shù)字符號值乘以一個與數(shù)字符號有關(guān)的常數(shù)，該常 數(shù)稱為“位權(quán)”（簡稱“權(quán)”）。位權(quán)的大小是以基數(shù)為底，數(shù)字符號所處的位置的序號為指數(shù)的整數(shù)次 幕。十進制數(shù)允許使用十個基本數(shù)字符號，所以基數(shù)為10,每位數(shù)字符號代表的位數(shù)的大

14、小是以10為底，數(shù)字符號所處位置的序號為指數(shù)的整數(shù)次幕。F:數(shù)的表示：為了表達方便起見，常在數(shù)字后加一縮寫字母后綴作為不同進制數(shù)的標(biāo)識。各種進 制數(shù)的后綴字母分別為：B:二進制數(shù)。Q:八進制數(shù)。D:十進制數(shù)。H:十六進制數(shù)。對于十進制數(shù)通常不加后綴，也即十進制數(shù)后的字母D可省略。G:進制轉(zhuǎn)換： 將其他進制轉(zhuǎn)換成10進制：“按權(quán)展開求和”如：(1011.01) 2 = ( 1 X 0X 23+ 1 X 21+ 1 X ?-F0X 2-1+ 1 X 2_3 ) w =(8+ 0+24-1 + 0+0.25) io=(11*25) iq將十進制轉(zhuǎn)換成二進制：對于整數(shù)部分，用被除數(shù)反復(fù)除以 2，除第一

15、次外，每次除以 2均取前一次商的整數(shù)部分作被除數(shù)并依次記下每次的余數(shù)。另外，所得到的商的最后一位余數(shù)是所求二進制數(shù)的最 高位。對于小數(shù)部分，采用連續(xù)乘以基數(shù)2，并依次取出的整數(shù)部分，直至結(jié)果的小數(shù)部分為0為止。故該例：將十進制117.625D轉(zhuǎn)換成二進制數(shù)221175®122902141270231211法稱“乘基取整法”。0 1小數(shù)部分：“乘以2取整，順序輸出”解：整數(shù)部分：“除以2取余，逆序輸出嶺 < 攝低位）0I.S251.2501C ki星高位O'252050<*»* 00 52LO1C最低仗:J所以 117.625D = 1110101.101

16、B將二進制數(shù)轉(zhuǎn)換為對應(yīng)的八進制數(shù)由于1位八進制數(shù)對應(yīng) 3位二進制數(shù)，所以二進制數(shù)轉(zhuǎn)換成八進制數(shù)時，只要以小數(shù)點為界，整數(shù)部 分向左，小數(shù)部分向右每3位分成一組，各組用對應(yīng)的1位八進制數(shù)字表示，即可得到對應(yīng)的八進制數(shù)值。 最左最右端分組不足 3位時，可用0補足。例：將1101101.10101B轉(zhuǎn)換成對應(yīng)的八進制數(shù)。解：二進制數(shù)：001 101 101.101 010八進制數(shù)：155.52所以，1101101.10101B = 155.52Q。同理，用相反的方法可以將八進制數(shù)轉(zhuǎn)換成對應(yīng)的二進制數(shù)。例：將八進制的37.416轉(zhuǎn)換成二進制數(shù)：37,416on in , too ooi no即:(37

17、416) 8 = (11111.lOOOOim 2例:將二進制tfi 101W.0011轉(zhuǎn)換成八進制:010 110.00110026 .14即：(10110.0115 2 = (26.14) g將二進制數(shù)轉(zhuǎn)為對應(yīng)的十六進制數(shù)由于1位十六進制數(shù)對應(yīng) 4位二進制數(shù)，所以二進制數(shù)轉(zhuǎn)換為十六進制時，只要以小數(shù)點為界，整數(shù) 部分向左，小數(shù)部分向右每4位分成一組，各組用對應(yīng)的1位十六進制數(shù)字表示，即可得到對應(yīng)的十六進制數(shù)值。兩端的分組不足4位時，用0補足。例：將1101101.10101B轉(zhuǎn)換成對應(yīng)的十六進制數(shù)二進制數(shù)：0110 1101 1010100LL解：.：.所以 1101101.10101B = 6D.8AH。同理，用相反的方法可以將十六進制數(shù)轉(zhuǎn)換成對應(yīng)的二進制數(shù)。 將十六進制數(shù)5DF.9轉(zhuǎn)換成二進制：5