1、,二級公共基礎(chǔ)知識輔導(dǎo),主講人：黃海軍 QQ：113958033 電話651196）,知識點分布,第一章 數(shù)據(jù)結(jié)構(gòu)與算法第二章 程序設(shè)計基礎(chǔ)第三章 軟件工程基礎(chǔ) 第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ),第一章 數(shù)據(jù)結(jié)構(gòu)與算法,1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。 *算法不等于程序，也不等于計算方法。 2、算法的基本特征,1.1 算法,可行性,確定性,有窮性,擁有足夠的情報,08年4月選擇題第5題 算法的有窮性是指_A_ A）算法程序的運行時間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的

2、用戶使用,3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。 （1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。 （2）算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 06年9月選擇題第7題 下列敘述中正確的是_D_ A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大 B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小 C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說法都不對,1.1 算法,1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下兩個方面的問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系

3、，即數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 *：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。,它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示

4、稱為鏈式存儲結(jié)構(gòu)。,除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。,07年4月選擇題第1題 下列敘述中正確的是_B_ A）算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B）算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量 C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的 D）算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān) 3、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點；2）每一個結(jié)點最多有一個前件，也最多有一個后件。*：常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。 （2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 *：常見的非線

5、性結(jié)構(gòu)有樹、二叉樹和圖等。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,07年9月選擇題第6題 下列敘述中正確的是_D_ A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的 B）由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu) C）程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu) D）以上三種說法都不對,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,1、棧及其基本運算 棧是限定在一端進行插入與刪除運算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織

6、數(shù)據(jù)的。 棧具有記憶作用。 06年9月填空題第4題 按“先進后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是_棧_。,1.3 棧和隊列,2、隊列及其基本運算 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。 隊列是“先進先出”或“后進后出”的線性表。 06年9月填空題第5題數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于_。 07年4月選擇題第5題 下面對隊列的敘述正確的是_ A) 隊列屬于非線性表 B) 隊列按“先進后出”原則組織數(shù)據(jù) C) 隊列在隊尾刪除數(shù)據(jù) D) 隊列按“先進先出”原則組織數(shù)據(jù),1

7、.3 棧和隊列,循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。 *：循環(huán)隊列中元素的個數(shù)=rear-front。 08年4月填空題第3題 設(shè)某循環(huán)對列的容量為50，頭指針front=5（指向?qū)︻^元素的前一位置），尾指針rear=29（指向隊尾元素），則該循環(huán)隊列中共有_個元素。 07年9月填空題第3題 線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列是隊列的_鏈式_ 存儲結(jié)構(gòu)。,1.3 棧和隊列,1、樹的基本概念 樹是一種簡單的非線性結(jié)構(gòu)。 沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹

8、的根。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。 06年9月填空題第1題 下列軟件系統(tǒng)結(jié)構(gòu)圖的寬度為_。,1.4 樹與二叉樹,2、二叉樹及其基本性質(zhì) （1）什么是二叉樹 二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1）非空二叉樹只有一個根結(jié)點；2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。 *：根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子樹）或2（有2棵子樹）。 （2）二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第k層上，最多有 個結(jié)點。 性質(zhì)2 深度為m的二叉

9、樹最多有個 個結(jié)點。 性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多一個。 性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為 ，其中 表示取 的整數(shù)部分。,1.4 樹與二叉樹,07年4月選擇題第7題 某二叉樹中有n個度為2的結(jié)點,則該二叉樹中的葉子結(jié)點數(shù)為 A (A)n+1 B)n-1 C)2n D)n/2 07年9月選擇題第8題 一顆二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為_ A）219 B）221 C）229 D）231,1.4 樹與二叉樹,3、滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。 完全二叉樹

10、：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。 08年4月填空題第2題 深度為5的滿二叉樹有_16_個葉子結(jié)點。 *：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點的個數(shù)為0或1。,1.4 樹與二叉樹,4、二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為 以下三種：,1.4 樹與二叉樹,（1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。,（2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左

11、子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。,（3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。,2007年4月選擇題第6題 對下列二叉樹進行前序遍歷的結(jié)果為_C_ A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ,1.4 樹與二叉樹,1.5 查找技術(shù) 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 2006年9月選擇題第8

12、題 在長度為 64 的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為 _A_ 。 A）63 B）64 C）6 D）7 1.6 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。1、交換類排序法（方法：冒泡排序，快速排序）。 2、插入類排序法（方法：簡單插入排序，希爾排序）。 3、選擇類排序法（方法：簡單選擇排序，堆排序）。,總結(jié)：各種排序法比較：,2008年4月選擇題第6題 對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是_D_ A）快速排序 B）冒泡排序 C）直接插入排序 D）堆排序 本章

13、應(yīng)考點撥：本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。,返回,第二章 程序設(shè)計基礎(chǔ),程序設(shè)計的風(fēng)格主要強調(diào)：“清晰第一，效率第二”。主要應(yīng)注重和考慮下述一些因素： （1）源程序文檔化。 符號名的命名。符號名能反映它所代表的實際東西，應(yīng)有一定的實際含義。 程序的注釋。分為序言性注釋和功能性注釋。 序言性注釋：位于程序開頭部分，包括程序標題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。 功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。 視覺組織。利用空格、空行、縮進等技巧

14、使程序?qū)哟吻逦?（2）輸入和輸出。 對輸入數(shù)據(jù)檢驗數(shù)據(jù)的合法性； 在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息。,2.1 程序設(shè)計風(fēng)格,06年9月選擇題第1題 下列選項中不符合良好程序設(shè)計風(fēng)格的是_D_。A）源程序要文檔化 B）數(shù)據(jù)說明的次序要規(guī)范化 C）避免濫用 goto 語句 D）模塊設(shè)計要保證高耦合、高內(nèi)聚（高內(nèi)聚，低耦合） 07年9月選擇題第4題 下列選項中不符合良好程序設(shè)計風(fēng)格的是_A_ A）程序的效率第一，清晰第二（清晰第一，效率第二） B）程序的可讀性好 C）程序中要有必要的注釋 D）輸入數(shù)

15、據(jù)前要有提示信息,2.1 程序設(shè)計風(fēng)格,1、結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語句。 （1）自頂向下。程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設(shè)計，逐步使問題具體化。 （2）逐步求精。對復(fù)雜問題，應(yīng)設(shè)計一些子目標作過渡，逐步細化。 （3）模塊化。一個復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。 *模塊設(shè)計要求高內(nèi)聚、低耦合。 （4）限制使用goto語句。 08年4月選擇題第

16、2題 結(jié)構(gòu)化程序設(shè)計的基本原則不包括_ A）多態(tài)性 B）自頂向下 C）模塊化 D）逐步求精 2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。,2.2 結(jié)構(gòu)化程序設(shè)計（面向過程的程序設(shè)計方法）,面向?qū)ο蠓椒ǖ闹饕獌?yōu)點：（1）與人類習(xí)慣的思維方法一致；（2）穩(wěn)定性好；（3）可重用性好；（4）易于開發(fā)大型軟件產(chǎn)品；（5）可維護性好。 *：面向?qū)ο蟮某绦蛟O(shè)計主要考慮的是提高軟件的可重用性。 對象是屬性和方法的封裝體。 *：一個對象由對象名、屬性和操作三部分組成。 面向?qū)ο蟮幕咎攸c：繼承性，多態(tài)性，封裝性。 （1）繼承。指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。 *：類的繼承性是類之

17、間共享屬性和操作的機制，它提高了軟件的可重用性。 （2）多態(tài)性。指同一個操作可以是不同對象的行為。 （3）封裝性。從外面看只能看到對象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法。對象的內(nèi)部，即處理能力的實行和內(nèi)部狀態(tài)，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對象的內(nèi)部狀態(tài)只能由其自身改變。 *：信息隱蔽是通過對象的封裝性來實現(xiàn)的。,2.3 面向?qū)ο蟮某绦蛟O(shè)計,軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程。,07年4月選擇題第4題 下面選項中不屬于面向?qū)ο蟪绦蛟O(shè)計特征的是_C_

18、 A）繼承性 B）多態(tài)性 C）類比性 D）封裝性 07年9月選擇題第3題 在面向?qū)ο蠓椒ㄖ?，實現(xiàn)信息隱蔽是依靠_ A）對象的繼承 B）對象的多態(tài) C）對象的封裝 D）對象的分類 類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。 *：在面向?qū)ο蠓椒ㄖ?，一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送消息。 本章應(yīng)考點撥：本章在考試中會出現(xiàn)約1個題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡單，掌握住基本的概念就可以輕松應(yīng)對考試了，所以在這部分丟分，比較可惜。,2.2 結(jié)構(gòu)化程序設(shè)計（面向過程的程序

19、設(shè)計方法）,返回,第三章 軟件工程基礎(chǔ),1、軟件的相關(guān)概念 計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 07年9月選擇題第1題 軟件是指_D_ A）程序 B）程序和文檔 C）算法加數(shù)據(jù)結(jié)構(gòu) D）程序、數(shù)據(jù)與相關(guān)文檔的完整集合 2、軟件危機與軟件工程 軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。 軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程，它包括3個要素：方法、工具和過程。方法是完成軟件工程項目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。,3.1 軟件工程基本概念,3、軟件生命周期 軟件

20、生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護三個階段： 1）軟件定義階段：包括制定計劃和需求分析。 制定計劃：確定總目標；可行性研究；探討解決方案；制定開發(fā)計劃。 需求分析：對待開發(fā)軟件提出的需求進行分析并給出詳細的定義。 2）軟件開發(fā)階段： 軟件設(shè)計：分為概要設(shè)計和詳細設(shè)計兩個部分。 軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。 軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分。 3）軟件運行維護階段：軟件投入運行，并在使用中不斷地維護，進行必要的擴充和刪改。 *：軟件生命周期中所花費最多的階段是軟件運行維護階段

21、。,3.1 軟件工程基本概念,08年4月選擇題第4題 在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是_B_ A）可行性分析報告 B）軟件需求規(guī)格說明書 C）概要設(shè)計說明書 D）集成測試計劃 07年4月填空題第4題 軟件生命周期可分為多個階段，一般分為定義階段、開發(fā)階段和維護階段。編碼和測試屬于 _開發(fā)_階段。 06年9月填空題第2題 從工程管理角度，軟件設(shè)計一般分為兩步完成，它們是 _ 。 A）概要設(shè)計與詳細設(shè)計 B）數(shù)據(jù)設(shè)計與接口設(shè)計 C）軟件結(jié)構(gòu)設(shè)計與數(shù)據(jù)設(shè)計 D）過程設(shè)計與數(shù)據(jù)設(shè)計 06年9月填空題第3題 下列選項中不屬于軟件生命周期開發(fā)階段任務(wù)的是 _ 。 A）軟件測試 B）概要設(shè)計 C）

22、軟件維護 D）詳細設(shè)計,3.1 軟件工程基本概念,4、軟件工程的目標和與原則 （1）軟件工程目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、 可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 （2）軟件工程需要達到的基本目標應(yīng)是：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用。,3.1 軟件工程基本概念,結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）； 3）判定樹；4）判定表。 數(shù)據(jù)流圖 上圖是數(shù)據(jù)流圖的基本圖形元素：數(shù)據(jù)字典 *：數(shù)據(jù)字典

23、的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。*：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。 07年4月填空題第5題 在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖（DFD）中，利用 _數(shù)據(jù)字典_ 對其中的圖形元素進行確切解釋。,3.2 結(jié)構(gòu)化分析方法,1、軟件設(shè)計的基礎(chǔ) *：需求分析主要解決“做什么”的問題，而軟件設(shè)計主要解決“怎么做”的問題。 從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。 從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計和詳細設(shè)計。 軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性。 2、總體設(shè)計（概要設(shè)計）和詳細設(shè)計 （1）總體設(shè)計（概要設(shè)計） 常用的軟件結(jié)

24、構(gòu)設(shè)計工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符： 模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù),3.3 結(jié)構(gòu)化設(shè)計方法,經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖： 它們的含義分別是： 傳入模塊：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級模塊。 傳出模塊：從上級模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。 變換模塊：從上級模塊取得數(shù)據(jù)，進行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級模塊。 協(xié)調(diào)模塊：對所有下屬模

25、塊進行協(xié)調(diào)和管理的模塊。 數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。,3.3 結(jié)構(gòu)化設(shè)計方法,（2）詳細設(shè)計 *：詳細設(shè)計的任務(wù)是確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。常用的過程設(shè)計（即詳細設(shè)計）工具有以下幾種： 圖形工具：程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。 程序流程圖中主要元素：1）方框：表示一個處理步驟2）菱形框：表示一個邏輯條件3）箭頭：表示控制流向 08年4月選擇題第1題 程序流程圖中帶有箭頭的線段表示的是_C_ A）圖元關(guān)系 B）數(shù)據(jù)流 C）控制流 D）調(diào)用關(guān)系 表格工具：判定表。 語言工具：PDL（偽碼）,

26、3.3 結(jié)構(gòu)化設(shè)計方法,1、軟件測試 *：軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯誤，不能也不可能證明程序沒有錯誤。 07年4月選擇題第3題 下列敘述中正確的是 _A） 軟件測試的主要目的是發(fā)現(xiàn)程序中的錯誤B） 軟件測試的主要目的是確定程序中錯誤的位置C） 為了提高軟件測試的效率，最好由程序編制者自己來完成軟件的測試工作D） 軟件測試是證明軟件沒有錯誤 2、軟件測試方法：靜態(tài)測試和動態(tài)測試。 動態(tài)測試：主要包括白盒測試方法和黑盒測試方法。,3.4 軟件測試,（1）白盒測試 白盒測試的基本原則：保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊所有判斷的每一分支至少執(zhí)行一次；保證所測模塊每一循

27、環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。 語句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執(zhí)行一次。 路徑覆蓋：執(zhí)行足夠的測試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。 判定覆蓋：使設(shè)計的測試用例保證程序中每個判斷的每個取值分支（T或F）至少經(jīng)歷一次。 條件覆蓋：設(shè)計的測試用例保證程序中每個判斷的每個條件的可能取值至少執(zhí)行一次。 判斷-條件覆蓋：設(shè)計足夠的測試用例，使判斷中每個條件的所有可能取值至少執(zhí)行一次，同時每個判斷的所有可能取值分支至少執(zhí)行一次。 *：覆蓋的強度依次是：語句覆蓋路徑覆蓋判定覆蓋條件覆蓋判斷-條件覆蓋。 07年9月填空題第2題

28、 在兩種基本測試方法中，_白盒_測試的原則之一是保證所測模塊中每一個獨立路徑至少要執(zhí)行一次。,3.4 軟件測試,（2）黑盒測試 黑盒測試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說明來設(shè)計測試用例，主要方法有等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟件的確認測試。 07年4月填空題第2題 軟件測試分為白箱（盒）測試和黑箱（盒）測試，等價類劃分法屬于 _黑盒_ 測試。,3.4 軟件測試,程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進行，調(diào)試程序應(yīng)該由編制源程序的程序員來完成。 06年9月填空題第2題 _程序調(diào)試_的任務(wù)是診斷和改正程序中的錯誤。 *：軟件的調(diào)試后要進行回歸測試，防

29、止引進新的錯誤。 本章應(yīng)考點撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。從出題的深度來看，本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此考生在復(fù)習(xí)本章時，重點應(yīng)放在基本概念的記憶和基本原理的理解上。,3.5 程序的調(diào)試,返回,第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ),4.1 數(shù)據(jù)庫系統(tǒng)的基本概念 1、數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng) （1）數(shù)據(jù)：實際上就是描述事物的符號記錄。 （2）數(shù)據(jù)庫（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。 （3）數(shù)據(jù)庫管理系統(tǒng)（DBMS）：一種系統(tǒng)軟

30、件，負責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。 07年4月填空題第3題 在數(shù)據(jù)庫系統(tǒng)中，實現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為 _數(shù)據(jù)庫管理系統(tǒng)_。,數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語言： 數(shù)據(jù)定義語言：負責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建； 數(shù)據(jù)操縱語言：負責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等； 數(shù)據(jù)控制語言：負責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。 08年4月填空題第5題 在數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)定義語言、數(shù)據(jù)操縱語言和數(shù)據(jù)控制語言中，_數(shù)據(jù)定義語言_負責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。 （4）數(shù)據(jù)庫管理員（DBA）：對數(shù)據(jù)庫進行

31、規(guī)劃、設(shè)計、維護、監(jiān)視等的專業(yè)管理人員。（5）數(shù)據(jù)庫系統(tǒng)（DBS）：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。 （6）數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。 *：數(shù)據(jù)庫技術(shù)的根本目標是解決數(shù)據(jù)的共享問題。,4.1 數(shù)據(jù)庫系統(tǒng)的基本概念,4.1 數(shù)據(jù)庫系統(tǒng)的基本概念,3、數(shù)據(jù)庫系統(tǒng)的基本特點 （1）數(shù)據(jù)的高集成性。 （2）數(shù)據(jù)的高共享性與低冗余性。 （3）數(shù)據(jù)獨立性：數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中數(shù)據(jù)獨立于應(yīng)用程序而不依賴于應(yīng)用程序。 數(shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性兩級

32、。 07年4月選擇題第10題 下列敘述中錯誤的是 _A)在數(shù)據(jù)庫系統(tǒng)中,數(shù)據(jù)的物理結(jié)構(gòu)必須與邏輯結(jié)構(gòu)一致B)數(shù)據(jù)庫技術(shù)的根本目標是解決數(shù)據(jù)共享問題C)數(shù)據(jù)庫技術(shù)是指己有數(shù)據(jù)管理系統(tǒng)的基礎(chǔ)上建立數(shù)據(jù)庫D)數(shù)據(jù)庫系統(tǒng)需要操作系統(tǒng)的支持,4.1 數(shù)據(jù)庫系統(tǒng)的基本概念,（4）數(shù)據(jù)統(tǒng)一管理與控制。 數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個方面： 1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。 2）數(shù)據(jù)的安全性保護：檢查數(shù)據(jù)庫訪問者以防止非法訪問。 3）并發(fā)控制：控制多個應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。,4.1 數(shù)據(jù)庫系統(tǒng)的基本概念,4、數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 （1）數(shù)據(jù)庫系統(tǒng)

33、的三級模式： 1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。 06年9月選擇題第4題 在數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為_ 。 A）概念模式 B）外模式 C）內(nèi)模式 D）物理模式,4.2 數(shù)據(jù)模型,（1）E-R模型的基本概念：1）實體：現(xiàn)實世界中的事物。2）屬性：事物的特性。3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。*：E-R模型的基本成分是實體和聯(lián)系

34、。 （2）E-R模型的圖示法： 1）實體集：用矩形表示。 2）屬性：用橢圓形表示。 3）聯(lián)系：用菱形表示。 4）實體集與屬性間的聯(lián)接關(guān)系：用無向線段表示。 5）實體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。,4.1 數(shù)據(jù)庫系統(tǒng)的基本概念,07年4月選擇題第9題 在ER圖中,用來表示實體之間聯(lián)系的圖形是 _C_A)矩形 B)橢圓形 C)菱形 D)平行四邊形,4.2 數(shù)據(jù)模型,（3）數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。 1）層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。 2）網(wǎng)狀模型是層次模型的一個特例，從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。,4.2 數(shù)據(jù)模型,3）關(guān)系模型采用二維表來表示，一個二維表就是一個關(guān)系，二維表中的每一個分量都是不可再分的。,*：同一個關(guān)系模型的任兩個元組值不能完全相同。,4.2 數(shù)據(jù)模型,08年4月填空題第4題 在關(guān)系數(shù)據(jù)庫中，用來表示實體之間聯(lián)系的是_菱形_。 *：在關(guān)系中，水平方向的行稱為元組，垂直方向的列稱為屬性，每一列有一個屬性名。 06年9月填空題第3題 一個關(guān)系表的行稱為_元組_。 主碼：或稱為關(guān)鍵字，表中的一個屬性或幾個屬性的組合、其值能唯一地標識表中一個元組