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

2、續(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)來表示線性鏈表：就是指線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈表4、算法的基本特征可行性：針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果確定性：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義性有窮性：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步驟之后終止，算法程序的運(yùn)行時(shí) 間是有限的擁有足夠的情報(bào)：要使算法有效必需為算法提供足夠的情報(bào)當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法 才最有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效5

3、、算法的復(fù)雜度時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，是指執(zhí)行算法所需要的計(jì)算工作量，即算法執(zhí)行過程中 所需要的基本運(yùn)算次數(shù)空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲(chǔ)空間6、順序表和鏈表的比較：入棧棧底bottom基于空間的考慮：(1)順序表的存儲(chǔ)空間是靜態(tài)分配的，而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。(2)順序表 占的存儲(chǔ)空間必須是連續(xù)的，而鏈表占的存儲(chǔ)空間可以是連續(xù)的，也可是不連續(xù)的棧實(shí)際也是線性表，只不過是一種特殊的線性表。棧稱為先進(jìn)后出”表或后進(jìn)先出表，順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)棧的計(jì)算：求棧中元素的個(gè)數(shù)：棧底元素一棧頂元素棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入元素的一端為棧頂，允許刪除元素的一端為棧底，

4、棧頂元素總是最后被插入的元素，也 是最先被刪除的元素;棧底元素則總是最先被插入而最后被刪除的元素三、隊(duì)列隊(duì)列也是一種運(yùn)算受限的線性表，是一種先進(jìn)先出”，后進(jìn)后出的線性表，順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)隊(duì)列的計(jì)算：求隊(duì)列中元素的個(gè)數(shù)：當(dāng)rearfront時(shí)，rearfront 當(dāng) rearfront 時(shí)，rear-front+mm（代表隊(duì)列的容量）循環(huán)隊(duì)列仍然是順序存儲(chǔ)結(jié)構(gòu)，是隊(duì)列常采用的形式隊(duì)列是一種線性表，它允許在一端進(jìn)行插入，在另一端進(jìn)行刪front :隊(duì)頭Rear :隊(duì)尾除出隊(duì)二入隊(duì)四、樹與二叉樹（非線性結(jié)構(gòu)）1、樹 節(jié)點(diǎn)：樹中的每一個(gè)點(diǎn)叫做節(jié)點(diǎn)，分為根節(jié)點(diǎn)（0或1個(gè)）、父節(jié)點(diǎn)、子節(jié)點(diǎn)度：一個(gè)結(jié)點(diǎn)擁

5、有的子樹數(shù)稱為該結(jié)點(diǎn)的度。一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。度為一 1的L樹點(diǎn)節(jié)叫做n1 ,度為2的節(jié)點(diǎn)叫做n2B |C葉子節(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉子（沒有子節(jié)點(diǎn)的節(jié)點(diǎn)）叫做當(dāng)上D | E | F | G深度：樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度或深度2、二叉樹 二叉樹：由左樹和右樹組成，二叉樹的度 = 1)性質(zhì)2 :深度為m的二叉樹至多有2m-1個(gè)結(jié)點(diǎn)(k=D性質(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è)二叉樹節(jié)點(diǎn)個(gè)數(shù)：n=n0+n1 + n2性質(zhì)4 :具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度至少為log2n + 1，其中l(wèi)o

6、g2n表示取log2n的整數(shù)部分 二叉樹的遍歷：遍歷：是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(1)前序遍歷：訪問根結(jié)點(diǎn)左子樹右子樹(2)中序遍歷：左子樹訪問根結(jié)點(diǎn)右子樹(3 )后序遍歷：左子樹右子樹訪問根結(jié)點(diǎn)例：前序：ABDEGCF中序：DBGEACF后序：DGEBFCA五、排序冒泡排序：是最簡(jiǎn)單的一種交換類排序法。在最壞的情況下，對(duì)長(zhǎng)度為n的線性表排序，冒泡排序需要比較的次數(shù)為n(n-1)/2 ,其時(shí)間復(fù)雜度為O(n2)直接選擇排序：最壞情況要比較的次數(shù)為O(n2)，其時(shí)間復(fù)雜度為O(m)直接插入排序：最壞的情況下，時(shí)間復(fù)雜度為O(n快速排序：平均時(shí)間為O(nlog2

7、n),最壞情況下，時(shí)間效率為O(m)堆排序：最壞情況下,時(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)六、查找順序查找：即適用順序存儲(chǔ)結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下需要比較n次二分查找：要求線性表是有序表，另外，二分查找只適用順序存儲(chǔ)結(jié)構(gòu)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上無 法實(shí)現(xiàn)二分查找二分法查找只適用于順序存儲(chǔ)的有序表，在最壞情況下，二分查找需要比較log2n次在平均情況下，在順序存

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

9、oto語句(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語句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ú)立性好標(biāo)識(shí)唯一性：對(duì)象是可以區(qū)分的分類性：具有相同屬性和操作的對(duì)象可以抽象成一個(gè)類(3 )多態(tài)性：同一個(gè)操作可以是不同對(duì)象的行為，是指在類中定義名稱相同的函數(shù)，但是這些 函數(shù)的參數(shù)或者返回值的類型不同(4

10、 )封裝性：對(duì)外部只提供接口，方便用戶調(diào)用，內(nèi)部實(shí)現(xiàn)對(duì)外不可見，可實(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)：n 八、.軟件工程基本概念(*)結(jié)構(gòu)化分析方法(*)結(jié)

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

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

13、個(gè)階段：軟件定義時(shí)期：包括問題定義、可行性和需求分析3個(gè)階段軟件開發(fā)期：包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)和測(cè)試4個(gè)階段運(yùn)行維護(hù)期：即運(yùn)行維護(hù)階段軟件生命周期各階段的主要任務(wù)：?jiǎn)栴}定義：可行性研究與計(jì)劃制定：需求分析：對(duì)待開發(fā)軟件提出需求進(jìn)行分析并給出詳細(xì)定義。編寫軟件規(guī)格說 明書及初步的用戶手冊(cè)，提交評(píng)審。軟件設(shè)計(jì)：通常又分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)階段，給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。該階段提交評(píng)審的文檔有概要 設(shè)計(jì)說明書、詳細(xì)設(shè)計(jì)說明書和測(cè)試計(jì)劃初稿軟件實(shí)現(xiàn)：在軟件設(shè)計(jì)的基礎(chǔ)上編寫程序。該階段完成的文檔有用戶手冊(cè)、操作手冊(cè)等面向用戶的文檔，以及為下一步做準(zhǔn)備而編寫的單元測(cè)試

14、計(jì)劃軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。編寫測(cè)試分析報(bào)告運(yùn)行維護(hù)：五、結(jié)構(gòu)化分析方法1、需求分析和需求分析方法、需求分析階段的工作：需求獲取需求分析需求編寫規(guī)格說明書需求評(píng)審、需求分析方法：常用見的需分析方法：(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)化英語、判定表和判定樹等工具，實(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ù)處理過程的工

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

16、可追蹤性六、結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)概述（1 ）軟件設(shè)計(jì)的基礎(chǔ)：從工程管理的角度來看可分為兩步：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)包括軟 件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(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)之間以及軟件與人之間如何通信過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述(2)軟件設(shè)計(jì)的基本原理和原則：模塊化抽象信息隱藏模塊獨(dú)立性模塊獨(dú)立性：一般來說，要求模塊之間的耦合盡可能弱，即模塊盡可能獨(dú)立，且要求模塊 的

17、內(nèi)聚程度盡可能高。內(nèi)聚性和耦合性是一個(gè)問題的兩個(gè)方向，耦合性能程 度弱的模塊，其內(nèi)聚程序一定高內(nèi)聚性：是一個(gè)模塊內(nèi)部包含的信息，對(duì)于不需要這些信息的其他模塊來說是不能訪問的；是一個(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ì)階段文檔有概要設(shè)計(jì)說明書、數(shù)據(jù)庫(kù)設(shè)計(jì)說明書和集成測(cè)試計(jì)劃 等。(2)概要設(shè)計(jì)文檔評(píng)審：在文檔編寫完成后，要對(duì)設(shè)計(jì)部分是否完整地實(shí)現(xiàn)了需求中規(guī)定的功能、性能等要求，設(shè)計(jì)方案的可

18、行性，關(guān)鍵的處理及內(nèi)外部接口定義正確性、有效性，各部分 之間的一致性等進(jìn)行評(píng)審。3、 詳細(xì)設(shè)計(jì)LAJ_I Z TOC o 1-5 h z 任務(wù)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確實(shí)實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)一、D | E |pF程序流程圖(PFD):方框表示一個(gè)加工步驟I I菱形表示一個(gè)邏輯條件箭頭表示控制流4、軟件系統(tǒng)結(jié)構(gòu)圖的寬度：整體控制跨度(最大塊數(shù)的層)的顯示(如右圖，寬度是4)七、軟件測(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è)試(

19、1 )靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等，是指不在計(jì)算機(jī)上運(yùn)行被測(cè)試程 序，而采用其他手段來達(dá)到對(duì)程序進(jìn)行檢測(cè)的目的，包括人工測(cè)試和計(jì)算機(jī)輔助靜 態(tài)分析方法。(2)動(dòng)態(tài)測(cè)試：主要通過人工進(jìn)行分析。通過運(yùn)行軟件來檢驗(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) 和處理過程，保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次;保證所測(cè) 模塊所有判斷的每一分支至少執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有 效性。主要方法有邏輯覆蓋、基本路徑測(cè)試等。(4 )黑盒測(cè)試(功能測(cè)試)：把

20、程序看成一只黑盒子，測(cè)試者完成不了解，或不考慮程序的結(jié)構(gòu)和 處理過程，也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試，測(cè)試時(shí)不考慮程序內(nèi)部 細(xì)節(jié)、結(jié)構(gòu)和實(shí)現(xiàn)方式、僅檢驗(yàn)程序結(jié)果與說明書的一致性。測(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è)試其功能集成測(cè)試：也稱組裝測(cè)試，它是對(duì)各模塊按照設(shè)計(jì)要求組裝成的程序進(jìn)行測(cè)試，主要目的是發(fā) 現(xiàn)與接口有關(guān)的錯(cuò)誤(3 )確認(rèn)測(cè)試的任務(wù)是檢

21、驗(yàn)軟件的功能、性能及其他特征是否與用戶的需求一致，它是以需求規(guī)格 說明書作為依據(jù)的測(cè)試。確認(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)：n 八、數(shù)據(jù)庫(kù)系統(tǒng)的基本概念(*)數(shù)據(jù)模型(*)關(guān)系代數(shù)(*)數(shù)據(jù)庫(kù)設(shè)計(jì)與管理(*)一、數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)(

22、1 )數(shù)據(jù)庫(kù)(DB )(2)數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)：數(shù)據(jù)庫(kù)語言：數(shù)據(jù)定義語言(DDL ):負(fù)責(zé)數(shù)據(jù)的模式定義和數(shù)據(jù)的物理存取構(gòu)建數(shù)據(jù)庫(kù)操縱語言(DML ):負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪除、改操作數(shù)據(jù)控制語言：負(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ù)不保存，沒有對(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ù)

23、的存儲(chǔ)基本上以記錄為單位，提供了簡(jiǎn)單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但它不能提供 .學(xué)習(xí)參考 完整的、統(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è)用戶和應(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)的描述，此種描述是一種抽象的描述，不但要描 述概念記錄類型，而且要描述記錄之間的聯(lián)系、所允許的操作

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

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