全國計算機等級考試二級公共基礎知識總結

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

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

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

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

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

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

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

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

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

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

11、，P2，P3，。，Pn，若P1=n，則Pi為n-i+1當p1=n，即n是最先出棧的，根據棧的運算原理，n必定是最后入棧的，那么輸入順序必定是1,2,3,.,n,則出棧的序列是n,n-1,n-2,.,113設初始輸入序列為1，2，3，4，5，利用一個棧產生輸出序列，下列B序列是不可能通過棧產生的由于棧的壓入和退出只能在棧頂進行，所以要使出棧的第一個數是序列的最后一個數5，只能先把序列所有元素都壓入棧，但這時出棧序列只能是（A 5，4，3，2，1），所以（B 5，3，4，1，2）選項的出棧序列是錯誤的，應選（B）。當初始序列壓入一個時，就退出一個元素，這樣就得到（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數據結構分為邏輯結構與存儲結構，線性鏈表屬于存儲結構。2數據結構中的每一個結點對應于一個存儲單元，這種存儲單元（一個一個小塊）稱為存儲結點，簡稱結點。3結點由兩部分組成：（1）用于存儲數據元素值，稱為數據域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結點。 4在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續(xù)，各數據結點的存儲順序與數據元素之間的邏

13、輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。因此，鏈式存儲結構是散列存儲5帶頭結點的雙向循環(huán)鏈表L為空的條件是：只有該頭結點，即L->next=L 或者 L->prior=L6對于鏈式隊列結構，插入元素是在隊尾進行的，只需修改隊尾指針，不需修改隊頭指針。向鏈式隊列中插入一個結點就是在單鏈表表尾插入一個結點，同時新插入的結點成為表尾結點。例：在一個鏈式隊列中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算是r->next=s;r=s;7向鏈式棧中插入一個結點，就是在單鏈表的表頭插入一個結點，同時將新結點的位置賦予棧頂指針。例：向一個棧頂指針為HS的鏈式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、35，47，50，62，83，90，115，134），當用二分法查找100時，需進行3次比較可確定成功（畫出二叉樹判定樹，當查找100時，需要和50、90、110比較，由于110的左子樹為空，查找結束，比較了3次。）12如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用分塊查找方法13順序查找法查找長度為n的線性表時，每個元素的平均查找長度為(n+1)/2。18 排序技術排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。1交換類排序法：（1）冒泡排序法，需要比較的次數（在最壞情況下的時間復雜度）為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次，依次類推，倒數第二個元素只須比較1次即可，所以總的比較次數為：(n-1)+(n-2)+.+2+1=n(n-1)/2。4（2）堆排序法，最壞情況需要O(nlog2n)次比較。堆排序的空間復雜度為O(1)；時間復雜度在最好情況為O(nlog2n)，平均情況為O

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

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

34、鍵字的大小插入到已經排序的子文件中適當位置上，直到全部記錄插入完成為止。當文件“局部有序”或文件長度較小的情況下，每趟的比較次數大為降低，也即n-1趟比較的時間復雜度由O(n2)降至O(n)。所以最佳內排序方法是它9在簡單插入排序過程中，當待排序列中記錄按關鍵字非遞減有序排序時，所需進行關鍵字比較的次數最小，為n-1，即記錄不需移動；反之，當待排序列中記錄按關鍵字非遞增有序排序時，總的比較次數達到最大值(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）選項已經基本有序，需要比較的次數最少。10例：在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較3次（當要插入60時，前6個元素已有序，即為：15，23，38，54，72，96，需從后向前比較到54為止，故要比較3次）11插入排序是將待排序的記錄插入到前面已排好序的子文件中，即考慮已排好序的子文件。所以是在待排序的元素序列基本有序的前提下，效率最高的排序方法12在堆排序和快速排序中，當原始記錄接近正序或反序時，則選用堆排序，若原始

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

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

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

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

40、塊的功能9源程序的文檔化應考慮如下幾點：（1）符號名的命名：符號名的命名應具有一定的實際含義，以便于對程序功能的理解。（2）程序注釋：正確的注釋能夠幫助讀者理解程序，注釋一般分為序言性注釋和功能性注釋。（3）視覺組織：為使程序的結構一目了然，可以在程序中利用空格、空行、縮進等技巧使程序層次清晰。不包括正確的文檔格式10程序設計方法和技術的發(fā)展經過了結構化程序設計、面向對象的程序設計兩個階段 11程序文檔化應注意以下幾點：（1）符號名的命名。符號名的命名具有一定的實際含義，以便于對程序功能的理解；（2）程序注釋。正確的注釋可以幫助讀者理解程序； 12輸入和輸出信息是用戶直接關心的。輸入、輸出方式

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

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

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

44、特征的對象的集合）。包括屬性和行為兩部分。所以類是對象的抽象，對象是對應類的一個實例。5多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現象。6面向對象技術具有多態(tài)性、封裝性和繼承性。7在面向對象方法中，一個對象請求另一對象為其服務的方式是通過發(fā)送消息8繼承是面向對象的方法的一個主要特征，但不是任何對象都必須有繼承性。9在面向對象的程序設計中，各個對象之間相對獨立，相互依賴性小。10繼承是使用已有的類定義作為基礎建立新類的定義技術。已有的類可當作基類來引用，則新類相應地可當作派生類來引用。 是類之間共享懺悔和操作的機制。 3對象具有如下的基本特點：（1）標識唯一性。對象是可區(qū)分的，

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

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

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

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

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

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

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

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

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

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

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

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