《二級(jí)公共基礎(chǔ)知識(shí)總結(jié)綱.doc》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《二級(jí)公共基礎(chǔ)知識(shí)總結(jié)綱.doc（42頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考綱考試內(nèi)容一、 基本數(shù)據(jù)結(jié)構(gòu)與算法1、算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。2、數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的概念。3、線(xiàn)性表的定義；線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5、線(xiàn)性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6、樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。7、順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序）。二、程序設(shè)計(jì)基礎(chǔ)1、程序設(shè)計(jì)方法與風(fēng)格。2

2、、結(jié)構(gòu)化程序設(shè)計(jì)。3、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1、軟件工程基本概念，軟件生命周戎概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。2、結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。3、結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4、軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。5、程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)1、數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。2、數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3、關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范

3、化理論。4、數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?？荚嚪绞剑汗不A(chǔ)的考試方式為筆試，與C語(yǔ)言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的筆試部分合為一張?jiān)嚲怼９不A(chǔ)部分占全卷的30分。公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題。第一章 數(shù)據(jù)結(jié)構(gòu)與算法一、內(nèi)容要點(diǎn)（一）算法1算法的基本概念：算法是指解題方案的準(zhǔn)確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，沒(méi)有二義性，同時(shí)該規(guī)則將在有限次運(yùn)算后可終止。2、算法的基本特征（1）可行性：由于算法的設(shè)計(jì)是為了在某一個(gè)特定的

4、計(jì)算工具上解決某一個(gè)實(shí)際的問(wèn)題而設(shè)計(jì)的，因此，它總是受到計(jì)算工具的限制，使執(zhí)行產(chǎn)生偏差。如：計(jì)算機(jī)的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進(jìn)行運(yùn)算時(shí)，往往會(huì)因?yàn)橛行粩?shù)的影響而使小數(shù)丟失，因此，在算法設(shè)計(jì)時(shí)，應(yīng)該考慮到這一點(diǎn)。（2）確定性：算法的設(shè)計(jì)必須是每一個(gè)步驟都有明確的定義，不允許有模糊的解釋?zhuān)膊荒苡卸嗔x性。例如，一個(gè)實(shí)際的問(wèn)題，小寶和萍萍共有12個(gè)蘋(píng)果，小寶比萍萍多4個(gè)，請(qǐng)問(wèn)小寶和萍萍各有幾個(gè)蘋(píng)果？這個(gè)問(wèn)題，我們可以立一個(gè)方程來(lái)求解，要求x和y的值，公式是正確的，但如何讓計(jì)算能夠進(jìn)行計(jì)算，我們的算法不能把公式直接輸進(jìn)去，而應(yīng)該設(shè)計(jì)出解題的步驟和過(guò)程。即設(shè)計(jì)的算法是計(jì)算工具所能夠正常解決問(wèn)題

5、的過(guò)程。（3）有窮性：算法的有窮性，即在一定的時(shí)間是能夠完成的，即算法應(yīng)該在計(jì)算有限個(gè)步驟后能夠正常結(jié)束。例如，在數(shù)學(xué)中的無(wú)窮級(jí)數(shù)，在計(jì)算機(jī)中只能求有限項(xiàng)，即計(jì)算的過(guò)程是有窮的。（4）擁有足夠的情報(bào)：算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)，不同的輸入或初始條件會(huì)有不同的輸出結(jié)果，提供準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。3、算法的基本要素：一是數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。（1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作：算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。即算法是計(jì)算機(jī)所能夠處理的操作所組成的指令序列。（2）算法的控制結(jié)構(gòu) 算法的功能不僅取決于

6、所選用的操作，而且還與各操作之間的順序有關(guān)。 在算法中，操作的執(zhí)行順序又稱(chēng)算法的控制結(jié)構(gòu)，一般的算法控制結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。 在算法描述是，有相關(guān)的工具對(duì)這三種結(jié)構(gòu)進(jìn)行描述，常用的描述工具有：流程圖、N-S結(jié)構(gòu)圖和算法描述語(yǔ)言等。4、算法設(shè)計(jì)的基本方法：為用計(jì)算機(jī)解決實(shí)際問(wèn)題而設(shè)計(jì)的算法，即是計(jì)算機(jī)算法。通常的算法設(shè)計(jì)有如下幾種：（1）列舉法：列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉出所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦菨M(mǎn)足條件的，哪些是不滿(mǎn)足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問(wèn)題。例如，我國(guó)古代的趣味數(shù)學(xué)題：“百錢(qián)買(mǎi)百雞”、“雞兔同籠”等

7、，均可采用列舉法進(jìn)行解決。 使用列舉法時(shí)，要對(duì)問(wèn)題進(jìn)行詳細(xì)的分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律。（2）歸納法：歸納法的基本思想是，通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對(duì)所有的情況進(jìn)行列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)行證明。（3）遞推：遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。例如，裴波那契數(shù)列，是采用遞推的方法解決問(wèn)題的。

8、（4）遞歸：在解決一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程序，通常是將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后的問(wèn)題那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的方法。遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱(chēng)為直接遞歸調(diào)用；如果一個(gè)算法A調(diào)用另一個(gè)算法B，而算法B又調(diào)用算法A，則此種遞歸稱(chēng)為間接遞歸調(diào)用。（5）減半遞推技術(shù)：減半遞推即將問(wèn)題的規(guī)模減半，然后，重復(fù)相同的遞推操作。如，一元二次方程求解。（6）回溯法：有些實(shí)際的問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀(guān)的求解步驟，也不能使用無(wú)限

9、的列舉。對(duì)于這類(lèi)問(wèn)題，只能采用試探的方法，通過(guò)對(duì)問(wèn)題的分析，找出解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索進(jìn)行試探，如果試探成功，就得到問(wèn)題的解，如果不成功，再逐步回退，換別的路線(xiàn)進(jìn)行試探。這種方法，即稱(chēng)為回溯法。如人工智能中的機(jī)器人下棋。5、算法復(fù)雜度：算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）時(shí)間復(fù)雜度：即實(shí)現(xiàn)該算法需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)計(jì)算。同一個(gè)問(wèn)題規(guī)模下，如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時(shí)，可以用以下兩種方法來(lái)分析算法的工作量：算法工作量=f(n) 平均性態(tài)：用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。設(shè)x是某個(gè)可能輸入中

10、的某個(gè)特定輸入，p(x)是x出現(xiàn)的概率，t(x)是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為：。Dn表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。 最壞情況復(fù)雜度指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為：例如，在具有n個(gè)元素的數(shù)列中搜索一個(gè)數(shù)x。 平均性態(tài)：即該數(shù)在數(shù)列中任何位置出現(xiàn)的數(shù)列是相同的，也有可能不存在，存在的概率為q。如果有一半的機(jī)會(huì)存在，則概率q為1/2，平均性態(tài)：如果查找的元素一定在數(shù)列中，則每個(gè)數(shù)存在的概率即為1，則平均性態(tài)為： 最壞情況分析：即要查找的元素X在數(shù)列的最后或不在數(shù)列中，顯然，它的最壞情況復(fù)雜度為：（2）算法的空間復(fù)雜度：指要

11、執(zhí)行該算法所需要的內(nèi)存空間。算法所占用的內(nèi)存空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間，如執(zhí)行過(guò)程中工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間等。（二）數(shù)據(jù)結(jié)構(gòu)的基本概念1、概念：數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。它包括以下兩個(gè)方面：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)之間的前后件關(guān)系。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合，記作D；數(shù)據(jù)之間的前后件關(guān)系，記作R。則數(shù)據(jù)結(jié)構(gòu)B=（D，R）（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，或數(shù)據(jù)的物

12、理結(jié)構(gòu)。即數(shù)據(jù)存儲(chǔ)時(shí)，不僅要存放數(shù)據(jù)元素的信息，而且要存儲(chǔ)數(shù)據(jù)元素之間的前后件關(guān)系的信息。通常的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。2、數(shù)據(jù)結(jié)構(gòu)的圖形表示 數(shù)據(jù)結(jié)構(gòu)的圖形表示有兩個(gè)元素：中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，稱(chēng)為數(shù)據(jù)結(jié)點(diǎn)；用有向線(xiàn)段表示數(shù)據(jù)元素之間的前后件關(guān)系，即有向線(xiàn)段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。 注意：在結(jié)構(gòu)圖中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)，也稱(chēng)葉子結(jié)點(diǎn)。3、線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)：（1）如果一個(gè)數(shù)據(jù)元素都沒(méi)有，該數(shù)據(jù)結(jié)構(gòu)稱(chēng)為空數(shù)據(jù)結(jié)構(gòu)；在空數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的元素后數(shù)據(jù)結(jié)構(gòu)變?yōu)榉强諗?shù)據(jù)結(jié)構(gòu)；將數(shù)據(jù)結(jié)構(gòu)中的所有元素均刪除，則該數(shù)據(jù)結(jié)構(gòu)變成空數(shù)據(jù)結(jié)構(gòu)。

13、（2）如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足如下條件，則該數(shù)據(jù)結(jié)構(gòu)為線(xiàn)性結(jié)構(gòu)： 有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，也最多只有一個(gè)后件線(xiàn)性結(jié)構(gòu)又稱(chēng)線(xiàn)性表。 注意：在線(xiàn)性結(jié)構(gòu)表中插入或刪除元素，該線(xiàn)性表仍然應(yīng)滿(mǎn)足線(xiàn)性結(jié)構(gòu)。（3）如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不滿(mǎn)足線(xiàn)性結(jié)構(gòu)，則稱(chēng)為非線(xiàn)性結(jié)構(gòu)。（三）線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu)1、基本概念：（1）線(xiàn)性表是最常用的數(shù)據(jù)結(jié)構(gòu)，它由一組數(shù)據(jù)元素組成。（2）注意：這里的數(shù)據(jù)元素是一個(gè)廣義的數(shù)據(jù)元素，并不僅僅是指一個(gè)數(shù)據(jù)。如，矩陣、學(xué)生記錄表等。（3）非空線(xiàn)性表的結(jié)構(gòu)特征：有且只有一個(gè)根結(jié)點(diǎn)，它無(wú)前件；有且只有一個(gè)終端結(jié)點(diǎn)，它無(wú)后件；除根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，所有的結(jié)點(diǎn)有且只有一

14、個(gè)前件和一個(gè)后件。線(xiàn)性表中結(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為結(jié)點(diǎn)的長(zhǎng)度n。當(dāng)n=0時(shí)，稱(chēng)為空表。2、順序存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：線(xiàn)性表中所有的元素所占的存儲(chǔ)空間是連續(xù)的；線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。（2）通常，順序存儲(chǔ)結(jié)構(gòu)中，線(xiàn)性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線(xiàn)性表中的位置序號(hào)唯一確定。（3）線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)下的基本運(yùn)算： 在指定位置插入一個(gè)元素； 刪除線(xiàn)性表中的指定元素； 查找某個(gè)或某些特定的元素； 線(xiàn)性表的排序； 按要求將一個(gè)線(xiàn)性表拆分為多個(gè)線(xiàn)性表； 將多個(gè)線(xiàn)性表合并為一個(gè)線(xiàn)性表； 復(fù)制線(xiàn)性表； 逆轉(zhuǎn)一個(gè)線(xiàn)性表。3、線(xiàn)性表的基本操作（1）順序表

15、的插入運(yùn)算：在順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中插入一個(gè)元素。注意：找到插入位置后，將插入位置開(kāi)始的所有元素從最后一個(gè)元素開(kāi)始順序后移。另外，在定義線(xiàn)性表時(shí)，一定要定義足夠的空間，否則，將不允許插入元素。（2）順序表的刪除運(yùn)算：在順序在存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中刪除一個(gè)元素。注意：找到刪除的數(shù)據(jù)元素后，從該元素位置開(kāi)始，將后面的元素一一向前移動(dòng)，在移動(dòng)完成后，線(xiàn)性表的長(zhǎng)度減1。（四）棧和隊(duì)列1、棧及其基本運(yùn)算（1）棧：棧是一種特殊的線(xiàn)性表，它是限定在一端進(jìn)行插入和刪除的線(xiàn)性表。它的插入和刪除只能在表的一端進(jìn)行，而另一端是封閉的，不允許進(jìn)行插入和刪除操作。在棧中，允許插入和刪除操作一端稱(chēng)為棧頂，不允許插入和刪除操作的一端則稱(chēng)為棧底。棧頂?shù)脑乜偸亲詈蟊徊迦氲脑?，也是最先被刪除的元素。它遵循的原則是：先進(jìn)后出或后進(jìn)先出。堆棧指針總是指向棧頂元素的。（2）棧的順序存儲(chǔ)及其運(yùn)算：在棧的順序存儲(chǔ)空間S（1：m）中，S（bottom）通常為棧底元素，S（top）為棧頂元素。Top=0表示?？?；top=m表示棧滿(mǎn)。 入棧運(yùn)算：在棧的頂部插入一個(gè)新元素。操作方式：將棧頂指針加1，再將元素插入至指針?biāo)傅奈恢谩?退棧運(yùn)算：退棧運(yùn)算即將棧頂元素取出并賦給一個(gè)指定的變量。操作方式是：先將棧頂元素賦給指定的變量，再將棧頂指針減1。