計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)考前背誦版

下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)的，表示特別重要,

基本每次考試都是必考；標(biāo)注了兩個(gè)星號(hào)或一個(gè)星號(hào)的，表示也較重

要，很簡潔考到。出現(xiàn)在［】括號(hào)中的內(nèi)容，表示要很精確的背下來

的。整個(gè)文檔中的五頁，建議考前都要仔細(xì)的記憶。

第一部分算法及數(shù)據(jù)結(jié)構(gòu)（歷年比例41盼1、算法?問題處理方案

的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的

效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮

性】和擁有足夠情報(bào)。

?算法的有窮性是指：算法程序的運(yùn)行時(shí)間是有限的。

?算法的困難度是衡量算法好壞的度量，分為【時(shí)間困難度】和【空

間困難度】。

★★時(shí)間困難度是指執(zhí)行算法所須要的【計(jì)算工作量】；算法的空

間困難度是指算法執(zhí)行過程中所需的【存儲(chǔ)空間】。

?算法時(shí)間困難度或空間困難度中的一項(xiàng)的值，沒有方法推出另一

項(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)，旦各種存儲(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ù)【先進(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ì)列**棧是一種特別的線性表，是只能在一端進(jìn)行插入和

刪除的線性表，特點(diǎn)是FILO(FirstInLastOut)o

★★棧是【先進(jìn)后出】的線性表；棧具有記憶作用；對(duì)棧的插入及

刪除操作中，不須要變更【棧底指針】。假定讓元素1、2、3、A、B

依次入棧，則出棧的依次是：B、A、3、2、1。

?棧及隊(duì)列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)

據(jù)結(jié)構(gòu)是【棧】。

?棧及隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。

?棧只能依次存儲(chǔ)的描述是錯(cuò)誤的。棧可以有【依次和鏈?zhǔn)健績煞N

存儲(chǔ)方式。

★★隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)

是【先進(jìn)先出】。

?循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同確定。循環(huán)

隊(duì)列的頭指針為front,尾指針為rear,容量為maxSize,則循環(huán)隊(duì)

列中元素的個(gè)數(shù)是【（rear-front+maxSize）modmaxSizelo

4、線性鏈表.線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈表表示線性

表的優(yōu)點(diǎn)是【便于插入和刪除操作】。

?線性鏈表的存儲(chǔ)空間不肯定連續(xù)，且個(gè)元素的存儲(chǔ)依次是隨意的。

5、樹及二叉樹?在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件（繼）的個(gè)數(shù)

稱為該結(jié)點(diǎn)的度，全部結(jié)點(diǎn)中最大的度稱為樹的度。二叉樹各結(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ù)量的幾特性質(zhì)，特別重要：

⑴對(duì)隨意的二叉樹，葉子結(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ù)量）

⑵完全二叉樹假如有N個(gè)結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為

（N+D/2,此時(shí)二叉樹只有度為0的葉子結(jié)點(diǎn)及度為2的結(jié)點(diǎn)，沒有

度為1的結(jié)點(diǎn)；當(dāng)N為偶數(shù)的時(shí)候，葉子結(jié)點(diǎn)的數(shù)量為N/2。（留意

條件，必需是完全一叉樹，當(dāng)然包括滿一叉樹）

⑶滿二叉樹第K層上的結(jié)點(diǎn)數(shù)量為2K-1；深度為K的滿二叉樹，結(jié)

點(diǎn)總數(shù)為2K7。上述的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7

的滿二叉樹，度為2的結(jié)點(diǎn)數(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）e

★★★二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個(gè)詞是

相對(duì)于根來講的，前序是【根一＞左一＞右］，中序是【左一》根一）

右】，后續(xù)是【左一〉右一》根］。具體操作為：

先序遍歷⑴LR）:訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右

子樹。

中序遍歷（LDR）:按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右

子樹。

后序遍歷（LRD）:按后序遍歷左子樹，按后序遍歷右子樹，訪問根

結(jié)點(diǎn)。

下面以中序遍歷為例，來講解實(shí)際的解題方法：對(duì)一棵樹，將根結(jié)點(diǎn)

下的左子樹用一個(gè)橢圓圈起來，右子樹也用一個(gè)橢圓圈起來。之后，

在左子樹上標(biāo)記上1,在根結(jié)點(diǎn)標(biāo)記上2,在右子樹上標(biāo)記上3。對(duì)

在左邊橢圓內(nèi)的左子樹，現(xiàn)在把它單獨(dú)拿出來分析。把它的左子樹圈

起來標(biāo)上1.1,根結(jié)點(diǎn)標(biāo)記上1.2,右子樹標(biāo)上1.3。依據(jù)上述方法

依次往下，直到樹不能拆分，然后依據(jù)“左一＞根一-＞右”的依次寫

出結(jié)點(diǎn)的訪問先后即可。

6、查找技術(shù).對(duì)于長度為n的線性表，依次查找最壞狀況下須要比

較n次。（對(duì)數(shù)據(jù)是否有序沒有要求）。?依次查找最好狀況下查詢

次數(shù)是1,最壞狀況下是n,平均為（l+n）/2。

★★對(duì)于長度為n的有序線性表，二分法最壞狀況下只須要比較

log2n次。（數(shù)據(jù)必需有序）

?能用二分法進(jìn)行查找的是【依次存儲(chǔ)的有序線性表】。

7、排序技術(shù)**對(duì)于長度為n的線性表，【冒泡排序、快速排序、

簡潔插入排序、簡潔選擇排序】這四種排序方式在最壞狀況下的比較

次數(shù)相同,都是［n（n-l）/2］o堆排序的效率最高,是次1。相n】o

★★希爾排序最壞狀況下須要次比較【nl.5］。希爾排序?qū)儆凇静?/p>

入類排序法】。

?己知數(shù)據(jù)表A中每個(gè)元素距最終位置不遠(yuǎn)，為節(jié)約時(shí)間，應(yīng)當(dāng)采

納的算法是【干脆插入排序】。選擇排序、插入排序、快速排序、歸

并排序中對(duì)內(nèi)存要求最大的是【歸并排序】。

其次部分軟件工程基礎(chǔ)（歷年比例27%）1、軟件工程基本概念★★

軟件是包括【程序】、【數(shù)據(jù)】及【相關(guān)文檔】的完整集合，軟件是

一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具和過程】，其中【過

程】支持軟件開發(fā)的各個(gè)環(huán)節(jié)的限制和管理。

?軟件工程的核心思想：把軟件產(chǎn)品當(dāng)作是一個(gè)工程產(chǎn)品來處理，

強(qiáng)調(diào)在軟件開發(fā)過程中應(yīng)用【工程化】原則。

?從工程管理角度，軟件設(shè)計(jì)一般分為兩步完成，它們是【概要設(shè)

計(jì)】和【具體設(shè)計(jì)】。

★★軟件生命周期可分為多個(gè)階段，一般分為【定義】階段、【開

發(fā)】階段和【維護(hù)】階段，編碼和測試屬于【開發(fā)階段】。

?需求分析階段產(chǎn)生的主要文檔是【軟件需求規(guī)格說明書】。軟件

需求的規(guī)格說明書應(yīng)當(dāng)有完整性、無歧義性、正確性、可驗(yàn)證性、可

修改性等特征，其中最重要的是【正確性】。

2、結(jié)構(gòu)化分析及設(shè)計(jì)★★需求分析的分發(fā)有：【結(jié)構(gòu)化】需求分析

方法，【面對(duì)對(duì)象】的分析方法。DFD是【需求分析階段】可以運(yùn)用

的工具之一。

?結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖（DFD）；數(shù)據(jù)字典；判定樹；判

定表。

?在結(jié)構(gòu)化分析運(yùn)用數(shù)據(jù)流圖（DFD）時(shí)候，利用【數(shù)據(jù)字典】對(duì)其中

的圖形元素進(jìn)行準(zhǔn)確的說明?！緮?shù)據(jù)字典】是結(jié)構(gòu)化分析的核心。

?典型的數(shù)據(jù)流類型有兩種，【交換性】和【事務(wù)型】。

?常見的過程設(shè)計(jì)工具有：圖形工具（程序流程圖、N-S,PAD,HIPO）>

表格工具（判定表）、語言工具（PDL偽碼）。

?內(nèi)聚性是模塊內(nèi)部的聯(lián)系，耦合性模塊之間的相互聯(lián)系的緊密程

度。

★★★追求目標(biāo)是：模塊的內(nèi)聚程度要高，模塊間的耦合程度要盡

量弱。即高內(nèi)聚低耦合。

★★程序流程圖中帶有箭頭的線段表示的是【限制流】。【平行四

邊形】代表輸入輸出，【矩形】代表處理，菱形代表【推斷】（留意，

數(shù)據(jù)流圖中的箭頭，代表【數(shù)據(jù)流】）o

?符合結(jié)構(gòu)化原則的三種基本限制結(jié)構(gòu)是：【依次結(jié)構(gòu)】，【選擇

結(jié)構(gòu)】和【循環(huán)結(jié)構(gòu)】。

3、軟件測試及維護(hù)**軟件測試的目的是盡可能多的發(fā)覺程序中的

錯(cuò)誤，但是不包括改正錯(cuò)誤。（軟件調(diào)試的目的才是改正錯(cuò)誤）

★★軟件測試分為靜態(tài)測試和動(dòng)態(tài)測試，其中【靜態(tài)測試】是指不

執(zhí)行程序，只對(duì)程序文本進(jìn)行檢查。軟件的動(dòng)態(tài)測試主要包括?【黑盒

測試】和【白盒測試】。

?黑盒測試的方法有等價(jià)類劃分法，邊界值分析法，錯(cuò)誤推想法，

因果圖；白盒測試主要方法有邏輯覆蓋、基本路徑測試。（考試時(shí)給

出一種方法的名字，你要知道屬于白盒還是黑盒）

【白盒測試】的原則之一是保證所測模塊的每一個(gè)獨(dú)立路徑至少要執(zhí)

行一次。白盒測試將程序看做是【路徑的集合】。

?軟件測試一般依據(jù)四個(gè)步驟進(jìn)行：單元測試，集成測試，驗(yàn)收測

試和系統(tǒng)測試。集成測試應(yīng)當(dāng)在【單元測試】之后進(jìn)行。

?在模塊測試中，須要為每個(gè)被測試的模塊設(shè)計(jì)【驅(qū)動(dòng)模塊】和【承

接模塊】。其中，驅(qū)動(dòng)模塊的作用是將測試的數(shù)據(jù)傳給被測試的模塊，

并顯示結(jié)果。

?【測試用例】是為某個(gè)目標(biāo)而編制的一組測試輸入、執(zhí)行條件及

預(yù)期結(jié)果。測試用例包括輸入值集和【輸出值集】。

★★診斷和改正程序中的錯(cuò)誤稱為【程序調(diào)試】（或軟件調(diào)試），通

常也稱為Debug。軟件調(diào)試可分為【靜態(tài)調(diào)試】和【動(dòng)態(tài)調(diào)試】。

?在軟件已經(jīng)交付運(yùn)田之后，為了改正錯(cuò)誤或滿意新的須要而修改

軟件的過程稱為【軟件維護(hù)】。留意軟件維護(hù)不屬于軟件生命周期【開

發(fā)階段】的任務(wù)。

第三部分?jǐn)?shù)據(jù)庫設(shè)計(jì)基礎(chǔ)（歷年比例24%）1、數(shù)據(jù)庫系統(tǒng)基本概念

?數(shù)據(jù)庫設(shè)計(jì)的根本目標(biāo)是要解決【數(shù)據(jù)共享問題】。在數(shù)據(jù)庫管

理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是【數(shù)據(jù)庫系統(tǒng)階段】。

數(shù)據(jù)獨(dú)立性最高的階段是【數(shù)據(jù)庫系統(tǒng)階段】。

?數(shù)據(jù)庫系統(tǒng)及文件系統(tǒng)的區(qū)分是前者具有【特定的數(shù)據(jù)模型】。

?數(shù)據(jù)庫系統(tǒng)常見的數(shù)據(jù)模型有層次模型，網(wǎng)絡(luò)模型和【關(guān)系模型】。

★★數(shù)據(jù)庫系統(tǒng)的核心是【數(shù)據(jù)庫管理系統(tǒng)】。

?DBS包括DB和DBMS。完整講，數(shù)據(jù)庫系統(tǒng)DBS由數(shù)據(jù)庫DB、

數(shù)據(jù)庫管理系統(tǒng)DBMS、數(shù)據(jù)庫管理員DBA、硬件平臺(tái)和軟件平臺(tái)組成。

?數(shù)據(jù)庫應(yīng)用系統(tǒng)的核心是【數(shù)據(jù)庫維護(hù)】。

?數(shù)據(jù)庫系統(tǒng)的三級(jí)模式結(jié)構(gòu)：內(nèi)模式處于最底層，它反映了數(shù)據(jù)

在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲(chǔ)形式；概念模式處于中層，它放映了

設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求，及軟硬件環(huán)境無關(guān)；

外模式處于最外層，它反映了用戶對(duì)數(shù)據(jù)的要求。

?在數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為【外模式】。

?數(shù)據(jù)庫設(shè)計(jì)的四個(gè)階段是：需求分析、概念設(shè)計(jì)、【邏輯設(shè)計(jì)】

和【物理設(shè)計(jì)】。將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型屬于【邏輯設(shè)計(jì)】階

段。

?數(shù)據(jù)庫管理系統(tǒng)供應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言DDL,數(shù)據(jù)操縱

語言DML,數(shù)據(jù)限制語言DCLoSQL的全稱是StructuredQuery

Language,中義意思是【結(jié)構(gòu)化查詢語言】。

2、數(shù)據(jù)模型★★★實(shí)體之間的聯(lián)系用樹形結(jié)構(gòu)來表示的模型是【層

次模型】。采納二維表來表示的是【關(guān)系模型】。在關(guān)系數(shù)據(jù)庫中，

把數(shù)據(jù)表示成二維表，每一個(gè)二維表稱為【關(guān)系】。

?在關(guān)系數(shù)據(jù)庫中，用來表示實(shí)體之間聯(lián)系的是【關(guān)系】。

?將E-R圖轉(zhuǎn)化為關(guān)系模式時(shí)，實(shí)體和聯(lián)系都可以表示為【關(guān)系】。

★★★確定兩個(gè)實(shí)體之間是一對(duì)一、一對(duì)多、還是多對(duì)多的方法是：

選擇實(shí)體A,看是否有多個(gè)實(shí)體B及之對(duì)應(yīng)；選擇實(shí)體B,看是否有

多個(gè)實(shí)體A及之對(duì)應(yīng)。例如在“學(xué)生學(xué)習(xí)課程”中的兩個(gè)實(shí)體，學(xué)生

及課程，一個(gè)學(xué)生可以學(xué)習(xí)多門課程，一門課程可以被多個(gè)學(xué)生學(xué)習(xí)，

所以二者是一種多對(duì)多的關(guān)系。

★★在E-R圖中，用來表示實(shí)體的圖形是【矩形】。用來表示【屬

性】的圖形是橢圓。用菱形來表示聯(lián)系。

★★一個(gè)關(guān)系表的行稱為【元組】（或記錄），列稱為【屬性】（或字

段）。

?在二維表中，元組的【重量】不能再分為更小的數(shù)據(jù)線。

?為了建立一個(gè)關(guān)系，首先要構(gòu)造數(shù)據(jù)的【邏輯關(guān)系】。

3、關(guān)系代數(shù).在交、差、投影中，不變更關(guān)系表中的屬性個(gè)數(shù)但是

能削減元組個(gè)數(shù)的是【交】運(yùn)算。

★★★關(guān)系運(yùn)算的規(guī)則（下面介紹的7種運(yùn)算，考試的時(shí)候一般會(huì)考

察一種，都要背）

（1）并運(yùn)算RUS：并運(yùn)算是兩個(gè)表行上的合并，重復(fù)的行只出現(xiàn)一次。

（2）交運(yùn)算RHS：交運(yùn)算是選出兩個(gè)表中的公共行。

⑶差運(yùn)算R-S：差運(yùn)算是從表R中，刪除R及S中都出現(xiàn)過的行。

⑷選擇運(yùn)算：選出二維表【