計(jì)算機(jī)國(guó)二office公共基礎(chǔ)知識(shí)

1、第1章 數(shù)據(jù)結(jié)構(gòu)及算法（10-12分）考點(diǎn)：1. 算法(*)2. 數(shù)據(jù)結(jié)構(gòu)(*)3. 線性表及其順序存儲(chǔ)結(jié)構(gòu)(*)4. 棧和隊(duì)列(*)5. 線性鏈表(*)6. 樹(shù)及二叉樹(shù)(*)7. 查找技術(shù)(*)8. 排序技術(shù)(*)一、數(shù)據(jù)結(jié)構(gòu)及算法1、概念算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作2、數(shù)據(jù)的邏輯結(jié)構(gòu)l 線性結(jié)構(gòu)(例：一維數(shù)組、鏈表、棧、隊(duì)列、串、線性表)l 非線性結(jié)構(gòu)(例：多維數(shù)組、廣義表、樹(shù)、圖)3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(線性表)l 順序存儲(chǔ)方法：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的;線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的l 鏈接存儲(chǔ)

2、方法：邏輯上相鄰的結(jié)點(diǎn)，物理上也相鄰，存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的l 計(jì)算機(jī)中有數(shù)據(jù)進(jìn)行處理時(shí)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對(duì)程序的執(zhí)行效率有很大的關(guān)系l 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)。數(shù)組是數(shù)據(jù)的邏輯結(jié)構(gòu)，可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)表示l 線性鏈表：就是指線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈表4、算法的基本特征l 可行性：針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果l 確定性：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義性l 有窮性：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步驟之后終止，算法程序的運(yùn)行時(shí)間是有限的l 擁有足夠的情報(bào)：要使算法有效必需為算法提供足夠的情報(bào)當(dāng)算

3、法擁有足夠的情報(bào)時(shí)，此算法才最有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效5、算法的復(fù)雜度l 時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，是指執(zhí)行算法所需要的計(jì)算工作量，即算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)l 空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲(chǔ)空間6、順序表和鏈表的比較：基于空間的考慮：(1)順序表的存儲(chǔ)空間是靜態(tài)分配的，而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。(2)順序表占的存儲(chǔ)空間必須是連續(xù)的，而鏈表占的存儲(chǔ)空間可以是連續(xù)的，也可是不連續(xù)的棧頂 topABCD棧底 bottom入棧出棧二、棧l 棧實(shí)際也是線性表，只不過(guò)是一種特殊的線性表。棧稱為“先進(jìn)后出”表或“后進(jìn)先出”表，順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)l 棧的計(jì)算：求

4、棧中元素的個(gè)數(shù)：棧底元素棧頂元素l 棧是限定在一端進(jìn)行插入及刪除的線性表，允許插入元素的一端為棧頂，允許刪除元素的一端為棧底，棧頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素則總是最先被插入而最后被刪除的元素三、隊(duì)列l(wèi) 隊(duì)列也是一種運(yùn)算受限的線性表，是一種“先進(jìn)先出”，“后進(jìn)后出”的線性表， 順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)l 隊(duì)列的計(jì)算：求隊(duì)列中元素的個(gè)數(shù)：當(dāng)rear>front時(shí), rearfront 當(dāng)rear<front時(shí)，rear-front+m m(代表隊(duì)列的容量)l 循環(huán)隊(duì)列仍然是順序存儲(chǔ)結(jié)構(gòu)，是隊(duì)列常采用的形式入隊(duì)出隊(duì)Rear：隊(duì)尾front：隊(duì)頭l 隊(duì)列是

5、一種線性表，它允許在一端進(jìn)行插入，在另一端進(jìn)行刪除四、樹(shù)及二叉樹(shù)（非線性結(jié)構(gòu)）1、樹(shù)l 節(jié)點(diǎn)：樹(shù)中的每一個(gè)點(diǎn)叫做節(jié)點(diǎn)，分為根節(jié)點(diǎn)(0或1個(gè))、父節(jié)點(diǎn)、子節(jié)點(diǎn)ABCGDEF樹(shù)l 度：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度。一棵樹(shù)的度是指該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。度為1的點(diǎn)節(jié)叫做n1，度為2的節(jié)點(diǎn)叫做n2l 葉子節(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉子（沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)） 叫做n0l 深度：樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的高度或深度2、二叉樹(shù)ABCDEGF二叉樹(shù)l 二叉樹(shù)：由左樹(shù)和右樹(shù)組成，二叉樹(shù)的度<=2 ,當(dāng)度 為0時(shí)叫做空樹(shù)l 具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有5種形態(tài)l 滿二叉樹(shù)：指除最后一層外，每一層上的所有結(jié)點(diǎn)都 有兩

6、個(gè)子結(jié)點(diǎn)的二叉樹(shù)ABCDEFG滿二叉樹(shù)l 完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá) 到最大值，在最后一層上只缺少右邊的若 干結(jié)點(diǎn)ABCDEF完全二叉樹(shù)l 二叉樹(shù)的性質(zhì)：性質(zhì)1：二叉樹(shù)第k層上的結(jié)點(diǎn)數(shù)目最多為2k-1(k>=1)性質(zhì)2：深度為m的二叉樹(shù)至多有2m-1個(gè)結(jié)點(diǎn)(k>=1)性質(zhì)3：度為2的結(jié)點(diǎn)數(shù)為n2，度為0的節(jié)點(diǎn)叫做n0，則n0=n2+1（度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)多一個(gè)），整個(gè)二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)：n=n0+n1+n2性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分l 二叉樹(shù)的遍歷：遍歷：是指沿著某條搜索路線，依次對(duì)樹(shù)

7、中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)（1）前序遍歷：ABCDEGF訪問(wèn)根結(jié)點(diǎn)左子樹(shù)右子樹(shù)（2）中序遍歷：左子樹(shù)訪問(wèn)根結(jié)點(diǎn)右子樹(shù)（3）后序遍歷：左子樹(shù)右子樹(shù)訪問(wèn)根結(jié)點(diǎn)例：前序：ABDEGCF中序：DBGEACF后序：DGEBFCA五、排序l 冒泡排序：是最簡(jiǎn)單的一種交換類排序法。在最壞的情況下，對(duì)長(zhǎng)度為n的線性表排序，冒泡排序需要比較的次數(shù)為n(n-1)/2，其時(shí)間復(fù)雜度為O(n2)l 直接選擇排序：最壞情況要比較的次數(shù)為O(n2) ，其時(shí)間復(fù)雜度為O(n2)l 直接插入排序：最壞的情況下，時(shí)間復(fù)雜度為O(n2)l 快速排序：平均時(shí)間為O(nlog2n)，最壞情況下，時(shí)間效率為O(n2)l 堆排序：

8、最壞情況下，時(shí)間復(fù)雜度為O(nlog2n)各種內(nèi)部排序方法的比較排序方法最壞時(shí)間直接插入O(n2) 或 n(n-1)/2直接選擇O(n2) 或 n(n-1)/2冒 泡O(n2) 或 n(n-1)/2快 速O(n2) 或 n(n-1)/2堆O(nlog2n)六、查找l 順序查找：即適用順序存儲(chǔ)結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下需要比較n次l 二分查找：要求線性表是有序表，另外，二分查找只適用順序存儲(chǔ)結(jié)構(gòu)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上無(wú)法實(shí)現(xiàn)二分查找l 二分法查找只適用于順序存儲(chǔ)的有序表，在最壞情況下，二分查找需要比較log2n次l 在平均情況下，在順序存儲(chǔ)的線性表中查詢一

9、個(gè)元素，需要一半的元素，在最壞情況下，則需要比較線性表中所有的元素。第2章 程序設(shè)計(jì)基礎(chǔ)（2-4分）考點(diǎn)：1. 程序設(shè)計(jì)方法和風(fēng)格(*)2. 結(jié)構(gòu)化程序設(shè)計(jì)(*)3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)(*)一、程序設(shè)計(jì)方法及風(fēng)格1、程序設(shè)計(jì)指設(shè)計(jì)、編制、調(diào)試程序的方法和過(guò)程2、良好的設(shè)計(jì)風(fēng)格：（1）源程序文檔化：程序注釋的目的主要是方便其他人人閱讀程序（程序中要有必要的注釋）（2）數(shù)據(jù)說(shuō)明的方法：數(shù)據(jù)說(shuō)明的次序要規(guī)范化，增強(qiáng)可讀性（程序的可讀性好）（3）語(yǔ)句的結(jié)構(gòu)：一行只寫一條語(yǔ)句；避免使用臨時(shí)變量；避免彩復(fù)雜條件語(yǔ)句；應(yīng)使用庫(kù)函數(shù)；程序模塊化；確保模塊獨(dú)立；不要修補(bǔ)不良結(jié)構(gòu)的程序，避免濫用goto語(yǔ)句（4

10、）輸入輸出：對(duì)輸入數(shù)據(jù)檢查合法性；排列合理；輸入格式簡(jiǎn)單；應(yīng)允許使用自由格式和默認(rèn)值；應(yīng)在屏幕上給出狀態(tài)信息（輸入數(shù)據(jù)前要有提示信息）*模塊設(shè)計(jì)要保證低耦合、高內(nèi)聚二、結(jié)構(gòu)化程序設(shè)計(jì)1、結(jié)構(gòu)化程序設(shè)計(jì)的原則：自頂向下、逐步求精、模塊化及限制使用goto語(yǔ)句2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序、選擇、循環(huán)結(jié)構(gòu)三、面向?qū)ο蟮某绦蛟O(shè)計(jì)1、對(duì)象的特點(diǎn)：標(biāo)識(shí)唯一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性好（1）標(biāo)識(shí)唯一性：對(duì)象是可以區(qū)分的（2）分類性：具有相同屬性和操作的對(duì)象可以抽象成一個(gè)類（3）多態(tài)性：同一個(gè)操作可以是不同對(duì)象的行為，是指在類中定義名稱相同的函數(shù)，但是這些函數(shù)的參數(shù)或者返回值的類型不同（4）封裝

11、性：對(duì)外部只提供接口，方便用戶調(diào)用，內(nèi)部實(shí)現(xiàn)對(duì)外不可見(jiàn)，可實(shí)現(xiàn)信息隱蔽，是指將對(duì)象分為內(nèi)部實(shí)現(xiàn)和外部接口兩個(gè)部分（5）模塊獨(dú)立性好：對(duì)象內(nèi)部各種元素彼此結(jié)合緊密，內(nèi)聚性好2、類：是具有共同屬性、共同方法的一組對(duì)象的集合，是關(guān)于對(duì)象的抽象描述，反映屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，類是對(duì)象的抽象，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例3、繼承：是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)地定義它們4、多態(tài)性：對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致完全不同的行為，該現(xiàn)象稱為多態(tài)性第3章軟件工程基礎(chǔ)（8分）考點(diǎn)：1. 軟件工程基本概念(*)2. 結(jié)構(gòu)化分析方法(*)3. 結(jié)構(gòu)化設(shè)

12、計(jì)方法(*)4. 軟件測(cè)試(*)5. 程序的調(diào)試(*)一、基本概念l 軟件：包括程序、數(shù)據(jù)、文檔的完整集合l 軟件按功能分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件二、軟件工程l 軟程包含3個(gè)要素：方法、工具和過(guò)程方法是完成軟件開(kāi)發(fā)各項(xiàng)任務(wù)的技術(shù)手段工具支持軟件的開(kāi)發(fā)、管理、文檔生成過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)的控制、管理l 軟件工程研究的主要內(nèi)容是軟件開(kāi)發(fā)技術(shù)和軟件開(kāi)發(fā)管理兩個(gè)方面。l 軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性 抽象：采用分層抽象、自頂向下、逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性信息隱蔽：將模塊設(shè)計(jì)成“黑箱”，實(shí)現(xiàn)的細(xì)節(jié)隱藏在模塊內(nèi)部。這就是信息封裝

13、，使用及實(shí)現(xiàn)分離的原則模塊化：有助于信息隱蔽和抽象，有助于表示復(fù)雜的系統(tǒng)局部化：保證模塊之間具有松散的耦合關(guān)系，模塊內(nèi)部具有較強(qiáng)的內(nèi)聚，這有助于控制分解的復(fù)雜性確定性：軟件開(kāi)發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定的、無(wú)歧義的、規(guī)范的可驗(yàn)證性：開(kāi)發(fā)大型的軟件系統(tǒng)需要對(duì)系統(tǒng)自頂向下、逐層分解，以確保系統(tǒng)的正確性三、軟件工程過(guò)程l 所進(jìn)行的基本活動(dòng)主要包含4種：軟件規(guī)格說(shuō)明、軟件開(kāi)發(fā)、軟件確認(rèn)、軟件演進(jìn)軟件規(guī)格說(shuō)明：規(guī)定軟件的功能以及運(yùn)行的限制軟件開(kāi)發(fā)：產(chǎn)生滿足規(guī)格說(shuō)明的軟件軟件確認(rèn)：確認(rèn)能夠滿足用戶提出的要求四、軟件生命周期l 軟件生存周期：通常把軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用、退役的過(guò) 程稱

14、為軟件生命周期l 軟件生命周期分為3個(gè)時(shí)期共8個(gè)階段：1. 軟件定義時(shí)期：包括問(wèn)題定義、可行性和需求分析3個(gè)階段2. 軟件開(kāi)發(fā)期：包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)和測(cè)試4個(gè)階段3. 運(yùn)行維護(hù)期：即運(yùn)行維護(hù)階段l 軟件生命周期各階段的主要任務(wù)：1. 問(wèn)題定義：2. 可行性研究及計(jì)劃制定：3. 需求分析：對(duì)待開(kāi)發(fā)軟件提出需求進(jìn)行分析并給出詳細(xì)定義。編寫軟件規(guī)格說(shuō) 明書及初步的用戶手冊(cè)，提交評(píng)審。4. 軟件設(shè)計(jì)：通常又分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)階段，給出軟件的結(jié)構(gòu)、模塊 的劃分、功能的分配以及處理流程。該階段提交評(píng)審的文檔有概要 設(shè)計(jì)說(shuō)明書、詳細(xì)設(shè)計(jì)說(shuō)明書和測(cè)試計(jì)劃初稿5. 軟件實(shí)現(xiàn)：在軟件設(shè)計(jì)的基礎(chǔ)上

15、編寫程序。該階段完成的文檔有用戶手冊(cè)、操 作手冊(cè)等面向用戶的文檔，以及為下一步做準(zhǔn)備而編寫的單元測(cè)試 計(jì)劃6. 軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。編寫測(cè)試分 析報(bào)告7. 運(yùn)行維護(hù)：五、結(jié)構(gòu)化分析方法1、需求分析和需求分析方法(1)、需求分析階段的工作：l 需求獲取l 需求分析l 需求編寫規(guī)格說(shuō)明書l 需求評(píng)審(2)、需求分析方法：常用見(jiàn)的需分析方法：（1） 結(jié)構(gòu)化分析方法（2） 面向?qū)ο蟮姆治龇椒ǎ悍譃殪o態(tài)分析方法和動(dòng)態(tài)分析方法2、結(jié)構(gòu)化分析方法使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語(yǔ)、判定表和判定樹(shù)等工具，實(shí)質(zhì)是眼于數(shù)據(jù)流、自頂向下、對(duì)系統(tǒng)的功能進(jìn)行逐層分

16、解、以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型3、結(jié)構(gòu)化分析方法的常用工具（1）數(shù)據(jù)流圖（DFD）l 數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，它是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用l 程序流程圖、N-S圖、PAD圖是詳細(xì)設(shè)計(jì)過(guò)程中常用的圖形工具數(shù)據(jù)流： 加工： (又稱轉(zhuǎn)換) 存儲(chǔ)文件： (又稱數(shù)據(jù)源)源/潭： (表示系統(tǒng)和環(huán)境的接口)*請(qǐng)注意：數(shù)據(jù)流圖及程序流程圖中表示的控制流有本質(zhì)不同，千萬(wàn)不要混淆（2）數(shù)據(jù)字典：其中有4種類型的條目：數(shù)據(jù)流、數(shù)據(jù)項(xiàng)、數(shù)據(jù)存儲(chǔ)、加工，對(duì)數(shù)據(jù)流圖中所有元素的定義的集合，是結(jié)構(gòu)化分析的核心。它以一種準(zhǔn)備的，無(wú)二義性的說(shuō)明方式為系統(tǒng)的分析、設(shè)計(jì)維護(hù)提供了

17、有關(guān)元素的一致性定義和詳細(xì)的描述。4、軟件需求規(guī)格說(shuō)明書軟件需求規(guī)格說(shuō)明書的標(biāo)準(zhǔn)：正確性、無(wú)歧義性、完整性、可驗(yàn)證性、一致性、可理解性、可修改性、可追蹤性六、結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)概述（1）軟件設(shè)計(jì)的基礎(chǔ)：從工程管理的角度來(lái)看可分為兩步：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)l 概要設(shè)計(jì)：將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)l 詳細(xì)設(shè)計(jì)：確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)l 結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系l 數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義l 接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件及人之間如何通信l 過(guò)程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)

18、部件轉(zhuǎn)換成軟件的過(guò)程描述（2）軟件設(shè)計(jì)的基本原理和原則：模塊化 抽象 信息隱藏 模塊獨(dú)立性模塊獨(dú)立性：一般來(lái)說(shuō)，要求模塊之間的耦合盡可能弱，即模塊盡可能獨(dú)立，且要求模塊的內(nèi)聚程度盡可能高。內(nèi)聚性和耦合性是一個(gè)問(wèn)題的兩個(gè)方向，耦合性能程度弱的模塊，其內(nèi)聚程序一定高內(nèi)聚性：是一個(gè)模塊內(nèi)部包含的信息，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的；是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程序的度量耦合性：是模塊間互相連接的緊密程度的度量對(duì)于模塊進(jìn)行設(shè)計(jì)時(shí)，應(yīng)該盡量做到高內(nèi)聚、低耦合，即減弱模塊之間的耦和性和提高模塊的內(nèi)聚性，這樣有利于提高模塊的獨(dú)立性2、概要設(shè)計(jì)（1）編寫概要設(shè)計(jì)文檔：概要設(shè)計(jì)階段文檔有

19、概要設(shè)計(jì)說(shuō)明書、數(shù)據(jù)庫(kù)設(shè)計(jì)說(shuō)明書和集成測(cè)試計(jì)劃等。（2）概要設(shè)計(jì)文檔評(píng)審：在文檔編寫完成后，要對(duì)設(shè)計(jì)部分是否完整地實(shí)現(xiàn)了需求中規(guī)定 的功能、性能等要求，設(shè)計(jì)方案的可行性，關(guān)鍵的處理及內(nèi)外部接口定義正確性、有效性，各部分之間的一致性等進(jìn)行評(píng)審。ABCDEGF3、詳細(xì)設(shè)計(jì)任務(wù)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確實(shí)實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)程序流程圖（PFD）：l 方框表示一個(gè)加工步驟l 菱形表示一個(gè)邏輯條件l 箭頭表示控制流4、軟件系統(tǒng)結(jié)構(gòu)圖的寬度：整體控制跨度（最大塊數(shù)的層）的顯示(如右圖，寬度是4)七、軟件測(cè)試1、軟件測(cè)試目的軟件測(cè)試就是在軟件投入運(yùn)行之前，盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤,發(fā)現(xiàn)程序中的錯(cuò)誤2

20、、軟件測(cè)試方法根據(jù)軟件是否需要被執(zhí)行，可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試，如果按照功能劃分，可以分為白盒測(cè)試和黑盒測(cè)試（1）靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等，是指不在計(jì)算機(jī)上運(yùn)行被測(cè)試程序，而采用其他手段來(lái)達(dá)到對(duì)程序進(jìn)行檢測(cè)的目的，包括人工測(cè)試和計(jì)算機(jī)輔助靜態(tài)分析方法。（2）動(dòng)態(tài)測(cè)試：主要通過(guò)人工進(jìn)行分析。通過(guò)運(yùn)行軟件來(lái)檢驗(yàn)軟件中的動(dòng)態(tài)行為和運(yùn)行結(jié)果的正確性，并用所設(shè)計(jì)的測(cè)試用倒對(duì)程序進(jìn)行檢測(cè)的方法（3）白盒測(cè)試（結(jié)構(gòu)測(cè)試）：是把程序看成裝在一只透明的白盒子里，測(cè)試者完成了解程序的結(jié)構(gòu)和處理過(guò)程，保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次；驗(yàn)

21、證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。主要方法有邏輯覆蓋、基本路徑測(cè)試等。（4）黑盒測(cè)試（功能測(cè)試）：把程序看成一只黑盒子，測(cè)試者完成不了解，或不考慮程序的結(jié)構(gòu)和處理過(guò)程，也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試，測(cè)試時(shí)不考慮程序內(nèi)部細(xì)節(jié)、結(jié)構(gòu)和實(shí)現(xiàn)方式、僅檢驗(yàn)程序結(jié)果及說(shuō)明書的一致性。測(cè)試方法主要有：等價(jià)劃分法、邊界分析法、錯(cuò)誤推測(cè)法、因果圖等，主要用于軟件確認(rèn)測(cè)試3、軟件測(cè)試的實(shí)施（1）單元測(cè)試：也稱模塊測(cè)試，模塊是軟件設(shè)計(jì)的最小單位，單元測(cè)試是對(duì)模塊進(jìn)行正確性的檢驗(yàn)。可以采用靜態(tài)測(cè)試或者動(dòng)態(tài)測(cè)試，動(dòng)態(tài)測(cè)試通常以白盒測(cè)試為主，測(cè)試其結(jié)構(gòu)，以黑盒測(cè)試法為輔，測(cè)試其功能（2）集成測(cè)試：也稱組裝測(cè)試，它是對(duì)各模塊按照

22、設(shè)計(jì)要求組裝成的程序進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)及接口有關(guān)的錯(cuò)誤（3）確認(rèn)測(cè)試的任務(wù)是檢驗(yàn)軟件的功能、性能及其他特征是否及用戶的需求一致，它是以需求規(guī)格說(shuō)明書作為依據(jù)的測(cè)試。確認(rèn)測(cè)試通常采用黑盒測(cè)試（4）系統(tǒng)測(cè)試：目的是在真實(shí)的系統(tǒng)工作環(huán)境下檢驗(yàn)軟件是否能及系統(tǒng)正確連接，發(fā)現(xiàn)軟件及系統(tǒng)需求不一致的地方l 測(cè)試用例是為測(cè)試設(shè)計(jì)的數(shù)據(jù)，測(cè)試用倒由測(cè)試輸入數(shù)據(jù)及之對(duì)應(yīng)的預(yù)期輸出結(jié)果兩部分組成。測(cè)試用倒的格式為（輸入值集），（輸出值集）八、程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤,改正以后還需要再測(cè)試第4章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)（8-10分）考點(diǎn)：1. 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念(*)2. 數(shù)據(jù)模型(*)3.

23、 關(guān)系代數(shù)(*)4. 數(shù)據(jù)庫(kù)設(shè)計(jì)及管理(*)一、數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)（1）數(shù)據(jù)庫(kù)（DB）（2）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：數(shù)據(jù)庫(kù)語(yǔ)言：l 數(shù)據(jù)定義語(yǔ)言（DDL）：負(fù)責(zé)數(shù)據(jù)的模式定義和數(shù)據(jù)的物理存取構(gòu)建l 數(shù)據(jù)庫(kù)操縱語(yǔ)言（DML）：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪除、改操作l 數(shù)據(jù)控制語(yǔ)言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義及檢查以及并發(fā)控制、數(shù)據(jù)恢復(fù)等功能（3）數(shù)據(jù)庫(kù)系統(tǒng)（DBS）三者關(guān)系：DBS包含DB和DBMS2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展（1）、人工管理階段：在工人管理階段，數(shù)據(jù)不保存，沒(méi)有對(duì)數(shù)據(jù)進(jìn)行管理的軟件，數(shù)據(jù)不能共享（2）、文件系統(tǒng)階段：這個(gè)時(shí)期數(shù)據(jù)管理的特點(diǎn)是：

24、數(shù)據(jù)需要長(zhǎng)期保留在外存儲(chǔ)器中供反復(fù)使用；程序和數(shù)據(jù)之間有了一定的獨(dú)立性；文件夾形式已經(jīng)多樣化；數(shù)據(jù)的存儲(chǔ)基本上以記錄為單位，提供了簡(jiǎn)單的數(shù)據(jù)共享及數(shù)據(jù)管理能力，但它不能提供完整的、統(tǒng)一的管理和共享數(shù)據(jù)的能力（3）、數(shù)據(jù)庫(kù)系統(tǒng)階段：l 實(shí)現(xiàn)了數(shù)據(jù)共享，減少了數(shù)據(jù)冗余；l 采用了特定的數(shù)據(jù)模型；l 真正統(tǒng)一的數(shù)據(jù)控制功能，能夠?yàn)槎鄠€(gè)用戶和應(yīng)用程序提供共享資源l 具有數(shù)據(jù)的集成性（4）、分布式數(shù)據(jù)庫(kù)系統(tǒng)階段3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)數(shù)據(jù)庫(kù)管理系統(tǒng)是數(shù)據(jù)庫(kù)系統(tǒng)的核心數(shù)據(jù)庫(kù)系統(tǒng)特點(diǎn)：l 數(shù)據(jù)高度集成l 數(shù)據(jù)統(tǒng)一管理控制l 數(shù)據(jù)獨(dú)立性l 共享性及低冗余性4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系l 概念模式：是數(shù)據(jù)庫(kù)系統(tǒng)

25、中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，此種描述是一種抽象的描述，不但要描述概念記錄類型，而且要描述記錄之間的聯(lián)系、所允許的操作、數(shù)據(jù)的一致性、安全性和其他數(shù)據(jù)控制方面的要求l 外模式：也稱為數(shù)據(jù)庫(kù)的用戶式或子模式，是從概念模式導(dǎo)出的子模式，用戶可以通過(guò)子模式描述語(yǔ)言來(lái)描述用戶級(jí)數(shù)據(jù)庫(kù)的記錄，還可以利用數(shù)據(jù)語(yǔ)言對(duì)這些記錄進(jìn)行操作。用戶使用數(shù)據(jù)操縱語(yǔ)言對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作，實(shí)際上是對(duì)外模式的外部記錄進(jìn)行操作l 內(nèi)模式：也稱為數(shù)據(jù)庫(kù)的物理式或存儲(chǔ)模式。它是由系統(tǒng)程序員設(shè)計(jì)和組織的、是系統(tǒng)程序員所看到和所理解的數(shù)據(jù)庫(kù)，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)及物理存取方法。DBMS一般提供相關(guān)的內(nèi)模式描述語(yǔ)言（DLL）l 數(shù)據(jù)庫(kù)系

26、統(tǒng)一般分為物理獨(dú)立性及邏輯獨(dú)立性兩級(jí)。物理獨(dú)立性指數(shù)據(jù)的物理結(jié)構(gòu)的改變。在數(shù)據(jù)系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)并不一定及邏輯結(jié)構(gòu)一致概念模式是一個(gè)全局模式，而外模式是用戶的局部模式，內(nèi)模式處于底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲(chǔ)形式，概念模式處于中層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層，它反映了用戶對(duì)數(shù)據(jù)的要求二、數(shù)據(jù)模型l 分為層次模型、網(wǎng)狀模型、關(guān)系模型實(shí)體集l 基本概念：一對(duì)一、一對(duì)多、多對(duì)多l(xiāng) E-R模型：屬性矩形：實(shí)體集橢圓：屬性菱形：聯(lián)系聯(lián)系1、層次模型層次模型的結(jié)構(gòu)是樹(shù)形結(jié)構(gòu)2、網(wǎng)狀模型用網(wǎng)狀結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型3、關(guān)系模型l 關(guān)系模型采用二維表來(lái)表示，每行數(shù)據(jù)稱為元組，列叫做屬性l 關(guān)系模型允許定義三類數(shù)據(jù)約束，它們是實(shí)體完整性約束、參照完整性約束以及用戶定義的完整性約束三、關(guān)系代數(shù)1、傳統(tǒng)的集合運(yùn)算并、交、差、笛卡爾積（1）并（）：由2個(gè)關(guān)系運(yùn)算生成第3個(gè)關(guān)系，要求兩個(gè)關(guān)系的元數(shù)（字段名稱）必須相同，元組（記錄）的個(gè)數(shù)相加SAB1335RABm1n2TABm1n21335例：RS（2）交（）：由2個(gè)關(guān)系運(yùn)算生成第3個(gè)關(guān)系，要求兩個(gè)關(guān)系的元數(shù)（字段名稱）必須相同，第3個(gè)關(guān)系中只保留前2個(gè)關(guān)系中相同的元組例：RSRABm1n2