二級(jí)公共基礎(chǔ)知識(shí)(教師版)

全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)熱烈歡迎你們來(lái)共同學(xué)習(xí)，有問題隨時(shí)聯(lián)系！2011年3月二級(jí)公共基礎(chǔ)知識(shí)點(diǎn)分布

第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱

1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。一.算法的基本概念*1.所謂算法是指解題方案的準(zhǔn)確而完整的描述。嚴(yán)格來(lái)說，一個(gè)算法必須具有以下五個(gè)主要特征：有窮性確定性可行性輸入輸出輸出或輸出可說成：擁有足夠的情報(bào)2.算法的組成要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法的控制結(jié)構(gòu)一.算法的基本概念3.算法設(shè)計(jì)的要求通常設(shè)計(jì)一個(gè)“好”的算法，應(yīng)考慮達(dá)到以下目標(biāo)。正確性：算法應(yīng)當(dāng)滿足具體問題的需求?？勺x性：算法主要是為了人的閱讀與交流，其次才是機(jī)器執(zhí)行。可讀性好有助于人對(duì)算法的理解。健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果。效率與低存儲(chǔ)量需求。效率指的是算法執(zhí)行時(shí)間。對(duì)于同一個(gè)問題如果有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高。低存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。

一.算法的基本概念4.算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸減半遞推回溯法一.算法的基本概念*5.算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量算法優(yōu)劣的量度。（1）算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法的時(shí)間復(fù)雜度為算法中的基本操作重復(fù)執(zhí)行的次數(shù)。是問題規(guī)模n的某個(gè)函數(shù)f(n)。一.算法的基本概念何估算算法的時(shí)間復(fù)雜度？

任何一個(gè)算法都是由一個(gè)“控制結(jié)構(gòu)”和若干“原操作”組成的，因此一個(gè)算法的執(zhí)行時(shí)間可以看成是所有原操作的執(zhí)行時(shí)間之和

∑(原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間)

Fori=1to100forj=1to100s=i*j。算法時(shí)間復(fù)雜度為：O（n2)一.算法的基本概念A(yù)Q21（2）算法的空間復(fù)雜度算法的空間負(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?？臻g復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作：S(n)=O(g(n))，其中n為問題的規(guī)模，表示隨問題規(guī)模的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。一般不估計(jì)空間復(fù)雜度典型例題

1.一個(gè)算法是對(duì)某類給定的問題求解過程的精確描述，算法中的操作都可能通過將已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)，這句話說明算法具有什么特性？

A有窮性B可行性C確定性D健壯性2.算法的時(shí)間復(fù)雜度是指（）

A）執(zhí)行算法程序所需要的時(shí)間B）算法程序的長(zhǎng)度

C）算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D）算法程序中的指令條數(shù)3.下面敘述正確的是（）

A）算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B）算法得空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù)C）算法得有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D）以上三種描述都不對(duì)4.算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（）。

A．正確性B．易讀性C．健壯性D．高效率5.

算法的計(jì)算量的大小稱為計(jì)算的（）。

A．效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度二.數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)的定義：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

備注：1）數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，由數(shù)據(jù)項(xiàng)組成。通俗的說：數(shù)據(jù)元素就是現(xiàn)實(shí)世界中的一個(gè)實(shí)體的抽象。

2）數(shù)據(jù)項(xiàng)：數(shù)據(jù)的最小單位。*2.數(shù)據(jù)結(jié)構(gòu)主要研究三個(gè)方面的問題：

1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。2)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單實(shí)例StudentStudent

zhangsanStudentlisi{name;{zhangsan;{lisi;

Sno;s20081001;s20081001;class;計(jì)算機(jī)1班；計(jì)算機(jī)1班；

Rscore;515；501；

}}}數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述（本身固有的），它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容是指在存儲(chǔ)空間中使用一個(gè)存儲(chǔ)結(jié)點(diǎn)來(lái)存儲(chǔ)一個(gè)數(shù)據(jù)元素，在存儲(chǔ)空間中建立各存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)，來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。常見的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)典型例題（1）數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A）存儲(chǔ)結(jié)構(gòu)B）物理結(jié)構(gòu)C）邏輯結(jié)構(gòu)D）物理和存儲(chǔ)結(jié)構(gòu)（2）數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置改變了，（）不變。A.數(shù)據(jù)的存儲(chǔ)地址B.數(shù)據(jù)間的邏輯關(guān)系C.數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)D.邏輯結(jié)構(gòu)和物理結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹和圖都屬于非線性結(jié)構(gòu)。線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：

(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個(gè)數(shù)n定義為線性表的表長(zhǎng)；n=0時(shí)的線性表被稱為空表。稱i為ai在線性表中的位序。線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑

基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加一個(gè)新結(jié)點(diǎn)。一般情況下，要在第i(1≤i≤n)個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入到第i項(xiàng)。刪除運(yùn)算是指撤銷結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)。一般情況，要?jiǎng)h除第i(1≤i≤n)個(gè)元素，要從第i+1個(gè)元素開始，直到第n個(gè)元素，共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進(jìn)先出的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。棧的操作入棧：在棧頂位置插入一個(gè)新元素，棧頂指針top加1。退棧：取出棧頂元素并賦值給一個(gè)指定的變量，棧頂指針top減1。取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。棧如果某棧的入棧順序是ABCDEF，則出棧順序不可能是哪個(gè)（）A、DCEFBAB、ABCDEFC、EDFCABD、CBAEDF隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱為退隊(duì)。循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。循環(huán)隊(duì)列初始狀態(tài)為空，即front=rear=0.Front總是指示隊(duì)頭元素，rear指示隊(duì)尾元素加1的位置。入隊(duì)操作時(shí)，rear加1，若rear+1>容量，則置rear=0；退隊(duì)操作時(shí)，front加1，若front+1>容量，則置front=0。**當(dāng)rear>front時(shí)，元素個(gè)數(shù)＝rear－front；當(dāng)rear<front時(shí)（只有循環(huán)隊(duì)列才會(huì)出現(xiàn)隊(duì)尾指針小于隊(duì)頭指針），元素個(gè)數(shù)＝總?cè)萘浚╢ront－rear）。例:容量為25的循環(huán)隊(duì)列中，若front=16，rear=9，有__個(gè)元素單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以連續(xù)，也可以不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需要存儲(chǔ)其后繼元素的存儲(chǔ)位置信息(指針域)。指針域中存儲(chǔ)的信息稱為指針或鏈，N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于結(jié)點(diǎn)中只包含一個(gè)指針域，故稱為單鏈表。單鏈表通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的地址，稱為頭指針。整個(gè)鏈表的存儲(chǔ)必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，其指針域?yàn)榭?。單鏈表的插入和刪除雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。HEAD…∧…∧HEAD…HEAD回顧：例：已知一組數(shù)據(jù)原先采用順序存儲(chǔ)，現(xiàn)改為散列存儲(chǔ)，則（）不變。

A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.數(shù)據(jù)間的順序D.不確定例：常見的線性結(jié)構(gòu)有___,____,_____例：在線性表中刪除第5個(gè)節(jié)點(diǎn)，則原第6個(gè)節(jié)點(diǎn)的位置（），如果單鏈表則（）

A.6B.5C.不變D.不確定例：已知棧的頭指針front當(dāng)前位置為5，從棧中讀取一個(gè)數(shù)據(jù)，則front指向（）

A.5B.6C.不變D.不確定例：如果某棧的入棧順序是123456，則出棧順序不可能是哪個(gè)（）

A、435621B.123456C、546312D、654321樹及其基本概念樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：

(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。

(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹，并且稱為根的子樹。集合為空的樹簡(jiǎn)稱為空樹；樹中的元素稱為結(jié)點(diǎn)。樹的主要術(shù)語(yǔ)結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。葉節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。雙親、孩子和兄弟：結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱為兄弟。層次：結(jié)點(diǎn)的層次從根開始定義，根為第一層，根的孩子為第二層。深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。二叉樹是另一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。二叉樹的基本性質(zhì)性質(zhì)1

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)2

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）性質(zhì)3

對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2

，則：n0=n2+1性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1例：一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為

A）221B）219C）231D）229例：一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為

A）3B）4C）5D）6滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也就是說每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為[log2n]+1。從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹

ADCBEF二叉樹的基本性質(zhì)性質(zhì)5

如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[log2n]+1）的結(jié)點(diǎn)按層序（從第1層到第[log2n]+1層，每層從左到右）從1起開始編號(hào)，則對(duì)任一編號(hào)為i的結(jié)點(diǎn)(1≤i≤n)，則:

(1)如果i=1，則編號(hào)為i的結(jié)點(diǎn)是二叉樹的根，無(wú)雙親；如果i>1，則其雙親結(jié)點(diǎn)parent(i)的編號(hào)是[i/2]。

(2)如果2i>n，則編號(hào)為i的結(jié)點(diǎn)無(wú)左孩子（編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編號(hào)是2i。

(3)如果2i+1>n，則編號(hào)為i的結(jié)點(diǎn)無(wú)右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)的編號(hào)是結(jié)點(diǎn)2i+1。

例：在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多是A）8B）16C）32D）15例：在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A）32B）31C）16D）15例：深度為4的二叉樹中，編號(hào)為7的節(jié)點(diǎn)，它的右孩子節(jié)點(diǎn)為（）該樹為滿二叉樹；如果該樹是完全二叉樹，但不是滿二叉樹，則它的最大節(jié)點(diǎn)編號(hào)為（）

A）14B）8C）9D）15例：設(shè)樹T的度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別人4，2，1，1.則T中的葉子結(jié)點(diǎn)數(shù)為

A)8B)7C)6Ｄ）５二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲(chǔ)左右子樹根節(jié)點(diǎn)的存儲(chǔ)位置，即指針。L(i)V(i)R(i)LchildvalueRchild二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由"根結(jié)點(diǎn)"、"左子樹"和"右子樹"三部分構(gòu)成，則遍歷二叉樹的操作可分解為"訪問根結(jié)點(diǎn)"、"遍歷左子樹"和"遍歷右子樹"三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進(jìn)行。

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA二叉樹的遍歷已知前序和中序遍歷時(shí)，判斷出根，分出左右子樹；再根據(jù)前序分別判斷出左右子樹的根，然后再分出左右子樹，以此類推下去……例：某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是A

B

D

G

C

E

F

H，中序遍歷的結(jié)點(diǎn)訪問順序是D

G

B

A

E

C

H

F，則后序遍歷的結(jié)點(diǎn)訪問順序是：已知前序和中序遍歷時(shí)，判斷出根，分出左右子樹；再根據(jù)后序分別判斷出左右子樹的根，然后再分出左右子樹，以此類推下去……例：已知一棵二叉樹的中根序列和后根序列分別為B

D

C

E

A

F

H

G和D

E

C

B

H

G

F

A，試畫出這棵二叉樹。

二叉樹的遍歷例：例：某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是ABEFGHMN，中序遍歷的結(jié)點(diǎn)訪問順序是EFBGAMHN，則后序遍歷的結(jié)點(diǎn)訪問順序是：例：已知一棵二叉樹的中根序列和后根序列分別為6739158和6793851，試畫出這棵二叉樹。(節(jié)點(diǎn)為0到9的數(shù)字）查找順序查找:是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。如果線性表為無(wú)序表，即表中元素的排列是無(wú)序的，則不管線性表采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都必須使用順序查找。如果線性表有序，但采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則也必須使用順序查找。平均查找長(zhǎng)度為（n+1)/2，最壞為n.二分查找(折半查找)二分查找法只適用于順序存儲(chǔ)的有序表。先確定待查目標(biāo)元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當(dāng)查找區(qū)間縮小到0也沒有找到目標(biāo)元素為止。查找過程中，給定值首先和處于待查區(qū)間“中間位置”的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到“前半個(gè)區(qū)間”或“后半個(gè)區(qū)間”之后繼續(xù)進(jìn)行查找。在等概率狀態(tài)下查找成功時(shí)的平均查找長(zhǎng)度為：

ASL≈log2（n＋1）-1（當(dāng)n>50時(shí)）

折半查找二分查找例題：1.以順序查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為(n+1)/2,時(shí)間復(fù)雜度為O(n)

。

2.以二分查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度小于等于

┍log2(n+1)┑

，時(shí)間復(fù)雜度為O(log2n)。排序 排序是指將一個(gè)無(wú)序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲(chǔ)的線性表為排序?qū)ο?，在程序設(shè)計(jì)語(yǔ)言中就是一維數(shù)組。常見的排序方法有插入排序(包括簡(jiǎn)單插入排序法和希爾排序法等)、交換排序(包括冒泡排序和快速排序法等)和選擇排序(包括簡(jiǎn)單選擇排序和堆排序等)。交換類排序冒泡排序基本思想：從表頭開始掃描線性表，在掃描的過程中依次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則交換它們的位置。顯然，在掃描過程中，不斷地將將相鄰元素間較大的向后移動(dòng)，最后將線性表中最大的元素移到表尾。然后，從后向前掃描剩下的線性表，同樣在掃描的過程中依次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則交換位置。在掃描過程中，不斷地將將相鄰元素間較小的向前移動(dòng)，最后將線性表中最小的元素移到表頭。對(duì)剩下的線性表重復(fù)上述過程，直到剩余線性表為空為止，此時(shí)線性表變?yōu)橛行?。最壞情況下運(yùn)算的次數(shù)為：n*(n-1)/2（即時(shí)間復(fù)雜度）。最好情況下為：n-1.冒泡排序示例第一遍(從前向后)第一遍(從后向前)第二遍(從前向后)第二遍(從后向前)快速排序基本思想：從線性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移動(dòng)到前面，將前面大于T的元素移動(dòng)到后面，將線性表分為兩個(gè)部分(子表)，T放到分界線的位置，這個(gè)過程稱為線性表的分割，通過一次分割，就以T為分界將線性表分為兩個(gè)子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原則對(duì)子表繼續(xù)進(jìn)行分割，直到子表為空，則整個(gè)線性表有序。快速排序操作步驟：首先，在表的第一個(gè)元素、最后一個(gè)元素和中間元素中選取一個(gè)中值，設(shè)為P(k)，并將P(k)賦值給T，再將表中的第一個(gè)元素移到P(k)的位置。設(shè)兩個(gè)指針i，j分別指向表的起始和最后位置，反復(fù)操作以下兩步：將j逐漸減小，并逐次比較P(j)和T，直到發(fā)現(xiàn)一個(gè)P(j)<T為止，并將P(j)移到P(i)的位置上。將i逐漸增大，并逐次比較P(i)和T，直到發(fā)現(xiàn)一個(gè)P(i)>T為止，并將P(i)移到P(j)的位置上。上述兩步操作交替進(jìn)行，直到i和j指向同一個(gè)位置，再將T移動(dòng)到P(i)的位置上，完成一次分割。3168459023395412877631暫存樞軸記錄T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割過程31插入類排序簡(jiǎn)單插入排序基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。每次掃描將未排序列表中的第一個(gè)元素取出并插入到已排序列表中的合適位置。包含n個(gè)元素的列表最多需要n-1次掃描。簡(jiǎn)單插入排序示例原始序列第1趟第2趟第3趟第4趟第5趟希爾排序基本思想：將整個(gè)無(wú)序序列分割成若干個(gè)小的子序列分別進(jìn)行插入排序。子序列的分割方法：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列，在排序過程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序完成。增量序列一般取ht=n/2k(k=1,2…[log2n])希爾排序h=6h=1h=3完成選擇類排序簡(jiǎn)單選擇排序基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一個(gè)元素進(jìn)行交換。經(jīng)過一次選擇和交換，列表中已排序部分增加一個(gè)元素，未排序部分減少一個(gè)元素。每次把一個(gè)元素從未排序部分移動(dòng)到已排序部分稱為完成一次分類掃描或稱為一趟排序。一個(gè)包含n個(gè)元素的列表需要進(jìn)行n-1次掃描完成排序。簡(jiǎn)單選擇排序示例原始序列第1趟第2趟第3趟第4趟第5趟排序時(shí)間復(fù)雜度匯總（基數(shù)空間為O（rd)**從上表應(yīng)當(dāng)看出：1.當(dāng)原表有序或基本有序時(shí),直接插入排序和冒泡排序最好，時(shí)間復(fù)雜度可降至O(n)。（也就是最好情況下）。如果選擇快速排序則相反，達(dá)到最壞時(shí)間復(fù)雜度。2.空間復(fù)雜度最壞的是歸并排序O（n)，其次是基數(shù)排序O（rd)。3.平均時(shí)間最好的是快速、堆、歸并排序O（nlgn)。4.穩(wěn)定排序和不穩(wěn)定排序（希爾、堆、直接選擇，快速）。5.最壞情況下，時(shí)間復(fù)雜度最小的是：堆和歸并排序。第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

知識(shí)點(diǎn)歸納程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、方法和工具來(lái)支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。在程序設(shè)計(jì)中，通常采用“自頂向下，逐步求精”的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語(yǔ)言編寫的程序。程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良好的程序設(shè)計(jì)風(fēng)格概括起來(lái)包括以下及格方面：源程序文檔化數(shù)據(jù)說明的方法語(yǔ)句的結(jié)構(gòu)輸入和輸出程序設(shè)計(jì)風(fēng)格（4個(gè)方面）源程序文檔化標(biāo)識(shí)符的命名:要有一定的實(shí)際含義。程序的注釋：較完善程序一般要有注視。序言性注釋：通常置于每個(gè)程序模塊的開頭部分,一般給出程序的整體說明。功能性注釋：一般是對(duì)某條語(yǔ)句的功能性說明。程序的視覺組織：一定要層次清晰數(shù)據(jù)的說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化：比如先說明變量，其次是簡(jiǎn)單類型（如數(shù)組），接著是構(gòu)造類型（如自己定義的數(shù)據(jù)結(jié)構(gòu)）。說明語(yǔ)句中變量的安排有序化：例如多個(gè)變量出現(xiàn)在同一個(gè)說明語(yǔ)句中，要按順序排列。使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)風(fēng)格語(yǔ)句結(jié)構(gòu)在一行內(nèi)只寫一條語(yǔ)句程序編寫應(yīng)優(yōu)先考慮清晰性除非對(duì)效率有特殊要求，程序編寫要做到清晰第一，效率第二首先要保證程序正確，然后才要求提高速度避免使用臨時(shí)變量而使程序的可讀性下降避免不必要的轉(zhuǎn)移盡可能使用庫(kù)函數(shù)避免使用復(fù)雜的條件語(yǔ)句盡量減少使用“否定”條件的條件語(yǔ)句數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化要模塊化，使模塊功能盡可能單一化利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性從數(shù)據(jù)出發(fā)構(gòu)造程序不要修補(bǔ)不好的程序，要重寫編寫程序設(shè)計(jì)風(fēng)格輸入和輸出對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性檢查輸入項(xiàng)的各種重要組合的合法性輸入格式要簡(jiǎn)單，以使輸入的步驟和操作盡可能簡(jiǎn)單輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式應(yīng)允許缺省值輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。逐步求精。對(duì)復(fù)雜的問題，應(yīng)設(shè)計(jì)一些子目標(biāo)過渡，逐步細(xì)化。模塊化。一個(gè)復(fù)雜問題肯定是有若干簡(jiǎn)單問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。嚴(yán)格限制GOTO語(yǔ)句的使用。（不是不能使用）結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：

順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)程序結(jié)構(gòu)的特點(diǎn)：?jiǎn)稳肟?、單出口、結(jié)構(gòu)中無(wú)死循環(huán)（也稱有限的控制結(jié)構(gòu)），程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。例：結(jié)構(gòu)化程序設(shè)計(jì)的基本思想是采用"自頂向下，逐步求精"的程序設(shè)計(jì)方法和"單入口單出口"的控制結(jié)構(gòu)。面向?qū)ο蟪绦蛟O(shè)計(jì)

面向?qū)ο蠓椒ǖ幕靖拍?.對(duì)象、類和屬性

(1)對(duì)象的定義：在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問題域中某個(gè)實(shí)體的抽象。

(2)對(duì)象通常由對(duì)象名、屬性和操作三部分組成。

(3)類是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，類是對(duì)象的抽象，而對(duì)象是類的具體實(shí)例。類是抽象的，不占用內(nèi)存，而對(duì)象是具體的，占用存儲(chǔ)空間。對(duì)象的特點(diǎn)標(biāo)識(shí)唯一性：對(duì)象名是唯一的分類性：每個(gè)對(duì)象都有屬于自己的類。封裝性：將對(duì)象的屬性和操作封裝成一個(gè)整體，也實(shí)現(xiàn)了數(shù)據(jù)的隱藏。模塊獨(dú)立性：例題：信息隱蔽的概念與下述哪一種概念直接相關(guān)______。A.軟件結(jié)構(gòu)定義B.模塊獨(dú)立性C.模塊類型劃分D.模擬耦合度

對(duì)象的特點(diǎn)繼承：指一個(gè)類(子類)直接使用另一個(gè)類(父類)的所有屬性和方法。

單重繼承：一個(gè)類從另一個(gè)類繼承屬性和操作多重繼承：一個(gè)類有幾個(gè)父類多態(tài)性：多態(tài)性可以用“一個(gè)對(duì)外界面，多個(gè)內(nèi)部實(shí)現(xiàn)”來(lái)表示?？梢酝ㄟ^方法重載和方法重寫來(lái)實(shí)現(xiàn)多態(tài)。舉一個(gè)例子，計(jì)算機(jī)中的堆棧可以存儲(chǔ)各種格式的數(shù)據(jù)，包括整型，浮點(diǎn)或字符。不管存儲(chǔ)的是何種數(shù)據(jù)，堆棧的算法實(shí)現(xiàn)是一樣的。例：有三個(gè)棧（對(duì)象），分別放數(shù)值型、字符型、日期型數(shù)據(jù)，隊(duì)列（對(duì)象）向三個(gè)棧發(fā)送同樣的“讀取”消息，則產(chǎn)生的結(jié)果不一樣。2.方法方法也可稱為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可為其他對(duì)象使用。3.消息：面向?qū)ο笙到y(tǒng)中的對(duì)象之間是通過消息機(jī)制彼此相互合作的。消息由三部分組成：消息標(biāo)識(shí)符、零個(gè)或多個(gè)參數(shù)、接受消息對(duì)象的對(duì)象名面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護(hù)性好1、程序設(shè)計(jì)語(yǔ)言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和（D）

A）對(duì)象成分B）變量成分C）語(yǔ)句成分D）傳輸成分2、結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是（D）

A）程序的規(guī)模B）程序的效率C）程序設(shè)計(jì)語(yǔ)言的先進(jìn)性D）程序易讀性3、對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是（A）

A）程序應(yīng)簡(jiǎn)單、清晰、可讀性好B）符號(hào)名的命名只要符合語(yǔ)法

C）充分考慮程序的執(zhí)行效率D）程序的注釋可有可無(wú)4、NULL是指（C）

A）0B）空格C）未知的值或無(wú)任何值D）空字符串5、在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的（C）A）安全性B）一致性C）可理解性D）合理性6、子程序通常分為兩類：【過程】和函數(shù)，前者是命令的抽象，后者是為了求值。7、.在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為【繼承】。8、一個(gè)類可以從直接或間接的祖先中繼承所有屬性和方法，提高了軟件的【可重用性】第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件危機(jī)，軟件工程的三要素、目標(biāo)與原則。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。

軟件定義和特點(diǎn)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。計(jì)算機(jī)軟件具有如下特點(diǎn)：軟件是一種邏輯實(shí)體，具有抽象性軟件生產(chǎn)沒有明顯的制造過程軟件在運(yùn)行、使用期間不存在磨損、老化問題軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性軟件復(fù)雜性高，成本昂貴軟件開發(fā)涉及諸多社會(huì)因素軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題，包括：軟件需求的增長(zhǎng)得不到滿足軟件開發(fā)成本和進(jìn)度無(wú)法控制軟件質(zhì)量難以保證軟件不可維護(hù)或可維護(hù)性低軟件成本不斷提高軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于計(jì)算機(jī)軟件定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的三要素方法：軟件開發(fā)提供了“如何做”的技術(shù)。它包括了多方面的任務(wù)，如項(xiàng)目計(jì)劃、軟件系統(tǒng)需求分析、系統(tǒng)總體結(jié)構(gòu)的設(shè)計(jì)、編碼、測(cè)試及維護(hù)等。

工具：提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境，即通常所說的軟件工具。過程：軟件工程過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。它包括兩方面含義：1.軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動(dòng)。通常包括四種基本活動(dòng)：P(Plan)：軟件規(guī)格說明D(Do)：軟件開發(fā)C(Check)：軟件確認(rèn)A(Action)：軟件演進(jìn)2.從軟件開發(fā)的觀點(diǎn)看，軟件工程過程是使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，在活動(dòng)結(jié)束時(shí)將輸入(用戶需求)轉(zhuǎn)化為輸出(軟件產(chǎn)品)。軟件工程目標(biāo)與原則目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。*軟件工程的理論和技術(shù)性研究的內(nèi)容包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。*衡量軟件的指標(biāo)：高內(nèi)聚（模塊內(nèi)）、低耦合（模塊間）。軟件開發(fā)工具與軟件開發(fā)環(huán)境計(jì)算機(jī)輔助軟件工程(CASE):是一組工具和方法集合，可以輔助軟件開發(fā)生命周期個(gè)階段進(jìn)行軟件開發(fā)幫助進(jìn)行應(yīng)用程序開發(fā)的軟件，包括分析、設(shè)計(jì)和代碼生成.(CASE)的集成:(1)平臺(tái)集成：工具運(yùn)行在相同的硬件/操作系統(tǒng)平臺(tái)。(2)數(shù)據(jù)集成：工具使用共享數(shù)據(jù)模型來(lái)操作。(3)表示集成：工具提供相同的用戶界面。(4)控制集成：工具激活后能控制其他工具的操作。(5)過程集成：工具在一個(gè)過程模型和“過程機(jī)”的指導(dǎo)下使用。

軟件生命周期軟件從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用的過程稱為軟件的生命周期。一般包括以下幾個(gè)階段：可行性研究：目的就是用最小的代價(jià)在盡可能短的時(shí)間內(nèi)確定該軟件項(xiàng)目是否值得去開發(fā)。其實(shí)質(zhì)是要進(jìn)行一次簡(jiǎn)化、壓縮了的需求分析需求分析：任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題（即系統(tǒng)功能）。

需求分析的方法是：結(jié)構(gòu)化分析方法和面向?qū)ο蠓治龇椒?。軟件設(shè)計(jì)：任務(wù)從軟件需求規(guī)格說明書出發(fā)，形成軟件的具體設(shè)計(jì)方案，即劃分模塊結(jié)構(gòu)的過程.軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。

軟件測(cè)試:運(yùn)行和維護(hù)：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。需求分析階段的主要工作需求獲?。喊ㄐ枨髞?lái)源和獲取需求的技術(shù)。它是軟件設(shè)計(jì)的第一階段，其本質(zhì)主要是人的活動(dòng)，涉及軟件設(shè)計(jì)人員如何與客戶建立有效的溝通(弄明白要做什么？）。也稱為“需求發(fā)現(xiàn)”、“需求獲得”。

需求分析：對(duì)溝通獲得的需求或信息進(jìn)行分析、匯總，并判斷能否完成。編寫需求規(guī)格說明書(SRS)

：是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。

需求評(píng)審：在軟件生命周期中，越晚發(fā)現(xiàn)的錯(cuò)誤越難修改，修改成本越昂貴的論斷也已經(jīng)成為了大家的共識(shí)。因此我們需要評(píng)審需求規(guī)格說明是否合理地確定了所有的性能目標(biāo)，是否合理地確定了安全性方面要考慮到的問題。

軟件需求軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發(fā)進(jìn)度需求等。需求分析應(yīng)交付的主要文檔是軟件需求規(guī)格說明書。軟件需求規(guī)格說明書的特點(diǎn)：

（1）正確性；（2）無(wú)岐義性；（3）完整性；（4）可驗(yàn)證性；（5）一致性；（6）可理解性；（7）可追蹤性。需求分析階段典型例題8、需求分析的任務(wù)不包括（）

A問題分析B系統(tǒng)設(shè)計(jì)C需求描述D需求評(píng)審。9.軟件的可行性研究中不包括（D）Ａ、法律可行性Ｂ、技術(shù)可行性Ｃ、經(jīng)濟(jì)可行性Ｄ、政治可行性10.軟件生產(chǎn)過程中，需求信息由（D）給出。

A、程序員B、項(xiàng)目管理者C、軟件分析設(shè)計(jì)人員D、軟件用戶11．可行性研究要進(jìn)行一次（）需求分析。參考答案為:C

A．詳細(xì)的B．全面的C．簡(jiǎn)化的、壓縮的D．徹底的**結(jié)構(gòu)化分析方法（SA）結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。結(jié)構(gòu)化分析方法是一種建模技術(shù)（是需求分析的一種有效方法，另一種是面向?qū)ο蟮姆椒ǎ?/p>

。其實(shí)質(zhì)著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析常用的工具：數(shù)據(jù)流圖數(shù)據(jù)字典判定樹判定表（有時(shí)也用結(jié)構(gòu)化語(yǔ)言）*數(shù)據(jù)流圖1.數(shù)據(jù)流圖（DFD）：就是采用圖形方式來(lái)表達(dá)系統(tǒng)的邏輯功能、數(shù)據(jù)在系統(tǒng)內(nèi)部的邏輯流向和邏輯變換過程，是結(jié)構(gòu)化系統(tǒng)分析方法的主要表達(dá)工具。2.數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，是描述數(shù)據(jù)處理過程的工。3.數(shù)據(jù)流圖的基本元素

數(shù)據(jù)源（終點(diǎn))數(shù)據(jù)流處理(加工)數(shù)據(jù)存儲(chǔ)數(shù)據(jù)流圖的基本符號(hào)的意思矩形表示數(shù)據(jù)的外部實(shí)體（數(shù)據(jù)源或終點(diǎn)）；圓角的矩形表示變換數(shù)據(jù)的處理（加工），加工過程至少要有一個(gè)輸入流和輸出流。少右面的邊矩形表示數(shù)據(jù)存儲(chǔ)；箭頭表示數(shù)據(jù)流，是數(shù)據(jù)的流向。例：數(shù)據(jù)流圖（DFD）*處理過程至少有一個(gè)輸入數(shù)據(jù)流和一個(gè)輸出數(shù)據(jù)流

數(shù)據(jù)流程圖上的每個(gè)元素都必須有名字。數(shù)據(jù)字典數(shù)據(jù)字典（DD）:是關(guān)于數(shù)據(jù)的信息的集合，對(duì)數(shù)據(jù)流圖中的各個(gè)元素進(jìn)行完整的定義和說明。數(shù)據(jù)字典是一個(gè)預(yù)留空間，一個(gè)數(shù)據(jù)庫(kù)，這是用來(lái)儲(chǔ)存信息數(shù)據(jù)庫(kù)本身。

數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。

數(shù)據(jù)字典通常包含5個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲(chǔ)和處理過程。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。

結(jié)構(gòu)化設(shè)計(jì)（SD）從技術(shù)角度出發(fā)軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。（每個(gè)設(shè)計(jì)的含義一定要記住，見P6！)從結(jié)構(gòu)化設(shè)計(jì)角度看，軟件設(shè)計(jì)分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步完成。1.概要設(shè)計(jì)，即總體設(shè)計(jì)。將需求分析得到的DFD轉(zhuǎn)化為轉(zhuǎn)化為軟件系統(tǒng)結(jié)構(gòu)和全局?jǐn)?shù)據(jù)結(jié)構(gòu)、確定數(shù)據(jù)庫(kù)模式（即概要設(shè)計(jì)的功能）。2.概要設(shè)計(jì)的工具是結(jié)構(gòu)圖(SC）.結(jié)構(gòu)圖基本組成成分：模塊、數(shù)據(jù)和調(diào)用.3.結(jié)構(gòu)圖基本圖符由上面的數(shù)據(jù)流圖轉(zhuǎn)化的SC圖儲(chǔ)戶模塊存錢模塊其他模塊取錢模塊驗(yàn)證密碼確認(rèn)簽字詳細(xì)設(shè)計(jì)即過程設(shè)計(jì)。功能是為軟件結(jié)構(gòu)圖（SC）中的每一個(gè)模塊確定采用的算法，模塊內(nèi)數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具（如N-S圖等）給出清晰的描述。

常用工具有：程序流程圖、N-S圖、PAD圖、過程設(shè)計(jì)語(yǔ)言PDL(偽碼)。詳細(xì)設(shè)計(jì)：由SC圖中的’密碼驗(yàn)證’得到的N-S圖

（右邊是N-S圖，左邊是根據(jù)圖寫的代碼）驗(yàn)證密碼輸入密碼返回繼續(xù)輸入錯(cuò)誤正確可以取錢輸入密碼mIfm=‘123’

可以取錢Else

密碼錯(cuò)誤，請(qǐng)重新輸入需求分析的工具：

（不要與方法弄混了，也不要與結(jié)構(gòu)化分析工具弄混?。。。?/p>

問題分析圖（PAD

）、程序流程圖（PFD

）、

N-S（也是一種流程圖）也稱為盒圖，是程序流程圖的一種改進(jìn)。程序流程圖（PFD）中的箭頭代表的是：控制流數(shù)據(jù)流圖中的箭頭代表：數(shù)據(jù)的流向結(jié)構(gòu)圖（sc):箭頭代表模塊的調(diào)用備注：幾個(gè)易混的知識(shí)點(diǎn)軟件設(shè)計(jì)階段典型例題軟件設(shè)計(jì)階段典型例題1.對(duì)在數(shù)據(jù)流圖中每一個(gè)命令的圖形元素均給以定義是（B）Ａ、條目定義Ｂ、數(shù)據(jù)字典Ｃ、數(shù)據(jù)定義Ｄ、數(shù)據(jù)說明2.結(jié)構(gòu)化程序設(shè)計(jì)理論認(rèn)為，實(shí)現(xiàn)良好的程序結(jié)構(gòu)要應(yīng)用（A）的分析方法。

A、自頂向下B、自底向上C、面向?qū)ο驞、基于組件3.從事物的組成部件及每個(gè)部件的屬性、功能來(lái)認(rèn)識(shí)事物。這種方法被稱為（A）的方法。A、面向?qū)ο驜、面向數(shù)據(jù)C、面向過程D、面向?qū)傩?.（D）工具在軟件詳細(xì)設(shè)計(jì)過程中不采用。

A．判定表B．IPO圖C．PDL

D．DFD圖5．程序的三種基本控制結(jié)構(gòu)的共同特點(diǎn)是參考答案為:DA．不能嵌套使用B．只能用來(lái)寫簡(jiǎn)單程序C．已經(jīng)用硬件實(shí)現(xiàn)D．只有一個(gè)入口和一個(gè)出口6.從工程管理的角度軟件設(shè)計(jì)可分為概要設(shè)計(jì)和（詳細(xì)）設(shè)計(jì)兩大步驟。7.流程圖也稱為程序框圖是最常用的一種表示法，它有順序、分支和（循環(huán)）三個(gè)基本控制構(gòu)件。8.軟件可靠性是指在給定的時(shí)間間隔內(nèi)，程序成功運(yùn)行的_概率____

9.軟件工程時(shí)代的生產(chǎn)方式是（）化。10.結(jié)構(gòu)化設(shè)計(jì)以（）為基礎(chǔ)映射成軟件結(jié)構(gòu)。軟件結(jié)構(gòu)是以（）為基礎(chǔ)而組成的一種控制層次結(jié)構(gòu)。軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。（有時(shí)也解決存在的問題）一個(gè)好的測(cè)試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例。一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試，一般由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。

測(cè)試用例應(yīng)該包括合理的和不合理的輸入條件。測(cè)試技術(shù)與方法綜述從是否需要執(zhí)行被測(cè)試軟件的角度，可將測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。

1.靜態(tài)測(cè)試主要包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等，它可以由人工進(jìn)行

。

2.動(dòng)態(tài)測(cè)試：動(dòng)態(tài)測(cè)試是通常意義上的測(cè)試，也就是運(yùn)行和使用軟件。是根據(jù)軟件開發(fā)的各個(gè)階段的規(guī)格說明和程序的內(nèi)部結(jié)構(gòu)而精心設(shè)計(jì)的一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過程。按照功能劃分，可將軟件測(cè)試分為黑盒測(cè)試和白盒測(cè)試。（有時(shí)也稱白箱和黑箱測(cè)試）測(cè)試技術(shù)與方法綜述1.黑盒測(cè)試將測(cè)試對(duì)象看作一個(gè)黑盒，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求規(guī)格說明書，檢查程序的功能是否符合它的功能說明。這種測(cè)試又稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。

黑盒測(cè)試的方法：等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖法等。2.白盒測(cè)試把測(cè)試對(duì)象看作一個(gè)透明的盒子，利用程序內(nèi)部的邏輯機(jī)構(gòu)及有關(guān)信息，設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序的所有邏輯路徑進(jìn)行測(cè)試。通過在不同點(diǎn)檢查程序的狀態(tài)，確定實(shí)際的狀態(tài)是否與預(yù)期的一致。這種測(cè)試又稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。

白盒測(cè)試的方法：邏輯覆蓋、基本路徑測(cè)試等。3.白盒和黑盒測(cè)試有可能是動(dòng)態(tài)測(cè)試，又有可能是靜態(tài)測(cè)試。軟件測(cè)試的實(shí)施軟件測(cè)試按四個(gè)步驟（不同階段）進(jìn)行：?jiǎn)卧獪y(cè)試：對(duì)軟件設(shè)計(jì)的最小單位－模塊進(jìn)行正確性的測(cè)試，其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。是在代碼編寫階段可進(jìn)行的測(cè)試，它是整個(gè)測(cè)試工作的基礎(chǔ)。集成測(cè)試：是測(cè)試和組裝軟件的過程，它是在把模塊按照設(shè)計(jì)要求組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。確認(rèn)測(cè)試：任務(wù)是驗(yàn)證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測(cè)試：系統(tǒng)測(cè)試是將已經(jīng)確認(rèn)的軟件、計(jì)算機(jī)硬件、外設(shè)、網(wǎng)絡(luò)等其他元素結(jié)合在一起，進(jìn)行信息系統(tǒng)的各種組裝測(cè)試和確認(rèn)測(cè)試，其目的是通過與系統(tǒng)的需求相比較，發(fā)現(xiàn)所開發(fā)的系統(tǒng)與用戶需求不符或矛盾的地方，從而提出更加完善的方案。程序調(diào)試程序調(diào)試的任務(wù)是診斷和修正程序中的錯(cuò)誤。調(diào)試的方法：強(qiáng)行排錯(cuò)法回溯法原因排除法軟件維護(hù)定義：軟件維護(hù)主要是指根據(jù)需求變化或硬件環(huán)境的變化對(duì)應(yīng)用程序進(jìn)行部分或全部的修改，修改時(shí)應(yīng)充分利用源程序．修改后要填寫程序改登記表，并在程序變更通知書上寫明新舊程序的不同之處。分類：

1.適應(yīng)性維護(hù)：為適應(yīng)軟件運(yùn)行環(huán)境的變化而修改軟件的活動(dòng)。

2.改善性維護(hù)：根據(jù)用戶在軟件使用過程中提出的建設(shè)性意見而進(jìn)行的維護(hù)活動(dòng)。

3.糾錯(cuò)性維護(hù)：為改正軟件系統(tǒng)中潛藏的錯(cuò)誤而進(jìn)行的維護(hù)活動(dòng)。

4.預(yù)防性維護(hù)：為了改進(jìn)應(yīng)用軟件的可靠性和可維護(hù)性，為了適應(yīng)未來(lái)的軟硬件環(huán)境的變化而進(jìn)行的維護(hù)活動(dòng)。維護(hù)的副作用維護(hù)的副作用有編碼副作用、數(shù)據(jù)副作用、文檔副作用三種。1.編碼副作用：在使用程序設(shè)計(jì)語(yǔ)言修改源代碼時(shí)，都可能引入錯(cuò)誤。例如，刪除或修改一個(gè)子程序、刪除或修改一個(gè)標(biāo)號(hào)、刪除或修改一個(gè)標(biāo)識(shí)符等。2.數(shù)據(jù)副作用：在修改數(shù)據(jù)結(jié)構(gòu)時(shí)，可能導(dǎo)致軟件出錯(cuò)。例如，在修改定義局部或全局常量、重新定義記錄或文件格式、增大或減小一個(gè)數(shù)組或數(shù)據(jù)結(jié)構(gòu)的大小。3.文檔副作用：對(duì)相關(guān)技術(shù)文檔進(jìn)行相應(yīng)修改而引起的錯(cuò)誤。例如：用戶對(duì)交互輸入的順序或格式進(jìn)行修改。軟件測(cè)試維護(hù)階段典型例題1.下列關(guān)于軟件測(cè)試的敘述中錯(cuò)誤的是（D）。（選擇一項(xiàng)）A、軟件測(cè)試可以作為度量軟件與用戶需求間差距的手段B、軟件測(cè)試的主要工作內(nèi)容包括發(fā)現(xiàn)軟件中存在的錯(cuò)誤并解決存在的問題C、軟件測(cè)試的根本目的是盡可能多地發(fā)現(xiàn)軟件中存在地問題，最終把以個(gè)高質(zhì)量地軟件系統(tǒng)交給用戶使用D、沒有發(fā)現(xiàn)錯(cuò)誤地測(cè)試也是有價(jià)值的2.在軟件工程中，白箱測(cè)試法可用于測(cè)試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是______。(C)

A.循環(huán)的集合B.地址的集合C.路徑的集合D.目標(biāo)的集合3.在設(shè)計(jì)測(cè)試用例時(shí)，應(yīng)當(dāng)包括（C）Ａ、合理的輸入條件Ｂ、不合理的輸入條件Ｃ、合理的和不合理的輸入條件Ｄ、部分條件4、與設(shè)計(jì)測(cè)試數(shù)據(jù)無(wú)關(guān)的文檔是（D）。

A、需求說明書B、設(shè)計(jì)說明書C、源程序D、項(xiàng)目開發(fā)設(shè)計(jì)5.軟件測(cè)試的目的是（）A實(shí)驗(yàn)性運(yùn)行軟件B找出軟件中的錯(cuò)誤C證明軟件正確D找出軟件中的全部錯(cuò)誤6.對(duì)于軟件測(cè)試分類，下列各項(xiàng)都是按照不同階段來(lái)進(jìn)行的劃分，除了（C）。

A、單元測(cè)試B、集成測(cè)試C、黑盒測(cè)試D、系統(tǒng)測(cè)試7.在設(shè)計(jì)測(cè)試用例時(shí)，應(yīng)當(dāng)包括（C）Ａ、合理的輸入條件Ｂ、不合理的輸入條件Ｃ、合理的和不合理的輸入條件Ｄ、部分條件測(cè)試與維護(hù)階段典型例題8.與設(shè)計(jì)測(cè)試數(shù)據(jù)無(wú)關(guān)的文檔是（D）。

A、需求說明書B、設(shè)計(jì)說明書C、源程序D、項(xiàng)目開發(fā)設(shè)計(jì)9、為了進(jìn)一步改善軟件系統(tǒng)的可維護(hù)性和可靠性，并為以后的改進(jìn)奠定基礎(chǔ)的軟件維護(hù)稱為（D）。

A。糾錯(cuò)性維護(hù)B適應(yīng)性維護(hù)C改善性維護(hù)D預(yù)防性維護(hù)10.為適應(yīng)軟件運(yùn)行環(huán)境的變化而修改軟件的活動(dòng)稱為（B）。

A.糾錯(cuò)性維護(hù)B適應(yīng)性維護(hù)C改善性維護(hù)D預(yù)防性維護(hù)11、根據(jù)用戶在軟件使用過程中提出的建設(shè)性意見而進(jìn)行的維護(hù)活動(dòng)稱為（C）。

A糾錯(cuò)性維護(hù)B適應(yīng)性維護(hù)C改善性維護(hù)D預(yù)防性維護(hù)12、為改正軟件系統(tǒng)中潛藏的錯(cuò)誤而進(jìn)行的維護(hù)活動(dòng)稱為（A）。

A錯(cuò)性維護(hù)B適應(yīng)性維護(hù)C改善性維護(hù)D預(yù)防性維護(hù)

13、以下不屬于白盒測(cè)試技術(shù)的是（D）

A邏輯覆蓋B基本路徑測(cè)試C循環(huán)覆蓋測(cè)試D等價(jià)類劃分14．產(chǎn)生軟件維護(hù)的副作用，是指（C）

A．開發(fā)時(shí)的錯(cuò)誤B．隱含的錯(cuò)誤C．因修改軟件而造成的錯(cuò)誤D．運(yùn)行時(shí)誤操作15.軟件測(cè)試方法中（）屬于靜態(tài)測(cè)試。

A黑盒法B路徑覆蓋C錯(cuò)誤推測(cè)D人工檢測(cè)測(cè)試與維護(hù)階段典型例題16.黑盒測(cè)試主要是測(cè)試軟件是否滿足（功能）需求。17.程序設(shè)計(jì)語(yǔ)言的（可維護(hù)）性通常指這種語(yǔ)言編寫的程序被理解，被修改及調(diào)整和改進(jìn)的難易程度。18.軟件測(cè)試是為了（）而執(zhí)行程序的過程。19.軟件測(cè)試的目的是盡可能的發(fā)現(xiàn)軟件中錯(cuò)誤，通常（）是在代碼編寫階段可進(jìn)行的測(cè)試，它是整個(gè)測(cè)試工作的基礎(chǔ)。

20.若按功能劃分，軟件測(cè)試的方法通常分為白盒測(cè)試方法和（）測(cè)試方法。按軟件是否被執(zhí)行，軟件測(cè)試分為（）和（）。21.測(cè)試用例應(yīng)有（）和預(yù)期的輸出數(shù)據(jù)兩部分組成。這樣便于對(duì)照檢查。22.黑盒測(cè)試是（）測(cè)試，因此設(shè)計(jì)測(cè)試用例時(shí)，需要研究需求規(guī)格說明書和概要設(shè)計(jì)說明書中有關(guān)程序功能或輸入、輸出之間的關(guān)系等信息。23.維護(hù)的副作用有編碼副作用、（）、文檔副作用三種。

24.程序（）的任務(wù)是診斷和修正程序中的錯(cuò)誤。其方法有強(qiáng)行排錯(cuò)法、（）和回溯法。第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。

4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。知識(shí)點(diǎn)歸納數(shù)據(jù)庫(kù)的定義1.長(zhǎng)期存放在計(jì)算機(jī)內(nèi)，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫(kù)中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲(chǔ)，具有較小的冗余度、較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性。數(shù)據(jù)獨(dú)立性包括：物理和邏輯獨(dú)立性。

物理獨(dú)立性是指用戶的應(yīng)用程序與存儲(chǔ)在磁盤上的數(shù)據(jù)庫(kù)中數(shù)據(jù)是相互獨(dú)立的。即，數(shù)據(jù)在磁盤上怎樣存儲(chǔ)由DBMS管理，用戶程序不需要了解。

邏輯獨(dú)立性是指用戶的應(yīng)用程序與數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)是相互獨(dú)立的，即，當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，用戶程序也可以不變。

2.數(shù)據(jù)庫(kù)還可以說成：是由一個(gè)互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的。3.數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。計(jì)算機(jī)數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段人工管理階段:數(shù)據(jù)不具有獨(dú)立性,由應(yīng)用程序管理數(shù)據(jù)本身。文件系統(tǒng)階段:數(shù)據(jù)獨(dú)立性和共享性差,由文件管理數(shù)據(jù)本身。數(shù)據(jù)庫(kù)系統(tǒng)階段：有較高的數(shù)據(jù)獨(dú)立性和共享性，由數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)管理數(shù)據(jù)。數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫(kù)的應(yīng)用程序的集合也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫(kù)等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義：數(shù)據(jù)庫(kù)存放數(shù)據(jù)的模式，即數(shù)據(jù)庫(kù)中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述。

數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。數(shù)據(jù)操縱：數(shù)據(jù)的查詢、修改、刪除、添加四種操作。數(shù)據(jù)的完整性、安全性定義和檢查：數(shù)據(jù)庫(kù)的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS提供了相應(yīng)的語(yǔ)言：數(shù)據(jù)定義語(yǔ)言(DDL)數(shù)據(jù)操縱語(yǔ)言(DML)數(shù)據(jù)控制語(yǔ)言(DCL，用來(lái)設(shè)置或者更改數(shù)據(jù)庫(kù)用戶或角色權(quán)限的語(yǔ)句)數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。

DBS=DB+DBMS+DBA數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式外模式：又稱為用戶模式，是每個(gè)用戶的局部數(shù)據(jù)描述，用戶的數(shù)據(jù)視圖.概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶的數(shù)據(jù)視圖.內(nèi)模式：又稱為物理模式，是數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)和物理存取方法的描述.二級(jí)映射:保證了數(shù)據(jù)的物理獨(dú)立性和邏輯獨(dú)立性概念模式到內(nèi)模式的映射(物理獨(dú)立性)外模式到概念模式的映射(邏輯獨(dú)立性)數(shù)據(jù)模型數(shù)據(jù)模型是數(shù)據(jù)模型（DataModel）是數(shù)據(jù)特征的抽象，它是數(shù)據(jù)及其操作的一種抽象表示。數(shù)據(jù)模型描述的內(nèi)容包括三部分：數(shù)據(jù)結(jié)構(gòu)：主要描述數(shù)據(jù)的類型、內(nèi)容、性質(zhì)以及數(shù)據(jù)間的聯(lián)系等。數(shù)據(jù)操作：主要描述在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)上的操作類型和操作方式。如選擇、投影、連接等。數(shù)據(jù)約束：主要描述數(shù)據(jù)結(jié)構(gòu)內(nèi)數(shù)據(jù)間的語(yǔ)法、詞義聯(lián)系等。一個(gè)學(xué)生實(shí)體轉(zhuǎn)換為關(guān)系模型一學(xué)生：姓名：張三；年齡：20；性別：男；班級(jí)：中文1；入學(xué)成績(jī)：550。學(xué)生表：姓名年齡性別班級(jí)入學(xué)成績(jī)張三20男中文1550數(shù)據(jù)模型數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型：概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型概念數(shù)據(jù)模型：簡(jiǎn)稱概念模型，是面向現(xiàn)實(shí)世界的，其出發(fā)點(diǎn)是有效地模擬現(xiàn)實(shí)世界，給出數(shù)據(jù)的概念化結(jié)構(gòu)。與具體的數(shù)據(jù)管理系統(tǒng)無(wú)關(guān)。概念數(shù)據(jù)模型必須換成邏輯數(shù)據(jù)模型，才能在DBMS中實(shí)現(xiàn)。

實(shí)體聯(lián)系模型是一種廣泛使用的概念模型，該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化為實(shí)體、聯(lián)系和屬性等幾個(gè)基本概念，并用ER圖直觀地表示出來(lái)。ER模型的基本概念實(shí)體：概念世界中的基本單位，它們是客觀存在且能相互區(qū)別的事物。凡具有共性的實(shí)體可以組成一個(gè)集合稱為實(shí)體集。屬性：屬性用來(lái)描述實(shí)體的特征。一個(gè)實(shí)體可以有多個(gè)屬性，每個(gè)屬性可以有值，一個(gè)