全國計算機等級考試二級公共基礎(chǔ)知識總結(jié)

1、全國計算機等級考試二級公共基礎(chǔ)知識總結(jié) 第一章數(shù)據(jù)結(jié)構(gòu)與算法 1.1 算法1算法的基本特征：可行性；確定性，有窮性；擁有足夠的情報。，2確定性：算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；3算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。4歸納法：通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論的算法的設(shè)計方法。5算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量?？梢杂盟惴ㄔ趫?zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量。6算法時間復(fù)雜度取決于問題的規(guī)模和待處理的數(shù)據(jù)的初態(tài)。7如果算法P調(diào)用另一個算法Q，而算法Q又調(diào)用算法P，則稱為間接遞歸調(diào)

2、用8工程上常用的分治法是減半遞推技術(shù)9算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。10如果查找的x一定在數(shù)組中，此時q=1，則A(n)=(n+1)/2。也就是說，在這種情況下，用順序搜索法在長度為n的一維數(shù)組中查找值為x的元素，在平均的情況下需要檢查數(shù)組中一半的元素。如果已知需要查找的x有一半機會在數(shù)組中，此時q=1/2。則A(n)=(n+1)/4+n/2=3n/4。x不在數(shù)組中時，A(n)=n。. 11下面程序段的時間復(fù)雜度是 for(int i=0;i<n;i+)for(int j=1;j<=m;j+)Aij=0;語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)，一個算法中所有語句的頻

3、度之和構(gòu)成了該算法的運行時間。本例中語句:Aij=0;的頻度是n*m，所以該程序段的時間復(fù)雜度是：O(m*n).12算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。13一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程較慢。14算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念1數(shù)據(jù)結(jié)構(gòu)研究的三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）；數(shù)據(jù)運算。2邏輯結(jié)構(gòu)是數(shù)據(jù)元素間關(guān)系的描述，與所用的計算機無關(guān)3數(shù)據(jù)的邏輯關(guān)系是指數(shù)據(jù)元素的關(guān)聯(lián)。4數(shù)據(jù)的不可分割的基本單位是數(shù)據(jù)項。5數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的

4、數(shù)據(jù)元素的集合。6一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、7。索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。8數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式，與所使用的計算機密切相關(guān)9根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。10在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點或結(jié)點11插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改等。12在數(shù)據(jù)結(jié)構(gòu)中，

5、用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的方式是線性結(jié)構(gòu)。13一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示13 線性表及其順序存儲結(jié)構(gòu)1數(shù)據(jù)元素的位置只取決于自己的序號，2線性表是由n個數(shù)據(jù)元素組成的一個有限序列。刪除一個元素，平均移動的元素的個數(shù)為(n-1+n-2+.+0)/n=(n-1)/2；插入一個元素，平均移動元素個數(shù)為(n+n-1+n-2+.+1)/n=(n+1)/2，所以總體移動元素個數(shù)為n/2。3線性表是一種線性結(jié)構(gòu)，數(shù)據(jù)元素之間的相對位置是線性的。4線性表可以是空表。5非空線性表的結(jié)構(gòu)特征：（1）且只有一個根結(jié)點a1，它無前件；（2）有且只有一個終端結(jié)點an，它無后

6、件；（3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。6線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。7ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。例：一個矢量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是108數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置，即：。 ADR(ai)=ADR(a1)+(i-1

7、)k 第5個元素的地址：ADR(a5)=100+(5-1)X2=1088在線性表的順序存儲結(jié)構(gòu)下，可以對線性表進(jìn)行各種處理。主要的運算有：線性表的插入、線性表的刪除、線性表的查找、線性表的排序、線性表的分解、線性表的合并、線性表的復(fù)制、線性表的逆轉(zhuǎn)等9線性表的順序存儲結(jié)構(gòu)對于小線性表或者其中元素不常變動的線性表來說是合適的，因為順序存儲的結(jié)構(gòu)比較簡單。10采用順序存儲的線性表，順序存儲結(jié)構(gòu)必須占用一片連續(xù)的存儲單元，當(dāng)對其進(jìn)行插入和刪除操作時需要移動大量的元素，優(yōu)點是存儲密度大，由于數(shù)組的存儲方式是采用順序存儲的，即占用連續(xù)的存儲空間，所以可以用數(shù)組的下標(biāo)直接存取。11查找第i-1個結(jié)點和第i

8、個結(jié)點，在順序表中查找的時間復(fù)雜度為O(1) 速度最快。由于鏈表結(jié)構(gòu)在空間存儲上的不連續(xù)性，在查找某個結(jié)點時，需要從當(dāng)前結(jié)點開始向前或者向后逐個比較查找，浪費時間，查找結(jié)果的時間復(fù)雜度均為O(n)，12鏈接存儲不是占用一片連續(xù)的存儲空間，所以便于進(jìn)行插入和刪除操作。13線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中的每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包括指針，每一個指針指向一個與本結(jié)點有邏輯關(guān)系的結(jié)點，此類存儲方式屬于順序存儲。14 棧和隊列1棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。2棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧

9、具有記憶作用。用top表示棧頂位置，用bottom表示棧底。3當(dāng)一個棧ST （最多元素為MaxSize）時，ST->top= -1是判斷順序棧為空的條件。ST->top=MaxSize-1是判斷順序棧為滿的條件。4棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進(jìn)行的。5通常元素出棧的順序是先取出棧頂元素再移動棧頂指針，使之指向新的棧頂元素。6從一個循環(huán)隊列中刪除一個元素，通常是先取出

10、元素再移動棧頂指針7隊列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。8在一個容量為25的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中共有3個元素9隊列是“先進(jìn)行出”（FIFO）或“后進(jìn)后出”（LILO）的線性表。10隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿11當(dāng)循環(huán)隊列為空（S=0）時，不能進(jìn)行退隊運算，這種情況稱為下溢12棧的基本操作。一個棧的入棧序列是1,2,3,.,n,其輸出序列為P1

11、，P2，P3，。，Pn，若P1=n，則Pi為n-i+1當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的運算原理，n必定是最后入棧的，那么輸入順序必定是1,2,3,.,n,則出棧的序列是n,n-1,n-2,.,113設(shè)初始輸入序列為1，2，3，4，5，利用一個棧產(chǎn)生輸出序列，下列B序列是不可能通過棧產(chǎn)生的由于棧的壓入和退出只能在棧頂進(jìn)行，所以要使出棧的第一個數(shù)是序列的最后一個數(shù)5，只能先把序列所有元素都壓入棧，但這時出棧序列只能是（A 5，4，3，2，1），所以（B 5，3，4，1，2）選項的出棧序列是錯誤的，應(yīng)選（B）。當(dāng)初始序列壓入一個時，就退出一個元素，這樣就得到（A）選項的出棧序列1，2，3，4，

12、5；先壓入1，2，3，4四個元素，再退出所有元素，最后壓入5，并退棧這時得到（C）選項的出棧序列4，3，2，1，5；壓入1，2后對后面的元素3，4，5分別壓入一個退出一個，這時便得到（D）選項的出棧序列3，4，5，2，1。15 線性鏈表1數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于存儲結(jié)構(gòu)。2數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元（一個一個小塊）稱為存儲結(jié)點，簡稱結(jié)點。3結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。 4在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏

13、輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)是散列存儲5帶頭結(jié)點的雙向循環(huán)鏈表L為空的條件是：只有該頭結(jié)點，即L->next=L 或者 L->prior=L6對于鏈?zhǔn)疥犃薪Y(jié)構(gòu)，插入元素是在隊尾進(jìn)行的，只需修改隊尾指針，不需修改隊頭指針。向鏈?zhǔn)疥犃兄胁迦胍粋€結(jié)點就是在單鏈表表尾插入一個結(jié)點，同時新插入的結(jié)點成為表尾結(jié)點。例：在一個鏈?zhǔn)疥犃兄?，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算是r->next=s;r=s;7向鏈?zhǔn)綏Ｖ胁迦胍粋€結(jié)點，就是在單鏈表的表頭插入一個結(jié)點，同時將新結(jié)點的位置賦予棧頂指針。例：向一個棧頂指針為HS的鏈?zhǔn)?/p>

14、棧中插入一個s所指的結(jié)點時，則執(zhí)行s->next=HS;HS=s;8線性鏈表的基本操作：插入、刪除、查找、排序。9雙向鏈表每個結(jié)點有兩個指針域，這兩個指針分別指向它的前驅(qū)結(jié)點和后繼結(jié)點。10單鏈表中，每個結(jié)點都含有一個指針域，這個指針指向它的下一個結(jié)點。因此訪問單鏈表中的結(jié)點時，必須沿著它的指針逐個進(jìn)行。11由于雙向鏈表比單鏈表結(jié)構(gòu)復(fù)雜，所以在插入和刪除元素時，要修改更多的指針域，相對比較復(fù)雜，單向鏈表和雙向鏈表在空間存儲上的不連續(xù)性決定了兩者都不可以隨機訪問，在雙向鏈表中由于每個結(jié)點包括兩個指針域，其中一個指向該結(jié)點的前驅(qū)結(jié)點，另一個指向該結(jié)點的后繼結(jié)點，因此它既可以直接訪問前驅(qū)結(jié)點，

15、又可以直接訪問后繼結(jié)點，而單鏈表每個結(jié)點只有一個指針域，指向它的后繼結(jié)點，所以它只能直接訪問它的下一個結(jié)點，而無法直接訪問它的前一個結(jié)點。所以雙向鏈表順序訪問相鄰結(jié)點更加靈活。12鏈表的特點：順序表可以隨機訪問任意一個結(jié)點，而鏈表必須從第一個數(shù)據(jù)結(jié)點出發(fā)，逐一查找每個結(jié)點。鏈表結(jié)構(gòu)是一些邏輯上相鄰，而空間上并不一定相鄰的數(shù)據(jù)元素的集合，相鄰的結(jié)點之間通過指針相互聯(lián)系，在插入和刪除元素時，只需修改結(jié)點指針即可，不需要移動數(shù)據(jù)元素。當(dāng)存儲空間不足時，可以動態(tài)為其分配內(nèi)存空間，所以不必事先估計存儲空間的大小。所需空間與其長度成正比。13用帶頭結(jié)點的鏈表表示線性表時，空表和非空表的插入、刪除是相同的。

16、當(dāng)往空鏈表插入元素時，只要把待插入元素的指針域指向頭結(jié)點的指針域，把頭結(jié)點的指針域指向新增元素即可，當(dāng)往非空鏈表插入元素時只要找到插入的位置，執(zhí)行同樣的操作即可完成插入。當(dāng)鏈表只有一個元素時，刪除操作只要修改指針指向下一個元素的指針?biāo)傅脑丶纯桑话愕逆湵韯h除操作是一樣的。帶頭結(jié)點的鏈表并不能加快對鏈表的遍歷，帶頭結(jié)點的鏈表反而要增加一個用于存儲頭結(jié)點的空間，并不能節(jié)省存儲空間，用帶頭結(jié)點的鏈表跟存取元素的速度無關(guān)。14忽略了最后結(jié)點或頭結(jié)點的指針，在n個結(jié)點的單向鏈表（無表頭結(jié)點）中，每個結(jié)點都有一個指針單元（即指針域），加上頭指針，至少需要n+1個指針單元。 16 樹與二叉樹1樹是一種

17、簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。棧和隊列都是線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。2樹的結(jié)點不能為空，結(jié)點最少的樹為只有一個結(jié)點的樹；二叉樹的結(jié)點數(shù)可以為0，結(jié)點最少的二叉樹為空的二叉樹。3設(shè)樹T的度為4，其中度為

18、1，2，3和4的結(jié)點的個數(shù)分別為4、2、1、1，則T中葉子結(jié)點的個數(shù)為8（根據(jù)樹的性質(zhì)：樹的結(jié)點數(shù)等于所有結(jié)點的度與對應(yīng)的結(jié)點個數(shù)乘積之和為1。因此樹的結(jié)點數(shù)為1*4+2*2+3*1+4*1+1=16。葉子結(jié)點數(shù)目等于樹結(jié)點總數(shù)減去度不為0的結(jié)點數(shù)之和，即16-(4+2+1+1)=8。）4設(shè)二叉樹根結(jié)點的層次為0，對含有100個結(jié)點的二叉樹，可能的最大樹深和最小樹深分別是99和6（要使二叉樹在規(guī)定結(jié)點下有最大樹深，這時二叉樹退化成一個線性鏈表，如果對應(yīng)二叉樹的根結(jié)點的層次為0，那么對應(yīng)二叉樹的樹深為結(jié)點個數(shù)減1，即99；要使二叉樹有最小樹深，則此二叉樹為滿二叉樹，當(dāng)滿二叉樹的根結(jié)點的層次為1時

19、，結(jié)點個數(shù)n和樹深h之間的關(guān)系為：n=2h-1，所以當(dāng)二叉樹的根結(jié)點層次為0時，對應(yīng)關(guān)系為n=2(h+1)-1。）二叉樹的基本性質(zhì)：（1）在二叉樹的第k層上，最多有2k-1(k1)個結(jié)點；（2）深度為m的二叉樹最多有2的m次方-1個結(jié)點；（3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；例：深度為5的二叉樹至多有2*2*2*2*2-1=31個結(jié)點。具有3個結(jié)點的二叉樹有5種，8例：設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點，則此二叉樹中所包含的結(jié)點數(shù)至少2h-1為結(jié)點最少的情況，除根結(jié)點層只有1個結(jié)點外，其余h-1層均有兩個結(jié)點，結(jié)點總數(shù)=2(h-1)+1=2h-1。（4）具有n個結(jié)

20、點的二叉樹，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分；（5）具有n個結(jié)點的完全二叉樹的深度為log2n+1；（6）設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，.n給結(jié)點進(jìn)行編號（k=1,2.n），有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點編號為INT(k/2)；若2kn，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；若2k+1n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。9對于深度等于其結(jié)點數(shù)的二叉樹，每層只有一個結(jié)點，假設(shè)從上向下

21、分別為a1,a2,.,an,則先序遍歷序列為a1,a2,.,an。后序遍歷序列為an,an-1,.a1。遍歷序列正好相反。滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k-1個結(jié)點深度為m的滿二叉樹有2m-1個結(jié)點。10由滿二叉樹的樹深和結(jié)點的關(guān)系知，對于深度為h的滿二叉樹，m個樹葉,n個結(jié)點,則n=2h-1即 n=20+21+22+.+2(h-1)=2h-1。完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點。11例：設(shè)一棵叉樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為1312例：假定根結(jié)點的層次是0，含有1

22、5個結(jié)點的二叉樹的最小樹深是3（要使二叉樹在規(guī)定結(jié)點數(shù)下的深度最小，這樣的二叉樹只能是完全二叉樹。當(dāng)根結(jié)點的層次為1時，二叉樹的結(jié)點n和深度h之間的關(guān)系是n=2h-1，所以當(dāng)二叉樹的根結(jié)點的層次為0時，結(jié)點和樹深的關(guān)系是n=2(h+1)-1，所以h=3，n=15）13在在深度為5的完全二叉樹中，度為2的結(jié)點數(shù)最多為1514樹的度是指樹內(nèi)各結(jié)點的度的最大值,一棵樹中除根結(jié)點之外,每個結(jié)點都有一個前驅(qū)結(jié)點,結(jié)點擁有子樹的個數(shù)稱為結(jié)點的度,所以結(jié)點的度數(shù)之和即為除根結(jié)點外所有結(jié)點的個數(shù),即每個結(jié)點的度數(shù)之和等于結(jié)點總數(shù)減1,結(jié)點的度即是擁有子樹的個數(shù),而結(jié)點與子樹之間是以邊連接的,所以一棵樹中每個結(jié)

23、點的度數(shù)之和與邊的條數(shù)相等,15由二叉樹的性質(zhì)知二叉樹葉子的個數(shù)n(0)和度為2的結(jié)點個數(shù)n(2)的關(guān)系為n(0)=n(2)+1。二叉樹的結(jié)點個數(shù)可以等于0，二叉樹中有些不是葉子的結(jié)點只有一個子女，二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲。16二叉樹的遍歷：前序遍歷DLR先根結(jié)點，后遍歷左子樹，最后遍歷右子樹；abdgcefh EFHIGJK EDBAC DBEAFC中序遍歷LDR先左子樹，后訪問根結(jié)點，最后遍歷右子樹；dgbaechf HFIEJKG DEBAC ABDECF后序遍歷LRD先左子樹，后遍歷右子樹，最后訪問根結(jié)點 gdbehfca 右子樹為

24、G DACBE DEBFCA17在先序、中序、后序遍歷序列中葉子結(jié)點總是從左向右的。相對次序是不發(fā)生改變的。是完全相同的。（任意兩種方法遍歷同一棵二叉樹，可以確保唯一一棵二叉樹，無論是用前序遍歷、中序遍歷、后序遍歷二叉樹，其區(qū)別都在于訪問根的先后次序不同，而葉子結(jié)點的順序是一樣的。）18例：對樹的三大部分：樹根、左子樹、右子樹，存在樹根結(jié)點大于左子樹各個結(jié)點，小于右子樹各個結(jié)點，因此要得到各個結(jié)點值的遞增序列，應(yīng)按“左子樹-根結(jié)點-右子樹”的順序進(jìn)行訪問，這就是中序遍歷的遍歷過程。 19例：設(shè)n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷中，n在m后的條件是n在m的右子樹上，如果n在m的右子樹上，

25、根據(jù)中序遍歷算法，先訪問根結(jié)點m，然后再訪問右子樹上的結(jié)點，所以n必然要在m后。如果n是m的祖先，則m可能在n的左子樹上，也可能在n的右子樹上，如果m在n的左子樹上，根據(jù)中序遍歷算法，先訪問n的左子樹，然后訪問n結(jié)點，所以n必然要在m后，對如果n是m的子孫，則n可能在m的左子樹上，也可能在m的右子樹上。中序遍歷時，先訪問左子樹，再訪問根結(jié)點。n在m前，則n必須在m的左子樹中。 20在中序遍歷序列中，根結(jié)點將左右子樹分開，左邊為左子樹中的所有結(jié)點，右邊為右子樹中的所有結(jié)點。21現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有5種不同形態(tài)的二叉樹可以得到這樣的遍歷結(jié)果22在一棵二叉樹中，度為0的結(jié)點個數(shù)為

26、m，度為2的結(jié)點個數(shù)為n，則二者之間的關(guān)系是m=n+123設(shè)一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中有350個葉子結(jié)點17 查找技術(shù)順序查找的使用情況：（1）線性表為無序表；（2）表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。1順序查找法適合于線性表，不論采用順序存儲還是鏈?zhǔn)酱鎯?。散列存儲于順序查找無關(guān)，同樣壓縮存儲、索引存儲也與順序查找無關(guān)2二分法查找也稱折半查找，只適用于順序存儲結(jié)構(gòu)的且數(shù)據(jù)元素按關(guān)鍵字有序的有序表，對于長度為n的有序線性表進(jìn)行二分查找，最壞情況只需比較log2n次。3例：有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找為82的結(jié)點時，4次比校

27、后查找成功。（此有序表的長度為13，按比較次數(shù)log2n計算應(yīng)該是4?；蛳日抑虚g結(jié)點45，再找77，95，最后找到82，經(jīng)過4次比較，）4例：對有18個元素的有序表用二分法查找，則查找A3的比較序列的下標(biāo)為9、4、2、3第一次(1+18)/2=9,第二次(1+8)/2=4,第三次(1+3)/2=2,第四次(3+3)/2=3。5例：設(shè)有一個已按元素的值排好序的線性表（長度大于2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數(shù)分別是s和b，在查找不成功的情況下，s和b的關(guān)系是s>b 。 (對于順序查找，查找不成功時和給定關(guān)鍵字比較的次數(shù)為n+1。二分查找查找不

28、成功的關(guān)鍵字比較次數(shù)為log2n+1即最大比較次數(shù)。當(dāng)n>=2時，顯然n+1>log2n+1。)6例：在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為4（二分查找是用要查找的關(guān)鍵碼與線性表的中間元素比較，根據(jù)比較結(jié)果是結(jié)束查找，還是在左邊或者右邊子表按相同的方法繼續(xù)查找。與11比較的關(guān)鍵碼分別為15、8、10、12。比較的次數(shù)為4。）7例：在順序表（8，12，16，20，26，27，31，34，43，49，51）中，用二分法查找關(guān)鍵值為21，需做的比較次數(shù)為4（首先與27比較，由于21比27小，根據(jù)二分法比較

29、的方法，所以接著與27左邊的16比較，由于21比16大，所以與16右邊的20比較，最后一次與26比較。所以總共比較了4次。）8例：對一個長度為10的排好序的表用二分法查找，若查找不成功，至少需要比較的次數(shù)是3（分查找的值小于表中所有元素和大于表中所有元素兩種情況進(jìn)行分析），9例：在長度為n的線性表中查找一個表中不存在的元素，需要的比較次數(shù)為n10例：設(shè)線性表（a1，a2，。，a500）元素的值由小到大排列，對一個給定的k值用二分法查找線性表，在查找不成功的情況下至多需比較9次（二分法查找在查找不成功的情況下至多需要比較log2n+1=9(n=500)。）11例：已知有序表為（12，18，24，

30、35，47，50，62，83，90，115，134），當(dāng)用二分法查找100時，需進(jìn)行3次比較可確定成功（畫出二叉樹判定樹，當(dāng)查找100時，需要和50、90、110比較，由于110的左子樹為空，查找結(jié)束，比較了3次。）12如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，可以采用分塊查找方法13順序查找法查找長度為n的線性表時，每個元素的平均查找長度為(n+1)/2。18 排序技術(shù)排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。1交換類排序法：（1）冒泡排序法，需要比較的次數(shù)（在最壞情況下的時間復(fù)雜度）為n(n-1)/2；（2）快速排序法。2插入類排序法：（1）簡單插入排序法，

31、最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要O(n1.5)次比較。3選擇類排序法：（1）簡單選擇排序法, 最壞情況需要n(n-1)/2次比較；選擇排序的思想為：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。第一個元素需要比較n-1次，第二個元素需要比較n-2次，依次類推，倒數(shù)第二個元素只須比較1次即可，所以總的比較次數(shù)為：(n-1)+(n-2)+.+2+1=n(n-1)/2。4（2）堆排序法，最壞情況需要O(nlog2n)次比較。堆排序的空間復(fù)雜度為O(1)；時間復(fù)雜度在最好情況為O(nlog2n)，平均情況為O

32、(nlog2n)，最壞情況為O(nlog2n)5在插入選擇排序中，若初始數(shù)據(jù)基本正序， 則選用插入排序；若初始數(shù)據(jù)基本反序，則選用選擇排序。因為插入排序在初始數(shù)據(jù)基本正序時時間復(fù)雜度為O(n)，而選擇排序在初始數(shù)據(jù)基本反序時時間復(fù)雜度為O(n)6插入排序的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。7例：設(shè)關(guān)鍵碼序列（16，9，4，25，15，2，13，18，17，5，8，24），要按關(guān)

33、鍵碼值遞增的次序排列，采用簡單選擇排序法，一趟掃描后的結(jié)果是2，9，4，25，15，16，13，18，17，5，8，24（簡單選擇排序法的思想是：以無序表的第一個元素作為比較標(biāo)準(zhǔn)，依次同后面的元素進(jìn)行比較，如果有一個元素比第一個元素小則記錄這個元素的下標(biāo)，然后以新的最小元素繼續(xù)往下比較，有更小的元素再記錄該下標(biāo)，再比較.，當(dāng)對整個數(shù)組掃描一趟后就可以等到最小元素的下標(biāo)，然后與無序表的第一個元素交換位置。本題很明顯第一趟掃描結(jié)果最小元素是2，與第一個元素交換位置后得到2，9，4，25，15，16，13，18，17，5，8，24選項的結(jié)果。）8簡單插入排序的過程是，每一趟將一個待排序的記錄，按其關(guān)

34、鍵字的大小插入到已經(jīng)排序的子文件中適當(dāng)位置上，直到全部記錄插入完成為止。當(dāng)文件“局部有序”或文件長度較小的情況下，每趟的比較次數(shù)大為降低，也即n-1趟比較的時間復(fù)雜度由O(n2)降至O(n)。所以最佳內(nèi)排序方法是它9在簡單插入排序過程中，當(dāng)待排序列中記錄按關(guān)鍵字非遞減有序排序時，所需進(jìn)行關(guān)鍵字比較的次數(shù)最小，為n-1，即記錄不需移動；反之，當(dāng)待排序列中記錄按關(guān)鍵字非遞增有序排序時，總的比較次數(shù)達(dá)到最大值(n+2)(n-1)/2。由（A：94，32，40，90，80，46，21，69）、（B：21，32，46，40，80，69，90，94）、（C：32，40，21，46，69，94，90，80）

35、、（D：90，69，80，46，21，32，94，40）四個答案中知（B）選項已經(jīng)基本有序，需要比較的次數(shù)最少。10例：在對一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較3次（當(dāng)要插入60時，前6個元素已有序，即為：15，23，38，54，72，96，需從后向前比較到54為止，故要比較3次）11插入排序是將待排序的記錄插入到前面已排好序的子文件中，即考慮已排好序的子文件。所以是在待排序的元素序列基本有序的前提下，效率最高的排序方法12在堆排序和快速排序中，當(dāng)原始記錄接近正序或反序時，則選用堆排序，若原始

36、記錄無序，則使用快速排序。13快速排序基本思想是：任取待排序表中的某個元素作為基準(zhǔn)（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子表的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個子表繼續(xù)進(jìn)行排序，直至整個表有序。只有左子表排好序，右子表還沒排好序；左子表的長度在排序過程中可能大于、等于或小于右子表的長度；14由于選擇排序每趟從待排序的記錄中選中關(guān)鍵字最小的記錄，每個記錄都要比較，不考慮已排好序的子文件，因此，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)?？焖倥判虿豢紤]已排好序的子記錄，15例：設(shè)有1000個無序的元素，希望用最快的

37、速度挑選出其中前10個最大的元素，由于堆排序每掃描一趟就排好一個記錄，只挑選出其中的前10個最大的元素時，使用堆排序為好。16希爾排序的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進(jìn)行直接插入排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進(jìn)行一次直接插入排序。17簡單選擇排序每趟從n-i+1個記錄中選取關(guān)鍵字最小的記錄，其時間復(fù)雜度為O(n)。18例：已知序列，請給出采用插入排序法對該序列作升序排序時的第五趟結(jié)果是(10,32,65,70,83,100),7,9或10,32,65,70,83,100,7,919 在插入排序、希爾排序、

38、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是快速排序，需要內(nèi)存容量最多的是基數(shù)排序 第二章程序設(shè)計基礎(chǔ)21 程序設(shè)計設(shè)計方法和風(fēng)格如何形成良好的程序設(shè)計風(fēng)格1、源程序文檔化； 2、數(shù)據(jù)說明的方法； 3、語句的結(jié)構(gòu)； 4、輸入和輸出。1程序設(shè)計的風(fēng)格總體而言應(yīng)該強調(diào)簡單和清晰，程序必須是可以理解的2注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二（已成為當(dāng)今主導(dǎo)的程序設(shè)計風(fēng)格）。3編制程序在選擇標(biāo)識符的名字時應(yīng)考慮選擇含義明確的名字，以正確提示所代表的實體。4編制程序在書寫功能性注解時應(yīng)考慮為程序段作注解，以幫助讀者理解程序。5程序設(shè)計中語句結(jié)構(gòu)的要求：（1

39、）在一行內(nèi)只寫一條語句；（2）程序編寫應(yīng)優(yōu)先考慮清晰性，程序編寫要做到清晰第一、效率第二；（3）在保證程序正確的基礎(chǔ)上再要求提高效率；（4）避免使用臨時變量而使程序的可讀性下降；避免不必要的轉(zhuǎn)移；6程序的語句結(jié)構(gòu)要從數(shù)據(jù)出發(fā)構(gòu)造程序，利用信息隱蔽確保每一個模塊的獨立性。7序言性注釋通常位于每個程序的開頭部分，它給出程序的整體說明，主要描述內(nèi)容可以包括：程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期、修改日期等。不包括數(shù)據(jù)的狀態(tài)8功能性注釋的位置一般嵌在源程序體之中，主要描述其后的語句或者程序做什么。包括數(shù)據(jù)的狀態(tài)，語句的功能，程序段的功能，不包括模

40、塊的功能9源程序的文檔化應(yīng)考慮如下幾點：（1）符號名的命名：符號名的命名應(yīng)具有一定的實際含義，以便于對程序功能的理解。（2）程序注釋：正確的注釋能夠幫助讀者理解程序，注釋一般分為序言性注釋和功能性注釋。（3）視覺組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦２话ㄕ_的文檔格式10程序設(shè)計方法和技術(shù)的發(fā)展經(jīng)過了結(jié)構(gòu)化程序設(shè)計、面向?qū)ο蟮某绦蛟O(shè)計兩個階段 11程序文檔化應(yīng)注意以下幾點：（1）符號名的命名。符號名的命名具有一定的實際含義，以便于對程序功能的理解；（2）程序注釋。正確的注釋可以幫助讀者理解程序； 12輸入和輸出信息是用戶直接關(guān)心的。輸入、輸出方式

41、和格式，應(yīng)盡可能方便用戶的使用， 在設(shè)計和編程時，對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性13影響輸入輸出風(fēng)格的因素包括通信環(huán)境，用戶經(jīng)驗，輸入/輸出設(shè)備，不包括數(shù)據(jù)狀態(tài)。22 結(jié)構(gòu)化程序設(shè)計1結(jié)構(gòu)化程序設(shè)計方法的四條原則是：1. 自頂向下；2. 逐步求精；3.模塊化；4.限制使用goto語句。2結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：（1）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)；順序結(jié)構(gòu)是順序執(zhí)行的結(jié)構(gòu)，就是按照語句的自然順序，一條一條地執(zhí)行程序（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列； （3）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根

42、據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。3在程序設(shè)計中，重復(fù)結(jié)構(gòu)對應(yīng)兩類循環(huán)語句：（1）對先判斷后執(zhí)行循環(huán)體的稱為當(dāng)型循環(huán)結(jié)構(gòu)；（2）對先執(zhí)行循環(huán)體后判斷的稱為直到型循環(huán)語句。4結(jié)構(gòu)化程序設(shè)計方法是程序設(shè)計的先進(jìn)方法工具。采用結(jié)構(gòu)化程序設(shè)計方法編寫程序，可使程序結(jié)構(gòu)良好、易讀（主要強調(diào)程序的易讀性）、易理解、易維護(hù)。其中最關(guān)鍵的是提高程序清晰性。5結(jié)構(gòu)化程序設(shè)計的主要特點是程序語句組成容易識別的模塊，每塊只有一個入口和一個出口。620世紀(jì)70年代提出了“結(jié)構(gòu)化程序設(shè)計（structured programming）”的思想和方法。7結(jié)構(gòu)化程序設(shè)計是一種面向過程的設(shè)計方法。8結(jié)構(gòu)化程序設(shè)

43、計減少了程序出錯的機會、提高了程序的可靠性、保證了程序的質(zhì)量。9結(jié)構(gòu)化程序設(shè)計具有方便理解和閱讀、便于維護(hù)、便于修改等優(yōu)點。沒有移植性好10將現(xiàn)實生活中的實體抽象成類是面向?qū)ο蟪绦蛟O(shè)計方法考慮的問題。11結(jié)構(gòu)化程序是由一些為數(shù)不多的基本結(jié)構(gòu)模塊組成，這些模塊甚至可以由機器自動生成，從而極大地減輕了編程工作量23 面向?qū)ο蟮某绦蛟O(shè)計1對象是現(xiàn)實世界中一個實際存在的事物，它可以是有形的也可以是無形的，如狗，桌子，飛機是對象，而蘋果的顏色不是對象。2屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。4類是指具有共同屬性、共同方法的對象的集合（即一組具在相同的數(shù)據(jù)結(jié)構(gòu)和相同的行為

44、特征的對象的集合）。包括屬性和行為兩部分。所以類是對象的抽象，對象是對應(yīng)類的一個實例。5多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。6面向?qū)ο蠹夹g(shù)具有多態(tài)性、封裝性和繼承性。7在面向?qū)ο蠓椒ㄖ校粋€對象請求另一對象為其服務(wù)的方式是通過發(fā)送消息8繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征，但不是任何對象都必須有繼承性。9在面向?qū)ο蟮某绦蛟O(shè)計中，各個對象之間相對獨立，相互依賴性小。10繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)作基類來引用，則新類相應(yīng)地可當(dāng)作派生類來引用。 是類之間共享懺悔和操作的機制。 3對象具有如下的基本特點：（1）標(biāo)識唯一性。對象是可區(qū)分的，

45、并且由對象的內(nèi)在本質(zhì)來區(qū)分。（2）分類性?？梢詫⒕哂邢嗤瑢傩院筒僮鞯膶ο蟪橄蟪深悾唬?）多態(tài)性。同一個操作可以是不同對象的行為。（4）封裝性。只能看到對象的外部特征，無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法。（5）模塊獨立性。面向?qū)ο笫怯蓴?shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體。 第三章軟件工程基礎(chǔ)31 軟件工程基本概念1計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。2軟件是一種邏輯實體（邏輯產(chǎn)品）；3軟件按功能分為（文檔）應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。4軟件工程包括3個要素：方法、工具和過程。5軟件工程過程包含4種基本活動：（1）P-軟件規(guī)格說明；（2）D-軟件開發(fā)；（3

46、）C-軟件確認(rèn)；（4）A-軟件演進(jìn)。6軟件生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的過程。7軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行維護(hù)，主要活動階段是：（問題定義）（1）可行性研究與計劃制定；（2）需求分析；（3）軟件設(shè)計；（4）軟件實現(xiàn)（編碼）；（5）軟件測試；（6）運行和維護(hù)。8軟件工程的目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。9軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。10軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件工具的集合11軟

47、件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。12在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是需求分析13軟件交付使用后，需要不斷地進(jìn)行維護(hù)，根據(jù)新提出的需求進(jìn)行必要而且可能的擴(kuò)充和刪除。14需求分析主要工作包括4個方面：需求獲取、需求分析、編寫說明書、需求評審。15SRS是軟件需求規(guī)格說明書的英文簡稱。32 結(jié)構(gòu)化分析方法1數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心2在結(jié)構(gòu)化分析方法中，用于描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件的文檔稱為數(shù)據(jù)字典3結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主

48、要工具,建立系統(tǒng)的邏輯模型。4Jackson方法是一種面向數(shù)據(jù)流的結(jié)構(gòu)化方法5結(jié)構(gòu)化分析的常用工具（1）數(shù)據(jù)流圖；（2）數(shù)據(jù)字典；（3）判定樹；（4）判定表。6數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。7數(shù)據(jù)流圖由一些特定的圖符構(gòu)成，包括：加工（轉(zhuǎn)換）、數(shù)據(jù)流、存儲文件（數(shù)據(jù)源）、源和潭，不包括控制流。8程序流程圖（PFD）中的箭頭代表的是控制流。9常見的需求分析方法有：結(jié)構(gòu)化分析方法和面向?qū)ο蟮姆治龇椒ǎ∣OA）。結(jié)構(gòu)化分析方法中，數(shù)據(jù)流圖（DFD）是需求分析最常用的工具。在數(shù)據(jù)流圖（DFD）中，帶有名字的箭頭表示數(shù)據(jù)的流向。10數(shù)據(jù)字典的作用

49、是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。11判定表4部分組成：左上部是基本條件、左下部是基本動作、右上部是條件項、右下部是動作項。33 結(jié)構(gòu)化設(shè)計方法1合性與內(nèi)聚性是模塊獨立性的兩個定性標(biāo)準(zhǔn)，其中內(nèi)聚反映了模塊內(nèi)各萬分之間的聯(lián)系在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。依據(jù)降低耦合提高內(nèi)聚的原則，通過把一些模塊取消或合并來來修改程序結(jié)構(gòu)2軟件概要設(shè)計的基本任務(wù)是：（1）設(shè)計軟件系統(tǒng)結(jié)構(gòu)； （2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計；（3）編寫概要設(shè)計文檔； （4）概要設(shè)計文檔評審。模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。 在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過

50、程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)。3典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。4變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。5在結(jié)構(gòu)化設(shè)計方法中生成的結(jié)構(gòu)圖（SD）中，帶有箭頭的連線表示模塊之間的調(diào)用關(guān)系6常見設(shè)計工具.N-S的重要特征是：每個構(gòu)件具有明確的作用域；控制轉(zhuǎn)移必須遵守結(jié)構(gòu)化設(shè)計要求；易于確定局部數(shù)據(jù)和（或）全局?jǐn)?shù)據(jù)的作用域；易于表達(dá)嵌套關(guān)系和模塊的層次結(jié)構(gòu)。7PAD有5種結(jié)構(gòu)，通常把程序流程圖的5種基本控制結(jié)構(gòu)組合或嵌套，可以構(gòu)成任何復(fù)雜的程序流程圖。8常見設(shè)計工具：圖形工具（程序流程圖，N-S，PAD，HIPO），表格

51、工具（判定表），語言工具（PDL）。9程序流程圖構(gòu)成的控制結(jié)構(gòu)的含義如下：（1）順序型：幾個連續(xù)的加工步驟依次排列構(gòu)成；（2）選擇型：由某個邏輯判斷式的取值決定選擇兩個加工中的一個；（3）先判斷重復(fù)型：先判斷條件是否成立，成立則執(zhí)行循環(huán)體語句；（4）后判斷重復(fù)型：重復(fù)執(zhí)行某些特定的加工，直到控制條件成立；（5）多分支選擇型：列舉多種加工情況，根據(jù)控制變量的取值，選擇執(zhí)行其中之一。10模塊化是指把一個待開發(fā)的軟件分解成若干小的簡單的部分11問題分析圖是繼程序流程圖和方框圖之后，提出的又一種用于描述軟件詳細(xì)設(shè)計的圖形表示工具34 軟件測試1軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。（盡可能多地發(fā)現(xiàn)

52、軟件系統(tǒng)中的錯誤和缺陷）2經(jīng)驗表明，程序中存在錯誤的概率與該程序中已發(fā)現(xiàn)的錯誤數(shù)成正比。3從功能角度劃分，試軟件測試方法：靜態(tài)測試和動態(tài)測試。4靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進(jìn)行（人工檢測）。5動態(tài)測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法（從功能角度劃分）。6動態(tài)測試（動態(tài)分析）是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。7白盒測試：在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作的驗證。主要方法有邏輯覆蓋、基本路徑測試。8黑盒測試：用于軟件確認(rèn)。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。黑盒測試方法也稱功能

53、測試或數(shù)據(jù)驅(qū)動測試，是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進(jìn)行測試和驗證9軟件測試過程一般按4個步驟進(jìn)行：單元測試、集成測試、驗收測試（確認(rèn)測試）和系統(tǒng)測試。10單元測試的技術(shù)可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒動態(tài)測試為主，輔之以黑盒測試。11集成測試所設(shè)計的內(nèi)容包括：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入的測試等12檢查軟件產(chǎn)品是否符合需求定義的過程稱為確認(rèn)測試13系統(tǒng)測試必須在目標(biāo)環(huán)境下運行，14白盒測試主要考慮程序內(nèi)部的邏輯結(jié)構(gòu)，主要用于完成軟件內(nèi)部操作的驗證。黑盒測試方法完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否符

54、合它的功能說明。15集成測試時要進(jìn)行軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件測試和非法輸入的測試等16測試準(zhǔn)則：（1）所有測試都應(yīng)追溯到需求；（2）嚴(yán)格執(zhí)行測試計劃，排除測試的隨意性；（3）充分注意測試中的群體現(xiàn)象；（4）程序員應(yīng)避免檢查自己的程序；（5）窮舉測試不可能；（6）妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告，為維護(hù)提供方便。17系統(tǒng)測試的目的是在真實的系統(tǒng)工作環(huán)境下，檢驗軟件是否能與系統(tǒng)正確連接，發(fā)現(xiàn)軟件與系統(tǒng)需求不一致的地方。包括：功能測試、性能測試、操作測試、配置測試、外部接口測試和安全測試等。18軟件測試是保證軟件質(zhì)量的重要手段，包括需求定義階段的需求測試、編碼

55、階段的單元測試、集成測試以及后期的確認(rèn)測試和系統(tǒng)測試。19代碼檢查，包括代碼審查、代碼走查、桌面檢查、靜態(tài)分析等具體方式。35 程序的調(diào)試1程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進(jìn)行。的關(guān)鍵是推斷程序內(nèi)部的錯誤位置及原因2程序調(diào)試的基本步驟：（1）錯誤定位；（2）修改設(shè)計和代碼，以排除錯誤；（3）進(jìn)行回歸測試，防止引進(jìn)新的錯誤。3軟件調(diào)試可分表靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：（1）強行排錯法；其過程可概括為設(shè)置斷點、程序暫停、觀察程序狀態(tài)、繼續(xù)運行程序。1）通過內(nèi)存全部打印來排錯

56、；2）在程序特定部位設(shè)置打印語句-即斷點法；3）自動調(diào)試工具。（2）回溯法；（3）原因排除法。原因排除法是通過演繹和歸納，以及二分法來實現(xiàn)4修改錯誤原則：（1）在出現(xiàn)錯誤的地方，很可能有別的錯誤；（2）修改錯誤的一個常見失誤是修改了這個錯誤的征兆或這個錯誤的表現(xiàn)，而沒有修改錯誤本身；（3）注意修正一個錯誤的同時有可能會引入新的錯誤；（4）修改錯誤的過程將迫使人們暫時回到程序設(shè)計階段；（5）修改源代碼程序，不要改變目標(biāo)代碼。5為了修改程序中錯誤，往往采用“補丁程序”來實現(xiàn)，但這種做法會引起整體程序質(zhì)量的下降。6確定錯誤位置占據(jù)了軟件調(diào)試絕大部分的工作量。7測試的目的是暴露錯誤，評價程序的可靠性，而調(diào)試的目的是發(fā)現(xiàn)錯誤的位置并改正錯誤8經(jīng)驗表明，錯誤有群集現(xiàn)象，當(dāng)在某一程序段發(fā)現(xiàn)錯誤時，在該程序段中還存在別的錯誤9程序調(diào)試活動由兩部分組成，一是根據(jù)錯誤的跡象確定程序中錯誤的確切性質(zhì)、原因和位置；二是對程序進(jìn)行修改，排除這個錯誤。目的是改正錯誤第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)41 數(shù)據(jù)庫系統(tǒng)的基本概念1數(shù)據(jù)管理技術(shù)的發(fā)展過程中，