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

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

2、正是這篇文章，為圖靈贏得了“人工智能之父”的桂冠。與計(jì)算機(jī)有關(guān)的最高獎(jiǎng)項(xiàng)“圖靈獎(jiǎng)”。2、與競(jìng)賽有關(guān)的知識(shí)：A：信息學(xué)奧賽相關(guān)的軟件有：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、與計(jì)算機(jī)系統(tǒng)相關(guān)的知識(shí)：A：常見的操作系統(tǒng)有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、LINUX、B：C：D：E：F：G：4、與計(jì)算機(jī)軟件相關(guān)的知識(shí)：5、與計(jì)算機(jī)硬件相關(guān)的

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

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

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

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

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

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

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

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

11、0、1、2、3、4、5、6、7共8個(gè)數(shù)字符號(hào)組成。相同數(shù)字符號(hào)在不同的數(shù)位上表示不同的數(shù)值，每個(gè)數(shù)位計(jì)滿八就向高位進(jìn)一，即“逢八進(jìn)一”。 一個(gè)任意的十進(jìn)制數(shù)都可以表示成：C：二進(jìn)制二進(jìn)制計(jì)數(shù)制由0和1共2個(gè)數(shù)字符號(hào)組成。相同數(shù)字符號(hào)在不同的數(shù)位上表示不同的數(shù)值，每個(gè)數(shù)位計(jì)滿二就向高位進(jìn)一，即“逢二進(jìn)一”。 一個(gè)任意的二進(jìn)制數(shù)都可以表示成：D：其他進(jìn)制在日常生活和日常工作中還使用其他進(jìn)制數(shù)如：十二進(jìn)制數(shù)、十六進(jìn)制數(shù)、百進(jìn)制數(shù)和千進(jìn)制數(shù)等。無論哪種進(jìn)制數(shù)，表示的方法都是類似的。如：十六進(jìn)制數(shù)由0、1、2、3、4、5、6、7、8、9、A、B、C、D、E和F共十六個(gè)符號(hào)組成，“逢十六進(jìn)一”。不同的是用

12、A、B、C、D、E和F分別表示10、11、12、13、14和15六個(gè)數(shù)字符號(hào)。E：基數(shù)與權(quán)某進(jìn)制計(jì)數(shù)制允許選用的基本數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)。一般而言，J進(jìn)制數(shù)的基數(shù)為J，可供選用的基本數(shù)字符號(hào)有J個(gè)，分別為0到J1，每個(gè)數(shù)位計(jì)滿J就向高位進(jìn)一，即“逢J進(jìn)一”。某進(jìn)制計(jì)數(shù)制中各位數(shù)字符號(hào)所表示的數(shù)值表示該數(shù)字符號(hào)值乘以一個(gè)與數(shù)字符號(hào)有關(guān)的常數(shù)，該常數(shù)稱為“位權(quán)”（簡(jiǎn)稱“權(quán)”）。位權(quán)的大小是以基數(shù)為底，數(shù)字符號(hào)所處的位置的序號(hào)為指數(shù)的整數(shù)次冪。十進(jìn)制數(shù)允許使用十個(gè)基本數(shù)字符號(hào)，所以基數(shù)為10，每位數(shù)字符號(hào)代表的位數(shù)的大小是以10為底，數(shù)字符號(hào)所處位置的序號(hào)為指數(shù)的整數(shù)次冪。 F：數(shù)的表示：為了表達(dá)

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

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