計(jì)算機(jī)公共知識(shí)

計(jì)算機(jī)公共基礎(chǔ)知識(shí)

考點(diǎn)1.算法的基本概念

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

(1)算法的基本特征

可行性：針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果，即必須有一個(gè)或多個(gè)輸出。如果在數(shù)學(xué)理

論上是正確的，但是在實(shí)際的計(jì)算工具上不能執(zhí)行，則該算法也是不具有可行性的。

確定性：是指算法中每?步驟都必須是有明確定義的。

仃窮性：是指兌法必須能在有限的時(shí)間內(nèi)做完。

擁有足夠的情報(bào)：一個(gè)算法是否有效，還取決「為算法所提供的情報(bào)是否足夠。

(2)算法的基本要素

算法一般山兩種基本要素構(gòu)成：

時(shí)數(shù)據(jù)對(duì)軟的運(yùn)算和操作：

算法的控制結(jié)構(gòu)，即運(yùn)算和操作時(shí)間的順序。

算法中對(duì)數(shù)據(jù)的運(yùn)算和操作：算法就是按解題要求從指令系統(tǒng)中選擇合適的指令組成的指令序列。因此計(jì)算機(jī)算法

就是計(jì)算機(jī)能進(jìn)行的操作所組成的指令序列。不同的計(jì)算機(jī)系統(tǒng)，指令系統(tǒng)是有差異的，但一般的計(jì)算機(jī)系統(tǒng)中都

包括的運(yùn)算和操作有4類，即算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)：算法中各操作之間的

進(jìn)行順序稱為算法的控制結(jié)構(gòu)。算法的功能不僅取決于所選用的操作，還與各操作之間的進(jìn)行順序有關(guān)?；镜目?/p>

制結(jié)構(gòu)包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)等。

(3)算法設(shè)計(jì)的基本方法

算法設(shè)計(jì)的基本方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術(shù)和回溯法。

2.算法復(fù)雜度

算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。

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

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

一般情況下，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù),

即：算法的工作量=f(n)其中n是問(wèn)題的規(guī)模。這個(gè)表達(dá)式表示隨著問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)

率和f(n)的增長(zhǎng)率相同。

在同?個(gè)問(wèn)題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí)，可以用兩種方法來(lái)分析算法的工

作量，即平均性態(tài)分析和最壞情況分析。

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

一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。算法執(zhí)行期間所需要的存儲(chǔ)空間包括3個(gè)部分:

算法程序所小的空間；

輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間；

算法執(zhí)行過(guò)程中所需要的額外空間。

在許多實(shí)際問(wèn)題中，為了減小算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，用于減小不必要的額外空間。

考點(diǎn)2數(shù)據(jù)結(jié)構(gòu)的基本概念

1,數(shù)據(jù)結(jié)構(gòu)的定義

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

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

所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系(即前后件關(guān)

系)的數(shù)據(jù)結(jié)構(gòu)。它包括兩個(gè)要素，即數(shù)據(jù)元素的集合和數(shù)據(jù)元素之間的

關(guān)系。

(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

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

結(jié)構(gòu)(也稱為數(shù)據(jù)的物理結(jié)構(gòu))。數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有：順序存儲(chǔ)方法、鏈?zhǔn)酱鎯?chǔ)方法、索引存儲(chǔ)方法和散列存

儲(chǔ)方法。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很

重要的。

數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容主要包括3個(gè)方面：

數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯美系，即數(shù)據(jù)的邏輯結(jié)構(gòu)：

在時(shí)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：

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

2.數(shù)據(jù)結(jié)構(gòu)的圖形表示

數(shù)據(jù)元素之間最基本的關(guān)系是前后件關(guān)系。所謂前后件關(guān)系即每一個(gè)二元組，都可以用圖形來(lái)表示。用中間標(biāo)有元

素值的方框表示數(shù)據(jù)元素，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，簡(jiǎn)稱為結(jié)點(diǎn)。對(duì)于每一個(gè)二元組，通常用一條有向線段從前件指

向后件。用圖形表示數(shù)據(jù)結(jié)構(gòu)具有直觀易懂的特點(diǎn)，在不引起歧義的情況下，前件結(jié)點(diǎn)到后件結(jié)點(diǎn)連線上的箭頭可

以省去。例如在樹形結(jié)構(gòu)中，通常都是用無(wú)向線段來(lái)表示前后件關(guān)系的。

3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后關(guān)系的復(fù)雜程度，一般可將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

如果?個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足有且只有一個(gè)根結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)和直接后繼，則稱該數(shù)據(jù)結(jié)

構(gòu)為線性結(jié)構(gòu)，又稱線性表。不滿足上述條件的數(shù)據(jù)結(jié)構(gòu)則稱為非線性結(jié)構(gòu)。

小提示，需要注意的是：在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)該是線性結(jié)構(gòu)，否則不能稱之為線性結(jié)

構(gòu)。

下列敘述中正確的是（）。

A）程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)

B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)

C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量

D）以上3種說(shuō)法都不對(duì)

【答案】A）

【解析】在計(jì)算機(jī)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)的執(zhí)行效率有較大的影響，例如在有序存儲(chǔ)的表中查找某個(gè)數(shù)值就比

在無(wú)序存儲(chǔ)的表中查找的效率高很多。

考點(diǎn)3.線性表的基本概念

在數(shù)據(jù)結(jié)構(gòu)中，通常將線性結(jié)構(gòu)習(xí)慣上稱為線性表，線性表是最簡(jiǎn)單也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是由

n（n20）個(gè)數(shù)據(jù)元素a1,a2,…，an組成的一個(gè)有限序列。除了表中的第一個(gè)元素外，有且只有一個(gè)前

件；除了最后一個(gè)元素外，有且只有一個(gè)后件。

線性表要么是一個(gè)空表，要么可以表示為：（al,a2,…，ai,…，an）其中ai（i=1,2,n）

是線性表的數(shù)據(jù)元素，也稱為線性表的一個(gè)結(jié)點(diǎn)。每個(gè)數(shù)據(jù)元素的具體含義，在不同的情況下各不相同，它可以是

一個(gè)數(shù)或一個(gè)字符，也可以是一個(gè)具體的事物，甚至其他更復(fù)雜的信息。但是需要注意的是：同一線性表中的數(shù)據(jù)

元素必定具有相同的特性，即屬于同一個(gè)數(shù)據(jù)對(duì)象。

小提示：

非空線性表具有以下一些結(jié)構(gòu)特征：只有一個(gè)根結(jié)點(diǎn)，即頭結(jié)點(diǎn)，它無(wú)前件；有且只有一個(gè)終結(jié)點(diǎn)，即尾結(jié)點(diǎn)，它

無(wú)后件；除了頭結(jié)點(diǎn)與尾結(jié)點(diǎn)外，其他所有節(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表

的長(zhǎng)度，當(dāng)n=0時(shí)稱為空表。

2.線性表的順序存儲(chǔ)結(jié)構(gòu)

將線性表中的元素一個(gè)接一個(gè)地存儲(chǔ)在一片相鄰的存儲(chǔ)區(qū)域中，這種順序表示的線性表也稱為順序表。線性表的順

序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

元素所占的存儲(chǔ)空間必須是連續(xù)的；

元素在存儲(chǔ)空間的位置是按邏輯順序存放的。

從這種特點(diǎn)也可以看出，線性表是用元素在計(jì)算機(jī)內(nèi)物理位置上的相鄰關(guān)系來(lái)表示元素之間邏輯上的相鄰關(guān)系。只

要確定了首地址，線性表內(nèi)任意元素的地址都可以方便地計(jì)算出來(lái)。

3.線性表的插入運(yùn)算

在線性表的插入運(yùn)算中，若在第i個(gè)元素之前插入一個(gè)新元素，完成插入操作主要有以下3個(gè)步驟：

（1）把原來(lái)第n個(gè)結(jié)點(diǎn)至第i個(gè)結(jié)點(diǎn)依次往后移一個(gè)元素的位置；

（2）把新結(jié)點(diǎn)放在第i個(gè)位置上；

（3）修正線性表的結(jié)點(diǎn)個(gè)數(shù)。

小提示

一般會(huì)為線性表開(kāi)辟一個(gè)大于線性表長(zhǎng)度的存儲(chǔ)空間，經(jīng)過(guò)多次插入運(yùn)算，可能出現(xiàn)存儲(chǔ)空間已滿的情況，如果此

時(shí)仍繼續(xù)進(jìn)行插入運(yùn)算，將會(huì)產(chǎn)生錯(cuò)誤，此類錯(cuò)誤稱為“上溢”。

如果需要在線性表末尾進(jìn)行插入運(yùn)算，則只需要在表的末尾增加一個(gè)元素即可，而不需要移動(dòng)線性表中的元素。如

果在第一個(gè)位置插入新的元素，則需要移動(dòng)表中所有的數(shù)據(jù)。

4.線性表的刪除運(yùn)算

在線性表的刪除運(yùn)算中，若刪除第i個(gè)位置的元素，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共n-i個(gè)

元素依次向前移一個(gè)位置。完成刪除主要有以下兒個(gè)步驟：

（1）把第i個(gè)元素之后（不包括第i個(gè)元素）的n—i個(gè)元素依次前移一個(gè)位置；

（2）修正線性表的結(jié)點(diǎn)個(gè)數(shù)。

顯然，如果刪除運(yùn)算在線性表的末尾進(jìn)行，即刪除第n個(gè)元素，則不需要移動(dòng)線性表中的元素。如果要?jiǎng)h除第1個(gè)

元素，則需要移動(dòng)表中所有的數(shù)據(jù)。小提示

由線性表的以上性質(zhì)可以看出，線性表的順序存儲(chǔ)結(jié)構(gòu)適用于小線性表或者建立之后其中的元素不常變動(dòng)的線性表,

而不適用于需要經(jīng)常進(jìn)行插入和刪除運(yùn)算的線性表和長(zhǎng)度較大的線性表。

【例1】下列有關(guān)順序存儲(chǔ)結(jié)構(gòu)的敘述，不正確的是（）?

A）存儲(chǔ)密度大

B）邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

C）可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

D）插入、刪除操作不方便

【答案】B）

【解析】順序存儲(chǔ)結(jié)構(gòu)要求邏輯上相鄰的元素物理上也相鄰，所以只有選項(xiàng)B敘述錯(cuò)誤。

【例2】在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素（l<i<n+l）位置插入一個(gè)新元素時(shí)，需要從后向前依次

移動(dòng)

個(gè)元素。

A）n-iB）iC）n-i-1D）n-i+1

【答案】D）

【解析】根據(jù)順序表的插入運(yùn)算的定義知道，在第i個(gè)位置上插入x,從ai到an都要向后移動(dòng)一個(gè)位置，共需

要移動(dòng)n—i+1個(gè)元素。

考點(diǎn)4.棧和隊(duì)列

1.棧及其基本運(yùn)算

（1）棧的基本概念

棧實(shí)際上也是線性表，只不過(guò)是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運(yùn)算都只在線性表的一

端進(jìn)行。在棧中，允許插入與刪除的一端稱為棧頂（t。p）,另一端稱為棧底（bottom）。當(dāng)棧中沒(méi)有元素

時(shí)則稱為空棧。棧也被稱為"先進(jìn)后出"表或"后進(jìn)先出"表。

（2）棧的特點(diǎn)

根據(jù)棧的上述定義，棧具有以下幾個(gè)特點(diǎn)：

0棧頂元素總是最后被插入的元素，也是最早被刪除的元素；

。棧底元素總是最早被插入的元素，也是最晚才能被刪除的元素；

顯棧具有記憶作用；

。在順序存儲(chǔ)結(jié)構(gòu)下，棧的插入和刪除運(yùn)算都不需要移動(dòng)表中其他的數(shù)據(jù)元素；

Q棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。

（3）棧的順序存儲(chǔ)及其運(yùn)算

根據(jù)棧的狀態(tài)，可以得知棧的基本運(yùn)算有以下3種：

入棧運(yùn)算：在板頂位置插入一個(gè)新元索；

退棧運(yùn)算：取出棧頂元素并賦給一個(gè)指定的變量；

讀棧頂元索：將棧頂元素賦給一個(gè)指定的變量。

2.隊(duì)列及其基本運(yùn)算

（1）隊(duì)列的基本概念

隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用?個(gè)稱為尾指針

（rear）的指針指向隊(duì)尾元素；允許刪除的一端稱為排頭，通常用一個(gè)頭指針（fr。nt）指向頭元素的前

一個(gè)位置。因此隊(duì)列又稱為“先進(jìn)先出”的線性表。插入元素稱為入隊(duì)運(yùn)算，刪除元素稱為退隊(duì)運(yùn)算。

（2）循環(huán)隊(duì)列及其運(yùn)算

所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。

在循環(huán)隊(duì)列中，用尾指針（rear）指向隊(duì)列的尾元素，用頭指針（fr。nt）指向頭元素的前一個(gè)位置，因

此，從頭指針（front）指向的后一個(gè)位置直到尾指針（rear）指向的位置之間所有的元素均為隊(duì)列中的

元素。循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front。

循環(huán)隊(duì)列的基本運(yùn)算主要有兩種：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。

入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新的元索。

退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素，并賦給指定的變量.

小提示

棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)，而隊(duì)列則是按照“先進(jìn)先出”或“后進(jìn)后出”的原則組織

數(shù)據(jù)，這就是棧和隊(duì)列的不同點(diǎn)。

【例1】下列對(duì)隊(duì)列的敘述正確的是（）。

A）隊(duì)列屬于非線性表B）隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù)

O隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D）隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)

【答案】D）

【解析】隊(duì)列是一種特殊的線性表，它只能在一端進(jìn)行插入，在另一端進(jìn)行刪除。允許插入的一端稱為隊(duì)尾，允許

刪除的另一端稱為隊(duì)頭。隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表，體現(xiàn)了“先到先服務(wù)”的原則。

【例2】下列關(guān)于棧的描述正確的是（）。

A）在棧中只能插入元素而不能刪除元素

B）在棧中只能刪除元素而不能插入元素

C）棧是特殊的線性表，只能在一端插入或刪除元素

D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

【答案】C）

【解析】棧是一種特殊的線性表。在這種特殊的線性表中，其插入和刪除操作只在線性表的?端進(jìn)行。

考點(diǎn)5.線性鏈表

1.線性鏈表的基本概念

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。為了存儲(chǔ)線性表中的每一個(gè)元素，一方面要存儲(chǔ)數(shù)據(jù)元素的值，另?方面要

存儲(chǔ)各數(shù)據(jù)元素之間的前后件關(guān)系。為此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分稱為數(shù)據(jù)域，用于

存放數(shù)據(jù)元素值；另一部分稱為指針域，用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)，即指向后件結(jié)點(diǎn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既

可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組不連續(xù)的存儲(chǔ)單元存儲(chǔ)線性表中

的各個(gè)元素。由于存儲(chǔ)單元不連續(xù)，因此數(shù)據(jù)元素之間的邏輯關(guān)系就不能依靠數(shù)據(jù)元素的存儲(chǔ)單元之間的物理關(guān)系

來(lái)表示。

2.線性鏈表的基本運(yùn)算

線性鏈表主要包括以下幾種運(yùn)算：

在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入?個(gè)新元素：

在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)；

將兩個(gè)線性鏈次按要求合并成一個(gè)線性鏈表；

將?個(gè)線性徒表按要求進(jìn)行分解：

逆轉(zhuǎn)線性鏈表：

復(fù)制線性鏈表;

線性鏈表的排序;

線性鏈表的杳找。

3.循環(huán)鏈表及其基本運(yùn)算

（1）循環(huán)鏈表的定義

在單鏈表的第一個(gè)結(jié)點(diǎn)前增加一個(gè)表頭結(jié)點(diǎn)，隊(duì)頭指針指向表頭結(jié)點(diǎn)，將最后一個(gè)結(jié)點(diǎn)的指針域的值山NULL改

為指向表頭結(jié)點(diǎn)，這樣的鏈表稱為循環(huán)鏈表。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。

（2）循環(huán)鏈表與單鏈表的比較

對(duì)單鏈表的訪問(wèn)是一種順序訪問(wèn)，從其中的某一個(gè)結(jié)點(diǎn)出發(fā)，只能找到它的直接后繼，但無(wú)法找到它的直接前驅(qū)。

而且對(duì)于空表和第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，空表與非空表的操作不統(tǒng)一.

在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)。并且由于表頭結(jié)

點(diǎn)是循環(huán)鏈表所固有的結(jié)點(diǎn)，因此即使在表中沒(méi)有數(shù)據(jù)元素的情況下，表中也至少有一個(gè)結(jié)點(diǎn)存在，從而使空表和

非空表的運(yùn)算統(tǒng)一。

下列敘述中正確的是（）。

A）線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B）棧與隊(duì)列是非線性結(jié)構(gòu)

C）雙向鏈表是非線性結(jié)構(gòu)D）只有根結(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu)

【答案】A）

【解析】根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)

構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：①有且只有一個(gè)根結(jié)點(diǎn)；②每個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有

一個(gè)后繼，則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，也叫做線性表。若不滿足上述條件，則稱之為非線性結(jié)構(gòu)。線性表、棧與

隊(duì)列、線性鏈表都是線性結(jié)構(gòu)，而二叉樹則是非線性結(jié)構(gòu)。

考點(diǎn)6.樹和二叉樹

1.樹的基本概念

樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)，直觀地來(lái)看樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹是由n（n20）個(gè)結(jié)點(diǎn)構(gòu)成的有限

集合，n=0的樹稱為空樹；當(dāng)nW0時(shí)，樹中的結(jié)點(diǎn)應(yīng)該滿足以下兩個(gè)條件：有且僅有一個(gè)沒(méi)有前驅(qū)的結(jié)點(diǎn)稱之

為根；其余的結(jié)點(diǎn)分成m（m>0）個(gè)互不相交的有限集合T1,T2,T}rmm,其中每一個(gè)集合又都是

一棵樹，稱Tl,T2,T}rmm為根結(jié)點(diǎn)的子樹。

在樹的結(jié)構(gòu)中主要會(huì)涉及到下面幾個(gè)概念。

每一個(gè)結(jié)點(diǎn)只有?個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有-個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根。每一個(gè)結(jié)點(diǎn)

可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)

點(diǎn)稱為葉子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)所擁有的后繼個(gè)數(shù)稱為該結(jié)點(diǎn)的度。所有結(jié)點(diǎn)最大的度稱為樹的度。樹的最大層次稱為

樹的深度。

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

（1）二叉樹的定義

二叉樹是一種非線性結(jié)構(gòu)，是一個(gè)有限的結(jié)點(diǎn)集合，該集合或者為空，或者由一個(gè)根結(jié)點(diǎn)及其兩棵互不相交的左右

二叉子樹所組成。當(dāng)集合為空時(shí),稱該二叉樹為空二叉樹。

二叉樹具有以下特點(diǎn)：

二義樹可以為空，空的二叉樹沒(méi)有結(jié)點(diǎn)，作空二叉樹有且只有?個(gè)根結(jié)點(diǎn)；

每一個(gè)結(jié)點(diǎn)最多有兩棵r樹，且分別稱為該結(jié)點(diǎn)的左r樹與&r?樹。

（2）滿二叉樹和完全二叉樹

滿二叉樹：除了最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，即在滿二叉樹的第k層上有2k—1個(gè)結(jié)點(diǎn)，

且深度為m的滿二叉樹中有2m-1個(gè)結(jié)點(diǎn)。

完全二叉樹：除了最后?層外，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

滿二叉樹與完全二叉樹的關(guān)系：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

（3）二叉樹的主要性質(zhì)

棵『空二義樹的第k層上最多有2k—1個(gè)結(jié)點(diǎn)（k21

深度為m的滿二義樹中有2m—1個(gè)結(jié)點(diǎn)。

對(duì)任何?棵二義樹而言，度為0的結(jié)點(diǎn)（即葉F結(jié)點(diǎn)）總站比度為2的結(jié)點(diǎn)多一個(gè)。

具有n個(gè)結(jié)點(diǎn)的完全二義樹的深度k為[log2n]+l.

3.二叉樹的存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成。由于每

一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），所以用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)指向該結(jié)點(diǎn)的

左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。因此，二叉樹的

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。對(duì)于滿二叉樹與完全二叉樹可以按層次進(jìn)行順序存儲(chǔ)。

4.二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問(wèn)二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷主要是針對(duì)非空二叉樹的；對(duì)于空二叉樹，則

結(jié)束返回。二叉樹的遍歷有前序遍歷、中序遍歷和后序遍歷等。

（1）前序遍序（DLR）

首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。

（2）中序遍歷（LDR）

首先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹。

（3）后序遍歷（LRD）

首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。

小提示

已知一棵二叉樹的前序遍歷序列和中序遍歷序列，可以唯一確定這棵二叉樹。已知一棵二叉樹的后序遍歷序列和中

序遍歷序列，也可以唯一確定這棵二叉樹。已知一棵二叉樹的前序遍歷序列和后序遍歷序列，則不能唯一確定這棵

二叉樹。

考點(diǎn)7.查找技術(shù)

1,順序查找

順序查找一般是指在線性表中查找指定的元素。其基本思路是：從表中的第一個(gè)元素開(kāi)始，依次將線性表中的

元素與被查找元素進(jìn)行比較，直到兩者相符，查到所要找的元素為止。若表中沒(méi)有要找的元素，則查找不成功。在

最好的情況下，第一個(gè)元素就是要查找的元素，則比較次數(shù)為1次。在最壞的情況下，順序查找需要比較n次。在

平均情況下，需要比較n/2次。因此查找算法的時(shí)間復(fù)雜度為0（n）。

在下列兩種情況下只能夠采取順序查找：

如果線性及中元索的排列是無(wú)序的，則無(wú)論是順序存儲(chǔ)結(jié)構(gòu)還是鋅式存儲(chǔ)結(jié)構(gòu)，都只能進(jìn)行順序杳找：即便是有

序線性表，若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能進(jìn)行順序查找。

2.二分查找

使用二分法查找的線性表必須滿足兩個(gè)條件：

順序存儲(chǔ)結(jié)構(gòu)：

線性表是有序衣。

所謂有序表，是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

對(duì)于長(zhǎng)度為n的有序線性表，利用二分法查找元素x的過(guò)程如下：

（1）將x與線性表的中間項(xiàng)進(jìn)行比較；

（2）若中間項(xiàng)的值等于X,則查找成功，結(jié)束查找；

（3）若x小于中間項(xiàng)的值，則在線性表的前半部分以二分法繼續(xù)查找；

（4）若x大于中間項(xiàng)的值，則在線性表的后半部分以二分法繼續(xù)查找。

這樣反復(fù)進(jìn)行查找，直到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有這個(gè)元素）為止。

當(dāng)有序線性表為順序存儲(chǔ)時(shí)采用二分查找的效率要比順序查找高得多。對(duì)于長(zhǎng)度為n的有序線性表，在最壞的情況

下，二分查找只需要比較1。g2n次，而順序查找則需要比較n次。

在下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是（）。

A.順序存儲(chǔ)的有序線性表B.線性鏈表C.二叉鏈表D.有序線性鏈表

【答案】A）

【解析】二分法查找只適用于順序存儲(chǔ)的有序表。所謂有序表是指線性表中的元素按值非遞減排列（即從小到大，

但允許

相鄰元素值相等）。

考點(diǎn)8.排序技術(shù)

1?交換類排序法

交換類排序法是指借助數(shù)據(jù)元素的“交換”來(lái)進(jìn)行排序的一種方法。本節(jié)介紹的冒泡排序法和快速排序法就是屬于

交換類排序法。

(1)冒泡排序法

冒泡排序的基本思路如下。

在線性表中依次查找相鄰的數(shù)據(jù)元素，將表中最大的元素不斷地往后移動(dòng)，反復(fù)操作直到消除所有的逆序，此時(shí)該

表即排序結(jié)束。

冒泡排序法的基本過(guò)程如下。

①?gòu)谋眍^開(kāi)始往后查找線性表，在查找過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若在相鄰兩個(gè)元素中，前面的元素大

于后面的元素，則將它們交換。

②從后到前查找剩下的線性表(除去最后一個(gè)元素)，同樣，在查找過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若在相

鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們交換。

③對(duì)剩下的線性表重復(fù)上述過(guò)程，直到剩下的線性表變空為止，即表示線性表排序完成。

假設(shè)線性表的長(zhǎng)度為n,則在最壞的情況下，冒泡排序需要經(jīng)過(guò)n/2遍的從前往后的掃描和n/2遍的從后往前

掃描，需要比較n(n-1)/2次，其數(shù)量級(jí)為n2。

(2)快速排序法

快速排序法的基本思路如下：

在線性表中逐個(gè)選取元素，對(duì)線性表進(jìn)行分割，直到所有元素全部選取完畢，此時(shí)線性表即排序結(jié)束。

快速排序法的基本過(guò)程如下。

①?gòu)木€性表中選取一個(gè)元素，設(shè)為T,將線性表后面小于T的元素移動(dòng)到前面，而將大于T的元素移到后面，這樣

就將線性表分成了兩部分(稱為兩個(gè)子表)。T處于分界線的位置，將線性表分成了前后兩個(gè)子表，目前面子表中

的所有元素均不大于T,而后子表中的所有元素均不小于T,此過(guò)程稱為線性表的分割。

②對(duì)分割后的子表再按上述原則進(jìn)行反復(fù)分割，直到所有子表為空為止，此時(shí)的線性表就變成有序的了。

2.插入類排序法

插入排序是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。下面主要介紹簡(jiǎn)單插入排序法和希爾排序法。

(1)簡(jiǎn)單插入排序法

簡(jiǎn)單插入排序是把n個(gè)待排序的元素看成一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)，有序表只包含一個(gè)元素，而無(wú)序表則

包含n-1個(gè)元素，每次取無(wú)序表中的第一個(gè)元素插入到有序表中的正確位置，使之成為增加一個(gè)元素的新的有序

表。插入元素時(shí)，插入位置及其后的記錄依次向后移動(dòng)。最后有序表的長(zhǎng)度為n,而無(wú)序表為空，此時(shí)排序完成。

在簡(jiǎn)單插入排序中，每一次比較后最多移掉一個(gè)逆序，因此該排序方法的效率與冒泡排序法相同。在最壞的情況下，

簡(jiǎn)單插入排序需要進(jìn)行n(n-1)/2次比較。

(2)希爾排序法

希爾排序法的基本思路為：將整個(gè)無(wú)序序列分割成若干個(gè)小的子序列并分別進(jìn)行插入排序。

分割方法如下：

①將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列；

②在排序過(guò)程中，逐次減少這個(gè)增量，直到h減到1時(shí)進(jìn)行一次插入排序，排序即可完成。

希爾排序的效率與所選取的增量序列有關(guān)。

3.選擇類排序法

選擇排序的基本思路是通過(guò)每?趟從待排序序列中選出值最小的元素，順序放在已排好序的有序子表的后面，直到

全部序列滿足排序要求為止。下血介紹選擇類排序法中的筒單選擇排序法和堆排序法。

(1)簡(jiǎn)單選擇排序法

簡(jiǎn)單選擇排序的基本思路是：首先從所有n個(gè)待排序的數(shù)據(jù)元素中選擇最小的元素，將該元素與第一個(gè)元素交換，

再?gòu)氖Ｏ碌膎—1個(gè)元素中選出最小的元素與第二個(gè)元素交換。重復(fù)這樣的操作直到所有的元素有序?yàn)橹埂?/p>

簡(jiǎn)單選擇排序在最壞的情況下需要比較n(n-1)/2次。

(2)堆排序法

堆排序的方法如下：

①將一個(gè)無(wú)序序列建成堆；

②將堆頂元素與堆中最后一個(gè)元素交換。忽略己經(jīng)交換到最后的那個(gè)元素，考慮前n—1個(gè)元素構(gòu)成的子序列，只

有左、右子樹是堆，可以將該子樹調(diào)整為堆。這樣反復(fù)下去做第二步，直到剩下的子序列空為止。

在最壞的情況下，堆排序需要比較的次數(shù)為。(n1。g2n)。

例題：對(duì)于長(zhǎng)度為n的線性表，在最壞的情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是（）。

A）冒泡排序?yàn)閚/2B）冒泡排序?yàn)閚

C）快速排序?yàn)閚D）快速排序?yàn)閚（n-1）/2

【答案】D）

【解析】假設(shè)線性表的長(zhǎng)度為n,則在最壞的情況下，冒泡排序需要經(jīng)過(guò)n/2遍的從前往后掃描和n/2遍的從

后往前掃描，需要比較的次數(shù)為n（n-1）/2?？焖倥判蚍ㄔ谧顗牡那闆r下，比較的次數(shù)也是n（n-1）/

2。

為什么只有二叉樹的前序遍歷和后序遍歷不能唯一確定一棵二叉樹？

在二叉樹遍歷中前序和后序中都可以肯定根結(jié)點(diǎn)，在中序是由左至根及右的順序，所以知道前序（或后序）和中序

肯定能唯一確定二叉樹；在前序和后序中只能確定根結(jié)點(diǎn)，而對(duì)于左右子樹的結(jié)點(diǎn)元素則沒(méi)有辦法正確選取，所以

很難確定一棵二叉樹。由此可見(jiàn)需要確定一棵二叉樹的基礎(chǔ)是必須得知道中序遍歷。

1.2程序設(shè)計(jì)基礎(chǔ)

考點(diǎn)9.程序設(shè)計(jì)方法與風(fēng)格

1.程序設(shè)計(jì)方法

程序設(shè)計(jì)是指設(shè)計(jì)、編制、調(diào)試程序的方法和過(guò)程。程序設(shè)計(jì)方法是研究問(wèn)題求解如何進(jìn)行系統(tǒng)構(gòu)造的軟件方

法學(xué)。常用的程序設(shè)計(jì)方法有：結(jié)構(gòu)化程序設(shè)計(jì)方法、軟件工程方法和面向?qū)ο蠓椒ā?/p>

2.程序設(shè)計(jì)風(fēng)格

程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。良好的程序設(shè)計(jì)風(fēng)格可以使程序結(jié)構(gòu)清晰合理，

程序代碼便于維護(hù)，因此程序設(shè)計(jì)風(fēng)格深深地影響著軟件的質(zhì)量和維護(hù)。要形成良好的程序設(shè)計(jì)風(fēng)格，主要應(yīng)注重

和考慮的因素有：源程序文檔化；數(shù)據(jù)說(shuō)明方法；語(yǔ)句的結(jié)構(gòu)；輸入和輸出.

【例1】下列敘述中，不屬于良好程序設(shè)計(jì)風(fēng)格要求的是（）。

A）程序的效率第一，清晰第二B）程序的可讀性好

O程序中要有必要的注釋D）輸入數(shù)據(jù)前要有提示信息

【答案】A）

【解析】著名的“清晰第一，效率第二”的論點(diǎn)已經(jīng)成為主導(dǎo)的程序設(shè)計(jì)風(fēng)格，所以選項(xiàng)A是錯(cuò)誤的，其余選項(xiàng)都

是良好程序設(shè)計(jì)風(fēng)格的要求。

［例2］下列選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是（）o

A）源程序要文檔化B）數(shù)據(jù)說(shuō)明的次序要規(guī)范化

O避免濫用got。語(yǔ)句D）模塊設(shè)計(jì)要保證高耦合、高內(nèi)聚

【答案】D）

【解析】良好的程序設(shè)計(jì)風(fēng)格可以使程序結(jié)構(gòu)清晰合理，程序代碼便于維護(hù)。主要應(yīng)注意和考慮的因素有：①源程

序要文檔化；②數(shù)據(jù)說(shuō)明的次序要規(guī)范化；③語(yǔ)句的結(jié)構(gòu)應(yīng)簡(jiǎn)單直接，不應(yīng)該為提高效率而把語(yǔ)句復(fù)雜化，應(yīng)避免

濫用g。t。語(yǔ)句；④模塊設(shè)計(jì)要保證低耦合、高內(nèi)聚。

考點(diǎn)10.結(jié)構(gòu)化程序設(shè)計(jì)

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

結(jié)構(gòu)化程序設(shè)計(jì)的主要原則可以概括為自頂向下、逐步求精、模塊化及限制使用g。t。語(yǔ)句。

白頂向卜,：在進(jìn)行程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)品先考慮全周目標(biāo)，后考慮具體問(wèn)題。

逐步求精：將復(fù)雜問(wèn)題細(xì)化，細(xì)分為逐個(gè)的小問(wèn)題各依次求解.

模塊化：把程序要解決的總II標(biāo)分解為若干個(gè)目標(biāo).再進(jìn)一步分解為

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

限制使用g。t。語(yǔ)句。

2.結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)

結(jié)構(gòu)化程序設(shè)計(jì)有3種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

3.結(jié)構(gòu)化程序設(shè)計(jì)的原則和方法的應(yīng)用

結(jié)構(gòu)化程序設(shè)計(jì)是一種面向過(guò)程的程序設(shè)計(jì)方法。在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中，需要注意以下幾個(gè)問(wèn)題：應(yīng)使

用程序設(shè)計(jì)語(yǔ)言的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和

一個(gè)出口；用程序語(yǔ)句組成容易識(shí)別的塊，每塊只有一個(gè)入口和?個(gè)出口；復(fù)雜結(jié)構(gòu)應(yīng)該應(yīng)用嵌套的基本控制結(jié)構(gòu)

進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)；對(duì)語(yǔ)言中所沒(méi)有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來(lái)模擬；嚴(yán)格控制g。t。語(yǔ)句的使

用。

下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是（）。

A）自頂向下B）逐步求精C）模塊化D）可復(fù)用

【答案】D）

【解析】自20世紀(jì)70年代以來(lái)，已提出了許多軟件設(shè)計(jì)方法，主要包括：①逐步求精。對(duì)復(fù)雜的問(wèn)題，應(yīng)設(shè)計(jì)

一些子目標(biāo)作過(guò)渡，逐步細(xì)化。②自頂向下。在進(jìn)行程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，

后考慮局部目標(biāo)。一開(kāi)始不要過(guò)多追求細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。③模塊化。一個(gè)復(fù)

雜問(wèn)題，肯定是山若干個(gè)相對(duì)簡(jiǎn)單的問(wèn)題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具

體的小目標(biāo)，每個(gè)小目標(biāo)稱為一個(gè)模塊。而可復(fù)用則是面向?qū)ο蟪绦蛟O(shè)計(jì)的一個(gè)優(yōu)點(diǎn)，不是結(jié)構(gòu)化程序設(shè)計(jì)方法。

考點(diǎn)11面向?qū)ο蟮牟樵冊(cè)O(shè)計(jì)

1.面向?qū)ο蠓椒ǖ谋举|(zhì)

面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方

法來(lái)認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn)題域。

2.面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)

面向?qū)ο蠓椒ㄓ幸韵轮饕獌?yōu)點(diǎn)：

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

穩(wěn)定性好：

可重用性好;

易于開(kāi)發(fā)人型軟件產(chǎn)品;

可維護(hù)性好。

3.面向?qū)ο蠓椒ǖ幕靖拍?/p>

（1）對(duì)象

對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。?duì)象可以用來(lái)表示客觀世界中的任何實(shí)體，它既可以是具體的物理實(shí)體的抽

象，也可以是人為概念，或者是任何有明確邊界和意義的東西。

（2）類

類是具有共同屬性、共同方法的對(duì)象的集合，是關(guān)于對(duì)象的抽象描述，反映屬于該對(duì)象類型的所有對(duì)象的性質(zhì)。

（3）實(shí)例

一個(gè)具體對(duì)象是其對(duì)應(yīng)類的一個(gè)實(shí)例。

（4）消息

消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流

和控制流。

（5）繼承

繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。在面向?qū)ο蠹夹g(shù)中，類組成為具有層次結(jié)構(gòu)的系統(tǒng)：一個(gè)

類的上層可有父類，下層可有子類；一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動(dòng)地共享基類中

定義的數(shù)據(jù)和方法。

（6）多態(tài)性

對(duì)象根據(jù)所接受的信息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)可以有完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性。

小提示

當(dāng)使用“對(duì)象”這個(gè)術(shù)語(yǔ)時(shí)，既可以指一個(gè)具體的對(duì)象，也可以泛指一般的對(duì)象。但是當(dāng)使用“實(shí)例”這個(gè)術(shù)語(yǔ)時(shí)，

則必須是指一個(gè)具體的對(duì)象。

在面向?qū)ο蟮姆椒ㄖ校瑢?shí)現(xiàn)信息隱蔽是依靠（）0

A）對(duì)象的繼承B）對(duì)象的多態(tài)C）對(duì)象的封裝D）對(duì)象的分類

【答案】O

【解析】對(duì)象是由數(shù)據(jù)和操作組成的封裝體，與客觀實(shí)體有直接的對(duì)應(yīng)關(guān)系。對(duì)象之間通過(guò)傳遞消息互相聯(lián)系，以

模擬現(xiàn)實(shí)世界中不同事物彼此之間的關(guān)系。面向?qū)ο蠹夹g(shù)的3個(gè)重要特性為：封裝性、繼承性和多態(tài)性。

對(duì)象是面向?qū)ο笞罨镜母拍睿?qǐng)問(wèn)對(duì)象有哪些特點(diǎn)？

標(biāo)識(shí)唯一性，指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來(lái)區(qū)分；分類性，指可以將具體相同屬性和操作的對(duì)象抽

象成類；多態(tài)性，指同?個(gè)操作可以是不同對(duì)象的行為；封裝性，指從外面不能直接使用對(duì)象的處理能力，也不能

直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。

1.3軟件工程基礎(chǔ)

考點(diǎn)12軟件工程基本概念

1,軟件定義與軟件特點(diǎn)

(1)軟件的定義

軟件(sofeware)是與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。

計(jì)算機(jī)軟件山兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用

等有關(guān)的文檔。

(2)軟件的特點(diǎn)

軟件主要包括以下幾個(gè)特點(diǎn)：

軟件是?種邏輯實(shí)體，具有抽象性：

軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程.；

軟件在運(yùn)行、使用期間，不存在磨損、名化問(wèn)題;

軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題：

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

軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。

2.軟件危機(jī)與軟件工程

(1)軟件危機(jī)

軟件危機(jī)泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)中所遇到的一系列嚴(yán)重問(wèn)題。具體地說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件

危機(jī)主要表現(xiàn)在以下幾方面：

軟件需求的增K得不到滿足：

軟件的開(kāi)發(fā)成木和進(jìn)度無(wú)法控制；

軟件質(zhì)量難以保證：

軟件不可維護(hù)或維護(hù)程度『常低；

軟件的成本不斷提高：

軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。

總之，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。

(2)軟件工程

軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程包括兩

方面內(nèi)容：軟件開(kāi)發(fā)技術(shù)和軟件工程管理。軟件工程包括3個(gè)要素，即方法、工具和過(guò)程。軟件的核心思想是把軟

件產(chǎn)品看做是一個(gè)工程產(chǎn)品來(lái)處理。

3.軟件工程過(guò)程與軟件生命周期

(1)軟件工程過(guò)程

軟件工程過(guò)程是把輸入轉(zhuǎn)化成為輸出的一組彼此相關(guān)的資源和活動(dòng)。

(2)軟件生命周期

通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用的過(guò)程稱為軟件生命周期。軟件生命周期主要包括軟件定義、

軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)等3個(gè)階段。其中軟件生命周期的主要活動(dòng)階段包括可行性研究與計(jì)劃制定、需求分析、

軟件設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測(cè)試和運(yùn)行維護(hù)等。

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

(1)軟件工程的目標(biāo)

軟件工程需達(dá)到的目標(biāo)是：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重

用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。

（2）軟件工程的原則

為了實(shí)現(xiàn)上述的軟件工程目標(biāo)，在軟件開(kāi)發(fā)過(guò)程中，必須遵循軟件工程的基本原則，這些原則適用于所有的軟件項(xiàng)

目。這些基本原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性等。

5.軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境

軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境的使用提高了軟件的開(kāi)發(fā)效率、維護(hù)效率和軟件質(zhì)量。

（1）軟件開(kāi)發(fā)工具

軟件開(kāi)發(fā)工具的產(chǎn)生、發(fā)展和完善促進(jìn)了軟件的開(kāi)發(fā)速度和質(zhì)量的提高。軟件開(kāi)發(fā)工具從初期的單項(xiàng)工具逐步向集

成工具發(fā)展。與此同時(shí)，軟件開(kāi)發(fā)的各種方法也必須得到相應(yīng)的軟件工具的支持，否則方法就很難有效地實(shí)施。

（2）軟件開(kāi)發(fā)環(huán)境

軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)過(guò)程的軟件工具集合.這些軟件工具按照一定的方法或模式組合起來(lái)，支持軟件

生命周期的各個(gè)階段和各項(xiàng)任務(wù)的完成。

計(jì)算機(jī)輔助軟件工程（CASE）是當(dāng)前軟件開(kāi)發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。CASE將各種軟件工

具、開(kāi)發(fā)機(jī)器和一個(gè)存放過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。一個(gè)良好的工程環(huán)境可以最大限度

地降低軟件開(kāi)發(fā)的技術(shù)難度，并能使軟件開(kāi)發(fā)的質(zhì)量得到保證。

下列描述中正確的是（）o

A）程序就是軟件B）軟件開(kāi)發(fā)不受計(jì)算機(jī)系統(tǒng)的限制

C）軟件既是邏輯實(shí)體，又是物理實(shí)體D）軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合

【答案】D）

【解析】計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件具

有以下幾個(gè)特點(diǎn)：①軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性；②軟件的生產(chǎn)過(guò)程與硬件不同，沒(méi)有明

顯的制作過(guò)程；③軟件在運(yùn)行、使用期間，不存在磨損、老化問(wèn)題；④軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有不同程

度的依賴性，這導(dǎo)致了軟件移植的問(wèn)題；⑤軟件復(fù)雜性高，成本昂貴；⑥軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。

考點(diǎn)I3結(jié)構(gòu)化分析方法

1?需求分析和需求分析方法

（1）需求分析

軟件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析的任務(wù)是發(fā)現(xiàn)需求、求

精、建模和定義需求的過(guò)程。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型利控制模型。需求分析階段的工作可以概

括為4個(gè)方面：需求獲取、需求分析、編寫需求規(guī)格說(shuō)明書、需求評(píng)審。

（2）需求分析方法

常用的需求分析方法有結(jié)構(gòu)化分析方法和面向?qū)ο蠓治龇椒ā?/p>

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

（1）結(jié)構(gòu)化分析方法介紹

結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。

結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流，自頂向下逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要

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

（2）結(jié)構(gòu)化分析方法的常用工具

常用工具包括數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、判斷樹、判斷表。下面主要介紹數(shù)據(jù)流圖和數(shù)據(jù)字典。

數(shù)據(jù)流圖（DateFlowDiagram,DFD）是描述數(shù)據(jù)處理的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)

的功能建模。

數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過(guò)程。

數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)，一般在旁邊標(biāo)注數(shù)據(jù)流名

存儲(chǔ)文件：表示處理過(guò)程中存放各種數(shù)據(jù)的文件

數(shù)據(jù)的源點(diǎn)/終點(diǎn)：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體

數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及明確的、

嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)■于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。通常數(shù)據(jù)字典包含

的信息有名稱、別名、何處使用/如何使用、內(nèi)容描述、補(bǔ)充信息等。數(shù)據(jù)字典中有4種類型的條目：數(shù)據(jù)流、數(shù)

據(jù)項(xiàng)、數(shù)據(jù)存儲(chǔ)和加工。

小提示：

數(shù)據(jù)流圖與程序流程圖中用箭頭表示的控制流有本質(zhì)的不同，千萬(wàn)不要混淆。此外，數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)流都是數(shù)據(jù)，

僅僅是所處的狀態(tài)不同。數(shù)據(jù)存儲(chǔ)是處于靜止?fàn)顟B(tài)的數(shù)據(jù)，數(shù)據(jù)流則是處于運(yùn)動(dòng)中的數(shù)據(jù)。

3.軟件需求規(guī)格說(shuō)明書

軟件需求規(guī)格說(shuō)明書是需求分析階段的最后結(jié)果，是軟件開(kāi)發(fā)中的重要文檔之一。

軟件需求規(guī)格說(shuō)明書的標(biāo)準(zhǔn)主要有：正確性、無(wú)歧義性、完整性、可驗(yàn)證性、-致性、可理解性、可修改性和可追

蹤性。

考點(diǎn)14結(jié)構(gòu)化設(shè)計(jì)方法

1,軟件設(shè)計(jì)的基本概念及方法

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

軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程。軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概

括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。

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

軟件設(shè)計(jì)遵循軟件工程的基本目標(biāo)和原則，建立了適用于在軟件設(shè)計(jì)中應(yīng)該遵循的基本原理和與軟件設(shè)計(jì)有關(guān)的概

念，主要包括抽象、模塊化、信息隱藏以及模塊的獨(dú)立性。下面主要介紹模塊獨(dú)立性的一些度量標(biāo)準(zhǔn)。模塊的獨(dú)立

程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性的定性度量標(biāo)準(zhǔn)是使用耦合性和內(nèi)聚性。耦合性是模

塊間互相聯(lián)結(jié)的緊密程度的度量，內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。通常較優(yōu)秀的軟

件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚、低耦合。

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

結(jié)構(gòu)化設(shè)計(jì)就是采用最佳可能的方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分及各部分之間的內(nèi)部聯(lián)系的技術(shù)。也就是說(shuō)，結(jié)構(gòu)化

設(shè)計(jì)是這樣一個(gè)過(guò)程，它決定用哪些方法把哪些部分聯(lián)系起來(lái)，才能解決好某個(gè)具體有清楚定義的問(wèn)題。

結(jié)構(gòu)化設(shè)計(jì)方法的基本思想是將軟件設(shè)計(jì)成山相對(duì)獨(dú)立、單一功能的模塊組成的結(jié)構(gòu)。

小提示：

一般來(lái)說(shuō)，要求模塊之間的耦合盡可能弱，即模塊盡可能獨(dú)立，且要求模塊的內(nèi)聚程度盡可能高。內(nèi)聚性和耦合性

是一個(gè)問(wèn)題的兩個(gè)方面，耦合性程度弱的模塊，其內(nèi)聚程度一定高。

2.概要設(shè)計(jì)

(1)概要設(shè)計(jì)的任務(wù)

軟件概要設(shè)計(jì)的任務(wù)是：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；編寫概要設(shè)計(jì)文檔；概要設(shè)計(jì)文檔評(píng)審。

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

在需求分析設(shè)計(jì)階段產(chǎn)生了數(shù)據(jù)流圖。面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些映射方法可以

把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示的軟件結(jié)構(gòu)。DFD從系統(tǒng)的輸入數(shù)據(jù)流到系統(tǒng)的輸出數(shù)據(jù)流的一連串連續(xù)加工形成

了一條信息流。

數(shù)據(jù)流圖的信息流可分為兩種類型：變換流和事務(wù)流。相應(yīng)地，數(shù)據(jù)流圖有兩種典型的結(jié)構(gòu)形式：變換型和事務(wù)型。

面向數(shù)據(jù)流的結(jié)構(gòu)化設(shè)計(jì)過(guò)程如下：

①確認(rèn)數(shù)據(jù)流圖的類型(是事務(wù)型還是變換型)；

②說(shuō)明數(shù)據(jù)流的邊界；

③把數(shù)據(jù)流圖映射為程序結(jié)構(gòu)；

④根據(jù)設(shè)計(jì)準(zhǔn)則對(duì)產(chǎn)生的結(jié)構(gòu)進(jìn)行優(yōu)化。

(3)結(jié)構(gòu)化設(shè)計(jì)的準(zhǔn)則

大量的實(shí)踐表明，以下的設(shè)計(jì)準(zhǔn)則可以借鑒為設(shè)計(jì)的指導(dǎo)和對(duì)軟件結(jié)構(gòu)圖進(jìn)行優(yōu)化的條件：

提高模塊獨(dú)立性：

模塊規(guī)模應(yīng)該適中；

深度、寬度、扇入和扇出都應(yīng)適當(dāng)；

模塊的作川域應(yīng)該在控制域之內(nèi)；

降低模塊之間接口的發(fā)柴程度；

設(shè)計(jì)單入口、單出口的模塊；

模塊功能應(yīng)該可以預(yù)測(cè)。

小提示：

扇出過(guò)大意味著模塊過(guò)分復(fù)雜，需要控制和協(xié)調(diào)過(guò)多的下級(jí)模塊；扇出過(guò)小時(shí)可以把下級(jí)模塊進(jìn)一步分解成若干個(gè)

子功能模塊，或者合并到它的上級(jí)模塊中去。扇入越大則共享該模塊的上級(jí)模塊數(shù)目越多，這是有好處的，但是不

能犧牲模塊的獨(dú)立性而單純地追求高扇入。大量實(shí)踐表明，設(shè)計(jì)的很好的軟件結(jié)構(gòu)通常頂層扇出比較高，中層扇出

較少，底層模塊有高扇入。

3.詳細(xì)設(shè)計(jì)

(1)詳細(xì)設(shè)計(jì)的任務(wù)

詳細(xì)設(shè)計(jì)的任務(wù)，是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法

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

(2)詳細(xì)設(shè)計(jì)的工具

常見(jiàn)的過(guò)程設(shè)計(jì)工具有：

圖形［北：程序流程圖、N—S、PAD及HIPO。

表格I：具：判定表。

語(yǔ)言r.n：PDL(偽碼)。

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

A)概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)B)數(shù)據(jù)設(shè)計(jì)與接口設(shè)計(jì)

O軟件結(jié)構(gòu)設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)D)過(guò)程設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)

【答案】A)

【解析】從工程管理角度看，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)將軟件需求轉(zhuǎn)化為軟件體系結(jié)

構(gòu)、確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式；詳細(xì)設(shè)計(jì)確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)?shù)?/p>

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

考點(diǎn)15軟件測(cè)試

1,軟件測(cè)試的目的及準(zhǔn)則

(1)軟件測(cè)試的目的

軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。

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

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

(2)軟件測(cè)試的準(zhǔn)則

鑒于軟件測(cè)試的重要性，要做好軟件測(cè)試，設(shè)計(jì)出有效的測(cè)試方案和好的測(cè)試用例，軟件測(cè)試人員需要充分理解和

運(yùn)用軟件測(cè)試的一些基本準(zhǔn)側(cè)：

所有測(cè)試都應(yīng)追溯到用戶需求：

嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性；

充分注意測(cè)試中的群集現(xiàn)象：

程序員應(yīng)避免檢杳自己的程序；

窮舉測(cè)試不可能；

妥善保存測(cè)試計(jì)劃、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告，為維護(hù)提供方便。

2.軟件測(cè)試技術(shù)和方法綜述

軟件測(cè)試的方法是多種多樣的，對(duì)于軟件測(cè)試方法和技術(shù)，可以從不同的角度分類。

若從是否需要執(zhí)行被測(cè)軟件的角度，可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。若按照功能劃分，可以分為白盒測(cè)試和黑盒測(cè)

試。

(1)靜態(tài)測(cè)試與動(dòng)態(tài)測(cè)試

靜態(tài)測(cè)試不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行分析，包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。其中代碼檢

查分為代碼審查、代碼走查、桌面檢查、靜態(tài)分析等具體形式。

動(dòng)態(tài)測(cè)試是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。設(shè)計(jì)高效、合理的測(cè)試用例是動(dòng)態(tài)測(cè)試的關(guān)鍵。

測(cè)試用例就是為測(cè)試設(shè)計(jì)的數(shù)據(jù)，由測(cè)試輸入數(shù)據(jù)和預(yù)期的輸出結(jié)果兩部分組成?測(cè)試用例的設(shè)計(jì)方法一般分為兩

類：黑盒測(cè)試和白盒測(cè)試。

(2)白盒測(cè)試方法與測(cè)試用例設(shè)計(jì)

白盒測(cè)試也稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試，它根據(jù)程序的內(nèi)部邏輯來(lái)設(shè)計(jì)測(cè)試用例，檢查程序中的邏輯通路是否都按

預(yù)定的要求正確地工作。

白盒測(cè)試的主要方法有邏輯覆蓋測(cè)試、基本路徑測(cè)試等。

(3)黑盒測(cè)試方法與測(cè)試用例設(shè)計(jì)

黑盒測(cè)試也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試，它根據(jù)規(guī)格說(shuō)明書的功能來(lái)設(shè)計(jì)測(cè)試用例，檢查程序的功能是否符合規(guī)

格說(shuō)明的要求。

黑盒測(cè)試的主要診斷方法有等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖法等，主要用于軟件確認(rèn)測(cè)試。

3.軟件測(cè)試的實(shí)施

軟件測(cè)試的實(shí)施過(guò)程主要有4個(gè)步驟：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試(驗(yàn)收測(cè)試)和系統(tǒng)測(cè)試。

(1)單元測(cè)試

單元測(cè)試也稱模塊測(cè)試，模塊是軟件設(shè)計(jì)的最小單位。單元測(cè)試是對(duì)模塊進(jìn)行正確性的檢驗(yàn)，以期盡早發(fā)現(xiàn)各模塊

內(nèi)部可能存在的各種錯(cuò)誤。

(2)集成測(cè)試

集成測(cè)試也稱組裝測(cè)試，它是對(duì)各模塊按照設(shè)計(jì)要求組裝成的程序進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。

(3)確認(rèn)測(cè)試

確認(rèn)測(cè)試的任務(wù)是用戶根據(jù)合同進(jìn)行，確定系統(tǒng)功能和性能是否可接受。確認(rèn)測(cè)試需要用戶積極參與，或者以用戶

為主進(jìn)行。

(4)系統(tǒng)測(cè)試

系統(tǒng)測(cè)試是將軟件系統(tǒng)與硬件、外設(shè)或其他元素結(jié)合在一起，對(duì)整個(gè)軟件系統(tǒng)進(jìn)行測(cè)試。

系統(tǒng)測(cè)試的內(nèi)容包括功能測(cè)試、操作測(cè)試、配置測(cè)試、性能測(cè)試、安全測(cè)試、外部接口測(cè)試等。

下列敘述中正確的是。

A)軟件測(cè)試應(yīng)該山程序開(kāi)發(fā)者來(lái)完成B)程序經(jīng)調(diào)試后一般不需要再測(cè)試

C)軟件維護(hù)只包括對(duì)程序代碼的維護(hù)D)以上3種說(shuō)法都不對(duì)

【答案】D)

【解析】程序調(diào)試的任務(wù)是診斷利改正程序中的錯(cuò)誤。軟件測(cè)試則不同，軟件測(cè)試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤。

先要發(fā)現(xiàn)軟件的錯(cuò)誤，然后借助于一定的調(diào)試工具去找出軟件錯(cuò)誤的具體位置。軟件測(cè)試貫穿整個(gè)軟件生命周期，

調(diào)試主要在開(kāi)發(fā)階段。為了實(shí)現(xiàn)更好的測(cè)試效果，應(yīng)該由獨(dú)立的第三方來(lái)構(gòu)造測(cè)試。軟件的運(yùn)行和維護(hù)是指將已交

付的軟件投入運(yùn)行，并在運(yùn)行使用中不斷地維護(hù)，根據(jù)新提出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改。

考點(diǎn)16程序的調(diào)試

1.程序調(diào)試的基本概念

調(diào)試是作為成功測(cè)試之后出現(xiàn)的步驟，也就是說(shuō)，調(diào)試是在測(cè)試發(fā)現(xiàn)錯(cuò)誤之后排除錯(cuò)誤的過(guò)程。軟件測(cè)試貫穿整個(gè)

軟件生命期，而調(diào)試則主要在開(kāi)發(fā)階段。

程序調(diào)試活動(dòng)山兩部分組成：

根據(jù)借誤的跡象確定程序中錯(cuò)誤的確切性質(zhì)、原因和位置；

對(duì)程序進(jìn)行修改，排除這個(gè)錯(cuò)誤。

(1)調(diào)試的基本步驟

①錯(cuò)誤定位；

②修改設(shè)計(jì)和代碼，以排除錯(cuò)誤；

③進(jìn)行回歸測(cè)試，防止引入新的錯(cuò)誤。

(2)調(diào)試的原則

調(diào)試活動(dòng)山對(duì)程序中錯(cuò)誤的定性、定位和排錯(cuò)兩部分組成，因此調(diào)試原則也應(yīng)從這兩個(gè)方面考慮：①確定錯(cuò)誤的性

質(zhì)和位置的原則；②修改錯(cuò)誤的原則。

2.程序調(diào)試方法

調(diào)試的關(guān)鍵在于推斷程序內(nèi)部的錯(cuò)誤位置及原因。從是否跟蹤和執(zhí)行程序的角度出發(fā)，它類似于軟件測(cè)試，分為靜

態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試則

是輔助靜態(tài)調(diào)試的。主要的程序調(diào)試方法有強(qiáng)行排錯(cuò)法、回溯法和原因排除法。其中強(qiáng)行排錯(cuò)法是傳統(tǒng)的調(diào)試方法，

回溯法適合于小規(guī)模程序的排錯(cuò)，原因排除法是通過(guò)演繹和歸納以及二分法來(lái)實(shí)現(xiàn)的。

程序調(diào)試的目的是()。

A)發(fā)現(xiàn)錯(cuò)誤B)更正錯(cuò)誤C)改善性能D)驗(yàn)證程序的正確性

【答案】B)

【解析】程序調(diào)試的目的是診斷和改正程序中的錯(cuò)誤，改正以后還需要進(jìn)行測(cè)試。

軟件設(shè)計(jì)的重要性和地位主要有哪些？

軟件開(kāi)發(fā)階段(設(shè)計(jì)、編碼、測(cè)試)占據(jù)軟件項(xiàng)目開(kāi)發(fā)總成本的絕大部分，是在軟件開(kāi)發(fā)中形成質(zhì)量的關(guān)鍵環(huán)節(jié)；

軟件設(shè)計(jì)是開(kāi)放階段最重要的步驟，是將需求準(zhǔn)確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑；軟件設(shè)計(jì)作出的決

策，最終影響軟件實(shí)現(xiàn)的成??；設(shè)計(jì)是軟件工程和軟件維護(hù)的基礎(chǔ)。

1.4數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)

考點(diǎn)17.數(shù)據(jù)庫(kù)系統(tǒng)的基本概念

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

（1）數(shù)據(jù)

數(shù)據(jù)（Data）是描述事物的符號(hào)記錄。

（2）數(shù)據(jù)庫(kù)

數(shù)據(jù)庫(kù)（DataBase,簡(jiǎn)稱DB）是指長(zhǎng)期存儲(chǔ)在計(jì)算機(jī)內(nèi)的、有組織的、可共享的數(shù)據(jù)集合。

（3）數(shù)據(jù)庫(kù)管理系統(tǒng)

數(shù)據(jù)庫(kù)管理系統(tǒng)（DataBaseManagementSystem,DBMS）是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，它是一個(gè)

系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、操縱、維護(hù)、控制、保護(hù)，

以及數(shù)據(jù)服務(wù)等。

數(shù)據(jù)庫(kù)管理系統(tǒng)的主要類型有4種：文件管理系統(tǒng)、層次數(shù)據(jù)庫(kù)系統(tǒng)、網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)和關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)，其中關(guān)

系數(shù)據(jù)庫(kù)系統(tǒng)的應(yīng)用最廣泛。

（4）數(shù)據(jù)庫(kù)系統(tǒng)

數(shù)據(jù)庫(kù)系統(tǒng)（DatabaseSystem,DBS）,是指引進(jìn)數(shù)據(jù)庫(kù)技術(shù)后的整個(gè)計(jì)算機(jī)系統(tǒng)，能實(shí)現(xiàn)有組

織地、動(dòng)態(tài)地存儲(chǔ)大量相關(guān)數(shù)據(jù)，提供數(shù)據(jù)處理和信息資源共享的便利手段。

小提示

在數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)庫(kù)管理系統(tǒng)和數(shù)據(jù)庫(kù)三者之間，數(shù)據(jù)庫(kù)管理系統(tǒng)是數(shù)據(jù)庫(kù)系統(tǒng)的組成部分，數(shù)據(jù)庫(kù)又是數(shù)據(jù)庫(kù)

管理系統(tǒng)的管理對(duì)象，因此我們可以說(shuō)數(shù)據(jù)庫(kù)系統(tǒng)包括數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)管理系統(tǒng)又包括數(shù)據(jù)庫(kù)。

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

數(shù)據(jù)管理發(fā)展至今已經(jīng)經(jīng)歷了3個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。

一般認(rèn)為，未來(lái)的數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)支持?jǐn)?shù)據(jù)管理、對(duì)象管理和知識(shí)管理，應(yīng)該具有面向?qū)ο蟮幕咎卣?。在關(guān)于數(shù)據(jù)

庫(kù)的諸多新技術(shù)中，有3種是比較重要的，它們是：面向?qū)ο髷?shù)據(jù)庫(kù)系統(tǒng)、知識(shí)庫(kù)系統(tǒng)、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的擴(kuò)充。

（1）面向?qū)ο髷?shù)據(jù)庫(kù)系統(tǒng)

用面向?qū)ο蠓椒?gòu)筑面向?qū)ο髷?shù)據(jù)庫(kù)模型，使其具有比關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)更為通用的能力。

（2）知識(shí)庫(kù)系統(tǒng)

用人工智能中的方法，特別是用邏輯知識(shí)表示方法構(gòu)筑數(shù)據(jù)模型，使其模型具有特別通用的能力。

（3）關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的擴(kuò)充

利用關(guān)系數(shù)據(jù)庫(kù)作進(jìn)一步的擴(kuò)展，使其在模型的表達(dá)能力與功能上有進(jìn)一步的加強(qiáng)，如與網(wǎng)絡(luò)技術(shù)相結(jié)合的Web

數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)及嵌入式數(shù)據(jù)庫(kù)等。

3.數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)

數(shù)據(jù)庫(kù)系統(tǒng)具有如下特點(diǎn)：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨(dú)立性、數(shù)據(jù)統(tǒng)一管理與控制。

4.數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部機(jī)構(gòu)體系

數(shù)據(jù)模式是數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式，具有不同的層次與結(jié)構(gòu)方式。

數(shù)據(jù)庫(kù)系統(tǒng)在其內(nèi)部具有3級(jí)模式及2級(jí)映射，3級(jí)模式分別是概念模式、內(nèi)模式與外模式；2級(jí)映射是外模式/

概念模式的映射和概念模式/內(nèi)模式的映射。3級(jí)模式與2級(jí)映射構(gòu)成了數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部的抽象結(jié)構(gòu)體系。模式的

3個(gè)級(jí)別層次反映了模式的3個(gè)不同環(huán)境以及它們的不同要求，其中內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物

理結(jié)構(gòu)中的實(shí)際存儲(chǔ)形式；概念模式處于中層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求；而外模式則位于最外層，它

反映了用戶對(duì)數(shù)據(jù)的要求。

小提示

一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式和一個(gè)內(nèi)模式，有多個(gè)外模式。

【例1】下列敘述中正確的是（）。

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

B）數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問(wèn)題

C）數(shù)據(jù)庫(kù)管理系統(tǒng)就是數(shù)據(jù)庫(kù)系統(tǒng)

D）以上3種說(shuō)法都不對(duì)

【答案】B）

【解析】數(shù)據(jù)庫(kù)系統(tǒng)（DatabaseSystem,DBS）,是由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、

計(jì)算機(jī)硬件、操作系統(tǒng)及數(shù)據(jù)

庫(kù)管理員等組成。作為處理數(shù)據(jù)的系統(tǒng)，數(shù)據(jù)庫(kù)技術(shù)的主要目的就是解決數(shù)據(jù)的共享問(wèn)題。

【例2］在數(shù)據(jù)庫(kù)系統(tǒng)中，用戶所見(jiàn)到的數(shù)據(jù)模式為（）。

A）概念模式B）外模式C）內(nèi)模式D）物理模式

【答案】B）

【解析】概念模式是數(shù)據(jù)庫(kù)系統(tǒng)中對(duì)全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）的公共數(shù)據(jù)視圖，它主要描述

數(shù)據(jù)的記錄類型及數(shù)據(jù)間的關(guān)系，還包括數(shù)據(jù)間的語(yǔ)義關(guān)系等。數(shù)據(jù)庫(kù)管理系統(tǒng)的3級(jí)模式結(jié)構(gòu)由外模式、模式、

內(nèi)模式組成。數(shù)據(jù)庫(kù)的外模式也叫做用戶級(jí)數(shù)據(jù)庫(kù)，是用戶所看到和理解的數(shù)據(jù)庫(kù)，是從概念模式導(dǎo)出的子模式，

用戶可以通過(guò)子模式描述語(yǔ)言來(lái)描述用戶級(jí)數(shù)據(jù)庫(kù)的記錄，還可以利用數(shù)據(jù)語(yǔ)言對(duì)這些記錄進(jìn)行操作。內(nèi)模式（或

存儲(chǔ)模式、物理模式）是指數(shù)據(jù)在數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)的存儲(chǔ)介質(zhì)上的表示，是對(duì)數(shù)據(jù)的物理結(jié)構(gòu)和存取方式的描述。

考點(diǎn)18數(shù)據(jù)模型

1,數(shù)據(jù)模型的基本概念

數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，而數(shù)據(jù)模型則是數(shù)據(jù)特征的抽象。它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)

行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。

數(shù)據(jù)模型所描述的內(nèi)容有3部分，即數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。數(shù)據(jù)模型按不同的應(yīng)用層次分為3種類

型，即概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。目前，邏輯數(shù)據(jù)模型也有很多種，較為成熟并先后被人們大

量使用過(guò)的有層次模型、網(wǎng)狀模型關(guān)系、模型、面向?qū)ο竽Ｐ偷取?/p>

2.E—R模型

E-R模型（實(shí)體聯(lián)系模型）將現(xiàn)實(shí)世界的要求轉(zhuǎn)化成實(shí)體、聯(lián)系、屬性等幾個(gè)基本概念，以及它們之間的兩種基

本連接關(guān)系，并且可以用E-R圖非常直觀地表示出來(lái)。E-R圖提供了表示實(shí)體、屬性和聯(lián)系的方法。

實(shí)體：客觀存在并且可以相互區(qū)別的事物，川矩形表示，矩形框內(nèi)寫明實(shí)體名。

屬性：描述實(shí)體的特性，川橢圓形表示，并用無(wú)向邊將其。相應(yīng)的實(shí)體連接起來(lái)，

聯(lián)系：實(shí)體之間的對(duì)應(yīng)關(guān)系，它反映現(xiàn)實(shí)世界出物之間的相互聯(lián)系，用菱形表示，菱形框內(nèi)寫明聯(lián)系名。在現(xiàn)實(shí)

世界中，實(shí)體之間的聯(lián)系可以分為3種類型：“一對(duì)一”的聯(lián)系（簡(jiǎn)記為1：1）、“一對(duì)多”的聯(lián)系（簡(jiǎn)記為1：

n）、“多對(duì)多”的聯(lián)系（簡(jiǎn)記為M:N或m：n）。

3.層次模型

層次模型是用樹形結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模式。在層次模型中，結(jié)點(diǎn)是實(shí)體，樹枝是聯(lián)系，從上到下是一對(duì)

多的關(guān)系。

層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，自頂向下，層次分明。其缺點(diǎn)是：受文件系統(tǒng)影響大，模型受限制多，物理成分

復(fù)雜，操作與使用均不理想，且不適用于表示非層次性的聯(lián)系。

4.網(wǎng)狀模型

網(wǎng)狀模型是用網(wǎng)狀結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型?？梢哉f(shuō)，網(wǎng)狀模型是層次模型的擴(kuò)展，表示多個(gè)從屬關(guān)系的

層次結(jié)構(gòu)，呈現(xiàn)一種交叉關(guān)系。

網(wǎng)狀模型是以記錄型為結(jié)點(diǎn)的網(wǎng)絡(luò)，它反映現(xiàn)實(shí)世界中較為復(fù)雜的事物間的聯(lián)系。

5.關(guān)系模型

（1）關(guān)系的數(shù)據(jù)結(jié)構(gòu)

關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱表。二維表由表框架及表的元組組成。表框架是由n個(gè)命名的屬性組成，n稱為

屬性元數(shù)。每個(gè)屬性都有一個(gè)取值范圍，稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可

以存放數(shù)據(jù)，每行數(shù)