全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)知識講義

1、全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)知識輔導(dǎo)講義貞腳.目錄第章數(shù)據(jù)結(jié)構(gòu)與算法L1算法11.2數(shù)據(jù)結(jié)構(gòu)的基本概念113線性表及其順序存儲結(jié)構(gòu)21.4棧和隊(duì)列2L5線性鏈表31.6樹與二叉樹41.7査找技術(shù)51.8排序技術(shù)6木萃應(yīng)考點(diǎn)撥6第二疥程序設(shè)計(jì)基礎(chǔ)72程序設(shè)計(jì)風(fēng)格72.2結(jié)構(gòu)化程序設(shè)計(jì)（面向過程的程序設(shè)計(jì)方法）723面向?qū)﹀璧某绦蛟O(shè)計(jì)8木章應(yīng)考點(diǎn)撥8第三章軟件工程基礎(chǔ)93軟件工程基木槪念93.2結(jié)構(gòu)化分析方法103.3結(jié)構(gòu)化設(shè)il方法113.4軟件測試133.5程序的調(diào)試15木萃應(yīng)考點(diǎn)撥15第四章數(shù)抿庫設(shè)計(jì)基礎(chǔ)164數(shù)據(jù)庫系統(tǒng)的基木概念164.2數(shù)據(jù)模型1843關(guān)系代數(shù)204.4數(shù)據(jù)庫設(shè)計(jì)方法和

2、步腺21木章應(yīng)考點(diǎn)撥21第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1、陲因是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特立問題求解步驟的一種 描述。*:算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。2、算法的基本特征（1）可行性。針對實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一 條執(zhí)行路徑，即相同的輸入只能得岀相同的輸岀。（3）有窮性。算法必須在有限的時(shí)間完成。有兩重含義，一是算法中的操作步驟為有限個(gè), 二是每個(gè)步驟都能在有限時(shí)間完成。（4）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對象上

3、，而這些運(yùn)算對象又 可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依拯。因此，一個(gè)算法執(zhí)行的結(jié)果總是與 輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯誤時(shí)，算法 將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的：而當(dāng)提 供的情報(bào)不夠時(shí)，算法可能無效。*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)匦沽x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的, 且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）算法陌間ggg是指執(zhí)行篦法所需要的計(jì)算匸作就，町以用執(zhí)行算法的過程中所需基 本運(yùn)算的執(zhí)行次數(shù)來度量。（2）算法|空間復(fù)雜度|是指

4、執(zhí)行這個(gè)算法所需要的存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1、|數(shù)據(jù)結(jié)構(gòu)|是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集介。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏借關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息：2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。（2）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、索引等。1）順序存儲。它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯 關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。2）存儲。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相

5、鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的 指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）索引存儲：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏借關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)） 是數(shù)據(jù)的邏輯結(jié)構(gòu)在汁算機(jī)存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的 存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中， 對于數(shù)拯集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)， 并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示

6、各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個(gè)二元 組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）|線性結(jié)構(gòu)| （非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)：2）每一個(gè)結(jié)點(diǎn)最多有 一個(gè)前件，也最多有一個(gè)后件。*：常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）|非線性結(jié)構(gòu)|：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。*：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。1.3線性表及其順序存儲結(jié)構(gòu)1、醫(yī)回由一組數(shù)拯元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位 宜是線性的。線性表是由n（nMO）個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素,

7、除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元 素的個(gè)數(shù)稱為線性表的長度。線性表可以為空表2、線性表的順序存儲結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲空間是連 續(xù)的：（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。*：由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲空間中是緊鄰的, 且前件元素一左存儲在后件元素的前而，可以通過計(jì)算機(jī)直接確左第i個(gè)結(jié)點(diǎn)的存儲地址。3、順序表的插入、刪除運(yùn)算（1）順序表的插入運(yùn)算：任一般情況下，要在第i （lWiWn）個(gè)元素之前插入一個(gè)新元素 時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開始，直到第

8、i個(gè)元素之間共n-i+l個(gè)元素依次向 后移動一個(gè)位程，移動結(jié)朿后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié) 束后，線性表的長度就增加了 1。*:順性表的插入運(yùn)算時(shí)需要移動元素，在等概率情況下，平均需要移動n/2個(gè)元素。（2）順序表的刪除運(yùn)算：在一般情況下，要刪除第i （lWiWn）個(gè)元素時(shí)，則要從第i+1 個(gè)元素開始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動一個(gè)位置。刪除結(jié)束后，線性 表的長度就減小了 lo*：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動元素，在等概率情況下，平均需要移動（n-l） /2 個(gè)元素。插入、刪除運(yùn)算不方便。1.4棧和隊(duì)列1、棧及其基本運(yùn)算岡是限宦在一端進(jìn)行插入與

9、刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素 總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照先進(jìn)后出”或“底 進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是 將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊(duì)列及其基本運(yùn)算回是揺允許任端（隊(duì)尾）進(jìn)行插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針 （Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是“先 進(jìn)先岀

10、”或后進(jìn)后岀”的線性表。隊(duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。 循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個(gè)位置繞到第一個(gè)位宜， 形成邏借上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的 隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后 一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。*：循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)隊(duì)列中元素的個(gè)數(shù)二rear-front。1.5線性鏈表1、線性表順序存儲的缺點(diǎn)：（1）插入或刪除的運(yùn)算效率很低。在順序存儲的線

11、性表中，插 入或刪除數(shù)據(jù)元素時(shí)需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的 存儲空間不便于擴(kuò)充：（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順 宦的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針來實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯Ψ绞?中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存 放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所 示：datanext數(shù)據(jù)域 描針域（a）結(jié)點(diǎn)結(jié)構(gòu)aia：cit i（b）個(gè)非空的線性鏈表示總圖A貞腳.線

12、性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到英后件結(jié)點(diǎn)，而不能找到英 前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)垃兩個(gè)指針，一個(gè)稱為左指 針，指向英前件結(jié)點(diǎn)；另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下 圖所示：左指針數(shù)據(jù)域右描針（a）結(jié)點(diǎn)結(jié)構(gòu)A0HEAD a.A（b）個(gè)非空的雙向鏈表示總圖3、線性鏈表的基本運(yùn)算（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。*：在線性鏈表中插入元素時(shí)，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不 會岀現(xiàn)“上溢”現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)

13、。*：在線性鏈表中刪除元素時(shí)，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。（3）將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。（4）將一個(gè)線性鏈表按要求進(jìn)行分解。（5）逆轉(zhuǎn)線性鏈表。（6）復(fù)制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。*：線性鏈表不能隨機(jī)存取。4、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問題，在運(yùn)算過程中對于 空表和對第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈 表的這個(gè)缺點(diǎn)，可以采用另一種方式，即循環(huán)鏈表。與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1）在鏈表中增加了一個(gè)表頭 結(jié)點(diǎn)，其數(shù)據(jù)

14、域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)，而循 環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)：2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表 頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。31下圖a是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表:非空表（b；空表循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方而：一是在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位 宜，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)；二是由于在 循環(huán)鏈表中設(shè)宜了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使 空表與非空表的運(yùn)算統(tǒng)一。*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個(gè)表頭結(jié)點(diǎn)，

15、其插入和刪除運(yùn)算與單鏈表相同。 但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。1.6樹與二叉樹1、樹的基本概念岡是一種簡單的非緒性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的 層次特性。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為反殛沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹 的限蘊(yùn)司，簡稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的蒔頁沒有后件的 結(jié)點(diǎn)稱為阡孑麗。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該?dān)Q點(diǎn)的度所有結(jié)點(diǎn)中最大的度稱為 葩畫。樹的最大層次稱為|樹的深度2、二叉樹及其基本性質(zhì)（1）什么是二叉樹二岡是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1

16、）非空二叉樹只有一個(gè)根結(jié)點(diǎn);2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。*：根據(jù)二叉樹的概念可知，二叉樹的度可以為0 （葉結(jié)點(diǎn)）、1 （只有一棵子樹）或2 （有 2棵子樹）。（2）二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第k層上，最多有伙XI）個(gè)結(jié)點(diǎn)。例：一棵二叉樹第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為個(gè)。性質(zhì)2深度為m的二叉樹最多有2-1個(gè)結(jié)點(diǎn)。例：深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。 例：某二叉樹中度數(shù)為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹中有個(gè)葉子結(jié)點(diǎn)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，英深度至少為log2”l + l

17、,其中1跆2川表示取log? 的整數(shù)部分。例：具有88個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為。3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 例：在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為個(gè)。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值：在最后一層上只缺少右邊的 若干結(jié)點(diǎn)。*：根據(jù)完全二叉樹的立義可得岀：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：0010（a）滿二叉樹（b）完全二叉樹完全二叉樹還具有如下兩個(gè)特性：性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為log2/7 + L例：具有90個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。性質(zhì)6設(shè)完全二叉樹

18、共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自 然數(shù)1, 2,，n給結(jié)點(diǎn)進(jìn)行編號，則對于編號為k （21, 2,，n）的結(jié)點(diǎn)有以下結(jié)論: 若21,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若kl,則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號為INT（k/2）。 若2kWn,則編號為k的左子結(jié)點(diǎn)編號為2k：否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié) 點(diǎn)）。 若2k+lWn,則編號為k的右子結(jié)點(diǎn)編號為2k+l：否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。例：設(shè)一棵n個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)這一層開始，每一層上的結(jié)點(diǎn)按從左到右的順序 存儲在數(shù)組A中，設(shè)某個(gè)結(jié)點(diǎn)在數(shù)組中的位置為i,則其父結(jié)點(diǎn)的位置是。4、二叉樹的存儲結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹通常

19、采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域。 但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），因此，用于存儲二叉樹 的存儲結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲地址，稱為左指針域; 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地址，稱為右指針域。*： 一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行 順序存儲。5、二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三種：（1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點(diǎn)，然后遍歷左 子樹，

20、最后遍歷右子樹：并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹， 最后遍歷右子樹。（2）中序遍歷（LDR）：若二叉樹為空，則結(jié)朿返回。否則：首先遍歷左子樹，然后訪問根 結(jié)點(diǎn)，最后遍歷右子樹：并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn), 最后遍歷右子樹。（3）后序遍歷（LRD）:若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右 子樹，最后訪問根結(jié)點(diǎn)，并且，在颯歷左、右子樹時(shí)，仍然先颯歷左子樹，然后遍歷右子樹, 最后訪問根結(jié)點(diǎn)。1.7査找技術(shù)査找：根拯給左的某個(gè)值，在査找表中確立一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。査找結(jié)果：（查找成功：找到：查找不成功：沒找到。）

21、平均查找長度：査找過程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序査找基本思想：從表中的第一個(gè)元素開始，將給左的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到 兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。在平均情況下.利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn) 行比較，最壞情況下需要比較丄次。 順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為0 （n）。下列兩種情況下只能采用順序査找：1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯?結(jié)構(gòu)，都只能用順序查找。2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序査找。2、

22、二分法查找思想：先確左待查找記錄所在的圍，然后逐步縮小圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。査找過程：1）若中間項(xiàng)的值等于x,則說明已查到；2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找：3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率髙。最壞的情況下，需要比較log2n次。*：二分法查找只適用于順序存儲的線性表,且表中元素必須按關(guān)鍵字有序（升序，但允許 相鄰元素值相等）排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度 為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為0 （log2n） o1.8排序技術(shù)排序

23、是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào) 整為有序記錄序列的一種操作。1、交換類排序法（方法：冒泡排序，快速排序）。2、插入類排序法（方法：簡單插入排序，希爾排序）。3、選擇類排序法（方法：簡單選擇排序，堆排序）?？偨Y(jié)：各種排序法比較：類別排序方法基本思想時(shí)間復(fù)雜屢交換類冒泡排序相綁元索比較，不滿足條件時(shí)交換如）總快速排序選擇基準(zhǔn)元素，適過交換，劃分成兩個(gè)子序列0仙豳插入類簡單插入排序待排序的元素看成為一個(gè)有序表和一個(gè)無序表， 將無序表中元索插入到有序表中n(n-l)/2希爾排序分割成若千個(gè)子序列分別進(jìn)行直接插入排序0(巧選擇類簡單選擇排序掃描整個(gè)線性表，從

24、中選出最水的元索，將它交 険到表的星前面如）總堆排序選淫堆，然后將堆頂元素與堆中最后一個(gè)元素交 険 再調(diào)整為堆O(nhgn)本章應(yīng)考點(diǎn)撥：本章容在筆試中會出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識部分出題量比較多的一 章，所占分值也比較大，約10分。第二章程序設(shè)計(jì)基礎(chǔ)2.1程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“淸晰第一，效率第二”。主要應(yīng)注重和考慮下述- 1（1）源程序文檔化。1）符號統(tǒng)的命名。符號名能反映它所代表的實(shí)際東西，應(yīng)有一立的實(shí)際含義。2）程序的注釋。分為序言性注釋和功能性注釋。序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程 序位置、開發(fā)簡歷、程序設(shè)計(jì)者、復(fù)審

25、者、復(fù)審日期及修改日期等。功能性注釋：嵌在源程序體之中，用于描述苴后的語句或程序的主要功能。3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟螠[晰。（2）數(shù)據(jù)說明。1）數(shù)據(jù)說明的次序規(guī)化：2）說明語句中變量安排有序化；3）使用注釋來 說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。（3）語句的結(jié)構(gòu)。1）在一行只寫一條語句；2）程序編寫應(yīng)優(yōu)先考慮淸晰性；3）程序編寫 要做到淸晰第一，效率第二：4）在保證程序正確的基礎(chǔ)上再要求提高效率：5）避免使用臨 時(shí)變量而使程序的可讀性下降；6）避免不必要的轉(zhuǎn)移：7）盡量使用庫函數(shù)：8）避免采用 復(fù)雜的條件語句：9）盡量減少使用“否龍”條件語句；10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化: 11）

26、要模塊化，使模塊功能盡可能單一化：12）利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性； 13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；14）不要修補(bǔ)不好的程序，要重新編寫。（4）輸入和輸岀。1）對輸入數(shù)據(jù)檢臉數(shù)據(jù)的合法性；2）檢查輸入項(xiàng)的各種重要組合的合 法性；3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單：4）輸入數(shù)據(jù)時(shí)，應(yīng)允許使 用自由格式：5）應(yīng)允許缺省值：6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)朿標(biāo)志；7）在以交 互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請求，同時(shí)在數(shù)據(jù) 輸入過程中和輸入結(jié)朿時(shí)，應(yīng)在屏幕上給岀狀態(tài)信息；8）當(dāng)程序設(shè)計(jì)語言對輸入格式有嚴(yán) 格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一

27、致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格 式。2.2結(jié)構(gòu)化程序設(shè)計(jì)（面向過程的程序設(shè)計(jì)方法）1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下,逐步求精,模塊化,限制使用 goto語句。（1）自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)：先考慮全局目標(biāo)，后考慮局部 目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。（2）逐步求精。對復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。（3）模塊化。一個(gè)復(fù)雜問題，肯立是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的 總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。（4）限制使用goto語句。

28、2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu),選擇結(jié)構(gòu),重復(fù)結(jié)構(gòu)。1）順序結(jié)構(gòu)。一種簡單的程序設(shè)計(jì)，即按照程序語句行的自然順序，一條語句一條語句地 執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)。2）選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選 擇哪一條分支來執(zhí)行相應(yīng)的語句序列。3）重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu),可根據(jù)給泄的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類 似的程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何 單入口 /單出口的程序。2.3面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對象,面向?qū)ο蠓椒ǖ谋举|(zhì)就是主從客觀世界 固有

29、的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實(shí)生活中常用的思維來認(rèn)識、理解和描述客觀事 拯強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的對象及對象之間的關(guān)系能夠 如實(shí)地反映問題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類習(xí)慣的思維方法一致:（2）穩(wěn)立性好;（3）可重用性 妊：（4）易于開發(fā)大型軟件產(chǎn)品:（5）可維護(hù)性好。*：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提髙軟件的可重用性?；厥嵌?qū)ο蠓椒ㄖ凶罨镜臉Ｄ?，可以用來表示客觀世界中的任何實(shí)體，對象是實(shí)體 的抽象。而向?qū)﹀璧某绦蛟O(shè)計(jì)方法中的對象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成 系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可

30、執(zhí)行的一組操作組成。*：對象是屬性和方法的封裝體。亟即對象所包含的信息，它在設(shè)汁對象時(shí)確左，一般只能通過執(zhí)行對象的操作來改變。 畫描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。*：操作是對象的動態(tài)屬性。*：-個(gè)對象山對象名、屬性和操作三部分組成。對象的基本特點(diǎn)：標(biāo)識惟一性,分類性,多態(tài)性,封裝性,模塊獨(dú)立性好。（1）標(biāo)識惟一性。指對象是可區(qū)分的，并且由對象的在本質(zhì)來區(qū)分，而不是通過描述來區(qū) 分。（2）分類性。指可以將具有相同屬性的操作的對象抽象成類。（3）多態(tài)性。指同一個(gè)操作可以是不同對象的行為。（4）封裝性。從外而看只能看到對象的外部特性，即只需知道數(shù)搦的取值用和可以對該數(shù) 據(jù)施加的操作，根本

31、無需知道數(shù)需的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對象的部，即處理能力 的實(shí)行和部狀態(tài)，對外是不可見的。從外面不能直接使用對象的處理能力，也不能宜接修改 其部狀態(tài)，對象的部狀態(tài)只能由其自身改變。*：信息隱蔽是通過對象的JI裝嘗來實(shí)現(xiàn)的。（5）模塊獨(dú)立性好。對象是而向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施 加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作用繞對其數(shù)據(jù)所需做的處理來 設(shè)苣，沒有無關(guān)的操作。從模塊的獨(dú)立性考慮，對象部各種元素彼此結(jié)合得很緊密，聚性強(qiáng)。 囲是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一 個(gè)實(shí)例。畫是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信

32、息。消息的組成包括：（1）接收消息的對象的 名稱：（2）消息標(biāo)識符，也稱消息名；（3）零個(gè)或多個(gè)參數(shù)。*：在而向?qū)ο蠓椒ㄖ?，一個(gè)對象請求另一個(gè)對彖為苴服務(wù)的方式是通過發(fā)送消息。 壓是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼 承。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。*：類的繼承性是類之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性。 壅囲是指同樣的消息被不同的對象接受時(shí)可導(dǎo)致完全不同的行動的現(xiàn)象。本章應(yīng)考點(diǎn)撥：本章在考試中會出現(xiàn)約1個(gè)題目，所占分值大約占2分，是出題量較小的一 章。本章容比較少，也很簡單，掌握住基本的概念就可以輕松應(yīng)對考

33、試了，所以在這部分丟 分，比較可惜。第三章軟件工程基礎(chǔ)3.1軟件工程基本概念1、軟件的相關(guān)概念計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體,而不是物理實(shí)體，具有抽象性；2）軟件的生產(chǎn) 與硬件不同，它沒有明顯的制作過程：3）軟件在運(yùn)行、使用期間不存在磨損、老化問題；4） 軟件的開發(fā)、運(yùn)行對計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問 題：5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會因素。2、軟件危機(jī)與軟件工程軟件工程概念的出現(xiàn)源自建觸所謂軟件危機(jī)是泛指在汁算機(jī)軟件的開發(fā)和維護(hù)過程中 所遇到的一系列嚴(yán)重問題。具體的說，在軟件開發(fā)

34、和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生。2）軟件開發(fā)成本和進(jìn)度無法控制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)泄日期的情況 經(jīng)常發(fā)生。3軟件質(zhì)量難以保證。4）軟件不可維護(hù)或維護(hù)程度非常低。5）軟件的成本不斷提髙。6）軟件開發(fā)生產(chǎn)率的提髙跟不上硬件的發(fā)展和應(yīng)用需求的增長?？傊?，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。軟歴裡是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn) 和工序。軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的容概括為以下兩點(diǎn)：1）軟件開發(fā)技術(shù),主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境

35、。2）軟件工程管理,主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工化原則運(yùn)用到軟件開發(fā)過程，它包括3個(gè)要素：方法、工具和 過程。歴|是完成軟件工程項(xiàng)目的技術(shù)手段; 回是支持軟件的開發(fā)、管理、文檔生成： 畫支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。3、軟件生命周期軟件生命周期|：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。 軟件生命周期分為軟件立義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段:1）軟件立義階段：包括制上訃劃和需求分析。制左計(jì)劃：確左總目標(biāo)：可行性研究；探討解決方案；制泄開發(fā)計(jì)劃。需求分析：對待開發(fā)軟件提出的需求進(jìn)行分析并給

36、岀詳細(xì)的泄義。2）軟件開發(fā)階段：軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。軟件實(shí)現(xiàn)：把軟件設(shè)汁轉(zhuǎn)換成汁算機(jī)可以接受的程序代碼。軟件測試：在設(shè)計(jì)測試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改。*：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。4、軟件工程的目標(biāo)與原則（1）軟件工程目標(biāo)：在給泄成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、 可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。（2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達(dá)到要求的軟件功能：取 得較好的軟件

37、性能：開發(fā)的軟件易于移植：需要較低的維護(hù)費(fèi)用：能按時(shí)完成開發(fā)，及時(shí)交 付使用。（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確泄性、一致性、完備性和可驗(yàn) 證性。1）匝逐抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)肖，采用分層次抽象，自頂向下, 逐層細(xì)化的辦法控制軟件開發(fā)過程的復(fù)雜性。2）|信息隱闕:采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)肖隱蔽起來，使模塊接口盡量簡單。3）|SW|：模塊是程序中相對獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口左義。 模塊的大小要適中，模塊過大會使模塊部的復(fù)雜性增加，不利于模塊的理解和修改，也不利 于模塊的調(diào)試和重用：模塊太小會導(dǎo)致整個(gè)系統(tǒng)表示過于復(fù)雜.不利于控制

38、系統(tǒng)的復(fù)雜性。4)局部化5)確定性6)一致性7)完備性8)可驗(yàn)證性保證模塊間具有松散的耦合關(guān)系，模塊部有較強(qiáng)的聚性。 軟件開發(fā)過程中所有槪念的表達(dá)應(yīng)是確定、無歧義且規(guī)的。程序外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。 軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。:應(yīng)遵循容易檢査、測評、評審的原則，以確保系統(tǒng)的正確性。5、軟件開發(fā)工具與軟件開發(fā)環(huán)境 （1）軟件開發(fā)工具軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高 質(zhì)屋。軟件開發(fā)工具的發(fā)展是從單項(xiàng)工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟 件工程方法提供了自動的或半自動的軟件支撐環(huán)境。同

39、時(shí)，軟件開發(fā)方法的有效應(yīng)用也必須 得到相應(yīng)工具的支持，否則方法將難以有效的實(shí)施。（2）軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合。計(jì)算機(jī)輔助軟件工程（CASE, Computer Aided Software Engineering）將各種軟件工具、 開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫組合尼來，形成軟件工程環(huán)境。它將極大降 低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。3.2結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。1. 需求分析需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）而向?qū)ο蟮姆治龇椒ā?： |需求分析|的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的

40、邏輯模型,解決“做什么”的問題。*:需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個(gè)步驟進(jìn)行。2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下,逐層分解,建立系統(tǒng)的處理流程,以數(shù) 據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏借模型。結(jié)構(gòu)化分析的常用工具:1）數(shù)據(jù)流圖（DFD）； 2）數(shù)據(jù)字典（DD）； 3）判定樹;4）判左表。 數(shù)據(jù)流圖|以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程,它反映了系統(tǒng)必須完成的邏 輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。下圖是數(shù)據(jù)流圖的基本圖形元素：加工數(shù)據(jù)流

41、存儲文件源、潭麗I （轉(zhuǎn)換）:輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸岀。ot|：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。 存儲文件| （數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。區(qū)團(tuán)：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。畫數(shù)據(jù)流圖的基本步驟：自外向，自頂向下，逐層細(xì)化，完善求精。 下圖是一個(gè)數(shù)據(jù)流圖的示例：帳卡|數(shù)據(jù)字典|：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義, 使得用戶和系統(tǒng)分析員對于輸入、輸岀、存儲成分和中間計(jì)算結(jié)果有共同的理解。*：數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。*：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、軟件需求規(guī)格說明書（S

42、RS）軟件禹求規(guī)格說麗|是需求分析階段的最后成果,通過建立完整的信息描述、詳細(xì)的功能 和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對目標(biāo)軟件的各種需求。 軟件需求規(guī)格說明書應(yīng)具有以下特點(diǎn)：1）正確性；2）無歧義性：3）完整性：4）可驗(yàn)證性: 5） 一致性：6）可理解性：7）可修改性：8）可追蹤性，其中最重要的特點(diǎn)是無歧義性。3.3結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)的基礎(chǔ)*：需求分析主要解決做什么”的問題，而軟件設(shè)計(jì)主要解決“怎么做”的問題。99從技術(shù)觀點(diǎn)來看，軟件設(shè)汁包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)訃、過程設(shè)汁。結(jié)構(gòu)設(shè)訃 數(shù)據(jù)設(shè)訃 接口設(shè)汁 過程設(shè)計(jì) 泄義軟件系統(tǒng)冬主要部件之間的關(guān)系。

43、將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的泄義。描述軟件部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。從工程角度來看，軟件設(shè)汁分兩步完成，即概要設(shè)訃和詳細(xì)設(shè)計(jì)。 概要設(shè)訓(xùn):又稱結(jié)構(gòu)設(shè)讓，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確左系統(tǒng)級接口、全局?jǐn)?shù)據(jù) 結(jié)構(gòu)或數(shù)據(jù)庫模式。詳細(xì)設(shè)計(jì)確定每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的 細(xì)節(jié)。軟件設(shè)計(jì)的基本原理包括：迪愛、模塊化、信息隱蔽和模塊獨(dú)立性。1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他細(xì)節(jié)。2）模塊化。解決一個(gè)復(fù)雜問題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對獨(dú)立 但

44、又不相互關(guān)聯(lián)的模塊的過程。3）信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對于其他模塊來說是隱蔽的。4）模塊獨(dú)立性。軟件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其 他的模塊的接口是簡單的。*：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。模塊的越辿和輕是衡量軟件的模塊獨(dú)立性的兩個(gè)左性指標(biāo)。在結(jié)構(gòu)化程序設(shè)汁中，模塊 劃分的原則是：模塊具有髙聚度，模塊間具有低耦合度。傳入模塊 傳出模塊 變換模塊 協(xié)調(diào)模塊寬度 扇入 扇出原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊。下圖是一個(gè)程序結(jié)構(gòu)圖的示例:國性：是一個(gè)模塊部各個(gè)元素間彼此結(jié)合的緊密程度的度量。*:按聚性由弱到強(qiáng)排列，聚可以分為以下幾種：偶然聚、邏輯聚、時(shí)

45、間聚、過程聚、通信 聚、順序聚及功能聚。逼囹性：是模塊間互相連接的緊密程度的度量。*:按耦合性由高到低排列，耦合可以分為以下幾種：容耦合、公共耦合、外部耦合、控制 耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有髙聚、低耦合的特征。2、總體設(shè)計(jì)（概要設(shè)計(jì)）和詳細(xì)設(shè)計(jì)（1）總體設(shè)計(jì)（概要設(shè)計(jì)）軟件槪要設(shè)計(jì)的基本任務(wù)是：1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)訃；3）編寫 概要設(shè)計(jì)文檔：4）概要設(shè)計(jì)文檔評審。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示 模塊調(diào)用過程中來

46、回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭 心表示傳遞的是數(shù)據(jù)信息。-. 命.一般模塊數(shù)據(jù)信息控制信息經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。苴表示形 式如下圖：/ AI傳入A塊I它們的含義分別是：:從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將英傳送給上級模塊。:從上級模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊匚:從上級模塊取得數(shù)拯，進(jìn)行特泄的處理，轉(zhuǎn)換成其他形式，再傳送給上級模塊。 :對所有下屬模塊進(jìn)行協(xié)調(diào)和管理的模塊。程序結(jié)構(gòu)圖的有關(guān)術(shù)語列舉如下：麗:表示控制的層數(shù)。上級模塊、從屬模塊：上、下兩層模塊a和b,且有。調(diào)用b,則a是上級模塊，b是從屬 模塊

47、。:整體控制跨度（最大模塊數(shù)的層）的表示。:調(diào)用一個(gè)給左模塊的模塊個(gè)數(shù)。:一個(gè)模塊直接調(diào)用的其他模塊數(shù)。頁腳.面向數(shù)據(jù)流的設(shè)汁方法立義了一些不同的映射方法，利用這些方法可以把她函變換成結(jié) 構(gòu)圖表示軟件的結(jié)構(gòu)。數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。A、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出 數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。B、事務(wù)型：事務(wù)型數(shù)拯處理問題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)， 選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧缓蠼o岀結(jié)果。（2）詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確左實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)

48、，用某種選左的表達(dá) 工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。*:詳細(xì)設(shè)汁的任務(wù)是確左實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。常用的過程設(shè)計(jì)（即詳細(xì)設(shè)計(jì)）工具有以下幾種：圖形工具：程序流程圖、N-S （方盒圖）、PAD （問題分析圖）和HIPO （層次圖+輸入/處理/ 輸岀圖）。表格工具：判能表。語言工具：PDL （偽碼）3.4軟件測試1、軟件測試定義：使用人工或自動手段來運(yùn)行或測立某個(gè)系統(tǒng)的過程，苴目的在于檢驗(yàn)它 是否滿足規(guī)左的需求或是弄淸預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。*：軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯誤,不能也不可能證明程序沒有錯誤。軟 件測試的關(guān)鍵是設(shè)汁測試用例,一個(gè)好的測試用例能找到迄

49、今為I匕尚未發(fā)現(xiàn)的錯誤。2、軟件測試方法：靜態(tài)測試和動態(tài)測試。靜態(tài)測訓(xùn):包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過人 工進(jìn)行。動態(tài)測試|：是基于計(jì)算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法。（1）白盒測試白盒測試方法也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的部工作過程，檢查部成 分，以確認(rèn)每種部操作符合設(shè)計(jì)規(guī)格要求。白盒測試的基本原則：保證所測模塊中每一獨(dú)立路徑至少執(zhí)行一次：保證所測模塊所有判斷 的每一分支至少執(zhí)行一次:保證所測模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一 次；驗(yàn)證所有部數(shù)據(jù)結(jié)構(gòu)的有效性。*：白盒測試法的測試用例是根據(jù)程序的蟄邏遐來設(shè)計(jì)的，

50、主要用軟件的單元測試,主要方 法有邏輯覆蓋、基本路徑測試等。A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序部的邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計(jì)技術(shù)。通常 程序中的邏輯表示有判斷、分支、條件等幾種表示方法。語句覆蓋：選擇足夠的測試用例，使得程序中每一個(gè)語句至少都能被執(zhí)行一次。 路徑覆蓋：執(zhí)行足夠的測試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。判左覆蓋：使設(shè)計(jì)的測試用例保證程序中每個(gè)判斷的每個(gè)取值分支（T或F）至少經(jīng)歷一次。 條件覆蓋：設(shè)訃的測試用例保證程序中每個(gè)判斷的每個(gè)條件的可能取值至少執(zhí)行一次。 判斷-條件覆蓋：設(shè)計(jì)足夠的測試用例，使判斷中每個(gè)條件的所有可能取值至少執(zhí)行一次， 同時(shí)每個(gè)判斷的所有可能

51、取值分支至少執(zhí)行一次。*：邏輯覆蓋的強(qiáng)度依次是：語句覆蓋路徑覆蓋判左覆蓋條件覆蓋判斷-條件覆蓋。B、基本路徑測試。其思想和步驟是，根據(jù)軟件過程性描述中的控制流程確左程序的環(huán)路復(fù) 雜性度量，用此度量左義基本路徑集合，并由此導(dǎo)出一組測試用例，對每一條獨(dú)立執(zhí)行路徑 進(jìn)行測試。（2）黑盒測試黑盒測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實(shí)現(xiàn)的功能是查潢足 需求進(jìn)行測試和驗(yàn)證。黑盒測試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、 初始化和終止條件錯誤。黑盒測試不關(guān)心程序部的邏輯，只是根據(jù)程序的功能說明來設(shè)汁測試用例,主要方法有等價(jià) 類劃分法、邊界值分析法、錯

52、誤推測法等,主要用軟件的確認(rèn)測試。A、|等價(jià)類劃分法這是一種典型的黑盒測試方法，它是將程序的所有可能的輸入數(shù)據(jù)劃分 成若干部分（及若干等價(jià)類），然后從每個(gè)等價(jià)類中選取數(shù)據(jù)作為測試用例。B、曲界值分析法它是對各種輸入、輸岀羽的邊界情況設(shè)計(jì)測試用例的方法。C、|錯誤推測法人們可以靠經(jīng)驗(yàn)和直覺推測程序中可能存在的各種錯誤，從而有針對性地 編寫檢査這些錯誤的用例。3、軟件測試過程一般按4個(gè)步驟進(jìn)行：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試。（1）單元測試單元測試|是對軟件設(shè)訃的最小單位一一模塊（程序單元）進(jìn)行正確性檢測的測試，口的是 發(fā)現(xiàn)各模塊部可能存在的各種錯誤。單元測試根據(jù)程序的部結(jié)構(gòu)來設(shè)訃測試用例

53、,其依據(jù)是詳細(xì)設(shè)汁說明書和源程序。單元測試 的技術(shù)可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒測試為主,輔之以黑盒測試。 單元測試的容包括：模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、錯誤處理測試和邊界測試。*：在進(jìn)行單元測試時(shí)，要用一些輔助模塊去模擬與被測模塊相聯(lián)系的英他模塊,即為被測 模塊設(shè)汁和搭建驅(qū)動模塊和樁模塊。其中，|驅(qū)動模塊|相當(dāng)于被測模塊的主程序，它接收測 試數(shù)據(jù)，并傳給被測模塊，輸出實(shí)際測試結(jié)果：而睡亟是模擬苴他被調(diào)用模塊，不必將 子模塊的所有功能帶入。（2）集成測試集成測試|是測試和組裝軟件的過程,它是把模塊在按照設(shè)訃要求組裝起來的同時(shí)進(jìn)行測試, 主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤。集成

54、測試的依據(jù)是概要設(shè)計(jì)說明書。集成測試所涉及的容包括：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入 的測試等。集成測試通常采用兩種方式：非增量方式組裝與增量方式組裝。非增量方式組裝|：也稱為一次性組裝方式。首先對每個(gè)模塊分別進(jìn)行模塊測試，然后再把 所有模塊組裝在一起進(jìn)行測試，最終得到要求的軟件系統(tǒng)。增量方式組裝|：又稱漸增式集成方式。首先對一個(gè)個(gè)模塊進(jìn)行模塊測試，然后將這些模塊 逐步組裝成較大的系統(tǒng)，在組裝的過程中邊連接邊測試，以發(fā)現(xiàn)連接過程中產(chǎn)生的問題。最 后通過增殖逐步組裝成要求的軟件系統(tǒng)。增屋方式組裝又包括自頂向下、自底向上、自頂向 下與自底向上相結(jié)合等三種方式。（3）確認(rèn)測試

55、確認(rèn)測訓(xùn)的任務(wù)是驗(yàn)證軟件的有效性,即驗(yàn)證軟件的功能和性能及其他特性是否與用戶的 要求一致。確認(rèn)測試的主要依拯是軟件需求規(guī)格說明書。確認(rèn)測試主要運(yùn)用黑盒測試法。（4）系統(tǒng)測試系統(tǒng)測試|的目的在于通過與系統(tǒng)的需求立義進(jìn)行比較，發(fā)現(xiàn)軟件與系統(tǒng)泄義不符合或與Z 矛盾的地方。系統(tǒng)測試的測試用例應(yīng)根拯需求分析規(guī)格說明來設(shè)計(jì)，并在實(shí)際使用環(huán)境下來運(yùn)行。系統(tǒng)測試的具體實(shí)施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口測試、 安全性測試等。3.5程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤,主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)該由編制源 程序的程序員來完成。程序調(diào)試的基本步驟：（1）錯誤左位:（2）糾正錯誤;（3）回歸測試。*：軟件的調(diào)試后要進(jìn)行型I測試,防止引進(jìn)新的錯誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和 排錯，是主要的調(diào)試手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。對軟件主要的調(diào)試方法可以采用：（1）強(qiáng)行排錯法。主要方法有：通過存全部打印來排錯：在程序特定部位設(shè)置打印語句： 自動調(diào)試工具。（2）回溯法。發(fā)現(xiàn)了錯誤，分析錯誤征兆，確定發(fā)現(xiàn)“癥狀”的位JIL 一般用于小程序。（3）原因排除法。是通過演繹、歸納和二分法來實(shí)現(xiàn)的