數據結構與算法

一、基本概念:

?:?數據（Data）：信息的載體，能夠被計算機

識別、存儲和加工處理的物理符號。包括

文本類型的數據（如：字母、數字、中文）

和多媒體類型的數據（如：聲音、動畫、

圖像）。

?:?數據元素（DataElement）：是數據的基本

單位，有時也稱為元素、結點、頂點、統

計，能夠有若干個數據項（字段、域、屬

性）組成。

?:?數據結構（DataStructure）：指的是數

據之間的相互關系，即數據的組織形式。

其包括三個部分：

1、邏輯結構：數據元素之間的邏輯關系

2、存儲結構：數據元素及其關系在計算

機存儲器內的表示。

3、數據的運算（算法）：即對數據施加的

操作

?:?數據的邏輯結構有兩大類:

1、線性結構:

特性是：若結構是非空集，則有且僅有一個

開始結點和一個終端結點，并且所有結點］l=J

多只有一個直接前趨和一個直接后繼。

例：一維數組、鏈表、棧、隊列、串

2、非線性結構：

特性是：一個結點也許有多個直接前趨和直

接后繼。

例：多維數組、廣義表、樹、圖

數據的存儲結構有如下基本存儲措施:

1、次序存儲措施:

該措施是將邏輯上相鄰的結點存儲在物理

位置上相鄰的存儲單元里，結點間的邏輯關

系由存儲單元的鄰接關系來體現，一般通過

數組來實現的。

2、鏈接存儲措施：

該措施不要求邏輯上相鄰的結點在物理位

置上亦相鄰，結點間的邏輯關系是由附加的

指針字段表示的。通過指針類型來實現的。

3、索引存儲措施：

該措施一般是在存儲結點信息的同時，還建

立附加的索引表，索引表中的每一項稱為索

引項，索引項的一般形式是：核心字，地址。

4、散列存儲措施：

該措施的基本思想是依照結點的核心字直

接計算出該結點的存儲地址，通過散列函數

實現。例：除余法散列函數、相乘取整法散

列函數

?:?算法的基本特性：

1＞可行性(Effectiveness)：針對實際問題

而設計的算法，執(zhí)行后能夠得到滿意的成

果。

2、確定性(Definiteness)：算法中的每一

個步驟都必須有明確的定義，不允許出現歧

義性。

3、有窮性(Finiteness)：算法必須在有限

時間內做完，即必須在執(zhí)行有限個步驟之后

終止。

?:?時間復雜度：該算法執(zhí)行的時間花費，它

是該算法所求解問題規(guī)模n的函數。

?:?空間復雜度：該算法執(zhí)行時所花費的存儲

空間，它也是問題規(guī)模n的函數。

二、線性表:

?線性表(LinearList)：是由n(n>=0)個數

據元素(結點)aba2,a3,....,an組成的

有限序列。對于非空的線性表，有且僅有

一個開始結點ai,它沒有直接前趨；有且

僅有一個終端結點為,它沒有直接后繼；

其他的結點有且僅有一個直接前趨結點

和一個直接后繼結點。

?:?線性表的存儲結構：

1、次序存儲(SequentialList)：將線性表

的結點按邏輯次序依次存儲在一組地址連

續(xù)的存儲單元里，用這種措施存儲的線性表

稱為次序表。

2、鏈式存儲(LinkedList)：邏輯上相鄰的

結點，物理上也相鄰，存儲單元能夠是連續(xù)

的，也能夠是不連續(xù)的，在存儲每個結點值

的同時，還存儲指向其后繼結點的地址，用

這種措施存儲的線性表稱為鏈表。

。常見的運算有：

表的初始化、求表的長度、取表中的第i個

結點、查找結點、插入新的結點、刪除結點。

?:?次序表和鏈表的比較:

1、基于空間的考慮：

A、次序表的存儲空間是靜態(tài)分派的，而鏈

表的存儲空間是動態(tài)分派的。

B、次序表占的存儲空間必須是連續(xù)的，而

鏈表占的存儲空間能夠是連續(xù)的，也可是不

連續(xù)的

C、次序表存儲密度為1,而鏈表中的每個結

點，除了數據域外，還要額外的設置指針域,

存儲密度小于1

2、基于時間的考慮：

A、在鏈表中的任何位置上進行插入和刪除,

只需要修改指針，而次序表中平均將要移動

近二分之一的結點。

B、次序表是隨機存取結構，它的存取時間

為0(1),而鏈表需從頭結點順著鏈掃描鏈

表。

總之，當線性表的長度變化不大，易于

事先確定其大小時，為了節(jié)約存儲空間，宜

采取次序表作為存儲結構；當線性表的長度

變化較大，難以估量其存儲規(guī)模時，以采取

鏈表作為存儲結構為好。若線性表的操作重

要是進行查找，極少做插入和刪除操作時，

采取次序表做存儲結構為宜；對于頻繁進行

插入和刪除的線性表，宜采取鏈表做存儲結

構。

例：有關線性表的描述中，錯誤的是()

A、線性表是線性結構B、線性表的次

序存儲結構，必須占用一片連續(xù)的存儲單元

C、線性表是單鏈表D、線性表的鏈式

存儲結構，無須占用一片連續(xù)的存儲單元

用數組表示線性表的優(yōu)點是()

A、便于插入和刪除操作B、便

于隨機存取

C、能夠動態(tài)地分派存儲空間D、不

需要占用一片連續(xù)的存儲空間

三、棧:

。棧(Stack)：是限制僅在表的一端進行插

入和刪除運算的線性表，一般稱插入、刪

除的這一端為棧頂(Top),另一端稱為棧

底(Bottom)。當表中沒有元素時稱為空

棧。是一個后進先出的線性表，又稱為

LIFO表。

?:?棧的基本運算有：

棧的初始化、判?？?、判棧滿、進棧、出

棧等

?:?棧的存儲：

次序存儲、鏈式存儲

例：若進棧的輸入序列是A、B、C、D、E,

并且在它們進棧的過程中能夠進行出棧操

作，則不也許出現的出棧序列是（）

A、EDCBAB、DECBAC、

DCEABD、ABCDE

四、隊列:

?:?隊列（Queue）：也是一個運算受限的線性

表，它只允許在表的一端進行插入，而在

另一端進行刪除。允許刪除的一段稱為隊

頭（Front）,允許插入的一段稱為隊）

（Rear）o（類似于生活中的購物排隊）。是

一個先進先出的線性表，又稱為FIFO表o

?:?隊列的基本運算：

隊列的初始化、判隊空、判隊滿、入隊、

出隊

?:?隊列的存儲實現:

次序存儲、鏈式存儲

例：一個隊列的入隊序列是1,2,3,4,

則隊列的輸出序列是()

A、4,3,2,1B、1,2,3,4

C、1,4,3,2D、3,2,4,1

五、串:

?:?串(String)：是零個或多個字符組成的有

限序列。

串中所包括的字符個數稱為該串的長度。

串中任意個連續(xù)字符組成的子序列稱為

該串的子串，包括子串的串對應地稱為主串

注：空串是任意串的子串，任意串是其自

身的子串

串有串常量、串變量之分:

1、串常量在程序中只能被引用但不能變

化其值,即只能讀不能寫。

2、串變量其值是能夠變化的。

?:?串的基本運算：

求串長、串復制、串聯接、串比較、字符

定位、

力、樹(非線性結構):

?:?樹(Tree)：是n(n>=0)個結點的有限集T,

T(n=O)為空時稱為空樹，否則它滿足如下

兩個條件：

1、有且僅有一個特定的稱為根(Root)的

結點

2、其他的結點可分為m(m>=0)個互不相交

的子集H,T2,…….，Tm,其中每個

子集自身又是一棵樹，并稱其為根的子

樹(Subtree)o

?:?在樹的樹形圖表示中，結點一般是用圓圈

表示的，結點的名字一般是寫在圓圈旁

邊，有時亦可寫在圓圈內。

?:?度(Degree)：一個結點擁有的子樹數稱為

該結點的度。一棵樹的度是指該樹中結點

三J

?葉子(Leaf)：度為零的結點稱為葉子或終

端結點

?:?分支結點(Node)：度不為零的結點稱為分

支結點。

?:?樹中某個結點的子樹之根稱為該結點的

孩子(Child)結點或子結點，對應的該結

點稱為孩子結點的雙親(Parents)結點或

父結點。

?:?同一個雙親的孩子稱為弟兄結點

(Sibling)

。結點的層數(Level)是從根起算，設根的

層數為1,其他結點的層數等于其雙親結

點的層數加1.

?:?樹中結點的最大層數稱為樹的高度

(Height)或深度(Depth).

?森林(Forest)：是m(m>=0)棵互不相交的

樹的集合。刪去一棵樹的根，就得到一個

森林，反之，加上一個結點作樹根，森林

就變?yōu)橐豢脴洹?/p>

?:?二叉樹(BinaryTree)：是n(n>=0)個結點

的有限集，它或者是空集(n=0),或者由

一個根結點及兩棵互不相交的、分別稱作

這個根的左子樹和右子樹的二叉樹組成。

二叉樹中，每個結點最多只能有兩棵子

樹，并且有左右之分。

?:?二叉樹的五種基本形態(tài)：

例：具備3個結點的二叉樹有幾個形態(tài)。

?:?滿二叉樹(FullBinaryTree)：一棵深度

為k且有2k-l個結點的二叉樹稱為滿二叉

樹

。完全二叉樹(CompleteBinaryTree)：若

一棵二叉樹至多只有最下面的兩層上結

點的度數能夠小于2,并且最下一層上的

結點都集中在該層最左邊的若干位置上,

則此二叉樹稱為完全二叉樹。

二叉樹的性質:

性質1：二叉樹第i層上的結點數目最多為

2%>=1)

性質2：深度為k的二叉樹至多有2k-l個結

點(k>=l)

性質3：在任意一棵二叉樹中，若終端結點

的個數為n。,度為2的結點數為n2,則n0=n2+l

性質4：具備n個結點的完全二叉樹的深度

為[lgn]+l(取下整)或[lg(n+l)](取上

整)。

例：一棵二叉樹的結點數為18個，求它的

=1

已知度為2的結點數為15個，求葉子結

點數

二叉樹的遍歷:

?:?遍歷(Traversal)：是指沿著某條搜索路

線，依次對樹中每個結點均做一次且僅做

一次訪問。

前序遍歷：(又稱為先序遍歷、先根遍歷)

若二叉樹為空，則執(zhí)行空操作。否則：

1、訪問根結點；

2、前序遍歷左子樹；

3、前序遍歷右子樹。

中序遍歷：（又稱為中根遍歷）

若二叉樹為空，則執(zhí)行空操作。否則:

1、中序遍歷左子樹;

2、訪問根結點；

3、中序遍歷右子樹。

后序遍歷：（又稱為后根遍歷）

若二叉樹為空，則執(zhí)行空操作。否則:

1、后序遍歷左子樹；

2、后序遍歷右子樹;

3、訪問根結點。

例：已知一棵二叉樹的中序遍歷序列是:

FDGBACHE,其后序遍歷序列是：FGDBHECA

求其前序遍歷序列。

一棵二叉樹的前序遍歷序列為ABDGCFK,

中序遍歷序列為DGBAFCK,則結點的后序遍

歷序列是（）

A、ACFKDBGB、GDBFKCAC、

KCFAGDBD、ABCDFKG

七、排序(Sort)：

?:?所謂排序，就是指整頓文獻中的統計，使

之按核心字遞增(或遞減)次序排列起來。

?冒泡排序(BubbleSorting)：

通過看待排序序列從后向前或從前向后

(從下標較大的元素開始)，依次比較相鄰元

素的排序碼，若發(fā)覺逆序則互換，使排序碼

較大的元素逐漸從前部移向后部或較小的

元素逐漸從后部移向前部(從下標較大的單

元移向下標較小的單元)。

?:?直接選擇排序(SelectionSorting)：

掃描整個線性表，從中選出最小的元素,

將它互換到表的最前面；然后對剩余的子表

采取同樣的措施，直到子表空為止。

?:?直接插入排序(InsertionSorting)：

每次將一個待排序的統計，按其核心字大

小插入到前面已經排好序的子文獻中的適

當位置，直到所有統計插入完成為止。

?:?迅速排序(QuickSorting)：任取待排序

序列中的某個元素作為基準（一般取第一

個元素），通過一趟排序，將待排元素分

為左右兩個子序列，左子序列元素的排序

碼均小于或等于基準元素的排序碼，右子

序列的排序碼則不小于基準元素的排序

碼，然后分別對兩個子序列繼續(xù)進行排

泡

快

O(nlgn)O(nlgn)0(n2)O(lgn)

速

堆O(nlgn)O(nlgn)O(nlgn)0(1)

例：對一個具備n個元素的序列進行冒泡排

序，在最壞情況下，要進行互換的次數是

()

A、n(n+l)/2B、n(n-l)/2C、

n*n/2D、n(n+l)/2-l

對n個元素進行冒泡排序過程中，最佳情

況下的時間復雜性為()

2

A、0⑴B>0(log2n)C>O(n)

D、0(n)

對n個元素進行迅速排序的過程中，平均

情況下的時間復雜性為()

A、0(1)B、0(lgn)C、

0(n2)D、O(nlgn)

兒查找(Searching)：

?:?所謂查找是指給定一個值K,在含有n個

結點的表中找出核心字等于給定值K的結

點。若找到，則查找成功，返回該結點的

信息或該結點在表中的位置；否則查找失

敗，返回有關的提示信息。

?:?次序查找(SequentialSearch)的基本思

想是：從表的一端開始，次序掃描線性表,

依次將掃描到的結點核心字和給定值K相

比較，若目前掃描到的結點核心字與K相

等，則查找成功；若掃描結束后，仍未找

到核心字等于K的結點，則查找失敗。次

序查找即合用次序存儲結構，又合用鏈式

存儲結構。

查找成功的平均查找長度為：(n為結點數

目)

(1+2+3+4+???+n)/n=(n+l)/2

?:?二分查找(BinarySearch)又稱折半查找,

它是一個效率較高的查找措施，二分查找

要求線性表是有序表，即表中結點按核心

字有序，并且要用向量作為表的存儲結

構。另外，二分查找只合用次序存儲結構,

在鏈式存儲結構上無法實現二分查找。

查找成功時的平均查找長度：(n為結點數

目)

手如+DT

當n很大時,可用近似公式：1g(n+1)-1

表示

軟件工程基礎

一、基本概念:

?:?軟件(Software)：軟件是一個產品(邏輯

產品)，指的是計算機中程序及其闡明程

序的各種文檔?！俺绦颉笔怯嬎闳蝿盏奶?/p>

理對象和處理規(guī)則的描述；“文檔”是有

關計算機程序功效、設計、編制、使用的

文字或圖形資料。

?:?軟件危機的體現：

1、軟件需求的增加得不到滿足

2、軟件開發(fā)成本和進度無法控制

3、軟件質量難以確保

4、軟件不可維護或維護程度非常低

5、軟件成本不停提升

6、軟件開發(fā)生產效率的提升趕不上硬件

的發(fā)展和應用需求的增加

?:?軟件工程(SoftwareEngineering)：用工

程化的措施、科學知識和技術原理來定

義、開發(fā)、維護軟件的一門學科。

。軟件工程的目標：

付出較低的開發(fā)成本；達成要求的軟件功

效；取得很好的軟件性能；開發(fā)的軟件易

于移植；需要較低的維護費用；能按時完

成開發(fā)任務，及時交付使用；開發(fā)的軟件

可靠性高。

?:?軟件工程研究的重要內容是軟件開發(fā)技

術和軟件開發(fā)管理兩個方面。

?:?軟件生存周期：是指一個軟件從提出開發(fā)

要求開始直到該軟件報廢(停止運行)為

止的整個時期。

?:?軟件生存周期模型：是描述軟件開發(fā)過程

中各種活動怎樣執(zhí)行的模型。

?:?常用的模型有：瀑布模型、增量模型、螺

旋模型、噴泉模型、變換模型和基于知識

的模型

瀑布模型是將軟件生存周期各個活動要求

為依線性次序連接的若干階段的模型。重要

包括問題定義及可行性分析、項目開發(fā)計

劃、需求分析、概要設計、詳細設計、編碼、

測試和維護幾個階段。

例：下列描述中正確的是()

A、程序就是軟件B、軟件開發(fā)

不受計算機系統的限制

C、軟件既是邏輯實體，又是物理實體

D、軟件是程序、數據與有關文

檔的集合

二、軟件可行性研究與項目開發(fā)計劃:

?:?軟件可行性研究的目標是用最小的代價

在盡也許短的時間內確定該軟件項目是

否能夠開發(fā)，是否值得去開發(fā)。

?:?可行性研究的任務：

A、技術可行性

B、經濟可行性

C、社會可行性（法律可行性）

?？尚行匝芯康脑敿毑襟E：

1、確定項目規(guī)模和目標

2、研究正在運行的系統

3、建立新系統的高層邏輯模型

4、導出和評價各種方案

5、推薦可行的方案

6、編寫可行性研究報告

三、軟件需求分析:

?:?需求分析是指開發(fā)人員要準確了解用戶

的要求，進行細致的調查分析，將用戶非

形式的需求陳述轉化為完整的需求定義,

再由需求定義轉換到對應的形式功效規(guī)

約（需求規(guī)格闡明）的過程。

?:?需求分析的基本任務：

1、問題識別

A、功效需求

B、性能需求

C、環(huán)境需求

D、用戶界面需求

2、分析與綜合，導出軟件的邏輯模型

3、編寫文檔(需求規(guī)格闡明書)

?:?需求分析的措施：

1、結構化分析(StructuredAnalysis)：是

面對數據流進行需求分析的措施。

SA措施利用圖形等半形式化的描述方式

體現需求，重要描述工具：

A、數據流圖(DFD)：是SA措施中用于表示

系統邏輯模型的一個工具，以圖形的方式描

繪數據在系統中流動和處理的過程。

B、數據字典(DD)：用以定義數據流圖中的

各個成份的詳細含義，為系統的分析、設計

及維護提供了有關元素的一致的定義和詳

細的描述。

C、描述加工邏輯的結構化語言、判定表、

判定樹

2、IDEF措施（是ICAMDefinition的縮寫）：

是一個用于進行復雜系統分析和設計的

措施，是在結構化分析和設計技術的基礎上

提出來的。

3、面對對象分析措施（OOP）：

將客觀世界的事物抽象為對象，通過屬性

和措施描述對象的狀態(tài)和行為，具備繼承、

封裝和多態(tài)性等特性。

例：軟件開發(fā)的結構化分析措施中，常用的

描述軟件功效需求的工具是（）

A、業(yè)務流程圖、處理闡明B、

軟件流程圖、模塊闡明

C、數據流程圖、數據字典D、

系統流程圖、程序編碼

四、軟件概要設計:

將軟件需求轉換為軟件表示的過程。

軟件概要設計的基本任務：

1、設計軟件系統結構

2、數據結構及數據庫設計（概要設計、

邏輯設計、物理設計）:

3、編寫概要設計文檔:

4、評審:

?:?軟件設計的措施:

模塊化：模塊在程序中是數據闡明、可執(zhí)

行語句等程序對象的集合，或者是單獨命名

和編址的元素，如高級語言中的過程、函數、

子程序等。

?:?模塊獨立性指每個模塊只完成系統要求

的獨立的子功效，并且與其他模塊的聯系

最少且接口簡單。其度量標準是：耦合性

和內聚性

。耦合性也稱塊間聯系，指軟件系統結構中

各模塊間相互聯系緊密程度的一個度量。

模塊之間聯系越緊密，其耦合性就越強，

模塊的獨立性則越差。

?:?內聚性也稱塊內聯系，指模塊功效強度的

度量，即一個模塊內部各個元素（語句之

間、程序段之間）彼此結合的緊密程度的

度量。

?:?將軟件系統劃分模塊時，盡也許做到高內

聚低耦合。

例：為了使模塊盡也許獨立，要求（）

A、模塊的內聚程序要盡也許高，且各模塊

間的耦合程序要盡也許強

B、模塊的內聚程序要盡也許高，且各模塊

間的耦合程序要盡也許弱

C、模塊的內聚程序要盡也許低，且各模塊

間的耦合程序要盡也許弱

D、模塊的內聚程序要盡也許低，且各模塊

間的耦合程序要盡也許強

五、軟件詳細設計:

重要確定每個模塊詳細執(zhí)行過程

?:?軟件詳細設計的基本任務：

1、為每個模塊進行詳細的算法設計:

2、為模塊內的數據結構進行設計：

3、對數據庫進行物理設計：

4、輸入、輸出格式設計

5、編寫詳細設計闡明書：

6、評審：

?:?詳細設計常用三種工具：

圖形（流程圖、盒圖、問題分析圖PAD）、

表格（判定表）、

語言（過程設計語言，又稱為偽碼）

力、軟件編碼:

重要是將詳細設計得到的處理過程描述

轉換為基于某種計算機語言的程序

常用的計算機語言：

Pascal、C>C++、Java等

七、軟件測試:

軟件測試代表了需求分析、設計、編碼的

后復審。軟件測試貫通于軟件開發(fā)的全過

程。

?:?軟件測試的目標:

1、軟件測試是為了盡也許多地發(fā)覺程序

中的錯誤而執(zhí)行程序的過程。

2、一個好的測試用例能夠發(fā)覺至今尚未

發(fā)覺的錯誤。

3、一個成功的測試是發(fā)覺了至今尚未發(fā)

覺的錯誤的測試。

。軟件測試的標準：

1、測試用例應由輸入數據和預期的輸出

數據兩部分組成。

2、測試用例不但選用合理的輸入數據，

還要選擇不合理的輸入數據

3、除了檢查程序是否做了它應當做的事

4、應制定測試計劃并嚴格執(zhí)行，排除隨

意性

5、長期保存測試用例

6、對發(fā)覺錯誤較多的程序段，應進行更

深入的測試

7、程序員防止測試自己的程序

?:?軟件測試措施:

1、靜態(tài)測試：

是指被測試程序不在機器上運行，而是

采取人工檢測和計算機輔助靜態(tài)分析的伎

倆對程序進行檢測。

2、動態(tài)測試：是指通過運行程序發(fā)覺錯

誤

A、黑盒測試法（功效測試）:

重要對軟件的接口進行測試，依據需求規(guī)

格闡明書，檢查程序是否滿足功效要求。常

用的技術是等價類劃分法、邊界值分析法、

錯誤推測法、因果圖法、綜合方略法

B、白盒測試法（結構測試）：

重要測試程序的內部結構和處理過程。常

用的技術是語句覆蓋、條件覆蓋、途徑覆蓋、

判定覆蓋等

?:?軟件測試的實行：

1、單元測試：

單元測試是對軟件設計的最小單位一一

模塊（程序單元）進行正確性檢查測試，重要

針對模塊的如下五個基本特性進行測試：

A、模塊接口

B、局部數據結構：

C、重要的執(zhí)行途徑：

D、錯誤處理測試：

E、邊界條件：

2、集成測試：

集成測試是指在單元測試的基礎上，將所

有模塊按照設計要求組裝成一個完整的系

統進行的測試，故也稱組裝測試或聯合測

試。

重要措施有兩種：

非漸增式測試：首先對每個模塊分別進行

單元測試，然后再把所有的模塊按設計要求

組裝在一起進行測試。

漸增式測試：逐一把未通過測試的模塊組

裝到已通過測試的模塊上去，進行集成測

試，每加入一個新模塊進行一次集成測試，

重復此過程直至程序組裝完成。

3、確認測試：

確認測試又稱有效性測試，它的任務是檢

查軟件的功效與性能是否與需求規(guī)格闡明

書中確定的指標相符合，因而需求規(guī)格闡明

是確認測試的基礎。

4、系統測試：

系統測試是通過測試確認的軟件作為整

個計算機系統的一個元素，與計算機硬件、

外設、支撐軟件、數據和人員等其他系統元

素組合在一起，在實際運行環(huán)境下對計算機

系統進行一系列的集成測試和確認測試。

?:?程序調試：

調試是在進行了成功的測試之后才開始

的工作，目標是確定錯誤的原因和位置，

并更正錯誤，又稱為糾錯。

例：軟件測試的目標是（）

A、證明軟件的正確性

B、找出軟件系統中存在的所有錯誤

C、盡也許多地發(fā)覺軟件系統中的錯誤

D、證明軟件系統中存在錯誤

在軟件測試措施中，黑箱測試法和白箱測

試法是常用的措施，其中黑箱測

試法重要是

用于測試（）

A、結構合理性B、軟件外部功效

C、程序正確性D、程序內部

邏輯

軟件維護:

軟件投入使用后進行的階段，是軟件生

存周期中時間最長的一個階段，所花費的精

力和費用也是最多的一個階段。重要是因

為：隱含的錯誤要修改；新增的功效要加入

進去；環(huán)境的變化對程序進行變動等。

?:?軟件維護的內容有四類：

1、校正性維護：

為了識別和糾正錯誤，修改軟件性能上的

缺陷，其占整個維護工作的21%

2、適應性維護：

為了使應用軟件適應環(huán)境（硬件、系統軟

件、數據）的變化而修改軟件的過程稱為適

應性維護，其占整個維護工作的25%

3、完善性維護：

增加軟件功效、增強軟件性能、提升軟件

運行效率而進行的維護活動稱為完善性維

護，其占整個維護工作的50%

4、預防性維護：

為了提升軟件的可維護性和可靠性而對

軟件進行的修改稱為預防性維護，其占整個

維護工作的4%

例：軟件維護是指（）

A、維護軟件正常運行B、軟件的配

備更新

C、對軟件的改進、適應和完善

D、軟件開發(fā)期的一個階段

軟件生命周期中所花費用最多的階段

是（）

A、詳細設計B軟件編

C、軟件測試D、軟件維護

數據庫原理基礎

一、基本概念:

?:?數據處理：是指將數據轉換成信息的過程

?:?數據管理是指對數據的組織、分類、編碼、

存儲、檢索和維護提供操作伎倆

其經歷了如下階段：

1、人工管理

2、文獻系統

3、數據庫系統

4、分布式數據庫系統階段

5、面對對象的數據庫系統階段

?:?數據庫(Database)：是指存儲在計算機存

儲設備上的結構化的有關數據的集合，不

但包括數據自身，還包括事物之間的聯

系。

?:?數據庫應用系統(DBAS)：是指系統開發(fā)人

員利用數據庫系統資源開發(fā)出來的，面對

某一類實際應用的應用軟件系統。

?:?數據庫管理系統(DBMS)：對數據庫的建

立、使用和維護進行管理和配備的軟件系

統。是數據庫系統的核心

?:?數據庫系統(DBS):由硬件系統、數據庫集

合、數據庫管理系統及有關軟件、數據庫

管理員和用戶組成。

?:?數據庫系統的特點：

實現數據共享、減少數據冗余

采取特定的數據模型

具備較高的數據獨立性

統一的數據控制功效

。實體：客觀存在并且能夠相互區(qū)分的事

物稱為實體。

?:?實體的屬性：實體所具備的物性稱為實體

的屬性。

?:?實體集：同類型的實體的集合稱為實體

集。

?:?實體型：屬性的集合表示一個實體類型，

稱為實體型。

例：數據庫管理系統能實現對數據庫中數據

的查詢、插入、修改和刪除，此類功效稱為

()

A、數據定義功效B、數據管理功效

C、數據操縱功效D、數據控制功效

?:?聯系：實體之間的對應關系。

聯系的類型：

1、一對一聯系：體現為主表中的每一條

統計只與有關表中的一條統計有關聯。

例如：班級與班長，學校與校長

2、一對多聯系：