信息學奧賽NOIP初賽復習知識點

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

2、關的最高獎項“圖靈獎”。2、與競賽有關的知識：A：信息學奧賽相關的軟件有：anjuta1.2.2版；RedHat9.0自帶了gcc/g+3.2.2版；Lazarus0.9.10版；freepascal編譯器2.0.1版；gdb6.3版；RHIDE;（turbopascal淘汰）3、與計算機系統(tǒng)相關的知識：A:常見的操作系統(tǒng)有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、LINUX、VISTA4、與計算機軟件相關的知識：無5、與計算機硬件相關的知識：A:斷電后能保存信息的有：ROM（只讀存儲器）、硬盤、軟盤、光盤、U盤、MP3、MP4等

3、；不能保存的主要是RAM（讀寫存儲器）。B:CPU又名中央處理器，它可以拆分成運算器、控制器中央處理器恰互利L存他5部1只法存儲熬蟀4J1.外昌跖殳備擇作不繞一清吉處理程序翼t挺屋管理系統(tǒng)上電一ft且鋌維其他L顯示器打印機其他車-需碓國汽盅棄他I.丘國手呈應用欽f牛j工具程J希1其他6、病毒及防火墻：A:防火墻的作用是防止黑客攻擊。7、與編程語言相關的知識：A：1972年PARC發(fā)布了Smalltalk的第一個版本。大約在此時，面向對象”這一術語正式確定。Smalltalk被認為是第一個真正面向對象的語言B:第一代語言：機器語言（0101001）;第二代語言：20世紀50年代，匯編語言，第三代

4、語言：高級語言、算法語言，如BASIC,FORTRAN,COBOL,PASCAL,C;高級語言的特點是可讀性強，編程方便；第四代語言：非過程化語言；SQL;第五代語言：智能性語言，PROLOG（代表）；還有：LISP,APL,SNOBOL,SIMULA。學習好資料歡迎下載C:編程時讀入一個很大的二維數組，按行讀和按列讀相比，輸入效率上(取決于數組的存儲方式)。8、計算機算法知識：A:算法特點：算法的改進，在很大程度上推動了計算機科學與技術的進步；判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性；目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法；B:采用

5、比較為主要操作的算法是：冒泡、插入、選擇排序9、函數或表達式：A:PASCAL語言中，表達式(21XOR2)的值是(23)B：PASCAL語言，判斷a不等于0且b不等于0的正確的條件表達式是(a<>0)and(b<>0)10、數據結構基礎：A:棧的出入順序是先進后出，隊列是先進先出；例如：某個車站呈狹長形，寬度只能容下一臺車，并且出入口是一個。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進、出、進、進、進、出、出、進、進、出、出”。假設車輛入站的順序為1,2,3,4,5,6,7則車輛出站的順序為(1,4,3,7,6)。B:高度為N的均衡的二叉樹是：如果去掉葉

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

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

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

9、后右的次序，三種組合DLR、LDR、LRD;這三種遍歷規(guī)則分別稱為先(前)序遍歷、中序遍歷和后序遍歷(以根為標準)。學習好資料歡迎下載前序遍歷前序遍歷的規(guī)則如下：若二叉樹為空，則退出。否則訪問處理根結點；前序遍歷左子樹；前序遍歷右子樹；abdehicfg中序遍歷中序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則中序遍歷左子樹；訪問處理根結點；中序遍歷右子樹；若中序遍歷上圖中的二叉樹，可以得到如下的中序序列：dbheiafcg后序遍歷樣題：1、給出一棵二叉樹的先序遍歷：ABCDEFGH中序遍歷：CBEDAGHF并寫出后序遍歷結果。2、已知一棵二叉樹，其中序與后序遍歷為：中序遍歷:CBGEAFHDIJ

10、后序遍歷：CGEBHFJIDA求先序后序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則后序遍歷左子樹；后序遍歷右子樹；訪問處理根結點；若后序遍歷上圖中的二叉樹，可以得到如下的后序序列dhiebfgca11、進制相關知識：見小冊子2日備份網站noi10-3.asp.htmlA：*進位計數制的基本概念將數字符號按序排列成數位，并遵照某種由低位到高位的進位方式計數表示數值的方法，稱作進位計數制。1.十進制十進制計數制由0、1、2、3、4、5、6、7、8、9共10個數字符號組成。相同數字符號在不同的數位上表示不同的數值，每個數位計滿十就向高位進一，即“逢十進一”。K潑3tlK.iK,?.乙同=K>X

11、1D4Kb1XX1Qi+KoX100+K4X104+K,2XW'4X10=VKixlOi式中/（>-網廠Z口Jj）為09十個數字符號中的一個。B:八進制八進制計數制由0、1、2、3、4、5、6、7共8個數字符號組成。相同數字符號在不同的數位上表示不同的數值，每個數位計滿八就向高位進一，即“逢八進一”。一個任意的十進制數都可以表示成：=K1kxM葉XXX20+K.：1Xm+K一11cH玄區(qū)位+1在海X8=天區(qū)產泮式中（1=一爪”2,-1,口,7）為08八個數字符號中的一個口i-nC:二進制二進制計數制由0和1共2個數字符號組成。相同數字符號在不同的數位上表示不同的數值，每個數位計滿

12、二就向高位進一，即“逢二進一”。一個任意的二進制數都可以表示成：學習好資料歡迎下載KjJC1tl.IC-ifC-j一一1GHEC1a=K1tX2K*ix2ftl+.,4Kjx2l+K0x2°+Kx2K.2x2,斗+K.M1*2g+l4Kgx2hl=ZKixK式中KJI=-g丁2丁1月,1g）為口和1兩個數字符號中的一個口D:其他進制在日常生活和日常工作中還使用其他進制數如：十二進制數、十六進制數、百進制數和千進制數等。無論哪種進制數，表示的方法都是類似的。如：十六進制數由0、1、2、3、4、5、6、7、8、9、AB、C、DE和F共十六個符號組成，“逢十六進一”。不同的是用A、B、CD

13、E和F分別表示10、11、12、13、14和15六個數字符號。E:基數與權某進制計數制允許選用的基本數字符號的個數稱為基數。一般而言，J進制數的基數為J,可供選用的基本數字符號有J個，分別為0到J1,每個數位計滿J就向高位進一，即“逢J進一”。某進制計數制中各位數字符號所表示的數值表示該數字符號值乘以一個與數字符號有關的常數，該常數稱為“位權”(簡稱“權”)。位權的大小是以基數為底，數字符號所處的位置的序號為指數的整數次哥。十進制數允許使用十個基本數字符號，所以基數為10,每位數字符號代表的位數的大小是以10為底，數字符號所處位置的序號為指數的整數次哥。F:數的表示：為了表達方便起見，常在數字

14、后加一縮寫字母后綴作為不同進制數的標識。各種進制數的后綴字母分別為：B:二進制數。Q:八進制數。D:十進制數。H:十六進制數。對于十進制數通常不加后綴，也即十進制數后的字母D可省略。G:進制轉換：將其他進制轉換成10進制：“按權展開求和”如：(1011.01)2=(1XOX23+1X21+1X?-F0X2-1+1X2-3)w=(8+0+2+1+0+0.25)10=(11.25)io將十進制轉換成二進制：對于整數部分，用被除數反復除以2,除第一次外，每次除以2均取前一次商的整數部分作被除數并依次記下每次的余數。另外，所得到的商的最后一位余數是所求二進制數的最高位。對于小數部分，采用連續(xù)乘以基數2

15、,并依次取出的整數部分，直至結果的小數部分為0為止。故該法稱“乘基取整法”。例：將十進制117.625D轉換成二進制數解：整數部分：“除以2取余，逆序輸出”2211了581&最低位)2290h2141270處231匕211小數部分01“乘以2取整，順序輸出”k(最高位)學習好資料歡迎下載0I,S251 2501t%最高位>025“32050一0t%*0521.01(L最低位:>所以117.625D=1110101.101B將二進制數轉換為對應的八進制數由于1位八進制數對應3位二進制數，所以二進制數轉換成八進制數時，只要以小數點為界，整數部分向左，小數部分向右每3位分成一組，

16、各組用應的1位八進制數字表示，即可得到對應的八進制數值。最左最右端分組不足3位時，可用0補足。例：將1101101.10101B轉換成對應的八進制數。解：二進制數：001101101.101010八迸制數：155.52所以，1101101.10101B=155.52Q。同理，用相反的方法可以將八進制數轉換成對應的二進制數。例：將八進制的笫.416轉換成二進制數：37,416onin,tooooino即：(37416)8=(11111.lOOOOim2例：將二進制的10110.0011轉換成八也制：010110.0011002 6.14即：(10110.01152=(26.14)s將二進制數轉為對應的十六進制數由于1位十六進制數對應4位二進制數，所以二進制數轉換為十六進制時，只要以小數點為界，整數部分向左，小數部分向右每4位分成一組，各組用對應的1位十六進制數字表示，即可得到對應的十六進制數值。兩端的分組不足4位時，用0補足。例：將1101101.10101B轉換成對應的十六進制數二進制數：011011011010100LL解：.一.丁制射：,.所以1101101.10101B=6D.8AHo同理，用相反的方法可以將十六進制數轉換成對應的二進制數。將十六進制數5DF.9轉換成二進制：5 DF