全國計算機二級內(nèi)容學(xué)習(xí)

《全國計算機二級內(nèi)容學(xué)習(xí)》由會員分享，可在線閱讀，更多相關(guān)《全國計算機二級內(nèi)容學(xué)習(xí)（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)與算法 一、基本概念： v 數(shù)據(jù)(Data)：信息的載體，能夠被計算機識別、存儲和加工處理的物理符號。包括文本類型的數(shù)據(jù)(如：字母、數(shù)字、漢字)和多媒體類型的數(shù)據(jù)(如：聲音、動畫、圖像)。 v 數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，有時也稱為元素、結(jié)點、頂點、記錄，可以有若干個數(shù)據(jù)項（字段、域、屬性）組成。 v 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包括三個部分： 1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系 2、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示。 3、數(shù)據(jù)的運算（算法）：即對數(shù)據(jù)施加的操作

2、 v 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類： 1、線性結(jié)構(gòu)： 特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點最多只有一個直接前趨和一個直接后繼。 例：一維數(shù)組、鏈表、棧、隊列、串 2、非線性結(jié)構(gòu)： 特征是：一個結(jié)點可能有多個直接前趨和直接后繼。 例：多維數(shù)組、廣義表、樹、圖 v 數(shù)據(jù)的存儲結(jié)構(gòu)有以下基本存儲方法： 1、順序存儲方法： 該方法是將邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，一般通過數(shù)組來實現(xiàn)的。 2、鏈接存儲方法： 該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加

3、的指針字段表示的。通過指針類型來實現(xiàn)的。 3、索引存儲方法： 該方法通常是在存儲結(jié)點信息的同時，還建立附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是：關(guān)鍵字，地址。 4、散列存儲方法： 該方法的基本思想是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，通過散列函數(shù)實現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù) v 算法的基本特征： 1、可行性(Effectiveness)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。 2、確定性(Definiteness)：算法中的每一個步驟都必須有明確的定義，不允許出現(xiàn)歧義性。 3、有窮性(Finiteness)：算法必須

4、在有限時間內(nèi)做完，即必須在執(zhí)行有限個步驟之后終止。 v 時間復(fù)雜度：該算法執(zhí)行的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。 v 空間復(fù)雜度：該算法執(zhí)行時所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。 二、線性表： v 線性表(Linear List)：是由n(n>=0)個數(shù)據(jù)元素(結(jié)點)a1,a2,a3,,an組成的有限序列。對于非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨；有且僅有一個終端結(jié)點an，它沒有直接后繼；其余的結(jié)點有且僅有一個直接前趨結(jié)點和一個直接后繼結(jié)點。 v 線性表的存儲結(jié)構(gòu)： 1、順序存儲(Sequential List)：將線性表的結(jié)點按邏輯次序

5、依次存放在一組地址連續(xù)的存儲單元里，用這種方法存儲的線性表稱為順序表。 2、鏈式存儲(Linked List)：邏輯上相鄰的結(jié)點，物理上也相鄰，存儲單元可以是連續(xù)的，也可以是不連續(xù)的，在存儲每個結(jié)點值的同時，還存儲指向其后繼結(jié)點的地址，用這種方法存儲的線性表稱為鏈表。 v 常見的運算有： 表的初始化、求表的長度、取表中的第i個結(jié)點、查找結(jié)點、插入新的結(jié)點、刪除結(jié)點。 v 順序表和鏈表的比較： 1、基于空間的考慮： A、順序表的存儲空間是靜態(tài)分配的，而鏈表的存儲空間是動態(tài)分配的。 B、順序表占的存儲空間必須是連續(xù)的，而鏈表占的存儲空間可以是連續(xù)的，也可是不連續(xù)的 C、順序表存

6、儲密度為1，而鏈表中的每個結(jié)點，除了數(shù)據(jù)域外，還要額外的設(shè)置指針域，存儲密度小于1 2、基于時間的考慮： A、在鏈表中的任何位置上進行插入和刪除，只需要修改指針，而順序表中平均將要移動近一半的結(jié)點。 B、順序表是隨機存取結(jié)構(gòu)，它的存取時間為O(1)，而鏈表需從頭結(jié)點順著鏈掃描鏈表。 總之，當(dāng)線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)；當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用鏈表作為存儲結(jié)構(gòu)為好。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲

7、結(jié)構(gòu)。 例：關(guān)于線性表的描述中，錯誤的是（ ） A、線性表是線性結(jié)構(gòu) B、線性表的順序存儲結(jié)構(gòu)，必須占用一片連續(xù)的存儲單元 C、線性表是單鏈表 D、線性表的鏈式存儲結(jié)構(gòu)，不必占用一片連續(xù)的存儲單元 用數(shù)組表示線性表的優(yōu)點是（ ） A、便于插入和刪除操作 B、便于隨機存取 C、可以動態(tài)地分配存儲空間 D、不需要占用一片連續(xù)的存儲空間 三、棧： v 棧(Stack)：是限制僅在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端稱為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。是一種后進先出的線性表

8、，又稱為LIFO表。 v 棧的基本運算有： 棧的初始化、判?？?、判棧滿、進棧、出棧等 v 棧的存儲： 順序存儲、鏈式存儲 例：若進棧的輸入序列是A、B、C、D、E，并且在它們進棧的過程中可以進行出棧操作，則不可能出現(xiàn)的出棧序列是（ ） A、EDCBA B、DECBA C、DCEAB D、ABCDE 四、隊列： v 隊列(Queue)：也是一種運算受限的線性表，它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一段稱為隊頭(Front)，允許插入的一段稱為隊尾(Rear)。（類似于生活中的購物排隊）。是一種先進先出的

9、線性表，又稱為FIFO表。 v 隊列的基本運算： 隊列的初始化、判隊空、判隊滿、入隊、出隊 v 隊列的存儲實現(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 五、串： v 串(String)：是零個或多個字符組成的有限序列。 串中所包含的字符個數(shù)稱為該串的長度。 串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串 注：空串是任意串的子串，任意串是其自身的子串 v 串有串常量、串變量之分：

10、1、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。 2、串變量其值是可以改變的。 v 串的基本運算： 求串長、串復(fù)制、串聯(lián)接、串比較、字符定位、 六、樹（非線性結(jié)構(gòu)）： v 樹(Tree)：是n(n>=0)個結(jié)點的有限集T，T(n=0)為空時稱為空樹，否則它滿足如下兩個條件： 1、有且僅有一個特定的稱為根(Root)的結(jié)點 2、其余的結(jié)點可分為m(m>=0)個互不相交的子集T1，T2，…….，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹(Subtree)。 v 在樹的樹形圖表示中，結(jié)點通常是用圓圈表示的，結(jié)點的名字一般是寫在圓圈旁邊，有時亦可寫在圓圈內(nèi)。

11、v 度(Degree)：一個結(jié)點擁有的子樹數(shù)稱為該結(jié)點的度。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。 v 葉子(Leaf)：度為零的結(jié)點稱為葉子或終端結(jié)點 v 分支結(jié)點(Node)：度不為零的結(jié)點稱為分支結(jié)點。 v 樹中某個結(jié)點的子樹之根稱為該結(jié)點的孩子(Child)結(jié)點或子結(jié)點，相應(yīng)的該結(jié)點稱為孩子結(jié)點的雙親(Parents)結(jié)點或父結(jié)點。 v 同一個雙親的孩子稱為兄弟結(jié)點(Sibling) v 結(jié)點的層數(shù)(Level)是從根起算,設(shè)根的層數(shù)為1,其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加1. v 樹中結(jié)點的最大層數(shù)稱為樹的高度(Height)或深度(Depth). v 森林(Fores

12、t)：是m(m>=0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個森林，反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴洹? v 二叉樹(Binary Tree)：是n(n>=0)個結(jié)點的有限集，它或者是空集(n=0)，或者由一個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。 二叉樹中，每個結(jié)點最多只能有兩棵子樹，并且有左右之分。 v 二叉樹的五種基本形態(tài)： 例：具有3個結(jié)點的二叉樹有幾種形態(tài)。 v 滿二叉樹(Full Binary Tree)：一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹 v 完全二叉樹(Complete Binary Tree)：

13、若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。 二叉樹的性質(zhì)： 性質(zhì)1：二叉樹第i層上的結(jié)點數(shù)目最多為2i-1(i>=1) 性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(k>=1) 性質(zhì)3：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為[lgn]+1(取下整) 或 [lg(n+1)](取上整)。 例：一棵二叉樹的結(jié)點數(shù)為18個，求它的最小高度 已知度為2的結(jié)點數(shù)為15個，求葉子結(jié)點數(shù) 二叉樹的遍歷： v

14、遍歷(Traversal)：是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。 前序遍歷：（又稱為先序遍歷、先根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、訪問根結(jié)點； 2、前序遍歷左子樹； 3、前序遍歷右子樹。 中序遍歷：（又稱為中根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、中序遍歷左子樹； 2、訪問根結(jié)點； 3、中序遍歷右子樹。 后序遍歷：（又稱為后根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、后序遍歷左子樹； 2、后序遍歷右子樹； 3、訪問根結(jié)點。 例：已知一棵二叉樹的中序遍歷序列是：FDGBACHE，其后序遍歷序列是：

15、FGDBHECA 求其前序遍歷序列。 一棵二叉樹的前序遍歷序列為ABDGCFK，中序遍歷序列為DGBAFCK，則結(jié)點的后序遍歷序列是（ ） A、ACFKDBG B、GDBFKCA C、KCFAGDB D、ABCDFKG 七、排序(Sort)： v 所謂排序，就是指整理文件中的記錄，使之按關(guān)鍵字遞增（或遞減）次序排列起來。 v 冒泡排序(Bubble Sorting)： 通過對待排序序列從后向前或從前向后(從下標較大的元素開始)，依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部（

16、從下標較大的單元移向下標較小的單元）。 v 直接選擇排序(Selection Sorting)： 掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。 v 直接插入排序(Insertion Sorting)： 每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。 v 快速排序(Quick Sorting)：任取待排序序列中的某個元素作為基準(一般取第一個元素)，通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基

17、準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。 各種內(nèi)部排序方法的比較 排序方法 時間復(fù)雜度 空間復(fù)雜度 最好時間 平均時間 最壞時間 直接插入 O(n) O(n2) O(n2) O(1) 直接選擇 O(n2) O(n2) O(n2) O(1) 冒 泡 O(n) O(n2) O(n2) O(1) 快 速 O(nlgn) O(nlgn) O(n2) O(lgn) 堆 O(nlgn) O(nlgn) O(nlgn) O(1) 例：對一個具有n個元素的序列進行冒泡排序，在最壞情況下，要進行交換的次數(shù)是（ ）

18、 A、n(n+1)/2 B、n(n-1)/2 C、n*n/2 D、n(n+1)/2-1 對n個元素進行冒泡排序過程中，最好情況下的時間復(fù)雜性為（ ） A、O(1) B、O(log2n) C、O(n2) D、O(n) 對n個元素進行快速排序的過程中，平均情況下的時間復(fù)雜性為（ ） A、O(1) B、O(lgn) C、O(n2) D、O(nlgn) 八、查找(Searching)： v 所謂查找是指給定一個值K，在含有n個結(jié)點的表中找出關(guān)鍵字等于給定值K的結(jié)點。若找到

19、，則查找成功，返回該結(jié)點的信息或該結(jié)點在表中的位置；否則查找失敗，返回相關(guān)的提示信息。 v 順序查找(Sequential Search)的基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點關(guān)鍵字和給定值K相比較，若當(dāng)前掃描到的結(jié)點關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點，則查找失敗。順序查找即適用順序存儲結(jié)構(gòu)，又適用鏈式存儲結(jié)構(gòu)。 查找成功的平均查找長度為：(n為結(jié)點數(shù)目) (1+2+3+4++n) / n = (n+1)/2 v 二分查找(Binary Search)又稱折半查找，它是一種效率較高的查找方法，二分查找要求線性表是有序表，即表中

20、結(jié)點按關(guān)鍵字有序，并且要用向量作為表的存儲結(jié)構(gòu)。另外，二分查找只適用順序存儲結(jié)構(gòu)，在鏈式存儲結(jié)構(gòu)上無法實現(xiàn)二分查找。 查找成功時的平均查找長度：(n為結(jié)點數(shù)目) 當(dāng)n很大時，可用近似公式： lg(n+1)-1 表示 軟件工程基礎(chǔ) 一、基本概念： v 軟件(Software)：軟件是一種產(chǎn)品(邏輯產(chǎn)品)，指的是計算機中程序及其說明程序的各種文檔?！俺绦颉笔怯嬎闳蝿?wù)的處理對象和處理規(guī)則的描述；“文檔”是有關(guān)計算機程序功能、設(shè)計、編制、使用的文字或圖形資料。 v 軟件危機的表現(xiàn)： 1、軟件需求的增長得不到滿足 2、軟件開發(fā)成本和進度無法控制 3、軟件質(zhì)量

21、難以保證 4、軟件不可維護或維護程度非常低 5、軟件成本不斷提高 6、軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長 v 軟件工程(Software Engineering)：用工程化的方法、科學(xué)知識和技術(shù)原理來定義、開發(fā)、維護軟件的一門學(xué)科。 v 軟件工程的目標： 付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)任務(wù)，及時交付使用；開發(fā)的軟件可靠性高。 v 軟件工程研究的主要內(nèi)容是軟件開發(fā)技術(shù)和軟件開發(fā)管理兩個方面。 v 軟件生存周期：是指一個軟件從提出開發(fā)要求開始直到該軟件報廢(停止運行)為止的整

22、個時期。 v 軟件生存周期模型：是描述軟件開發(fā)過程中各種活動如何執(zhí)行的模型。 v 常用的模型有：瀑布模型、增量模型、螺旋模型、噴泉模型、變換模型和基于知識的模型 瀑布模型是將軟件生存周期各個活動規(guī)定為依線性順序連接的若干階段的模型。主要包括問題定義及可行性分析、項目開發(fā)計劃、需求分析、概要設(shè)計、詳細設(shè)計、編碼、測試和維護幾個階段。 例：下列描述中正確的是（ ） A、程序就是軟件 B、軟件開發(fā)不受計算機系統(tǒng)的限制 C、軟件既是邏輯實體，又是物理實體 D、軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合 二、軟件可行性研究與項目開發(fā)計劃： v 軟件可行性研究的目的是用最小的代價在盡可能

23、短的時間內(nèi)確定該軟件項目是否能夠開發(fā)，是否值得去開發(fā)。 v 可行性研究的任務(wù)： A、技術(shù)可行性 B、經(jīng)濟可行性 C、社會可行性（法律可行性） v 可行性研究的具體步驟： 1、確定項目規(guī)模和目標 2、研究正在運行的系統(tǒng) 3、建立新系統(tǒng)的高層邏輯模型 4、導(dǎo)出和評價各種方案 5、推薦可行的方案 6、編寫可行性研究報告 三、軟件需求分析： v 需求分析是指開發(fā)人員要準確理解用戶的要求，進行細致的調(diào)查分析，將用戶非形式的需求陳述轉(zhuǎn)化為完整的需求定義，再由需求定義轉(zhuǎn)換到相應(yīng)的形式功能規(guī)約（需求規(guī)格說明）的過程。 v 需求分析的基本任務(wù)： 1、問題識別 A、功能需求

24、B、性能需求 C、環(huán)境需求 D、用戶界面需求 2、分析與綜合，導(dǎo)出軟件的邏輯模型 3、編寫文檔(需求規(guī)格說明書) v 需求分析的方法： 1、結(jié)構(gòu)化分析(Structured Analysis)：是面向數(shù)據(jù)流進行需求分析的方法。 SA方法利用圖形等半形式化的描述方式表達需求，主要描述工具： A、數(shù)據(jù)流圖(DFD)：是SA方法中用于表示系統(tǒng)邏輯模型的一種工具，以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程。 B、數(shù)據(jù)字典(DD)：用以定義數(shù)據(jù)流圖中的各個成分的具體含義，為系統(tǒng)的分析、設(shè)計及維護提供了有關(guān)元素的一致的定義和詳細的描述。 C、描述加工邏輯的結(jié)構(gòu)化語言、判定表、判定樹

25、 2、IDEF方法(是 ICAM Definition的縮寫)： 是一種用于進行復(fù)雜系統(tǒng)分析和設(shè)計的方法，是在結(jié)構(gòu)化分析和設(shè)計技術(shù)的基礎(chǔ)上提出來的。 3、面向?qū)ο蠓治龇椒?OOP)： 將客觀世界的事物抽象為對象，通過屬性和方法描述對象的狀態(tài)和行為，具有繼承、封裝和多態(tài)性等特征。 例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的描述軟件功能需求的工具是（ ） A、業(yè)務(wù)流程圖、處理說明 B、軟件流程圖、模塊說明 C、數(shù)據(jù)流程圖、數(shù)據(jù)字典 D、系統(tǒng)流程圖、程序編碼 四、軟件概要設(shè)計： 將軟件需求轉(zhuǎn)換為軟件表示的過程。 v 軟件概要設(shè)計的基本任務(wù)

26、： 1、設(shè)計軟件系統(tǒng)結(jié)構(gòu) 2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計（概要設(shè)計、邏輯設(shè)計、物理設(shè)計）： 3、編寫概要設(shè)計文檔： 4、評審： v 軟件設(shè)計的方法： 模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)行語句等程序?qū)ο蟮募希蛘呤菃为毭途幹返脑?，如高級語言中的過程、函數(shù)、子程序等。 v 模塊獨立性指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。其度量標準是：耦合性和內(nèi)聚性 v 耦合性也稱塊間聯(lián)系，指軟件系統(tǒng)結(jié)構(gòu)中各模塊間相互聯(lián)系緊密程度的一種度量。模塊之間聯(lián)系越緊密，其耦合性就越強，模塊的獨立性則越差。 v 內(nèi)聚性也稱塊內(nèi)聯(lián)系，指模塊功能強度的度量，即一個模塊內(nèi)

27、部各個元素(語句之間、程序段之間)彼此結(jié)合的緊密程度的度量。 v 將軟件系統(tǒng)劃分模塊時，盡量做到高內(nèi)聚低耦合。 例：為了使模塊盡可能獨立，要求（ ） A、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量強 B、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量弱 C、模塊的內(nèi)聚程序要盡量低，且各模塊間的耦合程序要盡量弱 D、模塊的內(nèi)聚程序要盡量低，且各模塊間的耦合程序要盡量強 五、軟件詳細設(shè)計： 主要確定每個模塊具體執(zhí)行過程 v 軟件詳細設(shè)計的基本任務(wù)： 1、為每個模塊進行詳細的算法設(shè)計： 2、為模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進行設(shè)計： 3、對數(shù)據(jù)庫進行物理設(shè)計：

28、 4、輸入、輸出格式設(shè)計 5、編寫詳細設(shè)計說明書： 6、評審： v 詳細設(shè)計常用三種工具： 圖形(流程圖、盒圖、問題分析圖PAD)、 表格(判定表)、 語言(過程設(shè)計語言，又稱為偽碼) 六、軟件編碼： 主要是將詳細設(shè)計得到的處理過程描述轉(zhuǎn)換為基于某種計算機語言的程序 常用的計算機語言： Pascal 、C、C++、Java等 七、軟件測試： 軟件測試代表了需求分析、設(shè)計、編碼的最終復(fù)審。軟件測試貫穿于軟件開發(fā)的全過程。 v 軟件測試的目的： 1、軟件測試是為了盡可能多地發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程。 2、一個好的測試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤。

29、 3、一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。 v 軟件測試的原則： 1、測試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。 2、測試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù) 3、除了檢查程序是否做了它應(yīng)該做的事 4、應(yīng)制定測試計劃并嚴格執(zhí)行，排除隨意性 5、長期保留測試用例 6、對發(fā)現(xiàn)錯誤較多的程序段，應(yīng)進行更深入的測試 7、程序員避免測試自己的程序 v 軟件測試方法： 1、靜態(tài)測試： 是指被測試程序不在機器上運行，而是采用人工檢測和計算機輔助靜態(tài)分析的手段對程序進行檢測。 2、動態(tài)測試：是指通過運行程序發(fā)現(xiàn)錯誤 A、黑盒測試法(功能測試)： 主

30、要對軟件的接口進行測試，依據(jù)需求規(guī)格說明書，檢查程序是否滿足功能要求。常用的技術(shù)是等價類劃分法、邊界值分析法、錯誤推測法、因果圖法、綜合策略法 B、白盒測試法(結(jié)構(gòu)測試)： 主要測試程序的內(nèi)部結(jié)構(gòu)和處理過程。常用的技術(shù)是語句覆蓋、條件覆蓋、路徑覆蓋、判定覆蓋等 v 軟件測試的實施： 1、單元測試： 單元測試是對軟件設(shè)計的最小單位——模塊(程序單元)進行正確性檢驗測試，主要針對模塊的以下五個基本特征進行測試： A、模塊接口 B、局部數(shù)據(jù)結(jié)構(gòu)： C、重要的執(zhí)行路徑： D、錯誤處理測試： E、邊界條件： 2、集成測試： 集成測試是指在單元測試的基礎(chǔ)上，將所有模塊按照設(shè)計要求組

31、裝成一個完整的系統(tǒng)進行的測試，故也稱組裝測試或聯(lián)合測試。 主要方法有兩種： 非漸增式測試：首先對每個模塊分別進行單元測試，然后再把所有的模塊按設(shè)計要求組裝在一起進行測試。 漸增式測試：逐個把未經(jīng)過測試的模塊組裝到已經(jīng)過測試的模塊上去，進行集成測試，每加入一個新模塊進行一次集成測試，重復(fù)此過程直至程序組裝完畢。 3、確認測試： 確認測試又稱有效性測試，它的任務(wù)是檢查軟件的功能與性能是否與需求規(guī)格說明書中確定的指標相符合，因而需求規(guī)格說明是確認測試的基礎(chǔ)。 4、系統(tǒng)測試： 系統(tǒng)測試是通過測試確認的軟件作為整個計算機系統(tǒng)的一個元素，與計算機硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素

32、組合在一起，在實際運行環(huán)境下對計算機系統(tǒng)進行一系列的集成測試和確認測試。 v 程序調(diào)試： 調(diào)試是在進行了成功的測試之后才開始的工作，目的是確定錯誤的原因和位置，并改正錯誤，又稱為糾錯。 例：軟件測試的目的是（ ） A、證明軟件的正確性 B、找出軟件系統(tǒng)中存在的所有錯誤 C、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯誤 D、證明軟件系統(tǒng)中存在錯誤 在軟件測試方法中，黑箱測試法和白箱測試法是常用的方法，其中黑箱測試法主要是 用于測試（ ） A、結(jié)構(gòu)合理性 B、軟件外部功能 C、程序正確性 D、程序內(nèi)部邏輯 八、軟件維護： 軟件投入使

33、用后進行的階段，是軟件生存周期中時間最長的一個階段，所花費的精力和費用也是最多的一個階段。主要是因為：隱含的錯誤要修改；新增的功能要加入進去；環(huán)境的變化對程序進行變動等。 v 軟件維護的內(nèi)容有四類： 1、校正性維護： 為了識別和糾正錯誤，修改軟件性能上的缺陷，其占整個維護工作的 21% 2、適應(yīng)性維護： 為了使應(yīng)用軟件適應(yīng)環(huán)境(硬件、系統(tǒng)軟件、數(shù)據(jù))的變化而修改軟件的過程稱為適應(yīng)性維護，其占整個維護工作的25% 3、完善性維護： 增加軟件功能、增強軟件性能、提高軟件運行效率而進行的維護活動稱為完善性維護，其占整個維護工作的 50% 4、預(yù)防性維護： 為了提高軟件的可維護性和可

34、靠性而對軟件進行的修改稱為預(yù)防性維護，其占整個維護工作的 4% 例：軟件維護是指（ ） A、維護軟件正常運行 B、軟件的配置更新 C、對軟件的改進、適應(yīng)和完善 D、軟件開發(fā)期的一個階段 軟件生命周期中所花費用最多的階段是（ ） A、詳細設(shè)計 B、軟件編碼 C、軟件測試 D、軟件維護 數(shù)據(jù)庫原理基礎(chǔ) 一、基本概念： v 數(shù)據(jù)處理：是指將數(shù)據(jù)轉(zhuǎn)換成信息的過程 v 數(shù)據(jù)管理是指對數(shù)據(jù)的組織、分類、編碼、存儲、檢索和維護提供操作手段 其經(jīng)歷了以下階段： 1、人工管理 2、文件系統(tǒng) 3、數(shù)據(jù)庫系統(tǒng) 4、分布式數(shù)據(jù)庫系統(tǒng)階段 5、面向?qū)ο蟮臄?shù)據(jù)庫系

35、統(tǒng)階段 v 數(shù)據(jù)庫(Database)：是指存儲在計算機存儲設(shè)備上的結(jié)構(gòu)化的相關(guān)數(shù)據(jù)的集合，不僅包括數(shù)據(jù)本身，還包括事物之間的聯(lián)系。 v v v v v v v v v v 數(shù)據(jù)庫應(yīng)用系統(tǒng)(DBAS)：是指系統(tǒng)開發(fā)人員利用數(shù)據(jù)庫系統(tǒng)資源開發(fā)出來的，面向某一類實際應(yīng)用的應(yīng)用軟件系統(tǒng)。 v v 數(shù)據(jù)庫管理系統(tǒng)(DBMS)： v v v v v v 對數(shù)據(jù)庫的建立、使用和維護進行管理和配置的軟件系統(tǒng)。 是數(shù)據(jù)庫系統(tǒng)的核心 v 數(shù)據(jù)庫系統(tǒng)(DBS):由硬件系統(tǒng)、數(shù)據(jù)庫集合、數(shù)據(jù)庫管理系統(tǒng)及相關(guān)軟件、數(shù)據(jù)庫管理員和用戶組成。 v 數(shù)據(jù)庫系統(tǒng)

36、的特點： 實現(xiàn)數(shù)據(jù)共享、減少數(shù)據(jù)冗余 采用特定的數(shù)據(jù)模型 具有較高的數(shù)據(jù)獨立性 統(tǒng)一的數(shù)據(jù)控制功能 v 實體： 客觀存在并且可以相互區(qū)別的事物稱為實體。 v 實體的屬性：實體所具有的物性稱為實體的屬性。 v 實體集：同類型的實體的集合稱為實體集。 v 實體型：屬性的集合表示一種實體類型，稱為實體型。 例：數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)對數(shù)據(jù)庫中數(shù)據(jù)的查詢、插入、修改和刪除，這類功能稱為（ ） A、數(shù)據(jù)定義功能 B、數(shù)據(jù)管理功能 C、數(shù)據(jù)操縱功能 D、數(shù)據(jù)控制功能 v 聯(lián)系：實體之間的對應(yīng)關(guān)系。 聯(lián)系的類型: 1、一對一聯(lián)系：表現(xiàn)為主表中的每一條記錄只與相關(guān)

37、表中的一條記錄相關(guān)聯(lián)。 例如： 班級與班長， 學(xué)校與校長 2、一對多聯(lián)系：表現(xiàn)為主表中的每一條記錄與相關(guān)表中的多條記錄相關(guān)聯(lián)。 例如： 班級與學(xué)生，部門與職工 3、多對多聯(lián)系：表現(xiàn)為一個表中的多個記錄在相關(guān)表中同樣有多個記錄相關(guān)聯(lián)。 例如： 學(xué)生與課程， 工程項目與零件 v 數(shù)據(jù)模型：不僅反映事物本身，還用來表示實體及實體之間聯(lián)系的方法。 1、層次模型：用樹形結(jié)構(gòu)表示實體及其之間聯(lián)系的模型稱為層次模型。 2、網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實體及其之間聯(lián)系的模型稱為網(wǎng)狀模型。 3、關(guān)系模型：用二維表結(jié)構(gòu)來表示實體及實體之間的聯(lián)系的模型稱為關(guān)系模型。 一個二維表稱為一個關(guān)系，在

38、VFP稱為數(shù)據(jù)表。一個關(guān)系不僅表示實體本身還表示實體之間的聯(lián)系。 例：用樹形結(jié)構(gòu)表示實體之間聯(lián)系的模型是（ ） A、關(guān)系模型 B、網(wǎng)狀模型 C、層次模型 D、以上三個都是 二、關(guān)系數(shù)據(jù)庫： v 元組(Record)：在一個關(guān)系中，水平方向的行稱為元組。在VFP中稱為記錄 v 屬性(Field)：一個二維表中垂直方向的列稱為屬性。在VFP中稱為字段名 v 域(Domain)：屬性的取值范圍。根據(jù)數(shù)據(jù)類型和寬度來決定的。 v 關(guān)鍵字(Primary Key)：其值能夠惟一標識一個元組的屬性或?qū)傩缘慕M合。 注：關(guān)鍵字不能出現(xiàn)空值或重復(fù)值 v 外部關(guān)鍵字(Foreign K

39、ey)：如果表中的一個字段不是本表的主關(guān)鍵字或侯選關(guān)鍵字，而是另外一個表的主關(guān)鍵字或侯選關(guān)鍵字，這個字段在本表中稱為外部關(guān)鍵字。 v 關(guān)系性質(zhì): 二維表中元組的個數(shù)是有限的——元組個數(shù)有限性 二維表中元組均不相同——元組的惟一性 二維表中元組的次序可以任意交換——元組的次序無關(guān)性 二維表中元組的分量是不可分割的基本數(shù)據(jù)項——元組分量的原子性 二維表中屬性名各不相同——屬性名惟一性 二維表中屬性與次序無關(guān)，可任意交換——屬性的次序無關(guān)性 例：關(guān)系數(shù)據(jù)模型中表示實體和實體間的聯(lián)系的結(jié)構(gòu)是（ ） A、樹型 B、網(wǎng)狀 C、二維表 D、對象

40、 三、關(guān)系運算： v 并（Union）：是由兩個關(guān)系的元組組成的集合。（兩個關(guān)系必須具有相同的關(guān)系模式） v 差（Difference）：若有兩個相同結(jié)構(gòu)的關(guān)系R和S，R差S的結(jié)果屬于R但不屬于S的元組組成的集合。 v 交（Intersection）：若有兩個相同的結(jié)構(gòu)關(guān)系R和S，交的結(jié)果為兩個關(guān)系共同的元組。 v 選擇（Selection）：從關(guān)系中找出滿足給定條件的元組的操作稱為選擇。 v 投影（Projection）：從關(guān)系模式中指定若干個屬性組成新的關(guān)系稱為投影。 v 聯(lián)接（Join）：是關(guān)系的橫向結(jié)合，關(guān)系模式改變了，是多個關(guān)系的關(guān)系模式的組合。聯(lián)接的結(jié)果是多個關(guān)系中滿足條件的元組。