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

信息學奧賽NOIP初賽復習知識點1、計算機相關科學家：A：被西方人譽為“計算機之父”的美籍匈牙利科學家、數(shù)學家馮?諾依曼于1945年發(fā)表了一個全新的”存儲程序通用電子計算機方案"一EDVAC。EDVAC方案提出了著名的“馮?諾依曼體系結構”理論：（1）采用二進制形式表示數(shù)據(jù)和指令（2）采用存儲程序方式（3）由運算器、存儲器、控制器、輸入設備和輸出設備五大部件組成計算機系統(tǒng)B：“圖靈機”與“馮?諾伊曼機”齊名，被永遠載入計算機的發(fā)展史中。1950年10月，圖靈又發(fā)表了另一篇題為“機器能思考嗎”的論文，成為劃時代之作。也正是這篇文章，為圖靈贏得了“人工智能之父”的桂冠。與計算機有關的最高獎項“圖靈獎”。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等；不能保存的主要是RAM（讀寫存儲器）。B：CPU又名中央處理器，它可以拆分成運算器、控制器硬件系統(tǒng)主機部分外部設備中央處理器一匚內(nèi)存儲器計算機——6、 病毒及防火A防火7、 與編程語言A：硬件系統(tǒng)主機部分外部設備中央處理器一匚內(nèi)存儲器計算機——6、 病毒及防火A防火7、 與編程語言A：197Smalltalk被認B：第-高級語言、算》輸入設備輸出設備輔助存儲器-:墻：〈墻的作用是防止黑客攻擊。-相關的知識：2年PARC發(fā)布了Smalltalk的第一個版本為是第一個真正面向?qū)ο蟮恼Z言

「代語言：機器語言（0101001）去語言，如BASIC,FO程方便；第四代語言:車非過程化語言；運算器控制器廠隨機存儲器L只讀存儲器—鼠標—鍵盤L其他—顯喬器—打印機L其他—軟盤—硬盤—TLiril匚其他。大約輕此此時，“面向?qū)ο蟆边@一術語正式確定。—吾言處理程序語言：20世紀50年僚，匯編語言，第三代語言：pascal，c；高級語言的特點是可讀性強，編SQL；第五代語言：智能性語言，PROLOG（代表）；還有：LISP,RTRAN，COBOL，APL,SNOBOLAPL,SNOBOL,SIMULAo應用軟件一一工具程序L其他C：編程時讀入一個很大的二維數(shù)組，按行讀和按列讀相比，輸入效率上（取決于數(shù)組的存儲方式）。8、計算機算法知識：A：算法特點：算法的改進，在很大程度上推動了計算機科學與技術的進步；判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性；目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法；B：采用比較為主要操作的算法是：冒泡、插入、選擇排序9、 函數(shù)或表達式：A：PASCAL語言中，表達式（21XOR2）的值是（23）B：PASCAL語言，判斷a不等于0且b不等于0的正確的條件表達式是（av>0）and（bv>0）10、 數(shù)據(jù)結構基礎：A：棧的出入順序是先進后出，隊列是先進先出；例如：某個車站呈狹長形，寬度只能容下一臺車,并且出入口是一個。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進、出、進、進、進、出、出、進、進、出、出”。假設車輛入站的順序為1，2，3，4，5，6，7則車輛出站的順序為（1，4，3，7，6）。B：高度為N的均衡的二叉樹是：如果去掉葉結點及相應的樹枝，它應該是高度為N-1的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為0，如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為（11）。C：（1）結點的度：一個結點的子樹數(shù)目稱為該結點的度（區(qū)分圖中結點的度）。圖中，結點i度為3,結點t的度為2,結點b的度為1。顯然，所有樹葉的度為0。（2）樹的度：所有結點中最大的度稱為該樹的度（寬度）。（3）樹的深度（高度）：樹是分層次的。結點所在的層次是從根算起的。根結點在第一層，根的兒子在第二層，其余各層依次類推。圖中的樹共有五層。在樹中，父結點在同一層的所有結點構成兄弟關系。樹中最大的層次稱為樹的深度，亦稱高度。D：樹的表示除自然界的樹形表示法外（畫圖）還有括號表示法：先將根結點放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如圖可寫成如下形式（（a（w,x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））E：二叉樹的遞歸定義和基本形態(tài)：二叉樹是以結點為元素的有限集，它或者為空，或者滿足以下條件：（1）有一個特定的結點稱為根；⑵余下的結點分為互不相交的子集L和R,其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；F：二叉樹的兩個特殊形態(tài)：⑴滿二叉樹：若深度為K的二叉樹，共有2K-1個結點，即第I層有21-1的結點，稱為滿二叉樹。⑵完全二叉樹：如果一棵二叉樹最多只有最下面兩層結點度數(shù)可以小于2,并且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹G：二叉樹的三個主要性質(zhì)：性質(zhì)1：在二叉樹的第i（三1）層上，最多有2i-1個結點性質(zhì)2：在深度為k（k21）的二叉樹中最多有2k-1個結點。性質(zhì)3：在任何二叉樹中，葉子結點數(shù)總比度為2的結點多1。n0=n2+1H：二叉樹的遍歷是不重復地訪問二叉樹中的每一個結點。在訪問到每個結點時，可以取出結點中的信息，或?qū)Y點作其它的處理。如果用L、D、R分別表示遍歷左子樹、訪問根結點、遍歷右子樹，限定先左后右的次序，三種組合DLR、LDR、LRD；這三種遍歷規(guī)則分別稱為先（前）序遍歷、中序遍歷和后序遍歷（以根為標準）。

樣d、?遍歷：CBEDAG2、已知一棵歷:CBGEAFHDIJ后序遍歷樣d、?遍歷：CBEDAG2、已知一棵歷:CBGEAFHDIJ后序遍歷:e樹的歷：ABCDEFGH中序序遍歷結果。并寫乞樹，其中序與后序遍歷為：中序遍EBHFJIDA求先序前序遍歷前序遍歷的規(guī)則如下：若二叉樹為空，則退出。否則⑴訪問處理根結點； ⑵前序遍歷左子樹； ⑶前序遍歷右子樹；abdehicfg中序遍歷中序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則⑴中序遍歷左子樹；⑵訪問處理根結點；⑶中序遍歷右子樹；若中序遍歷上圖中的二叉樹，可以得到如下的中序序列: dbheiafcg后序遍歷后序遍歷的規(guī)則如下：若二叉樹為空，則退出；否則⑴后序遍歷左子樹；⑵后序遍歷右子樹；⑶訪問處理根結點；若后序遍歷上圖中的二叉樹，可以得到如下的后序序列dhiebfgca11、進制相關知識：見G:\小冊子2日備份\網(wǎng)站\noi\10-3.asp.htmlA：*進位計數(shù)制的基本概念將數(shù)字符號按序排列成數(shù)位，并遵照某種由低位到高位的進位方式計數(shù)表示數(shù)值的方法，稱作進位計數(shù)制。1.十進制 十進制計數(shù)制由0、 1、 2、 3、 4、 5、 6、 7、 8、 9共10個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿十就向高位進一，即“逢十進一”。疋/辺…陷心心心…Ejm+lkm=^10^&1X10al+...-HCiX10T+KoX10°+K.!X104+K.2X10 10^+14K皿X1D說=^KixlOi式中叫（1=一皿...,2丄叩,..』）為。~9十個數(shù)字符號中的一仁i-iLB：八進制八進制計數(shù)制由0、1、2、3、4、5、6、7共8個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿八就向高位進一，即“逢八進一”。一個任意的十進制數(shù)都可以表示成：KJCjtl…ICKo.K-1K-2...IGjnfiKm.=KhX X即1+...4K1X魁+JC°X別+JC1X8-LFK.2><宙斗...+疋_迪X8^+1-4C皿X8^-m=2 式中（I=-氓…,2-1』丄…M為D5八平數(shù)字符號中的一仁i-nC:二進制二進制計數(shù)制由0和1共2個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿二就向高位進一，即“逢二進一”。一個任意的二進制數(shù)都可以表示成：11758117582914K-m+lKm=Kkx x2'^K.2x?i4-...+K.IirnX2^+1-HC皿x巧m=》齢找 式中陽(I=-氓…,2丄。丄…衛(wèi))為。和1兩個數(shù)字符號中的一個口D：其他進制在日常生活和日常工作中還使用其他進制數(shù)如：十二進制數(shù)、十六進制數(shù)、百進制數(shù)和千進制數(shù)等。無論哪種進制數(shù)，表示的方法都是類似的。如：十六進制數(shù)由0、1、2、3、4、5、6、7、8、9、A、B、C、D、E和F共十六個符號組成，“逢十六進一”。不同的是用A、B、C、D、E和F分別表示10、11、12、13、14和15六個數(shù)字符號。E：基數(shù)與權某進制計數(shù)制允許選用的基本數(shù)字符號的個數(shù)稱為基數(shù)。一般而言，J進制數(shù)的基數(shù)為J,可供選用的基本數(shù)字符號有J個，分別為0到J—1,每個數(shù)位計滿J就向高位進一，即“逢J進一”。某進制計數(shù)制中各位數(shù)字符號所表示的數(shù)值表示該數(shù)字符號值乘以一個與數(shù)字符號有關的常數(shù)，該常數(shù)稱為“位權”(簡稱“權”)。位權的大小是以基數(shù)為底，數(shù)字符號所處的位置的序號為指數(shù)的整數(shù)次冪。十進制數(shù)允許使用十個基本數(shù)字符號，所以基數(shù)為10，每位數(shù)字符號代表的位數(shù)的大小是以10為底，數(shù)字符號所處位置的序號為指數(shù)的整數(shù)次冪。F：數(shù)的表示：為了表達方便起見，常在數(shù)字后加一縮寫字母后綴作為不同進制數(shù)的標識。各種進制數(shù)的后綴字母分別為： B：二進制數(shù)。 Q：八進制數(shù)。 D：十進制數(shù)。 H：十六進制數(shù)。對于十進制數(shù)通常不加后綴，也即十進制數(shù)后的字母D可省略。G：進制轉換：將其他進制轉換成10進制：“按權展開求和”如：(1011.01)2=(1x?+0XP+1X21+1X?+0X2"1+1X2"2)山=(8+0+2+1+0+0.25)io=(11.25)iq將十進制轉換成二進制：對于整數(shù)部分，用被除數(shù)反復除以2,除第一次外，每次除以2均取前一次商的整數(shù)部分作被除數(shù)并依次記下每次的余數(shù)。另外，所得到的商的最后一位余數(shù)是所求二進制數(shù)的最高位。對于小數(shù)部分，采用連續(xù)乘以基數(shù)2，并依次取出的整數(shù)部分，直至結果的小數(shù)部分為0為止。故該法稱“乘基取整法”。例：將十進制117.625D轉換成二進制數(shù)解：整數(shù)部分：“除以2取余，逆序輸出”1 商(攝低位)0 kx1 k?1 ki1 b1 kt （攝高位）小數(shù)部分:“乘以2取整，順序輸出”0.62521.250 1 (ki攝高位)0.25x) 20.50 0 (k2J0.5所以117625花1110101.10輛將二進制數(shù)轉換為對應的八進制數(shù)由于1位八進制數(shù)對應3位二進制數(shù)，所以二進制數(shù)轉換成八進制數(shù)時，只要以小數(shù)點為界，整數(shù)部分向左，小數(shù)部分向右每3位分成一組，各組用對應的1位八進制數(shù)字表示，即可得到對應的八進制數(shù)值。最左最右端分組不足3位時，可用0補足。例：將1101101.10101B轉換成對應的八進制數(shù)。解：二進制數(shù)：001101101.101Q10八進制數(shù)：1 5 5.52所以，1101101.10101B=155.52Q。同理，用相反的方法可以將八進制數(shù)轉換成對應的二進制數(shù)。例孑將層進制的幼4花轉換成二進制數(shù)：3 7,416Oil111 ,1齟GQ1110’即：(37.416^8-(11111.10000111)洛例：將二進制的10110(011轉換成恥進制：010 110-.0心11如2修.1 4即：2=怠&14〕0將二進制數(shù)轉為對應的十六進制數(shù)由于1位十六進制數(shù)對應4位二進制數(shù)，所以二進制數(shù)轉換為十六進制時，只要以小數(shù)點為界，整數(shù)部分向左，小數(shù)部分向右每4位分成一組，各組用對應的1位十六進制數(shù)字表示，即可得到對應的十六進制數(shù)值。兩端的分組不足4位時，用0補足。例：將1101101.10101B轉換成對應的十六進制數(shù)二進制數(shù)：01101101■10101000解：所以1101101.10101B=6D.8AH。同理，用相反的方法可以將十六進制數(shù)轉