計算機公共知識

計算機公共基礎知識

考點1.算法的基本概念

算法是指解題方案的準確而完整的描述。

(1)算法的基本特征

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

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

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

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

擁有足夠的情報：一個算法是否有效，還取決「為算法所提供的情報是否足夠。

(2)算法的基本要素

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

時數(shù)據(jù)對軟的運算和操作：

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

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

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

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

進行順序稱為算法的控制結(jié)構(gòu)。算法的功能不僅取決于所選用的操作，還與各操作之間的進行順序有關。基本的控

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

(3)算法設計的基本方法

算法設計的基本方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。

2.算法復雜度

算法復雜度主要包括時間復雜度和空間復雜度。

(1)算法的時間復雜度

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

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

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

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

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

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

(2)算法的空間復雜度

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

算法程序所小的空間；

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

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

在許多實際問題中，為了減小算法所占的存儲空間，通常采用壓縮存儲技術，用于減小不必要的額外空間。

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

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

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

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

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

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

關系。

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

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

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

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

重要的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

構(gòu)。

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

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

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

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

D）以上3種說法都不對

【答案】A）

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

在無序存儲的表中查找的效率高很多。

考點3.線性表的基本概念

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

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

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

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

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

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

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

小提示：

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

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

的長度，當n=0時稱為空表。

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

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

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

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

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

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

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

3.線性表的插入運算

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

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

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

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

小提示

一般會為線性表開辟一個大于線性表長度的存儲空間，經(jīng)過多次插入運算，可能出現(xiàn)存儲空間已滿的情況，如果此

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

如果需要在線性表末尾進行插入運算，則只需要在表的末尾增加一個元素即可，而不需要移動線性表中的元素。如

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

4.線性表的刪除運算

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

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

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

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

顯然，如果刪除運算在線性表的末尾進行，即刪除第n個元素，則不需要移動線性表中的元素。如果要刪除第1個

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

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

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

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

A）存儲密度大

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

C）可以通過計算機直接確定第i個結(jié)點的存儲地址

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

【答案】B）

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

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

移動

個元素。

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

【答案】D）

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

要移動n—i+1個元素。

考點4.棧和隊列

1.棧及其基本運算

（1）棧的基本概念

棧實際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運算都只在線性表的一

端進行。在棧中，允許插入與刪除的一端稱為棧頂（t。p）,另一端稱為棧底（bottom）。當棧中沒有元素

時則稱為空棧。棧也被稱為"先進后出"表或"后進先出"表。

（2）棧的特點

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

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

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

顯棧具有記憶作用；

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

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

（3）棧的順序存儲及其運算

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

入棧運算：在板頂位置插入一個新元索；

退棧運算：取出棧頂元素并賦給一個指定的變量；

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

2.隊列及其基本運算

（1）隊列的基本概念

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

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

一個位置。因此隊列又稱為“先進先出”的線性表。插入元素稱為入隊運算，刪除元素稱為退隊運算。

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

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

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

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

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

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

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

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

小提示

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

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

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

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

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

【答案】D）

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

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

【例2】下列關于棧的描述正確的是（）。

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

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

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

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

【答案】C）

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

考點5.線性鏈表

1.線性鏈表的基本概念

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

存儲各數(shù)據(jù)元素之間的前后件關系。為此，在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分稱為數(shù)據(jù)域，用于

存放數(shù)據(jù)元素值；另一部分稱為指針域，用于存放下一個數(shù)據(jù)元素的存儲序號，即指向后件結(jié)點。鏈式存儲結(jié)構(gòu)既

可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。線性表鏈式存儲結(jié)構(gòu)的特點是用一組不連續(xù)的存儲單元存儲線性表中

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

來表示。

2.線性鏈表的基本運算

線性鏈表主要包括以下幾種運算：

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

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

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

將?個線性徒表按要求進行分解：

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

復制線性鏈表;

線性鏈表的排序;

線性鏈表的杳找。

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

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

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

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

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

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

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

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

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

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

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

A）線性鏈表是線性表的鏈式存儲結(jié)構(gòu)B）棧與隊列是非線性結(jié)構(gòu)

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

【答案】A）

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

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

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

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

考點6.樹和二叉樹

1.樹的基本概念

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

集合，n=0的樹稱為空樹；當nW0時，樹中的結(jié)點應該滿足以下兩個條件：有且僅有一個沒有前驅(qū)的結(jié)點稱之

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

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

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

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

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

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

樹的深度。

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

（1）二叉樹的定義

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

二叉子樹所組成。當集合為空時,稱該二叉樹為空二叉樹。

二叉樹具有以下特點：

二義樹可以為空，空的二叉樹沒有結(jié)點，作空二叉樹有且只有?個根結(jié)點；

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

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

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

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

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

滿二叉樹與完全二叉樹的關系：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

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

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

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

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

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

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

在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點由數(shù)據(jù)域和指針域組成。由于每

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

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

鏈式存儲結(jié)構(gòu)也稱為二叉鏈表。對于滿二叉樹與完全二叉樹可以按層次進行順序存儲。

4.二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷主要是針對非空二叉樹的；對于空二叉樹，則

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

（1）前序遍序（DLR）

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

（2）中序遍歷（LDR）

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

（3）后序遍歷（LRD）

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

小提示

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

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

二叉樹。

考點7.查找技術

1,順序查找

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

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

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

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

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

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

序線性表，若采用鏈式存儲結(jié)構(gòu)，也只能進行順序查找。

2.二分查找

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

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

線性表是有序衣。

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

對于長度為n的有序線性表，利用二分法查找元素x的過程如下：

（1）將x與線性表的中間項進行比較；

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

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

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

這樣反復進行查找，直到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。

當有序線性表為順序存儲時采用二分查找的效率要比順序查找高得多。對于長度為n的有序線性表，在最壞的情況

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

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

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

【答案】A）

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

但允許

相鄰元素值相等）。

考點8.排序技術

1?交換類排序法

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

交換類排序法。

(1)冒泡排序法

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

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

表即排序結(jié)束。

冒泡排序法的基本過程如下。

①從表頭開始往后查找線性表，在查找過程中逐次比較相鄰兩個元素的大小。若在相鄰兩個元素中，前面的元素大

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

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

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

③對剩下的線性表重復上述過程，直到剩下的線性表變空為止，即表示線性表排序完成。

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

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

(2)快速排序法

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

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

快速排序法的基本過程如下。

①從線性表中選取一個元素，設為T,將線性表后面小于T的元素移動到前面，而將大于T的元素移到后面，這樣

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

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

②對分割后的子表再按上述原則進行反復分割，直到所有子表為空為止，此時的線性表就變成有序的了。

2.插入類排序法

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

(1)簡單插入排序法

簡單插入排序是把n個待排序的元素看成一個有序表和一個無序表，開始時，有序表只包含一個元素，而無序表則

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

表。插入元素時，插入位置及其后的記錄依次向后移動。最后有序表的長度為n,而無序表為空，此時排序完成。

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

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

(2)希爾排序法

希爾排序法的基本思路為：將整個無序序列分割成若干個小的子序列并分別進行插入排序。

分割方法如下：

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

②在排序過程中，逐次減少這個增量，直到h減到1時進行一次插入排序，排序即可完成。

希爾排序的效率與所選取的增量序列有關。

3.選擇類排序法

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

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

(1)簡單選擇排序法

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

再從剩下的n—1個元素中選出最小的元素與第二個元素交換。重復這樣的操作直到所有的元素有序為止。

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

(2)堆排序法

堆排序的方法如下：

①將一個無序序列建成堆；

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

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

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

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

A）冒泡排序為n/2B）冒泡排序為n

C）快速排序為nD）快速排序為n（n-1）/2

【答案】D）

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

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

2。

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

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

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

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

1.2程序設計基礎

考點9.程序設計方法與風格

1.程序設計方法

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

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

2.程序設計風格

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

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

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

【例1】下列敘述中，不屬于良好程序設計風格要求的是（）。

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

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

【答案】A）

【解析】著名的“清晰第一，效率第二”的論點已經(jīng)成為主導的程序設計風格，所以選項A是錯誤的，其余選項都

是良好程序設計風格的要求。

［例2］下列選項中不符合良好程序設計風格的是（）o

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

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

【答案】D）

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

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

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

考點10.結(jié)構(gòu)化程序設計

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

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

白頂向卜,：在進行程序設計時，應先考慮總體，后考慮細品先考慮全周目標，后考慮具體問題。

逐步求精：將復雜問題細化，細分為逐個的小問題各依次求解.

模塊化：把程序要解決的總II標分解為若干個目標.再進一步分解為

具體的小目標，每個小目標稱為一個模塊。

限制使用g。t。語句。

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

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

3.結(jié)構(gòu)化程序設計的原則和方法的應用

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

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

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

進行組合嵌套來實現(xiàn)；對語言中所沒有的控制結(jié)構(gòu)，應該采用前后一致的方法來模擬；嚴格控制g。t。語句的使

用。

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

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

【答案】D）

【解析】自20世紀70年代以來，已提出了許多軟件設計方法，主要包括：①逐步求精。對復雜的問題，應設計

一些子目標作過渡，逐步細化。②自頂向下。在進行程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，

后考慮局部目標。一開始不要過多追求細節(jié)，先從最上層總目標開始設計，逐步使問題具體化。③模塊化。一個復

雜問題，肯定是山若干個相對簡單的問題構(gòu)成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具

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

考點11面向?qū)ο蟮牟樵冊O計

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

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

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

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

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

與人類習慣的思維方法一致；

穩(wěn)定性好：

可重用性好;

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

可維護性好。

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

（1）對象

對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢ο罂梢杂脕肀硎究陀^世界中的任何實體，它既可以是具體的物理實體的抽

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

（2）類

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

（3）實例

一個具體對象是其對應類的一個實例。

（4）消息

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

和控制流。

（5）繼承

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

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

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

（6）多態(tài)性

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

小提示

當使用“對象”這個術語時，既可以指一個具體的對象，也可以泛指一般的對象。但是當使用“實例”這個術語時，

則必須是指一個具體的對象。

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

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

【答案】O

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

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

對象是面向?qū)ο笞罨镜母拍?，請問對象有哪些特點？

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

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

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

1.3軟件工程基礎

考點12軟件工程基本概念

1,軟件定義與軟件特點

(1)軟件的定義

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

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

等有關的文檔。

(2)軟件的特點

軟件主要包括以下幾個特點：

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

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

軟件在運行、使用期間，不存在磨損、名化問題;

軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移植的問題：

軟件復雜性高，成本昂貴：

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

2.軟件危機與軟件工程

(1)軟件危機

軟件危機泛指在計算機軟件的開發(fā)和維護中所遇到的一系列嚴重問題。具體地說，在軟件開發(fā)和維護過程中，軟件

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

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

軟件的開發(fā)成木和進度無法控制；

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

軟件不可維護或維護程度『常低；

軟件的成本不斷提高：

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

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

(2)軟件工程

軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程包括兩

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

件產(chǎn)品看做是一個工程產(chǎn)品來處理。

3.軟件工程過程與軟件生命周期

(1)軟件工程過程

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

(2)軟件生命周期

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

軟件開發(fā)及軟件運行維護等3個階段。其中軟件生命周期的主要活動階段包括可行性研究與計劃制定、需求分析、

軟件設計、軟件實現(xiàn)、軟件測試和運行維護等。

4.軟件工程的目標與原則

(1)軟件工程的目標

軟件工程需達到的目標是：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重

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

（2）軟件工程的原則

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

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

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

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

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

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

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

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

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

生命周期的各個階段和各項任務的完成。

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

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

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

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

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

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

【答案】D）

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

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

顯的制作過程；③軟件在運行、使用期間，不存在磨損、老化問題；④軟件的開發(fā)、運行對計算機系統(tǒng)具有不同程

度的依賴性，這導致了軟件移植的問題；⑤軟件復雜性高，成本昂貴；⑥軟件開發(fā)涉及諸多的社會因素。

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

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

（1）需求分析

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

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

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

（2）需求分析方法

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

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

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

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

結(jié)構(gòu)化分析方法的實質(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ù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程。

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

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

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

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

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

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

據(jù)項、數(shù)據(jù)存儲和加工。

小提示：

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

僅僅是所處的狀態(tài)不同。數(shù)據(jù)存儲是處于靜止狀態(tài)的數(shù)據(jù)，數(shù)據(jù)流則是處于運動中的數(shù)據(jù)。

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

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

軟件需求規(guī)格說明書的標準主要有：正確性、無歧義性、完整性、可驗證性、-致性、可理解性、可修改性和可追

蹤性。

考點14結(jié)構(gòu)化設計方法

1,軟件設計的基本概念及方法

(1)軟件設計的基礎

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

括的方式確定目標系統(tǒng)如何完成預定的任務，即軟件設計是確定系統(tǒng)的物理模型。

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

軟件設計遵循軟件工程的基本目標和原則，建立了適用于在軟件設計中應該遵循的基本原理和與軟件設計有關的概

念，主要包括抽象、模塊化、信息隱藏以及模塊的獨立性。下面主要介紹模塊獨立性的一些度量標準。模塊的獨立

程度是評價設計好壞的重要度量標準。衡量軟件的模塊獨立性的定性度量標準是使用耦合性和內(nèi)聚性。耦合性是模

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

件設計，應盡量做到高內(nèi)聚、低耦合。

(3)結(jié)構(gòu)化設計方法

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

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

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

小提示：

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

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

2.概要設計

(1)概要設計的任務

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

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

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

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

了一條信息流。

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

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

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

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

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

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

(3)結(jié)構(gòu)化設計的準則

大量的實踐表明，以下的設計準則可以借鑒為設計的指導和對軟件結(jié)構(gòu)圖進行優(yōu)化的條件：

提高模塊獨立性：

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

深度、寬度、扇入和扇出都應適當；

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

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

設計單入口、單出口的模塊；

模塊功能應該可以預測。

小提示：

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

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

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

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

3.詳細設計

(1)詳細設計的任務

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

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

(2)詳細設計的工具

常見的過程設計工具有：

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

表格I：具：判定表。

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

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

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

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

【答案】A)

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

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

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

考點15軟件測試

1,軟件測試的目的及準則

(1)軟件測試的目的

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

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

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

(2)軟件測試的準則

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

運用軟件測試的一些基本準側(cè)：

所有測試都應追溯到用戶需求：

嚴格執(zhí)行測試計劃，排除測試的隨意性；

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

程序員應避免檢杳自己的程序；

窮舉測試不可能；

妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告，為維護提供方便。

2.軟件測試技術和方法綜述

軟件測試的方法是多種多樣的，對于軟件測試方法和技術，可以從不同的角度分類。

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

試。

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

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

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

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

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

類：黑盒測試和白盒測試。

(2)白盒測試方法與測試用例設計

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

預定的要求正確地工作。

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

(3)黑盒測試方法與測試用例設計

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

格說明的要求。

黑盒測試的主要診斷方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖法等，主要用于軟件確認測試。

3.軟件測試的實施

軟件測試的實施過程主要有4個步驟：單元測試、集成測試、確認測試(驗收測試)和系統(tǒng)測試。

(1)單元測試

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

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

(2)集成測試

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

(3)確認測試

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

為主進行。

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

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

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

下列敘述中正確的是。

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

C)軟件維護只包括對程序代碼的維護D)以上3種說法都不對

【答案】D)

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

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

調(diào)試主要在開發(fā)階段。為了實現(xiàn)更好的測試效果，應該由獨立的第三方來構(gòu)造測試。軟件的運行和維護是指將已交

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

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

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

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

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

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

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

對程序進行修改，排除這個錯誤。

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

①錯誤定位；

②修改設計和代碼，以排除錯誤；

③進行回歸測試，防止引入新的錯誤。

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

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

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

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

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

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

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

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

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

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

【答案】B)

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

軟件設計的重要性和地位主要有哪些？

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

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

策，最終影響軟件實現(xiàn)的成?。辉O計是軟件工程和軟件維護的基礎。

1.4數(shù)據(jù)庫設計基礎

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

小提示

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

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

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

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

一般認為，未來的數(shù)據(jù)庫系統(tǒng)應支持數(shù)據(jù)管理、對象管理和知識管理，應該具有面向?qū)ο蟮幕咎卣?。在關于數(shù)據(jù)

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

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

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

（2）知識庫系統(tǒng)

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

（3）關系數(shù)據(jù)庫系統(tǒng)的擴充

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

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

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

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

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

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

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

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

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

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

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

小提示

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

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

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

B）數(shù)據(jù)庫技術的根本目標是要解決數(shù)據(jù)的共享問題

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

D）以上3種說法都不對

【答案】B）

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

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

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

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

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

【答案】B）

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

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

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

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

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

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

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

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

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

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

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

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

2.E—R模型

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

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

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

屬性：描述實體的特性，川橢圓形表示，并用無向邊將其。相應的實體連接起來，

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

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

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

3.層次模型

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

多的關系。

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

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

4.網(wǎng)狀模型

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

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

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

5.關系模型

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

關系模型采用二維表來表示，簡稱表。二維表由表框架及表的元組組成。表框架是由n個命名的屬性組成，n稱為

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

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