全國計算機(jī)二級VB公共基礎(chǔ)知識總匯

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

經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，筆試部分經(jīng)

?？疾榈氖撬惴◤?fù)雜度、數(shù)據(jù)結(jié)構(gòu)的概念、棧、二叉樹的遍歷、二分

法查找，讀者應(yīng)對此部分進(jìn)行重點學(xué)習(xí)。

詳細(xì)重點學(xué)習(xí)知識點：

1.算法的概念、算法時間復(fù)雜度及空間復(fù)雜度的概念

2.數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輯結(jié)構(gòu)及物理結(jié)構(gòu)的定義

3.棧的定義及其運算、線性鏈表的存儲方式

4.樹與二叉樹的概念、二叉樹的基本性質(zhì)、完全二叉樹的概念、

二叉樹的遍歷

5.二分查找法

6.冒泡排序法

1.1算法

考點1算法的基本概念

考試鏈接：

考點1在筆試考試中考核的兒率為30%,主要是以填空題的形式出現(xiàn),

分值為2分，此考點為識記內(nèi)容，讀者還應(yīng)該了解算法中對數(shù)據(jù)的基本

運算。

計算機(jī)解題的過程實際上是在實施某種算法，這種算法稱為計算

機(jī)算法。

1.算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報。

2.算法的基本要素：

(1)算法中對數(shù)據(jù)的運算和操作

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

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

在一般的計算機(jī)系統(tǒng)中，基本的運算和操作有以下4類：算術(shù)運算、

邏輯運算、關(guān)系運算和數(shù)據(jù)傳輸。

(2)算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序稱為算法的

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

描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述

語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)

組合而成。

考點2算法復(fù)雜度

考試鏈接：

考點2在筆試考試中，是一個經(jīng)常考查的內(nèi)容，在筆試考試中出現(xiàn)的

幾率為70%,主要是以選擇的形式出現(xiàn)，分值為2分，此考點為重點識

記內(nèi)容，讀者還應(yīng)該識記算法時間復(fù)雜度及空間復(fù)雜度的概念。

1.算法的時間復(fù)雜度

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

同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，

或者在不同的計算機(jī)上運行，效率均不同。這表明使用絕對的時間單

位衡量算法的效率是不合適的。撇開這些與計算機(jī)硬件、軟件有關(guān)的

因素，可以認(rèn)為一個特定算法〃運行工作量〃的大小，只依賴于問題的

規(guī)模(通常用整數(shù)n表示)，它是問題規(guī)模的函數(shù)。即

算法的工作量=f(n)

2.算法的空間復(fù)雜度

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

一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初

始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中

額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所

需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，

則稱該算法是原地工作的。在許多實際問題中，為了減少算法所占的

存儲空間，通常采用壓縮存儲技術(shù)，以便盡量減少不必要的額外空間。

?疑難解答：算法的工作量用什么來計算？

算法的工作量用算法所執(zhí)行的基本運算次數(shù)來計算，而算法所執(zhí)

行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=￡(n),其中

n是問題的規(guī)模。

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

考點3數(shù)據(jù)結(jié)構(gòu)的定義

考試鏈接：

考點3在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的

幾率為70%,主要是以選擇的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)

容，讀者還應(yīng)該識記數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的概念。

數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究和討論以下三個方面:

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

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

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

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

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

數(shù)據(jù)：是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸

入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整

體進(jìn)行考慮和處理。

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用

一個數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏

輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)

系，它反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。一個數(shù)據(jù)結(jié)

構(gòu)可以表示成

B=(D,R)

其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系,

一般用二元組來表示。

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

結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))。

由于數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系可能與邏輯關(guān)系不

同，因此，為了表示存放在計算機(jī)存儲空間中的各數(shù)據(jù)元素之間的邏

輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)

元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的

存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，

其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時，選擇合適的

存儲結(jié)構(gòu)是很重要的。

考點4線性結(jié)構(gòu)與非線性結(jié)構(gòu)

考試鏈接：

考點4在筆試考試中，雖然說不是考試經(jīng)?？疾榈膬?nèi)容，但讀者還是

對此考點有所了解，在筆試考試中出現(xiàn)的幾率為30%,主要是以填空題

出現(xiàn)的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容。

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

數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)

據(jù)結(jié)構(gòu)滿足下列兩個條件：

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

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

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個線性

結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)

構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。

?疑難解答：空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)?

一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這

要根據(jù)具體情況來確定。如果對該數(shù)據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)

則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。

1.3棧及線性鏈表

考點5棧及其基本運算

考試鏈接：

考點5在筆試考試中，是一個必考的內(nèi)容，在筆試考試中出現(xiàn)的兒率

為100%,主要是以選擇的形式出現(xiàn)，分值為2分，此考點為重點掌握內(nèi)

容，讀者應(yīng)該掌握棧的運算。

1.棧的基本概念

棧是限定只在一端進(jìn)行插入與刪除的線性表，通常稱插入、刪除

的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時稱為空棧。棧頂

元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總

是最先被插入的元素，從而也是最后才能被刪除的元素。棧是按照“

先進(jìn)后出〃或"后進(jìn)先出〃的原則組織數(shù)據(jù)的。

2.棧的順序存儲及其運算

用一維數(shù)組S（1：m）作為棧的順序存儲空間，其中m為最大容量。

在棧的順序存儲空間S（1：m）中，S（bottom）為棧底元素，S

（top）為棧頂元素。top=0表示?？?；top=m表示棧滿。

棧的基本運算有三種：入棧、退棧與讀棧頂元素。

（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先

將棧頂指針加一（即top加1）,然后將新元素插入到棧頂指針指向的

位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g

已滿，不可能再進(jìn)行入棧操作。這種情況稱為?！ㄉ弦纭ㄥe誤。

（2）退棧運算：退棧是指取出棧頂元素并賦給一個指定的變量。

首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后

將棧頂指針減一（即top減1）。當(dāng)棧頂指針為0時，說明棧空，不可進(jìn)

行退棧操作。這種情況稱為棧的〃下溢“錯誤。

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

量。這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指

針不會改變。當(dāng)棧頂指針為。時，說明棧空，讀不到棧頂元素。

?小技巧：棧是按照〃先進(jìn)后出〃或〃后進(jìn)先出”的原則組織數(shù)據(jù)，

但是出棧方式有多種選擇，在考題中經(jīng)?？疾楦鞣N不同的出棧方式。

考點6線性鏈表的基本概念

考試鏈接：

考點6在筆試考試中出現(xiàn)的幾率為30%,主要是以選擇的形式出現(xiàn)，

分值為2分，此考點為識記內(nèi)容。重點識記結(jié)點的組成。

在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點由兩部分組成：一部分用于存

放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。

其中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。

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

（1）線性鏈表

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。

在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱

為左指針，用以指向其前件結(jié)點；另一個稱為右指針，用以指向其后

件結(jié)點。這樣的表稱為雙向鏈表。

(2)帶鏈的棧

棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。帶鏈的?？梢杂脕硎?/p>

集計算機(jī)存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用

棧。

?疑難解答：在鏈?zhǔn)浇Y(jié)構(gòu)中，存儲空間位置關(guān)系與邏輯關(guān)系是什么？

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

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

素之間的邏輯關(guān)系是由指針域來確定的。

1.4樹與二叉樹

考點7樹與二叉樹及其基本性質(zhì)

考試鏈接：

考點7在筆試考試中，是一個必考的內(nèi)容，在筆試考試中出現(xiàn)的幾率

為100%,主要是以選擇的形式出現(xiàn)，有時也有出現(xiàn)在填空題中，分值為

2分，此考點為重點掌握內(nèi)容。重點識記樹及二叉樹的性質(zhì)。

誤區(qū)警示：

滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應(yīng)該

注意二者的區(qū)別。

1、樹的基本概念

樹(tree)是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個結(jié)點只

有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)

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

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

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

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

2、二叉樹及其基本性質(zhì)

(1)二叉樹的定義

二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個特點：

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

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

子樹。

由以上特點可以看出，在二叉樹中，每一個結(jié)點的度最大為2,即

所有子樹(左子樹或右子樹)也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)

點的度可以是任意的。另外，二叉樹中的每個結(jié)點的子樹被明顯地分

為左子樹和右子樹。在二叉樹中，一個結(jié)點可以只有左子樹而沒有右

子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個結(jié)點既沒有左子樹也

沒有右子樹時，該結(jié)點即為葉子結(jié)點。

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

二叉樹具有以下幾個性質(zhì)：

性質(zhì)1：在二叉樹的第k層上，最多有2kT(k^l)個結(jié)點；

性質(zhì)2：深度為m的二叉樹最多有2m-1個結(jié)點；

性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是

比度為2的結(jié)點多一個。

性質(zhì)4：具有n個結(jié)點的二叉樹，其深度至少為［log2n］+1,其中

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

，小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是

后序遍歷，二叉樹的葉子結(jié)點的先后順序都是不變的。

3、滿二叉樹與完全二叉樹

滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所

有結(jié)點都有兩個子結(jié)點。在滿二叉樹中，每一層上的結(jié)點數(shù)都達(dá)到最

大值，即在滿二叉樹的第k層上有2kT個結(jié)點，且深度為m的滿二叉樹

有2m—1個結(jié)點。

完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點

數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。

對于完全二叉樹來說，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn):

對于任何一個結(jié)點，若其右分支下的子孫結(jié)點的最大層次為P，則其

左分支下的子孫結(jié)點的最大層次或為P，或為P+1。

完全二叉樹具有以下兩個性質(zhì)：

性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為［log.nl+10

性質(zhì)6:設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層次（每

一層從左到右）用自然數(shù)1,2,……，n給結(jié)點進(jìn)行編號，則對于編

號為k（k=l,2,....，n）的結(jié)點有以下結(jié)論：

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

的父結(jié)點編號為INT(k/2)o

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

無左子結(jié)點(顯然也沒有右子結(jié)點)。

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

結(jié)點無右子結(jié)點。

考點8二叉樹的遍歷

考試鏈接：

考點8在筆試考試中考核幾率為30%,分值為2分，讀者應(yīng)該熟練掌

握各種遍歷的具體算法，能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果。

在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在

先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷分為三類:

前序遍歷、中序遍歷和后序遍歷。

(1)前序遍歷：先訪問根結(jié)點、然后遍歷左子樹，最后遍歷右子

樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子

樹，最后遍歷右子樹。

(2)中序遍歷：先遍歷左子樹、然后訪問根結(jié)點，最后遍歷右子

樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)

點，最后遍歷右子樹。

(3)后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)

點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子

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

?疑難解答：樹與二叉樹的不同之處是什么？

在二叉樹中，每一個結(jié)點的度最大為2,即所有子樹(左子樹或右

子樹)也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。

1.5查找技術(shù)

考點9順序查找

考試鏈接：

考點9在筆試考試中考核幾率在30%,一般出現(xiàn)選擇題中，分值為2

分，讀者應(yīng)該具體掌握順序查找的算法。

查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性

表的第一個元素開始，依次將線性表中的元素與被查找的元素相比

較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素

進(jìn)行了比較但都不相等，則表示查找失敗。

在下列兩種情況下也只能采用順序查找：

(1)如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯?/p>

結(jié)構(gòu)，只能用順序查找。

(2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序

查找。

考點10二分法查找

考試鏈接：

考點10在筆試考試中考核幾率為30%,一般出現(xiàn)填空題中，分值為2

分,考核比較多查找的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。

二分法只適用于順序存儲的，按非遞減排列的有序表，其方法如

下：

設(shè)有序線性表的長度為n,被查找的元素為i,

(1)將i與線性表的中間項進(jìn)行比較；

(2)若i與中間項的值相等，則查找成功；

(3)若i小于中間項，則在線性表的前半部分以相同的方法查找;

(4)若i大于中間項，則在線性表的后半部分以相同的方法查找。

?疑難解答：二分查找法適用于哪種情況？

二分查找法只適用于順序存儲的有序表。在此所說的有序表是指

線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相

等)。

這個過程一直進(jìn)行到查找成功或子表長度為0為止。

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

log2n次。

1.6排序技術(shù)

考點11交換類排序法

考試鏈接：

考點11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為

30%,分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。

冒泡排序法和快速排序法都屬于交換類排序法O

(1)冒泡排序法

首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大

小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相

鄰元素中的大者往后移動，最后最大者到了線性表的最后。

然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大

小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相

鄰元素中的小者往前移動，最后最小者到了線性表的最前面。

對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此

時已經(jīng)排好序。

在最壞的情況下，冒泡排序需要比較次數(shù)為n(n-1)/2o

(2)快速排序法

它的基本思想是：任取待排序序列中的某個元素作為基準(zhǔn)(一般

取第一個元素)，通過一趟排序，將待排元素分為左右兩個子序列，

左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的

排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個子序列繼續(xù)進(jìn)行排

序，直至整個序列有序。

■疑難解答：冒泡排序和快速排序的平均執(zhí)行時間分別是多少？

冒泡排序法的平均執(zhí)行時間是0(n2),而快速排序法的平均執(zhí)行時

間是0(nlog2n)0

1.7例題詳解

一、選擇題

【例1】算法的時間復(fù)雜度取決于o(考點2)

A）問題的規(guī)模B）待處理的數(shù)據(jù)的初態(tài)

C）問題的難度D）A）和B）

解析：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，在同一個問題

規(guī)模下，而且與輸入數(shù)據(jù)有關(guān)。即與輸入數(shù)據(jù)所有的可能取值范圍、

輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。

答案：D）

【例2】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成o

（考點3）

A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B）線性結(jié)構(gòu)和非線性結(jié)

構(gòu)

C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

解析：邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線性結(jié)構(gòu)表示數(shù)

據(jù)元素之間為一對一的關(guān)系，非線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對多

或者多對一的關(guān)系，所以答案為B）。

答案：B）

【例3】以下不是棧的基本運算。（考點5）

A）判斷棧是否為素空B）將棧置為空棧

C）刪除棧頂元素D）刪除棧底元素

解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、

置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧

頂進(jìn)行的。

答案：D）

【例4】鏈表不具備的特點是o（考點6）

A）可隨機(jī)訪問任意一個結(jié)點B）插入和刪除不需

要移動任何元素

C）不必事先估計存儲空間D）所需空間與其長

度成正比

解析：順序表可以隨機(jī)訪問任意一個結(jié)點，而鏈表必須從第一個

數(shù)據(jù)結(jié)點出發(fā)，逐一查找每個結(jié)點。所以答案為A）。

答案：A）

【例5】已知某二叉樹的后序遍歷序列是DACBE,中序遍歷序列是

DEBAC,則它的前序遍歷序列是o（考點8）

A）ACBEDB）DEABC

C）DECABD）EDBAC

解析：后序遍歷的順序是〃左子樹一右子樹一根結(jié)點”；中序遍歷

順序是〃左子樹一根結(jié)點一右子樹〃；前序遍歷順序是〃根結(jié)點一左子

樹一右子樹根據(jù)各種遍歷算法，不難得出前序遍歷序列是EDBAC。

所以答案為D）。

答案：D）

【例6】設(shè)有一個已按各元素的值排好序的線性表（長度大于2）,

對給定的值k,分別用順序查找法和二分查找法查找一個與k相等的元

素，比較的次數(shù)分別是s和b,在查找不成功的情況下，s和b的關(guān)系是

（,（考點9）

A)s=bB)s>bC)s<bD)s

2b

解析：對于順序查找，查找不成功時和給定關(guān)鍵字比較的次數(shù)為

n+U二分查找查找不成功的關(guān)鍵字比較次數(shù)為[log2n]+lo當(dāng)n22

時，顯然n+l>[log2n]+lo

答案：B）

【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）

分成左、右兩個子表，考慮這兩個子表，下列結(jié)論一定正確的是

o（考點11）

A）左、右兩個子表都已各自排好序

B）左邊子表中的元素都不大于右邊子表中的元素

C）左邊子表的長度小于右邊子表的長度

D）左、右兩個子表中元素的平均值相等

解析：快速排序基本思想是：任取待排序表中的某個元素作為基

準(zhǔn)（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個

子表，左子表元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子表

的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個子表繼續(xù)進(jìn)行排

序，直至整個表有序。

答案：B）

二、填空題

【例1】問題處理方案的正確而完整的描述稱為o（考點1）

解析：計算機(jī)解題的過程實際上是在實施某種算法，這種算法稱

為計算機(jī)算法。

答案：算法

【例2】一個空的數(shù)據(jù)結(jié)構(gòu)是按線性結(jié)構(gòu)處理的，則屬于o

（考點4）

解析：一個空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)或是非線性結(jié)構(gòu)，要根據(jù)具

體情況而定。如果對數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)來處理的，則屬于

線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。

答案：線性結(jié)構(gòu)

【例3】設(shè)樹T的度為4,其中度為1、2、3和4的結(jié)點的個數(shù)

分別為4、2、1、1,則T中葉子結(jié)點的個數(shù)為o（考點7）

解析：根據(jù)樹的性質(zhì)：樹的結(jié)點數(shù)等于所有結(jié)點的度與對應(yīng)的結(jié)點

個數(shù)乘積之和加1。

因此樹的結(jié)點數(shù)為1X4+2X2+3X1+4X1+1=16。

葉子結(jié)點數(shù)目等于樹結(jié)點總數(shù)減去度不為0的結(jié)點數(shù)之和，即16—

（4+2+1+1）=8o

答案：8

【例4】二分法查找的存儲結(jié)構(gòu)僅限于且是有序的。（考點

10）

解析：二分查找，也稱折半查找，它是一種高效率的查找方法。

但二分查找有條件限制：要求表必須用順序存儲結(jié)構(gòu)，且表中元素必

須按關(guān)鍵字有序（升序或降序均可）。

答案：順序存儲結(jié)構(gòu)

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

經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，筆試部分經(jīng)

常考查的是結(jié)構(gòu)化程序設(shè)計的原則、面向?qū)ο蠓椒ǖ幕靖拍?，讀者

應(yīng)對此部分進(jìn)行重點學(xué)習(xí)。

詳細(xì)重點學(xué)習(xí)知識點：

1.結(jié)構(gòu)化程序設(shè)計方法的四個原則

2.對象、類、消息、繼承的概念、類與實例的區(qū)別

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

考點1結(jié)構(gòu)化程序設(shè)計的原則

考試鏈接：

考點1在筆試考試中出現(xiàn)的幾率為30%,主要是以選擇題的形式出

現(xiàn)，分值為2分，此考點為識記內(nèi)容，讀者應(yīng)該識記結(jié)構(gòu)化程序設(shè)計方

法的四個主要原則。

20世紀(jì)70年代提出了〃結(jié)構(gòu)化程序設(shè)計〃的思想和方法。結(jié)構(gòu)化程

序設(shè)計方法引入了工程化思想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編

程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計方法的主要原則為：自頂向下、

逐步求精、模塊化和限制使用goto語句。

?疑難解答：如何進(jìn)行自頂向下設(shè)計方法？

程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后

考慮局部目標(biāo)；不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目

標(biāo)開始設(shè)計，逐步使問題具體化。

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

考點2面向?qū)ο蠓椒ǖ幕靖拍?/p>

考試鏈接：

考點2在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的

幾率為70%,主要是以填空題的形式出現(xiàn)，分值為2分，此考點為重點

識記內(nèi)容，讀者應(yīng)該識記幾個基本要素的定義、對象的特征以及消息、

繼承、類的定義。

誤區(qū)警示：

當(dāng)使用〃對象〃這個術(shù)語時，既可以指一個具體的對象，也可以泛指

一般的對象，但是當(dāng)使用〃實例〃這個術(shù)語時，必須是指一個具體的對象。

面向?qū)ο蠓椒êw對象及對象屬性與方法、類、繼承、多態(tài)性幾

個基本要素。

(1)對象

通常把對對象的操作也稱為方法或服務(wù)。

屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過

執(zhí)行對象的操作來改變。屬性值應(yīng)該指的是純粹的數(shù)據(jù)值，而不能指

對象。

操作描述了對象執(zhí)行的功能，若通過信息的傳遞，還可以為其他

對象使用。

對象具有如下特征：標(biāo)識惟一性、分類性、多態(tài)性、封裝性、模

塊獨立性。

（2）類和實例

類是具有共同屬性、共同方法的對象的集合。它描述了屬于該對

象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實例。

類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和

在數(shù)據(jù)上的一組合法操作。

（3）消息

消息是實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某

一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。

一個消息由三部分組成：接收消息的對象的名稱、消息標(biāo)識符（消

息名）和零個或多個參數(shù)。

（4）繼承

廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重

復(fù)定義它們。

繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個

父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指，一個類允許有多個父類。

（5）多態(tài)性

對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接

收時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。

?疑難解答：能舉一下現(xiàn)實中的對象及其屬性和操作嗎？

一輛汽車是一個對象，它包含了汽車的屬性（如顏色、型號等）

及其操作（如啟動、剎車等）。一個窗口是對象，它包含了窗口的

屬性（如大小、顏色等）及其操作（如打開、關(guān)閉等）。

2.3例題詳解

一、選擇題

【例1】結(jié)構(gòu)化程序設(shè)計方法提出于o(考點1)

A)20世紀(jì)50年代B)20世紀(jì)60年代

C)20世紀(jì)70年代D)20世紀(jì)80年代

解析：20世紀(jì)70年代提出了〃結(jié)構(gòu)化程序設(shè)計(structured

programming)〃的思想和方法。結(jié)構(gòu)化程序設(shè)計方法引入了工程化思

想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編程得到了極大的改善。

答案：O

【例2】結(jié)構(gòu)化程序設(shè)計方法的主要原則有下列4項，不正確的是

o(考點1)

A)自下向上B)逐步求精

C)模塊化D)限制使用goto語句

解析：結(jié)構(gòu)化程序設(shè)計方法的主要原則為：

(1)自頂向下：即先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，

后考慮局部目標(biāo)。

(2)逐步求精：對復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)作過渡，逐步細(xì)

化。

（3）模塊化：把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分

解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。

（4）限制使用goto語句。

答案:A）

【例3】面向?qū)ο蟮拈_發(fā)方法中，類與對象的關(guān)系是o（考

點2）

A）抽象與具體B）具體與抽象

C）部分與整體D）整體與部分

解析：現(xiàn)實世界中的很多事物都具有相似的性質(zhì)，把具有相似的

屬性和操作的對象歸為類，也就是說類是具有共同屬性、共同方法的

對象的集合，是對對象的抽象。它描述了該對象類型的所有對象的性

質(zhì)，而一個對象則是對應(yīng)類的一個具體實例。所以本題正確答案為A）

項。

答案：A）

二、填空題

【例1】在面向?qū)ο蠓椒ㄖ?，使用已?jīng)存在的類定義作為基礎(chǔ)建立

新的類定義，這樣的技術(shù)叫做o（考點2）

解析：繼承是面向?qū)ο蠓椒ǖ囊粋€主要特征。繼承是使用已有的類

定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)作基類來引用，則

新類相應(yīng)地可當(dāng)作派生類來引用。

答案：繼承

【例2】對象的基本特點包括、分類性、多態(tài)性、封裝性和

模塊獨立性好等5個特點。（考點2）

解析：對象具有如下的基本特點：

（1）標(biāo)識惟一性。對象是可區(qū)分的，并且由對象的內(nèi)在本質(zhì)來區(qū)

分；

（2）分類性。可以將具有相同屬性和操作的對象抽象成類；

（3）多態(tài)性。同一個操作可以是不同對象的行為；

（4）封裝性。只能看到對象的外部特征，無需知道數(shù)據(jù)的具體結(jié)

構(gòu)以及實現(xiàn)操作的算法；

（5）模塊獨立性。面向?qū)ο笫怯蓴?shù)據(jù)及可以對這些數(shù)據(jù)施加的操

作所組成的統(tǒng)一體。

答案：標(biāo)識惟一性

【例3】對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的

對象所接收時可能導(dǎo)致完全不同的行為，這種現(xiàn)象稱為o（考

點2）

解析：對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的

對象接收時可導(dǎo)致完全不同的行為，該現(xiàn)象稱為多態(tài)性。

答案：多態(tài)性

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

經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，筆試部分經(jīng)

?？疾榈氖擒浖芷?、軟件設(shè)計的基本原理，軟件測試的目的、

軟件調(diào)試的基本概念，讀者應(yīng)對此部分進(jìn)行重點學(xué)習(xí)。

詳細(xì)重點學(xué)習(xí)知識點：

1.軟件的概念、軟件生命周期的概念及各階段所包含的活動

2.概要設(shè)計與詳細(xì)設(shè)計的概念、模塊獨立性及其度量的標(biāo)準(zhǔn)、

詳細(xì)設(shè)計常用的工具

3.軟件測試的目的、軟件測試的4個步驟、

4.軟件調(diào)試的任務(wù)

3.1軟件工程基本概念

考點1軟件定義與軟件特點

考試鏈接：

考點1在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，考核的兒率為70%,

主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容，讀者應(yīng)

該識記軟件的定義，特點及其分類。

軟件指的是計算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、

數(shù)據(jù)和相關(guān)文檔的完整集合。程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)

的、用程序設(shè)計語言描述的、適合計算機(jī)執(zhí)行的指令序列。數(shù)據(jù)是使

程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序的開發(fā)、維護(hù)和使用

有關(guān)的圖文資料“可見，軟件由兩部分組成：

(1)機(jī)器可執(zhí)行的程序和數(shù)據(jù);

(2)機(jī)器不可執(zhí)行的，與軟件開發(fā)、運行、維護(hù)、使用等有關(guān)的

文檔。

軟件的特點：

(1)軟件是邏輯實體，而不是物理實體，具有抽象性；

(2)沒有明顯的制作過程，可進(jìn)行大量的復(fù)制；

(3)使用期間不存在磨損、老化問題；

(4)軟件的開發(fā)、運行對計算機(jī)系統(tǒng)具有依賴性；

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

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

根據(jù)應(yīng)用目標(biāo)的不同，軟件可分應(yīng)用軟件、系統(tǒng)軟件和支撐軟件

(或工具軟件)。

?小提示：應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件；系

統(tǒng)軟件是計算機(jī)管理自身資源，提高計算機(jī)使用效率并為計算機(jī)用戶

提供各種服務(wù)的軟件；支撐軟件是介于兩者之間，協(xié)助用戶開發(fā)軟件

的工具性軟件。

考點2軟件工程過程與軟件生命周期

考試鏈接：

考點2在筆試考試中，在筆試考試中出現(xiàn)的幾率為30%,主要是以選

擇題的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容，讀者應(yīng)該識記軟件

生命周期的定義，主要活動階段及其任務(wù)。

軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟

件生命周期。一般包括可行性分析研究與需求分析、設(shè)計、實現(xiàn)、測

試、交付使用以及維護(hù)等活動，如圖3—1所示。

圖3—1軟件生命周期

還可以將軟件生命周期分為如上圖所示的軟件定義、軟件開發(fā)和

軟件運行維護(hù)3個階段。

生命周期的主要活動階段是：可行性研究與計劃制定、需求分析、

軟件設(shè)計、軟件實施、軟件測試及運行與維護(hù)。

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

考點3軟件設(shè)計的基本概念

考試鏈接：

考點3在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，考核中幾率為70%,

主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為重點掌握內(nèi)容，讀

者應(yīng)該識記模塊獨立性中的耦合性和內(nèi)聚性。

誤區(qū)警示:

在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強，則耦合性越弱。軟件設(shè)計應(yīng)

盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)

聚性，有利于提高模塊的獨立性。

1.軟件設(shè)計的基礎(chǔ)

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

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

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

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

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

人之間如何通信；

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

從工程管理角度來看，軟件設(shè)計分兩步完成：概要設(shè)計和詳細(xì)設(shè)

計。

(1)概要設(shè)計將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級接口、

全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式；

(2)詳細(xì)設(shè)計確立每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)

方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。

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

(1)抽象：軟件設(shè)計中考慮模塊化解決方案時，可以定出多個抽

象級別。抽象的層次從概要設(shè)計到詳細(xì)設(shè)計逐步降低。

(2)模塊化：模塊是指把一個待開發(fā)的軟件分解成若干小的簡單

的部分。模塊化是指解決一個復(fù)雜問題時自頂向下逐層把軟件系統(tǒng)劃

分成若干模塊的過程。

（3）信息隱蔽：信息隱蔽是指在一個模塊內(nèi)包含的信息（過程或

數(shù)據(jù)），對于不需要這些信息的其他模塊來說是不能訪問的。

（4）模塊獨立性：模塊獨立性是指每個模塊只完成系統(tǒng)要求的獨

立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。模塊的獨立程

度是評價設(shè)計好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨立性使用耦合

性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn)。內(nèi)聚性是信息隱蔽和局部化概念的

自然擴(kuò)展。一個模塊的內(nèi)聚性越強則該模塊的模塊獨立性越強。一個

模塊與其他模塊的耦合性越強則該模塊的模塊獨立性越弱。

內(nèi)聚性是度量一個模塊功能強度的一個相對指標(biāo)。內(nèi)聚是從功能

角度來衡量模塊的聯(lián)系，它描述的是模塊內(nèi)的功能聯(lián)系。內(nèi)聚有如下

種類，它們之間的內(nèi)聚度由弱到強排列：偶然內(nèi)聚、邏輯內(nèi)聚、時間

內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。

耦合性是模塊之間互相連接的緊密程度的度量。耦合性取決于各

個模塊之間接口的復(fù)雜度、調(diào)用方式以及哪些信息通過接口。耦合可

以分為下列幾種，它們之間的耦合度由高到低排列：內(nèi)容耦合、公共

耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合。

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

秀的軟件設(shè)計，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合

性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨立性。

?小提示：上面僅是對耦合機(jī)制進(jìn)行的一個分類?？梢娨粋€模塊

與其他模塊的耦合性越強則該模塊獨立性越弱。原則上講，模塊化設(shè)

計總是希望模塊之間的耦合表現(xiàn)為非直接耦合方式。但是，由于問題

所固有的復(fù)雜性和結(jié)構(gòu)化設(shè)計的原則，非直接耦合是不存在的。

考點4詳細(xì)設(shè)計

考試鏈接：

考點4在筆試考試中，在筆試考試中出現(xiàn)的兒率為30%,主要是以選

擇題的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容，讀者應(yīng)該識記過程

設(shè)計包括哪些常用工具。

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

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

詳細(xì)過程設(shè)計的常用工具有：

(1)圖形工具：程序流程圖，N-S,PAD,HIPOo

(2)表格工具：判定表。

(3)語言工具：PDL(偽碼)。

程序流程圖的5種控制結(jié)構(gòu)：順序型、選擇型、先判斷重復(fù)型、后

判斷重復(fù)型和多分支選擇型。

方框圖中僅含5種基本的控制結(jié)構(gòu)，即順序型、選擇型、多分支選

擇型、WHILE重復(fù)型和UNTIL重復(fù)型。

PAD圖表示5種基本控制結(jié)構(gòu)，即順序型、選擇型、多分支選擇型、

WHILE重復(fù)型和UNTIL重復(fù)型。

過程設(shè)計語言(PDL)也稱為結(jié)構(gòu)化的語言和偽碼，它是一種混合

語言，采用英語的詞匯和結(jié)構(gòu)化程序設(shè)計語言，類似編程語言。

PDL可以由編程語言轉(zhuǎn)換得到，也可以是專門為過程描述而設(shè)計

的。

?疑難解答：程序流程圖，N-S圖，PAD圖的控制結(jié)構(gòu)的異同點是什

么？

相同點是三種圖都有順序結(jié)構(gòu)，選擇結(jié)構(gòu)和多分支選擇，并且N-S

圖和PAD圖還有相同的WHILE重復(fù)型、UNTIL重復(fù)型；不同點是程序流

程圖沒有WHILE重復(fù)型、UNTIL重復(fù)型而有后判斷重復(fù)型和先判斷重復(fù)

型。

3.3軟件測試

考點5軟件測試的目的

考試鏈接：

考點5在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的

兒率為70%,主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為理解

內(nèi)容，讀者應(yīng)該理解測試是為了發(fā)現(xiàn)錯誤。

軟件測試是在軟件投入運行前對軟件需求、設(shè)計、編碼的最后審

核。其工作量、成本占總工作量、總成本的40%以上，而且具有較高

的組織管理和技術(shù)難度。

(1)軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程；

(2)一個好的測試用例是能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤的用例；

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

考點6軟件測試的實施

考試鏈接：

考點6在筆試考試中出現(xiàn)的兒率為30%,主要是以選擇題的形式出現(xiàn),

分值為2分,此考點為識記內(nèi)容,讀者應(yīng)該識記軟件測試過程的4個步驟,

單元測試的兩種測試方式。

軟件測試過程分4個步驟，即單元測試、集成測試、驗收測試和系

統(tǒng)測試。

單元測試是對軟件設(shè)計的最小單位一模塊（程序單元）進(jìn)行正確

性檢驗測試。單元測試的技術(shù)可以采用靜態(tài)分析和動態(tài)測試。

集成測試是測試和組裝軟件的過程，主要目的是發(fā)現(xiàn)與接口有關(guān)

的錯誤，主要依據(jù)是概要設(shè)計說明書。集成測試所設(shè)計的內(nèi)容包括：

軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入的測

試等。集成測試時將模塊組裝成程序，通常采用兩種方式：非增量方

式組裝和增量方式組裝。

確認(rèn)測試的任務(wù)是驗證軟件的功能和性能，以及其他特性是否滿

足了需求規(guī)格說明中確定的各種需求，包括軟件配置是否完全、正確。

確認(rèn)測試的實施首先運用黑盒測試方法，對軟件進(jìn)行有效性測試，即

驗證被測軟件是否滿足需求規(guī)格說明確認(rèn)的標(biāo)準(zhǔn)。

系統(tǒng)測試是通過測試確認(rèn)軟件，作為整個基于計算機(jī)系統(tǒng)的一個

元素，與計算機(jī)硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素

組合在一起，在實際運行（使用）環(huán)境下對計算機(jī)系統(tǒng)進(jìn)行一系列的

集成測試和確認(rèn)測試。

系統(tǒng)測試的具體實施一般包括：功能測試、性能測試、操作測試、

配置測試、外部接口測試、安全性測試等。

3.4軟件的調(diào)試

考點7軟件調(diào)試的基本概念

考試鏈接：

考點7在筆試考試中，是一個經(jīng)常考查的內(nèi)容，在筆試考試中出現(xiàn)的

幾率為70%,主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為重點

識記內(nèi)容，讀者應(yīng)該識記軟件調(diào)試的概念。

誤區(qū)警示：

程序經(jīng)調(diào)試改錯后還應(yīng)進(jìn)行再測試，因為經(jīng)調(diào)試后有可能產(chǎn)生新的

錯誤，而且測試是貫穿生命周期的整個過程。

在對程序進(jìn)行了成功的測試之后將進(jìn)入程序調(diào)試(通常稱Debug,

即排錯)。程序的調(diào)試任務(wù)是診斷和改正程序中的錯誤。調(diào)試主要在

開發(fā)階段進(jìn)行。

程序調(diào)試活動由兩部分組成，一是根據(jù)錯誤的跡象確定程序中錯

誤的確切性質(zhì)、原因和位置；二是對程序進(jìn)行修改，排除這個錯誤。

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

(1)錯誤定位。從錯誤的外部表現(xiàn)形式入手，研究有關(guān)部分的程

序，確定程序中出錯位置，找出錯誤的內(nèi)在原因；

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

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

調(diào)試原則可以從以下兩個方面考慮：

(1)確定錯誤的性質(zhì)和位置時的注意事項

分析思考與錯誤征兆有關(guān)的信息；避開死胡同；只把調(diào)試工具當(dāng)

作輔助手段來使用；避免用試探法，最多只能把它當(dāng)作最后手段。

（2）修改錯誤原則

在出現(xiàn)錯誤的地方，很可能有別的錯誤；修改錯誤的一個常見失誤是

只修改了這個錯誤的征兆或這個錯誤的表現(xiàn)，而沒有修改錯誤本身；

注意修正一個錯誤的同時有可能會引入新的錯誤；修改錯誤的過程將

迫使人們暫時回到程序設(shè)計階段；修改源代碼程序，不要改變目標(biāo)代

碼。

?疑難解答：軟件測試與軟件調(diào)試有何不同？

軟件測試是盡可能多地發(fā)現(xiàn)軟件中的錯誤，而軟件調(diào)試的任務(wù)是

診斷和改正程序中的錯誤。軟件測試貫穿整個軟件生命周期，調(diào)試主

要在開發(fā)階段。

3.5例題詳解

一、選擇題

【例1】對軟件的特點，下面描述正確的是O（考點1）

A）軟件是一種物理實體

B）軟件在運行使用期間不存在老化問題

C）軟件開發(fā)、運行對計算機(jī)沒有依賴性，不受計算機(jī)系統(tǒng)

的限制

D）軟件的生產(chǎn)有一個明顯的制作過程

解析：軟件在運行期間不會因為介質(zhì)的磨損而老化，只可能因為

適應(yīng)硬件環(huán)境以及需求變化進(jìn)行修改而引入錯誤，導(dǎo)致失效率升高從

而軟件退化，所以本題正確答案為B）。

答案：B）

【例2】以下哪項是軟件生命周期的主要活動階段？（考

點2)

A）需求分析B）軟件開發(fā)

C）軟件確認(rèn)D）軟件演進(jìn)

解析：B）、C）、D）項都是軟件工程過程的基本活動，還有一個是

軟件規(guī)格說明。

答案：A）

【例3】從技術(shù)觀點看一，軟件設(shè)計包括o（考點3）

A）結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、程序設(shè)計

B）結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計

C）結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、文檔設(shè)計、過程設(shè)計

D）結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、文檔設(shè)計、程序設(shè)計

解析：技術(shù)角度，要進(jìn)行結(jié)構(gòu)、接口、數(shù)據(jù)、過程的設(shè)計。結(jié)構(gòu)

設(shè)計是定義系統(tǒng)各部件關(guān)系，數(shù)據(jù)設(shè)計是根據(jù)分析模型轉(zhuǎn)化數(shù)據(jù)結(jié)

構(gòu)，接口設(shè)計是描述如何通信，過程設(shè)計是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)化為軟

件的過程性描述。

答案：B）

【例4】以下哪個是軟件測試的目的？（考點5）

A）證明程序沒有錯誤B）演示程序的正確性

C）發(fā)現(xiàn)程序中的錯誤D）改正程序中的錯誤

解析：關(guān)于測試目的的基本知識，IEEE的定義是：使用人工或自

動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)

定的需求，或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別，所以正確答案

是C）。

答案：C）

【例5】以下哪個測試要對接口測試？。（考點6）

A）單元測試B）集成測試

C）驗收測試D）系統(tǒng)測試

解析：檢查對測試實施各階段的了解，集成測試時要進(jìn)行接口測

試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件測試和非法輸入的測試等，所以正

確答案是B）。

答案：B）

【例6】程序調(diào)試的主要任務(wù)是o（考點7）

A）檢查錯誤B）改正錯誤

C）發(fā)現(xiàn)錯誤D）以上都不是

解析：程序的調(diào)試任務(wù)是診斷和改正程序中的錯誤。調(diào)試主要在

開發(fā)階段進(jìn)行。

答案：B）

【例7】以下哪些不是程序調(diào)試的基本步驟？（考點7）

A）分析錯誤原因B）錯誤定位

C）修改設(shè)計代碼以排除錯誤D）回歸測試，防止引入

新錯誤

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

（1）錯誤定位。從錯誤的外部表現(xiàn)形式入手，研究有關(guān)部分的程

序，確定程序中出錯位置，找出錯誤的內(nèi)在原因。

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

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

答案：A)

【例8】在修改錯誤時應(yīng)遵循的原則有。(考點7)

A)注意修改錯誤本身而不僅僅是錯誤的征兆和表現(xiàn)

B)修改錯誤的是源代碼而不是目標(biāo)代碼

C)遵循在程序設(shè)計過程中的各種方法和原則

D)以上3個都是

解析：修改錯誤原則：

(1)在出現(xiàn)錯誤的地方，很可能有別的錯誤；

(2)修改錯誤的一個常見失誤是只修改了這個錯誤的征兆或這個

錯誤的表現(xiàn)，而沒有修改錯誤本身；

(3)注意修正一個錯誤的同時有可能會引入新的錯誤；

(4)修改錯誤的過程將迫使人們暫時回到程序設(shè)計階段；

(5)修改源代碼程序，不要改變目標(biāo)代碼。

答案：D)

二、填空題

【例1】軟件設(shè)計是軟件工程的重要階段，是一個把軟件需求轉(zhuǎn)換

為的過程。(考點3)

解析：軟件設(shè)計是軟件工程的重要階段，是一個把軟件需求轉(zhuǎn)換

為軟件表示的過程。其基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系

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

答案：軟件表示

【例2】是指把一個待開發(fā)的軟件分解成若干小的簡單的

部分。（考點3）

解析：模塊化是指把一個待開發(fā)的軟件分解成若干小的簡單的部

分。如高級語言中的過程、函數(shù)、子程序等。每個模塊可以完成一個

特定的子功能，各個模塊可以按一定的方法組裝起來成為一個整體，

從而實現(xiàn)整個系統(tǒng)的功能。

答案：模塊化

【例3】數(shù)據(jù)流圖采用4種符號表示、數(shù)據(jù)源點和終點、數(shù)

據(jù)流向和數(shù)據(jù)加工。（考點4）

解析：數(shù)據(jù)流圖可以表達(dá)軟件系統(tǒng)的數(shù)據(jù)存儲、數(shù)據(jù)源點和終點、

數(shù)據(jù)流向和數(shù)據(jù)加工。其中，用箭頭表示數(shù)據(jù)流向，用圓或者橢圓表

示數(shù)據(jù)加工，用雙杠表示數(shù)據(jù)存儲，用方框來表示數(shù)據(jù)源點和終點。

答案：數(shù)據(jù)存儲

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

經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，筆試部分經(jīng)

?？疾榈氖菙?shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫基本特點，數(shù)據(jù)庫系統(tǒng)的三級模

式及二級映射，E-R模型，關(guān)系模型和關(guān)系代數(shù)，讀者應(yīng)對此部分進(jìn)

行重點學(xué)習(xí)。

詳細(xì)重點學(xué)習(xí)知識點：

1.數(shù)據(jù)的概念、數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言、數(shù)據(jù)管理員

的主要工作、數(shù)據(jù)庫系統(tǒng)階段的特點、數(shù)據(jù)的物理獨立性及邏輯獨立

性、數(shù)據(jù)統(tǒng)一管理與控制、三級模式及兩級映射的概念

2.數(shù)據(jù)模型3個描述內(nèi)容、E-R模型的概念及其E-R圖表示法、關(guān)

系操縱、關(guān)系模型三類數(shù)據(jù)約束

3.關(guān)系模型的基本操作、關(guān)系代數(shù)中的擴(kuò)充運算

4.數(shù)據(jù)庫設(shè)計生命周期法的4個階段

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

考點1數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)

考試鏈接：

考點1在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的

機(jī)率為70%,主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為重點

識記內(nèi)容，讀者還應(yīng)該識記數(shù)據(jù)語言所包括的數(shù)據(jù)定義語言、數(shù)據(jù)操縱

語言和數(shù)據(jù)控制語言。

數(shù)據(jù)是數(shù)據(jù)庫中存儲的基本對象，描述事物的符號記錄。

數(shù)據(jù)庫是長期儲存在計算機(jī)內(nèi)、有組織的、可共享的大量數(shù)據(jù)的

集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)

用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。

數(shù)據(jù)庫管理系統(tǒng)(DBMS,DatabaseManagementSystem)是數(shù)據(jù)

庫的機(jī)構(gòu)，它是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操作、

數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)系統(tǒng)的

核心，主要有如下功能：數(shù)據(jù)模式定義、數(shù)據(jù)存取的物理構(gòu)建、數(shù)據(jù)

操縱、數(shù)據(jù)的完整性、安全性定義和檢查、數(shù)據(jù)庫的并發(fā)控制與故障

恢復(fù)、數(shù)據(jù)的服務(wù)。

為完成數(shù)據(jù)庫管理系統(tǒng)的功能，數(shù)據(jù)庫管理系統(tǒng)提供相應(yīng)的數(shù)據(jù)

語言：數(shù)據(jù)定義語言、數(shù)據(jù)操縱語言、數(shù)據(jù)控制語言。

數(shù)據(jù)庫管理員的主要工作如下：數(shù)據(jù)庫設(shè)計、數(shù)據(jù)庫維護(hù)、改善

系統(tǒng)性能，提高系統(tǒng)效率。

考點2數(shù)據(jù)庫系統(tǒng)的發(fā)展

考試鏈接：

考點2在筆試考試中出現(xiàn)的機(jī)率為30%,主要是以選擇題的形式出現(xiàn),

分值為2分，此考點為識記內(nèi)容，讀者還應(yīng)該注意各個階段的特點。

數(shù)據(jù)管理技術(shù)的發(fā)展經(jīng)歷了3個階段，見表4-1：

表4-1各階段特點的詳細(xì)說明

?>人工?理配段,文件系統(tǒng)階段」敷得莊不鄴介段?

應(yīng)用背景，科學(xué)計算?科學(xué)計算、管理」大炊事管理，

甘硬件背景無直接存取存儲設(shè)備」破彘.誨鼓」大容置*溫」

和軟件,索?及有操作系統(tǒng)，有文件耳統(tǒng)，有效據(jù)庫?理系統(tǒng),

處理方式」批處理?聯(lián)機(jī)實時處理、批處理.聚機(jī)實時處理、分布處理、批處理?

數(shù)據(jù)的管理者3用戶（程序員）'文件系統(tǒng)”數(shù)據(jù)庫管理系統(tǒng).

數(shù)擺面向的對象＞某一直用程序?某一曲用,,現(xiàn)實世界?

求據(jù)的共享程度」無共享，冗余度大，共享性蒼，冗余度大一共享性高，冗余度小2

n具有高度的物理獨立性和一定的

數(shù)據(jù)的獨立性*不獨立,完全依0千程序，獨立性差。

遨?獨立性a

數(shù)據(jù)結(jié)構(gòu)化，無結(jié)構(gòu)，記錄內(nèi)有結(jié)構(gòu)、整體無結(jié)構(gòu)”整體結(jié)構(gòu)化，用敗據(jù)模型描述」

由效據(jù)序■理系統(tǒng)提供獨據(jù)安全

數(shù)據(jù)控制?坡h應(yīng)用程序自己控制?，應(yīng)程序自己控知

性.完整性、井發(fā)控制和恢復(fù)也力?

考點3數(shù)據(jù)庫系統(tǒng)的基本特點

考試鏈接：

考點3在筆試考試中出現(xiàn)的機(jī)率為30%,主要是以填空題的形式出現(xiàn),

分值為2分，此考點為識記內(nèi)容，讀者還應(yīng)該理解物理獨立性和邏輯獨

立性的定義。

數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中的數(shù)據(jù)獨

立于應(yīng)用程序而不依賴于應(yīng)用程序。

數(shù)據(jù)的獨立性一般分為物理獨立性與邏輯獨立性兩種。

（1）物理獨立性：指用戶的應(yīng)用程序與存儲在磁盤上的數(shù)據(jù)庫中

數(shù)據(jù)是相互獨立的。當(dāng)數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲結(jié)構(gòu)、存取方式等）

改變時，如存儲設(shè)備的更換、物理存儲的更換、存取方式改變等，應(yīng)

用程序都不用改變。

（2）邏輯獨立性：指用戶的應(yīng)用程序與數(shù)據(jù)庫的邏輯結(jié)構(gòu)是相互

獨立的。數(shù)據(jù)的邏輯結(jié)構(gòu)改變了，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類

型、改變數(shù)據(jù)間聯(lián)系等，用戶程序都可以不變。

數(shù)據(jù)統(tǒng)一管理與控制主要包括以下3個方面：數(shù)據(jù)的完整性檢查、

數(shù)據(jù)的安全性保護(hù)和并發(fā)控制。

考點4數(shù)據(jù)庫系統(tǒng)的內(nèi)部