2023計算機二級公共基礎知識

第一章數(shù)據(jù)結構與算法

具體重點學習學問點：

1.算法的概念、算法時間困難度及空間困難度的概念

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

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

4.樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷

5.二分查找法

6.冒泡排序法

考點1算法的基本概念

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

2.算法的基本要素；

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

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

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

傳輸。

(2)算法的限制結構；算法中各操作之間的執(zhí)行依次稱為算法的限制結構。

描述算法的工具通常有傳統(tǒng)流程圖、N6結構化流程圖、算法描述語言等。一個算法一般

都可以用依次、選擇、循環(huán)3種基本限制結構組合而成，

考點2算法困難度

1.算法的時間困難度

算法的時間困難度是指執(zhí)行算法所須要的計算工作量。認為一個特定算法”運行工作量”的

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

算法的工作量=f(n)

2,算法的空間困難度

算法的空間困難度是指執(zhí)行這個算法所須要的內存空間。

一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以

及算法執(zhí)行過程中所須要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及

某種數(shù)據(jù)結構所須要的附加存儲空間。假如額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算

法是原地工作的。在很多實際問題中，為了削減算法所占的存儲空間，通常采納壓縮存儲技術,

以便盡量削減不必要的額外空間。

考點3數(shù)據(jù)結構的定義

數(shù)據(jù)結構作為計算機的一門學科，主要探討和探討以下三個方面：

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

（2）在對數(shù)據(jù)元素進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構；

（3）對各種數(shù)據(jù)結構進行的運算。

數(shù)據(jù)；是對客觀事物的符號表示，在計算機科學中是指全部能輸入到計算機中并被計算機

程序處理的符號的總稱。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

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

數(shù)據(jù)的邏輯結構是對數(shù)據(jù)元素之間的邏輯關系的描述，它可以用一個數(shù)據(jù)元素的集合和定

義在此集合中的若干關系來表示。數(shù)據(jù)的邏輯結構有兩個要素；一是數(shù)據(jù)元素的集合，通常記

為D：二是D上的關系，它反映了數(shù)據(jù)元素之間的前后件關系，通常記為R。一個數(shù)據(jù)結構可以

表示成

B=（D,R）

其中B表示數(shù)據(jù)結構。為了反映D中各數(shù)據(jù)元素之間的前后件關系，一股用二元組來表示。

數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結構（也稱數(shù)據(jù)的物理結

構）。

由于數(shù)據(jù)元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放

在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關系（即前后件關系），在數(shù)據(jù)的存儲結構中，不

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

考點4線性結構與非線性結構

依據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的困難程度，一般將數(shù)據(jù)結構分為兩大類型：

線性結構與非線性結構。假如一個非空的數(shù)據(jù)結構滿意下列兩個條件：

（1）有且只有一個根結點；

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

則稱該數(shù)據(jù)結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一

個結點后還應是線性結構。假如一個數(shù)據(jù)結構不是線性結構，則稱之為非線性結構6

考點5棧及其基本運算

1.棧的基本概念

棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為枝頂，另一端

為棧底。當表中沒有元素時稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的

元素；棧底元素總是最先被插入的元素，從而也是最終才能被刪除的元素。棧是依據(jù)“先進后出

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

2.棧的依次存儲及其運算

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

在棧的依次存儲空間S（1：m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0

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

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

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

加1),然后將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最終一個位

置時，說明?？臻g已滿，不行能再進行入棧操作。這種狀況稱為?！鄙弦?錯誤。

(2)退棧運算；退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素(棧頂指

針指向的元素)賦給一個指定的變量，然后將棧頂指針減?(即top減1)。當枝頂指針為。時，

說明棧空，不行進行退棧操作。這種狀況稱為棧的“下溢”錯誤。

(3)讀找頂元素：讀枝頂元素是指將棧頂元素賦給一個指定的變量。這個運算不刪除板頂

元素，只是將它賦給一個變量，因此棧頂指針不會變更。當棧頂指針為0時，說明?？?，讀不到

棧頂元素。

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

在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)

域，另一部分用于存放指針，稱為指針域。其中指針用于指向該結點的前一個或后一個結點(即

前件或后件)。

鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。

(1)線性鏈表

線性表的鏈式存儲結構稱為線性鏈表。

在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前

件結點；另一個稱為右指針，用以有向其后件結點。這樣的表稱為雙向鏈表。

(2)帶鏈的棧

棧也是線性表，也可以采納鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中全部

空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

考點7樹與二叉樹及其基本性質

誤區(qū)警示：

滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應當留意二者的區(qū)分。

1、樹的基本概念

樹(tree)是一種簡潔的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點,

沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個后件，它們稱為該結點的

子結點,沒有后件的結點稱為葉子結點。

在樹結構中，一個結點所擁有的后件個數(shù)稱為該結點的度。葉子結點的度為0。在樹中，全

部結點中的最大的度稱為樹的度。

2、二叉樹及其基本性質

(1)二叉樹的定義

二叉樹是一種很有用的非線性結構，具有以下兩個特點：

①非空二叉樹只有一個根結點；

②每一個結點最多有兩棵子樹：且分別稱為該結點的左子樹和右子樹。

由以上特點可以看出，在二叉樹中，每一個結點的度最大為2,即全部子樹(左子樹或右子

樹)也均為二叉樹，而樹結構中的每一個結點的度可以是隨意的。另外，二叉樹中的每個結點

考點9依次查找

查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素。從線性表的第一個元素起先，依

次將線性表中的元素與被查找的元素相比較，若相等則表示查找勝利；若線性表中全部的元素

都與被查找元素進行了比較但都不相等，則表示資找失敗。

在下列兩種狀況下也只能采納依次查找：

(1)假如線性表為無序表，則不管是依次存儲結構還是鏈式存儲結構，只能用依次查找。

(2)即使是有序線性表，假如采納鏈式存儲結構，也只能用依次查找。

考點10二分法查找

二分法只適用于依次存儲的，或非遞減排列的有序表，其方法如下；

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

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

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

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

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

二分查找法只適用于依次存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞

減排列(即從小到大，但允許相鄰元素值相等)。

這個過程始終進行到查找勝利或子表長度為。為止6

對于長度為n的有序線性表，在最壞狀況下，二分查找只須要比較log2n次。

考點11交換類排序法

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

(1)冒泡排序法

首先，從表頭起先往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后

面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最終最大者到了線性表

的最終。

然后，從后到前掃描剩卜?的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前

面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最終最小者到了線性表

的最前面。

對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。

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

(2)快速排序法

它的基本思想是；任取待排序序列中的某個元素作為基準(一般取第一個元素)，通過一趟

排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序

碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列接著進行排序，直至

整個序列有序。

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

冒泡排序法的平均執(zhí)行時間是0(乃)，而快速排序法的平均執(zhí)行時間是0(nlog2n)o

例題詳解

一、選擇題

【例1】莫法的時間困難度取決于0（考點2）

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

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

解析：算法的時間困難度不僅與問題的規(guī)模有關，在同一個問題規(guī)模下，而且與輸入數(shù)據(jù)

有關。即與輸入數(shù)據(jù)全部的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關。

答案：D）

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

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

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

解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、推斷棧是否為空或

滿、提取棧頂元素等，對枝的操作都是在棧頂進行的。

答案：D）

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

A）可隨機訪問隨意一個結點B）插入和刪除穴須要移動任何元素

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

解析：依次表可以隨機訪問隨意一個結點，而鏈表必需從第一個數(shù)據(jù)結點動身，逐一查找

每個結點。所以答案為A）。

答案；A）

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

歷序列是,（考點8）

A）ACBEDB）DEABC

C）DECABD）EDBAC

解析：后序遍歷的依次是"左子樹一石子樹一根結點”；中序遍歷依次是"左子樹一根結點一

右子樹"：前序遍歷依次是”根結點一左子樹一右子樹"。依據(jù)各種遍歷算法，不難得出前序遍歷

序列是EDBAC。所以答案為D）。

答案：D）

【例6】設有一個己按各元素的值排好序的線性表（長度大于2）,對給定的值k,分別用依

次查找法和二分查找法查找一個與k相等的元素，比較的次數(shù)分別是s和b,在查找不勝利的狀況

下，s和b的關系是。（考點9）

A）s=bB）s>bC）s<bD）s^b

解析：對于依次查找，查找不勝利時和給定關鍵字比較的次數(shù)為n+1。二分查找查找不勝

利的關鍵字比較次數(shù)為[logzn]+1o當nN2時，明顯n+1>[logsn]+1。

答案：B）

【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考

慮這兩個子表，下列結論肯定正確的是o（考點11）

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

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

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

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

解析：快速排序基本思想是：狂取待排序表中的某個元素作為基準（一般取第一個元素），

通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小于或等于基準元素的

排序碼，右子表的排序碼則大于基準元索的排序碼，然后分別對兩個子表接著進行排序，直至

整個表有序。

答窠：B）

二、填空題

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

解析：計算機解題的過程事實上是在實施某種算法，這種算法稱為計算機算法。

答案；算法

【例2】一個空的數(shù)據(jù)結構是按線性結構處理的，則屬于。（考點4）

解析：一個空的數(shù)據(jù)結構是線性結構或是非線性結構，要依據(jù)具體狀況而定。假如對數(shù)據(jù)

結構的運算是按線性結構來處理的，則屬于線性結構，否則屬于非線性結構。

答案：線性結構

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

則T中葉子結點的個數(shù)為。（考點7）

解析；依據(jù)樹的性質；樹的結點數(shù)等于全部結點的度與對應的結點個數(shù)乘積之和加L

因此樹的結點數(shù)為1x4+2x2+3x1+4x1+1=16。葉子結點數(shù)目等于樹結點總數(shù)

減去度不為0的結點數(shù)之和，即16—（4+2+1+1）=80

答案:8

【例4】二分法查找的存儲結構僅限于且是有序的。（考點10）

解析；二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制；

要求表必需用依次存儲結構，且表中元素必需按關鍵字有序（升序或降序均可）。

答案：依次存儲結構

其次章程序設計基礎

具體重點學習學問點：

1.結構化程序設計方法的四個原則

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

考點1結構化程序設計的原則

結構化程序設計方法的主要原則為：自頂向下、逐步求精、模塊化和限制運用goto語句o

考點2面對對象方法的基本概念

面對對象方法涵蓋對象及對象屬性與方法、類、繼承、多態(tài)性幾個基本要素。

(1)對象

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

屬性即對象所包含的信息，它在設計對象時確定，一般只能通過執(zhí)行對象的操作來變更。

屬性值應當指的是純粹的數(shù)據(jù)值，而不能指對象。

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

對象具有如下特征：標識惟一性、分類性、多態(tài)性、封裝性、模塊獨立性。

(2)類和實例

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

而一個對象則是其對應類的一個實例a

類是關于對象性質的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。

(3)消息

消息是實例之間傳遞的信息，它懇求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了

數(shù)據(jù)流和限制流。

一個消息由三部分組成：接收哨息的對象的名稱、消息標識符(消息名)和零個或多個參

數(shù)。

(4)繼承

廣義地說，繼承是指能夠干脆獲得已有的性質和特征，而不必重復定義它們。

繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類，即類等級為樹形結

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

(5)多態(tài)性

對象依據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接收時可導致完全不同的行

動，該現(xiàn)象稱為多態(tài)性。

例題詳解

一、選擇題

【例2】結構化程序設計方法的主要原則有下列4項，不正確的是o(考點1)

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

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

解析；結構化程序設計方法的主要原則為；

(1)自頂向下：即先考慮總體，后考慮細微環(huán)節(jié)：先考慮全局目標，后考慮局部目標。

(2)逐步求精：對困難問題，應設計一些子目標作過渡，逐步細化。

(3)模塊化：把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每

個小目標稱為一個模塊。

(4)限制運用got。語句。

答案:A)

【例3】面對對象的開發(fā)方法中，類與對象的關系是o（考點2）

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

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

解析：現(xiàn)實世界中的很多事物都具有相像的性質，把具有相像的屬性和操作的對象歸為類,

也就是說類是具有共同屬性、共同方法的對象的集合，是對對象的抽象。它描述了該對象類型

的全部對象的性質，而一個對象則是對應類的一個具體實例e所以本題正確答案為A）項,

答案：A）

二、填空題

【例1】在面對對象方法中，運用已經存在的類定義作為基礎建立新的類定義，這樣的技術

叫做。（考點2）

解析：繼承是面對對象方法的一個主要特征。繼承是運用已有的類定義作為基礎建立新類的

定義技術。己有的類可當作基類來引用，則新類相應地可當作派生類來弓I用。

答案：繼承

【例3】對象依據(jù)所接收的消息而做出動作，同樣的消息被不同的對象所接收時可能導致完

全不同的行為，這種現(xiàn)象稱為。（考點2）

解析：對象依據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接收時可導致完全不

同的行為，該現(xiàn)象稱為多態(tài)性。

答案：多態(tài)性

第三章軟件工程基礎

具體重點學習學問點：

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

2?概要設計與具體設計的概念、模塊獨立性及其度量的標準、具體設計常用的工具

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

4.軟件調試的任務

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

軟件指的是計算機系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)和相關文檔的完整

集合。程序是軟件開發(fā)人員依據(jù)用戶需求開發(fā)的、用程序設計語言描述的、適合計算機執(zhí)行的

指令序列6數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結構6文檔是與程序的開發(fā)、維護和運用有關

的圖文資料?？梢?，軟件由兩部分組成：

（1）機器可執(zhí)行的程序和數(shù)據(jù)；

（2）機器不行執(zhí)行的，與軟件開發(fā)、運行、維護、運用等有關的文檔。

軟件的特點：

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

（2）沒有明顯的制作過程，可進行大量的復制；

（3）運用期間不存在磨損、老化問題：

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

（5）軟件困難性高，成本昂貴；

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

依據(jù)應用目標的不同，軟件可分應用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。

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

軟件產品從提出、實現(xiàn)、運用維護到停止運用退役的過程稱為軟件生命周期。一般包括可

行性分析探討與需求分析、交付運用以及維護等活動，如圖3—1所示。

定義階段

開發(fā)階段

卸階段

圖3-1軟件生命周期

還可以將軟件生命周期分為如上圖所示的軟件定義、軟件開發(fā)和軟件運行維護3個階段。

生命周期的主要活動階段是，可行性探討與安排制定、需求分析、軟件設計、軟件實施、

軟件測試及運行與維護。

考點3軟件設計的基本概念

誤區(qū)警示：

在程序結構中，各模塊的內聚性越強，則耦合性越弱。軟件設計應盡量做到高內聚，低耦合,

即減弱模塊之間的耦合性和提高模塊內的內聚性，有利于提高模塊的獨立性。

1.軟件設計的基礎

從技術觀點上看，軟件設計包括軟件結構設計、數(shù)據(jù)設計、接口設計、過程設計。

（1）結構設計定義軟件系統(tǒng)各主要部件之間的關系：

（2）數(shù)據(jù)設計將分析時創(chuàng)建的模型轉化為數(shù)據(jù)結構的定義；

（3）接口設計是描述軟件內部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信：

（4）過程設計則是把系統(tǒng)結構部件轉換為軟件的過程性描述。

從工程管理角度來看，軟件設計分兩步完成：概要設計和具體設計，

（1）概要設計將軟件需求轉化為軟件體系結構、確定系統(tǒng)級接口、全局數(shù)據(jù)結構或數(shù)據(jù)庫

模式；

（2）具體設計確立每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結構，用適當方法表示算法和數(shù)據(jù)結構

的細微環(huán)節(jié)。

2.軟件設計的基本原理

（1）抽象：軟件設計中考慮模塊化解決方案時，可以定出多個抽象級別。抽象的層次從概

要設計到具體設計逐步降低。

（2）模塊化：模塊是指把一個待開發(fā)的軟件分解成若干小的簡潔的部分。模塊化是指解決

一個困難問題時自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。

（3）信息隱藏：信息隱藏是指在一個模塊內包含的信息（過程或數(shù)據(jù)），對于不須要這些

信息的其他模塊來說是不能訪問的.

（4）模塊獨立性；模塊獨立性是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他

模塊的聯(lián)系最少且接口簡潔。模塊的獨立程度是評價設計好壞的重要度量標準。衡量軟件的模

塊獨立性運用耦合性和內聚性兩個定性的度量標準。內聚性是信息隱藏和局部化概念的自然擴

展。一個模塊的內聚性越強則該模塊的模塊獨立性越強。一個模塊與其他模塊的耦合性越強則

該模塊的模塊獨立性越弱。

內聚性是度量一個模塊功能強度的一個相對指標。內聚是從功能角度來衡量模塊的聯(lián)系，

它描述的是模塊內的功能聯(lián)系。內聚有如下種類，它們之間的內聚度由弱到強排列：偶然內聚、

邏輯內聚、時間內聚、過程內聚、通信內聚、依次內聚、功能內聚。

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

調用方式以及哪些信息通過接口。耦合可以分為下列幾種，它們之間的耦合度由高到低排列：

內容耦合、公共耦合、外部耦合、限制耦合、標記耦合、數(shù)據(jù)耦合、非干脆耦合。

在程序結構中，各模塊的內聚性越強，則耦合性越弱。一般較優(yōu)秀的軟件設計，應盡量做

到高內聚，低耦合，即減弱模塊之間的耦合性和提高模塊內的內聚性，有利于提高模塊的獨立

性。

考點4具體設計

具體設計的任務是為軟件結構圖中的每個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結構，用某種選定

的表達表示工具算法和數(shù)據(jù)結構的細微環(huán)節(jié)。

具體過程設計的常用工具有：

（1）圖形工具:程序流程圖,N-S,PAD,HIPO-

（2）表格工具：判定表。

（3）語言工具；PDL（偽碼）.

程序流程圖的5種限制結構：依次型、選擇駕、先推斷重復型、后推斷重復型和多分支選擇

型。

方框圖中僅含5種基本的限制結構，即依次型、選擇型、多分支選擇型、WHILE重復型和

UNTIL重復型。

PAD圖表示5種基本限制結構，即依次型、選擇型、多分支選擇型、WHILE重復型和UNTIL

重復型。

過程設計語言（PDL）也稱為結構化的語言和偽碼，它是一種混合語言，采納英語的詞匯

和結構化程序設計語言，類似編程語言。

PDL可以由編程語言轉換得到，也可以是特地為過程描述而設計的。

考點5軟件測試的目的

軟件測試是在軟件投入運行前時軟件需求、設計、編碼的最終審核。其工作量、成本占總

工作量、總成本的40%以上，而且具有較高的組織管理和技術難度。

（1）軟件測試是為了發(fā)覺錯誤而執(zhí)行程序的過程；

（2）一個好的測試用例是能夠發(fā)覺至今尚未發(fā)覺的錯誤的用例；

（3）一個勝利的測試是發(fā)覺了至今尚未發(fā)覺的錯誤的測試。

考點6軟件測試的實施

軟件測試過程分4個步驟，即單元測試、集成測試、驗收測試和系統(tǒng)測試。

單元測試是對軟件設計的最小單位-模塊（程序單元）進行正確性檢驗測試。單元測試的

技術可以采納靜態(tài)分析和動態(tài)測試.

集成測試是測試和組裝軟件的過程，主要目的是發(fā)覺與接口有關的錯誤，主要依據(jù)是概要

設計說明書。集成測試所設計的內容包括；軟件單元的接口測試、全局數(shù)據(jù)結構測試、邊界條

件和非法輸入的測試等。集成測試時將模塊組裝成程序，通常采納兩種方式：非增量方式組裝

和增量方式組裝，

確認測試的任務是驗證軟件的功能和性能，以及其他特性是否滿意了需求規(guī)格說明中確定

的各種需求，包括軟件配置是否完全、正確。確認測試的實施首先運用黑盒測試方法，對軟件

進行有效性測試，即驗證被測軟件是否滿意需求規(guī)格說明確認的標準。

系統(tǒng)測試是通過測試確認軟件,作為整個基于計算機系統(tǒng)的一個元素，與計算機硬件、外

設、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實際運行（運用）環(huán)境下對計算機

系統(tǒng)進行一系列的集成測試和確認測試。

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

試、平安性測試等。

考點7軟件調試的基本概念

誤區(qū)警示：

程序經調試改錯后還應進行再測試，因為經調試后有可能產生新的錯誤，而且測試是貫穿生命

周期的整個過程。

在對程序進行了勝利的測試之后將進入程序調試（通常稱Debug,即排錯打程序的調試任

務是診斷和改正程序中的錯誤。調試主要在開發(fā)階段進行。

程序調試活動由兩部分組成，一是依據(jù)錯誤的跡象確定程序中錯誤的準確性質、緣由和位

置：二是對程序進行修改，解除這個錯誤。程序調試的基本步驟：

（1）錯誤定位。從錯誤的外部表現(xiàn)形式入手，探討有關部分的程序，確定程序中出錯位置,

找出錯誤的內在緣由：

（2）修改設計和代碼，以解除錯誤；

（3）進行回來測試，防止引進新的錯誤。

調試原則可以從以下兩個方面考慮：

（1）確定錯誤的性質和位置時的留意事項

分析思索與錯誤征兆有關的信息：避開死胡同；只把調試工具當作協(xié)助手段來運用；避開

用摸索法，最多只能把它當作最終手段。

（2）修改錯誤原則

在出現(xiàn)錯誤的地方，很可能有別的錯誤：修改錯誤的一個常見失誤是只修改了這個錯誤的征兆

或這個錯誤的表現(xiàn)，而沒有修改錯誤本身；留意修正一個錯誤的同時有可能會引入新的錯誤；

修改錯誤的過程將迫使人們短暫回到程序設計階段；修改源代碼程序，不要變更目標代碼。

?疑難解答；軟件測試與軟件調試有何不同？

軟件測試是盡可能多地發(fā)覺軟件中的錯誤，而軟件調試的任務是診斷和改正程序中的錯誤。

軟件測試貫穿整個軟件生命周期，調試主要在開發(fā)階段。

例題詳解

一、選擇題

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

A）軟件是一種物理實體

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

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

D）軟件的生產有一個明顯的制作過程

解析：軟件在運行期間不會因為介質的磨損而老化，只可能因為適應硬件環(huán)境以及需求變

更進行修改而引入錯誤，導致失效率上升從而軟件退化，所以本題正確答案為B）。

答案；B）

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

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

C）軟件確認D）軟件演進

解析：B）、C）、D）項都是軟件工程過程的基本活動，還有一個是軟件規(guī)格說明。

答案；A）

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

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

C）發(fā)覺程序中的錯誤D）改正程序中的錯誤

解析：關于測試目的的基本學問，IEEE的定義是：運用人工或自動手段來運行或測定某個

系統(tǒng)的過程，其目的在于檢驗它是否滿意規(guī)定的需求，或是弄清預期結果與實際結果之間的差

別，所以正確答案是C）。

答案：C）

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

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

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

解析；檢查對測試實施各階段的了解，集成測試時要進行接口測試、全局數(shù)據(jù)結構測試、

邊界條件測試和非法輸入的測試等，所以正確答案是B）。

答案：B）

【例6】程序調試的主要任務是6（考點7）

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

C）發(fā)覺錯誤D）以上都不是

解析：程序的調試任務是診斷和改正程序中的錯誤。調試主要在開發(fā)階段進行。

答案：B）

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

A）分析錯誤緣由B）錯誤定位

0）修改設計代碼以解除錯誤D）回來測試，防止引入新錯誤

解析，程序調試的基本步驟：

（1）錯誤定位。從錯誤的外部表現(xiàn)形式入手，探討有關部分的程序，確定程序中出錯位置,

找出錯誤的內在緣由。

（2）修改設計和代碼，以解除錯誤。

（3）進行回來測試，防止引道新的錯誤。

答案：A）

【例8】在修改錯誤時應遵循的原則有°（考點7）

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

B）修改錯誤的是源代碼而不是目標代碼

C）遵循在程序設計過程中的各種方法和原則

D）以上3個都是

解析：修改錯誤原則；

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

（2）修改錯誤的一個常見失誤是只修改了這個錯誤的征兆或這個錯謾的表現(xiàn)，而沒有修改

錯誤本身：

（3）留意修正一個錯誤的同時有可能會引入新的錯誤：

（4）修改錯誤的過程將迫使人們短暫回到程序設計階段；

（5）修改源代碼程序，不要變更目標代碼。

答案:D）

二、填空題

【例1】軟件設計是軟件工程的重要階段，是一個把軟件需求轉換為的過程。（考

點3）

解析：軟件設計是軟件工程的重要階段，是一個把軟件需求轉換為軟件表示的過程。其基

本目標是用比較抽象概括的方式確定口標系統(tǒng)如何完成預定的任務，即軟件設計是確定系統(tǒng)的

物理模型。

答案：軟件表示

【例2】是指把一個待開發(fā)的軟件分解成若干小的簡潔的部分。（考點3）

解析：模塊化是指把一個待開發(fā)的軟件分解成若干小的簡潔的部分0如高級語言中的過程、

函數(shù)、子程序等。每個模塊可以完成一個特定的子功能，各個模塊可以按肯定的方法組裝起來

成為一個整體，從而實現(xiàn)整個系統(tǒng)的功能,

答案：模塊化

【例3】數(shù)據(jù)流圖采納4種符號表示、數(shù)據(jù)源點和終點、數(shù)據(jù)流向和數(shù)據(jù)加工。（考

點4）

解析；數(shù)據(jù)流圖可以表達軟件系統(tǒng)的數(shù)據(jù)存儲、數(shù)據(jù)源點和終點、數(shù)據(jù)流向和數(shù)據(jù)加工。

其中，用箭頭表示數(shù)據(jù)流向，用圓或者橢圓表示數(shù)據(jù)加工，用雙杠表示數(shù)據(jù)存儲，用方框來表

示數(shù)據(jù)源點和終點。

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

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

具體重點學習學問點；

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個描述內容、E-R模型的概念及其E-R圖表示法、關系操縱、關系模型三類

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

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

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

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

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

數(shù)據(jù)庫是長期儲存在計算機內,有組織的、可共享的大量數(shù)據(jù)的集合，它具有統(tǒng)一的結構

形式并存放于統(tǒng)一的存儲介質內，是多種應用數(shù)據(jù)的集成，并可被各個應用程序所共享。

數(shù)據(jù)庫管理系統(tǒng)（DBMS,DatabaseManagementSystem）是數(shù)據(jù)庫的機構，它是一種

系統(tǒng)軟件，負責數(shù)據(jù)庫巾的數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)維護、限制及愛護和數(shù)據(jù)服務等。數(shù)據(jù)

庫管理系統(tǒng)是數(shù)據(jù)系統(tǒng)的核心，主要有如下功能：數(shù)據(jù)模式定義、數(shù)據(jù)存取的物理構建、數(shù)據(jù)

操縱、數(shù)據(jù)的完整性、平安性定義和檢查、數(shù)據(jù)庫的并發(fā)限制與故障賃原、數(shù)據(jù)的服務。

為完成數(shù)據(jù)庫管理系統(tǒng)的功能.數(shù)據(jù)庫管理系統(tǒng)供應相應的數(shù)據(jù)語言：數(shù)據(jù)定義語言、數(shù)

據(jù)操縱語言、數(shù)據(jù)限制語言。

數(shù)據(jù)庫管理員的主要工作如下：數(shù)據(jù)庫設計、數(shù)據(jù)庫維護、改善系統(tǒng)性能，提高系統(tǒng)效率。

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

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

數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依靠性，即數(shù)據(jù)庫中的數(shù)據(jù)獨立于應用程序而不依靠于

應用程序。

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

(1)物理獨立性；指用戶的應用程序與存儲在磁盤上的數(shù)據(jù)庫中數(shù)據(jù)是相互獨立的。當數(shù)

據(jù)的物理結構(包括存儲結構、存取方式等)變更時，如存儲設備的更換、物理存儲的更換、

存取方式變更等，應用程序都不用變更。

(2)邏輯獨立性：指用戶的應用程序與數(shù)據(jù)庫的邏輯結構是相互獨立的6數(shù)據(jù)的邏輯結構

變更了，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、變更數(shù)據(jù)間聯(lián)系等，用戶程序都可以不變。

數(shù)據(jù)統(tǒng)一管理與限制主要包括以下3個方面；數(shù)據(jù)的完整性檢查、數(shù)據(jù)的平安性愛護和并發(fā)

限制。

考點4數(shù)據(jù)庫系統(tǒng)的內部結構體系

誤區(qū)警示；

一個數(shù)據(jù)庫只有一個概念模式。一個概念模式可以有若干個外模式。三級模式都有幾種名稱，

讀者應當熟記每個模式的另一些名稱。

1.數(shù)據(jù)統(tǒng)系統(tǒng)的3級模式

(1)概念模式，也稱邏輯模式，是對數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結構的描述，是全體用戶

〈應用〉公共數(shù)據(jù)視圖。一個數(shù)據(jù)庫只有一個概念模式。

(2)外模式，外模式也稱子模式，它是數(shù)據(jù)庫用戶能夠望見和運用的局部數(shù)據(jù)的邏輯結構

和特征的描述，它是由概念模式推導而出來的，是數(shù)據(jù)庫用戶的數(shù)據(jù)視圖，是與某一應用有關

的數(shù)據(jù)的邏輯表示。一個概念模式可以有若干個外模式。

(3)內模式，內模式又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結構與物理存取方法。

內模式處于最底層，它反映了數(shù)據(jù)在計算機物理結構中的實際存儲形式，概念模式處于中

間層，它反映了設計者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層，它反映了用戶對數(shù)據(jù)的要

?小提示：內模式處于最底層，它反映了數(shù)據(jù)在計算機物理結構中的實際存儲形式，概

念模式處于中間層，它反映了設計者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層，它反映了用

戶對數(shù)據(jù)的要求。

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

兩級映射保證了數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨立性。

(1)概念模式到內模式的映射。該映射給出了概念模式中數(shù)據(jù)的全局邏輯結構到數(shù)據(jù)的物

理存儲結構間的對應關系；

(2)外模式到概念模式的映射。概念模式是一個全局模式而外模式是用戶的局部模式。一

個概念模式中可以定義多個外模式，而每個外模式是概念模式的一個基本視圖。

考點5數(shù)據(jù)模型的基本概念

數(shù)據(jù)模型用來抽象、表示和處理現(xiàn)實世界中的數(shù)據(jù)和信息。分為兩個階段：把現(xiàn)實世界中

的客觀對象抽象為概念模型；把概念模型轉換為某一DBMS支持的數(shù)據(jù)模型。

數(shù)據(jù)模型所描述的內容有3個部分，它們是數(shù)據(jù)結構、數(shù)據(jù)操作與數(shù)據(jù)約束。

考點6E?R模型

1.E-R模型的基本概念

(1)實體；現(xiàn)實世界中的事物可以抽象成為實體，實體是概念世界中的基本單位，它們是

客觀存在的且又能相互區(qū)分的事物.

(2)屬性：現(xiàn)實世界中事物均有一些特性，這些特性可以用屬性來表示。

(3)碼：唯一標識實體的屬性集稱為碼。

(4)域：屬性的取值范圉稱為該屬性的域。

(5)聯(lián)系：在現(xiàn)實世界中事物間的關聯(lián)稱為聯(lián)系。

兩個實體集間的聯(lián)系事實上是實體集間的函數(shù)關系，這種函數(shù)關系可以有下面幾種：一對

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

2.E?R模型的圖示法

E?R模型用E?R圖來表示。

(1)實體表示法：在E?R圖中用矩形表示實體集，在矩形內寫上該實體集的名字。

(2)屬性表示法：在E?R圖中用橢圓形表示屬性，在橢圓形內寫上該屬性的名稱。

(3)聯(lián)系表示法；在E-R圖中用菱形表示聯(lián)系，菱形內寫上聯(lián)系名。

考點7層次模型

滿意下面兩個條件的基本層次聯(lián)系的集合為層次模型。

(1)有且只有一個結點沒有雙親結點，這個結點稱為根結點；

(2)除根結點以外的其他結點有且僅有一個雙親結點。

考點8關系模型

關系模型采納二維表來表示，二維表一般滿意下面7特性質；

(1)二維表中元組個數(shù)是有限的一元組個數(shù)有限性；

(2)二維表中元組均不相同--元組的唯一性；

(3)二維表中元組的次序可以隨意交換一元組的次序無關性；

(4)二維表中元組的重量是不行分割的基本數(shù)據(jù)項--元組重量的原子性；

(5)二維表中屬性名各不相同--屬性名唯一性；

(6)二維表中屬性與次序無關，可隨意交換?一屬性的次序無關性：

(7)二維表屬性的重量具有與該屬性相同的值域-重量值域的統(tǒng)一性。

在二維表中惟一標識元組的最小屬性值稱為該表的鍵或碼。二維表中可能有若干個健，它

們稱為表的侯選碼或侯選健。從二維表的全部侯選鍵選取一個作為用戶運用的鍵稱為主鍵或主

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

關系操縱：數(shù)據(jù)查詢、數(shù)據(jù)刪除、數(shù)據(jù)插入、數(shù)據(jù)修改。

關系模型允許定義三類數(shù)據(jù)約束，它們是實體完整性約束、參照完整性約束以及用戶定義

的完整性約束。

考點9關系代數(shù)

1.關系模型的基本操作

關系模型的基本操作：插入、刪除、修改和查詢。

其中查詢包含如下運算：

①投影運算。從R中選擇出若干屬性列組成新的關系。

②選擇運算。選擇運算是一個一元運算，關系R通過選擇運算(并由該運算給出所選擇的

邏輯條件)后仍為一個關系。設關系的邏輯條件為F,則R滿意F的選擇N算可寫成：aF(R)

③笛卡爾積運算。設有n元關系R及m元關系S,它們分別有p、q個元組，則關系R與S經笛

卡爾積記為RxS,該關系是一個n+m元關系，元組個數(shù)是pxq,由R與S的有序組組合而成。

2.關系代數(shù)中的擴充運算

(1)交運算；關系R與S經交運算后所得到的關系是由那些既在R內又在S內的有序組所組

成，記為RCIS。

(2)除運算

假如將笛卡爾積運算看作乘運算的話，除運算就是它的逆運算。當關系T二RxS時，則可將

除運算寫成：14^=5或丁用=$

S稱為T除以R的商。除法運算不是基本運算，它可以由基本運算推導而出。

(3)連接與自然連接運算

連接運算又可稱為。運算，這是一種二元運算，通過它可以將兩個關系合并成一個大關系。

設有關系R、S以及比較式i6j,其中i為R中的域，j為S中的域，8含義同前。則可以將R、S在域

i,j上的。連接記為：

R|x|S

在0連接中假如e為就稱此連接為等值連接，否則稱為不等值連接；如。為時稱為小

于連接；如。為少'時稱為大于連接。

自然連接(naturaljoin)是一種特別的等值連接，它滿意下面的條件：

①兩關系間有公共域；

②通過公共域的等值進行連接。

設有關系R、S,R有域Ai,A2,An,S有域Bi,B2........Bm,并且，Aii,Ai2,

Aij,與&,B2,…，Bj分別為相同域，此時它們自然連接可記為；

R|x|S

自然連接的含義可用下式表示：

R|x|S=HA1.A2........An,Bj>1,……Bm(QAi1=B1AAi2?B2A...AAij=,Bj(RxS))

考點10數(shù)據(jù)庫設計概述

數(shù)據(jù)庫設計中有兩種方法，面對數(shù)據(jù)的方法和面對過程的方法：

面對數(shù)據(jù)的方法是以信息需求為主，兼顧處理需求；面對過程的方法是以處理需求為主，

兼顧信息需求。由于數(shù)據(jù)在系統(tǒng)中穩(wěn)定性高，數(shù)據(jù)已成為系統(tǒng)的核心，因此面對數(shù)據(jù)的設計方

法己成為主流。

數(shù)據(jù)庫設計目前一般采納生命周期法，即將整個數(shù)據(jù)庫應用系統(tǒng)的開發(fā)分解成目標獨立的

若干階段。它們是：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、

測試階段、運行階段和進一步修改階段。在數(shù)據(jù)庫設計中采納前4個階段。

例題詳解

一、選擇題

【例1】對于數(shù)據(jù)庫系統(tǒng)，負責定義數(shù)據(jù)庫內容，確定存儲結構和存取策略及平安授權等工

作的是°（考點1）

A）應用程序員B）用戶

O數(shù)據(jù)庫管理員D）數(shù)據(jù)庫管理系統(tǒng)的軟件設計員

解析：數(shù)據(jù)庫管理員（簡稱DBA）,具有如.卜的職能：設計、定義數(shù)據(jù)庫系統(tǒng)：幫助用戶運

用數(shù)據(jù)庫系統(tǒng)；監(jiān)督與限制數(shù)據(jù)庫系統(tǒng)的運用和運行；改進和重組數(shù)據(jù)庫系統(tǒng)；轉儲和復原數(shù)

據(jù)庫；重構數(shù)據(jù)庫。所以，定義數(shù)據(jù)庫內容，確定存儲結構和存取策略及平安授權等是數(shù)據(jù)庫

管理員（DBA）的職責。

答