2020年全國計算機等級考試二級公共基礎(chǔ)知識必考重點提綱

2020年全國計算機等級考試二級公共基

礎(chǔ)知識必考重點提綱（精華版）

全國計算機等級考試公共基礎(chǔ)知識

2020年全國計算機等級考試二級公共基礎(chǔ)知識必考重

點提綱（精華版）

第一章數(shù)據(jù)結(jié)構(gòu)與算法

1.1算法

算法：是指解題方案的準(zhǔn)確而完整的描述。

算法不等于程序，也不等計算機方法，程序的編制不可能

優(yōu)于算法的設(shè)計。

算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，每

一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終

止。

特征包括：

（1）可行性；

（2）確定性，算法中每一步驟都必須有明確定義，不允

許有模棱兩可的解釋，不允許有多義性；

（3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在

執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義;

(4)擁有足夠的情報。

算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算

法的控制結(jié)構(gòu)。

基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、

數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半

遞推技術(shù)、回溯法。

算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。

-1-

全國計算機等級考試公共基礎(chǔ)知識

算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。

一般來說，算法的工作量用其執(zhí)行的基本運算次數(shù)來度量,

而算法執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)。在同一個問題

規(guī)模下，用平均性態(tài)和最壞情況復(fù)雜性來分析。一般情況下，

用最壞情況復(fù)雜性來分析算法的時間復(fù)雜度。

算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)研究的三個方面：

(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即

數(shù)據(jù)的邏輯結(jié)構(gòu)；

(2)在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存

儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；

(3)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)是反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。

數(shù)據(jù)的邏輯結(jié)構(gòu)包含：

(1)表示數(shù)據(jù)元素的信息；

(2)表示各數(shù)據(jù)元素之間的前后件關(guān)系。(邏輯關(guān)系，

與在計算機內(nèi)的存儲位置無關(guān))

一個數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素在計算機存儲空間中的位置

關(guān)系與邏輯關(guān)系有可能不同。

數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的

存放形式。

常用的存儲結(jié)構(gòu)有順序、鏈接、索引等。

-2-

全國計算機等級考試公共基礎(chǔ)知識

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，

一般將數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

線性結(jié)構(gòu)條件：

(1)有且只有一個根結(jié)點；

(2)每一個結(jié)點最多有一個前件，也最多有一個后件。

非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

1.3線性表及其順序存儲結(jié)構(gòu)

線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自

己的序號，元素之間的相對位置是線性的。

如：一個N維向量、矩陣

在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為

記錄，而由多個記錄構(gòu)成的線性表又稱為文件。

非空線性表的結(jié)構(gòu)特征：

(1)有且只有一個根結(jié)點al,它無前件；

(2)有且只有一個終端結(jié)點an,它無后件；

(3)除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一

個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度,

當(dāng)n=0時，稱為空表。

線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：

(1)線性表中所有元素的所占的存儲空間是連續(xù)的；

(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依

次存放的。

ai的存儲地址為：ADR(ai)=ADR(al)+(i-l)k,,ADR(al)為

第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。

-3-

全國計算機等級考試公共基礎(chǔ)知識

順序表的運算：插入、刪除。

1.4棧和隊列

1.棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與

刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。

棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出"(LIFO)組織

數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表

示棧底。

2.棧的順序存儲

用一維數(shù)組S(l:m)作為棧的順序存儲空間，M為棧的

最大容量。S(bottom)表示棧底元素，s(top)為棧頂元素，top=0

表示棧空，top=m表示棧滿。

3.棧的基本運算：

(1)插入元素稱為入棧運算；(top=top+1;將新元素插入

到棧頂指針指向的位置)上溢

(2)刪除元素稱為退棧運算；(將棧頂指針指向的元素

賦給指定的變量，top=top-1)下溢

（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此

時指針無變化。

1.隊列

隊列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊

頭）進(jìn)行刪除的線性表。Rear指針指向隊尾，front指針指向

隊頭。

隊列是“先進(jìn)先出“（FIFO）或“后進(jìn)后出”（LILO）的線

性表。

隊列的順序存儲

與棧類似，用一維數(shù)組Q（1：m）作為隊列的順序存儲

空間

-4-

全國計算機等級考試公共基礎(chǔ)知識

隊列運算

（1）入隊運算：從隊尾插入一個元素；

（2）退隊運算：從隊頭刪除一個元素。

循環(huán)隊列：

在循環(huán)隊列結(jié)構(gòu)中，當(dāng)存儲空間的最后一個位置已被使用

而要進(jìn)行入隊運算時，只要存儲空間的第一個位置空閑，就可

將元素加入到第一個位置，即將存儲空間的第一個位置作為隊

尾。

從Front指針指向的后一個位置直到隊尾指針rear指向的

位置之間所有的元素均為隊列中的元素。

循環(huán)隊列的初始狀態(tài)為空：rear=front=m

當(dāng)循環(huán)隊列滿時，rear=Front

為區(qū)別隊滿還是隊空，增加標(biāo)志S。

s=0表示隊列空，s=l且fron仁rear表示隊列滿

1.5線性鏈表

對于元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，而

應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個

存儲單元，這種

-5-

全國計算機等級考試公共基礎(chǔ)知識

存儲單元稱為存儲結(jié)點，簡稱結(jié)點。

結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)

據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或

后一個結(jié)點。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),

各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,

而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線

性結(jié)構(gòu)。

線性鏈表，HEAD稱為頭指針，HEAD=NULL（或）稱為

空表，如果是兩指針：左指針（Llink）指向前件結(jié)點，右指

針（Rlink）指向后件結(jié)點。

線性鏈表的基本運算：查找、插入、刪除。

1.6樹與二叉樹

樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層

次特性。

A

BC

DEFG

HI

在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒

有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一

個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)

點稱為葉子結(jié)點。

在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的

度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的

深度。

度為2的樹稱為二叉樹。

-6-

全國計算機等級考試公共基礎(chǔ)知識

A1

B2

D4E5

HI

C3

F6G7

二叉樹的特點：

(1)非空二叉樹只有一個根結(jié)點；

(2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的

左子樹與右子樹。

二叉樹的基本性質(zhì)：

(1)在二叉樹的第k層上，最多有2k-l(kNl)個結(jié)點；

(2)深度為m的二叉樹最多有2m-l個結(jié)點；

(3)度為的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多

一個；

(4)具有n個結(jié)點的二叉樹，其深度至少為［log2n］+l,其

中［log2n］表示取log2n的整數(shù)部分；

滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個

子結(jié)點，

A1

B2

D4

HIJ

E5

KL

C3

F6

MN

G7

O

滿二叉樹的性質(zhì)：

第k層上有2k-l個結(jié)點，深度為m的滿二叉樹有2m-1

個結(jié)點。

完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到

最大值，在最后一層上只缺少右邊的若干結(jié)點。

-7-

全國計算機等級考試公共基礎(chǔ)知識

A1

B2

D4

HIJ

E5

C3

F6G7

由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是

完全二叉樹，完全二叉樹一般不是滿二叉樹。

完全二叉樹的性質(zhì)：

(1)具有n個結(jié)點的完全二叉樹的深度為[log2n]+l；

(2)設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，

按層序(每一層從左到右)用自然數(shù)1,2,n給結(jié)點進(jìn)行

編號(k=l,2....n),有以下結(jié)論：

①若k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>l,

則該結(jié)點的父結(jié)點編號為INT(k/2)；

②若2k<n,則編號為k的結(jié)點的左子結(jié)點編號為2k；否

則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；

③若2k+l<n,則編號為k的結(jié)點的右子結(jié)點編號為2k+l；

否則該結(jié)點無右子結(jié)點。

二叉樹存儲結(jié)構(gòu)

采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層

序進(jìn)行順序存儲。

二叉樹的遍歷：

（1）前序遍歷（DLR）,首先訪問根結(jié)點，然后遍歷左

子樹，最后遍歷右子樹；

（2）中序遍歷（LDR）,首先遍歷左子樹，然后訪問根

結(jié)點，最后遍歷右子

-8-

全國計算機等級考試公共基礎(chǔ)知識

樹；

（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷

右子樹，最后訪問根結(jié)點。

例：設(shè)有如下的二叉樹

A1

B2

D4E5

HI

C3

F6G7

其前序遍歷（DLR）的結(jié)果為：ABDEHICFG

其中序遍歷（LDR）的結(jié)果為：DBHEIAFCG

其后序遍歷（LRD）的結(jié)果為：DHIEBFGCA

1.7查找技術(shù)

順序查找的使用情況：

（1）線性表為無序表；（不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)?/p>

存儲結(jié)構(gòu)）

（2）表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。（即使是有序線性表）

二分法查找只適用于順序存儲的有序表，

對于長度為n的有序線性表，二分查找最壞情況只需比較

log2n次，順序查找需要比較n次。

1.8排序技術(shù)

排序是指將一個無序序列整理成按值非遞減順序排列的有

序序列。

交換類排序法：

-9-

全國計算機等級考試公共基礎(chǔ)知識

假設(shè)線性表的長度為n

(1)冒泡排序法

在最壞情況下，需要比較的次數(shù)為n(n-l)/2；

(2)快速排序法

在最壞情況下，需要比較的次數(shù)為n(n-l)/2

插入類排序法：

(1)簡單插入排序法，最壞情況需要n(n-l)/2次比較;

(2)希爾排序法，最壞情況需要0(nl.5)次比較。

選擇類排序法：

(1)簡單選擇排序法,最壞情況需要n(n-l)/2次比較；

(2)堆排序法，最壞情況需要O(nlog2n)次比較。

-10-

全國計算機等級考試公共基礎(chǔ)知識

第二章程序設(shè)計基礎(chǔ)

2.1程序設(shè)計設(shè)計方法和風(fēng)格

如何形成良好的程序設(shè)計風(fēng)格

1、源程序文檔化；2、數(shù)據(jù)說明的方法；

3、語句的結(jié)構(gòu)；4、輸入和輸出。

注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效

率第二。

2.2結(jié)構(gòu)化程序設(shè)計

結(jié)構(gòu)化程序設(shè)計方法的四條原則是：1.自頂向下；2.逐步

求精；3.模塊化；4.限制使用goto語句。

結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：

(1)順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用

的結(jié)構(gòu)；

(2)選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支

選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)

的語句序列；

(3)重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷

是否需要重復(fù)執(zhí)行某一相同程序段。

2.3面向?qū)ο蟮某绦蛟O(shè)計

面向?qū)ο蟮某绦蛟O(shè)計：以60年代末挪威奧斯陸大學(xué)和挪

威計算機中心研制的SIMULA語言為標(biāo)志。

面向?qū)ο蠓椒ǖ膬?yōu)點：

(1)與人類習(xí)慣的思維方法一致；

(2)穩(wěn)定性好；

(3)可重用性好；

-11-

全國計算機等級考試公共基礎(chǔ)知識

(4)易于開發(fā)大型軟件產(chǎn)品；

(5)可維護性好。

對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀

世界中的任何實體，對象是實體的抽象。

面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀

事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其

靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。

屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，

操作也稱為方法或服務(wù)。

對象的基本特點：

(1)標(biāo)識惟一性；

(2)分類性；

(3)多態(tài)性；

(4)封裝性；

(5)模塊獨立性好。

類是指具有共同屬性、共同方法的對象的集合。所以類是

對象的抽象，對象是對應(yīng)類的一個實例。

消息是一個實例與另一個實例之間傳遞的信息。

消息的組成包括（1）接收消息的對象的名稱；（2）消息

標(biāo)識符，也稱消息名；（3）零個或多個參數(shù)。

繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定

義他們。

繼承分單繼承和多重繼承。單繼承指一個類只允許有一個

父類，多重繼承指一個類允許有多個父類。

-12-

全國計算機等級考試公共基礎(chǔ)知識

多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不

同的行動的現(xiàn)象。

-13-

全國計算機等級考試公共基礎(chǔ)知識

第三章軟件工程基礎(chǔ)

3.1軟件工程基本概念

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

軟件的特點包括：

（1）軟件是一種邏輯實體；

（2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；

（3）軟件在運行、使用期間不存在磨損、老化問題；

（4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計

算機系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；

（5）軟件復(fù)雜性高，成本昂貴；

（6）軟件開發(fā)涉及諸多的社會因素。

軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具

軟件）。

軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所遇到

的一系列嚴(yán)重問題（軟件開發(fā)成本和進(jìn)度無法控制；質(zhì)量難以

保證；軟件維護程度低）

軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。

軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整

套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。

軟件工程包括3個要素：方法、工具和過程。

方法是完成軟件工程項目的技術(shù)手段；

工具支持軟件的開發(fā)、管理、文檔生成；

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

軟件工程的核心思想是把軟件產(chǎn)品看作是一個工程產(chǎn)品來

處理。

-14-

全國計算機等級考試公共基礎(chǔ)知識

軟件工程過程：是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資

源和活動，包含4種基本活動：

(1)P(Plan)——軟件規(guī)格說明；(功能及其運行時的

限制)

(2)D(Do)——軟件開發(fā)；(產(chǎn)生滿足規(guī)格說明的軟件)

(3)C(Check)——軟件確認(rèn)；(確認(rèn)軟件能夠滿足客戶

提出的要求)

(4)A(Action)------軟件演進(jìn)。

軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用

退役的過程。

軟件生命周期三個階段：

軟件定義、軟件開發(fā)、運行維護

軟件定義階段：

(1)可行性研究與計劃制定；

(2)需求分析；

軟件開發(fā)階段：

(3)軟件設(shè)計；(概要設(shè)計和詳細(xì)設(shè)計)

(4)軟件實現(xiàn)；

(5)軟件測試；

軟件維護階段：

(6)運行和維護。

(7)退役

軟件工程的目標(biāo)與原則：

目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、

可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植

性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。

-15-

全國計算機等級考試公共基礎(chǔ)知識

基本目標(biāo)：付出較低的開發(fā)成本；達(dá)到要求的軟件功能；

取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；

能按時完成開發(fā)，及時交付使用。

基本原則：

抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完

備性和可驗證性。

軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)

技術(shù)和軟件工程管理。

軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工

具和軟件工程環(huán)境。

軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟學(xué)、軟件

心理學(xué)等內(nèi)容。

軟件管理學(xué)包括人員組織、進(jìn)度安排、質(zhì)量保證、配置管

理、項目計劃等。

軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確

定性、一致性、完備性和可驗證性。

現(xiàn)代軟件工程方法之所以得以實施，其重要的保證是軟件

開發(fā)工具和環(huán)境的保證。

軟件開發(fā)工具

軟件開發(fā)環(huán)境(全面支持軟件開發(fā)全過程的軟件工具的集

合)

3.2結(jié)構(gòu)化分析方法

軟件開發(fā)方法是軟件開發(fā)過程所遵循的方法和步驟，包括

分析方法、設(shè)計方法和程序設(shè)計方法。

結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。

需求分析階段的工作：

-16-

全國計算機等級考試公共基礎(chǔ)知識

(1)需求獲取：確定對目標(biāo)系統(tǒng)的各方面需求

(2)需求分析：確定給出系統(tǒng)的解決方案和目標(biāo)系統(tǒng)的

邏輯模型

(3)編寫需求規(guī)格說明書

（4）需求評審

需求分析方法有（1）結(jié)構(gòu)化需求分析方法；（2）面向?qū)?/p>

象的分析的方法。

結(jié)構(gòu)化分析方法

結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層

分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工

具，建立系統(tǒng)的邏輯模型。

結(jié)構(gòu)化分析的常用工具

（1）數(shù)據(jù)流圖；（2）數(shù)據(jù)字典；（3）判定樹；（4）判

定表。

數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯

模型的圖形表示，它直接支持系統(tǒng)功能建模。

數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的

列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對于

輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。

判定樹：從問題定義的文字描述中分清哪些是判定的條件,

哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定條件之

間的從屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。

判定表：與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多

個邏輯條件的取值，即完成該加工的一組動作是由于某一組條

件取值的組合而引發(fā)的，使用判定表描述比較適宜。

數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。

軟件需求規(guī)格說明書的特點：

-17-

全國計算機等級考試公共基礎(chǔ)知識

(1)正確性；

(2)無岐義性；

(3)完整性；

(4)可驗證性；

(5)一致性；

(6)可理解性；

(7)可追蹤性。

3.3結(jié)構(gòu)化設(shè)計方法

軟件設(shè)計的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系

統(tǒng)如何完成預(yù)定的任務(wù)，軟件設(shè)計是確定系統(tǒng)的物理模型。

軟件設(shè)計是開發(fā)階段最重要的步驟，是將需求準(zhǔn)確地轉(zhuǎn)化

為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。

從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、

接口設(shè)計、過程設(shè)計。

結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。

數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。

接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件

與人之間如何通信。

過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。

從工程管理角度來看：概要設(shè)計和詳細(xì)設(shè)計。

軟件設(shè)計的一般過程：軟件設(shè)計是一個迭代的過程；先進(jìn)

行高層次的結(jié)構(gòu)設(shè)計；后進(jìn)行低層次的過程設(shè)計；穿插進(jìn)行數(shù)

據(jù)設(shè)計和接口設(shè)計。

-18-

全國計算機等級考試公共基礎(chǔ)知識

軟件設(shè)計的基本原理：

(1)抽象(2)模塊化(3)信息屏蔽

(4)模塊獨立性

衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量

標(biāo)準(zhǔn)。

在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀

軟件應(yīng)高內(nèi)聚，低耦合。

軟件概要設(shè)計的基本任務(wù)是：

(1)設(shè)計軟件系統(tǒng)結(jié)構(gòu)；

(2)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計；

(3)編寫概要設(shè)計文檔；

(4)概要設(shè)計文檔評審。

常用的軟件結(jié)構(gòu)設(shè)計工具是程序結(jié)構(gòu)圖(SC),使用它

描述軟件系統(tǒng)的層次和結(jié)構(gòu)關(guān)系。

模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。

在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來

回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息,

帶空心圓的箭心表示傳遞的是數(shù)據(jù)。

結(jié)構(gòu)圖的基本形式：基本形式、順序形式、重復(fù)形式、選

擇形式。

結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊

和協(xié)調(diào)模塊。

面向數(shù)據(jù)流的設(shè)計方法

在需求分析階段，主要分析信息在系統(tǒng)中加工和流動的情

況。

面向數(shù)據(jù)流的設(shè)計方法定義一些映射方法，把數(shù)據(jù)流圖變

換成結(jié)構(gòu)圖表示的軟件結(jié)構(gòu)。

-19-

全國計算機等級考試公共基礎(chǔ)知識

典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。

變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。

事務(wù)型數(shù)據(jù)流的特點是：接受一項事務(wù)，根據(jù)事務(wù)處理的

特點和性質(zhì)，選擇分派一個適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。

詳細(xì)設(shè)計

詳細(xì)設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和

局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的

細(xì)節(jié)。

常見的過程設(shè)計工具有：

圖形工具：程序流程圖、N-S（方框圖）、PAD（問題分

析圖）、HIPO

表格工具：判定表

語言工具：PDL

3.4軟件測試

軟件測試是保證軟件質(zhì)量的重要手段，其主要過程涵蓋了

整個軟件生命周期的過程，包括需求定義階段的需求測試、編

碼階段的單元測試、集成測試以及后期的確認(rèn)測試、系統(tǒng)測試。

軟件測試定義：使用人工或自動手段來運行或測定某個系

統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預(yù)

期結(jié)果與實際結(jié)果之間的差別。

軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。

一個好的測試用例是指很可能找到迄今為止尚未發(fā)現(xiàn)的錯

誤的用例。

一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。

測試要以查找錯誤為中心，測試只能證明程序中有錯誤，

不能證明程序中沒有錯誤。

-20-

全國計算機等級考試公共基礎(chǔ)知識

軟件測試方法

從是否需要執(zhí)行被測軟件的角度，分為靜態(tài)測試和動態(tài)測

試。

按照功能劃分可以分為白盒測試和黑盒測試。

(1)靜態(tài)測試和動態(tài)測試

靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。

不實際運行軟件，主要通過人工進(jìn)行。

動態(tài)測試：是基本計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行

程序的過程。（利用測試用例去運行程序，以發(fā)現(xiàn)程序錯誤的

過程）

測試用例是為測試設(shè)計的數(shù)據(jù)。

動態(tài)測試主要包括白盒測試方法和黑盒測試方法。

白盒測試也稱結(jié)構(gòu)測試，根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，

檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計規(guī)格要求。

白盒測試：在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作

的驗證。主要方法有邏輯覆蓋、基本路徑測試。

黑盒測試也稱功能測試，是對軟件已經(jīng)實現(xiàn)的功能是否滿

足需求進(jìn)行測試和驗證。（不考慮內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性,

只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否滿足

功能說明）

黑盒測試是在軟件接口處進(jìn)行，完成功能驗證。

黑盒測試：主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)

構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，

主要用于軟件確認(rèn)測試。主要方法有等價類劃分法、邊界值分

析法、錯誤推測法等。

軟件測試過程一般按4個步驟進(jìn)行：

單元測試、集成測試、驗收測試（確認(rèn)測試）和系統(tǒng)測試。

-21-

全國計算機等級考試公共基礎(chǔ)知識

3.5程序的調(diào)試

注意程序測試與調(diào)試的區(qū)別：

測試是盡可能多地發(fā)現(xiàn)軟件中的錯誤，軟件測試貫穿整個

軟件生命期

調(diào)試是診斷和改正程序中的錯誤，主要在開發(fā)階段進(jìn)行

程序調(diào)試的基本步驟：

(1)錯誤定位；

(2)修改設(shè)計和代碼，以排除錯誤；

(3)進(jìn)行回歸測試，防止引進(jìn)新的錯誤。

軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指

通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段，

而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：

(1)強行排錯法；(設(shè)置斷點、程序暫停、監(jiān)視表達(dá)式

等)

(2)回溯法；

(3)原因排除法。

-22-

全國計算機等級考試公共基礎(chǔ)知識

第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)

4.1數(shù)據(jù)庫系統(tǒng)的基本概念

數(shù)據(jù)：實際上就是描述事物的符號記錄。

數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之分，如整型、實

型、字符型等。而數(shù)據(jù)的值給出了符合定型的值，如整型值

15o

數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)

一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程

序共享。

數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有

集成與共享的特點。

數(shù)據(jù)庫管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組

織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)

庫的核心。

數(shù)據(jù)庫管理系統(tǒng)功能：

（1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架；

（2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)

建提供有效的存取方法與手段；

（3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方便，如

查詢、插入、修改、刪除等以及簡單的算術(shù)運算及統(tǒng)計;

（4）數(shù)據(jù)的完整性、安生性定義與檢查；

（5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)；

（6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分

析等。

為完成以上六個功能，數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語

言：

（1）數(shù)據(jù)定義語言（DDL）：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)

據(jù)的物理存取構(gòu)建；

-23-

全國計算機等級考試公共基礎(chǔ)知識

（2）數(shù)據(jù)操縱語言（DML）：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢

與增、刪、改等；

（3）數(shù)據(jù)控制語言（DCL）：負(fù)責(zé)數(shù)據(jù)完整性、安全性

的定義與檢查以及并發(fā)控制、故障恢復(fù)等。

數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令

（又稱自含型或自主型語言）宿主型語言（一般可嵌入某些宿主

語言中）。

目前流行的數(shù)據(jù)庫管理系統(tǒng)都是關(guān)系數(shù)據(jù)庫系統(tǒng)，如

ORACLE、PowerBuider、SqlServer.VisualFoxpro和Access

等。

數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護、監(jiān)視等

的專業(yè)管理人員。

數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟

件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺

（軟件）五個部分構(gòu)成的運行實體。

數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三

者組成。

文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，

但是它無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。

層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提

供了有力支撐。

關(guān)系數(shù)據(jù)庫系統(tǒng)階段

數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性

與低冗余性、數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）、數(shù)據(jù)

統(tǒng)一管理與控制。

數(shù)據(jù)庫系統(tǒng)的三級模式：

（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述,

全體用戶公共數(shù)據(jù)視圖；

（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視

圖，也就是用戶所見到的數(shù)據(jù)模式;

(3)內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲

結(jié)構(gòu)與物理存取方

-24-

全國計算機等級考試公共基礎(chǔ)知識

法。

數(shù)據(jù)庫系統(tǒng)的兩級映射：

(1)概念模式到內(nèi)模式的映射；

(2)外模式到概念模式的映射。

4.2數(shù)據(jù)模型

數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述

了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信

息表與操作提供一個抽象的框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作

及數(shù)據(jù)約束。

E-R模型的基本概念

(1)實體：現(xiàn)實世界中的事物；

(2)屬性：事物的特性；

(3)聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有

一對一、一對多、多對多的聯(lián)系。

E-R模型三個基本概念之間的聯(lián)接關(guān)系：實體是概念世界

中的基本單位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。

一個實體的所有屬性值叫元組。

E-R模型的圖示法：(1)實體集表示法；(2)屬性表法;

(3)聯(lián)系表不法。

層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點：

(1)每棵樹有且僅有一個無雙親結(jié)點，稱為根；

(2)樹中除根外所有結(jié)點有且僅有一個雙親。

從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。

關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元

組組成。一個二維表就是一個關(guān)系。

-25-

全國計算機等級考試公共基礎(chǔ)知識

在二維表中凡能唯一標(biāo)識元組的最小屬性稱為鍵或碼。從

所有侯選健中選取一個作為用戶使用的鍵稱主鍵。表A中的

某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。

關(guān)系中的數(shù)據(jù)約束：

(1)實體完整性約束：約束關(guān)系的主鍵中屬性值不能為

空值；

(2)參照完全性約束：是關(guān)系之間的基本約束;

（3）用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)

的語義要求。

4.3關(guān)系代數(shù)

關(guān)系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之

上，有很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為

著名的是關(guān)系代數(shù)與關(guān)系演算。

關(guān)系模型的基本運算：

（1）插入（2）刪除⑶修改（4）查詢（包括投影、選擇、

笛卡爾積運算）

1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那

些符合指定條件的記錄挑出來。

2）投影：投影是從所有字段中選取一部分字段及其值進(jìn)

行操作，它是一種縱向操作。

3）聯(lián)接：聯(lián)接將兩個關(guān)系模式拼接成一個更寬的關(guān)系模

式，生成的新關(guān)系中包含滿足聯(lián)接條件的元組。

4.4數(shù)據(jù)庫設(shè)計與管理

數(shù)據(jù)庫設(shè)計是數(shù)據(jù)應(yīng)用的核心。

數(shù)據(jù)庫設(shè)計的兩種方法：

（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；

-26-

全國計算機等級考試公共基礎(chǔ)知識

（2）面向過程：以處理需求為主，兼顧信息需求。

數(shù)據(jù)庫設(shè)計階段包括：需求分析、概念分析、邏輯設(shè)計、

物理設(shè)計。

1）需求分析階段：這是數(shù)據(jù)庫設(shè)計的第一個階段，任務(wù)

主要是收集和分析數(shù)

據(jù)，這一階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計

概念結(jié)構(gòu)的基礎(chǔ)。

2）概念設(shè)計階段：分析數(shù)據(jù)間內(nèi)在語義關(guān)聯(lián)，在此基礎(chǔ)

上建立一個數(shù)據(jù)的抽

象模型，即形成E-R圖。

3）邏輯設(shè)計階段：將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)

系模式。

4）物理設(shè)計階段：對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇

合理的存取路徑，以

提高數(shù)據(jù)庫訪問速度及有效利用存儲空間。

需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒?。結(jié)構(gòu)化分析

（簡稱SA）方法用自頂向下、逐層分解的方式分析系統(tǒng)。用

數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過程的關(guān)系。對數(shù)據(jù)庫設(shè)計來講，數(shù)

據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。

數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個部分：數(shù)據(jù)項、

數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以是數(shù)據(jù)項，也可以是數(shù)據(jù)結(jié)構(gòu)）、數(shù)

據(jù)存儲、處理過程。

數(shù)據(jù)庫概念設(shè)計的目的是分析數(shù)據(jù)內(nèi)在語義關(guān)系。設(shè)計的

方法有兩種

（1）集中式模式設(shè)計法（適用于小型或并不復(fù)雜的單位

或部門）；

（2）視圖集成設(shè)計法。

設(shè)計方法：E-R模型與視圖集成。

視圖設(shè)計一般有三種設(shè)計次序：自頂向下、由底向上、由

內(nèi)向外。

視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約

束沖突。

關(guān)系視圖設(shè)計：關(guān)系視圖的設(shè)計又稱外模式設(shè)計。

關(guān)系視圖的主要作用：

-27-

全國計算機等級考試公共基礎(chǔ)知識

（1）提供數(shù)據(jù)邏輯獨立性；

（2）能適應(yīng)用戶對數(shù)據(jù)的不同需求；

（3）有一定數(shù)據(jù)保密功能。

數(shù)據(jù)庫的物理設(shè)計主要目標(biāo)是對數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整

并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度有效利用存儲

空間。一般RDBMS中留給用戶參與物理設(shè)計的內(nèi)容大致有索

引設(shè)計、集成簇設(shè)計和分區(qū)設(shè)計。

數(shù)據(jù)庫管理的內(nèi)容：

(1)數(shù)據(jù)庫的建立；

(2)數(shù)據(jù)庫的調(diào)整；

(3)數(shù)據(jù)庫的重組；

(4)數(shù)據(jù)庫安全性與完整性控制；

(5)數(shù)據(jù)庫的故障恢復(fù)；

(6)數(shù)據(jù)庫監(jiān)控。

-28-

全國計算機等級考試公共基礎(chǔ)知識

二級公共基礎(chǔ)知識試題匯編

一、選擇題(80道)

1.下面敘述正確的是O

A.算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

B.算法的空間復(fù)雜度是指算法程序中指令(或語句)的條

數(shù)

C.算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終

D.以上三種描述都不對

2.以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是o

A.隊列

A.8

B.線性表C.二叉樹

D.15

D.棧

3.在一棵二叉樹上第5層的結(jié)點數(shù)最多是o

B.16C.32

4.下面描述中，符合結(jié)構(gòu)化程序設(shè)計風(fēng)格的是o

A.使用順序、選擇和重復(fù)（循環(huán)）三種基本控制結(jié)構(gòu)表示

程序的控制邏輯

B.模塊只有一個入口，可以有多個出口

C.注重提高程序的執(zhí)行效率

D.不使用goto語句

5.下面概念中，不屬于面向?qū)ο蠓椒ǖ氖莖

A.對象B.繼承C.類D.過程調(diào)用

6.在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖（DFD）作為描述工具

的軟件開發(fā)階段是

A.可行性分析B.需求分析C.詳細(xì)設(shè)計D.程序編碼

7.在軟件開發(fā)中，下面任務(wù)不屬于設(shè)計階段的是o

A.數(shù)據(jù)結(jié)構(gòu)設(shè)計

C.定義模塊算法

B.給出系統(tǒng)模塊結(jié)構(gòu)

D.定義需求并建立系統(tǒng)模型

8.數(shù)據(jù)庫系統(tǒng)的核心是o

-29-

全國計算機等級考試公共基礎(chǔ)知識

A.數(shù)據(jù)模型B.數(shù)據(jù)庫管理系統(tǒng)C.軟件工具D.數(shù)據(jù)庫9.下

列敘述中正確的是O

A.數(shù)據(jù)庫是一個獨立的系統(tǒng)，不需要操作系統(tǒng)的支持

B.數(shù)據(jù)庫設(shè)計是指設(shè)計數(shù)據(jù)庫管理系統(tǒng)

C.數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)共享的問題

D.數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)必須與邏輯結(jié)構(gòu)一致

10.下列模式中，能夠給出數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存

取方法的是O

A.內(nèi)模式B.外模式C.概念模式D.邏輯模式

B.算法程序的長度

D.算法程序中的指令條數(shù)11.算法的時間復(fù)雜度是指

A.執(zhí)行算法程序所需要的時間

C.算法執(zhí)行過程中所需要的基本運算次數(shù)

12.下列敘述中正確的是o

A.線性表是線性結(jié)構(gòu)B.棧與隊列是非線性結(jié)構(gòu)

D.二叉樹是線性結(jié)構(gòu)

D.351

C.線性鏈表是非線性結(jié)構(gòu)

A.349B.350C.255

13.設(shè)一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中

的葉子結(jié)點數(shù)為o14.結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是

A.程序的規(guī)模B.程序的易讀性

D.程序的可移植性C.程序的執(zhí)行效率

15.在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什

么和必須具備哪些功能

的階段是o

A.概要設(shè)計B.詳細(xì)設(shè)計C.可行性分析D.需求分析

16.數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型，數(shù)據(jù)流

圖由一些特定的圖符構(gòu)

成。下列圖符名標(biāo)識的圖符不屬于數(shù)據(jù)流圖合法圖符的是

A.控制流B.加工C.數(shù)據(jù)存儲D.源和潭

17.軟件需求分析階段的工作，可以分為四個方面：需求

獲取、需求分析、編寫

需求規(guī)格說明書以及O

A.階段性報告B.需求評審C.總結(jié)

-30-

D.都不正確

全國計算機等級考試公共基礎(chǔ)知識

18.下述關(guān)于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是o

A.數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余

B.數(shù)據(jù)庫系統(tǒng)避免了一切冗余

C.數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類型的一致

D.數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)

19.關(guān)系表中的每一橫行稱為一個o

A.元組B.字段C.屬性D.碼

20.數(shù)據(jù)庫設(shè)計包括兩個方面的設(shè)計內(nèi)容，它們是

A.概念設(shè)計和邏輯設(shè)計

B.模式設(shè)計和內(nèi)模式設(shè)計

C.內(nèi)模式設(shè)計和物理設(shè)計

D.結(jié)構(gòu)特性設(shè)計和行為特性設(shè)計

21.算法的空間復(fù)雜度是指。

A.算法程序的長度

B.算法程序中的指令條數(shù)

C.算法程序所占的存儲空間

D.算法執(zhí)行過程中所需要的存儲空間

22.下列關(guān)于棧的敘述中正確的是o

A.在棧中只能插入數(shù)據(jù)

B.在棧中只能刪除數(shù)據(jù)

C.棧是先進(jìn)先出的線性表

D.棧是先進(jìn)后出的線性表

23.在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為

A.32B.31C.16D.15

24.對建立良好的程序設(shè)計風(fēng)格，下面描述正確的是

A.程序應(yīng)簡單、清晰、可讀性好

-31-

全國計算機等級考試公共基礎(chǔ)知識

B.符號名的命名要符合語法

C.充分考慮程序的執(zhí)行效率

D.程序的注釋可有可無

25.下面對對象概念描述錯誤的是o

A.任何對象都必須有繼承性

B.對象是屬性和方法的封裝體

C.對象間的通訊靠消息傳遞

D.操作是對象的動態(tài)性屬性

26.下面不屬于軟件工程的3個要素的是o

A.工具B.過程C.方法D.環(huán)境

D.組成關(guān)系

27.程序流程圖（PFD）中的箭頭代表的是o

A.數(shù)據(jù)流B.控制流C.調(diào)用關(guān)系

28.在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)歷了人工管理階段、

文件系統(tǒng)階段和數(shù)據(jù)

庫系統(tǒng)階段。其中數(shù)據(jù)獨立性最高的階段是o

A.數(shù)據(jù)庫系統(tǒng)

A.關(guān)系模型

B.文件系統(tǒng)C.人工管理D.數(shù)據(jù)項管理

D.數(shù)據(jù)模型29.用樹形結(jié)構(gòu)來表示實體之間聯(lián)系的模型稱

為O

B.層次模型C.網(wǎng)狀模型

30.關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關(guān)系運算包括

A.排序、索引、統(tǒng)計

C.關(guān)聯(lián)、更新、排序

A.循環(huán)、分支、遞歸

C.循環(huán)、遞歸、選擇

B.選擇、投影、連接

D.顯示、打印、制表

B.順序、循環(huán)、嵌套

D.順序、選擇、循環(huán)

31.算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成

32.數(shù)據(jù)的存儲結(jié)構(gòu)是指o

A.數(shù)據(jù)所占的存儲空間量

B.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示

-32-

全國計算機等級考試公共基礎(chǔ)知識

C.數(shù)據(jù)在計算機中的順序存儲方式

D.存儲在外存中的數(shù)據(jù)

33.設(shè)有下列二叉樹：對此二叉樹中序遍歷的結(jié)果為

o（缺圖）

A.ABCDEFB.DBEAFCC.ABDECFD.DEBFCA

34.在面向?qū)ο蠓椒ㄖ校粋€對象請求另一對象為其服務(wù)

的方式是通過發(fā)送

A.調(diào)用語句

A.確認(rèn)測試

A.PAD

A.抽象

A.模式

B.命令C.口令D.消息

D.驗收測試

35.檢查軟件產(chǎn)品是否符合需求定義的過程稱為

B.集成測試

C.N-S

C.驗證測試

36.下列工具中屬于需求分析常用工具的是o

B.PFDD.DFD

D.信息隱蔽

37.下面不屬于軟件設(shè)計原則的是o

B.模塊化

B.內(nèi)模式

C.自底向上

C.外模式

38.索引屬于o

D.概念模式

D.二維表

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

A.樹結(jié)構(gòu)

A.屬性

B.網(wǎng)結(jié)構(gòu)C.線性表

D.域

D.擁有足夠的情報

C.選擇類排序法D.建堆排序40.將E-R圖轉(zhuǎn)換到關(guān)系模式

時，實體與聯(lián)系都可以表示成o

B.關(guān)系C.鍵

41.在下列選項中，哪個不是一個算法一般應(yīng)該具有的基

本特征o

A.確定性B.可行性C.無窮性

42.希爾排序法屬于哪一種類型的排序法。

A.交換類排序法

法

43.下列關(guān)于隊列的敘述中正確的是o

A.在隊列中只能插入數(shù)據(jù)

C.隊列是先進(jìn)先出的線性表

B.在隊列中只能刪除數(shù)據(jù)

B.插入類排序法

D.隊列是先進(jìn)后出的線性表

44.對長度為N的線性表進(jìn)行順序查找，在最壞情況下所

需要的比較次數(shù)為

-33-

全國計算機等級考試公共基礎(chǔ)知識

A.N+1B.NC.(N+l)/2D.N/2

C.模塊類型劃分D.模擬耦合度45.信息隱蔽的概念與下述

哪一種概念直接相關(guān)O

A.軟件結(jié)構(gòu)定義B.模塊獨立性

46.面向?qū)ο蟮脑O(shè)計方法與傳統(tǒng)的的面向過程的方法有本

質(zhì)不同，它的基本原理

是o

A.模擬現(xiàn)實世界中不同事物之間的聯(lián)系

B.強調(diào)模擬現(xiàn)實世界中的算法而不強調(diào)概念

C.使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問

題

D.鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領(lǐng)域的概

念去思考47.在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開

發(fā)中的階段是o

A.詳細(xì)設(shè)計

A.發(fā)現(xiàn)錯誤

能

49.按條件f對關(guān)系R進(jìn)行選擇，其關(guān)系代數(shù)表達(dá)式為

A.R|X|RC.6f(R)D，nf(R)B.R|X|R

50.數(shù)據(jù)庫概念設(shè)計的過程中，視圖設(shè)計一般有三種設(shè)計

次序，以下各項中不對

的是o

A.自頂向下

A.查詢方法

排序方法

52.棧和隊列的共同點是o

A.都是先進(jìn)后出B.都是先進(jìn)先出

D.沒有共同點

B.由底向上

B.加工方法

C.由內(nèi)向外D.由整體到局部

D.

B.需求分析

B.改正錯誤

C.總體設(shè)計D.編程調(diào)試

D.挖掘軟件的潛48.軟件調(diào)試的目的是o

C.改善軟件的性能

51.在計算機中，算法是指o

C.解題方案的準(zhǔn)確而完整的描述

C.只允許在端點處插入和刪除元素

53.已知二叉樹后序遍歷序列是dabec,中序遍歷序列是

debac,它的前序遍歷序

列是O

-34-

全國計算機等級考試公共基礎(chǔ)知識

A.cedbaB.acbedC.decabD.deabc

D.歸并排序

54.在下列幾種排序方法中，要求內(nèi)存量最大的是

A.插入排序B.選擇排序C.快速排序

55.在設(shè)計程序時，應(yīng)采納的原則之一是o

A.程序結(jié)構(gòu)應(yīng)有助于讀者理解

C.減少或取消注解行

A.強行排錯法

B.不限制goto語句的使用

D.程序越短越好

C.回溯法D.原因排除法

56.下列不屬于軟件調(diào)試技術(shù)的是o

B.集成測試法

57.下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是

A.便于用戶、開發(fā)人員進(jìn)行理解和交流

B.反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)

和依據(jù)

C.作為確認(rèn)測試和驗收的依據(jù)

D.便于開發(fā)人員進(jìn)行需求分析

58.在數(shù)據(jù)流圖（DFD）中，帶有名字的箭頭表示

A.控制程序的執(zhí)行順序

C.數(shù)據(jù)的流向

B.模塊之間的調(diào)用關(guān)系

D.程序的組成成分

B.結(jié)構(gòu)化控制語言

D.結(jié)構(gòu)化操縱語言

C.由內(nèi)向外

C.邏輯結(jié)構(gòu)

D.自底向上

D.物理和存儲結(jié)構(gòu)59.SQL語言又稱為o

A.結(jié)構(gòu)化定義語言

C.結(jié)構(gòu)化查詢語言

A.自頂向下

A.存儲結(jié)構(gòu)

60.視圖設(shè)計一般有3種設(shè)計次序，下列不屬于視圖設(shè)計

的是o

B.由外向內(nèi)

B.物理結(jié)構(gòu)

61.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的

62.棧底至棧頂依次存放元素A、B、C、D,在第五個元

素E入棧前，棧中元素

可以出棧，則出棧序列可能是O

A.ABCEDB.DBCEAC.CDABED.DCBEA

63.線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別

是o

-35-

全國計算機等級考試公共基礎(chǔ)知識

A.順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

順序存取的存儲結(jié)構(gòu)

C.隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)

構(gòu)、任意存取的存儲結(jié)構(gòu)

64.在單鏈表中，增加頭結(jié)點的目的是o

A.方便運算的實現(xiàn)

B.隨機存取的存儲結(jié)構(gòu)、

D.任意存取的存儲結(jié)

B.使單鏈表至少有一個結(jié)點

D.說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn)C.標(biāo)識表結(jié)點中

首結(jié)點的位置

65.軟件設(shè)計包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設(shè)計，其

中軟件的過程設(shè)計是指

A.模塊間的關(guān)系

C.軟件層次結(jié)構(gòu)

B.系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述

D.軟件開發(fā)過程

66.為了避免流程圖在描述程序邏輯時的靈活性，提出了

用方框圖來代替?zhèn)鹘y(tǒng)的

程序流程圖，通常也把這種圖稱為O

A.PAD圖

A.數(shù)據(jù)

B.N-S圖C.結(jié)構(gòu)圖

C.數(shù)據(jù)項

D.數(shù)據(jù)流圖

D.數(shù)據(jù)結(jié)構(gòu)

67.數(shù)據(jù)處理的最小單位是o

B.數(shù)據(jù)元素

68.下列有關(guān)數(shù)據(jù)庫的描述，正確的是o

A.數(shù)據(jù)庫是一個DBF文件B.數(shù)據(jù)庫是一個關(guān)系

D.數(shù)據(jù)庫是一組文件

D.存儲模式

D.軟件系統(tǒng)

C.數(shù)據(jù)庫是一個結(jié)構(gòu)化的數(shù)據(jù)集合

A.外模式B.概念模式

69.單個用戶使用的數(shù)據(jù)視圖的描述稱為.

C.內(nèi)模式

70.需求分析階段的任務(wù)是確定。

A.軟件開發(fā)方法

功能

71.算法分析的目的是o

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

系

-36-

B.軟件開發(fā)工具C.軟件開發(fā)賽用

B.找出算法中輸入和輸出之間的關(guān)

全國計算機等級考試公共基礎(chǔ)知識

C.分析算法的易懂性和可靠性

A.n-lB.n(n-l)C.n

D.分析算法的效率以求改進(jìn)72.n個頂點的強連通圖的邊

數(shù)至少有o

D.n+1

73.已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，為節(jié)省

時間，應(yīng)采用的算法是

A.堆排序B.直接插入排序C.快速排序D.直接選擇排序74.

用鏈表表示線性表的優(yōu)點是O

A.便于插入和刪除操作

同

C.花費的存儲空間較順序存儲少

A.數(shù)據(jù)流圖B.數(shù)據(jù)字典

D.便于隨機存取

D.PAD圖

B.數(shù)據(jù)元素的物理順序與邏輯順序相75.下列不屬于結(jié)構(gòu)

化分析的常用工具的是O

C.判定樹

76.軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分

成O

A.定義、開發(fā)、運行維護B.設(shè)計階段、編程階段、測試

階段

D.需求分析、功能定義、系統(tǒng)設(shè)計C.總體設(shè)計、詳細(xì)設(shè)

計、編程調(diào)試

77.在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)

構(gòu)。此方法將程序看做

是o

A.循環(huán)的集合B.地址的集合C.路徑的集合D.目標(biāo)的集合

78.在數(shù)據(jù)管理技術(shù)發(fā)展過程中，文件系統(tǒng)與數(shù)據(jù)庫系統(tǒng)

的主要區(qū)別是數(shù)據(jù)庫系

統(tǒng)具有o

A.數(shù)據(jù)無冗余

據(jù)模型

79.分布式數(shù)據(jù)庫系統(tǒng)不具有的特點是o

A.分布式B.數(shù)據(jù)冗余

D.位置透明性和復(fù)制透明性

C.數(shù)據(jù)查詢D.數(shù)據(jù)約束

B.數(shù)據(jù)可共享C.專門的數(shù)據(jù)管理軟件D.特定的數(shù)

C.數(shù)據(jù)分布性和邏輯整體性

A.數(shù)據(jù)結(jié)構(gòu)

80.下列說法中，不屬于數(shù)據(jù)模型所描述的內(nèi)容的是

B.數(shù)據(jù)操作

-37-

全國計算機等級考試公共基礎(chǔ)知識

二、填空題(40道)

(1)算法的復(fù)雜度主要包括復(fù)雜度和空間復(fù)雜度。

(2)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為

數(shù)據(jù)的