1、二級公共基礎宇創(chuàng)教育 田老師2 宇創(chuàng)教育 田老師1、程序流程圖P80 程序流程圖的基本圖符：程序流程圖的基本圖符： 控制流控制流 表示為：表示為： 或或 加工步驟加工步驟 表示為：表示為： 邏輯條件邏輯條件 表示為：表示為：西瓜西瓜草莓草莓西瓜西瓜西瓜西瓜草莓草莓3 宇創(chuàng)教育 田老師2、結構化程序設計原則P77自頂向下逐步求精模塊化限用gotogoto先考慮總體，后考慮細節(jié)；先考先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標慮全局目標，后考慮局部目標對復雜問題，先設計一個目對復雜問題，先設計一個目標作為過渡，然后逐步細化標作為過渡，然后逐步細化把程序要解決的總目標把程序要解決的總目標分

2、解為一個一個的模塊分解為一個一個的模塊限制使用限制使用gotogoto語句，程序的語句，程序的質量與質量與gotogoto語句數(shù)量成反比語句數(shù)量成反比4 宇創(chuàng)教育 田老師2、結構化程序設計 結構化程序設計常采用順序、選擇結構化程序設計常采用順序、選擇( (分支分支) )和循環(huán)三和循環(huán)三種基本結構種基本結構2009.32010.92009.32010.9僅由順序、選擇僅由順序、選擇( (分支分支) )和循環(huán)結構和循環(huán)結構構成的程序是構成的程序是 程序。程序。結構化結構化西瓜西瓜草莓草莓西瓜西瓜草莓草莓西瓜西瓜5 宇創(chuàng)教育 田老師 內聚性內聚性指一個模塊內部各個元素指一個模塊內部各個元素間彼此結合

3、的緊密程度間彼此結合的緊密程度 耦合性耦合性指模塊間互相連接的緊密指模塊間互相連接的緊密程度程度3、軟件模塊獨立性p816 宇創(chuàng)教育 田老師4、軟件工程p79使用使用維護維護退役退役可行性研可行性研究、初步究、初步項目計劃項目計劃需求分析需求分析實現(xiàn)實現(xiàn)測試測試概要設計概要設計詳細設計詳細設計可行性分析報告可行性分析報告需求規(guī)格說明書需求規(guī)格說明書測試分析報告測試分析報告概要設計說明書概要設計說明書定定義義開開發(fā)發(fā)維維護護詳細設計說明書詳細設計說明書用戶操作手冊用戶操作手冊數(shù)據(jù)流圖數(shù)據(jù)流圖DFD,DFD,判定樹判定樹數(shù)據(jù)字典數(shù)據(jù)字典DD,DD,判定表判定表程序結構圖程序結構圖(SC)(SC)程

4、序流程圖程序流程圖,N-S,PAD,N-S,PAD,HIPO,HIPO,判定表判定表,PDL,PDL靜靜/ /動態(tài)動態(tài), ,白白/ /黑盒黑盒7 宇創(chuàng)教育 田老師5、算法基本特征p73可行性確定性有窮性足夠的情報行定窮情在設計一個算法時，必在設計一個算法時，必須考慮它的可行性須考慮它的可行性算法中的每個步驟必須是明算法中的每個步驟必須是明確定義的，不允許模棱兩可確定義的，不允許模棱兩可算法必須在有限的時間內做完，算法必須在有限的時間內做完，必須在執(zhí)行有限個步驟之后終止必須在執(zhí)行有限個步驟之后終止是指算法要有一定的輸入是指算法要有一定的輸入數(shù)據(jù)和必須要有輸出結果數(shù)據(jù)和必須要有輸出結果 算法算法：

5、是指解題方案的準確而完整的描述。是指解題方案的準確而完整的描述。2008.42008.4算法的有窮性是指算法的有窮性是指A)A)算法程序的運行時間是有限的算法程序的運行時間是有限的B)B)算法程序所處理的數(shù)據(jù)是有限的算法程序所處理的數(shù)據(jù)是有限的C)C)算法程序的長度是有限的算法程序的長度是有限的D)D)算法只能被有限的用戶使用算法只能被有限的用戶使用8 宇創(chuàng)教育 田老師6、排序p77nlognlog2 2n nnlognlog2 2n n堆堆 排排 序序n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2選擇排序選擇排序選擇類選擇類n n1.51.5nlognlog2 2n n希爾

6、排序希爾排序n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2插入排序插入排序插入類插入類n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2快速排序快速排序n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2冒泡排序冒泡排序交換類交換類最壞情況最壞情況平均時間平均時間排排 序序9 宇創(chuàng)教育 田老師7、棧p74 棧棧是限定在一端進行插入和刪除的線性表。原則是：是限定在一端進行插入和刪除的線性表。原則是：先進后出先進后出( (或后進先出或后進先出) )。棧具有記憶功能。棧具有記憶功能。蘋果蘋果草莓草莓桔子桔子西瓜西瓜香蕉香蕉2 23 34 45 56 61

7、1toptopbottombottom葡萄葡萄棧底指針棧底指針 bottombottom棧頂指針棧頂指針 toptop?？諚？?toptop = = 0 0入棧入棧棧滿棧滿出棧出棧toptoptoptoptoptoptoptoptoptoptoptop0 010 宇創(chuàng)教育 田老師8、E-R模型p84 E-R E-R模型模型( (實體聯(lián)系模型實體聯(lián)系模型) ) 實體實體 屬性屬性 聯(lián)系聯(lián)系 聯(lián)接關系聯(lián)接關系成績成績選課選課學號學號年齡年齡學生學生姓名姓名課程號課程號課程名課程名課程課程m mn n11 宇創(chuàng)教育 田老師數(shù)據(jù)模型學校學校部處部處員工員工領導領導領導領導院系院系領導領導學生學生領導領

8、導教師教師領導領導學校學校班級班級領導領導領導領導教師教師學生學生領導領導領導領導層次模型層次模型樹樹網(wǎng)狀模型網(wǎng)狀模型無向圖無向圖關系模型關系模型二維表二維表12 宇創(chuàng)教育 田老師9、并 T=R+S p85姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲櫻木花道櫻木花道流川楓流川楓照片照片T T流川楓流川楓櫻木花道櫻木花道姓名姓名照片照片R R姓名姓名三井壽三井壽宮城良田宮城良田照片照片S S赤木剛憲赤木剛憲13 宇創(chuàng)教育 田老師差 T=R-S姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲櫻木花道櫻木花道流川楓流川楓照片照片R R流川楓流川楓櫻木花道櫻木花道姓名姓名照片照片T T姓名

9、姓名三井壽三井壽宮城良田宮城良田照片照片S S赤木剛憲赤木剛憲14 宇創(chuàng)教育 田老師交姓名姓名宮城良田宮城良田櫻木花道櫻木花道流川楓流川楓照片照片R R流川楓流川楓姓名姓名照片照片T T姓名姓名流川楓流川楓三井壽三井壽赤木剛憲赤木剛憲照片照片S S15 宇創(chuàng)教育 田老師選擇流川楓流川楓櫻木花道櫻木花道姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲11111010球衣球衣7 714144 4照片照片R R姓名姓名球衣球衣三井壽三井壽赤木剛憲赤木剛憲14144 4照片照片T T16 宇創(chuàng)教育 田老師投影流川楓流川楓櫻木花道櫻木花道姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲照片照片T

10、 T0102010201010101學號學號020102010302030203010301流川楓流川楓櫻木花道櫻木花道姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲11111010球衣球衣7 714144 4照片照片R R17 宇創(chuàng)教育 田老師笛卡爾積 T=RS位置位置后衛(wèi)后衛(wèi)前鋒前鋒7 71010球衣球衣S S照片照片R R學號學號010201020101010102010201T T學號學號照片照片位置位置球衣球衣01020102后衛(wèi)后衛(wèi)7 701010101前鋒前鋒101001010101后衛(wèi)后衛(wèi)7 702010201前鋒前鋒101002010201后衛(wèi)后衛(wèi)7 701020102

11、前鋒前鋒101018 宇創(chuàng)教育 田老師除 T=RS 例1位置位置后衛(wèi)后衛(wèi)前鋒前鋒7 71010球衣球衣S S照片照片T T學號學號0102010201010101R R學號學號照片照片位置位置球衣球衣01020102后衛(wèi)后衛(wèi)7 701010101前鋒前鋒101001010101后衛(wèi)后衛(wèi)7 701020102前鋒前鋒101001010101中鋒中鋒4 419 宇創(chuàng)教育 田老師除 T=RS 例2位置位置前鋒前鋒1010球衣球衣S S照片照片T T學號學號0102010201010101R R學號學號照片照片位置位置球衣球衣01020102后衛(wèi)后衛(wèi)7 701010101前鋒前鋒10100101010

12、1后衛(wèi)后衛(wèi)7 701020102前鋒前鋒101001010101中鋒中鋒4 420 宇創(chuàng)教育 田老師除 T=RS 例3照片照片T T學號學號01010101R R學號學號照片照片位置位置球衣球衣01020102后衛(wèi)后衛(wèi)7 701010101前鋒前鋒101001010101后衛(wèi)后衛(wèi)7 701020102前鋒前鋒101001010101中鋒中鋒4 4位置位置后衛(wèi)后衛(wèi)前鋒前鋒7 71010球衣球衣S S中鋒中鋒4 421 宇創(chuàng)教育 田老師自然連接后衛(wèi)后衛(wèi)R R照片照片前鋒前鋒前鋒前鋒位置位置后衛(wèi)后衛(wèi)中鋒中鋒S S中鋒中鋒前鋒前鋒位置位置特長特長籃板籃板灌籃灌籃T T照片照片前鋒前鋒前鋒前鋒位置位置中

13、鋒中鋒灌籃灌籃灌籃灌籃特長特長籃板籃板22 宇創(chuàng)教育 田老師10、關系模型p84 關系的性質關系的性質( (二維表二維表) )0102010201010101學號學號020102010302030203010301流川楓流川楓櫻木花道櫻木花道姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲11111010球衣球衣7 714144 4照片照片主鍵主鍵元組元組( (記錄記錄) )屬性屬性元組個數(shù)有限性元組個數(shù)有限性元組的唯一性元組的唯一性元組的次序無關性元組的次序無關性元組分量的原子性元組分量的原子性屬性名的唯一性屬性名的唯一性屬性的次序無關性屬性的次序無關性分量值域的同一性分量值域的同一性2

14、3 宇創(chuàng)教育 田老師外鍵(外碼) 表表A A某屬性集是表某屬性集是表B B的鍵，則該屬性集為的鍵，則該屬性集為A A的外鍵。的外鍵。鍵鍵0102010201010101學號學號020102010302030203010301流川楓流川楓櫻木花道櫻木花道姓名姓名宮城良田宮城良田三井壽三井壽赤木剛憲赤木剛憲11111010球衣球衣7 714144 4照片照片表表A A187187189189身高身高16816818418419719775758383體重體重5959707090900102010201010101學號學號020102010302030203010301表表B B外鍵外鍵24 宇創(chuàng)教

15、育 田老師12、隊列p74 隊隊列列是指允許在一端進行插入，而在另一端進行刪是指允許在一端進行插入，而在另一端進行刪除的線性表。原則是：先進先出除的線性表。原則是：先進先出( (或后進后出或后進后出) )。隊頭指針隊頭指針 frontfront隊尾指針隊尾指針 rearrear入隊入隊 出隊出隊 2 23 34 45 56 61 1frontfrontrearrear草莓草莓桔子桔子西瓜西瓜香蕉香蕉rearrearfrontfrontrearrear葡萄葡萄frontfront25 宇創(chuàng)教育 田老師13、二分查找p77 二分查找二分查找：適用于順序存儲的有序表，對長度為：適用于順序存儲的有序表

16、，對長度為 n n 的線性表，在最壞情況下進行的線性表，在最壞情況下進行 loglog2 2n n 次比較。次比較。1 11 12 25 555558 83 313133434212189891 12 23 34 45 56 67 78 89 911111010leftleftmidmidrightright 注意：即使是有序線性表，如果采用鏈式存儲結注意：即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。構，也只能用順序查找。26 宇創(chuàng)教育 田老師14、數(shù)據(jù)的存儲結構P74 數(shù)據(jù)的數(shù)據(jù)的存儲結構存儲結構是指數(shù)據(jù)的邏輯結構在計算機存儲是指數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式。一種

17、數(shù)據(jù)結構的邏輯結構根據(jù)空間中的存放形式。一種數(shù)據(jù)結構的邏輯結構根據(jù)需要可以表示成多種存儲結構。采用不同的存儲結需要可以表示成多種存儲結構。采用不同的存儲結構，其數(shù)據(jù)處理的效率是不同的。構，其數(shù)據(jù)處理的效率是不同的。 順序存儲順序存儲 鏈式存儲鏈式存儲27 宇創(chuàng)教育 田老師17、對象基本特點p88標識唯一性對象可由內在本質來區(qū)分，對象可由內在本質來區(qū)分，而不是通過描述來區(qū)分。而不是通過描述來區(qū)分。1分類性可以將具有相同屬性和操作可以將具有相同屬性和操作的對象抽象成類。的對象抽象成類。2多態(tài)性同一操作可以是不同對象的同一操作可以是不同對象的行為。行為。3封裝性從外面看不到對象的內部，從外面看不到對

18、象的內部，只能看到對象的外部特征。只能看到對象的外部特征。4模塊獨立性好對象是面向對象的軟件的基對象是面向對象的軟件的基本模塊，內聚性強。本模塊，內聚性強。528 宇創(chuàng)教育 田老師文件系統(tǒng)文件系統(tǒng)人工管理人工管理數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)19、數(shù)據(jù)管理三個階段p8329 宇創(chuàng)教育 田老師 常用術語常用術語 父結點、子結點父結點、子結點 根結點、葉子結點根結點、葉子結點 結點的度、樹的度結點的度、樹的度 樹的深度樹的深度 子樹子樹23、樹p75 樹樹是是 n(n0)n(n0) 個元素的有限集合。它有且僅有一個個元素的有限集合。它有且僅有一個稱為稱為根根的元素；其余元素是互不相交的子樹。的元素；其余元素

19、是互不相交的子樹。A AB BC CD DI IE EF FG GH HJ JK KL LM MN N30 宇創(chuàng)教育 田老師二叉樹 非空非空二叉樹二叉樹只有一個根結點，每個結點最多有兩棵只有一個根結點，每個結點最多有兩棵子樹，分別稱為左子樹和右子樹。子樹，分別稱為左子樹和右子樹。 在二叉樹的第在二叉樹的第 k k 層上，最多有層上，最多有 2 2k-1k-1 個結點個結點 深度為深度為 m m 的二叉樹最多有的二叉樹最多有 2 2m m-1-1 個結點個結點 度為度為 0 0 的結點（葉子的結點（葉子 結點）總比度為結點）總比度為 2 2 的結的結 點多一個點多一個 有有 n n 個結點的二叉

20、樹個結點的二叉樹 深度至少為深度至少為 loglog2 2n+1n+1A AB BC CG GD DE EF FH HM ML LN N31 宇創(chuàng)教育 田老師26、程序調試p82 對程序進行了成功的測試之后將進入程序調試，通對程序進行了成功的測試之后將進入程序調試，通常稱為常稱為Debug(Debug(排錯排錯) )，主要在開發(fā)階段進行。，主要在開發(fā)階段進行。 程序調試的任務是程序調試的任務是診斷和改正程序的錯誤診斷和改正程序的錯誤。 基本步驟：基本步驟： 錯誤定位錯誤定位 修改設計和代碼，以排除錯誤修改設計和代碼，以排除錯誤 進行回歸測試，防止引進新的錯誤進行回歸測試，防止引進新的錯誤32

21、宇創(chuàng)教育 田老師2011.92011.9程序調試的任務是程序調試的任務是 A)A)發(fā)現(xiàn)程序中的錯誤發(fā)現(xiàn)程序中的錯誤 B)B)驗證程序的正確性驗證程序的正確性 C)C)診斷和改正程序中的錯誤診斷和改正程序中的錯誤 D)D)設計測試用例設計測試用例習題演練2007.92010.32007.92010.3軟件（程序）調試的任務是軟件（程序）調試的任務是 A)A)盡可能多地發(fā)現(xiàn)程序中的錯誤盡可能多地發(fā)現(xiàn)程序中的錯誤 B)B)確定程序中錯誤的性質確定程序中錯誤的性質 C)C)診斷和改正程序中的錯誤診斷和改正程序中的錯誤 D)D)發(fā)現(xiàn)并改正程序中的所有錯誤發(fā)現(xiàn)并改正程序中的所有錯誤33 宇創(chuàng)教育 田老師習

22、題演練2009.32009.3下面敘述中錯誤的是下面敘述中錯誤的是 A)A)軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤 B)B)對程序對程序“錯誤定位錯誤定位”是程序調試的必要步驟是程序調試的必要步驟 C)C)程序調試通常也稱為程序調試通常也稱為debugdebug D) D)軟件測試應嚴格執(zhí)行測試計劃，排除隨意性軟件測試應嚴格執(zhí)行測試計劃，排除隨意性2005.92006.42005.92006.4下面敘述中正確的是下面敘述中正確的是 A)A)程序設計就是編制程序程序設計就是編制程序 B)B)程序的測試必須由程序員自己去完成程序的測試必須由程序員自己去完成 C)C)程

23、序經(jīng)調試改錯后還應進行再測試程序經(jīng)調試改錯后還應進行再測試 D)D)程序經(jīng)調試改錯后不必進行再測試程序經(jīng)調試改錯后不必進行再測試34 宇創(chuàng)教育 田老師 數(shù)據(jù)數(shù)據(jù)庫庫： 是數(shù)據(jù)是數(shù)據(jù)的集合，具有統(tǒng)一的集合，具有統(tǒng)一的結構形式并存放于統(tǒng)一的結構形式并存放于統(tǒng)一的存儲介質內，是多種應的存儲介質內，是多種應用數(shù)據(jù)的用數(shù)據(jù)的集成集成，并可被各，并可被各個應用程序個應用程序共享共享。28、數(shù)據(jù)庫p8635 宇創(chuàng)教育 田老師習題演練2006.42006.4數(shù)據(jù)庫數(shù)據(jù)庫DBDB、數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)庫系統(tǒng)DBSDBS、數(shù)據(jù)庫管理系、數(shù)據(jù)庫管理系統(tǒng)統(tǒng)DBMSDBMS之間的關系是之間的關系是 A)DBA)DB包含包含DBSDBS和和DBMS B)DBMSDBMS B)DBMS包含包含DBDB和和DBSDBS C)DBS C)DBS包含包含DBDB和和DBMS D)DBMS D)沒有任何關系沒有任何關系2007.92007.9下列敘述中正確的是下列敘述中正確的是 A)A)數(shù)據(jù)庫系統(tǒng)是一個獨立的系統(tǒng)，不需要操作系統(tǒng)數(shù)據(jù)庫系統(tǒng)是一個獨立的系統(tǒng)，不需要操作系統(tǒng)的支持的支持 B)B)數(shù)據(jù)庫技術的根本目標是要解決數(shù)據(jù)的共享問題數(shù)據(jù)庫技術的