信息學奧賽NOIP初賽復習知識點_第1頁
信息學奧賽NOIP初賽復習知識點_第2頁
信息學奧賽NOIP初賽復習知識點_第3頁
信息學奧賽NOIP初賽復習知識點_第4頁
信息學奧賽NOIP初賽復習知識點_第5頁
已閱讀5頁,還剩1頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

信息學奧賽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ù)轉

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論