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

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

2、正是這篇文章，為圖靈贏得了“人工智能之父”的桂冠。與計算機有關的最高獎項“圖靈獎”。2、與競賽有關的知識：A：信息學奧賽相關的軟件有：anjuta 1.2.2版； Red Hat 9.0 自帶了gcc/g+ 3.2.2版； Lazarus 0.9.10版； free pascal編譯器2.0.1版； gdb 6.3版；RHIDE；（turbo pascal淘汰）B：C：D：3、與計算機系統(tǒng)相關的知識：A：常見的操作系統(tǒng)有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、LINUX、B：C：D：E：F：G：4、與計算機軟件相關的知識：5、與計算機硬件相關的

3、知識： A：斷電后能保存信息的有：ROM（只讀存儲器）、硬盤、軟盤、光盤、U盤、MP3、MP4等；不能保存的主要是RAM（讀寫存儲器）。B：CPU又名中央處理器，它可以拆分成運算器、控制器C：D：E：F：6、病毒及防火墻： A：防火墻的作用是防止黑客攻擊。B：C：D：E：F：7、與編程語言相關的知識： A：1972年PARC發(fā)布了Smalltalk的第一個版本。大約在此時，“面向?qū)ο蟆边@一術語正式確定。Smalltalk被認為是第一個真正面向?qū)ο蟮恼Z言B：第一代語言：機器語言（0101001）；第二代語言：20世紀50年代，匯編語言，第三代語言：高級語言、算法語言，如BASIC，F(xiàn)ORTRAN

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

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

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é)點構成兄弟關系。樹中最大的層次稱為樹的深度，亦稱高度。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)：滿二叉樹： 若深度為K的二叉樹，共有2K-1個結(jié)點，即第I層有2I-

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

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

10、 a f c g 后序遍歷后序遍歷的規(guī)則如下： 若二叉樹為空，則退出；否則后序遍歷左子樹；后序遍歷右子樹；訪問處理根結(jié)點； 若后序遍歷上圖中的二叉樹，可以得到如下的后序序列 d h i e b f g c a11、進制相關知識：見 G:小冊子2日備份網(wǎng)站noi10-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ù)位計滿十就向高位進一，即“逢十進一”。B：八進制八進制計數(shù)制由

11、0、1、2、3、4、5、6、7共8個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿八就向高位進一，即“逢八進一”。 一個任意的十進制數(shù)都可以表示成：C：二進制二進制計數(shù)制由0和1共2個數(shù)字符號組成。相同數(shù)字符號在不同的數(shù)位上表示不同的數(shù)值，每個數(shù)位計滿二就向高位進一，即“逢二進一”。 一個任意的二進制數(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共十六個符號組成，“逢十六進一”。不同的是用

12、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到J1，每個數(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ù)的表示：為了表達

13、方便起見，常在數(shù)字后加一縮寫字母后綴作為不同進制數(shù)的標識。各種進制數(shù)的后綴字母分別為：B：二進制數(shù)。Q：八進制數(shù)。D：十進制數(shù)。H：十六進制數(shù)。對于十進制數(shù)通常不加后綴，也即十進制數(shù)后的字母D可省略。 G：進制轉(zhuǎn)換： 將其他進制轉(zhuǎn)換成10 進制：“按權展開求和”如：將十進制轉(zhuǎn)換成二進制：對于整數(shù)部分，用被除數(shù)反復除以2，除第一次外，每次除以2均取前一次商的整數(shù)部分作被除數(shù)并依次記下每次的余數(shù)。另外，所得到的商的最后一位余數(shù)是所求二進制數(shù)的最高位。對于小數(shù)部分，采用連續(xù)乘以基數(shù)2，并依次取出的整數(shù)部分，直至結(jié)果的小數(shù)部分為0為止。故該法稱“乘基取整法”。例：將十進制117.625D轉(zhuǎn)換成二進制數(shù)

14、 解：整數(shù)部分：“除以2取余，逆序輸出”小數(shù)部分:“乘以2取整，順序輸出”所以117.625D1110101.101B將二進制數(shù)轉(zhuǎn)換為對應的八進制數(shù)由于1位八進制數(shù)對應3位二進制數(shù)，所以二進制數(shù)轉(zhuǎn)換成八進制數(shù)時，只要以小數(shù)點為界，整數(shù)部分向左，小數(shù)部分向右每3位分成一組，各組用對應的1位八進制數(shù)字表示，即可得到對應的八進制數(shù)值。最左最右端分組不足3位時，可用0補足。例：將1101101.10101B轉(zhuǎn)換成對應的八進制數(shù)。解：所以，1101101.10101B155.52Q。同理，用相反的方法可以將八進制數(shù)轉(zhuǎn)換成對應的二進制數(shù)。將二進制數(shù)轉(zhuǎn)為對應的十六進制數(shù)由于1位十六進制數(shù)對應4位二進制數(shù)，所以二進制數(shù)轉(zhuǎn)換為十六進制時，只要以小數(shù)點為界，整數(shù)部分向左，小數(shù)部分向右每4位分成一組，各組用對應的1位十六進制數(shù)字表示，即可得到對應的十六進制數(shù)值。兩端的分組不足4位時，用0補足。例：將1101101.10101B轉(zhuǎn)換成對應的十六進制數(shù)解：所以11