數(shù)據結構與算法

一、基本概念

 數(shù)據(Data)：信息的載體,，能夠被計算機識別,、存儲和加工處理的物理符號。包括文本類型的數(shù)據(如：字母,、數(shù)字,、漢字)和多媒體類型的數(shù)據(如：聲音、動畫,、圖像),。

數(shù)據結構（Data Structure）：指的是數(shù)據之間的相互關系，即數(shù)據的組織形式,。其包括三個部分：

1,、邏輯結構：數(shù)據元素之間的邏輯關系2、存儲結構：數(shù)據元素及其關系在計算機存儲器內的表示,。

3,、數(shù)據的運算（算法）：即對數(shù)據施加的操作

數(shù)據的邏輯結構有兩大類：

1、線性結構：

特征是：若結構是非空集,，則有且僅有一個開始結點和一個終端結點,，并且所有結點最多只有一個直接前趨和一個直接后繼。例：一維數(shù)組,、鏈表,、棧、隊列,、串

2,、非線性結構：特征是：一個結點可能有多個直接前趨和直接后繼。

例：多維數(shù)組,、廣義表,、樹、圖

 數(shù)據的存儲結構有以下基本存儲方法：

1,、順序存儲方法：該方法是將邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里,，結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)，一般通過數(shù)組來實現(xiàn)的,。

2,、鏈接存儲方法：該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰,，結點間的邏輯關系是由附加的指針字段表示的。通過指針類型來實現(xiàn)的,。

3,、索引存儲方法：該方法通常是在存儲結點信息的同時，還建立附加的索引表,，索引表中的每一項稱為索引項,，索引項的一般形式是：關鍵字，地址,。

4,、散列存儲方法：該方法的基本思想是根據結點的關鍵字直接計算出該結點的存儲地址，通過散列函數(shù)實現(xiàn),。例：除余法散列函數(shù),、相乘取整法散列函數(shù)

 算法的基本特征：

1、可行性(Effectiveness)：針對實際問題而設計的算法,，執(zhí)行后能夠得到滿意的結果,。

2、確定性(Definiteness)：算法中的每一個步驟都必須有明確的定義,，不允許出現(xiàn)歧義性,。

3、有窮性(Finiteness)：算法必須在有限時間內做完,，即必須在執(zhí)行有限個步驟之后終止,。

 時間復雜度：該算法執(zhí)行的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù),。

 空間復雜度：該算法執(zhí)行時所耗費的存儲空間,，它也是問題規(guī)模n的函數(shù)。

二,、線性表：

 線性表(Linear List)：是由n(n>=0)個數(shù)據元素(結點)a1,a2,a3,······,an組成的有限序列,。對于非空的線性表，有且僅有一個開始結點a1,，它沒有直接前趨,；有且僅有一個終端結點an，它沒有直接后繼,；其余的結點有且僅有一個直接前趨結點和一個直接后繼結點,。

 線性表的存儲結構：

1、順序存儲(Sequential List)：將線性表的結點按邏輯次序依次存放在一組地址連續(xù)的存儲單元里,，用這種方法存儲的線性表稱為順序表,。

2、鏈式存儲(Linked List)：邏輯上相鄰的結點，物理上也相鄰,，存儲單元可以是連續(xù)的,，也可以是不連續(xù)的,，在存儲每個結點值的同時,，還存儲指向其后繼結點的地址，用這種方法存儲的線性表稱為鏈表,。

常見的運算有：

表的初始化,、求表的長度、取表中的第i個結點,、查找結點,、插入新的結點、刪除結點,。

順序表和鏈表的比較：

1,、基于空間的考慮：

A、順序表的存儲空間是靜態(tài)分配的,，而鏈表的存儲空間是動態(tài)分配的,。

B、順序表占的存儲空間必須是連續(xù)的,，而鏈表占的存儲空間可以是連續(xù)的,，也可是不連續(xù)的

C、順序表存儲密度為1,，而鏈表中的每個結點,，除了數(shù)據域外，還要額外的設置指針域,，存儲密度小于1

2,、基于時間的考慮：

A、在鏈表中的任何位置上進行插入和刪除,，只需要修改指針,，而順序表中平均將要移動近一半的結點。

B,、順序表是隨機存取結構,，它的存取時間為O(1)，而鏈表需從頭結點順著鏈掃描鏈表,。

   總之,，當線性表的長度變化不大，易于事先確定其大小時,，為了節(jié)約存儲空間,，宜采用順序表作為存儲結構；當線性表的長度變化較大,，難以估計其存儲規(guī)模時,，以采用鏈表作為存儲結構為好,。若線性表的操作主要是進行查找，很少做插入和刪除操作時,，采用順序表做存儲結構為宜,；對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲結構,。

例：關于線性表的描述中,，錯誤的是（   ）

A、線性表是線性結構  B,、線性表的順序存儲結構,，必須占用一片連續(xù)的存儲單元

C、線性表是單鏈表    D,、線性表的鏈式存儲結構,，不必占用一片連續(xù)的存儲單元

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

A、便于插入和刪除操作  B,、便于隨機存取C,、可以動態(tài)地分配存儲空間    D、不需要占用一片連續(xù)的存儲空間

三,、棧：棧(Stack)：是限制僅在表的一端進行插入和刪除運算的線性表,，通常稱插入、刪除的這一端為棧頂(Top),，另一端稱為棧底(Bottom),。當表中沒有元素時稱為空棧。是一種后進先出的線性表,，又稱為LIFO表,。

棧的基本運算有：棧的初始化、判?？?、判棧滿、進棧,、出棧等

 棧的存儲：順序存儲,、鏈式存儲

例：若進棧的輸入序列是A、B,、C,、D、E,，并且在它們進棧的過程中可以進行出棧操作,，則不可能出現(xiàn)的出棧序列是（   ）A、EDCBA        B、DECBA         C,、DCEAB        D,、ABCDE

四、隊列：

 隊列(Queue)：也是一種運算受限的線性表,，它只允許在表的一端進行插入,，而在另一端進行刪除。允許刪除的一段稱為隊頭(Front),，允許插入的一段稱為隊尾(Rear),。（類似于生活中的購物排隊）,。是一種先進先出的線性表,，又稱為FIFO表。

 隊列的基本運算：隊列的初始化,、判隊空,、判隊滿、入隊,、出隊

 隊列的存儲實現(xiàn)：順序存儲,、鏈式存儲

例：一個隊列的入隊序列是1，2,，3,，4，則隊列的輸出序列是 （   ）

A,、4,，3，2,，1     B,、1，2,，3,，4     C、1,，4,，3，2     D,、3,，2，4,，1

五,、串：串(String)：是零個或多個字符組成的有限序列。串中所包含的字符個數(shù)稱為該串的長度。

串中任意個連續(xù)字符組成的子序列稱為該串的子串,，包含子串的串相應地稱為主串

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

 串有串常量、串變量之分： 1,、串常量在程序中只能被引用但不能改變其值,，即只能讀不能寫。

2,、串變量其值是可以改變的,。

 串的基本運算：求串長、串復制,、串聯(lián)接,、串比較、字符定位,、

六,、樹（非線性結構樹(Tree)：是n(n>=0)個結點的有限集T，T(n=0)為空時稱為空樹,，否則它滿足如下兩個條件：

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

2、其余的結點可分為m(m>=0)個互不相交的子集T1,，T2,，…….，Tm,，其中每個子集本身又是一棵樹,，并稱其為根的子樹(Subtree)。

 在樹的樹形圖表示中,，結點通常是用圓圈表示的,，結點的名字一般是寫在圓圈旁邊，有時亦可寫在圓圈內,。

 度(Degree)：一個結點擁有的子樹數(shù)稱為該結點的度,。一棵樹的度是指該樹中結點的最大度數(shù)。

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

 分支結點(Node)：度不為零的結點稱為分支結點,。

樹中某個結點的子樹之根稱為該結點的孩子(Child)結點或子結點,，相應的該結點稱為孩子結點的雙親(Parents)結點或父結點。

 同一個雙親的孩子稱為兄弟結點(Sibling)

結點的層數(shù)(Level)是從根起算,設根的層數(shù)為1,其余結點的層數(shù)等于其雙親結點的層數(shù)加1.

 樹中結點的最大層數(shù)稱為樹的高度(Height)或深度(Depth).

森林(Forest)：是m(m>=0)棵互不相交的樹的集合,。刪去一棵樹的根,，就得到一個森林，反之,，加上一個結點作樹根,，森林就變?yōu)橐豢脴洹?/p>

二叉樹(Binary Tree)：是n(n>=0)個結點的有限集,，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的,、分別稱作這個根的左子樹和右子樹的二叉樹組成,。

二叉樹中，每個結點最多只能有兩棵子樹,，并且有左右之分,。

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

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

 滿二叉樹(Full Binary Tree)：一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹

完全二叉樹(Complete Binary Tree)：若一棵二叉樹至多只有最下面的兩層上結點的度數(shù)可以小于2,，并且最下一層上的結點都集中在該層最左邊的若干位置上,，則此二叉樹稱為完全二叉樹。

二叉樹的性質：性質1：二叉樹第i層上的結點數(shù)目最多為2i-1(i>=1)

性質2：深度為k的二叉樹至多有2k-1個結點(k>=1)性質3：在任意一棵二叉樹中,，若終端結點的個數(shù)為n0,，度為2的結點數(shù)為n2，則n0=n2+1性質4：具有n個結點的完全二叉樹的深度為[lgn]+1(取下整) 或 [lg(n+1)](取上整),。

例：一棵二叉樹的結點數(shù)為18個,，求它的最小高度  已知度為2的結點數(shù)為15個,，求葉子結點數(shù)

二叉樹的遍歷：

遍歷(Traversal)：是指沿著某條搜索路線,，依次對樹中每個結點均做一次且僅做一次訪問。

前序遍歷：（又稱為先序遍歷,、先根遍歷）

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

1,、訪問根結點,； 2、前序遍歷左子樹,； 3,、前序遍歷右子樹。中序遍歷：（又稱為中根遍歷）若二叉樹為空,，則執(zhí)行空操作,。否則： 1、中序遍歷左子樹,； 2,、訪問根結點； 3,、中序遍歷右子樹,。后序遍歷：（又稱為后根遍歷）

若二叉樹為空，則執(zhí)行空操作,。否則： 1,、后序遍歷左子樹,； 2、后序遍歷右子樹,； 3,、訪問根結點。

例：已知一棵二叉樹的中序遍歷序列是：FDGBACHE,，其后序遍歷序列是：FGDBHECA 

求其前序遍歷序列,。一棵二叉樹的前序遍歷序列為ABDGCFK，中序遍歷序列為DGBAFCK,，則結點的后序遍歷序列是（   ）A,、ACFKDBG      B、GDBFKCA       C,、KCFAGDB      D,、ABCDFKG

七、排序(Sort)：

 冒泡排序(Bubble Sorting)：

通過對待排序序列從后向前或從前向后(從下標較大的元素開始),，依次比較相鄰元素的排序碼,，若發(fā)現(xiàn)逆序則交換，使排序碼較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部（從下標較大的單元移向下標較小的單元）,。

直接選擇排序(Selection Sorting)：

掃描整個線性表,，從中選出最小的元素，將它交換到表的最前面,；然后對剩下的子表采用同樣的方法,，直到子表空為止。

 直接插入排序(Insertion Sorting)：

每次將一個待排序的記錄,，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置,，直到全部記錄插入完成為止。

 快速排序(Quick Sorting)：任取待排序序列中的某個元素作為基準(一般取第一個元素),，通過一趟排序,，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼,，右子序列的排序碼則大于基準元素的排序碼,，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序,。

各種內部排序方法的比較

例：對一個具有n個元素的序列進行冒泡排序,，在最壞情況下，要進行交換的次數(shù)是（  ）

A,、n(n+1)/2    B,、n(n-1)/2      C、n*n/2       D,、n(n+1)/2-1

對n個元素進行冒泡排序過程中,，最好情況下的時間復雜性為（   ）A,、O(1) B、O(log2n) C,、O(n2) D,、O(n)

對n個元素進行快速排序的過程中，平均情況下的時間復雜性為（   ）A,、O(1) B,、O(lgn) C、O(n2) D,、O(nlgn)

八,、查找(Searching)：

v 所謂查找是指給定一個值K，在含有n個結點的表中找出關鍵字等于給定值K的結點,。若找到,，則查找成功，返回該結點的信息或該結點在表中的位置,；否則查找失敗,，返回相關的提示信息。

v 順序查找(Sequential Search)的基本思想是：從表的一端開始,，順序掃描線性表,，依次將掃描到的結點關鍵字和給定值K相比較，若當前掃描到的結點關鍵字與K相等,，則查找成功,；若掃描結束后，仍未找到關鍵字等于K的結點,，則查找失敗。順序查找即適用順序存儲結構,，又適用鏈式存儲結構,。

查找成功的平均查找長度為：(n為結點數(shù)目) (1+2+3+4+···+n) / n = (n+1)/2

v 二分查找(Binary Search)又稱折半查找，它是一種效率較高的查找方法,，二分查找要求線性表是有序表,，即表中結點按關鍵字有序，并且要用向量作為表的存儲結構,。另外,，二分查找只適用順序存儲結構，在鏈式存儲結構上無法實現(xiàn)二分查找,。

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

當n很大時,，可用近似公式：   lg(n+1)-1     表示

軟件工程基礎

一、基本概念：

v 軟件(Software)：軟件是一種產品(邏輯產品),，指的是計算機中程序及其說明程序的各種文檔,。“程序”是計算任務的處理對象和處理規(guī)則的描述,；“文檔”是有關計算機程序功能、設計,、編制,、使用的文字或圖形資料。

v 軟件危機的表現(xiàn)： 1,、軟件需求的增長得不到滿足2,、軟件開發(fā)成本和進度無法控制3、軟件質量難以保證

4,、軟件不可維護或維護程度非常低5,、軟件成本不斷提高6、軟件開發(fā)生產效率的提高趕不上硬件的發(fā)展和應用需求的增長

v 軟件工程(Software Engineering)：用工程化的方法,、科學知識和技術原理來定義,、開發(fā)、維護軟件的一門學科,。

v 軟件工程的目標：付出較低的開發(fā)成本,；達到要求的軟件功能；取得較好的軟件性能,；開發(fā)的軟件易于移植,；需要較低的維護費用；能按時完成開發(fā)任務,，及時交付使用,；開發(fā)的軟件可靠性高。

v 軟件工程研究的主要內容是軟件開發(fā)技術和軟件開發(fā)管理兩個方面,。

v 軟件生存周期：是指一個軟件從提出開發(fā)要求開始直到該軟件報廢(停止運行)為止的整個時期,。

v 軟件生存周期模型：是描述軟件開發(fā)過程中各種活動如何執(zhí)行的模型。

v 常用的模型有：瀑布模型,、增量模型,、螺旋模型、噴泉模型,、變換模型和基于知識的模型

瀑布模型是將軟件生存周期各個活動規(guī)定為依線性順序連接的若干階段的模型,。主要包括問題定義及可行性分析、項目開發(fā)計劃,、需求分析,、概要設計、詳細設計,、編碼,、測試和維護幾個階段。

例：下列描述中正確的是（  ） A,、程序就是軟件 B,、軟件開發(fā)不受計算機系統(tǒng)的限制

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

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

v 軟件可行性研究的目的是用最小的代價在盡可能短的時間內確定該軟件項目是否能夠開發(fā),，是否值得去開發(fā),。

v 可行性研究的任務： A、技術可行性B,、經濟可行性C,、社會可行性（法律可行性）

v 可行性研究的具體步驟： 1、確定項目規(guī)模和目標2,、研究正在運行的系統(tǒng)3,、建立新系統(tǒng)的高層邏輯模型

4、導出和評價各種方案5,、推薦可行的方案6,、編寫可行性研究報告

三、軟件需求分析：

v 需求分析是指開發(fā)人員要準確理解用戶的要求,，進行細致的調查分析,，將用戶非形式的需求陳述轉化為完整的需求定義，再由需求定義轉換到相應的形式功能規(guī)約（需求規(guī)格說明）的過程,。

v 需求分析的基本任務：

1,、問題識別A、功能需求B,、性能需求C,、環(huán)境需求D、用戶界面需求

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

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

v 需求分析的方法：

1,、結構化分析(Structured Analysis)：是面向數(shù)據流進行需求分析的方法。

SA方法利用圖形等半形式化的描述方式表達需求,，主要描述工具：

A,、數(shù)據流圖(DFD)：是SA方法中用于表示系統(tǒng)邏輯模型的一種工具，以圖形的方式描繪數(shù)據在系統(tǒng)中流動和處理的過程,。B,、數(shù)據字典(DD)：用以定義數(shù)據流圖中的各個成分的具體含義，為系統(tǒng)的分析,、設計及維護提供了有關元素的一致的定義和詳細的描述,。C,、描述加工邏輯的結構化語言、判定表,、判定樹

2,、IDEF方法(是 ICAM Definition的縮寫)：

是一種用于進行復雜系統(tǒng)分析和設計的方法，是在結構化分析和設計技術的基礎上提出來的,。

3,、面向對象分析方法(OOP)：

將客觀世界的事物抽象為對象，通過屬性和方法描述對象的狀態(tài)和行為,，具有繼承,、封裝和多態(tài)性等特征。

例：軟件開發(fā)的結構化分析方法中,，常用的描述軟件功能需求的工具是（   ）

A,、業(yè)務流程圖、處理說明  B,、軟件流程圖,、模塊說明C、數(shù)據流程圖,、數(shù)據字典  D,、系統(tǒng)流程圖、程序編碼

四,、軟件概要設計：將軟件需求轉換為軟件表示的過程,。

 軟件概要設計的基本任務： 1、設計軟件系統(tǒng)結構2,、數(shù)據結構及數(shù)據庫設計（概要設計,、邏輯設計、物理設計）：

3,、編寫概要設計文檔： 4,、評審：

 軟件設計的方法：

模塊化：模塊在程序中是數(shù)據說明、可執(zhí)行語句等程序對象的集合,，或者是單獨命名和編址的元素,，如高級語言中的過程、函數(shù),、子程序等,。

 模塊獨立性指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單,。其度量標準是：耦合性和內聚性

 耦合性也稱塊間聯(lián)系,，指軟件系統(tǒng)結構中各模塊間相互聯(lián)系緊密程度的一種度量。模塊之間聯(lián)系越緊密，其耦合性就越強,，模塊的獨立性則越差,。

 內聚性也稱塊內聯(lián)系，指模塊功能強度的度量,，即一個模塊內部各個元素(語句之間,、程序段之間)彼此結合的緊密程度的度量。

 將軟件系統(tǒng)劃分模塊時,，盡量做到高內聚低耦合,。

例：為了使模塊盡可能獨立，要求（  ）

A,、模塊的內聚程序要盡量高,，且各模塊間的耦合程序要盡量強

B、模塊的內聚程序要盡量高,，且各模塊間的耦合程序要盡量弱

C,、模塊的內聚程序要盡量低，且各模塊間的耦合程序要盡量弱

D,、模塊的內聚程序要盡量低,，且各模塊間的耦合程序要盡量強

五、軟件詳細設計：主要確定每個模塊具體執(zhí)行過程

 軟件詳細設計的基本任務： 1,、為每個模塊進行詳細的算法設計： 2,、為模塊內的數(shù)據結構進行設計：

3、對數(shù)據庫進行物理設計： 4,、輸入,、輸出格式設計5、編寫詳細設計說明書： 6,、評審：

v 詳細設計常用三種工具：圖形(流程圖,、盒圖、問題分析圖PAD),、表格(判定表)語言(過程設計語言,，又稱為偽碼)

六、軟件編碼：主要是將詳細設計得到的處理過程描述轉換為基于某種計算機語言的程序

常用的計算機語言： Pascal ,、C,、C++、Java等

七,、軟件測試：軟件測試代表了需求分析,、設計、編碼的最終復審,。軟件測試貫穿于軟件開發(fā)的全過程。

軟件測試的目的： 1,、軟件測試是為了盡可能多地發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程,。

2,、一個好的測試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤。

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

軟件測試的原則： 1、測試用例應由輸入數(shù)據和預期的輸出數(shù)據兩部分組成,。

2,、測試用例不僅選用合理的輸入數(shù)據，還要選擇不合理的輸入數(shù)據3,、除了檢查程序是否做了它應該做的事

4,、應制定測試計劃并嚴格執(zhí)行，排除隨意性5,、長期保留測試用例

6,、對發(fā)現(xiàn)錯誤較多的程序段，應進行更深入的測試7,、程序員避免測試自己的程序

v 軟件測試方法：

1,、靜態(tài)測試：是指被測試程序不在機器上運行，而是采用人工檢測和計算機輔助靜態(tài)分析的手段對程序進行檢測,。

2,、動態(tài)測試：是指通過運行程序發(fā)現(xiàn)錯誤A、黑盒測試法(功能測試)：

主要對軟件的接口進行測試,，依據需求規(guī)格說明書,，檢查程序是否滿足功能要求。常用的技術是等價類劃分法,、邊界值分析法,、錯誤推測法、因果圖法,、綜合策略法

B,、白盒測試法(結構測試)：

主要測試程序的內部結構和處理過程。常用的技術是語句覆蓋,、條件覆蓋,、路徑覆蓋、判定覆蓋等

 軟件測試的實施：

1,、單元測試：

單元測試是對軟件設計的最小單位——模塊(程序單元)進行正確性檢驗測試,，主要針對模塊的以下五個基本特征進行測試： A、模塊接口B,、局部數(shù)據結構： C,、重要的執(zhí)行路徑D、錯誤處理測試： E、邊界條件： 2,、集成測試：

集成測試是指在單元測試的基礎上,，將所有模塊按照設計要求組裝成一個完整的系統(tǒng)進行的測試，故也稱組裝測試或聯(lián)合測試,。

主要方法有兩種：

非漸增式測試：首先對每個模塊分別進行單元測試,，然后再把所有的模塊按設計要求組裝在一起進行測試。

漸增式測試：逐個把未經過測試的模塊組裝到已經過測試的模塊上去,，進行集成測試,，每加入一個新模塊進行一次集成測試，重復此過程直至程序組裝完畢,。

3,、確認測試：

確認測試又稱有效性測試，它的任務是檢查軟件的功能與性能是否與需求規(guī)格說明書中確定的指標相符合,，因而需求規(guī)格說明是確認測試的基礎,。

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

系統(tǒng)測試是通過測試確認的軟件作為整個計算機系統(tǒng)的一個元素,，與計算機硬件,、外設、支撐軟件,、數(shù)據和人員等其他系統(tǒng)元素組合在一起,，在實際運行環(huán)境下對計算機系統(tǒng)進行一系列的集成測試和確認測試。

 程序調試：

調試是在進行了成功的測試之后才開始的工作,，目的是確定錯誤的原因和位置,，并改正錯誤，又稱為糾錯,。

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

A,、證明軟件的正確性                 B、找出軟件系統(tǒng)中存在的所有錯誤

C,、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯誤   D,、證明軟件系統(tǒng)中存在錯誤

在軟件測試方法中，黑箱測試法和白箱測試法是常用的方法,，其中黑箱測試法主要是

用于測試（  ） A,、結構合理性 B、軟件外部功能 C,、程序正確性 D,、程序內部邏輯

八、軟件維護：

    軟件投入使用后進行的階段,，是軟件生存周期中時間最長的一個階段,，所花費的精力和費用也是最多的一個階段,。主要是因為：隱含的錯誤要修改；新增的功能要加入進去,；環(huán)境的變化對程序進行變動等,。

 軟件維護的內容有四類：

1、校正性維護：

為了識別和糾正錯誤,，修改軟件性能上的缺陷，其占整個維護工作的 21%

2,、適應性維護：

為了使應用軟件適應環(huán)境(硬件,、系統(tǒng)軟件、數(shù)據)的變化而修改軟件的過程稱為適應性維護,，其占整個維護工作的25%

3,、完善性維護：

增加軟件功能、增強軟件性能,、提高軟件運行效率而進行的維護活動稱為完善性維護,，其占整個維護工作的 50%

4、預防性維護：

為了提高軟件的可維護性和可靠性而對軟件進行的修改稱為預防性維護,，其占整個維護工作的 4%

例：軟件維護是指（   ）

A,、維護軟件正常運行B、軟件的配置更新C,、對軟件的改進,、適應和完善 D、軟件開發(fā)期的一個階段

軟件生命周期中所花費用最多的階段是（  ）A,、詳細設計 B,、軟件編碼 C、軟件測試 D,、軟件維護

數(shù)據庫原理基礎

一,、基本概念：

 數(shù)據處理：是指將數(shù)據轉換成信息的過程

 數(shù)據管理是指對數(shù)據的組織、分類,、編碼,、存儲、檢索和維護提供操作手段

其經歷了以下階段： 1,、人工管理2,、文件系統(tǒng)3、數(shù)據庫系統(tǒng)4,、分布式數(shù)據庫系統(tǒng)階段

5,、面向對象的數(shù)據庫系統(tǒng)階段

數(shù)據庫(Database)：是指存儲在計算機存儲設備上的結構化的相關數(shù)據的集合，不僅包括數(shù)據本身,，還包括事物之間的聯(lián)系,。

  數(shù)據庫應用系統(tǒng)(DBAS)：是指系統(tǒng)開發(fā)人員利用數(shù)據庫系統(tǒng)資源開發(fā)出來的,，面向某一類實際應用的應用軟件系統(tǒng)。 

 數(shù)據庫管理系統(tǒng)(DBMS)：

數(shù)據庫的建立,、使用和維護進行管理和配置的軟件系統(tǒng),。

是數(shù)據庫系統(tǒng)的核心

 數(shù)據庫系統(tǒng)(DBS):由硬件系統(tǒng)、數(shù)據庫集合,、數(shù)據庫管理系統(tǒng)及相關軟件,、數(shù)據庫管理員和用戶組成。

 數(shù)據庫系統(tǒng)的特點：實現(xiàn)數(shù)據共享,、減少數(shù)據冗余   采用特定的數(shù)據模型

具有較高的數(shù)據獨立性    統(tǒng)一的數(shù)據控制功能

 實體： 客觀存在并且可以相互區(qū)別的事物稱為實體,。

實體的屬性：實體所具有的物性稱為實體的屬性。

實體集：同類型的實體的集合稱為實體集,。

 實體型：屬性的集合表示一種實體類型,，稱為實體型。

例：數(shù)據庫管理系統(tǒng)能實現(xiàn)對數(shù)據庫中數(shù)據的查詢,、插入,、修改和刪除，這類功能稱為（ ）

A,、數(shù)據定義功能 B,、數(shù)據管理功能 C、數(shù)據操縱功能 D,、數(shù)據控制功能

 聯(lián)系：實體之間的對應關系,。

聯(lián)系的類型:

1、一對一聯(lián)系：表現(xiàn)為主表中的每一條記錄只與相關表中的一條記錄相關聯(lián),。 

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

2、一對多聯(lián)系：表現(xiàn)為主表中的每一條記錄與相關表中的多條記錄相關聯(lián),。

例如： 班級與學生,，部門與職工

3、多對多聯(lián)系：表現(xiàn)為一個表中的多個記錄在相關表中同樣有多個記錄相關聯(lián),。

例如： 學生與課程,， 工程項目與零件 

 數(shù)據模型：不僅反映事物本身，還用來表示實體及實體之間聯(lián)系的方法,。

1,、層次模型：用樹形結構表示實體及其之間聯(lián)系的模型稱為層次模型。

2,、網狀模型：用網狀結構表示實體及其之間聯(lián)系的模型稱為網狀模型,。

3、關系模型：用二維表結構來表示實體及實體之間的聯(lián)系的模型稱為關系模型,。 

一個二維表稱為一個關系,，在VFP稱為數(shù)據表,。一個關系不僅表示實體本身還表示實體之間的聯(lián)系。

例：用樹形結構表示實體之間聯(lián)系的模型是（  ）

A,、關系模型 B,、網狀模型 C、層次模型 D,、以上三個都是

二,、關系數(shù)據庫：

元組(Record)：在一個關系中，水平方向的行稱為元組,。在VFP中稱為記錄 

v 屬性(Field)：一個二維表中垂直方向的列稱為屬性,。在VFP中稱為字段名

v 域(Domain)：屬性的取值范圍。根據數(shù)據類型和寬度來決定的,。

v 關鍵字(Primary Key)：其值能夠惟一標識一個元組的屬性或屬性的組合。

注：關鍵字不能出現(xiàn)空值或重復值

v 外部關鍵字(Foreign Key)：如果表中的一個字段不是本表的主關鍵字或侯選關鍵字,，而是另外一個表的主關鍵字或侯選關鍵字,，這個字段在本表中稱為外部關鍵字。

v 關系性質:

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

二維表中元組均不相同——元組的惟一性

二維表中元組的次序可以任意交換——元組的次序無關性

二維表中元組的分量是不可分割的基本數(shù)據項——元組分量的原子性

二維表中屬性名各不相同——屬性名惟一性

二維表中屬性與次序無關,，可任意交換——屬性的次序無關性

例：關系數(shù)據模型中表示實體和實體間的聯(lián)系的結構是（  ）

A,、樹型       B、網狀       C,、二維表        D,、對象

三、關系運算：

并（Union）：是由兩個關系的元組組成的集合,。（兩個關系必須具有相同的關系模式）

差（Difference）：若有兩個相同結構的關系R和S,，R差S的結果屬于R但不屬于S的元組組成的集合。

 交（Intersection）：若有兩個相同的結構關系R和S,，交的結果為兩個關系共同的元組,。

  選擇（Selection）：從關系中找出滿足給定條件的元組的操作稱為選擇。

投影（Projection）：從關系模式中指定若干個屬性組成新的關系稱為投影,。

 聯(lián)接（Join）：是關系的橫向結合,，關系模式改變了，是多個關系的關系模式的組合,。聯(lián)接的結果是多個關系中滿足條件的元組,。