二級公共基礎(chǔ)知識突擊學習全國計算機等級考試二級教程公共基礎(chǔ)知識考試說明及考綱程序設(shè)計基本概念及算法程序設(shè)計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)總體章節(jié)全國計算機等級考試

1、公共基礎(chǔ)知識考試說明及考綱

基本要求

1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)的能力。6.掌握數(shù)據(jù)的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計?？荚噧?nèi)容

一、基本數(shù)據(jù)結(jié)構(gòu)與算法

1.算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。4.棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。

二、程序設(shè)計基礎(chǔ)1.程序設(shè)計方法與風格。2.結(jié)構(gòu)化程序設(shè)計。3.面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細設(shè)計。4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。四、數(shù)據(jù)庫設(shè)計基礎(chǔ)1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2.數(shù)據(jù)模型，實體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。4.數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略?？荚嚪绞?、公共基礎(chǔ)的考試方式為筆試，與VisualFOXPRO的筆試部分合為一張試卷。公共基礎(chǔ)部分占全卷的30分。2、公共基礎(chǔ)知識有10道選擇題和5道填空題。學習方法理解基本概念多做練習適當記憶一些名詞與所學的VF程序設(shè)計知識結(jié)合起來，以增加對知識的理解能力全國計算機等級考試

2、程序設(shè)計基本概念及算法程序概念

什么是程序？

△指令的集合。（解釋指令）

△通過硬件控制系統(tǒng)自動完成某一功能。

△通過一系列代碼實現(xiàn)。

程序怎樣執(zhí)行？怎樣編寫？

△計算機本身僅能識別二進制代碼“0”、“1”?！骶幊套钪苯?、最低級的就是機器語言?！鳛榻鉀Q機器語言難理解、記憶等問題。出現(xiàn)符號語言?！鳛槭咕幊探咏匀徽Z言，出現(xiàn)高級語言。如C、PASCAL、FORTRAN2.1算法2.1.1算法(algorithm)基本概念對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。關(guān)于問題及問題解決方案的具體描述。

算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報）等５個重要特點。有窮性：在有限時間有限步驟內(nèi)執(zhí)行完畢。確定性：在執(zhí)行過程中命令只可由一個方式，不可有歧義必須唯一?？尚行裕簩轭}的描述可行。有一定的輸入輸出又稱為有足夠的情報2.1.2算法的基本要素

1、對數(shù)據(jù)對象的運算和操作算術(shù)運算邏輯運算關(guān)系運算數(shù)據(jù)傳輸2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等一個算法一般可以用順序、選擇、循環(huán)三種基本機構(gòu)組合而成。2.2算法復(fù)雜度2.2.1時間復(fù)雜度依據(jù)算法算法編制的程序在計算機上運行時所消耗的時間來度量。通常有事后統(tǒng)計法和事前分析估算法。一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作構(gòu)成的，算法時間取決于兩者的綜合效果。復(fù)雜性執(zhí)行效率（事前評估\事后分析）算法的時間復(fù)雜度：算法在執(zhí)行過程中所需要執(zhí)行的基本運算次序。2.2.2算法的空間復(fù)雜度

算法空間復(fù)雜度：算法在執(zhí)行過程中所用到的存儲空間大小一般是指執(zhí)行這個算法所需要的內(nèi)存空間一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。例題講解算法的時間復(fù)雜度是指A)執(zhí)行算法程序所需要的時間B)算法程序的長度C)算法執(zhí)行過程中所需要的基本運算次數(shù)D)算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、

【1】和擁有足夠的情報。算法的空間復(fù)雜度是指

A)算法程序的長度 B)算法程序中的指令條數(shù)

C)算法程序所占的存儲空間D)執(zhí)行過程中所需要的存儲空間在計算機中，算法是指

A)加工方法 B)解題方案的準確而完整的描述

C)排序方法 D)查詢方法算法分析的目的是

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)找出算法中輸入和輸出之間的關(guān)系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的【1】。數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有時一個數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點或記錄。

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

2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)

B．非線性結(jié)構(gòu)A順序存儲

B鏈式存儲線性表、數(shù)組棧、廣義表隊列、串樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面數(shù)據(jù)結(jié)構(gòu)可描述為Group=（D，R）樹形結(jié)構(gòu)全校學生檔案管理的組織方式計算機程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)ABCDEFGH樹形結(jié)構(gòu)——結(jié)點間具有分層次的連接關(guān)系HBCDEFGA1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

圖形結(jié)構(gòu)——節(jié)點間的連結(jié)是任意的元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容順序存儲元素n……..元素i……..元素2元素1存儲內(nèi)容順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。順序存儲結(jié)構(gòu)的三個弱點：1.作插入或刪除操作時，需移動大量元數(shù)。2.長度變化較大時，需按最大空間分配。3.表的容量難以擴充。例題講解數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于【1】

。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的

A)存儲結(jié)構(gòu) B)物理結(jié)構(gòu)

C)邏輯結(jié)構(gòu) D)物理和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】

兩大類。順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置

【2】的存儲單元中。數(shù)據(jù)處理的最小單位是

A)數(shù)據(jù) B)數(shù)據(jù)元素C)數(shù)據(jù)項 D)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及

A)數(shù)據(jù)的存儲結(jié)構(gòu) B)計算方法C)數(shù)據(jù)映象D)邏輯存儲線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是

A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B)隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

C)隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)

D)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)2.3.2線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作特點：

1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。

2、所有元素所占的存儲空間是連續(xù)的

3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的

2.做插入、刪除時需移動大量元素。

3.空間估計不明時，按最大空間分配。…..a2a1an…..ai+1ai01i-1in-1

1-1插入運算ai-1…..a2a1alength…ai+1aixai-1…..a2a1

aiai+1…alength

alength……ai+1

aix

插入算法的分析假設(shè)線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：

刪除算法的分析在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：

分析結(jié)論順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。2.4棧和隊列2.4.1棧和隊列的定義

棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。2.4.1.1棧的定義棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進先出設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底（bottom):不允許插入和刪除的一端。a1a2….an進棧出棧棧頂棧底隊列的主要運算（1）設(shè)置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；2.4.1.2隊列的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結(jié)構(gòu)稱為先進先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an隊列示意圖隊頭隊尾2.4.2棧的順序存儲結(jié)構(gòu)及其基本運算a2a1a1a2top用順序存儲結(jié)構(gòu)表示的棧。

順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\算：壓（進）棧：PUSH出棧：POP例題講解棧和隊列的共同特點是

A)都是先進先出B)都是先進后出

C)只允許在端點處插入和刪除元素D)沒有共同點如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e4,e3,e2,e1 D)任意順序下列關(guān)于棧的敘述中正確的是Ａ）在棧中只能插入數(shù)據(jù)B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表D）棧是后進先出的線性表下列關(guān)于隊列的敘述中正確的是Ａ）在隊列中只能插入數(shù)據(jù)B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表D）隊列是后進先出的線性表棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE

棧通常采用的兩種存儲結(jié)構(gòu)是

A)線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B)散列方式和索引方式

C)鏈表存儲結(jié)構(gòu)和數(shù)組D)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊列通常采用的存儲結(jié)構(gòu)是【1】

。下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是

A)線性鏈表B)棧C)循環(huán)鏈表 D)順序表2.6樹樹的基本概念二叉樹的定義及其存儲結(jié)構(gòu)二叉樹的前序、中序和后序遍歷2.6.1樹的定義由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。

A

C

GT2D

HIT3J

M

BEL

KT1F現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。介紹幾個概念：結(jié)點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。結(jié)點的度（Degree）：結(jié)點擁有的子樹數(shù)。結(jié)點的層次：從根結(jié)點開始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點，也稱端結(jié)點。孩子（Child）：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的雙親。深度（Depth)：樹中結(jié)點的最大層次數(shù)。森林（Forest）：M棵互不相交的樹的集合。

A

C

GT2D

HIT3J

M

BEL

KT1F2.6.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結(jié)構(gòu)，特點是樹中每個結(jié)點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。空二叉樹

僅有根結(jié)點

右子樹為空左子樹為空左右子樹均非空因為樹的每個結(jié)點的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。二叉數(shù)是n(n0)個結(jié)點的有限集合。它或為空數(shù)(n=0),或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。

特別要注意：二叉數(shù)不是樹的特殊情況。aabb兩棵不同的二叉數(shù)A、

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。(2)二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。A、

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。

B、

深度為h的二叉樹中至多含有2h-1個結(jié)點。(2)二叉樹的基本性質(zhì)423167891011121314155此樹的深度h=4，共有24-1=15個節(jié)點。A、

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。B、

深度為h的二叉樹中至多含有2h-1個結(jié)點。C、

若在任意一棵二叉樹中，有n0個葉子結(jié)點，有n2個度為2的結(jié)點，則：n0=n2+1(2)二叉樹的基本性質(zhì)423167891011121314155n0=8n2=7（3）滿二叉樹423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)。423167891011125

非完全二叉樹（4）完全二叉樹423167891011125

完全二叉樹特點：除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。（5）樹與二叉樹的區(qū)別A．樹的結(jié)點個數(shù)至少為1，而二叉樹的結(jié)點個數(shù)可以為0。B．樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。C．樹的結(jié)點無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。

樹

二叉樹2、二叉樹的存儲結(jié)構(gòu)

(2)鏈式存儲結(jié)構(gòu)T[16]若父結(jié)點在數(shù)組中i下標處，其左孩子在2*i處，右孩子在2*i+1處。11ABcFED

●●●●●●●●●124

8

910563712131415(1)順序存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)2h-1=24-1=15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。2.6.3二叉樹的遍歷查找某個結(jié)點，或?qū)Χ鏄渲腥拷Y(jié)點進行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)點只被訪問一次。按先左后右的原則，一般使用三種遍歷：前序遍歷:

根左右

訪問根結(jié)點，前序遍歷左子樹，前序遍歷右子樹。中序遍歷:左根右

按中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹。后序遍歷:左右根

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。

（2）遍歷算法先序遍歷：中序遍歷：后序遍歷：ADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA例題講解已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是

A)acbedB)decabC)deabc

D)cedba

已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG樹是結(jié)點的集合，它的根結(jié)點數(shù)目是

A)有且只有1 B)1或多于1C)0或1 D)至少2在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為

A)32 B)31C)16 D)15若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是

A)bdgcefhaB)gdbecfhaC)bdgaechf

D)gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點沒有【1】根。下列敘述中正確的是

A)線性表是線性結(jié)構(gòu)

B)棧與隊列是非線性結(jié)構(gòu)

C)線性鏈表是非線性結(jié)構(gòu) D)二叉樹是線性結(jié)構(gòu)具有3個結(jié)點的二叉樹有

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)

設(shè)有下列二叉樹：

對此二叉樹前序遍歷的結(jié)果為A)ZBTTCPXA B)ATBZXCTPC)ZBTACTXPD)ATBZXCPT設(shè)一棵二叉樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為

A)12 B)13C)14 D)15

設(shè)有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA設(shè)樹T的深度為4,其中度為1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點數(shù)為n0=n2+1A）8B）7C）6D）5設(shè)一棵完全二叉樹共有700個結(jié)點，則該二叉樹中有（350）個葉子結(jié)點。

設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（DEBFCA）。2.7查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）2.7.1查找查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點查找失敗：找不到滿足條件的結(jié)點。2.7.1.1順序查找（線性查找）查找過程：對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達表的另一端。可以采用從前向后查，也可采用從后向前查的方法?！ぴ谄骄闆r下，大約要與表中一半以上元素進行比較，效率較低。平均查找長度較大?！ぴ谙旅鎯煞N情況下只能采取順序查找：

a.線性表為無序表（元素排列是無序的）；

b.即使是有序線性表，但采用的是鏈式存儲結(jié)構(gòu)。2.7.1.2折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。分三種情況：1）若中間項的值等于x,則說明已查到。2）若x小于中間項的值，則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。2.7.2排序2.7.2.1概述1、排序的功能：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個按關(guān)鍵字有序的序列。2、排序過程的組成步驟：首先比較兩個關(guān)鍵字的大??；然后將記錄從一個位置移動到另一個位置。排序方法插入排序選擇排序交換排序歸并排序直接插入排序折半插入排序簡單選擇排序堆排序起泡排序快速排序2.7.2.2插入排序

直接插入、折半插入1、直接插入排序:

基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當位置上。需要n(n-1)/2次比較該算法適合于n較小的情況，時間復(fù)雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1次2、折半插入排序

折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。折半插入排序的條件：在有序序列中插入一個關(guān)鍵字。例：有6個記錄，前5個已排序的基礎(chǔ)上，對第6個記錄排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找結(jié)束，插入位置為low或high+1)(42>36)(42<53)

1、簡單選擇排序思想：首先從1~n個元素中選出關(guān)鍵字最小的記錄交換到第一個位置上。然后再從第2個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。時間復(fù)雜度為O(n2)，最壞情況下需要比較

n(n-1)/2次適用于待排序元素較少的情況。2.7.2.3選擇排序

簡單選擇排序、堆排序初態(tài)83916839168391683916ijkijkijkijk1

3986互換ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟

2

堆排序

也是一種選擇排序。是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結(jié)點的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。

(1)堆的示例

897624331510112536497856(a):堆頂元素取最大值(b):堆頂元素取最小值(2)實現(xiàn)堆排序需解決兩個問題：

（1）如何由一個無序序列建成一個堆？（2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個新的堆？堆排序需要比較的次數(shù)為O(nlog2n)2.7.2.4交換排序交換排序的特點在于交換。有冒泡和快速排序兩種。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，……關(guān)鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個位置上；依次類推，則完成排序。正序：時間復(fù)雜度為O(n)逆序：時間復(fù)雜度為O(n2)

適合于數(shù)據(jù)較少的情況。

排序n個記錄的文件最多需要n-1趟冒泡排序。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字思想：小的浮起，大的沉底。49364165117836653641563641654136415611783636414911564925252511494956111111252525252、快速排序(對冒泡排序的改進）思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠郑蛊渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達到整個序列有序。關(guān)鍵字通常取第一個記錄的值為基準值。做法：附設(shè)兩個指針low和high

，初值分別指向第一個記錄和最后一個記錄，設(shè)關(guān)鍵字為

key

，首先從high所指位置起向前搜索，找到第一個小于基準值的記錄與基準記錄交換，然后從low

所指位置起向后搜索，找到第一個大于基準值的記錄與基準記錄交換，重復(fù)這兩步直至low=high為止。時間復(fù)雜度：O(log2n)快速排序過程示意圖：有序序列618235267key初始序列235266718lowhigh一次交換185266723lowhigh二次交換18

2366752high三次交換[186]23[6752]//完成一趟排序后分別進行快速排序lowhigh2.7.2.5內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點，故在不同情況下可作不同的選擇。通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大小；記錄的鍵值分布情況等。若待排序的記錄個數(shù)n較小時，可采用簡單排序方法。若n較大時，應(yīng)采用快速排序或堆排序。若待排序的記錄已基本有序，可采用起泡排序。例題講解在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數(shù)為

【2】。長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為【1】

。假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為

A)log2n B)n2C)O(n1..5) D)n(n-1)/2已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應(yīng)采用的算法是

A)堆排序B)直接插入排序C)快速排序D)直接選擇排序在下列幾種排序方法中，要求內(nèi)存量最大的是

A)插入排序

B)選擇排序C)快速排序 D)歸并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A)冒泡排序

B)選擇排序C)快速排序D)歸并排序

希爾排序?qū)儆?/p>

A)交換排序B)歸并排序C)選擇排序 D)插入排序?qū)﹂L度為n的線性表進行順序查找，在最壞的情況下所需要的比較次數(shù)為Ａ)n+1B)nC)(n+1)/2D)n/22.8其他串圖2.8.1串串的定義和基本運算串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。串中字符的數(shù)目n被稱作串的長度。當n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串。

s1=“”s2=“”s1中沒有字符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。兩個串相等：兩個串的長度相等，并且各個對應(yīng)的字符也都相同。例如，有下列四個串a(chǎn)，b，c，d：

a=“program”b=“Program”c=“pro”d=“program”

圖有向圖無向圖在有向圖中，<V1，V3>表示從V1到V3的一條弧。

V1為弧尾或初始點，V3為弧頭或終端點。在無向圖中，(V1，V3)表示V1和V3之間的一條邊。V1V3V2V4V1V3V2V4圖沒有層次關(guān)系層有層次關(guān)系2.8.2圖的基本概念連通圖：選中任意一個點都可以到其它節(jié)點非連通圖：E無法與A,B,C,D建立聯(lián)系強連通圖：n個頂點的連通圖中邊的條數(shù)至少為n-1條．n個頂點的強連通圖的邊數(shù)至少有n條．EABCDE例題講解串的長度是

A)串中不同字符的個數(shù)B)串中不同字母的個數(shù)

C)串中所含字符的個數(shù)且字符個數(shù)大于零D)串中所含字符的個數(shù)若串s=“MathTypes”，則其子串的數(shù)目是

【3】。

n個頂點的強連通圖的邊數(shù)至少有

A)n-1 B)n(n-1)C)n D)n+1

設(shè)有兩個串p和q，求q在p中首次出現(xiàn)位置的運算稱作

A)連接 B)模式匹配C)求子串D)求串長n個頂點的連通圖中邊的條數(shù)至少為

A)0 B)1C)n-1 D)n全國計算機等級考試

3.程序設(shè)計基礎(chǔ)

3.1程序設(shè)計方法與風格3.1.1程序設(shè)計方法1、結(jié)構(gòu)化設(shè)計方法模塊內(nèi)部程序各部分要按照自頂向下的結(jié)構(gòu)劃分各程序部分應(yīng)按功能組合各程序之間的聯(lián)系盡量通過調(diào)用子程序來實現(xiàn)，不用或少用GOTO方式2.語句的結(jié)構(gòu)每條語句簡單明了盡量不用或少用GOTO語句盡量只采用3種基本控制結(jié)構(gòu)編程3.輸入和輸出對所有輸入數(shù)據(jù)進行校驗和合理性檢查輸入輸出格式保持一致設(shè)計良好的輸出報表三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)三種基本結(jié)構(gòu)的特點只有一個入口只有一個出口每一個基本結(jié)構(gòu)中的每一部分都有機會執(zhí)行到結(jié)構(gòu)內(nèi)不存在“死循環(huán)”3.2.2設(shè)計原則自頂向下逐步求精模塊化限制使用goto語句類(Class)一個類定義了一組大體上相似的對象。一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。類是在對象之上的抽象，對象是類的具體化，是類的實例封裝(Encapsulation)將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構(gòu)成一個具有類類型的對象的描述。對象的內(nèi)部實現(xiàn)受保護，外界不能訪問封裝簡化了程序員對對象的使用例題講解結(jié)構(gòu)化程序設(shè)計的3種結(jié)構(gòu)是

A)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)B)分支結(jié)構(gòu)、等價結(jié)構(gòu)、循環(huán)結(jié)構(gòu)

C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價結(jié)構(gòu)D)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)在設(shè)計程序時，應(yīng)采納的原則之一是

A)不限制goto語句的使用B)減少或取消注解行

C)程序越短越好 D)程序結(jié)構(gòu)應(yīng)有助于讀者理解結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是

A)程序的規(guī)模 B)程序的效率

C)程序設(shè)計語言的先進性 D)程序易讀性以下不屬于對象的基本特點的是

A)分類性B)多態(tài)性C)繼承性 D)封裝性

對建立良好的程序設(shè)計風格，下面描述正確的是

A)程序應(yīng)簡單、清晰、可讀性好 B)符號名的命名只要符合語法

C)充分考慮程序的執(zhí)行效率 D)程序的注釋可有可無在結(jié)構(gòu)化程序設(shè)計思想提出之前，在程序設(shè)計中曾強調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的

A)安全性 B)一致性C)可理解性 D)合理性程序的3種基本控制結(jié)構(gòu)是

A)過程、子過程和分程序 B)順序、選擇和重復(fù)

C)遞歸、堆棧和隊列 D)調(diào)用、返回和轉(zhuǎn)移下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計方法的主要原則的是

A)自頂向下 B)由底向上

C)模塊化 D)限制使用goto語句對象實現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進行

A)結(jié)合 B)隱藏C)封裝 D)抽象在面向?qū)ο蠓椒ㄖ校粋€對象請求另一個對象為其服務(wù)的方式是通過發(fā)送A）調(diào)用語句B）命令C）口令D）消息信息屏蔽的概念與下述哪一種概念直接相關(guān)A）軟件結(jié)構(gòu)定義B）模塊獨立性C）模塊類型劃分D）模塊偶合度下列對象概念描述錯誤的是A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動態(tài)屬性全國計算機等級考試

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

(4)4.軟件工程基礎(chǔ)4.1基本概念1.軟件工程軟件工程是指應(yīng)用計算機科學、數(shù)學及管理科學等原理，以工程化的原則和方法來解決軟件問題的工程。其目的是提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低軟件成本。2.軟件危機早期的軟件主要指程序，采用個體工作方式，缺少相關(guān)文檔，質(zhì)量低，維護困難，這些問題稱為“軟件危機”，軟件工程概念的出現(xiàn)源自于軟件危機。3.軟件生命周期將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護3個階段。維護是持續(xù)時間最長，花費代價最大的一個階段，軟件工程學的一個目的就是提高軟件的可維護性，降低維護代價4.軟件工程三要素方法：完成軟件工程項目的技術(shù)手段工具：支持軟件的開發(fā)、管理、文檔生成過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理4.2結(jié)構(gòu)化分析方法基本思想將系統(tǒng)分析看成工程項目，有計劃、有步驟地進行工作。開發(fā)策略自頂向下，逐層分解分析結(jié)果一套分層的數(shù)據(jù)流圖(DFD)：用來描述數(shù)據(jù)流從輸入到輸出的變換流程一個數(shù)據(jù)字典(DD)：用來描述DFD中的每個數(shù)據(jù)流、文件以及組成數(shù)據(jù)流或文件的數(shù)據(jù)項一組小說明（加工邏輯說明）：用來描述每個基本加工的加工邏輯PAD程序設(shè)計圖PFD程序流程圖N-S方格圖（方格表示分支）DFD數(shù)據(jù)流圖4.3.總體設(shè)計設(shè)計原則分解—協(xié)調(diào)原則自頂向下的原則信息屏蔽、抽象的原則一致性原則明確性原則模塊間的耦合度盡可能小，模塊內(nèi)部組合盡可能緊湊（內(nèi)聚性高）耦合度：兩個或兩個模塊之間關(guān)聯(lián)的緊密程度稱為4.4軟件測試4.4.1意義目的為了發(fā)現(xiàn)錯誤希望能以最少的人力和時間發(fā)現(xiàn)潛在的各種錯誤和缺陷保證系統(tǒng)質(zhì)量和可靠性的關(guān)鍵步驟4.4.2測試方法人工測試機器測試4.4.3白盒測試結(jié)構(gòu)測試將軟件看成透明的白盒，根據(jù)程序的內(nèi)部結(jié)構(gòu)和邏輯結(jié)構(gòu)來設(shè)計測試例子，對程序的路徑和過程進行測試，檢查是否滿足設(shè)計的要求4.4.4黑盒測試功能測試將軟件看成黑盒子，在完全考慮軟件內(nèi)部結(jié)構(gòu)和特性的情況下，測試軟件的外部特性4.5程序調(diào)試4.5.1任務(wù)根據(jù)測試時發(fā)現(xiàn)的錯誤，找出原因和具體的位置，進行改正有程序開發(fā)人員來進行，誰開發(fā)的程序就由誰來進行調(diào)試方法：強行排錯法回溯法原因排除法（演繹、歸納、二分法)例題講解為了提高測試的效率，應(yīng)該

A)隨機選取測試數(shù)據(jù)B)取一切可能的輸入數(shù)據(jù)作為測試數(shù)據(jù)

C)在完成編碼以后制定軟件的測試計劃D)集中對付那些錯誤群集的程序軟件生命周期中所花費用最多的階段是

A)詳細設(shè)計 B)軟件編碼C)軟件測試D)軟件維護下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是

A)便于用戶、開發(fā)人員進行理解和交流

B)反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)

C)作為確認測試和驗收的依據(jù)

D)便于開發(fā)人員進行需求分析下列不屬于軟件工程的3個要素的是Ａ)工具 Ｂ)過程Ｃ)方法 Ｄ)環(huán)境開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱作

A)軟件投機 B)軟件危機C)軟件工程D)軟件產(chǎn)生下面不屬于軟件設(shè)計原則的是Ａ)抽象 Ｂ)模塊化Ｃ)自底向上Ｄ)信息隱蔽開發(fā)大型軟件時，產(chǎn)生困難的根本原因是

A)大系統(tǒng)的復(fù)雜性 B)人員知識不足

C)客觀世界千變?nèi)f化 D)時間緊、任務(wù)重軟件工程的出現(xiàn)是由于

A)程序設(shè)計方法學的影響 B)軟件產(chǎn)業(yè)化的需要

C)軟件危機的出現(xiàn) D)計算機的發(fā)展軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持，其中必要的測試數(shù)據(jù)屬于

A)硬件資源 B)通信資源C)支持軟件D)輔助資源在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列不屬于結(jié)構(gòu)化分析的常用工具的是

A)數(shù)據(jù)流圖 B)數(shù)據(jù)字典C)判定樹 D)PAD圖在軟件生產(chǎn)過程中，需求信息的給出是

A)程序員B)項目管理者

C)軟件分析設(shè)計人員 D)軟件用戶下列工具不是需求分析常用工具的是Ａ)PAD Ｂ)PFDＣ)N-S Ｄ)DFD模塊獨立性是軟件模塊化所提出的要求，衡量模塊獨立性的度量標準則是模塊的

A)抽象和信息隱蔽 B)局部化和封裝化

C)內(nèi)聚性和耦合性 D)激活機制和控制方法軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成

A)定義、開發(fā)、運行維護B)設(shè)計階段、編程階段、測試階段

C)總體設(shè)計、詳細設(shè)計、編程調(diào)試D)需求分析、功能定義、系統(tǒng)設(shè)計在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是

A)

路徑的集合B)循環(huán)的集合C)目標的集合D)地址的集合完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導(dǎo)出測試用例的測試方法是

A)黑箱測試法B)白箱測試法C)錯誤推測法D)安裝測試法在結(jié)構(gòu)化設(shè)計方法中，生成的結(jié)構(gòu)圖(SC)中，帶有箭頭的連線表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列選項中，不屬于模塊間耦合的是

A)數(shù)據(jù)耦合B)同構(gòu)耦合C)異構(gòu)耦合D)公用耦合下列敘述中，不屬于測試的特征的是

A)測試的挑剔性 B)完全測試的不可能性

C)測試的可靠性 D)測試的經(jīng)濟性需求分析中開發(fā)人員要從用戶那里了解

A)軟件做什么 B)用戶使用界面

C)輸入的信息 D)軟件的規(guī)模下列不屬于軟件調(diào)試技術(shù)的是

A)強行排錯法 B)集成測試法

C)回溯法 D)原因排除法為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為

A)PAD圖 B)N-S圖C)結(jié)構(gòu)圖 D)數(shù)據(jù)流圖軟件復(fù)雜性度量的參數(shù)包括

A)效率 B)規(guī)模C)完整性 D)容錯性下列敘述中，正確的是

A)軟件就是程序清單B)軟件就是存放在計算機中的文件

C)軟件應(yīng)包括程序清單及運行結(jié)果D)軟件包括程序和文檔軟件設(shè)計中，有利于提高模塊獨立性的一個準則是

A)低內(nèi)聚低耦合 B)低內(nèi)聚高耦合

C)高內(nèi)聚低耦合 D)高內(nèi)聚高耦合軟件生命周期中花費時間最多的階段是

A)詳細設(shè)計 B)軟件編碼C)軟件測試D)軟件維護下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法

D)面向?qū)ο蟮姆治龇椒ㄔ敿氃O(shè)計的結(jié)果基本決定了最終程序的

A)代碼的規(guī)模 B)運行速度

C)質(zhì)量 D)可維護性下列不屬于靜態(tài)測試方法的是

A)代碼檢查 B)白盒法

C)靜態(tài)結(jié)構(gòu)分析 D)代碼質(zhì)量度量在軟件生命周期中，能準確地確定軟件系統(tǒng)必須做什么和必須局別哪些功能的階段是A）概要設(shè)計B）詳細設(shè)計C）可行性分析D）需求分析檢查軟件產(chǎn)品是否符合需求定義的過程稱為A）確認測試B）集成測試C）驗證測試D）驗收測試數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成，下列圖符名標識的圖符不屬于數(shù)據(jù)流圖合法圖符的是A）控制流B）加工C）數(shù)據(jù)存儲D）源和潭下面不屬于軟件設(shè)計原則的是A）抽象B）模塊化C）自底向上D）信息屏蔽程序流程圖（PFD）中的箭頭代表的是A）數(shù)據(jù)流B）控制流C）調(diào)用關(guān)系D）組成關(guān)系下列工具中為需求分析常用工具的是A）PADB）PFDC）N-SD）DFD在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是A）詳細設(shè)計B）需求分析C）總體設(shè)計D）編程調(diào)試軟件調(diào)試的目的是A）發(fā)現(xiàn)錯誤B）改正錯誤C）改善軟件的性能D）挖掘軟件的潛能軟件需求分析階段的工作，可以分為四個方面：需求獲取，需求分析，編寫需求規(guī)格說明書，以及A）階段性報告B）需求評審C）總結(jié)D）都不正確全國計算機等級考試

5.數(shù)據(jù)庫設(shè)計基礎(chǔ)5.數(shù)據(jù)庫設(shè)計基礎(chǔ)5.1基本概念

1.數(shù)據(jù)(Data)2.數(shù)據(jù)庫(DB)3.數(shù)據(jù)庫管理系統(tǒng)(DBMS)主要功能包括數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS一般提供相應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言數(shù)據(jù)操縱語言數(shù)據(jù)控制語言

4.數(shù)據(jù)庫管理員主要工作包括：數(shù)據(jù)庫設(shè)計數(shù)據(jù)庫維護改善系統(tǒng)性能，提高系統(tǒng)效率5.數(shù)據(jù)庫系統(tǒng)（DBS）由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、系統(tǒng)平臺之硬件平臺（硬件）和軟件平臺（軟件）構(gòu)成。6.數(shù)據(jù)庫管理技術(shù)的發(fā)展人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段7.數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫系統(tǒng)的三級模式（1）概念模式（2）外模式（3）內(nèi)模式內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計算機物理結(jié)構(gòu)中的實際存儲形式概念模式處于中層，它放映了設(shè)計者的數(shù)據(jù)全局邏輯要求外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求5.2數(shù)據(jù)模型5.2.1數(shù)據(jù)模型的基本概念數(shù)據(jù)模型是數(shù)據(jù)特性的抽象數(shù)據(jù)模型描述的內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型概念數(shù)據(jù)模型（概念模型）邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）物理數(shù)據(jù)模型（物理模型）5.2.2E-R模型（實體聯(lián)系模型）基本概念（1）實體（2）屬性（3）聯(lián)系一對一（1：1）一對多（1：M或M：1）多對多（M：N）5.2.3層次模型一種樹形結(jié)構(gòu)5.2.4網(wǎng)狀模型一個不加任何條件限制的無向圖優(yōu)于層次模型使用時設(shè)計系統(tǒng)內(nèi)部的物理因素較多，用戶操作不方便，其數(shù)據(jù)模式與系統(tǒng)實現(xiàn)不甚理想5.2.5關(guān)系模型采用二維表來表示，簡稱表。二維表的性質(zhì)：元素個數(shù)有限性、元組的惟一性、元組的次序無關(guān)性、屬性的次序無關(guān)性、分量值域的同一性關(guān)系操縱：查詢、增加、刪除和修改數(shù)據(jù)庫設(shè)計目前一般采用生命周期法，分若干階段需求分析階段概念設(shè)計階段邏輯設(shè)計階段物理設(shè)計階段編碼階段測試階段運行階段進一步修改階段在數(shù)據(jù)庫設(shè)計中采用前四個階段，并且重點以數(shù)據(jù)結(jié)構(gòu)與模型的設(shè)計為主線5.4數(shù)據(jù)庫概念設(shè)計設(shè)計的過程

3種設(shè)計次序（自頂向下、由底向上、由內(nèi)向外）例題講解下列有關(guān)數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)庫是一個DBF文件 B)數(shù)據(jù)庫是一個關(guān)系

C)數(shù)據(jù)庫是一個結(jié)構(gòu)化的數(shù)據(jù)集合 D)數(shù)據(jù)庫是一組文件下列有關(guān)數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程

B)數(shù)據(jù)的物理獨立性是指當數(shù)據(jù)的邏輯結(jié)構(gòu)改變時，數(shù)據(jù)的存儲結(jié)構(gòu)不變

C)關(guān)系中的每一列稱為元組，一個元組就是一個字段

D)如果一個關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個關(guān)系的關(guān)鍵字，則稱其為本關(guān)系的外關(guān)鍵字在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。其中數(shù)據(jù)獨立性最高的階段是Ａ)數(shù)據(jù)庫系統(tǒng) Ｂ)文件系統(tǒng)Ｃ)人工管理 Ｄ)數(shù)據(jù)項管理下述關(guān)于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是Ａ)數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余Ｂ)數(shù)據(jù)庫系統(tǒng)避免了一切冗余Ｃ)數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類型一致Ｄ)數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)下列SQL語句中，用于修改表結(jié)構(gòu)的是

A)ALTER B)CREATEC)UPDATED)INSERT數(shù)據(jù)庫系統(tǒng)的核心是

A)數(shù)據(jù)庫 B)數(shù)據(jù)庫管理系統(tǒng)

C)模擬模型 D)軟件工程數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)之間的關(guān)系是

A)數(shù)據(jù)庫包括數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)

B)數(shù)據(jù)庫系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)

C)數(shù)據(jù)庫管理系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫系統(tǒng)

D)3者沒有明顯的包含關(guān)系關(guān)系模型允許定義3類數(shù)據(jù)約束，下列不屬于數(shù)據(jù)約束的是

A)實體完整性約束 B)參照完整性約束

C)域完整性約束 D)用戶自定義的完整性約束關(guān)系表