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

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

全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí) 數(shù)據(jù)結(jié)構(gòu)與算法 一、基本概念： v 數(shù)據(jù)(Data)：信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的物理符號(hào)。包括文本類型的數(shù)據(jù)(如：字母、數(shù)字、漢字)和多媒體類型的數(shù)據(jù)(如：聲音、動(dòng)畫、圖像)。 v 數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，有時(shí)也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄，可以有若干個(gè)數(shù)據(jù)項(xiàng)（字段、域、屬性）組成。 v 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包括三個(gè)部分： 1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系 2、存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。 3、數(shù)據(jù)的運(yùn)算（算法）：即對(duì)數(shù)據(jù)施加的操作 v 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類： 1、線性結(jié)構(gòu)： 特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和一個(gè)直接后繼。 例：一維數(shù)組、鏈表、棧、隊(duì)列、串 2、非線性結(jié)構(gòu)： 特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。 例：多維數(shù)組、廣義表、樹、圖 v 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有以下基本存儲(chǔ)方法： 1、順序存儲(chǔ)方法： 該方法是將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)，一般通過數(shù)組來實(shí)現(xiàn)的。 2、鏈接存儲(chǔ)方法： 該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。通過指針類型來實(shí)現(xiàn)的。 3、索引存儲(chǔ)方法： 該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：關(guān)鍵字，地址。 4、散列存儲(chǔ)方法： 該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，通過散列函數(shù)實(shí)現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù) v 算法的基本特征： 1、可行性(Effectiveness)：針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。 2、確定性(Definiteness)：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義性。 3、有窮性(Finiteness)：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步驟之后終止。 v 時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。 v 空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)。 二、線性表： v 線性表(Linear List)：是由n(n>=0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1,a2,a3,······,an組成的有限序列。對(duì)于非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒有直接前趨；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼；其余的結(jié)點(diǎn)有且僅有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。 v 線性表的存儲(chǔ)結(jié)構(gòu)： 1、順序存儲(chǔ)(Sequential List)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里，用這種方法存儲(chǔ)的線性表稱為順序表。 2、鏈?zhǔn)酱鎯?chǔ)(Linked List)：邏輯上相鄰的結(jié)點(diǎn)，物理上也相鄰，存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)指向其后繼結(jié)點(diǎn)的地址，用這種方法存儲(chǔ)的線性表稱為鏈表。 v 常見的運(yùn)算有： 表的初始化、求表的長(zhǎng)度、取表中的第i個(gè)結(jié)點(diǎn)、查找結(jié)點(diǎn)、插入新的結(jié)點(diǎn)、刪除結(jié)點(diǎn)。 v 順序表和鏈表的比較： 1、基于空間的考慮： A、順序表的存儲(chǔ)空間是靜態(tài)分配的，而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。 B、順序表占的存儲(chǔ)空間必須是連續(xù)的，而鏈表占的存儲(chǔ)空間可以是連續(xù)的，也可是不連續(xù)的 C、順序表存儲(chǔ)密度為1，而鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外的設(shè)置指針域，存儲(chǔ)密度小于1 2、基于時(shí)間的考慮： A、在鏈表中的任何位置上進(jìn)行插入和刪除，只需要修改指針，而順序表中平均將要移動(dòng)近一半的結(jié)點(diǎn)。 B、順序表是隨機(jī)存取結(jié)構(gòu)，它的存取時(shí)間為O(1)，而鏈表需從頭結(jié)點(diǎn)順著鏈掃描鏈表。 總之，當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)；當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用鏈表作為存儲(chǔ)結(jié)構(gòu)為好。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。 例：關(guān)于線性表的描述中，錯(cuò)誤的是（ ） A、線性表是線性結(jié)構(gòu) B、線性表的順序存儲(chǔ)結(jié)構(gòu)，必須占用一片連續(xù)的存儲(chǔ)單元 C、線性表是單鏈表 D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不必占用一片連續(xù)的存儲(chǔ)單元 用數(shù)組表示線性表的優(yōu)點(diǎn)是（ ） A、便于插入和刪除操作 B、便于隨機(jī)存取 C、可以動(dòng)態(tài)地分配存儲(chǔ)空間 D、不需要占用一片連續(xù)的存儲(chǔ)空間 三、棧： v 棧(Stack)：是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端稱為棧底(Bottom)。當(dāng)表中沒有元素時(shí)稱為空棧。是一種后進(jìn)先出的線性表，又稱為L(zhǎng)IFO表。 v 棧的基本運(yùn)算有： 棧的初始化、判棧空、判棧滿、進(jìn)棧、出棧等 v 棧的存儲(chǔ)： 順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ) 例：若進(jìn)棧的輸入序列是A、B、C、D、E，并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操作，則不可能出現(xiàn)的出棧序列是（ ） A、EDCBA B、DECBA C、DCEAB D、ABCDE 四、隊(duì)列： v 隊(duì)列(Queue)：也是一種運(yùn)算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一段稱為隊(duì)頭(Front)，允許插入的一段稱為隊(duì)尾(Rear)。（類似于生活中的購物排隊(duì)）。是一種先進(jìn)先出的線性表，又稱為FIFO表。 v 隊(duì)列的基本運(yùn)算： 隊(duì)列的初始化、判隊(duì)空、判隊(duì)滿、入隊(duì)、出隊(duì) v 隊(duì)列的存儲(chǔ)實(shí)現(xiàn)： 順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ) 例：一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是 （ ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 五、串： v 串(String)：是零個(gè)或多個(gè)字符組成的有限序列。 串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串 注：空串是任意串的子串，任意串是其自身的子串 v 串有串常量、串變量之分： 1、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。 2、串變量其值是可以改變的。 v 串的基本運(yùn)算： 求串長(zhǎng)、串復(fù)制、串聯(lián)接、串比較、字符定位、 六、樹（非線性結(jié)構(gòu)）： v 樹(Tree)：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，T(n=0)為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件： 1、有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn) 2、其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1，T2，…….，Tm，其中每個(gè)子集本身又是一棵樹，并稱其為根的子樹(Subtree)。 v 在樹的樹形圖表示中，結(jié)點(diǎn)通常是用圓圈表示的，結(jié)點(diǎn)的名字一般是寫在圓圈旁邊，有時(shí)亦可寫在圓圈內(nèi)。 v 度(Degree)：一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。 v 葉子(Leaf)：度為零的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn) v 分支結(jié)點(diǎn)(Node)：度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。 v 樹中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的孩子(Child)結(jié)點(diǎn)或子結(jié)點(diǎn)，相應(yīng)的該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親(Parents)結(jié)點(diǎn)或父結(jié)點(diǎn)。 v 同一個(gè)雙親的孩子稱為兄弟結(jié)點(diǎn)(Sibling) v 結(jié)點(diǎn)的層數(shù)(Level)是從根起算,設(shè)根的層數(shù)為1,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1. v 樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth). v 森林(Forest)：是m(m>=0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個(gè)森林，反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴洹? v 二叉樹(Binary Tree)：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。 二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，并且有左右之分。 v 二叉樹的五種基本形態(tài)： 例：具有3個(gè)結(jié)點(diǎn)的二叉樹有幾種形態(tài)。 v 滿二叉樹(Full Binary Tree)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹 v 完全二叉樹(Complete Binary Tree)：若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。 二叉樹的性質(zhì)： 性質(zhì)1：二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1(i>=1) 性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k>=1) 性質(zhì)3：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[lgn]+1(取下整) 或 [lg(n+1)](取上整)。 例：一棵二叉樹的結(jié)點(diǎn)數(shù)為18個(gè)，求它的最小高度 已知度為2的結(jié)點(diǎn)數(shù)為15個(gè)，求葉子結(jié)點(diǎn)數(shù) 二叉樹的遍歷： v 遍歷(Traversal)：是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。 前序遍歷：（又稱為先序遍歷、先根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、訪問根結(jié)點(diǎn)； 2、前序遍歷左子樹； 3、前序遍歷右子樹。 中序遍歷：（又稱為中根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、中序遍歷左子樹； 2、訪問根結(jié)點(diǎn)； 3、中序遍歷右子樹。 后序遍歷：（又稱為后根遍歷） 若二叉樹為空，則執(zhí)行空操作。否則： 1、后序遍歷左子樹； 2、后序遍歷右子樹； 3、訪問根結(jié)點(diǎn)。 例：已知一棵二叉樹的中序遍歷序列是：FDGBACHE，其后序遍歷序列是：FGDBHECA 求其前序遍歷序列。 一棵二叉樹的前序遍歷序列為ABDGCFK，中序遍歷序列為DGBAFCK，則結(jié)點(diǎn)的后序遍歷序列是（ ） A、ACFKDBG B、GDBFKCA C、KCFAGDB D、ABCDFKG 七、排序(Sort)： v 所謂排序，就是指整理文件中的記錄，使之按關(guān)鍵字遞增（或遞減）次序排列起來。 v 冒泡排序(Bubble Sorting)： 通過對(duì)待排序序列從后向前或從前向后(從下標(biāo)較大的元素開始)，依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部（從下標(biāo)較大的單元移向下標(biāo)較小的單元）。 v 直接選擇排序(Selection Sorting)： 掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。 v 直接插入排序(Insertion Sorting)： 每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。 v 快速排序(Quick Sorting)：任取待排序序列中的某個(gè)元素作為基準(zhǔn)(一般取第一個(gè)元素)，通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。 各種內(nèi)部排序方法的比較 排序方法 時(shí)間復(fù)雜度 空間復(fù)雜度 最好時(shí)間 平均時(shí)間 最壞時(shí)間 直接插入 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) 例：對(duì)一個(gè)具有n個(gè)元素的序列進(jìn)行冒泡排序，在最壞情況下，要進(jìn)行交換的次數(shù)是（ ） A、n(n+1)/2 B、n(n-1)/2 C、n*n/2 D、n(n+1)/2-1 對(duì)n個(gè)元素進(jìn)行冒泡排序過程中，最好情況下的時(shí)間復(fù)雜性為（ ） A、O(1) B、O(log2n) C、O(n2) D、O(n) 對(duì)n個(gè)元素進(jìn)行快速排序的過程中，平均情況下的時(shí)間復(fù)雜性為（ ） A、O(1) B、O(lgn) C、O(n2) D、O(nlgn) 八、查找(Searching)： v 所謂查找是指給定一個(gè)值K，在含有n個(gè)結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置；否則查找失敗，返回相關(guān)的提示信息。 v 順序查找(Sequential Search)的基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。順序查找即適用順序存儲(chǔ)結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 查找成功的平均查找長(zhǎng)度為：(n為結(jié)點(diǎn)數(shù)目) (1+2+3+4+···+n) / n = (n+1)/2 v 二分查找(Binary Search)又稱折半查找，它是一種效率較高的查找方法，二分查找要求線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。另外，二分查找只適用順序存儲(chǔ)結(jié)構(gòu)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上無法實(shí)現(xiàn)二分查找。 查找成功時(shí)的平均查找長(zhǎng)度：(n為結(jié)點(diǎn)數(shù)目) 當(dāng)n很大時(shí)，可用近似公式： lg(n+1)-1 表示 軟件工程基礎(chǔ) 一、基本概念： v 軟件(Software)：軟件是一種產(chǎn)品(邏輯產(chǎn)品)，指的是計(jì)算機(jī)中程序及其說明程序的各種文檔?！俺绦颉笔怯?jì)算任務(wù)的處理對(duì)象和處理規(guī)則的描述；“文檔”是有關(guān)計(jì)算機(jī)程序功能、設(shè)計(jì)、編制、使用的文字或圖形資料。 v 軟件危機(jī)的表現(xiàn)： 1、軟件需求的增長(zhǎng)得不到滿足 2、軟件開發(fā)成本和進(jìn)度無法控制 3、軟件質(zhì)量難以保證 4、軟件不可維護(hù)或維護(hù)程度非常低 5、軟件成本不斷提高 6、軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng) v 軟件工程(Software Engineering)：用工程化的方法、科學(xué)知識(shí)和技術(shù)原理來定義、開發(fā)、維護(hù)軟件的一門學(xué)科。 v 軟件工程的目標(biāo)： 付出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開發(fā)任務(wù)，及時(shí)交付使用；開發(fā)的軟件可靠性高。 v 軟件工程研究的主要內(nèi)容是軟件開發(fā)技術(shù)和軟件開發(fā)管理兩個(gè)方面。 v 軟件生存周期：是指一個(gè)軟件從提出開發(fā)要求開始直到該軟件報(bào)廢(停止運(yùn)行)為止的整個(gè)時(shí)期。 v 軟件生存周期模型：是描述軟件開發(fā)過程中各種活動(dòng)如何執(zhí)行的模型。 v 常用的模型有：瀑布模型、增量模型、螺旋模型、噴泉模型、變換模型和基于知識(shí)的模型 瀑布模型是將軟件生存周期各個(gè)活動(dòng)規(guī)定為依線性順序連接的若干階段的模型。主要包括問題定義及可行性分析、項(xiàng)目開發(fā)計(jì)劃、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測(cè)試和維護(hù)幾個(gè)階段。 例：下列描述中正確的是（ ） A、程序就是軟件 B、軟件開發(fā)不受計(jì)算機(jī)系統(tǒng)的限制 C、軟件既是邏輯實(shí)體，又是物理實(shí)體 D、軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合 二、軟件可行性研究與項(xiàng)目開發(fā)計(jì)劃： v 軟件可行性研究的目的是用最小的代價(jià)在盡可能短的時(shí)間內(nèi)確定該軟件項(xiàng)目是否能夠開發(fā)，是否值得去開發(fā)。 v 可行性研究的任務(wù)： A、技術(shù)可行性 B、經(jīng)濟(jì)可行性 C、社會(huì)可行性（法律可行性） v 可行性研究的具體步驟： 1、確定項(xiàng)目規(guī)模和目標(biāo) 2、研究正在運(yùn)行的系統(tǒng) 3、建立新系統(tǒng)的高層邏輯模型 4、導(dǎo)出和評(píng)價(jià)各種方案 5、推薦可行的方案 6、編寫可行性研究報(bào)告 三、軟件需求分析： v 需求分析是指開發(fā)人員要準(zhǔn)確理解用戶的要求，進(jìn)行細(xì)致的調(diào)查分析，將用戶非形式的需求陳述轉(zhuǎn)化為完整的需求定義，再由需求定義轉(zhuǎn)換到相應(yīng)的形式功能規(guī)約（需求規(guī)格說明）的過程。 v 需求分析的基本任務(wù)： 1、問題識(shí)別 A、功能需求 B、性能需求 C、環(huán)境需求 D、用戶界面需求 2、分析與綜合，導(dǎo)出軟件的邏輯模型 3、編寫文檔(需求規(guī)格說明書) v 需求分析的方法： 1、結(jié)構(gòu)化分析(Structured Analysis)：是面向數(shù)據(jù)流進(jìn)行需求分析的方法。 SA方法利用圖形等半形式化的描述方式表達(dá)需求，主要描述工具： A、數(shù)據(jù)流圖(DFD)：是SA方法中用于表示系統(tǒng)邏輯模型的一種工具，以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程。 B、數(shù)據(jù)字典(DD)：用以定義數(shù)據(jù)流圖中的各個(gè)成分的具體含義，為系統(tǒng)的分析、設(shè)計(jì)及維護(hù)提供了有關(guān)元素的一致的定義和詳細(xì)的描述。 C、描述加工邏輯的結(jié)構(gòu)化語言、判定表、判定樹 2、IDEF方法(是 ICAM Definition的縮寫)： 是一種用于進(jìn)行復(fù)雜系統(tǒng)分析和設(shè)計(jì)的方法，是在結(jié)構(gòu)化分析和設(shè)計(jì)技術(shù)的基礎(chǔ)上提出來的。 3、面向?qū)ο蠓治龇椒?OOP)： 將客觀世界的事物抽象為對(duì)象，通過屬性和方法描述對(duì)象的狀態(tài)和行為，具有繼承、封裝和多態(tài)性等特征。 例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的描述軟件功能需求的工具是（ ） A、業(yè)務(wù)流程圖、處理說明 B、軟件流程圖、模塊說明 C、數(shù)據(jù)流程圖、數(shù)據(jù)字典 D、系統(tǒng)流程圖、程序編碼 四、軟件概要設(shè)計(jì)： 將軟件需求轉(zhuǎn)換為軟件表示的過程。 v 軟件概要設(shè)計(jì)的基本任務(wù)： 1、設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu) 2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)（概要設(shè)計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)）： 3、編寫概要設(shè)計(jì)文檔： 4、評(píng)審： v 軟件設(shè)計(jì)的方法： 模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)行語句等程序?qū)ο蟮募?，或者是單?dú)命名和編址的元素，如高級(jí)語言中的過程、函數(shù)、子程序等。 v 模塊獨(dú)立性指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。其度量標(biāo)準(zhǔn)是：耦合性和內(nèi)聚性 v 耦合性也稱塊間聯(lián)系，指軟件系統(tǒng)結(jié)構(gòu)中各模塊間相互聯(lián)系緊密程度的一種度量。模塊之間聯(lián)系越緊密，其耦合性就越強(qiáng)，模塊的獨(dú)立性則越差。 v 內(nèi)聚性也稱塊內(nèi)聯(lián)系，指模塊功能強(qiáng)度的度量，即一個(gè)模塊內(nèi)部各個(gè)元素(語句之間、程序段之間)彼此結(jié)合的緊密程度的度量。 v 將軟件系統(tǒng)劃分模塊時(shí)，盡量做到高內(nèi)聚低耦合。 例：為了使模塊盡可能獨(dú)立，要求（ ） A、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量強(qiáng) B、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量弱 C、模塊的內(nèi)聚程序要盡量低，且各模塊間的耦合程序要盡量弱 D、模塊的內(nèi)聚程序要盡量低，且各模塊間的耦合程序要盡量強(qiáng) 五、軟件詳細(xì)設(shè)計(jì)： 主要確定每個(gè)模塊具體執(zhí)行過程 v 軟件詳細(xì)設(shè)計(jì)的基本任務(wù)： 1、為每個(gè)模塊進(jìn)行詳細(xì)的算法設(shè)計(jì)： 2、為模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)： 3、對(duì)數(shù)據(jù)庫進(jìn)行物理設(shè)計(jì)： 4、輸入、輸出格式設(shè)計(jì) 5、編寫詳細(xì)設(shè)計(jì)說明書： 6、評(píng)審： v 詳細(xì)設(shè)計(jì)常用三種工具： 圖形(流程圖、盒圖、問題分析圖PAD)、 表格(判定表)、 語言(過程設(shè)計(jì)語言，又稱為偽碼) 六、軟件編碼： 主要是將詳細(xì)設(shè)計(jì)得到的處理過程描述轉(zhuǎn)換為基于某種計(jì)算機(jī)語言的程序 常用的計(jì)算機(jī)語言： Pascal 、C、C++、Java等 七、軟件測(cè)試： 軟件測(cè)試代表了需求分析、設(shè)計(jì)、編碼的最終復(fù)審。軟件測(cè)試貫穿于軟件開發(fā)的全過程。 v 軟件測(cè)試的目的： 1、軟件測(cè)試是為了盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤而執(zhí)行程序的過程。 2、一個(gè)好的測(cè)試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤。 3、一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。 v 軟件測(cè)試的原則： 1、測(cè)試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。 2、測(cè)試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù) 3、除了檢查程序是否做了它應(yīng)該做的事 4、應(yīng)制定測(cè)試計(jì)劃并嚴(yán)格執(zhí)行，排除隨意性 5、長(zhǎng)期保留測(cè)試用例 6、對(duì)發(fā)現(xiàn)錯(cuò)誤較多的程序段，應(yīng)進(jìn)行更深入的測(cè)試 7、程序員避免測(cè)試自己的程序 v 軟件測(cè)試方法： 1、靜態(tài)測(cè)試： 是指被測(cè)試程序不在機(jī)器上運(yùn)行，而是采用人工檢測(cè)和計(jì)算機(jī)輔助靜態(tài)分析的手段對(duì)程序進(jìn)行檢測(cè)。 2、動(dòng)態(tài)測(cè)試：是指通過運(yùn)行程序發(fā)現(xiàn)錯(cuò)誤 A、黑盒測(cè)試法(功能測(cè)試)： 主要對(duì)軟件的接口進(jìn)行測(cè)試，依據(jù)需求規(guī)格說明書，檢查程序是否滿足功能要求。常用的技術(shù)是等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖法、綜合策略法 B、白盒測(cè)試法(結(jié)構(gòu)測(cè)試)： 主要測(cè)試程序的內(nèi)部結(jié)構(gòu)和處理過程。常用的技術(shù)是語句覆蓋、條件覆蓋、路徑覆蓋、判定覆蓋等 v 軟件測(cè)試的實(shí)施： 1、單元測(cè)試： 單元測(cè)試是對(duì)軟件設(shè)計(jì)的最小單位——模塊(程序單元)進(jìn)行正確性檢驗(yàn)測(cè)試，主要針對(duì)模塊的以下五個(gè)基本特征進(jìn)行測(cè)試： A、模塊接口 B、局部數(shù)據(jù)結(jié)構(gòu)： C、重要的執(zhí)行路徑： D、錯(cuò)誤處理測(cè)試： E、邊界條件： 2、集成測(cè)試： 集成測(cè)試是指在單元測(cè)試的基礎(chǔ)上，將所有模塊按照設(shè)計(jì)要求組裝成一個(gè)完整的系統(tǒng)進(jìn)行的測(cè)試，故也稱組裝測(cè)試或聯(lián)合測(cè)試。 主要方法有兩種： 非漸增式測(cè)試：首先對(duì)每個(gè)模塊分別進(jìn)行單元測(cè)試，然后再把所有的模塊按設(shè)計(jì)要求組裝在一起進(jìn)行測(cè)試。 漸增式測(cè)試：逐個(gè)把未經(jīng)過測(cè)試的模塊組裝到已經(jīng)過測(cè)試的模塊上去，進(jìn)行集成測(cè)試，每加入一個(gè)新模塊進(jìn)行一次集成測(cè)試，重復(fù)此過程直至程序組裝完畢。 3、確認(rèn)測(cè)試： 確認(rèn)測(cè)試又稱有效性測(cè)試，它的任務(wù)是檢查軟件的功能與性能是否與需求規(guī)格說明書中確定的指標(biāo)相符合，因而需求規(guī)格說明是確認(rèn)測(cè)試的基礎(chǔ)。 4、系統(tǒng)測(cè)試： 系統(tǒng)測(cè)試是通過測(cè)試確認(rèn)的軟件作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)境下對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行一系列的集成測(cè)試和確認(rèn)測(cè)試。 v 程序調(diào)試： 調(diào)試是在進(jìn)行了成功的測(cè)試之后才開始的工作，目的是確定錯(cuò)誤的原因和位置，并改正錯(cuò)誤，又稱為糾錯(cuò)。 例：軟件測(cè)試的目的是（ ） A、證明軟件的正確性 B、找出軟件系統(tǒng)中存在的所有錯(cuò)誤 C、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯(cuò)誤 D、證明軟件系統(tǒng)中存在錯(cuò)誤 在軟件測(cè)試方法中，黑箱測(cè)試法和白箱測(cè)試法是常用的方法，其中黑箱測(cè)試法主要是 用于測(cè)試（ ） A、結(jié)構(gòu)合理性 B、軟件外部功能 C、程序正確性 D、程序內(nèi)部邏輯 八、軟件維護(hù)： 軟件投入使用后進(jìn)行的階段，是軟件生存周期中時(shí)間最長(zhǎng)的一個(gè)階段，所花費(fèi)的精力和費(fèi)用也是最多的一個(gè)階段。主要是因?yàn)椋弘[含的錯(cuò)誤要修改；新增的功能要加入進(jìn)去；環(huán)境的變化對(duì)程序進(jìn)行變動(dòng)等。 v 軟件維護(hù)的內(nèi)容有四類： 1、校正性維護(hù)： 為了識(shí)別和糾正錯(cuò)誤，修改軟件性能上的缺陷，其占整個(gè)維護(hù)工作的 21% 2、適應(yīng)性維護(hù)： 為了使應(yīng)用軟件適應(yīng)環(huán)境(硬件、系統(tǒng)軟件、數(shù)據(jù))的變化而修改軟件的過程稱為適應(yīng)性維護(hù)，其占整個(gè)維護(hù)工作的25% 3、完善性維護(hù)： 增加軟件功能、增強(qiáng)軟件性能、提高軟件運(yùn)行效率而進(jìn)行的維護(hù)活動(dòng)稱為完善性維護(hù)，其占整個(gè)維護(hù)工作的 50% 4、預(yù)防性維護(hù)： 為了提高軟件的可維護(hù)性和可靠性而對(duì)軟件進(jìn)行的修改稱為預(yù)防性維護(hù)，其占整個(gè)維護(hù)工作的 4% 例：軟件維護(hù)是指（ ） A、維護(hù)軟件正常運(yùn)行 B、軟件的配置更新 C、對(duì)軟件的改進(jìn)、適應(yīng)和完善 D、軟件開發(fā)期的一個(gè)階段 軟件生命周期中所花費(fèi)用最多的階段是（ ） A、詳細(xì)設(shè)計(jì) B、軟件編碼 C、軟件測(cè)試 D、軟件維護(hù) 數(shù)據(jù)庫原理基礎(chǔ) 一、基本概念： v 數(shù)據(jù)處理：是指將數(shù)據(jù)轉(zhuǎn)換成信息的過程 v 數(shù)據(jù)管理是指對(duì)數(shù)據(jù)的組織、分類、編碼、存儲(chǔ)、檢索和維護(hù)提供操作手段 其經(jīng)歷了以下階段： 1、人工管理 2、文件系統(tǒng) 3、數(shù)據(jù)庫系統(tǒng) 4、分布式數(shù)據(jù)庫系統(tǒng)階段 5、面向?qū)ο蟮臄?shù)據(jù)庫系統(tǒng)階段 v 數(shù)據(jù)庫(Database)：是指存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)設(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ā)出來的，面向某一類實(shí)際應(yīng)用的應(yīng)用軟件系統(tǒng)。 v v 數(shù)據(jù)庫管理系統(tǒng)(DBMS)： v v v v v v 對(duì)數(shù)據(jù)庫的建立、使用和維護(hù)進(jìn)行管理和配置的軟件系統(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)的特點(diǎn)： 實(shí)現(xiàn)數(shù)據(jù)共享、減少數(shù)據(jù)冗余 采用特定的數(shù)據(jù)模型 具有較高的數(shù)據(jù)獨(dú)立性 統(tǒng)一的數(shù)據(jù)控制功能 v 實(shí)體： 客觀存在并且可以相互區(qū)別的事物稱為實(shí)體。 v 實(shí)體的屬性：實(shí)體所具有的物性稱為實(shí)體的屬性。 v 實(shí)體集：同類型的實(shí)體的集合稱為實(shí)體集。 v 實(shí)體型：屬性的集合表示一種實(shí)體類型，稱為實(shí)體型。 例：數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)對(duì)數(shù)據(jù)庫中數(shù)據(jù)的查詢、插入、修改和刪除，這類功能稱為（ ） A、數(shù)據(jù)定義功能 B、數(shù)據(jù)管理功能 C、數(shù)據(jù)操縱功能 D、數(shù)據(jù)控制功能 v 聯(lián)系：實(shí)體之間的對(duì)應(yīng)關(guān)系。 聯(lián)系的類型: 1、一對(duì)一聯(lián)系：表現(xiàn)為主表中的每一條記錄只與相關(guān)表中的一條記錄相關(guān)聯(lián)。 例如： 班級(jí)與班長(zhǎng)， 學(xué)校與校長(zhǎng) 2、一對(duì)多聯(lián)系：表現(xiàn)為主表中的每一條記錄與相關(guān)表中的多條記錄相關(guān)聯(lián)。 例如： 班級(jí)與學(xué)生，部門與職工 3、多對(duì)多聯(lián)系：表現(xiàn)為一個(gè)表中的多個(gè)記錄在相關(guān)表中同樣有多個(gè)記錄相關(guān)聯(lián)。 例如： 學(xué)生與課程， 工程項(xiàng)目與零件 v 數(shù)據(jù)模型：不僅反映事物本身，還用來表示實(shí)體及實(shí)體之間聯(lián)系的方法。 1、層次模型：用樹形結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型稱為層次模型。 2、網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型稱為網(wǎng)狀模型。 3、關(guān)系模型：用二維表結(jié)構(gòu)來表示實(shí)體及實(shí)體之間的聯(lián)系的模型稱為關(guān)系模型。 一個(gè)二維表稱為一個(gè)關(guān)系，在VFP稱為數(shù)據(jù)表。一個(gè)關(guān)系不僅表示實(shí)體本身還表示實(shí)體之間的聯(lián)系。 例：用樹形結(jié)構(gòu)表示實(shí)體之間聯(lián)系的模型是（ ） A、關(guān)系模型 B、網(wǎng)狀模型 C、層次模型 D、以上三個(gè)都是 二、關(guān)系數(shù)據(jù)庫： v 元組(Record)：在一個(gè)關(guān)系中，水平方向的行稱為元組。在VFP中稱為記錄 v 屬性(Field)：一個(gè)二維表中垂直方向的列稱為屬性。在VFP中稱為字段名 v 域(Domain)：屬性的取值范圍。根據(jù)數(shù)據(jù)類型和寬度來決定的。 v 關(guān)鍵字(Primary Key)：其值能夠惟一標(biāo)識(shí)一個(gè)元組的屬性或?qū)傩缘慕M合。 注：關(guān)鍵字不能出現(xiàn)空值或重復(fù)值 v 外部關(guān)鍵字(Foreign Key)：如果表中的一個(gè)字段不是本表的主關(guān)鍵字或侯選關(guān)鍵字，而是另外一個(gè)表的主關(guān)鍵字或侯選關(guān)鍵字，這個(gè)字段在本表中稱為外部關(guān)鍵字。 v 關(guān)系性質(zhì): 二維表中元組的個(gè)數(shù)是有限的——元組個(gè)數(shù)有限性 二維表中元組均不相同——元組的惟一性 二維表中元組的次序可以任意交換——元組的次序無關(guān)性 二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)——元組分量的原子性 二維表中屬性名各不相同——屬性名惟一性 二維表中屬性與次序無關(guān)，可任意交換——屬性的次序無關(guān)性 例：關(guān)系數(shù)據(jù)模型中表示實(shí)體和實(shí)體間的聯(lián)系的結(jié)構(gòu)是（ ） A、樹型 B、網(wǎng)狀 C、二維表 D、對(duì)象 三、關(guān)系運(yùn)算： v 并（Union）：是由兩個(gè)關(guān)系的元組組成的集合。（兩個(gè)關(guān)系必須具有相同的關(guān)系模式） v 差（Difference）：若有兩個(gè)相同結(jié)構(gòu)的關(guān)系R和S，R差S的結(jié)果屬于R但不屬于S的元組組成的集合。 v 交（Intersection）：若有兩個(gè)相同的結(jié)構(gòu)關(guān)系R和S，交的結(jié)果為兩個(gè)關(guān)系共同的元組。 v 選擇（Selection）：從關(guān)系中找出滿足給定條件的元組的操作稱為選擇。 v 投影（Projection）：從關(guān)系模式中指定若干個(gè)屬性組成新的關(guān)系稱為投影。 v 聯(lián)接（Join）：是關(guān)系的橫向結(jié)合，關(guān)系模式改變了，是多個(gè)關(guān)系的關(guān)系模式的組合。聯(lián)接的結(jié)果是多個(gè)關(guān)系中滿足條件的元組。 第 38 頁，共 38 頁