全國(guó)計(jì)算機(jī)二級(jí)基礎(chǔ)知識(shí)輔導(dǎo)

全國(guó)計(jì)算機(jī)等級(jí)考試一一二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)考試大綱：一、基本數(shù)據(jù)結(jié)構(gòu)與算法.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性與非線性結(jié)構(gòu)的概念。.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。.樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。.順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序）。二、程序設(shè)計(jì)基礎(chǔ).程序設(shè)計(jì)方法與風(fēng)格。.結(jié)構(gòu)化程序設(shè)計(jì)。.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ).軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。.軟件測(cè)試的方法，白盒與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試實(shí)施，單元測(cè)試、集成和系統(tǒng)測(cè)試。.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ).數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?？荚嚪绞剑汗不A(chǔ)知識(shí)有10道選擇題和5道填空題共三十分。第一章數(shù)據(jù)結(jié)構(gòu)與算法算法1、遨是指解題方案的準(zhǔn)確而完整的描述。換句話說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述。*:算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)（這是因?yàn)椋涸诰帉?xiě)程序時(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無(wú)關(guān)的細(xì)節(jié)問(wèn)題。）。2、算法的基本特征（1）可行性。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無(wú)二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。（4）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）算法遜復(fù)幽是指執(zhí)行算法所需要的讓皿踵，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度鼠。（2）算法|空間復(fù)雜闔是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)的基本概念1、|數(shù)據(jù)結(jié)構(gòu)|是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題：（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)系（即直接前驅(qū)與直接后繼關(guān)系）。（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。2）鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(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)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4,數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）|線性結(jié)構(gòu)|（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)（在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。）;2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。*：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）排線性結(jié)構(gòu)卜不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。*：常見(jiàn)的非線性結(jié)構(gòu)有樹(shù)、二叉樹(shù)和圖等。3線性表及其順序存儲(chǔ)結(jié)構(gòu)1、|線性表曲一組數(shù)據(jù)元素構(gòu)成,數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n（n2O）個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第?個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元索的個(gè)數(shù)稱為線性表的長(zhǎng)度。線性表可以為空表。：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順序和鏈?zhǔn)健?、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。3、順序表的插入、刪除運(yùn)算（1）順序表的插入運(yùn)算：在一般情況下，要在第i 個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開(kāi)始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增加r1。：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。（2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（IWiWn）個(gè)元素時(shí)，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長(zhǎng)度就減小了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)算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出"或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線性表類(lèi)似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊(duì)列及其基本運(yùn)算畫(huà)是指允許在一端（隊(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è)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。*：循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front。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ò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所示：數(shù)據(jù)域指針域data next HEAD-―Oi— —|-*|a：—― *|儂 |―a>（a）結(jié)點(diǎn)結(jié)構(gòu) （b）一個(gè)非空的線性鏈表示意圖線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類(lèi)型。在單鏈表中，每一個(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ù)域右指針HEAD―aai, ?ai-? ???―?a.1a（a）結(jié)點(diǎn)結(jié)構(gòu) （b）一個(gè)非空的雙向鏈表示意圖3、線性鏈表的基本運(yùn)算（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。

:在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢”現(xiàn)象（當(dāng)為一個(gè)線性表分配順序存儲(chǔ)結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)，就會(huì)發(fā)生“上溢”現(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ī)存取（在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i,也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)。）。4、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(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ù)需耍來(lái)設(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)鏈表：head—?⑹至表head—?⑹至表循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面：?是在循環(huán)鏈表中，只要指出表中任何?個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(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)出發(fā)來(lái)訪問(wèn)表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。1.6樹(shù)與二叉樹(shù)1、樹(shù)的基本概念網(wǎng)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)”二所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為|父結(jié)點(diǎn)沒(méi)有前件的結(jié)點(diǎn)只有一個(gè),稱為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的序鬲司。沒(méi)有后件的結(jié)點(diǎn)稱為阡錦畫(huà)。（就是度為0的結(jié)點(diǎn)就是沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn)）在樹(shù)結(jié)構(gòu)中，二個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該阿詞跡所有結(jié)點(diǎn)中最大的度稱為|樹(shù)的度樹(shù)的最大層次稱為|樹(shù)的深度2、二叉樹(shù)及其基本性質(zhì)（1）什么是二叉樹(shù)二叉樹(shù)|是一種很有用的非線性結(jié)構(gòu),它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。：根據(jù)二叉樹(shù)的概念可知，二叉樹(shù)的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹(shù)）或2（有2棵子樹(shù)）.（2）二叉樹(shù)的基本性質(zhì)性質(zhì)1在二叉樹(shù)的第k層上，最多有21（%21）個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹(shù)最多有個(gè)2"'-1個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹(shù)中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。[nO：度為0的節(jié)點(diǎn)數(shù),nl:度為1的結(jié)點(diǎn)n2：度為2的節(jié)點(diǎn)數(shù)。N是總結(jié)點(diǎn)!HlJ<：nO=n2+l;N=nO+nl+n2]性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2〃]+l，其中[log2"]表示取bg2〃的整數(shù)部分。（補(bǔ)充：log就是取對(duì)數(shù)。log2n就是以2為底n的對(duì)數(shù)，Iog525=2也就是以5為底，25的對(duì)數(shù)為2）3、滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。：根據(jù)完全二叉樹(shù)的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或建下圖a表示的是滿二叉樹(shù)，下圖b表示的是完全二叉樹(shù)：完全二叉樹(shù)還具有如下兩個(gè)特性：性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為[log2〃]+1。性質(zhì)6設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開(kāi)始,按層序（每一層從左到右）用自然數(shù)1,2,…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=l,2,…，n）的結(jié)點(diǎn)有以下結(jié)論：①若k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>l,則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT（k/2）。②若2k《n,則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k：否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）o③若2k+lWn,則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+l；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。4、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與線性鏈表類(lèi)似，用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹(shù)中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），因此，用于存儲(chǔ)二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域：另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。：一般二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō)，可以按層序進(jìn)行順序存儲(chǔ)（這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹(shù)不適用。）。5、二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。二叉樹(shù)的遍歷可以分為以下三種：（1）前序遍歷（DLR）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)：并且，在遍歷左右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。（2）中序遍歷（LDR）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。（3）后序遍歷（LRD）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。1.7查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒(méi)找到。）平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想：從表中的第一個(gè)元素開(kāi)始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符,查到所要找的元素為止。否則就是表中沒(méi)有要找的元素，查找不成功。在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較里次。順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為0（n）。（注：O（n）表示某函數(shù)值，為復(fù)雜度上界）下列兩種情況下只能采用順序查找：1）如果線性表是無(wú)序表（即表中的元素是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。2、二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。查找過(guò)程：1）若中間項(xiàng)（中間項(xiàng)mid=（nT）/2,mid的值四舍五入取整）的值等于x,則說(shuō)明已查到；2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。*：二分法查找只適用于順序存儲(chǔ)的線性表,且表中元素必須按關(guān)鍵字有序（升序）排列。對(duì)于無(wú)序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為0（log2n）o1.8排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列，即是將無(wú)序的記錄序列調(diào)整為有序記錄序列的一種操作。1、交換類(lèi)排序法（方法：冒泡排序，快速排序）。2、插入類(lèi)排序法（方法：簡(jiǎn)單插入排序，希爾排序）。3,選擇類(lèi)排序法（方法：簡(jiǎn)單選擇排序，堆排序）?？偨Y(jié)：各種排序法比較：類(lèi)別排序方法基本思想時(shí)間復(fù)雜度交換類(lèi)冒泡排序相鄰元素比較，不滿足條件時(shí)交換n(n-l)/2快速排序選擇基準(zhǔn)元素，通過(guò)交換，劃分成兩個(gè)子序列O(nlo&n)插入類(lèi)簡(jiǎn)單插入排序待排序的元素看成為1個(gè)有序表和一個(gè)無(wú)序表，將無(wú)序表中元素插入到有序表中n(n-l)/2希爾排序分割成若干個(gè)子序列分別進(jìn)行直接插入排序O(n1J)選擇類(lèi)簡(jiǎn)單選擇排序掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面n(n-l)/2堆排序選建堆，然后將堆頂元素與堆中最后一個(gè)元素交換，再調(diào)整為堆O(nlogjn)本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會(huì)出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分第二章程序設(shè)計(jì)基礎(chǔ)2.1程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二（“清晰第一，效率第二”是當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。）主要應(yīng)注重和考慮下述一些因素：（1）源程序文檔化。1）符號(hào)名的命名。符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。2）程序的注釋。分為序言性注釋和功能性注釋。序言性注釋：位于程序開(kāi)頭部分，包括程序標(biāo)題、程序功能說(shuō)明、主要算法、接口說(shuō)明、程序位置、開(kāi)發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、復(fù)審者、復(fù)審日期及修改日期等。功能性注釋：嵌在源程序體之中，用于描述其后的語(yǔ)句或程序的主要功能。3）視覺(jué)組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?。?）數(shù)據(jù)說(shuō)明。1）數(shù)據(jù)說(shuō)明的次序規(guī)范化；2）說(shuō)明語(yǔ)句中變量安排有序化；3）使用注釋來(lái)說(shuō)明友雜數(shù)據(jù)的結(jié)構(gòu)。（3）語(yǔ)句的結(jié)構(gòu)。1）在一行內(nèi)只寫(xiě)一條語(yǔ)句；2）程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性；3）程序編寫(xiě)要做到清晰第一，效率第二；4）在保證程序正確的基礎(chǔ)上再要求提高效率；5）避免使用臨時(shí)變量而使程序的可讀性下降；6）避免不必要的轉(zhuǎn)移；7）盡量使用庫(kù)函數(shù)；8）避免采用復(fù)雜的條件語(yǔ)句；9）盡量減少使用“否定”條件語(yǔ)句：10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化：11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性；13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；14）不要修補(bǔ)不好的程序，要重新編寫(xiě)。（4）輸入和輸出。1）對(duì)輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性；2）檢行輸入項(xiàng)的各種重要組合的合法性；3）輸入格式要簡(jiǎn)單，使得輸入的步驟和操作盡可能簡(jiǎn)單；4）輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式；5）應(yīng)允許缺省值；6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志；7）在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過(guò)程中和輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息；8）當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性;給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。2.2結(jié)構(gòu)化程序設(shè)計(jì)（面向過(guò)程的程序設(shè)計(jì)方法）1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下,逐步求精,模塊化,限制使用got。語(yǔ)句。（1）自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。（2）逐步求精。對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)化。（3）模塊化。一個(gè)復(fù)雜問(wèn)題，肯定是由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。（4）限制使用goto語(yǔ)句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu),選擇結(jié)構(gòu),重復(fù)結(jié)構(gòu)。1）順序結(jié)構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì)，即按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序,它是最基本、最常用的結(jié)構(gòu)。2）選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列.3）重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu),可根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類(lèi)似的程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何單人口/單出口的程序。2.3面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)牛.活中常用的思維來(lái)認(rèn)識(shí)、理解和描述客觀事物,強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn)題域。也就是說(shuō)，系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)地反映問(wèn)題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類(lèi)習(xí)慣的思維方法一致;（2）穩(wěn)定性好;（3）可市用性好;（軟件的重用是指在不同的軟件開(kāi)發(fā)過(guò)程中重復(fù)使用相同或相似軟件的過(guò)程。）（4）易于開(kāi)發(fā)大型軟件產(chǎn)品；（5）可維護(hù)性好。：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。幽是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿梢杂脕?lái)表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由?組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對(duì)象是屬性和方法的封裝體。而用即對(duì)象所包含的信息,它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過(guò)執(zhí)行對(duì)象的操作來(lái)改變。睡描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是對(duì)象的動(dòng)態(tài)屬性。：一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成。對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟?性,分類(lèi)性,多態(tài)性,封裝性,模塊獨(dú)立性好。（1）標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來(lái)區(qū)分，而不是通過(guò)描述來(lái)區(qū)分。（2）分類(lèi)性。指可以將具有相同屬性的操作的對(duì)象抽象成類(lèi)。（3）多態(tài)性。指同一個(gè)操作可以是不同對(duì)象的行為。（4）封裝性。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無(wú)需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對(duì)象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見(jiàn)的。從外面不能直接使用對(duì)■象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。：信息隱蔽是通過(guò)對(duì)象的封裝性來(lái)實(shí)現(xiàn)的。（5）模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)?體，而且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做的處理來(lái)設(shè)置，沒(méi)有無(wú)關(guān)的操作。從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。圖是指具有共同屬性、共同方法的對(duì)象的集合。所以類(lèi)是對(duì)■象的抽象，時(shí)象是對(duì)應(yīng)類(lèi)的個(gè)實(shí)例。睡是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括：（1）接收消息的對(duì)象的名稱；（2）消息標(biāo)識(shí)符，也稱消息名；（3）零個(gè)或多個(gè)參數(shù)。：在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送消息。邈是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多建繼承。單繼承指一個(gè)類(lèi)只允許有一個(gè)父類(lèi)，多重繼承指一個(gè)類(lèi)允許有多個(gè)父類(lèi)。:類(lèi)的繼承性是類(lèi)之間共享屬性和操作的機(jī)制，它提高了軟件的可堇用性。I多態(tài)性I是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。本章應(yīng)考點(diǎn)撥：本章在考試中會(huì)出現(xiàn)約1個(gè)題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡(jiǎn)單，掌握住基本的概念就可以輕松應(yīng)對(duì)考試了，所以在這部分丟分，比較可惜。第三章軟件工程基礎(chǔ)3.1軟件工程基本概念1、軟件的相關(guān)概念計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體,而不是物理實(shí)體，具有抽象性；2）軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程；3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題；4）軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。2、軟件危機(jī)與軟件工程軟件工程源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。具體的說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件危機(jī)主要表現(xiàn)在：1）軟件需求的增長(zhǎng)得不到滿足。用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生。2）軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。開(kāi)發(fā)成本超出預(yù)算，開(kāi)發(fā)周期大大超過(guò)規(guī)定日期的情況經(jīng)常發(fā)生。3）軟件質(zhì)量難以保證。4）軟件不可維護(hù)或維護(hù)程度非常低。5）軟件的成本不斷提高。6）軟件開(kāi)發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？傊?，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。軟件工程|是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：1）軟件開(kāi)發(fā)技術(shù),主要有軟件開(kāi)發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2）軟件工程管理,主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工程化原則運(yùn)用到軟件開(kāi)發(fā)過(guò)程,它包括3個(gè)要素：方法、工具和過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開(kāi)發(fā)、管理、文檔生成；過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理。軟件工程過(guò)程是把皿轉(zhuǎn)化為揄出的一組彼此相關(guān)的資源和活動(dòng)。3、軟件生命周期軟件生命周期|：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段:1）軟件定義階段：包括制定計(jì)劃和需求分析。制定計(jì)劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開(kāi)發(fā)計(jì)劃。需求分析：對(duì)待開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。2）軟件開(kāi)發(fā)階段：軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(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)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。(2)軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開(kāi)發(fā)的軟件易于移植：需要較低的維護(hù)費(fèi)用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用。(3)軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。1)幽：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性。|信息隱蔽|：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來(lái)，使模塊接口盡量簡(jiǎn)單。|模塊化|：模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。|局部化|：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性。|確定性|：軟件開(kāi)發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定、無(wú)歧義且規(guī)范的。|一致性|：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說(shuō)明與系統(tǒng)行為應(yīng)保持一致。|完備性|：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。8)阿驗(yàn)證性卜應(yīng)遵循容易檢查、測(cè)評(píng)、評(píng)審的原則，以確保系統(tǒng)的正確性。5、軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境(1)軟件開(kāi)發(fā)工具軟件開(kāi)發(fā)工具的完善和發(fā)展將促使軟件開(kāi)發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開(kāi)發(fā)的高速度和高質(zhì)量。軟件開(kāi)發(fā)工具的發(fā)展是從單項(xiàng)工具的開(kāi)發(fā)逐步向集成工具發(fā)展的，軟件開(kāi)發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境。同時(shí)，軟件開(kāi)發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難以有效的實(shí)施。(2)軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)環(huán)境(或稱軟件工程環(huán)境)是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。計(jì)算機(jī)輔助軟件工程(CASE,ComputerAidedSoftwareEngineering)將各種軟件工具、開(kāi)發(fā)機(jī)器和一個(gè)存放開(kāi)發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。它將極大降低軟件開(kāi)發(fā)的技術(shù)難度并保證軟件開(kāi)發(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)的邏輯模型,解決'‘做什么”的問(wèn)題。：需求分析一般分為需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)和需求評(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ù)流，向頂向F,逐層分解,建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹(shù);4）判定表。數(shù)據(jù)流圖|以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過(guò)程,它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。加工 數(shù)據(jù)流存儲(chǔ)文件源、潭加工 數(shù)據(jù)流存儲(chǔ)文件源、潭上圖是數(shù)據(jù)流圖的基本圖形元素：E|（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。|數(shù)據(jù)流|：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。I存儲(chǔ)文件I（數(shù)據(jù)源）：表示處理過(guò)程中存放各種數(shù)據(jù)的文件。I源，潭|：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。畫(huà)數(shù)據(jù)流圖的基本步驟：日外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。下圖是一個(gè)數(shù)據(jù)流圖的示例：帳卡帳卡數(shù)據(jù)字典|：對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、軟件需求規(guī)格說(shuō)明書(shū)（SRS）軟件需求規(guī)格瓦麗用是需求分析階段的最后成果，通過(guò)建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說(shuō)明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。3結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)的基礎(chǔ)：需求分析主要解決“做什么”的問(wèn)題，而軟件設(shè)計(jì)主要解決“怎么做”的問(wèn)題。從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(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)的定義。接U設(shè)計(jì)卜描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。

過(guò)程設(shè)計(jì)卜把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述。從工程角度來(lái)看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(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ù)庫(kù)模式。詳細(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ì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。2）模塊化。解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對(duì)獨(dú)立但又不相互關(guān)聯(lián)的模塊的過(guò)程。3）信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他模塊來(lái)說(shuō)是隱蔽的。4）模塊獨(dú)立性。軟件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其他的模塊的接口是簡(jiǎn)單的。：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個(gè)定性指標(biāo)。麗性:是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。麗|性:是模塊間互相連接的緊密程度的度量。：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦*~的特征。在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。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ù)庫(kù)設(shè)計(jì)；3）編寫(xiě)概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過(guò)程中來(lái)回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。一般模塊數(shù)據(jù)信息一般模塊數(shù)據(jù)信息控制信息經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類(lèi)型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖:J/A傳入■塊J/A傳入■塊IJ，A傳出模塊 T、(d)它們的含義分別是：傳入模塊I：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級(jí)模塊。傳出模塊卜從上級(jí)模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。變換模塊（從上級(jí)模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊。協(xié)調(diào)模塊|：對(duì)所有下屬模塊進(jìn)行協(xié)調(diào)和管理的模塊。程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語(yǔ)列舉如下：寬度 寬度 深度|：表示控制的層數(shù)。上級(jí)模塊、從屬模塊：上、下兩層模塊a和b,且有a調(diào)用b,則a是上級(jí)模塊，b是從屬模塊。邈：整體控制跨度（最大模塊數(shù)的層）的表示。網(wǎng)調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)。麗一個(gè)模塊直接調(diào)用的其他模塊數(shù)。原子模塊：樹(shù)中位于葉子結(jié)點(diǎn)的模塊。面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。數(shù)據(jù)流的類(lèi)型：大體可以分為兩種類(lèi)型，變換型和事務(wù)型。A、變換型：變換型數(shù)據(jù)處理問(wèn)題的工作過(guò)程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問(wèn)題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)，選擇分派一個(gè)適當(dāng)?shù)奶幚韱?元（單元是程序中最小的部分，由可以隱含的三部分組成：數(shù)據(jù)輸入、加工和數(shù)據(jù)輸出?）＞然后給lH結(jié)果。（2）詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。*:詳細(xì)設(shè)計(jì)的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。常用的過(guò)程設(shè)計(jì)（即詳細(xì)設(shè)計(jì)）工具有以下幾種：圖形工具：程序流程圖、N-S（方盒圖）、PAD（問(wèn)題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。表格工具：判定表。語(yǔ)言工具：PDL（偽碼）3.4軟件測(cè)試1、軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。：軟件測(cè)試的目的：盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤,不能也不可能證明程序沒(méi)有錯(cuò)誤。軟件測(cè)試的關(guān)鍵是設(shè)計(jì)測(cè)試用例（測(cè)試用例是指對(duì)一項(xiàng)特定的軟件產(chǎn)品進(jìn)行測(cè)試任務(wù)的描述,體現(xiàn)測(cè)試方案、方法、技術(shù)和策略。一個(gè)好的測(cè)試用例能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤。2、軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。|靜態(tài)測(cè)試|：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。|動(dòng)態(tài)測(cè)試|：是基于計(jì)算機(jī)的測(cè)試，主要包括匕I盒測(cè)試方法和黑盒測(cè)試方法。（1）白盒測(cè)試白盒測(cè)試方法也稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。白盒測(cè)試的基本原則：保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次；保證所測(cè)模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。：白盒測(cè)試法的測(cè)試用例是根據(jù)程序的內(nèi)部邏輯來(lái)設(shè)計(jì)的,主要用軟件的單元測(cè)試,主要方法有邏輯覆蓋、基本路徑測(cè)試等。A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例設(shè)計(jì)技術(shù)。通常程序中的邏輯表示有判斷、分支、條件等兒種表示方法。語(yǔ)句覆蓋：選擇足夠的測(cè)試用例，使得程序中每一個(gè)語(yǔ)句至少都能被執(zhí)行一次。路徑覆蓋：執(zhí)行足夠的測(cè)試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。判定覆蓋：使設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)取值分支（T或F）至少經(jīng)歷一次。條件覆蓋：設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)條件的可能取值至少執(zhí)行一次。判斷-條件覆蓋：設(shè)計(jì)足夠的測(cè)試用例，使判斷中每個(gè)條件的所有可能取值至少執(zhí)行一次，同時(shí)每個(gè)判斷的所有可能取值分支至少執(zhí)行一次。：邏輯覆蓋的強(qiáng)度依次是：語(yǔ)句覆蓋〈路徑覆蓋〈判定覆蓋〈條件覆蓋〈判斷-條件覆蓋。B、基本路徑測(cè)試。其思想和步驟是，根據(jù)軟件過(guò)程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量,用此度量定義基本路徑集合，并由此導(dǎo)出一組測(cè)試用例，對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測(cè)試。（2）黑盒測(cè)試黑盒測(cè)試方法也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試主要診斷功能不對(duì)或遺漏、接口錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪問(wèn)錯(cuò)誤、性能錯(cuò)誤、初始化

和終止條件錯(cuò)誤。黑盒測(cè)試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說(shuō)明來(lái)設(shè)計(jì)測(cè)試用例,主要方法有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法等,主要用軟件的確認(rèn)測(cè)試。B、|邊界值分析法C、|錯(cuò)誤推測(cè)法LB、|邊界值分析法C、|錯(cuò)誤推測(cè)法Lo它是對(duì)各種輸入、輸出范圍的邊界情況設(shè)計(jì)測(cè)試用例的方法。. .人們可以靠經(jīng)驗(yàn)和直覺(jué)推測(cè)程序中可能存在的各種錯(cuò)誤，從而有針對(duì)性地編寫(xiě)檢查這些錯(cuò)誤的用例。3、軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試。(1)單元測(cè)試|單元測(cè)試［是對(duì)軟件設(shè)計(jì)的最小單位——模塊(程序單元)進(jìn)行正確性檢測(cè)的測(cè)試，目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。單元測(cè)試根據(jù)程序的內(nèi)部結(jié)構(gòu)來(lái)設(shè)計(jì)測(cè)試用例,其依據(jù)是詳細(xì)設(shè)計(jì)說(shuō)明檸和源程序。單元測(cè)試的技術(shù)可以采用靜態(tài)分析和動(dòng)態(tài)測(cè)試。對(duì)動(dòng)態(tài)測(cè)試通常以白盒測(cè)試為主,輔之以黑盒測(cè)試。單元測(cè)試的內(nèi)容包括：模塊接U測(cè)試、局部數(shù)據(jù)結(jié)構(gòu)測(cè)試、錯(cuò)誤處現(xiàn)測(cè)試和邊界測(cè)試。*：在進(jìn)行單元測(cè)試時(shí)，要用一些輔助模塊去模擬與被測(cè)模塊相聯(lián)系的其他模塊，即為被測(cè)模塊設(shè)計(jì)和搭建驅(qū)動(dòng)模塊和樁模塊。其中，|驅(qū)動(dòng)模塊|相當(dāng)于被測(cè)模塊的主程序,它接收測(cè)試數(shù)據(jù)，并傳給被測(cè)模塊，輸出實(shí)際測(cè)試結(jié)果：而|樁模塊|是模擬其他被調(diào)用模塊,不必將子模塊的所有功能帶入。(2)集成測(cè)試集成測(cè)試|是測(cè)試和組裝軟件的過(guò)程,它是把模塊在按照設(shè)計(jì)要求組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。集成測(cè)試的依據(jù)是概要設(shè)計(jì)說(shuō)明書(shū)。集成測(cè)試所涉及的內(nèi)容包括：軟件單兀的接口測(cè)試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測(cè)試、邊界條件和非法輸入的測(cè)試等。集成測(cè)試通常采用兩種方式：非增量方式組裝與增量方式組裝。作增量方式組裝|：也稱為一次性組裝方式。首先對(duì)每個(gè)模塊分別進(jìn)行模塊測(cè)試，然后再把所有模塊組裝在?起進(jìn)行測(cè)試，最終得到要求的軟件系統(tǒng)。增量方式組裝|：又稱漸增式集成方式。首先對(duì)一個(gè)個(gè)模塊進(jìn)行模塊測(cè)試，然后將這些模塊逐步組裝成較大的系統(tǒng)，在組裝的過(guò)程中邊連接邊測(cè)試，以發(fā)現(xiàn)連接過(guò)程中產(chǎn)生的問(wèn)題。最后通過(guò)增殖逐步組裝成要求的軟件系統(tǒng)。增量方式組裝又包括自頂向下、自底向上、自頂向下與自底向上相結(jié)合等三種方式。(3)確認(rèn)測(cè)試確認(rèn)測(cè)試|的任務(wù)是驗(yàn)證軟件的有效性,即驗(yàn)證軟件的功能和性能及其他特性是否與用戶的要求一致。確認(rèn)測(cè)試的主要依據(jù)是軟件需求規(guī)格說(shuō)明書(shū)。確認(rèn)測(cè)試主要運(yùn)用黑盒測(cè)試法。(4)系統(tǒng)測(cè)試系統(tǒng)測(cè)試|的H的在于通過(guò)與系統(tǒng)的需求定義進(jìn)行比較,發(fā)現(xiàn)軟件與系統(tǒng)定義不符合或與之矛盾的地方。系統(tǒng)測(cè)試的測(cè)試用例應(yīng)根據(jù)需求分析規(guī)格說(shuō)明來(lái)設(shè)計(jì),并在實(shí)際使用環(huán)境下來(lái)運(yùn)行。系統(tǒng)測(cè)試的具體實(shí)施一般包括：功能測(cè)試、性能測(cè)試、操作測(cè)試、配置測(cè)試、外部接口測(cè)試、安全性測(cè)試等。3.5程序的調(diào)試程序調(diào)試（注意與軟件測(cè)試區(qū)分。）的任務(wù)是診斷和改正程序中的錯(cuò)誤,主要在開(kāi)發(fā)階段進(jìn)行，調(diào)試程序應(yīng)該由編制源程序的程序員來(lái)完成o程序調(diào)試的基本步驟：（1）錯(cuò)誤定位;（2）糾正錯(cuò)誤;（3）回歸測(cè)試。*：軟件的調(diào)試后要進(jìn)行回歸測(cè)試,防止引進(jìn)新的錯(cuò)誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。對(duì)軟件主要的調(diào)試方法可以采用：（1）強(qiáng)行排錯(cuò)法。主要方法有：通過(guò)內(nèi)存全部打印來(lái)排錯(cuò)；在程序特定部位設(shè)置打印語(yǔ)句；自動(dòng)調(diào)試工具。（2）回溯法。發(fā)現(xiàn)了錯(cuò)誤，分析錯(cuò)誤征兆，確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程序。（3）原因排除法。是通過(guò)演繹、歸納和二分法來(lái)實(shí)現(xiàn)的。1）演繹法。根據(jù)已有的測(cè)試用例，設(shè)想及枚舉出所有可能出錯(cuò)的原因作為假設(shè)；然后再用原始測(cè)試數(shù)據(jù)或新的測(cè)試，從中逐個(gè)排除不可能正確的假設(shè)；最后，再用測(cè)試數(shù)據(jù)驗(yàn)證余下的假設(shè)確定出錯(cuò)的原因。2）歸納法。從錯(cuò)誤征兆著手，通過(guò)分析它們之間的關(guān)系來(lái)找出錯(cuò)誤。大致分四步：收集有關(guān)的數(shù)據(jù)；組織數(shù)據(jù)；提出假設(shè)；證明假設(shè)。3）二分法。在程序的關(guān)鍵點(diǎn)給變量賦正確值，然后運(yùn)行程序并檢查程序的輸出。如果輸出結(jié)果正確，則錯(cuò)誤原因在程序的前半部分；反之，錯(cuò)誤原因在程序的后半部分。本章應(yīng)考點(diǎn)撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。從出題的深度來(lái)看，本章主要考察對(duì)基本概念的識(shí)記，有少量對(duì)基本原理的理解，沒(méi)有實(shí)際運(yùn)用，因此考生在愛(ài)習(xí)本章時(shí)，重點(diǎn)應(yīng)放在基本概念的記憶和基本原理的理解上。第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)管理系統(tǒng)（1）數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類(lèi)型，如整型、實(shí)型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。（2）|數(shù)據(jù)庫(kù)（db71：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)，亦即是數(shù)據(jù)庫(kù)集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一的構(gòu)造和存儲(chǔ)，而使它們可被不同應(yīng)用程序所使用。|數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）|：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：1）數(shù)據(jù)模式定義。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫(kù)構(gòu)建模式，也就是為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架。2）數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。3）數(shù)據(jù)操縱。數(shù)據(jù)庫(kù)管理系統(tǒng)為用戶使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)提供方便，它一般提供如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)的能力，而且還可以與某些過(guò)程性語(yǔ)言結(jié)合，使其具有強(qiáng)大的過(guò)程性操作能力。4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有內(nèi)在語(yǔ)義上的關(guān)聯(lián)性與一致性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫(kù)中數(shù)據(jù)正確的必要條件，因此必須經(jīng)常檢查以維護(hù)數(shù)據(jù)正確。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會(huì)引發(fā)數(shù)據(jù)的非法使用，因此必須要對(duì)數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時(shí)做檢查，這就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性3安全性的維護(hù)是數(shù)據(jù)庫(kù)系統(tǒng)的基本功能。5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫(kù)是一個(gè)集成、共享的數(shù)據(jù)集合體，它能為多個(gè)應(yīng)用程序服務(wù)，所以就存在著多個(gè)應(yīng)用程序?qū)?shù)據(jù)庫(kù)的并發(fā)操作。在并發(fā)操作中如果不加控制和管理，多個(gè)應(yīng)用程序間就會(huì)相互干擾，從而對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成破壞。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)必須對(duì)多個(gè)應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞，這就是數(shù)據(jù)庫(kù)的并發(fā)控制。數(shù)據(jù)庫(kù)中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫(kù)管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢愛(ài)，這就是數(shù)據(jù)庫(kù)的故障恢愛(ài)。6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫(kù)管理系統(tǒng)提供對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。|數(shù)據(jù)庫(kù)管理員（DBA）|：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專業(yè)管理人員。|數(shù)據(jù)庫(kù)系統(tǒng)⑴甌：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。*：數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展

數(shù)據(jù)庫(kù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。下表是數(shù)據(jù)管理三個(gè)階段的比較：人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)階段背!；■'應(yīng)用背景科學(xué)計(jì)算科學(xué)計(jì)算、管理大規(guī)模管理硬件背景無(wú)直接存取存儲(chǔ)設(shè)備磁盤(pán)、磁鼓大容量磁備盤(pán)軟件背景沒(méi)有操作系統(tǒng)有文件系統(tǒng)有數(shù)據(jù)庫(kù)管理系統(tǒng)處理方式批處理聯(lián)機(jī)實(shí)時(shí)處理、批處理聯(lián)機(jī)實(shí)時(shí)處理、分布處理、批處理特點(diǎn)數(shù)據(jù)的管理者用戶(程序員)文件系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)面向的對(duì)象某一應(yīng)用程序某一應(yīng)用現(xiàn)實(shí)世界數(shù)據(jù)的共享程度無(wú)共享，冗余度極大共享性差，冗余度大共享性高，冗余度小數(shù)據(jù)的獨(dú)立性不獨(dú)立，完全依賴于程序獨(dú)立性差具有高度的物理獨(dú)立性和一定的邏輯獨(dú)立性數(shù)據(jù)的結(jié)構(gòu)化無(wú)結(jié)構(gòu)記錄內(nèi)有結(jié)構(gòu)，整體無(wú)結(jié)構(gòu)整體結(jié)構(gòu)化，用數(shù)據(jù)模型描述數(shù)據(jù)控制能力應(yīng)用程序自己控制應(yīng)用程序自己控制由數(shù)據(jù)庫(kù)管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)能力3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)(1)數(shù)據(jù)的高集成性。(2)數(shù)據(jù)的高共享性叮低冗余性。*：數(shù)據(jù)庫(kù)系統(tǒng)可以減少數(shù)據(jù)冗余(在一個(gè)集合中的重復(fù)數(shù)據(jù)稱為數(shù)據(jù)冗余。)，但無(wú)法避免一切冗余。(3)數(shù)據(jù)獨(dú)立性:|數(shù)據(jù)獨(dú)立性|是數(shù)據(jù)與程序間的互不依賴性,即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說(shuō)，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性?般分為物理獨(dú)立性與邏輯獨(dú)立性兩級(jí)。|物理獨(dú)立樹(shù):物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)(包括存儲(chǔ)結(jié)構(gòu)，存取方式等)的改變，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化。|邏輯獨(dú)立性|：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類(lèi)型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。(4)數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個(gè)方面：1)數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫(kù)中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。2）數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫(kù)訪問(wèn)者以防止非法訪問(wèn)。3）并發(fā)控制：控制多個(gè)應(yīng)用的并發(fā)訪問(wèn)所產(chǎn)生的相互干擾以保證其正確性。4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系（1）數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：I概念模式|：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖（視圖是從一個(gè)或幾個(gè)基本表（或視圖）導(dǎo)出的表，它與基本表不同，是一個(gè)虛表。數(shù)據(jù)庫(kù)中只存放視圖的定義，而不存放視圖對(duì)應(yīng)的數(shù)據(jù)，這些數(shù)據(jù)仍然存放在原來(lái)的基本表中。）?|外模式b也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。|內(nèi)模式|：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級(jí)上，它還未深入到設(shè)備級(jí)上（如磁盤(pán)及磁盤(pán)操作）。內(nèi)模式對(duì)一般用戶是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。（2）數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：1）|概念模式/內(nèi)模式的映射|：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫(kù)的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨(dú)立性。2”外模式/概念模式的映射卜實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立:性。4.2數(shù)據(jù)模型1、數(shù)據(jù)模型（1）數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。（2）數(shù)據(jù)模型所描述的內(nèi)容有三個(gè)部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是所研究的對(duì)象類(lèi)型的集合，包括與數(shù)據(jù)類(lèi)型、內(nèi)容、性質(zhì)有關(guān)的對(duì)象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對(duì)象。它用于描述系統(tǒng)的靜態(tài)特性。2）數(shù)據(jù)操作：數(shù)據(jù)操作是對(duì)數(shù)據(jù)庫(kù)中各種對(duì)象（型）的實(shí)例（值）允許執(zhí)行的操作的集合，包括操作的含義、符號(hào)、操作規(guī)則及實(shí)現(xiàn)操作的語(yǔ)句等。它用于描述系統(tǒng)的動(dòng)態(tài)特性。3）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號(hào)數(shù)據(jù)模型的數(shù)據(jù)庫(kù)狀態(tài)及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。（3）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類(lèi)：1）概念數(shù)據(jù)模型：簡(jiǎn)稱概念模型，是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫(huà)。概念模型主要有：E-R模型（實(shí)體聯(lián)系模型）、擴(kuò)充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫(kù)系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫(kù)系統(tǒng)一級(jí)的實(shí)現(xiàn)。邏輯數(shù)據(jù)模型主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取?）物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。

2、實(shí)體聯(lián)系模型及E-R圖E-R模型的基本概念：1）實(shí)體：現(xiàn)實(shí)世界中的事物。2）屬性：事物的特性。3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。E-R模型三個(gè)基本概念之間的聯(lián)接關(guān)系：1）實(shí)體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）實(shí)體（集）與聯(lián)系。*：E-R模型的基本成分是實(shí)體和聯(lián)系。E-R模型的圖示法：1）實(shí)體集：用矩形表示。2）屬性：用橢圓形表示。3）聯(lián)系：用菱形表示。4）實(shí)體集與屬性間的聯(lián)接關(guān)系：用無(wú)向線段表示。5）實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系：用無(wú)向線段表示。（3）數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型二種。1）層次模型的基本結(jié)構(gòu)是施結(jié)構(gòu)，具有以下特點(diǎn)：A、每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱為根;B、樹(shù)中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。2）網(wǎng)狀模型是層次模型的一個(gè)特例，從圖論上看，網(wǎng)狀模型是?個(gè)不加任何條件限制的無(wú)向圖。學(xué)校學(xué)生學(xué)校學(xué)生（b）工作與設(shè)備（a）教學(xué)關(guān)系E-R（b）工作與設(shè)備3）關(guān)系模型采用二維表來(lái)表示,簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。二維表的表框架由n個(gè)命名的屬性組成，n稱為屬性元數(shù)。每個(gè)屬性有一個(gè)取值范圍稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類(lèi)型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組,實(shí)際上，一個(gè)元組是由n個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值。學(xué)號(hào)姓名性別出生年月班級(jí)籍貫2007102張潔然男07-07-8807動(dòng)畫(huà)1班天津2007203李一明男05-01-8707播音5班廣西南寧2007305王麗女04-09-8807管理4班遼寧沈陽(yáng)2007406劉宏男10-11-8807新聞3班江蘇南京*：同一個(gè)關(guān)系模型的任兩個(gè)元組值不能完全相同。主碼：或稱為關(guān)鍵字、主鍵，簡(jiǎn)稱碼、鍵，表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的，稱為關(guān)系的主碼或關(guān)鍵字。例如，學(xué)生的學(xué)號(hào)。主碼屬性不能取空值。外部關(guān)鍵字：或稱為外鍵,在一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組稱為該關(guān)系的外部關(guān)鍵字。外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?duì)應(yīng)的關(guān)鍵字值。例如，在學(xué)生表中含有的所屬班級(jí)名字，是班級(jí)表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。（4）關(guān)系中的數(shù)據(jù)約束：1）|實(shí)體完整性藥雨:要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯一決定元組的，如為空值則其唯一性就成為不可能的了。2）慘照完整性約束］:關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，即在關(guān)系中的外健要么是所關(guān)聯(lián)關(guān)系中實(shí)際存在的元組，要么為空值。|用戶定義的完整性約束卜反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語(yǔ)義要求。例如某個(gè)屬性的取值范圍在0—100之間等。3、從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)）中的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實(shí)體與聯(lián)系都可以以示成關(guān)系,E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。3關(guān)系代數(shù)1、關(guān)系的數(shù)據(jù)結(jié)構(gòu)關(guān)系是由若干個(gè)不同的元組所組成，因此關(guān)系可視為元組的集合。n元關(guān)系是一個(gè)n元有序組的集合。關(guān)系模型的基本運(yùn)算：1）插入；2）刪除；3）修改；4）查詢（包括投影、選擇、笛卡爾積運(yùn)算）。2、關(guān)系操縱關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四種操作。3、集合運(yùn)算及選擇、投影、連接運(yùn)算⑴并（U）：關(guān)系R和S具有相同的關(guān)系模式，R相S的并是由屬于R或?qū)儆冖挪ⅲ║）：RsRuSABC AB CABCal bl cl alb2 c2alblclal b2 c2 alb3 c2alb；c2Q b2 cl a2b2 clQb；cl(a)(b)alb：(c)c2R-SRosRXSABC AB C R.AR.BR.CS.ASBS.Cal bl cl alb2 c2 alblclab2c2a2b2 cl alblclab3c2alblcl包2b2cl(d) (e)alb2c2alb2c2alb2c2ab3c2alb2c2工2b2cl式b2clab2c2a2b2clab3c2立b2clb2cl(f)（2）差（一）：關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合。（3）交（C）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S的元組構(gòu)成的集合。（4）廣義笛卡爾積（X）：設(shè)關(guān)系R和S的屬性個(gè)數(shù)分別為n、m,則R和S的廣義笛卡爾枳是一個(gè)有（n+m）列的元組的集合。每個(gè)元組的前n列來(lái)自R的一個(gè)元組，后m列來(lái)自S的一個(gè)元組，記為RXS。*:根據(jù)笛卡爾枳的定義：有n元關(guān)系R及m元關(guān)系S,它們分別有p、q個(gè)元組，則關(guān)系R與S經(jīng)笛卡爾積記為RXS,該關(guān)系是?個(gè)n+m元關(guān)系,元組個(gè)數(shù)是pXq,由R與S的有序組組合而成。例：有兩個(gè)關(guān)系R和S,分別進(jìn)行并、差、交和廣義笛卡爾積運(yùn)算。（5）在關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)中（關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)（RDBMS）是引入基于關(guān)系型模型的一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）。這個(gè)系統(tǒng)必須滿足以下最小標(biāo)準(zhǔn)：（1）對(duì)用戶以關(guān)系顯示數(shù)據(jù)（以表格形式顯示）；（2）提供關(guān)系運(yùn)算以表格形式維護(hù)這些數(shù)據(jù)。*：VFP是一種關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)。），基本的關(guān)系運(yùn)算有選擇、投影與聯(lián)接三種操作：1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那些符合指定條件的記錄挑出來(lái)。2）投影：投影是從所有字段中選取一部分字段及其值進(jìn)行操作，它是一種縱向操作。3）聯(lián)接：聯(lián)接將兩個(gè)關(guān)系模式拼接成一個(gè)更寬的關(guān)系模式，生成的新關(guān)系中包含滿足聯(lián)接條件的元組。4.4數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟(1)數(shù)據(jù)庫(kù)設(shè)計(jì)階段包括：需求分析、概念分析、邏輯設(shè)計(jì)、物理設(shè)計(jì)。(2)數(shù)據(jù)庫(kù)設(shè)計(jì)的每個(gè)階段都有各自的任務(wù)：1)|需求分析階凰這是數(shù)據(jù)庫(kù)設(shè)計(jì)的第一個(gè)階段，任務(wù)主要是收集和分析數(shù)據(jù)，這一階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計(jì)概念結(jié)構(gòu)的基礎(chǔ)。|概念設(shè)計(jì)階閾:分析數(shù)據(jù)間內(nèi)在語(yǔ)義關(guān)聯(lián)，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)的抽象模型，即形成E-R圖。*：數(shù)據(jù)庫(kù)概念設(shè)計(jì)的過(guò)程包括選擇局部應(yīng)用、視圖設(shè)計(jì)和視圖集成。|邏輯設(shè)計(jì)階段|：將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。|物理設(shè)計(jì)階段|：對(duì)數(shù)據(jù)庫(kù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫(kù)訪問(wèn)速度及有效利用存儲(chǔ)空間。本章應(yīng)考點(diǎn)撥：本章在考試中一般出現(xiàn)24個(gè)小題。本章內(nèi)容概括性強(qiáng)，比較抽象，難于理解，因此建議考生在復(fù)習(xí)的時(shí)候，首先熟讀講義，其次對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的基本概念及原理等知識(shí)耍注意理解、加強(qiáng)記憶。計(jì)算機(jī)等級(jí)考試二級(jí)基礎(chǔ)部分歸納二.算法的4個(gè)特性是：確定性，可行性，有窮性，擁有足夠的情報(bào).一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。.算法設(shè)計(jì)的基本方法主耍有：列舉法，歸納法，遞推，遞歸和減半遞推技術(shù).常用的存儲(chǔ)結(jié)構(gòu)有：順序，鏈接，索引.堆排序：nlog2快速排序：n/2最壞.數(shù)據(jù)流程圖中：箭頭數(shù)據(jù)流程序流程圖中：箭頭事物流.數(shù)據(jù)庫(kù)系統(tǒng)在其內(nèi)部三級(jí)模式：概念模式，內(nèi)部模式，外部模式；.過(guò)程設(shè)計(jì)語(yǔ)言(PDL)是結(jié)構(gòu)化的英語(yǔ)和偽碼，是一種混合語(yǔ)言.用戶參與物理設(shè)計(jì)的內(nèi)容有索引設(shè)計(jì)，集簇設(shè)計(jì)和分區(qū)設(shè)計(jì)等三種.衡量模塊獨(dú)立程度的度量標(biāo)準(zhǔn)：耦合和內(nèi)聚.程序設(shè)計(jì)主要經(jīng)過(guò)了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì).數(shù)據(jù)庫(kù)設(shè)計(jì)包括：概念設(shè)計(jì)和邏輯設(shè)計(jì).數(shù)據(jù)庫(kù)的物理結(jié)構(gòu)主要指數(shù)據(jù)庫(kù)的存儲(chǔ)記錄格式，存儲(chǔ)記錄安排和存取方法.數(shù)據(jù)庫(kù)的建立包括數(shù)據(jù)模式的建立與數(shù)據(jù)加載.數(shù)據(jù)庫(kù)設(shè)計(jì)一般采用生命周期法.源程序文檔化時(shí)程序應(yīng)加注釋。注釋一般分為序言性注釋和功能性注釋.結(jié)構(gòu)化程序設(shè)計(jì)的主要特點(diǎn)是每個(gè)控制結(jié)構(gòu)只有一個(gè)入口和一個(gè)出口.結(jié)構(gòu)化程序設(shè)計(jì)的主要方法是自頂向下，逐步求精，模塊化，限制使用GOTO語(yǔ)句.在面向?qū)ο蟮姆椒ㄖ?，?lèi)的實(shí)例成為對(duì)象.在面向?qū)ο蟮姆椒ㄖ校苯臃从沉擞脩魧?duì)目標(biāo)系統(tǒng)的要求的模型是功能模型.對(duì)象有三種成分：標(biāo)識(shí)，屬性和方法.軟件工程研究的主要內(nèi)容：軟件開(kāi)發(fā)技術(shù)和軟件工程治理.軟件工程的三要素：方法，工具和過(guò)程.軟件是程序，數(shù)據(jù)和文檔的集合.軟件工程的原則包括：抽象，隱蔽，模塊化，局部化，確定性，一致性，完備性和可驗(yàn)證性.結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論.軟件需求分析階段的工作：需求獲取，需求分析，編寫(xiě)需求規(guī)格說(shuō)明書(shū)，需求評(píng)審.在結(jié)構(gòu)化分析方法中，用于描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件的文檔稱為數(shù)據(jù)字典.軟件需求規(guī)格說(shuō)明書(shū)是需求分析階段的最后成果.軟件設(shè)計(jì)的基本原則：抽象，模塊化，隱蔽，模塊獨(dú)立性.數(shù)據(jù)流程圖的類(lèi)型：變換型和事務(wù)型.好的軟件設(shè)計(jì)結(jié)構(gòu)通常頂層高扇出，中間扇出較少，底層高扇出.具體設(shè)計(jì)的方法主要是結(jié)構(gòu)化程序設(shè)計(jì).常用圖形描述工具有程序流程圖，盒圖盒問(wèn)題分析圖.具體設(shè)計(jì)的典型語(yǔ)言描述工具是PDL.結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是程序的易讀性.在軟件生命周期中，能準(zhǔn)確的確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是需求分析.關(guān)系表中每一個(gè)橫行稱為一個(gè)元組.對(duì)象是屬性和方法的封裝體，操作是對(duì)象的動(dòng)態(tài)性屬性.在數(shù)據(jù)治理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工治理階段，文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段,其中數(shù)據(jù)獨(dú)立性最高的是數(shù)據(jù)庫(kù)系統(tǒng).用樹(shù)形結(jié)構(gòu)來(lái)表示實(shí)體之間聯(lián)系的模型成為層次模型.關(guān)系數(shù)據(jù)庫(kù)治理系統(tǒng)能使現(xiàn)的專門(mén)關(guān)系運(yùn)算包括選擇，投影，連接.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示.檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱為確認(rèn)測(cè)試.需求分析常用工具DFD.索引屬于內(nèi)模式.在關(guān)系數(shù)據(jù)庫(kù)中，用來(lái)表示實(shí)體之間關(guān)系的是二維表.將E-R圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成關(guān)系.希爾排序法屬于插入類(lèi)排序法.診斷和改正程序中錯(cuò)誤的工作通常稱為程序調(diào)試.問(wèn)題處理方案的正確而完整的描述稱為算法.白盒測(cè)試一般適用于單元測(cè)試.數(shù)據(jù)就是描述事物的符號(hào)記錄.數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)由數(shù)據(jù)庫(kù)系統(tǒng)，應(yīng)用軟件和應(yīng)用界面組成.數(shù)據(jù)模型所描述的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)操作，數(shù)據(jù)約束。2010年3月全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)筆試試卷C語(yǔ)言程序設(shè)計(jì)（考試時(shí)間90分鐘，滿分100分）一、選擇題（（1）~（10）、（21）?（40）每題2分，（11）~（20）每題1分，共70分）下列各題A）、B）、C）、D）四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是正確的。請(qǐng)將正確選項(xiàng)填涂在答題卡相應(yīng)位置上，答在試卷上不得分。（1）下列敘述中正確的是A）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為（n/2）C）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為（logzn）D）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需耍的比較次數(shù)為（log2n）（2）算法的時(shí)間復(fù)雜度是指A）算法的執(zhí)行時(shí)間B）算法所處理的數(shù)據(jù)量O算法程序中的語(yǔ)句或指令條數(shù)D）算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)（3）軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于系統(tǒng)軟件的是A）編輯軟件B）操作系統(tǒng)O教務(wù)管理系統(tǒng)D）瀏覽器（4）軟件（程序）調(diào)試的任務(wù)是A）診斷和改正程序中的錯(cuò)誤B）盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤C）發(fā)現(xiàn)并改正程序中的所有錯(cuò)誤D）確定程序中錯(cuò)誤的性質(zhì)（5）數(shù)據(jù)流程圖（DFD圖）是A）軟件概要設(shè)計(jì)的工具B）軟件詳細(xì)設(shè)計(jì)的工具O結(jié)構(gòu)化方法的需求分析工具D）面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ撸?）軟件生命周期可分為定義階段，開(kāi)發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計(jì)屬于A）定義階段B）開(kāi)發(fā)階段C）維護(hù)階段C）上述三個(gè)階段（7）數(shù)據(jù)庫(kù)管理系統(tǒng)中負(fù)責(zé)數(shù)據(jù)模式定義的語(yǔ)言是A）數(shù)據(jù)定義語(yǔ)言B）數(shù)據(jù)管理語(yǔ)言C）數(shù)據(jù)操縱語(yǔ)言D）數(shù)據(jù)控制語(yǔ)言（8）在學(xué)生管理的關(guān)系數(shù)據(jù)庫(kù)中，存取一個(gè)學(xué)生信息的數(shù)據(jù)單位是A）文件B）數(shù)據(jù)庫(kù)C）字段D）記錄（9）數(shù)據(jù)庫(kù)設(shè)計(jì)中，用E-R圖來(lái)描述信息結(jié)構(gòu)但不涉及信息在計(jì)算機(jī)中的表示，它屬于數(shù)據(jù)庫(kù)設(shè)計(jì)的A）需求分析階段B）邏輯設(shè)計(jì)階段C）概念設(shè)計(jì)階段D）物理設(shè)計(jì)階段（10）有兩個(gè)關(guān)系R和T如下:R TABCa12b22ABCc32c32d32_d 32則由關(guān)系R得到關(guān)系T的操作是A)選擇B)投影C)交D)并(11)以下敘述正確的是A)C語(yǔ)言程序是由過(guò)程和函數(shù)組成的B)C語(yǔ)言函數(shù)可以嵌套調(diào)用，例如：fun(fun(x))C)C語(yǔ)言函數(shù)不可以單獨(dú)編譯D)C語(yǔ)言中除了main函數(shù)，其他函數(shù)不可作為單獨(dú)文件形式存在(12)以下關(guān)于C語(yǔ)言的敘述中正確的是A)C語(yǔ)言中的注釋不可以?shī)A在變量名或關(guān)鍵字的中間B)C語(yǔ)言中的變量可以在使用之前的任何位置進(jìn)行定義O在C語(yǔ)言算術(shù)表達(dá)式的書(shū)寫(xiě)中，運(yùn)算符兩側(cè)的運(yùn)算數(shù)類(lèi)型必須一致D)C語(yǔ)言的數(shù)值常量中夾帶空格不影響常量值的正確表示(13)以下C語(yǔ)言用戶標(biāo)識(shí)符中，不合法的是A) 1B)AaBcC)a bD)a b(14)若有定義：doubIea=22；inti=0,k=18；,則不符合C語(yǔ)言規(guī)定的賦值語(yǔ)句是A)a=a++,i++； B)i=(a+k)<=(i+k)；C)i=a%11； D)i=!a；(15)有以下程序#include<stdio.h>main(){chara,b,c,d;scanf( ，&a,&b);c=getchar();d二getchar;printf(u%c%c%c%c\nv,a,b,c,d);}當(dāng)執(zhí)行程序時(shí)，按下列方式輸入數(shù)據(jù)(從第1列開(kāi)始，VCR>代表回車(chē)，注意：回車(chē)也是一個(gè)字符)12<CR>34<CR>則輸出結(jié)果是A)1234B)12C)12D)123 34(16)以下關(guān)于C語(yǔ)言數(shù)據(jù)類(lèi)型使用的敘述中錯(cuò)誤的是A)若要準(zhǔn)確無(wú)誤差的表示自然數(shù)，應(yīng)使用整數(shù)類(lèi)型B)若要保存帶有多位小數(shù)的數(shù)據(jù)，應(yīng)使用雙精度類(lèi)型C)若要處理如“人員信息”等含有不同類(lèi)型的相關(guān)數(shù)據(jù)，應(yīng)自定義結(jié)構(gòu)體類(lèi)型D)若只處理“真”和“假”兩種邏輯值，應(yīng)使用邏輯類(lèi)型(17)若a是數(shù)值類(lèi)型，則邏輯表達(dá)式(a==I)||(a!=1)的值是A)1B)0C)2D)不知道a的值，不能確定(18)以下選項(xiàng)中與if(a==l)a=b；elsea++；語(yǔ)句功能不同的switch語(yǔ)句是A)switch(a