全國(guó)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)部分

1、下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)的，表示非常重要，基本每次考試都是必考；標(biāo)注了的，表示非常重要，基本每次考試都是必考；標(biāo)注了兩個(gè)星號(hào)或一個(gè)星號(hào)的，表示也較重要，很容易考兩個(gè)星號(hào)或一個(gè)星號(hào)的，表示也較重要，很容易考到。出現(xiàn)在【】括號(hào)中的內(nèi)容，表示要很精確的背下到。出現(xiàn)在【】括號(hào)中的內(nèi)容，表示要很精確的背下來(lái)的。整個(gè)文檔中的五頁(yè)，建議考前都要認(rèn)真的記來(lái)的。整個(gè)文檔中的五頁(yè)，建議考前都要認(rèn)真的記憶。憶。第一部分算法與數(shù)據(jù)結(jié)構(gòu) (歷年比例 41%)1、算法問(wèn)題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進(jìn)。算法的

2、基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報(bào)。算法的有窮性是指：算法程序的運(yùn)行時(shí)間是有限的。算法的復(fù)雜度是衡量算法好壞的度量，分為【時(shí)間復(fù)雜度】和【空間復(fù)雜度】。時(shí)間復(fù)雜度是指執(zhí)行算法所需要的【計(jì)算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行過(guò)程中所需的【存儲(chǔ)空間】。算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒(méi)有辦法推出另一項(xiàng)的值。2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)】和【存儲(chǔ)結(jié)構(gòu)】。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)?、索引屬于存?chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))。循環(huán)隊(duì)列屬于【存儲(chǔ)結(jié)構(gòu)】。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)

3、，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)。數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(jié)構(gòu)】。線性表的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)空間不一定是連續(xù)的。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列的【順序】存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨(dú)立性】。3、棧和隊(duì)列棧是一種特殊的線性表，是

4、只能在一端進(jìn)行插入和刪除的線性表，特點(diǎn)是 filo(first in last out)。棧是【先進(jìn)后出】的線性表；棧具有記憶作用；對(duì)棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素 1、2、3、a、b 依次入棧，則出棧的順序是：b、a、3、2、1。棧與隊(duì)列都是線性結(jié)構(gòu)，樹(shù)是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【?！俊Ｅc隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。棧只能順序存儲(chǔ)的描述是錯(cuò)誤的。?？梢杂小卷樞蚝玩?zhǔn)健績(jī)煞N存儲(chǔ)方式。隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)是【先進(jìn)先出】。循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)隊(duì)列的頭指針為 fro

5、nt，尾指針為 rear，容量為 maxsize，則循環(huán)隊(duì)列中元素的個(gè)數(shù)是【 (rear-front+maxsize) mod maxsize】。4、線性鏈表線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈表表示線性表的優(yōu)點(diǎn)是【便于插入和刪除操作】。線性鏈表的存儲(chǔ)空間不一定連續(xù)，且個(gè)元素的存儲(chǔ)順序是任意的。5、樹(shù)與二叉樹(shù)在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件（繼）的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。二叉樹(shù)各結(jié)點(diǎn)的度只可能取值 0、1、2，不可能是其它值。換言之，知道了度為 1 結(jié)點(diǎn)數(shù)量的前提下，葉子結(jié)點(diǎn)或度為 2 的結(jié)點(diǎn)中知道其一，就可以求出總的結(jié)點(diǎn)數(shù)。下面關(guān)于計(jì)算結(jié)點(diǎn)數(shù)量的幾個(gè)性質(zhì)，非常重要：

6、(1)對(duì)任意的二叉樹(shù)，葉子結(jié)點(diǎn)的數(shù)量，比度為 2 的結(jié)點(diǎn)數(shù)量多一個(gè)(換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去 1 則是度為 2 的結(jié)點(diǎn)數(shù)量；已知度為 2 的結(jié)點(diǎn)數(shù)量，加上 1就是葉子結(jié)點(diǎn)數(shù)量)(2)完全二叉樹(shù)如果有 n 個(gè)結(jié)點(diǎn)，當(dāng) n 為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為(n+1)/2，此時(shí)二叉樹(shù)只有度為 0 的葉子結(jié)點(diǎn)及度為 2 的結(jié)點(diǎn)，沒(méi)有度為 1 的結(jié)點(diǎn)；當(dāng) n 為偶數(shù)的時(shí)候，葉子結(jié)點(diǎn)的數(shù)量為 n/2。(注意條件，必須是完全二叉樹(shù)，當(dāng)然包括滿二叉樹(shù))(3)滿二叉樹(shù)第 k 層上的結(jié)點(diǎn)數(shù)量為 2k-1；深度為 k 的滿二叉樹(shù)，結(jié)點(diǎn)總數(shù)為 2k-1。上述的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為 7 的滿二叉樹(shù)，

7、度為 2 的結(jié)點(diǎn)數(shù)量是多少？既然是滿二叉樹(shù)，葉子結(jié)點(diǎn)的數(shù)量就是第 7 層的結(jié)點(diǎn)數(shù)量，也就是 26，可以算出葉子結(jié)點(diǎn)為 64，因此度為 2 的結(jié)點(diǎn)數(shù)是 63(葉子結(jié)點(diǎn)數(shù)減去 1)。二叉樹(shù)的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個(gè)詞是相對(duì)于根來(lái)講的，前序是【根-左-右】，中序是【左-根-右】，后續(xù)是【左-右-根】。具體操作為：先序遍歷(d l r): 訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。中序遍歷(l d r): 按中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。后序遍歷(l r d): 按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。下面以中序遍歷為例，來(lái)講解實(shí)際的解題方法：對(duì)一棵樹(shù)，將

8、根結(jié)點(diǎn)下的左子樹(shù)用一個(gè)橢圓圈起來(lái)，右子樹(shù)也用一個(gè)橢圓圈起來(lái)。之后，在左子樹(shù)上標(biāo)記上1，在根結(jié)點(diǎn)標(biāo)記上 2，在右子樹(shù)上標(biāo)記上 3。對(duì)在左邊橢圓內(nèi)的左子樹(shù)，現(xiàn)在把它單獨(dú)拿出來(lái)分析。把它的左子樹(shù)圈起來(lái)標(biāo)上 1.1，根結(jié)點(diǎn)標(biāo)記上 1.2，右子樹(shù)標(biāo)上1.3。按照上述方法依次往下，直到樹(shù)不能拆分，然后按照“左-根-右”的順序?qū)懗鼋Y(jié)點(diǎn)的訪問(wèn)先后即可。6、查找技術(shù)對(duì)于長(zhǎng)度為 n 的線性表，順序查找最壞情況下需要比較 n 次。(對(duì)數(shù)據(jù)是否有序沒(méi)有要求)。順序查找最好情況下查詢次數(shù)是 1，最壞情況下是 n，平均為(1+n)/2。對(duì)于長(zhǎng)度為 n 的有序線性表，二分法最壞情況下只需要比較 log2n 次。(數(shù)據(jù)必須有

9、序)能用二分法進(jìn)行查找的是【順序存儲(chǔ)的有序線性表】。7、排序技術(shù)對(duì)于長(zhǎng)度為 n 的線性表，【冒泡排序、快速排序、簡(jiǎn)單插入排序、簡(jiǎn)單選擇排序】這四種排序方式在最壞情況下的比較次數(shù)相同，都是【n(n-1)/2】。堆排序的效率最高，是【nlog2n】。希爾排序最壞情況下需要次比較【n1.5】。希爾排序?qū)儆凇静迦腩惻判蚍ā俊Ｒ阎獢?shù)據(jù)表 a 中每個(gè)元素距最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對(duì)內(nèi)存要求最大的是【歸并排序】。第二部分軟件工程基礎(chǔ) (歷年比例 27%)1、軟件工程基本概念軟件是包括【程序】、【數(shù)據(jù)】及【相關(guān)文檔】的完整集合，軟件是

10、一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具和過(guò)程】，其中【過(guò)程】支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制和管理。軟件工程的核心思想：把軟件產(chǎn)品當(dāng)作是一個(gè)工程產(chǎn)品來(lái)處理，強(qiáng)調(diào)在軟件開(kāi)發(fā)過(guò)程中應(yīng)用【工程化】原則。從工程管理角度，軟件設(shè)計(jì)一般分為兩步完成，它們是【概要設(shè)計(jì)】和【詳細(xì)設(shè)計(jì)】。軟件生命周期可分為多個(gè)階段，一般分為【定義】階段、【開(kāi)發(fā)】階段和【維護(hù)】階段，編碼和測(cè)試屬于【開(kāi)發(fā)階段】。需求分析階段產(chǎn)生的主要文檔是【軟件需求規(guī)格說(shuō)明書】。軟件需求的規(guī)格說(shuō)明書應(yīng)該有完整性、無(wú)歧義性、正確性、可驗(yàn)證性、可修改性等特征，其中最重要的是【正確性】。2、結(jié)構(gòu)化分析與設(shè)計(jì)需求分析的分發(fā)有：【結(jié)構(gòu)化】需求分析方法，【

11、面向?qū)ο蟆康姆治龇椒?。dfd 是【需求分析階段】可以使用的工具之一。結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖(dfd)；數(shù)據(jù)字典；判定樹(shù)；判定表。在結(jié)構(gòu)化分析使用數(shù)據(jù)流圖(dfd)時(shí)候，利用【數(shù)據(jù)字典】對(duì)其中的圖形元素進(jìn)行確切的解釋?！緮?shù)據(jù)字典】是結(jié)構(gòu)化分析的核心。典型的數(shù)據(jù)流類型有兩種，【交換性】和【事務(wù)型】。常見(jiàn)的過(guò)程設(shè)計(jì)工具有：圖形工具(程序流程圖、n-s，pad，hipo)、表格工具(判定表)、語(yǔ)言工具(pdl 偽碼)。內(nèi)聚性是模塊內(nèi)部的聯(lián)系，耦合性模塊之間的相互聯(lián)系的緊密程度。追求目標(biāo)是：模塊的內(nèi)聚程度要高，模塊間的耦合程度要盡量弱。即高內(nèi)聚低耦合。程序流程圖中帶有箭頭的線段表示的是【控制流】

12、?！酒叫兴倪呅巍看磔斎胼敵觯揪匦巍看硖幚?，菱形代表【判斷】(注意，數(shù)據(jù)流圖中的箭頭，代表【數(shù)據(jù)流】)。符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：【順序結(jié)構(gòu)】，【選擇結(jié)構(gòu)】和【循環(huán)結(jié)構(gòu)】。3、軟件測(cè)試與維護(hù)軟件測(cè)試的目的是盡可能多的發(fā)現(xiàn)程序中的錯(cuò)誤，但是不包括改正錯(cuò)誤。(軟件調(diào)試的目的才是改正錯(cuò)誤)軟件測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試，其中【靜態(tài)測(cè)試】是指不執(zhí)行程序，只對(duì)程序文本進(jìn)行檢查。軟件的動(dòng)態(tài)測(cè)試主要包括【黑盒測(cè)試】和【白盒測(cè)試】。黑盒測(cè)試的方法有等價(jià)類劃分法，邊界值分析法，錯(cuò)誤推測(cè)法，因果圖；白盒測(cè)試主要方法有邏輯覆蓋、基本路徑測(cè)試。(考試時(shí)給出一種方法的名字，你要知道屬于白盒還是黑盒)【白盒

13、測(cè)試】的原則之一是保證所測(cè)模塊的每一個(gè)獨(dú)立路徑至少要執(zhí)行一次。白盒測(cè)試將程序看做是【路徑的集合】。軟件測(cè)試一般按照四個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試，集成測(cè)試，驗(yàn)收測(cè)試和系統(tǒng)測(cè)試。集成測(cè)試應(yīng)該在【單元測(cè)試】之后進(jìn)行。在模塊測(cè)試中，需要為每個(gè)被測(cè)試的模塊設(shè)計(jì)【驅(qū)動(dòng)模塊】和【承接模塊】。其中，驅(qū)動(dòng)模塊的作用是將測(cè)試的數(shù)據(jù)傳給被測(cè)試的模塊，并顯示結(jié)果?！緶y(cè)試用例】是為某個(gè)目標(biāo)而編制的一組測(cè)試輸入、執(zhí)行條件及預(yù)期結(jié)果。測(cè)試用例包括輸入值集和【輸出值集】。診斷和改正程序中的錯(cuò)誤稱為【程序調(diào)試】(或軟件調(diào)試)，通常也稱為debug。軟件調(diào)試可分為【靜態(tài)調(diào)試】和【動(dòng)態(tài)調(diào)試】。在軟件已經(jīng)交付使用之后，為了改正錯(cuò)誤或滿足新的需要而修改軟件的過(guò)程稱為【軟件維護(hù)】。注意軟件維護(hù)不屬于軟件生命周期【開(kāi)發(fā)階段】的任務(wù)。第三部分?jǐn)?shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) (歷年比例 24%)1、數(shù)據(jù)庫(kù)系統(tǒng)基本概念數(shù)據(jù)庫(kù)設(shè)計(jì)的根本目標(biāo)是要解決【數(shù)據(jù)共享問(wèn)題】。在數(shù)據(jù)庫(kù)管理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是【數(shù)據(jù)庫(kù)系統(tǒng)階段】。數(shù)據(jù)獨(dú)立性最高的階段是【數(shù)據(jù)庫(kù)系統(tǒng)階段】。數(shù)據(jù)庫(kù)系統(tǒng)與文件系統(tǒng)的區(qū)別是前者具有【特定的數(shù)據(jù)模型】。數(shù)據(jù)庫(kù)系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型，網(wǎng)絡(luò)模型和【關(guān)系模型】。數(shù)據(jù)庫(kù)系統(tǒng)的核心是【數(shù)據(jù)庫(kù)管理系統(tǒng)】。 dbs 包括 db 和 dbms。完整講，數(shù)據(jù)庫(kù)系統(tǒng) dbs 由數(shù)據(jù)庫(kù) db、數(shù)據(jù)庫(kù)管理系統(tǒng) dbms、數(shù)據(jù)庫(kù)管理員 dba、