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

1、ncre 二級(jí)公共基礎(chǔ)學(xué)問輔導(dǎo)講義全國運(yùn)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)學(xué)問輔導(dǎo)講義目錄第一章數(shù)據(jù)結(jié)構(gòu)與算法11.1 算法11.2 數(shù)據(jù)結(jié)構(gòu)的基本概念11.3 線性表及其次序儲(chǔ)備結(jié)構(gòu)21.4 棧和隊(duì)列21.5 線性鏈表31.6 樹與二叉樹41.7 查找技術(shù)51.8 排序技術(shù)6本章應(yīng)考點(diǎn)撥6其次章程序設(shè)計(jì)基礎(chǔ)72.1 程序設(shè)計(jì)風(fēng)格72.2 結(jié)構(gòu)化程序設(shè)計(jì)（面對(duì)過程的程序設(shè)計(jì)方法）72.3 面對(duì)對(duì)象的程序設(shè)計(jì)8本章應(yīng)考點(diǎn)撥8第三章軟件工程基礎(chǔ)93.1 軟件工程基本概念93.2 結(jié)構(gòu)化分析方法103.3 結(jié)構(gòu)化設(shè)計(jì)方法113.4 軟件測試133.5 程序的調(diào)試15本章應(yīng)考點(diǎn)撥15第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)164.

2、1 數(shù)據(jù)庫系統(tǒng)的基本概念164.2 數(shù)據(jù)模型184.3 關(guān)系代數(shù)204.4 數(shù)據(jù)庫設(shè)計(jì)方法和步驟21本章應(yīng)考點(diǎn)撥21incre 二級(jí)公共基礎(chǔ)學(xué)問輔導(dǎo)講義第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法1、算法是指解題方案的精確而完整的描述；換句話說，算法是對(duì)特定問題求解步驟的一種描述；* ：算法不等于程序，也不等于運(yùn)算方法；程序的編制不行能優(yōu)于算法的設(shè)計(jì)；2、算法的基本特點(diǎn)（ 1）可行性；針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到中意的結(jié)果；（ 2）確定性；每一條指令的含義明確，無二義性；并且在任何條件下，算法只有唯獨(dú)的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出；（ 3）有窮性；算法必需在有限的時(shí)間內(nèi)完成；有

3、兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成；（ 4）擁有足夠的情報(bào)；算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)；因此， 一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)， 不同的輸入將會(huì)有不同的結(jié)果輸出；當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無法執(zhí)行或執(zhí)行有錯(cuò)；一般說來，當(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ù)雜度

4、；（ 1）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量；（ 2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間；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ī)律關(guān)系，即數(shù)據(jù)的規(guī)律結(jié)構(gòu)；數(shù)據(jù)的規(guī)律結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系；（ 2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在運(yùn)算機(jī)中的儲(chǔ)備關(guān)系，即數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)；數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)有次序、鏈接、索引等； 1）次序儲(chǔ)備；它是把規(guī)律上相鄰的結(jié)點(diǎn)儲(chǔ)備在物理位置相鄰的

5、儲(chǔ)備單元里，結(jié)點(diǎn)間的規(guī)律關(guān)系由儲(chǔ)備單元的鄰接關(guān)系來表達(dá)；由此得到的儲(chǔ)備表示稱為次序儲(chǔ)備結(jié)構(gòu)； 2）鏈接儲(chǔ)備；它不要求規(guī)律上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的規(guī)律關(guān)系是由附加的指針字段表示的；由此得到的儲(chǔ)備表示稱為鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)； 3）索引儲(chǔ)備：除建立儲(chǔ)備結(jié)點(diǎn)信息外，仍建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址；* ：數(shù)據(jù)的規(guī)律結(jié)構(gòu)反映數(shù)據(jù)元素之間的規(guī)律關(guān)系，數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu) （也稱數(shù)據(jù)的物理結(jié)構(gòu)） 是數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)儲(chǔ)備空間中的存放形式；同一種規(guī)律結(jié)構(gòu)的數(shù)據(jù)可以采納不同的 儲(chǔ)備結(jié)構(gòu)，但影響數(shù)據(jù)處理效率；（ 3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算；3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，仍可以

6、直觀地用圖形表示； 在數(shù)據(jù)結(jié)構(gòu)的圖形表示中， 對(duì)于數(shù)據(jù)集合 d 中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)； 為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系 r 中的每一個(gè)二元21組，用一條有向線段從前件結(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 線性表及其次序儲(chǔ)備結(jié)構(gòu)1、

7、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的； 線性表是由 nn 0 個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素， 除了第一個(gè)外，有且只有一個(gè)前件，除了最終一個(gè)外，有且只有一個(gè)后件；線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長度；線性表可以為空表；2、線性表的次序儲(chǔ)備結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（ 1）線性表中全部元素所占的儲(chǔ)備空間是連續(xù)的；（ 2）線性表中各數(shù)據(jù)元素在儲(chǔ)備空間中是按規(guī)律次序依次存放的；* ：由此可以看出， 在線性表的次序儲(chǔ)備結(jié)構(gòu)中，其前后件兩個(gè)元素在儲(chǔ)備空間中是緊鄰 的，且前件元素肯定儲(chǔ)備在后件元素的前面，可以通過運(yùn)算機(jī)直接確定第i 個(gè)結(jié)點(diǎn)

8、的儲(chǔ)備地址；3、次序表的插入、刪除運(yùn)算（ 1）次序表的插入運(yùn)算：在一般情形下，要在第i （1 i n）個(gè)元素之前插入一個(gè)新元素時(shí)，第一要從最終一個(gè)（即第n 個(gè)）元素開頭，直到第i 個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)終止后，第i 個(gè)位置就被空出，然后將新元素插入到第i 項(xiàng)；插入終止后，線性表的長度就增加了1；* ：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情形下，平均需要移動(dòng)n/2 個(gè)元素；（ 2）次序表的刪除運(yùn)算：在一般情形下，要?jiǎng)h除第 i （1 i n）個(gè)元素時(shí)，就要從第 i+1 個(gè)元素開頭， 直到第 n 個(gè)元素之間共 n-i 個(gè)元素依次向前移動(dòng)一個(gè)位置； 刪除終止后， 線

9、性表的長度就減小了 1；* ：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情形下，平均需要移動(dòng)（ n-1 ） /2個(gè)元素；插入、刪除運(yùn)算不便利；1.4 棧和隊(duì)列1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性 表；在棧中， 答應(yīng)插入與刪除的一端稱為棧頂，不答應(yīng)插入與刪除的另一端稱為棧底；棧頂元素總是最終被插入的元素， 棧底元素總是最先被插入的元素；即棧是依據(jù)“先進(jìn)后出”或“后 進(jìn)先出”的原就組織數(shù)據(jù)的；棧具有記憶作用；棧的基本運(yùn)算： 1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化；棧的儲(chǔ)備方式和線性表類似，也有兩種，即

10、次序棧和鏈?zhǔn)綏＃?、隊(duì)列及其基本運(yùn)算隊(duì)列是指答應(yīng)在一端（隊(duì)尾）進(jìn)行插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性 表；尾指針（ rear ）指向隊(duì)尾元素， 頭指針（ front）指向排頭元素的前一個(gè)位置（隊(duì)頭） ；隊(duì)列是“先進(jìn)先出”或“后進(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ì)列儲(chǔ)備空間的最終一個(gè)位置繞到第一個(gè)位置，形成規(guī)律上的環(huán)狀空間，供隊(duì)列循環(huán)使用；在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素， 用排頭指針 front指向排頭元素的前一個(gè)位置，因此， 從頭指針 front指向的后一個(gè)位置直

11、到隊(duì)尾指針rear指向的位置之間，全部的元素均為隊(duì)列中的元素；* ：循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)，循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front；1.5 線性鏈表1、線性表次序儲(chǔ)備的缺點(diǎn)：（ 1）插入或刪除的運(yùn)算效率很低；在次序儲(chǔ)備的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素；（2）線性表的次序儲(chǔ)備結(jié)構(gòu)下，線性表的儲(chǔ)備空間不便于擴(kuò)充；（3）線性表的次序儲(chǔ)備結(jié)構(gòu)不便于對(duì)儲(chǔ)備空間的動(dòng)態(tài)安排；2、線性鏈表：線性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)稱為線性鏈表，是一種物理儲(chǔ)備單元上非連續(xù)、非順序的儲(chǔ)備結(jié)構(gòu)， 數(shù)據(jù)元素的規(guī)律次序是通過鏈表中的指針鏈接來實(shí)現(xiàn)的；因此， 在鏈?zhǔn)絻?chǔ)備方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于

12、存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所示：數(shù)據(jù)域指針域datanextheada1a2an-1an(a) 結(jié)點(diǎn)結(jié)構(gòu)b 一個(gè)非空的線性鏈表示意圖線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型；在單鏈表中， 每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)；因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示：左指針數(shù)據(jù)域(a) 結(jié)點(diǎn)結(jié)構(gòu)右指針heada1a2(b) 一個(gè)非空的雙向鏈

13、表示意圖an3、線性鏈表的基本運(yùn)算（ 1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素；* ：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)顯現(xiàn)“上溢”現(xiàn)象；（ 2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)；* ：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可；（ 3）將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表；（ 4）將一個(gè)線性鏈表按要求進(jìn)行分解；（ 5）逆轉(zhuǎn)線性鏈表；（ 6）復(fù)制線性鏈表；（ 7）線性鏈表的排序；（ 8）線性鏈表的查找；* ：線性鏈表不能隨機(jī)存?。?、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中， 其插入與刪除的運(yùn)算雖然比較便利， 但

14、仍存在一個(gè)問題， 在運(yùn)算過程中對(duì)于空表和對(duì)第一個(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ù)域?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)狀鏈；下圖 a 是一個(gè)非空的循環(huán)鏈表，圖b 是一個(gè)空的循環(huán)鏈表：循環(huán)鏈表的優(yōu)點(diǎn)主要表達(dá)在兩個(gè)方面：一是在循環(huán)鏈表中， 只要指出表中任何一個(gè)

15、結(jié)點(diǎn)的位置， 就可以從它動(dòng)身拜訪到表中其他全部的結(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)，其插入和刪除運(yùn)算與單鏈表相同；但它可以從任一結(jié)點(diǎn)動(dòng)身來拜訪表中其他全部結(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)；沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根；每一個(gè)結(jié)點(diǎn)可以有多個(gè)后

16、件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)；在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，全部結(jié)點(diǎn)中最大的度稱為樹的度；樹的最大層次稱為樹的深度；2、二叉樹及其基本性質(zhì)（ 1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)： 1）非空二叉樹只有一個(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 層上，最多有2 k 1k1) 個(gè)結(jié)點(diǎn)；例： 一棵二叉樹第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為個(gè)；性

17、質(zhì) 2深度為 m的二叉樹最多有 2m1 個(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)的二叉樹，其深度至少為的整數(shù)部分；log 2 n1 ，其中l(wèi)og 2 n 表示取log 2 n例： 具有 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á)到最

18、大值；在最終一層上只缺少右邊的如干結(jié)點(diǎn)；* ：依據(jù)完全二叉樹的定義可得出：度為1 的結(jié)點(diǎn)的個(gè)數(shù)為 0 或 1；下圖 a 表示的是滿二叉樹，下圖b 表示的是完全二叉樹：001212345634567891011121314789a 滿二叉樹完全二叉樹仍具有如下兩個(gè)特性：b 完全二叉樹性質(zhì) 5具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹深度為log 2 n例： 具有 90 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為1；性質(zhì) 6設(shè)完全二叉樹共有n 個(gè)結(jié)點(diǎn)，假如從根結(jié)點(diǎn)開頭，按層序（每一層從左到右）用自然數(shù) 1， 2， n 給結(jié)點(diǎn)進(jìn)行編號(hào)，就對(duì)于編號(hào)為k（ k=1 ，2， n）的結(jié)點(diǎn)有以下結(jié)論：如 k=1 ，就該結(jié)點(diǎn)為根結(jié)點(diǎn)， 它沒

19、有父結(jié)點(diǎn)； 如 k>1 ，就該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為intk/2；如 2kn，就編號(hào)為 k 的左子結(jié)點(diǎn)編號(hào)為點(diǎn)）；2k；否就該結(jié)點(diǎn)無左子結(jié)點(diǎn)（明顯也沒有右子結(jié)如 2k+1 n，就編號(hào)為 k 的右子結(jié)點(diǎn)編號(hào)為2k+1；否就該結(jié)點(diǎn)無右子結(jié)點(diǎn)；例：設(shè)一棵 n 個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)這一層開頭，每一層上的結(jié)點(diǎn)按從左到右的次序儲(chǔ)備在數(shù)組 a 中，設(shè)某個(gè)結(jié)點(diǎn)在數(shù)組中的位置為i ，就其父結(jié)點(diǎn)的位置是；4、二叉樹的儲(chǔ)備結(jié)構(gòu)在運(yùn)算機(jī)中，二叉樹通常采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)；與線性鏈表類似，用于儲(chǔ)備二叉樹中各元素的儲(chǔ)備結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域；但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），因

20、此，用于儲(chǔ)備二叉樹的儲(chǔ)備結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的儲(chǔ)備地址，稱為左指針域； 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的儲(chǔ)備地址，稱為右指針域；* ：一般二叉樹通常采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行次序儲(chǔ)備；5、二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地拜訪二叉樹中的全部結(jié)點(diǎn)；二叉樹的遍歷可以分為以下三種：（ 1）前序遍歷（ dlr）：如二叉樹為空，就終止返回；否就：第一拜訪根結(jié)點(diǎn)，然后遍歷左子樹，最終遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍舊先拜訪根結(jié)點(diǎn)，然后遍歷左子樹， 最終遍歷右子樹；（ 2）中序遍歷（ ldr）：如二叉樹為空，就終止返回；否就：第一遍歷左

21、子樹，然后拜訪根結(jié)點(diǎn)， 最終遍歷右子樹； 并且， 在遍歷左、 右子樹時(shí)， 仍舊先遍歷左子樹，然后拜訪根結(jié)點(diǎn)， 最終遍歷右子樹；（ 3）后序遍歷（ lrd）：如二叉樹為空，就終止返回；否就：第一遍歷左子樹，然后遍歷右子樹， 最終拜訪根結(jié)點(diǎn)， 并且， 在遍歷左、 右子樹時(shí)， 仍舊先遍歷左子樹，然后遍歷右子樹， 最終拜訪根結(jié)點(diǎn)；1.7 查找技術(shù)查找：依據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素；查找結(jié)果：（查找勝利：找到；查找不勝利：沒找到；）平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)；1、次序查找基本思想： 從表中的第一個(gè)元素開頭，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行

22、比較，直到兩者相符，查到所要找的元素為止；否就就是表中沒有要找的元素，查找不勝利；在平均情形下， 利用次序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情形下需要比較 n 次；次序查找一個(gè)具有n 個(gè)元素的線性表，其平均復(fù)雜度為o（ n）；以下兩種情形下只能采納次序查找：1）假如線性表是無序表（即表中的元素是無序的），就不管是次序儲(chǔ)備結(jié)構(gòu)仍是鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)，都只能用次序查找； 2）即使是有序線性表，假如采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)，也只能用次序查找；2、二分法查找思想： 先確定待查找記錄所在的范疇，然后逐步縮小范疇，直到找到或確認(rèn)找不到該記錄為止；前提：必需在具有次序儲(chǔ)備結(jié)構(gòu)的有序表中

23、進(jìn)行；查找過程：1） 如中間項(xiàng)的值等于x，就說明已查到；2） 如 x 小于中間項(xiàng)的值，就在線性表的前半部分查找；3） 如 x 大于中間項(xiàng)的值，就在線性表的后半部分查找；特點(diǎn)：比次序查找方法效率高；最壞的情形下，需要比較log2n 次；* ：二分法查找只適用于次序儲(chǔ)備的線性表，且表中元素必需按關(guān)鍵字有序（升序，但答應(yīng)相鄰元素值相等） 排列； 對(duì)于無序線性表和線性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)只能用次序查找；在長度為 n 的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為o（ log2n ）；1.8 排序技術(shù)排序是指將一個(gè)無序序列整理成按值非遞減次序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作；1

24、、交換類排序法（方法：冒泡排序，快速排序）；2、插入類排序法（方法：簡潔插入排序，希爾排序）；3、挑選類排序法（方法：簡潔挑選排序，堆排序）；總結(jié)： 各種排序法比較：本章應(yīng)考點(diǎn)撥： 本章內(nèi)容在筆試中會(huì)顯現(xiàn)5-6 個(gè)題目， 是公共基礎(chǔ)學(xué)問部分出題量比較多的一章，所占分值也比較大，約10 分；其次章程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)： “清楚第一，效率其次” ；主要應(yīng)留意和考慮下述一些因素：（ 1）源程序文檔化；1）符號(hào)名的命名；符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有肯定的實(shí)際含義；2） 程序的注釋；分為序言性注釋和功能性注釋；序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能

25、說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計(jì)者、復(fù)審者、復(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）在一行內(nèi)只寫一條語句；2）程序編寫應(yīng)優(yōu)先考慮清楚性；3）程序編寫要做到清楚第一，效率其次；4）在保證程序正確的基礎(chǔ)上再要求提高效率；5）防止使用暫時(shí)變量而使程序的可讀性下降；6）防止不必要的轉(zhuǎn)移；7）盡量使用庫函數(shù)； 8）防止采納復(fù)雜的條件語句；9）盡

26、量削減使用“否定”條件語句；10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡 化； 11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱藏，確保每一個(gè)模塊的獨(dú)立 性； 13）從數(shù)據(jù)動(dòng)身去構(gòu)造程序；14）不要修補(bǔ)不好的程序，要重新編寫；（ 4）輸入和輸出； 1）對(duì)輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性；2）檢查輸入項(xiàng)的各種重要組合的合 法性； 3）輸入格式要簡潔，使得輸入的步驟和操作盡可能簡潔；4）輸入數(shù)據(jù)時(shí)，應(yīng)答應(yīng)使用自由格式； 5）應(yīng)答應(yīng)缺省值；6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入終止標(biāo)志；7）在以交互式輸入 / 輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的懇求，同時(shí)在數(shù)據(jù)輸入過程中和輸入終止時(shí)，應(yīng)在屏幕上給出狀

27、態(tài)信息；8）當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)， 應(yīng)保持輸入格式與輸入語句的一樣性；給全部的輸出加注釋， 并設(shè)計(jì)輸出報(bào)表格式；2.2 結(jié)構(gòu)化程序設(shè)計(jì)（面對(duì)過程的程序設(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）逐步求精；對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化；（ 3）模塊化；一個(gè)復(fù)雜問題，確定是由如干稍簡潔的問題構(gòu)成；模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)

28、，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊；（ 4）限制使用 goto 語句；2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：次序結(jié)構(gòu)，挑選結(jié)構(gòu)，重復(fù)結(jié)構(gòu)；1） 次序結(jié)構(gòu)；一種簡潔的程序設(shè)計(jì)，即依據(jù)程序語句行的自然次序，一條語句一條語句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)； 2）挑選結(jié)構(gòu)；又稱分支結(jié)構(gòu)，包括簡潔挑選和多分支挑選結(jié)構(gòu)，可依據(jù)條件，判定應(yīng)當(dā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 面對(duì)對(duì)象的

29、程序設(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面對(duì)對(duì)象方法的本質(zhì)就是主見從客觀世 界固有的事物動(dòng)身來構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來熟悉、懂得和描述客觀事物， 強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域；也就是說， 系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能夠照實(shí)地反映問題域中固有的事物及其關(guān)系；面對(duì)對(duì)象方法的主要優(yōu)點(diǎn)： （ 1）與人類習(xí)慣的思維方法一樣； （ 2）穩(wěn)固性好；（3）可重用性好；（ 4）易于開發(fā)大型軟件產(chǎn)品； （ 5）可愛護(hù)性好；* ：面對(duì)對(duì)象的程序設(shè)計(jì)主要考慮的是提高軟件的可重用性；對(duì)象是面對(duì)對(duì)象方法中最基本的概念，可以用來表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象； 面對(duì)對(duì)象的程

30、序設(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特點(diǎn)的屬性和它可執(zhí)行的一組操作組成；* ：對(duì)象是屬性和方法的封裝體；屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來轉(zhuǎn)變；操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)；* ：操作是對(duì)象的動(dòng)態(tài)屬性；* ：一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成；對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性好；（ 1）標(biāo)識(shí)惟一性；指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分；（ 2）分類性；指可以將具有相同屬性的操作的對(duì)象抽象成類；（ 3）多態(tài)性；指同一個(gè)

31、操作可以是不同對(duì)象的行為；（ 4）封裝性；從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范疇和可以對(duì)該數(shù)據(jù)施加的操作， 根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法； 對(duì)象的內(nèi)部， 即處理才能的實(shí)行和內(nèi)部狀態(tài)， 對(duì)外是不行見的； 從外面不能直接使用對(duì)象的處理才能， 也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身轉(zhuǎn)變；* ：信息隱藏是通過對(duì)象的封裝性來實(shí)現(xiàn)的；（ 5）模塊獨(dú)立性好；對(duì)象是面對(duì)對(duì)象的軟件的基本模塊，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對(duì)象是以數(shù)據(jù)為中心的，操作環(huán)繞對(duì)其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作；從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合

32、得很緊密，內(nèi)聚性強(qiáng)；類是指具有共同屬性、共同方法的對(duì)象的集合；所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例；消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息；消息的組成包括：（ 1）接收消息的對(duì)象的名稱；（ 2）消息標(biāo)識(shí)符，也稱消息名；（ 3）零個(gè)或多個(gè)參數(shù)；* ：在面對(duì)對(duì)象方法中，一個(gè)對(duì)象懇求另一個(gè)對(duì)象為其服務(wù)的方式是通過發(fā)送消息；繼承是指能夠直接獲得已有的性質(zhì)和特點(diǎn)，而不必重復(fù)定義他們；繼承分單繼承和多重繼承；單繼承指一個(gè)類只答應(yīng)有一個(gè)父類，多重繼承指一個(gè)類答應(yīng)有多個(gè)父類；* ：類的繼承性是類之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性；多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)

33、的現(xiàn)象；本章應(yīng)考點(diǎn)撥： 本章在考試中會(huì)顯現(xiàn)約1 個(gè)題目， 所占分值大約占 2 分， 是出題量較小的一章；本章內(nèi)容比較少，也很簡潔，把握住基本的概念就可以輕松應(yīng)對(duì)考試了，所以在這部分丟分，比較惋惜；第三章軟件工程基礎(chǔ)3.1 軟件工程基本概念1、軟件的相關(guān)概念運(yùn)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合；軟件的特點(diǎn)包括： 1）軟件是一種規(guī)律實(shí)體，而不是物理實(shí)體，具有抽象性；2）軟件的生產(chǎn) 與硬件不同， 它沒有明顯的制作過程； 3）軟件在運(yùn)行、 使用期間不存在磨損、 老化問題； 4） 軟件的開發(fā)、 運(yùn)行對(duì)運(yùn)算機(jī)系統(tǒng)具有依靠性，受運(yùn)算機(jī)系統(tǒng)的限制， 這導(dǎo)致了軟件移植的問題； 5）軟件復(fù)雜性高，成本昂

34、貴；6）軟件開發(fā)涉及諸多的社會(huì)因素；2、軟件危機(jī)與軟件工程軟件工程概念的顯現(xiàn)源自軟件危機(jī)；所謂軟件危機(jī)是泛指在運(yùn)算機(jī)軟件的開發(fā)和愛護(hù)過程中所遇到的一系列嚴(yán)峻問題；具體的說，在軟件開發(fā)和愛護(hù)過程中，軟件危機(jī)主要表現(xiàn)在： 1）軟件需求的增長得不到滿意；用戶對(duì)系統(tǒng)不中意的情形常常發(fā)生；2） 軟件開發(fā)成本和進(jìn)度無法掌握；開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)定日期的情形常常發(fā)生；3） 軟件質(zhì)量難以保證；4） 軟件不行愛護(hù)或愛護(hù)程度特別低；5） 軟件的成本不斷提高；6） 軟件開發(fā)生產(chǎn)率的提高跟不上硬件的進(jìn)展和應(yīng)用需求的增長；總之，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題；軟件工程是應(yīng)用于運(yùn)算機(jī)軟件

35、的定義、開發(fā)和愛護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序；軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：1） 軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境；2） 軟件工程治理，主要有軟件治理、軟件工程經(jīng)濟(jì)學(xué)；軟件工程的主要思想是將工程化原就運(yùn)用到軟件開發(fā)過程，它包括 3 個(gè)要素： 方法、 工具和過程；方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、治理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的掌握、治理；軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)；3、軟件生命周期軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用愛護(hù)到停止使用退役的過程；軟

36、件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行愛護(hù)三個(gè)階段： 1）軟件定義階段：包括制定方案和需求分析；制定方案：確定總目標(biāo)；可行性爭論；探討解決方案；制定開發(fā)方案；需求分析：對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出具體的定義； 2）軟件開發(fā)階段：軟件設(shè)計(jì)：分為概要設(shè)計(jì)和具體設(shè)計(jì)兩個(gè)部分；軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成運(yù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)度的前提下，

37、開發(fā)出具有有效性、牢靠性、可懂得性、可愛護(hù)性、 可重用性、 可適應(yīng)性、 可移植性、 可追蹤性和可互操作性且滿意用戶需求的產(chǎn)品；（ 2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的愛護(hù)費(fèi)用；能按時(shí)完成開發(fā)，準(zhǔn)時(shí)交付使用；（ 3）軟件工程原就：抽象、信息隱藏、模塊化、局部化、確定性、一樣性、完備性和可驗(yàn)證性；1 抽象：抽象是事物最基本的特性和行為，忽視非本質(zhì)細(xì)節(jié)，采納分層次抽象，自頂向下， 逐層細(xì)化的方法掌握軟件開發(fā)過程的復(fù)雜性； 2）信息隱藏：采納封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱藏起來，使模塊接口盡量簡潔； 3）模塊化

38、：模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義；模塊的大小要適中，模塊過大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的懂得和修改，也不利于模塊的調(diào)試和重用； 模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過于復(fù)雜，不利于掌握系統(tǒng)的復(fù)雜性；4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性；5） 確定性：軟件開發(fā)過程中全部概念的表達(dá)應(yīng)是確定、無歧義且規(guī)范的；6） 一樣性：程序內(nèi)外部接口應(yīng)保持一樣，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一樣；7） 完備性：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能；8） 可驗(yàn)證性：應(yīng)遵循簡潔檢查、測評(píng)、評(píng)審的原就，以確保系統(tǒng)的正確性；5、軟件開發(fā)工具與軟件

39、開發(fā)環(huán)境1 軟件開發(fā)工具軟件開發(fā)工具的完善和進(jìn)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量；軟件開發(fā)工具的進(jìn)展是從單項(xiàng)工具的開發(fā)逐步向集成工具進(jìn)展的，軟件開發(fā)工具為軟件工程方法供應(yīng)了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境；同時(shí)， 軟件開發(fā)方法的有效應(yīng)用也必需得到相應(yīng)工具的支持，否就方法將難以有效的實(shí)施；（ 2）軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合；運(yùn)算機(jī)幫助軟件工程（case， computer aided software engineering）將各種軟件工具、開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境； 它將

40、極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量；3.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論；1、需求分析需求分析方法有： 1）結(jié)構(gòu)化需求分析方法；2）面對(duì)對(duì)象的分析方法；* ：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的規(guī)律模型，解決“做什么 ”的問題；* ：需求分析一般分為需求獵取、需求分析、 編寫需求規(guī)格說明書和需求評(píng)審四個(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)的規(guī)律模型；結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（ dfd

41、）；2）數(shù)據(jù)字典（ dd）；3）判定樹； 4）判定表；數(shù)據(jù)流圖以圖形的方式描畫數(shù)據(jù)在系統(tǒng)中流淌和處理的過程，它反映了系統(tǒng)必需完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)規(guī)律模型的一種工具；下圖是數(shù)據(jù)流圖的基本圖形元素：加工數(shù)據(jù)流儲(chǔ)備文件源、潭加工（轉(zhuǎn)換） ：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出；數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名；儲(chǔ)備文件（數(shù)據(jù)源） ：表示處理過程中存放各種數(shù)據(jù)的文件；源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體；畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精；下圖是一個(gè)數(shù)據(jù)流圖的示例：數(shù)據(jù)字典：對(duì)全部與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精

42、確的、嚴(yán)格的定義， 使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、儲(chǔ)備成分和中間運(yùn)算結(jié)果有共同的懂得；* ：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中顯現(xiàn)的被命名的圖形元素的準(zhǔn)確說明；* ：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心；3、軟件需求規(guī)格說明書（srs）軟件需求規(guī)格說明書是需求分析階段的最終成果，通過建立完整的信息描述、具體的功能和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(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、軟件

43、設(shè)計(jì)的基礎(chǔ)* ：需求分析主要解決“做什么”的問題，而軟件設(shè)計(jì)主要解決“怎么做”的問題；從技術(shù)觀點(diǎn)來看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)；結(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)換成軟件的過程性描述；從工程角度來看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和具體設(shè)計(jì)；概要設(shè)計(jì)：又稱結(jié)構(gòu)設(shè)計(jì)，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式；具體設(shè)計(jì)：確定每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的

44、細(xì)節(jié)；軟件設(shè)計(jì)的基本原理包括：抽象、模塊化、信息隱藏和模塊獨(dú)立性；1） 抽象；抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他細(xì)節(jié)；2） 模塊化；解決一個(gè)復(fù)雜問題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對(duì)獨(dú)立但又不相互關(guān)聯(lián)的模塊的過程； 3）信息隱藏；每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他模塊來說是隱藏的；4）模塊獨(dú)立性；軟件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其他的模塊的接口是簡潔的；* ：模塊分解的主要指導(dǎo)思想是信息隱藏和模塊獨(dú)立性；模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個(gè)定性指標(biāo)；在結(jié)構(gòu)化程序設(shè)計(jì)中， 模塊劃分的原就是：模塊內(nèi)具有高內(nèi)聚度，模塊間具

45、有低耦合度；內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量；* ：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、規(guī)律內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、次序內(nèi)聚及功能內(nèi)聚；耦合性：是模塊間相互連接的緊密程度的度量；* ：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、掌握耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合；一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特點(diǎn)；2、總體設(shè)計(jì)（概要設(shè)計(jì)）和具體設(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è)計(jì)；3）編寫概要設(shè)計(jì)文檔； 4）概要設(shè)計(jì)文檔評(píng)審；常用的軟件

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

47、進(jìn)行和諧和治理的模塊；程序結(jié)構(gòu)圖的有關(guān)術(shù)語列舉如下： 深度：表示掌握的層數(shù)；上級(jí)模塊、從屬模塊：上、下兩層模塊a 和 b，且有 a 調(diào)用 b，就 a 是上級(jí)模塊， b 是從屬模塊；寬度：整體掌握跨度（最大模塊數(shù)的層）的表示；扇入：調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)；扇出：一個(gè)模塊直接調(diào)用的其他模塊數(shù)；原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊；下圖是一個(gè)程序結(jié)構(gòu)圖的示例：面對(duì)數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)；數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型；a、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)；變換型

48、系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成；b、事務(wù)型： 事務(wù)型數(shù)據(jù)處理問題的工作機(jī)理是接受一項(xiàng)事務(wù)，依據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)， 挑選分派一個(gè)適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果；（ 2）具體設(shè)計(jì)具體設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)；* ：具體設(shè)計(jì)的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程；常用的過程設(shè)計(jì)（即具體設(shè)計(jì)）工具有以下幾種：圖形工具：程序流程圖、n-s（方盒圖）、pad（問題分析圖）和hipo（層次圖 +輸入 / 處理/輸出圖）；表格工具：判定表；語言工具： pdl（偽碼）3.4 軟件測試1、軟件測試定義：使用

49、人工或自動(dòng)手段來運(yùn)行或測定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿意規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別；* ：軟件測試的目的：盡可能地多發(fā)覺程序中的錯(cuò)誤，不能也不行能證明程序沒有錯(cuò)誤；軟件測試的關(guān)鍵是設(shè)計(jì)測試用例，一個(gè)好的測試用例能找到迄今為止尚未發(fā)覺的錯(cuò)誤；2、軟件測試方法：靜態(tài)測試和動(dòng)態(tài)測試；靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量；不實(shí)際運(yùn)行軟件，主要通過人工進(jìn)行；動(dòng)態(tài)測試：是基于運(yùn)算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法；（ 1）白盒測試白盒測試方法也稱為結(jié)構(gòu)測試或規(guī)律驅(qū)動(dòng)測試；它是依據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求；

50、白盒測試的基本原就： 保證所測模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測模塊全部判定的每一分支至少執(zhí)行一次； 保證所測模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗(yàn)證全部內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性；* ：白盒測試法的測試用例是依據(jù)程序的內(nèi)部規(guī)律來設(shè)計(jì)的，主要用軟件的單元測試，主要方法有規(guī)律掩蓋、基本路徑測試等；a、規(guī)律掩蓋；規(guī)律掩蓋泛指一系列以程序內(nèi)部的規(guī)律結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計(jì)技術(shù)；通常程序中的規(guī)律表示有判定、分支、條件等幾種表示方法；語句掩蓋：挑選足夠的測試用例，使得程序中每一個(gè)語句至少都能被執(zhí)行一次；路徑掩蓋：執(zhí)行足夠的測試用例，使程序中全部的可能的路徑都至少經(jīng)受一次；判定掩蓋： 使設(shè)

51、計(jì)的測試用例保證程序中每個(gè)判定的每個(gè)取值分支（ t 或 f）至少經(jīng)受一次；條件掩蓋：設(shè)計(jì)的測試用例保證程序中每個(gè)判定的每個(gè)條件的可能取值至少執(zhí)行一次；判定 - 條件掩蓋：設(shè)計(jì)足夠的測試用例，使判定中每個(gè)條件的全部可能取值至少執(zhí)行一次， 同時(shí)每個(gè)判定的全部可能取值分支至少執(zhí)行一次；* ：規(guī)律掩蓋的強(qiáng)度依次是：語句掩蓋<路徑掩蓋 <判定掩蓋 <條件掩蓋 <判定 - 條件掩蓋；b、基本路徑測試；其思想和步驟是，依據(jù)軟件過程性描述中的掌握流程確定程序的環(huán)路復(fù)雜性度量， 用此度量定義基本路徑集合，并由此導(dǎo)出一組測試用例，對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測試；（ 2）黑盒測試黑盒測試方法也

52、稱為功能測試或數(shù)據(jù)驅(qū)動(dòng)測試；黑盒測試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿意需求進(jìn)行測試和驗(yàn)證；黑盒測試主要診斷功能不對(duì)或遺漏、接口錯(cuò)誤、 數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫拜訪錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤；黑盒測試不關(guān)懷程序內(nèi)部的規(guī)律，只是依據(jù)程序的功能說明來設(shè)計(jì)測試用例，主要方法有等價(jià)類劃分法、邊界值分析法、錯(cuò)誤估計(jì)法等，主要用軟件的確認(rèn)測試；a、等價(jià)類劃分法；這是一種典型的黑盒測試方法，它是將程序的全部可能的輸入數(shù)據(jù)劃分成如干部分（及如干等價(jià)類） ，然后從每個(gè)等價(jià)類中選取數(shù)據(jù)作為測試用例；b、邊界值分析法；它是對(duì)各種輸入、輸出范疇的邊界情形設(shè)計(jì)測試用例的方法；c、錯(cuò)誤估計(jì)法；人們可以靠體會(huì)和直覺估計(jì)程序

53、中可能存在的各種錯(cuò)誤，從而有針對(duì)性地編寫檢查這些錯(cuò)誤的用例；3、軟件測試過程一般按4 個(gè)步驟進(jìn)行：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試；（ 1）單元測試單元測試是對(duì)軟件設(shè)計(jì)的最小單位模塊（程序單元）進(jìn)行正確性檢測的測試，目的是發(fā)覺各模塊內(nèi)部可能存在的各種錯(cuò)誤；單元測試依據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計(jì)測試用例，其依據(jù)是具體設(shè)計(jì)說明書和源程序；單元測試的技術(shù)可以采納靜態(tài)分析和動(dòng)態(tài)測試；對(duì)動(dòng)態(tài)測試通常以白盒測試為主，輔之以黑盒測試；單元測試的內(nèi)容包括：模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、錯(cuò)誤處理測試和邊界測試；* ：在進(jìn)行單元測試時(shí)，要用一些幫助模塊去模擬與被測模塊相聯(lián)系的其他模塊，即為被測模塊設(shè)計(jì)和搭建驅(qū)動(dòng)模塊和樁模塊；其中，驅(qū)動(dòng)模塊相當(dāng)于被測模塊的主程序，它接收測試數(shù)據(jù)，并傳給被測模塊，輸出實(shí)際測試結(jié)果；而樁模塊是模擬其他被調(diào)用模塊，不必將子模塊的全部功能帶入；（ 2）集成測試集成測試是測試和組裝軟件的過程，它是把模塊在依據(jù)設(shè)計(jì)要求組裝起來的同時(shí)進(jìn)行測試， 主要目的是發(fā)覺與接口有關(guān)的錯(cuò)誤；集成測試的依據(jù)是概要設(shè)計(jì)說明書；集