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

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

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

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

5、ront:隊(duì)頭 Rear：隊(duì)尾 四、樹(shù)與二叉樹(shù)（非線(xiàn)性結(jié)構(gòu)） 1、樹(shù) 節(jié)點(diǎn)：樹(shù)中的每一個(gè)點(diǎn)叫做節(jié)點(diǎn)，分為 根節(jié)點(diǎn)（0或1個(gè)）、父節(jié)點(diǎn)、子節(jié)點(diǎn) 度：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。一棵樹(shù)的度是指該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。度為1的 點(diǎn)節(jié)叫做n 1,度為2的節(jié)點(diǎn)叫做n2 葉子節(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱(chēng)為葉子（沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)） 深度：樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的高度或深度 2、二叉樹(shù) 二叉樹(shù)：由左樹(shù)和右樹(shù)組成，二叉樹(shù)的度=1） 性質(zhì)2：深度為m的二叉樹(shù)至多有 21個(gè)結(jié)點(diǎn)（k=1） 性質(zhì)3:度為2的結(jié)點(diǎn)數(shù)為n2，度為0的節(jié)點(diǎn)叫做n0. （度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)多一個(gè)），整個(gè)二叉樹(shù)節(jié) 點(diǎn)個(gè)數(shù)：n=n0+n1

6、+n2 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度至少為log 2n+1，其中 Iog2n表示取log 2n的整數(shù)部分 二叉樹(shù)的遍歷： 遍歷：是指沿著某條搜索路線(xiàn)，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪(fǎng)問(wèn) （1）前序遍歷： 訪(fǎng)問(wèn)根結(jié)點(diǎn)一一左子樹(shù)一一右子樹(shù) （2）中序遍歷： 左子樹(shù)一一訪(fǎng)問(wèn)根結(jié)點(diǎn)一一右子樹(shù) （3）后序遍歷： 左子樹(shù)一一右子樹(shù)一一訪(fǎng)問(wèn)根結(jié)點(diǎn) 例：前序：ABDEGCF 中序：DBGEACF 后序：DGEBFCA 五、排序 冒泡排序：是最簡(jiǎn)單的一種交換類(lèi)排序法。在最壞的情況下，對(duì)長(zhǎng)度為n的線(xiàn)性表排序，冒泡排 序需要比較的次數(shù)為 n(n-1)/2 ，其時(shí)間復(fù)雜度為0(n2) 直接選擇排序：最

7、壞情況要比較的次數(shù)為0(n2)，其時(shí)間復(fù)雜度為0(n2) 2 直接插入排序：最壞的情況下，時(shí)間復(fù)雜度為0( n) 快速排序：平均時(shí)間為O(nlog n)，最壞情況下，時(shí)間效率為0(n) 堆排序：最壞情況下，時(shí)間復(fù)雜度為0(n Iog2 n) 各種內(nèi)部排序方法的比較 排序方法 最壞時(shí)間 直接插入 0( n2)或 n(n-1)/2 直接選擇 0(n)或 n(n-1)/2 冒泡 0(n)或 n(n-1)/2 快速 0(n)或 n(n-1)/2 堆 0(nlog 2n) 六、查找 順序查找：即適用順序存儲(chǔ)結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)長(zhǎng)度為n的線(xiàn)性表進(jìn)行順序查找，在 最壞情況下需要比較 n次 二分查找：

8、要求線(xiàn)性表是有序表，另外，二分查找只適用順序存儲(chǔ)結(jié)構(gòu)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上無(wú)法 實(shí)現(xiàn)二分查找 二分法查找只適用于順序存儲(chǔ)的有序表，在最壞情況下，二分查找需要比較log 2n次 在平均情況下，在順序存儲(chǔ)的線(xiàn)性表中查詢(xún)一個(gè)元素，需要一半的元素，在最壞情況下，則需要 比較線(xiàn)性表中所有的元素。 第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）源程序文檔化：程序注釋的目的主要是方便其他人人閱讀程序（程序中要有必要的注釋?zhuān)?/p>

9、 （2 ）數(shù)據(jù)說(shuō)明的方法：數(shù)據(jù)說(shuō)明的次序要規(guī)范化，增強(qiáng)可讀性（程序的可讀性好） （3）語(yǔ)句的結(jié)構(gòu)：一行只寫(xiě)一條語(yǔ)句；避免使用臨時(shí)變量；避免彩復(fù)雜條件語(yǔ)句；應(yīng)使用庫(kù)函數(shù)； 程序模塊化；確保模塊獨(dú)立；不要修補(bǔ)不良結(jié)構(gòu)的程序，避免濫用goto語(yǔ)句 （4 ）輸入輸出：對(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ì)象的

10、特點(diǎn)： 標(biāo)識(shí)唯一性、分類(lèi)性、多態(tài)性、封裝性、模塊獨(dú)立性好 （1）標(biāo)識(shí)唯一性：對(duì)象是可以區(qū)分的 （2）分類(lèi)性：具有相同屬性和操作的對(duì)象可以抽象成一個(gè)類(lèi) （3 ）多態(tài)性：同一個(gè)操作可以是不同對(duì)象的行為，是指在類(lèi)中定義名稱(chēng)相同的函數(shù)，但是這些 函數(shù)的參數(shù)或者返回值的類(lèi)型不同 （4）封裝性：對(duì)外部只提供接口，方便用戶(hù)調(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、類(lèi)： 是具有共同屬性、共同方法的一組對(duì)象的集合，是關(guān)于對(duì)象的抽象描述，反映屬于該對(duì)象類(lèi)型的所有 對(duì)象的性質(zhì)，類(lèi)是對(duì)象的抽象，而一個(gè)對(duì)象則是其

11、對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例 3、繼承： 是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)地定義它們 4、多態(tài)性： 對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致完全不同的行為，該現(xiàn)象 稱(chēng)為多態(tài)性 第3章軟件工程基礎(chǔ)（8分） 考點(diǎn)： 1. 軟件工程基本概念（* ） 2. 結(jié)構(gòu)化分析方法（* ） 3. 結(jié)構(gòu)化設(shè)計(jì)方法（*） 4. 軟件測(cè)試（* ） 5. 程序的調(diào)試（*） 、基本概念 軟件：包括程序、數(shù)據(jù)、文檔 的完整集合 軟件按功能分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件 、軟件工程 軟程包含3個(gè)要素：方法、工具和過(guò)程 方法是完成軟件開(kāi)發(fā)各項(xiàng)任務(wù)的技術(shù)手段 工具支持軟件的開(kāi)發(fā)、管理、文檔生成 過(guò)程

12、支持軟件開(kāi)發(fā)的各個(gè)環(huán)的控制、管理 軟件工程研究的主要內(nèi)容是軟件開(kāi)發(fā)技術(shù)和軟件開(kāi)發(fā)管理兩個(gè)方面。 軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性 抽象：采用分層抽象、自頂向下、逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性 信息隱蔽：將模塊設(shè)計(jì)成“黑箱”，實(shí)現(xiàn)的細(xì)節(jié)隱藏在模塊內(nèi)部。這就是信息封裝，使用與 實(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)自頂向

13、下、逐層分解，以確保系統(tǒng)的正確性 三、軟件工程過(guò)程 所進(jìn)行的基本活動(dòng)主要包含 4種：軟件規(guī)格說(shuō)明、軟件開(kāi)發(fā)、軟件確認(rèn)、軟件演進(jìn) 軟件規(guī)格說(shuō)明：規(guī)定軟件的功能以及運(yùn)行的限制 軟件開(kāi)發(fā)：產(chǎn)生滿(mǎn)足規(guī)格說(shuō)明的軟件 軟件確認(rèn)：確認(rèn)能夠滿(mǎn)足用戶(hù)提出的要求 四、軟件生命周期 軟件生存周期：通常把軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用、退役的過(guò) 程稱(chēng)為軟件生命周期 軟件生命周期分為 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ù)階段 軟件生命周期各階段的主要任務(wù)： 1. 問(wèn)題定義：

14、 2. 可行性研究與計(jì)劃制定： 3. 需求分析：對(duì)待開(kāi)發(fā)軟件提出需求進(jìn)行分析并給出詳細(xì)定義。編寫(xiě)軟件規(guī)格說(shuō) 明書(shū)及初步的用戶(hù)手冊(cè)，提交評(píng)審。 4. 軟件設(shè)計(jì)：通常又分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)階段，給出軟件的結(jié)構(gòu)、模塊 的劃分、功能的分配以及處理流程。該階段提交評(píng)審的文檔有概要 設(shè)計(jì)說(shuō)明書(shū)、詳細(xì)設(shè)計(jì)說(shuō)明書(shū)和測(cè)試計(jì)劃初稿 5. 軟件實(shí)現(xiàn)：在軟件設(shè)計(jì)的基礎(chǔ)上編寫(xiě)程序。該階段完成的文檔有用戶(hù)手冊(cè)、操 作手冊(cè)等面向用戶(hù)的文檔，以及為下一步做準(zhǔn)備而編寫(xiě)的單元測(cè)試 計(jì)劃 6. 軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。編寫(xiě)測(cè)試分 析報(bào)告 7. 運(yùn)行維護(hù)： 五、結(jié)構(gòu)化分析方法 1需求分析和需求

15、分析方法 （1）、需求分析階段的工作： 需求獲取 需求分析 需求編寫(xiě)規(guī)格說(shuō)明書(shū) 需求評(píng)審 （2）、需求分析方法： 常用見(jiàn)的需分析方法： （1）結(jié)構(gòu)化分析方法 （2）面向?qū)ο蟮姆治龇椒ǎ悍譃?靜態(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)行逐層分解、以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型 3、結(jié)構(gòu)化分析方法的常用工具 （1）數(shù)據(jù)流圖（DFD 數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，它是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的 運(yùn)用 程序流程圖、N-S圖、PAD圖是詳細(xì)設(shè)計(jì)過(guò)

16、程中常用的圖形工具 數(shù)據(jù)流： 加工：-（又稱(chēng)轉(zhuǎn)換） 存儲(chǔ)文件：（又稱(chēng)數(shù)據(jù)源） 源/ 潭: 表示系統(tǒng)和環(huán)境的接口 請(qǐng)注意：數(shù)據(jù)流圖與程序流程圖中表示的控制流有本質(zhì)不同，千萬(wàn)不要混淆 （2）數(shù)據(jù)字典：其中有 4種類(lèi)型的條目：數(shù)據(jù)流、數(shù)據(jù)項(xiàng)、數(shù)據(jù)存儲(chǔ)、加工，對(duì)數(shù)據(jù)流圖中所有元 素的定義的集合，是結(jié)構(gòu)化分析的核心。它以一種準(zhǔn)備的，無(wú)二義性的說(shuō)明方式為系統(tǒng)的分析、 設(shè)計(jì)維護(hù)提供了有關(guān)元素的一致性定義和詳細(xì)的描述。 4、軟件需求規(guī)格說(shuō)明書(shū) 軟件需求規(guī)格說(shuō)明書(shū)的標(biāo)準(zhǔn)：正確性、無(wú)歧義性、完整性、可驗(yàn)證性、一致性、可理解性、可修改性、 可追蹤性 六、結(jié)構(gòu)化設(shè)計(jì)方法 1、軟件設(shè)計(jì)概述 概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)

17、包括軟 （1、軟件設(shè)計(jì)的基礎(chǔ)：從工程管理的角度來(lái)看可分為兩步: 件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)概要設(shè)計(jì)：將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu) 詳細(xì)設(shè)計(jì)：確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu) 結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系 數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義 接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信 過(guò)程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述 （2 ）軟件設(shè)計(jì)的基本原理和原則： 模塊化抽象信息隱藏 模塊獨(dú)立性 模塊獨(dú)立性：一般來(lái)說(shuō)，要求模塊之間的耦合盡可能弱，即模塊盡可能獨(dú)立，且要求模塊的 內(nèi)聚程度盡可能高。內(nèi)聚性和耦合性是一個(gè)問(wèn)題的兩個(gè)方

18、向，耦合性能程度弱 的模塊，其內(nèi)聚程序一定高 內(nèi)聚性：是一個(gè)模塊內(nèi)部包含的信息，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪(fǎng)問(wèn)的； 是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程序的度量 耦合性：是模塊間互相連接的緊密程度的度量 對(duì)于模塊進(jìn)行設(shè)計(jì)時(shí)，應(yīng)該盡量做到高內(nèi)聚、低耦合，即減弱模塊之間的耦和性和提高模塊 的內(nèi)聚性，這樣有利于提高模塊的獨(dú)立性 2、概要設(shè)計(jì) （1 ）編寫(xiě)概要設(shè)計(jì)文檔：概要設(shè)計(jì)階段文檔有概要設(shè)計(jì)說(shuō)明書(shū)、數(shù)據(jù)庫(kù)設(shè)計(jì)說(shuō)明書(shū)和集成測(cè)試計(jì)劃 等。 的功能、 （2）概要設(shè)計(jì)文檔評(píng)審：在文檔編寫(xiě)完成后，要對(duì)設(shè)計(jì)部分是否完整地實(shí)現(xiàn)了需求中規(guī)定 的一致性等進(jìn)行評(píng)審。 3、詳細(xì)設(shè)計(jì) 性能等要求，設(shè)計(jì)方案

19、的可行性，關(guān)鍵的處理及內(nèi)外部接口定義正確性、有效性，各部分之間 程序流程圖（PFD： 任務(wù)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確實(shí)實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu) 方框表示一個(gè)加工步驟 菱形表示一個(gè)邏輯條件 箭頭表示控制流 4、軟件系統(tǒng)結(jié)構(gòu)圖的寬度：整體控制跨度（最大塊數(shù)的層）的顯示 七、軟件測(cè)試 1、軟件測(cè)試目的 軟件測(cè)試就是在軟件投入運(yùn)行之前，盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤，發(fā)現(xiàn)程序中的錯(cuò)誤 2、軟件測(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è)試程 序，而采用其他

20、手段來(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)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。 主要方法有邏輯覆蓋、基本路徑測(cè)試等。 （4 ）黑盒測(cè)試（功能測(cè)試）：把程序看成一只黑盒子，測(cè)試者完成不了解，或不考慮程序的結(jié)構(gòu)和處 理過(guò)程，也稱(chēng)為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試

21、，測(cè)試時(shí)不考慮程序內(nèi)部細(xì)節(jié)、 結(jié)構(gòu)和實(shí)現(xiàn)方式、僅檢驗(yàn)程序結(jié)果與說(shuō)明書(shū)的一致性。 測(cè)試方法主要有：等價(jià)劃分法、邊界分析法、錯(cuò)誤推測(cè)法、因果圖等， 主要用于軟件確認(rèn)測(cè)試 3、軟件測(cè)試的實(shí)施 （1）單元測(cè)試：也稱(chēng)模塊測(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è)試：也稱(chēng)組裝測(cè)試，它是對(duì)各模塊按照設(shè)計(jì)要求組裝成的程序進(jìn)行測(cè)試，主要目的是發(fā) 現(xiàn)與接口有關(guān)的錯(cuò)誤 （3）確認(rèn)測(cè)試的任務(wù)是檢驗(yàn)軟件的功能、性能及其他特征是否與用戶(hù)的需求一致，它是以需求規(guī)格 說(shuō)明書(shū)作為依據(jù)的測(cè)試

22、。確認(rèn)測(cè)試通常采用黑盒測(cè)試 （4）系統(tǒng)測(cè)試：目的是在真實(shí)的系統(tǒng)工作環(huán)境下檢驗(yàn)軟件是否能與系統(tǒng)正確連接，發(fā)現(xiàn)軟件與系統(tǒng) 需求不一致的地方 測(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. 關(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ù)管

23、理系統(tǒng)（DBMS： 數(shù)據(jù)庫(kù)語(yǔ)言： 數(shù)據(jù)定義語(yǔ)言（DDL :負(fù)責(zé)數(shù)據(jù)的模式定義和數(shù)據(jù)的物理存取構(gòu)建 數(shù)據(jù)庫(kù)操縱語(yǔ)言（DML：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢(xún)及增、刪除、改操作 數(shù)據(jù)控制語(yǔ)言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、數(shù)據(jù)恢復(fù)等功能 （3）數(shù)據(jù)庫(kù)系統(tǒng)（DBS 三者關(guān)系：DBS包含DB和DBMS 2、數(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)是：數(shù)據(jù)需要長(zhǎng)期保留在外存儲(chǔ)器中供反復(fù)使用；程 序和數(shù)據(jù)之間有了一定的獨(dú)立性；文件夾形式已經(jīng)多樣化；數(shù)據(jù)的存儲(chǔ)基本上 以記錄為單位，提供

24、了簡(jiǎn)單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但它不能提供完整的、 統(tǒng)一的管理和共享數(shù)據(jù)的能力 （3）、數(shù)據(jù)庫(kù)系統(tǒng)階段： 實(shí)現(xiàn)了數(shù)據(jù)共享，減少了數(shù)據(jù)冗余； 采用了特定的數(shù)據(jù)模型； 真正統(tǒng)一的數(shù)據(jù)控制功能，能夠?yàn)槎鄠€(gè)用戶(hù)和應(yīng)用程序提供共享資源 具有數(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)： 數(shù)據(jù)高度集成 數(shù)據(jù)統(tǒng)一管理控制 數(shù)據(jù)獨(dú)立性 共享性與低冗余性 4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 概念模式：是數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，此種描述是一種抽象的描述，不但要描述 概念記錄類(lèi)型，而且要描述記錄之間的聯(lián)系、所允許的操作、數(shù)據(jù)的一致性、

25、安全性和其他數(shù)據(jù) 控制方面的要求 外模式：也稱(chēng)為數(shù)據(jù)庫(kù)的用戶(hù)式或子模式，是從概念模式導(dǎo)出的子模式，用戶(hù)可以通過(guò)子模式描 述語(yǔ)言來(lái)描述用戶(hù)級(jí)數(shù)據(jù)庫(kù)的記錄，還可以利用數(shù)據(jù)語(yǔ)言對(duì)這些記錄進(jìn)行操作。用戶(hù)使用數(shù)據(jù)操 縱語(yǔ)言對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作，實(shí)際上是對(duì)外模式的外部記錄進(jìn)行操作 內(nèi)模式：也稱(chēng)為數(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） 數(shù)據(jù)庫(kù)系統(tǒng)一般分為物理獨(dú)立性與邏輯獨(dú)立性?xún)杉?jí)。物理獨(dú)立性指數(shù)據(jù)的物理結(jié)構(gòu)的改變。在數(shù) 據(jù)系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)并不一定與邏輯結(jié)構(gòu)一致

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