計算機二級公共基礎(chǔ)知識

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

1.算法

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

算法不等于程序，也不等于計算方法,程序的編制不可能優(yōu)于算法的設(shè)計。

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

的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：

(1)可行性；

(2)確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，

不允許有多義性；

(3)有窮性，算法必須能在有限的時間內(nèi)做完,即能在執(zhí)行有限個步驟后終止,

包括合理的執(zhí)行時間的含義；

(4)擁有足夠的情報。

算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制構(gòu)造。

算法的三種基本控制構(gòu)造：順序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造。

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

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

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

案例0.算法的有窮性是指(D)

A.算法只能被有限的用戶使用

B.算法程序的長度是有限的

C.算法程序所處理的數(shù)據(jù)量是有限的

D.算法程序的運行時間是有限的

案例1.以下表達中正確的選項是(BG)

A.一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小

B.算法的時間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系

C.一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大

D.算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)

E.算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲構(gòu)造無關(guān)

F.數(shù)據(jù)的邏輯構(gòu)造與存儲構(gòu)造是一一對應(yīng)的

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

2.棧及其基本運算

棧是限定在一端進展插入與刪除運算的線性表。

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

棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。

即棧是按照“先進后出〃或“后進先出〃的原則組織數(shù)據(jù)的。

棧的基本運算：

1)插入元素稱為入棧運算；2)刪除元素稱為退棧運算；

案例2.一個棧的初始狀態(tài)為空。先將元素1,2,3,A,B,C依次入棧，然后再

依次出棧，則元素出棧的順序是(C,B,A,3,2,1)

3.隊列及其基本運算

隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進展刪除的線性

表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊

頭）。

隊列是“先進先出〃或“后進后出〃的線性表。

隊列運算包括：

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

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

案例3.以下與隊列構(gòu)造有關(guān)聯(lián)的是（A）

A.先到先服務(wù)的作業(yè)調(diào)度B.函數(shù)的遞歸調(diào)用

C.數(shù)組元素的引用D.多重循環(huán)的執(zhí)行

4.循環(huán)隊列及其運算：

所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，

形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear

指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此,

從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的

元素均為隊列中的元素。

循環(huán)隊歹！J中元素的個數(shù)=rear-front。

案例4.以下表達中正確的選項是（B）

A.循環(huán)隊列有隊頭和隊尾兩個指針，因此循環(huán)隊列是非線性構(gòu)造

B.循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定

C.在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況

D.在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況

案例5.設(shè)循環(huán)隊列的存儲空間為Q（1:35）,初始狀態(tài)為front=rear=35.

現(xiàn)經(jīng)過一系列入隊與退隊運算后，front=15,rear=15,則循環(huán)隊列中的

元素個數(shù)為（A）

A.0或35B.15C.20D.16

解析:循環(huán)隊列中的元素個數(shù)的計算方法是：隊尾-隊頭

1.如果大于0,rear-front即為元素的個數(shù)。

2.如果小于0,rear-fron七+空間容量即為元素個數(shù)。

3.如果等于0,元素個數(shù)為0或空間容量。

5.二叉樹及其基本性質(zhì)二叉樹是一種非線性構(gòu)造，它具有以下兩個特點：

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

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

根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子

樹）或2（有2棵子樹）。

二叉樹考點1:

一在任意二棵三叉樹中，度數(shù)為0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多

一個。葉子數(shù)（度為0）=度為2結(jié)點數(shù)+1

二叉樹考點2:二叉樹的深度即二叉樹的層次數(shù)

二叉樹考點3:

總結(jié)點數(shù)=度為2的結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為0的結(jié)點數(shù)(葉子)

案例6.某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深

度為(假設(shè)根結(jié)點在第1層)o(7)

案例7.一棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為1的結(jié)

點數(shù)為______________o(16)_

解析：葉子結(jié)點數(shù)=度為2皈結(jié)點數(shù)+1

5=+1

求得度為2的結(jié)點數(shù)為4

總結(jié)點數(shù)=度為2的結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為0的結(jié)點數(shù)(葉子)

25=4++5

求得度為1的結(jié)點數(shù)為16

二叉樹考點4:二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。

二叉樹的遍歷可以分為以下三種：(1)前序遍歷：假設(shè)二叉樹為空，則完畢

返回。否則：首先訪問根結(jié)點，然后遍歷

左子樹，最后遍歷右子樹。

(2)中序遍歷：假設(shè)二叉樹為空，則完畢返回。否則：首先遍歷左子樹，然后訪

問

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

(3)后序遍歷：假設(shè)二叉樹為空，則完畢返回。否則：首先遍歷左子樹，然后遍

歷

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

案例8.對以下二叉樹

進展前,ECFXZ)

6.線性彳

由一：1置只取決于自己的序號，元素之間的

相對位*小W由n(n20)個數(shù)據(jù)元素組成的一個有

限序列，叵*寤一個外，有且只有一個前件，除了最

后一個夕中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。

線性表口

套性表是一種存儲構(gòu)造,

它的存儲方式：順序和鏈?zhǔn)健?/p>

線性表的順序存儲構(gòu)造具有兩個基本特點：

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

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

由此可以看出，在線性表的順序存儲構(gòu)造中，其前后件兩個元素在存儲空間中

是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定

第i個結(jié)點的存儲地址。

順序表的插入、刪除運算

線性表的鏈?zhǔn)酱鎯?gòu)造(線性鏈表)

數(shù)據(jù)構(gòu)造中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，

簡稱結(jié)點。

結(jié)點由兩局部組成：

(1)用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；

(2)用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。

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

順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由

指針域來確定的。

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

線性構(gòu)造條件:

(1)有且只有一個根結(jié)占?

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

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

案例9.以下表達中正確的選項是(A)

A.循環(huán)隊列是隊列的一種順序存儲構(gòu)造

B.循環(huán)隊列是非線性構(gòu)造

C.循環(huán)隊列是一種邏輯構(gòu)造

D.循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯?gòu)造

解析：常見的線性構(gòu)造有：隊列、棧。非線性構(gòu)造有:樹、二叉樹

案例10.以下表達中正確的選項是(CE)

A.線性表鏈?zhǔn)酱鎯?gòu)造與順序存儲構(gòu)造所需要的存儲空間是一樣的

(不一樣)

B.線性表鏈?zhǔn)酱鎯?gòu)造所需要的存儲空間一般要少于順序存儲構(gòu)造

(多于)

C.線性表鏈?zhǔn)酱鎯?gòu)造所需要的存儲空間一般要多于順序存儲構(gòu)造

D.線性表鏈?zhǔn)酱鎯?gòu)造與順序存儲構(gòu)造的存儲空間都是連續(xù)的

E,線性表鏈?zhǔn)酱鎯?gòu)造的存儲空間可以是連續(xù)的，也可以是不連續(xù)的

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

是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。

冒泡排序、快速排序、直接插入排序：

假設(shè)線性表的長度為n,則在最壞情況下,需要對比的次數(shù)為n(n-1)/2

堆排序：

在最壞情況下,需要對比的次數(shù)為nloq2n

8.順序查找和二分查找

順序查找又稱為順序搜索。順序查找一般是指在線性表中查找指定的元素

下面兩種情況

1.如果線性表為無序表(即表中元素排序是無序的)，則不管是順序存儲構(gòu)造

還是鏈?zhǔn)酱鎯?gòu)造，都只能用順序查找

2.即使是有序線性表，如果采用鏈?zhǔn)酱鎯?gòu)造，也只能用于順序查找

二分查找只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素

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

當(dāng)有序線性表為順序存儲時才能采用二分查找，對于長度為n的有序線性表，

在最壞情況下,二分查找只需要對比loq2n次，而順序查找需要對比n次。

案例11.對長度為n的線性表排序，在最壞情況下，對比次數(shù)不是n(n-l)/2

的排序方法是(C)

A.快速排序B,冒泡排序C.堆排序D.直接插入排序

案例12.在長度為n的有序線性表中進展二分查找，最壞情況下需要對比的次

數(shù)是(A)

n2

A.O(log2n)B.0(nlog2)C.0(n)D.0(n)

案例13.對長度為10的線性表進展冒泡排序，最壞情況下需要對比的次

(B)

A.9B.45C.90D.10

第二章軟件工程基本概念

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

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

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

軟件周期:軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停頓使用退役的過程。

軟件生命周期三個階段：軟件定義、軟件開發(fā)、運行維護，主要活動階段是：

(1)可行性研究與方案制定;

(2)需求分析;

(3)軟件設(shè)計;

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

(5)軟件測試;

(6)運行和維護。

衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn)。

在程序構(gòu)造中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦

迨1。

內(nèi)聚性是指一個模塊內(nèi)部各個元素間彼此結(jié)合的嚴(yán)密程度

耦合性是指模塊間相互連接的嚴(yán)密程度

2.軟件測試

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

軟件測試方法：靜態(tài)測試和動態(tài)測試。

靜態(tài)測試包括代碼檢查、靜態(tài)構(gòu)造分析、代碼質(zhì)量度量。不實際運行軟件，主

要通過人工進展。

動態(tài)測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。

白盒測試：在程序內(nèi)部進展,主要用于完成軟件內(nèi)部CAO作的驗證。主要方法

有邏輯覆蓋、基本基路徑測試。

黑盒測試：在黑盒測試方法中,設(shè)計測試用例的主要根據(jù)是程序外部功能。主

要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。

軟件測試過程一般按4個步驟進展：單元測試、集成測試、驗收測試（確認測

述）和系統(tǒng)測試。

3.程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進展。

案例14.軟件詳細設(shè)計產(chǎn)生的圖如下：（C）

該圖是

A.PAD圖B.E-R圖C.程序流程圖D.N-S圖

第三章數(shù)據(jù)庫設(shè)計根基

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

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

數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。

（1）數(shù)據(jù)定義語言：負責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；

（2）數(shù)據(jù)操縱語言：負責(zé)數(shù)據(jù)的操縱，如查詢與增、冊人改等；

（3）數(shù)據(jù)控制語言：負責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故

障恢復(fù)等。

數(shù)據(jù)語言按其使用方式具有兩種構(gòu)造形式：交互式命令（又稱自含型或自主型

語言）宿主型語言（一般可嵌入某些宿主語言中）。

數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進展規(guī)劃、設(shè)計、維護、監(jiān)視等的專業(yè)管理人員。

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

員）、硬件平臺（硬件）、軟件平臺（軟件）五個局部構(gòu)成的運行實體。

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

段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng)一的、

管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段:為統(tǒng)一與共享數(shù)

據(jù)提供了有力支撐。

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

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

數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）、數(shù)據(jù)統(tǒng)一管理與控制。

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

（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯構(gòu)造的描述，全體用戶公共數(shù)據(jù)視

圖；

7?）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到

的數(shù)據(jù)模式;

（3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲構(gòu)造與物理存取方法。

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

數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、

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

述了數(shù)據(jù)構(gòu)造、數(shù)據(jù)操作及數(shù)據(jù)約束。

E-R模型的基本概念

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

（2）屬性：事物的特性；

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

多的聯(lián)系。

案例15.假設(shè)實體A和B是一對多的聯(lián)系，實體B和C是一對一的聯(lián)系，則

實體A和C的聯(lián)系是__________o一間宿舍可住多個學(xué)生，則實體宿舍和學(xué)生

之間的聯(lián)系是o（一對多）（一對多）

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

位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。一個實體的所有屬性值叫元

組。

E-R模型的圖示法：（1）實體集表示法；（2）屬性表法；（3）聯(lián)系表示法。

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

取一個作為用戶使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬

性集為A的外鍵或外碼。

系斗?的J數(shù)^折Jj.

（J）,實體完整值約束：約束關(guān)系的主鍵中屬性值不能為空值;

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

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

3.關(guān)系代數(shù)

關(guān)系數(shù)據(jù)庫系統(tǒng)的特點之一是它建設(shè)在數(shù)據(jù)理論的根基之上，有很多數(shù)據(jù)理論

可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。

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

（1）插入（2）刪除（3）修改（4）查詢（包括投影、選擇、笛卡爾積運算）

解析:

AB

1

a12

b21

c31

案例16.有三個關(guān)系R、S和T如下：(A)

則由關(guān)系R和S得到關(guān)系T的操作是

A.自然連接B.并C.投影D.交

案例.有三個關(guān)系R,S和T如下：(A)

則由關(guān)系R和S得到關(guān)系T的操作是

A.并B.交C.投影D.選擇

案例18.有三個關(guān)系R,S和T如下：(D)

則由關(guān)系R和S得到關(guān)系T的操作是

A.選擇B.交C.并D.差

案例19.有兩個關(guān)系R和S如下(A)

則由關(guān)系R得到關(guān)系S的操作是

A.選擇B.并C.自然連接D.投影

案例20.有兩個關(guān)系R,S如下：(C)

由關(guān)系R通過運算得到關(guān)系S,則所使用的運算為

A.連接B.插入C.投影D.選擇

第四章程序設(shè)計根基

1.面向?qū)ο蟮某绦蛟O(shè)計和構(gòu)造化程序設(shè)計面向?qū)ο蠓椒ǖ闹饕獌?yōu)點：(1)與

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

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

(3)可重用(注釋1)性好；

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

(5)可維護性好。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿梢杂脕肀硎究陀^

世界中的任何實體，對象是實體的抽象。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是

系統(tǒng)中用