CSP初賽知識(shí)點(diǎn)復(fù)習(xí)

1、CSP-J/S第一輪（初賽）知識(shí)點(diǎn)精講NOF （全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽）于2019年取消。取而代之的是由CCF推出的非 專業(yè)級(jí)軟件能力認(rèn)證，也就是現(xiàn)在的CSP-J/SoCSP非專業(yè)級(jí)認(rèn)證的第一輪（也就是NO F 初賽）常常使某些大神對(duì)基礎(chǔ)知識(shí)不太了解無緣復(fù)賽所以今天學(xué)習(xí)下初賽知識(shí)點(diǎn)。信息學(xué)史及基本知識(shí)一、信息學(xué)及計(jì)算機(jī)史 計(jì)算機(jī)的頂級(jí)獎(jiǎng)項(xiàng)：圖靈獎(jiǎng)、馮諾依曼獎(jiǎng)圖靈獎(jiǎng)：由ACM （美國(guó)計(jì)算機(jī)協(xié)會(huì)）設(shè)立于1966年。是"計(jì)算機(jī)界的諾貝爾獎(jiǎng)”。馮諾依區(qū)獎(jiǎng)：由EEE設(shè)立。對(duì)信息科學(xué)做出突出貢獻(xiàn)的大神：圖靈（所以才有個(gè)獎(jiǎng)），馮諾伊顯中國(guó)獲圖靈獎(jiǎng)的大神：姚期智（清華就有姚班，就是以他的名字命

2、名的）世界第一臺(tái)電子計(jì)算機(jī)：埃尼阿克（EN/ACENEC）,于1946年2月14日在美國(guó) 賓夕法尼亞大學(xué)誕生。又被叫做電子管計(jì)算機(jī)。二、關(guān)于編程 編程語言：分兩類：面向?qū)ο蠛兔嫦蜻^程。 高級(jí)語言和低級(jí)語言的區(qū)別：高級(jí)語言需要編譯運(yùn)行，常數(shù)較大，運(yùn)行速度慢。而低級(jí)語言常數(shù)極小，運(yùn)行速度快。此外, 高級(jí)語言更容易移植。 常見低級(jí)語言：匯編 面向?qū)ο蟮母呒?jí)語言：C+, Java, EFFEL, Sin ub 67 等。 面向過程的高級(jí)語言：C， Fortran 語言。 遞歸編程：遞歸是指一種通過重復(fù)將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用 于解決很多的計(jì)算機(jī)科學(xué)問題，簡(jiǎn)單來講，就

3、是“自身調(diào)用自身”（在函數(shù)中）。P類/NP類/NPC類問題:1、P類問題：如果一個(gè)問題能找到一個(gè)在多項(xiàng)式時(shí)間內(nèi)解決它的算法，那么這個(gè)問題就是 P問題。2、NP類問題：注意：NP問題不是非P類問題，而是在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解的問題。 或者，我們可以將其理解為在多項(xiàng)式時(shí)間內(nèi)猜出一個(gè)解的問題°3、NPC類問題：定義如下：如果一個(gè)問題是NP問題，而且所有的NP問題都可以約化到 它。那么它就是NPC類問題。再來介紹一下關(guān)于約化的定義：如果一個(gè)問題A可以約化為 問題B,含義就是這個(gè)問題A可以用問題B的解法來解決.三、關(guān)于計(jì)算機(jī)先上張大圖:運(yùn)算器rcpu漱型計(jì)算機(jī)系統(tǒng)硬件系統(tǒng)主板存儲(chǔ)器機(jī)箱電源控

4、制器內(nèi)存儲(chǔ)只談存儲(chǔ)器（ROM）i隨機(jī)存儲(chǔ)器（眄）外存儲(chǔ)器硬盤、光盤、軟盤等）r箭人設(shè)備（鍵盤、鼠標(biāo)、掃描儀等）k輸入輸出設(shè)備，*，幼出設(shè)備（顯示器、打印機(jī)等）操作系統(tǒng)（DOS、Windows、UNIX、Linux 等）r機(jī)器洛吉港言處理程序 工編語言I 高級(jí)洛言（C、C+、Fortran、Pascal）I文字處理軟件（Microsoft Word、WPS等）I應(yīng)用軟件J表裕處理軟件（Microsoft Excel、金山表格等）輔助設(shè)計(jì)軟件（AutoCADs Master cam等）重要設(shè)備：硬件組成：控制器ConmD：是整個(gè)計(jì)算機(jī)的中樞神經(jīng)，其功能是對(duì)程序規(guī)定的控制信息進(jìn)行解釋, 根據(jù)其要求進(jìn)

5、行控制，調(diào)度程序、數(shù)據(jù)、地址，協(xié)調(diào)計(jì)算機(jī)各部分工作及內(nèi)存與外設(shè) 的訪問等。運(yùn)算器ID atapalh）：運(yùn)算器的功能是對(duì)數(shù)據(jù)進(jìn)行各種算術(shù)運(yùn)算和邏輯運(yùn)算，即對(duì)數(shù)據(jù)進(jìn) 行加工處理。存儲(chǔ)器Memory）:存儲(chǔ)器的功能是存儲(chǔ)程序、數(shù)據(jù)和各種信號(hào)、命令等信息，并在需要 時(shí)提供這些信息。輸入設(shè)備（hputsystem ）:輸入設(shè)備是計(jì)算機(jī)的重要組成部分，輸入設(shè)備與輸出設(shè)備合稱 為外部設(shè)備，簡(jiǎn)稱外設(shè)，輸入設(shè)備的作用是將程序、原始數(shù)據(jù)、文字、字符、控制命 令或現(xiàn)場(chǎng)采集的數(shù)據(jù)等信息輸入到計(jì)算機(jī)。常見的輸入設(shè)備有犍盤、鼠標(biāo)器、光電輸 入機(jī)、磁帶機(jī)、磁盤機(jī)、光盤機(jī)等。輸出設(shè)備（OuTputsystem ）輸出設(shè)備與

6、輸入設(shè)備同樣是計(jì)算機(jī)的重要組成部分，它把外 算機(jī)的中間結(jié)果或最后結(jié)果、機(jī)內(nèi)的各種數(shù)據(jù)符號(hào)及文字或各種控制信號(hào)等信息輸出 出來。微機(jī)常用的輸出設(shè)備有顯示終端CRT、打印機(jī)、激光印字機(jī)、繪圖儀及磁帶、 光盤機(jī)等。CPU及存儲(chǔ)：CPU （中央處理器）二運(yùn)算器+控制器+寄存器運(yùn)算器二算術(shù)邏輯運(yùn)算單元（ALU ）及浮點(diǎn)運(yùn)算單元（FPU）存儲(chǔ)器二內(nèi)存儲(chǔ)器+外存儲(chǔ)器B D S是英文空ask hputO ulputS ystem ”的縮略語，直譯過來后中文名稱就是“基本輸入輸 出系統(tǒng)。其實(shí)，它是一組固化到計(jì)算機(jī)內(nèi)主板上一個(gè)ROM芯片上的程序，它保存著計(jì)算 機(jī)最重要的基本輸入輸出的程序、系統(tǒng)設(shè)置信息、開機(jī)后自檢

7、程序和系統(tǒng)自啟動(dòng)程序。其 主要功能是為計(jì)算機(jī)提供最底層的、最直接的硬件設(shè)置和控制。隨機(jī)存儲(chǔ)器RAM的“隨機(jī)”指"隨時(shí)訪問"所以，我們記下來以下知識(shí)點(diǎn)：斷電后可以保存數(shù)據(jù)：硬盤，ROM斷電后不可以保存數(shù)據(jù)：顯存（顯卡內(nèi)存），RAM, CPU計(jì)算機(jī)各存儲(chǔ)單位及進(jìn)位關(guān)系：計(jì)算機(jī)的存儲(chǔ)單位有以下幾種：TB.GB.MB.KB.B他們之間的進(jìn)位關(guān)系為1024 （這應(yīng)該是常識(shí)，沒打過比賽還沒玩過手機(jī)么？）3特殊地，lB=8lbe,這里的bit是二進(jìn)制下的一位內(nèi)存。進(jìn)制及進(jìn)制轉(zhuǎn)化十進(jìn)制轉(zhuǎn)任意進(jìn)制將十進(jìn)制轉(zhuǎn)換成N進(jìn)制，只需把十進(jìn)制數(shù)每次除N求余數(shù)，然后把余數(shù)逆序?qū)懗鰜怼?看不懂就看圖：2 1

8、50 余數(shù)2 75 0 150/2商為7S,余0十進(jìn)制轉(zhuǎn)二進(jìn)制從展后一個(gè)余數(shù)讀到第一 小1 萬/2商為37.余11 37/2商為18余1，0聞2商為9, 余0 19/2商為4,余1-04/2高為2,余002/2商為1,余111/2商為0,余1150的二進(jìn)制數(shù)就是：10010110這是二進(jìn)制的圖，其他進(jìn)制就類比推一下就可以了。如果這個(gè)看不懂的話就不要參加初賽了, 50塊錢買點(diǎn)啥不好任意進(jìn)制轉(zhuǎn)十進(jìn)制簡(jiǎn)單說就是：按位轉(zhuǎn)，第i位的數(shù)字乘以要轉(zhuǎn)換的進(jìn)制的n-1次舞即可。還是上圖：4顧名思義：正數(shù)的反碼是本身，負(fù)數(shù)的反碼是其除符號(hào)位之外的所有位按位取反的結(jié)果。附：ASCII碼ASCII碼的正規(guī)名稱是：美國(guó)

9、信息交換標(biāo)準(zhǔn)代碼，是基于拉丁字母的一套電腦編碼系統(tǒng)。是 最通用的信息交換標(biāo)準(zhǔn)。一共定義了 128個(gè)字符。這里不賦A S C II碼的轉(zhuǎn)換表。只給出幾種比較常用的轉(zhuǎn)換：字符0-48大寫字母At65小寫字母a-97空格t32換行->13位運(yùn)算位運(yùn)算不僅在初賽中是一個(gè)知識(shí)點(diǎn)分類，在復(fù)賽（即真正的程序設(shè)計(jì)與運(yùn)用）的時(shí)候也有很 大的一個(gè)應(yīng)用。而且，位運(yùn)算的相關(guān)知識(shí)是計(jì)算機(jī)運(yùn)算的靈魂，更是每個(gè)程序猿應(yīng)該理解的 一種基本操作。關(guān)于位運(yùn)算的相關(guān)知識(shí)，本翦翦在另一篇專門的博客中詳細(xì)的講解。常用的位運(yùn)算技巧為了應(yīng)對(duì)初賽的筆試題，建議讀者在閱讀完這篇博客之后至少應(yīng)該掌握：各種位運(yùn)算的運(yùn)算 法則以及位運(yùn)算優(yōu)先級(jí)

10、。另外，對(duì)于位運(yùn)算的優(yōu)先級(jí)，本苗翦在后面的邏輯運(yùn)算部分還會(huì)有詳細(xì)的解析。邏輯運(yùn)算邏輯運(yùn)算邏輯運(yùn)算一共有三種，每種都有兩種寫法：邏輯非：！或1邏輯與：&&或八邏輯或：或V邏輯運(yùn)算的優(yōu)先級(jí)非與或位運(yùn)算+邏輯運(yùn)算的優(yōu)先級(jí)邏輯非(!,-)=按位反() 位移運(yùn)算(«,») 不等號(hào)(=,=) 等號(hào)(=,!=) 按位與(&) 按位異或按位或(|) 邏輯與(&&，八)邏輯或(II，v )邏輯表達(dá)式由邏輯運(yùn)算復(fù)合而成，只有兩種結(jié)果：mie和笈se,在C/C+中，返回的值以0表示假，以1表示真。條件表達(dá)式條件表達(dá)式的基本形式如下：表達(dá)式1?表達(dá)式2：表達(dá)

11、式3其表達(dá)意義是：如果表達(dá)式1成立，則執(zhí)行表達(dá)式2,否則執(zhí)行表達(dá)式3。其實(shí)也等價(jià)于if-ekeif-else條件語句。例如下：#define Min(azb) ab?a:b注意：如果條件表達(dá)式有多個(gè)進(jìn)行復(fù)合，那么在執(zhí)行的時(shí)候需要從由往左依次判斷最后得出 一個(gè)結(jié)果。即：右結(jié)合性。比如：表達(dá)式1?表達(dá)式2：表達(dá)式3?表達(dá)式4：表達(dá)式5那么，在執(zhí)行的時(shí)候是從3開始判斷是否為真.，然后執(zhí)行某一個(gè)表達(dá)式，依次向上回溯。圖論理論知識(shí)基本概念完全圖：任意兩點(diǎn)都有邊相連，我們很容易推出來，一張完全圖的邊數(shù)為(n為節(jié)點(diǎn)個(gè)數(shù))nx(n-1)2連通圖：顧名思義，連通圖就是連通的圖，即任意兩點(diǎn)都能直接或間接到達(dá)，這就

12、區(qū) 別于完全圖必須直接用邊到達(dá)的定義。樹：emm直觀來講，就是一張長(zhǎng)得像樹的圖，定義是任意兩點(diǎn)之間的簡(jiǎn)單路徑有且 只有一條。樹是一棵連通且無環(huán)的圖。它的邊數(shù)是二叉樹的遍歷二叉樹有不同的遍歷方式，一般來講，我們將其分成三類：先序遍歷（也叫先根遍歷）、中 序遍歷（中根遍歷）以及后序遍歷（后根遍歷）。先序遍歷：遍歷方式如下：根一左兒子一右兒子中序遍歷：遍歷方式如下：左兒子一根一右兒子后序遍歷：遍歷方式如下：左兒子一右兒子一根我們用一張圖來理解一下這幾種遍歷方式。這張圖的先序遍歷：1245367中序遍歷：4251637后序遍歷：4526731一個(gè)推論：先序遍歷+中序遍歷二一棵確定的二叉樹后序遍歷十中序

13、遍歷二一棵確定的二叉樹先序遍歷+后序遍歷二啥也不是特殊二叉樹及其性質(zhì) 完全二叉樹：只有最后一層不是滿的，且最后一層的所有節(jié)點(diǎn)均集中在左側(cè)。圖例如下： 滿二叉樹：節(jié)點(diǎn)個(gè)數(shù)已滿.圖例如下：9特殊二叉樹的性質(zhì):1、對(duì)于一棵完全二叉樹來講，它的葉子仔點(diǎn)為n,則節(jié)點(diǎn)總數(shù)為2xn-10此結(jié)論可逆。2、對(duì)于一棵滿二叉樹來講，它的層數(shù)（深度）為k,則它的節(jié)點(diǎn)總數(shù)為2k-1。此結(jié)論可逆。拓?fù)渑判?本黃疆有一篇專門講拓?fù)渑判虻闹v解: 拓?fù)渑判蛟斀夂?jiǎn)單數(shù)據(jù)結(jié)構(gòu)基本理論1、棧想象一個(gè)桶，你從上面往里扔磚，然后你想把某一塊磚拿出來，你需要先拿出來你后扔進(jìn)去 的磚。這就是棧。棧的基本原則是：后進(jìn)先出來一發(fā)圖示？1附；前、

14、中、后綴表達(dá)式一篇專門的博客：淺談前、中、后綴表達(dá)式2、隊(duì)列想象你在排隊(duì)買票，這個(gè)隊(duì)伍中的人都非常有素質(zhì)，都自覺排隊(duì)而且不會(huì)提前離開隊(duì)伍。這 樣就只能從隊(duì)首買完票再離開，從隊(duì)尾進(jìn)入隊(duì)伍。隊(duì)列的基本原則是：先進(jìn)先出。再來一發(fā)圖示：tail,出隊(duì)從head ,所 以一定滿足規(guī)律：先進(jìn) 先出！3、鏈表鏈表分兩種：?jiǎn)蜗蜴湵砗碗p向鏈表。關(guān)于鏈表，我有一篇專門講解的博客。有興趣的讀者請(qǐng) 戳：鏈表詳解4、字符串字符串子串的概念：字符串是一串字符（廢話），它的子串被定義為：字符串中任意個(gè)連續(xù) 的字符組成的子序列。字符串子串個(gè)數(shù)的計(jì)算公式:nX(n+l)2+l（就是字符串長(zhǎng)度等差數(shù)列）如果是非空子串，就把那個(gè)一

15、減去即可（子串個(gè)數(shù)的公式加一就是考慮空子串的情況）,時(shí)空復(fù)雜度的計(jì)算時(shí)間復(fù)雜度：漸進(jìn)時(shí)間復(fù)雜度用符號(hào)0表示。一個(gè)程序的語句執(zhí)行次數(shù)可以用一個(gè)代 數(shù)式表示，那么我們?nèi)∵@個(gè)代數(shù)式的最高次項(xiàng)且忽略此項(xiàng)系數(shù)作為時(shí)間復(fù)雜度。如果 一個(gè)程序的語句執(zhí)行次數(shù)為2n3+3n2+n+7,那么這個(gè)程序的漸進(jìn)時(shí)間復(fù)雜度為0 33）。計(jì)算非遞歸程序的時(shí)間復(fù)雜度：簡(jiǎn)單粗暴，數(shù)循環(huán)。常數(shù)：常數(shù)即為我們忽略掉的。0中最高次項(xiàng)的系數(shù)與低次項(xiàng)所帶來的時(shí)間消耗。空間復(fù)雜度：類比時(shí)間復(fù)雜度。看開空間開了多大。計(jì)算空間占用量：根據(jù)我們以上說過的計(jì)算機(jī)存儲(chǔ)單位的知識(shí)：一個(gè)iit占用的內(nèi)存是 4B,所以我們把開的iit乘上4,再除以1024就是KB,同理，再除1024就是MB。公式：n為元素個(gè)數(shù)，M為最終答案（以MB為單位）M=4nl024XL024PS:一般來講，比賽中所給的256MB內(nèi)存可以開6 M07個(gè)ht類型的變量。另外，大數(shù)組 必須開全局變量。如果扔在主函數(shù)里極容易爆棧。數(shù)學(xué)、邏輯學(xué)及運(yùn)籌學(xué)知識(shí)