當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

软件设计师知识体系归纳总结

發布時間：2023/12/20 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了软件设计师知识体系归纳总结小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

軟件設計師知識體系歸納總結

歷年考點

上午題

下午題

第一章計算機組成原理及體系結構

1.數據的表示

1.1進制轉換

(1) R進制轉十進制

(2) 十進制轉R進制

(3) 二進制八進制十六進制的轉換

2.原碼反碼補碼移碼

2.1相互關系

原碼->反碼->補碼->移碼

原碼:原碼就是符號位加上真值的絕對值, 即用第一位表示符號, 其余位表示值.

第一位是符號位. 因為第一位是符號位, 所以8位二進制數的取值范圍就是:

[1111 1111 , 0111 1111]

反碼:正數的反碼是其本身,負數的反碼是在其原碼的基礎上, 符號位不變，其余各個位取反.

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

補碼:正數的補碼就是其本身,負數的補碼是在其原碼的基礎上, 符號位不變, 其余各位取反, 最后+1. (即在反碼的基礎上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]補

[-1] = [10000001]原 = [11111110]反 = [11111111]補

移碼：不管正負數，只要將其補碼的符號位取反即可。

例如：X=-101011 , [X]原= 10101011 ，[X]反=11010100，[X]補=11010101，[X]移=01010101

2.2表示范圍

3.浮點數運算(小階向大階看齊,尾數向右移n位)

（1）對階
首先計算兩個數的指數差，把指數小的向指數大的對齊，并將尾數右移指數差的位數，這樣兩個浮點數就完成了對階的操作。可以看出，對階的過程可能使得指數小的浮點數失去一些有效位。
如果兩個浮點數階數相差很大，大于指數小的浮點數的尾數寬度，那么對階后那個浮點數的尾數就變成了0，即當做機器零處理了。

（2）尾數計算
對階完成后，兩個浮點數尾數就如同定點數，計算過程同定點數計算。

（3）結果格式化
尾數計算后，可能會產生溢出，此時將尾數右移，同時指數加1，如果指數加1后發生了溢出，則表示兩個浮點數的運算發生了溢出。
如果尾數計算沒有溢出，則尾數不斷左移，同時指數減1，直到尾數為格式化數。如果這個過程中，指數小于機器能表達的最小數，則將結果置“機器零”，這種情況稱為下溢。

4.校驗碼

為了實現數據的自動檢錯與糾錯，引入了校驗碼。而最簡單的就是奇偶校驗碼，它分為奇校驗和偶校驗兩種，均是添加1位校驗位，根據信息碼中1的個數來決定校驗位的取值，使得填入校驗位后，使得1的個數為奇數（奇校驗）或偶數（偶校驗)。

1.海明碼(可檢錯可糾錯)

對于信息位為m的原始數據，需加入k位的校驗碼，它滿足m+k+1<2

要能夠糾正n位錯誤，則所需最小的碼距應該是“2n+1

根據海明的研究發現，可以發現“≤碼距-1”位的錯誤

2.CRC校驗碼(可檢錯不可糾錯)

要計算CRC校驗碼，需根據CRC生成多項式進行。例如：原始報文為“11001010101”，其生成多項式為：“x4+x3+x+1”。在計算時，是在原始報文的后面若干個0（等于校驗碼的位數，而生成多項式的最高冪次就是校驗位的位數，即使用該生成多項式產生的校驗碼為4位）作為被除數，除以生成多項式所對應的二進制數（根據其冪次的值決定，得到11011，因為生成多項式中除了沒有x2之外，其他位都有）。然后使用模2除，得到的商就是校驗碼。

5.計算機的硬件組成

其中運算器和控制器組成中央處理器（CPU）。

運算器負責完成算術、邏輯運算功能，通常由ALU（算術/邏輯單元）、寄存器、多路轉換器、數據總線組成。

控制器則負責依次訪問程序指令，進行指令譯碼，并協調其他設備，通常由程序計數器（PC）、指令寄存器、指令譯碼器、狀態/條件寄存器、時序發生器、微操作信號發生器組成。

幾個主要部件的功能：

程序計數器：用于存放下一條指令所在單元的地址的地方。由于大多數指令都是按順序來執行的，所以修改的過程通常只是簡單的對PC加1。當遇到轉移指令時，后繼指令的地址（即PC的內容）必須從指令寄存器中的地址字段取得。在這種情況下，下一條從內存取出的指令將由轉移指令來規定，而不像通常一樣按順序來取得。因此程序計數器的結構是具有寄存信息和計數兩種功能的結構。

指令寄存器：用來保存當前正在執行的一條指令。當執行一條指令時，先把它從內存取到數據寄存器中，然后再傳送至指令寄存器。指令劃分為操作碼和地址碼字段，由二進制數字組成。為了執行任何給定的指令，必須對操作碼進行測試，以便識別所要求的操作。

指令譯碼器：譯碼是編碼的逆過程，在編碼時，每一種二進制代碼，都賦予了特定的含義，即都表示了一個確定的信號或者對象。把代碼狀態的特定含義“翻譯”出來的過程叫做譯碼，實現譯碼操作的電路稱為譯碼器。或者說，譯碼器是可以將輸入二進制代碼的狀態翻譯成輸出信號，以表示其原來含義的電路。

5.1計算機體系結構分類(Flynn分類法)

6.指令集(復雜指令集和精簡指令集)

7.流水線技術(計算指令執行的總時間,平均時間,計算機運行速度)

7.1基本概念

流水線是指在程序執行時多條指令重疊進行操作的一種準并行處理實現技術。各種部件同時處理是針對不同指令而言的，它們可同時為多條指令的不同部分進行工作，以提高各部件的利用率和指令的平均執行速度。指令流水線是將指令執行分成幾個子過程，每一個子過程對應一個工位，我們稱為流水級或流水節拍，這個工位在計算機里就是可以重疊工作的功能部件，稱為流水部件。

流水線要求所有的流水級部件必須在相同的時間內完成各自的子過程。在流水線中，指令流動一步便是一個機器周期，機器周期的長度必須由最慢的流水級部件處理子過程所需的時間來決定。

計算流水線執行時間

7.2計算流水線執行時間

假定有某種類型的任務，共可分成N個子任務，執行每個子任務需要時間t，則完成該任務所需的時間即為Nt。若以傳統的方式，則完成k個任務所需的時間是kNt；而使用流水線技術執行，花費的時間是Nt+(k-1)t。也就是說，除了第一個任務需要完整的時間外，其他都通過并行，節省下了大量的時間，只需一個子任務的單位時間就夠了。

另外要注意的是，如果每個子任務所需的時間不同，則其速度取決于其執行順序中最慢的那個（也就是流水線周期值等于最慢的那個指令周期），要根據實際情況進行調整。

7.3 流水線吞吐率計算

7.4 流水線加速比

7.5 流水線的效率

8.Cache

8.1基本概念

由于在CPU與存儲系統間存在著數據傳送帶寬的限制，因此在其中設置了Cache（高速緩沖存
儲器，通常速度比內存快），以提高整體效率。但由于其成本更高，因此Cache的容量要比內存小
得多。Cache是一種相聯存儲器（即按內容進行存儲的存儲器）。

8.2原理命中率失效率

使用Cache改善系統性能的主要依據是程序的局部性原理。通俗地說，就是一段時間內，執行的語句常集中于某個局部。而Cache正式將訪問集中的內容放在速度更快的Cache上，以提高性能。
引入Cache后，CPU在需要數據時，先找Cache，如果沒有再找內存。
如果Cache的訪問命中率為h（通常1-h就是Cache的失效率），而Cache的訪問周期時間是t1，主存儲器的訪問周期時間是t2，則整個系統的平均訪存時間就應該是：t3 = h * t1+(1-h) * t2

8.3Cache映射

CPU發生訪存請求時，會先讓Cache判斷是否包括，如果命中（即包括請求的內容）就直接使用。

直接映射：是一種多對一的映射關系，但一個主存塊只能夠復制到Cache的一個特定位置上去。Cache的行號i和主存的塊號j有函數關系：i=j%m（其中m為Cache總行數)。

相聯映射：將主存中一個塊的地址與塊的內容一起存于Cache的行中。速度更快，但控制復雜。

組相聯映射：是前兩種方式的折中方案。它將Cache中的塊再分成組。然后通過直接映射方式決定組號，再通過相聯映射的方式決定Cache中的塊號。

8.4Cache淘汰算法

當Cache數據已滿，并且出現未命中情況時，就是淘汰一些老的數據，更新一些新的數據。而選擇淘汰什么數據的方法就是淘汰算法，常見的方法有三種：隨機淘汰、先進先出（FIFO）淘汰（淘汰最早調入Cache的數據）、最近最少使用（LRU）淘汰法。其中平均命中率最高的是LRU算法。

8.5Cache存儲器的寫操作

在使用Cache時，需要保證其數據與主存一致，因此在寫Cache時就需要考慮與主存間的同步問題，通常使用以下三種方法：寫直達（寫Cache時，同時寫主存）、寫回（寫Cache時不馬上寫主存，而是等其淘汰時回寫）、標記法。

9.主存

9.1主存儲器的種類

RAM：隨機存儲器，可讀寫，斷電后數據無法保存，只能暫存數據。
SRAM：靜態隨機存儲器，在不斷電時信息能夠一直保持。
DRAM：動態隨機存儲器，需要定時刷新以維持信息不丟失。
ROM：只讀存儲器，出廠前用掩膜技術寫入，常用于存放BIOS和微程序控制。
PROM：可編程ROM，只能夠一次寫入，需用特殊電子設備進行寫入。
EPROM：可擦除的PROM，用紫外線照射15～20分鐘可擦去所有信息，可寫入多次。
E2PROM：電可擦除ERPOM，可以寫入，但速度慢。
閃速存儲器：現在U盤使用的種類，可以快速寫入。

記憶時，抓住幾個關鍵英文字母。A，即Access，說明讀寫都行；O，即Only，說明只讀；P，即Programmable，說明可通過特殊電子設備寫入；E，即Erasable，說明可擦寫；E平方說明是兩個E，第二個E是電子。

9.2主存儲器的組成

實際的存儲器總是由一片或多片存儲器配以控制電路構成的（如圖1-7所示）。其容量為W×B，W是存儲單元（word，即字）的數量，B表示每個word由多少bit（位）組成。如果某一芯片規格為w×b，則組成W×B的存儲器需要用（W/w）×（B/b）個芯片。

9.3主存儲器的地址編碼

主存儲器（內存）采用的是隨機存取方式，需對每個數據塊進行編碼，而在主存儲器中數據塊是以word來標識的，即每個字一個地址，通常采用的是16進制表示。例如，按字節編址，地址從A4000H到CBFFFH，則表示有(CBFFF-A4000)+1個字節，28000H個，也就是163840個字節，等于160KB。

要注意的是，編址的基礎可以是字節，也可以是字（字是由1個或多個字節組成的），要算地址位數，首先應計算要編址的字或字節數，然后求2的對數即可得到。

10.可靠性

10.1串聯系統

假設一個系統由n個子系統組成，當且僅當所有的子系統都能正常工作時，系統才能正常工作，這種系統稱為串聯系統，如圖所示。可靠性為R = R1 * R2 * … * Rn

10.2并聯系統

假如一個系統由n個子系統組成，只要有一個子系統能夠正常工作，系統就能正常工作.R = 1-(1-R1) * (1 - R2) * … * (1-Rn).

第二章操作系統知識

1.進程管理

1.1進程狀態轉換

1.2PV操作

P操作：也稱為down()、wait()操作，使S=S-1，若S<0，進程暫停執行，放入信號量的等待隊列。
V操作：也稱為up()、signal()操作，使S=S+1，若S≤0，喚醒等待隊列中的一個進程。

1.3死鎖問題

死鎖是指各并發進程彼此互相等待對方所擁有的資源，且這些并發進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發進程不能繼續向前推進的狀態。

四個必要條件：
（1）互斥條件：即一個資源每次只能被一個進程使用，在操作系統中這是真實存在的情況。
（2）保持和等待條件：有一個進程已獲得了一些資源，但因請求其他資源被阻塞時，對已獲得的資源保持不放。
（3）不剝奪條件：有些系統資源是不可剝奪的，當某個進程已獲得這種資源后，系統不能強行收回，只能由進程使用完時自己釋放。
（4）環路等待條件：若干個進程形成環形鏈，每個都占用對方要申請的下一個資源。

對待死鎖的策略主要有：

（1）死鎖的預防。不讓任一產生死鎖的必要條件發生就可以預防死鎖。
（2）死鎖的避免。這種策略不對用戶進程的推進順序加以限制，在進程申請資源時先判斷這次分配安全否，只有安全才實施分配，典型的算法是銀行家算法。
（3）死鎖的檢測。這種策略采用資源請求分配圖的化簡方法來判斷是否發生了不安全狀態。資源請求分配圖是一種有向圖，表示進程與資源之間的關系。死鎖的檢測是在需要的時刻執行的，當發現系統處于不安全狀態時，即執行死鎖的解除策略。
（4）死鎖的解除。解除死鎖的基本方法是剝奪。一種方法是把資源從一些進程處剝奪分給別的進程，被剝奪資源的進程則需回退到請求資源處重新等待執行；另一種方法是終止一個進程，剝奪其全部資源，以后再重新運行被終止的進程。

1.4銀行家算法

當某個進程提出申請時，必須判斷將資源分配給該進程后，會不會引起死鎖。若不會，則進行分配；否則就不分配。這樣做能保證在任何時刻至少有一個進程可以得到所需的全部資源而執行結束，并將歸還資源加入到系統的剩余資源中，這些資源又至少可以滿足一個進程的最大需求，于是保證所有進程都能在有限的時間內得到需求的全部資源。

2.存儲管理

1.三種虛擬存儲技術

2.頁面置換算法

由于實際主存是小于虛存的，因此可能會發生內存中已滿，但需要使用的頁不在主存中這一情況。這時就需要進行置換，即將一些主存中的頁淘汰到外存，騰出空間給要使用的頁，這個過程也稱為Swapping。其工作原理與Cache調入相類似。

最優算法（OPT）：淘汰不用的或最遠的將來才用的頁。這是一種理想算法，不可能實現，只是用來作為衡量算法效率的參照物。

隨機算法（RAND）：隨機淘汰。這種算法開銷小，但性能不穩定。

先進先出算法（FIFO）：選擇最早調入（也是駐留時間最長）的頁。

最近最少使用算法（LRU）：選擇離當前時刻最近的一段時間內使用得最少的頁。

3.磁盤調度算法

先來先服務（FCFS）：該算法根據進程請求訪問磁盤的先后次序進行調度。其優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優化，致使平均尋道時間可能較長。

最短尋道時間優先（SSTF）：該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調度算法卻不能保證平均尋道時間最短。

掃描算法（SCAN）：SCAN算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，SCAN算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。由于這種算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度算法。

循環掃描（CSCAN）算法：該算法規定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環，進行掃描。

3.設備管理

1．數據傳輸控制方式

程序控制方式：CPU直接利用I/O指令編程，實現數據的I/O。CPU發出I/O命令，命令中包含了外設的地址信息和所要執行的操作，相應的I/O系統執行該命令并設置狀態寄存器；CPU不停地（定期地）查詢I/O系統以確定該操作是否完成。由程序主動查詢外設，完成主機與外設間的數據傳送，方法簡單，硬件開銷小。

中斷方式：CPU利用中斷方式完成數據的I/O，當I/O系統與外設交換數據時，CPU無需等待也不必去查詢I/O的狀態，當I/O系統完成了數據傳輸后則以中斷信號通知CPU。CPU然后保存正在執行程序的現場，轉入I/O中斷服務程序完成與I/O系統的數據交換。然后返回原主程序繼續執行。與程序控制方式相比，中斷方式因為CPU無需等待而提高了效率。在系統中具有多個中斷源的情況下，常用的處理方法有：多中斷信號線法、中斷軟件查詢法、雛菊鏈法、總線仲裁法和中斷向量表法。

DMA方式：使用DMA控制器（DMAC）來控制和管理數據傳輸。DMAC和CPU共享系統總線，并且具有獨立訪問存儲器的能力。在進行DMA時CPU放棄對系統總線的控制而由DMAC控制總線；由DMAC提供存儲器地址及必須的讀寫控制信號，實現外設與存儲器之間進行數據交換。
DMAC獲取總線方式主要有三種，分別是暫停方式、周期竊取方式和共享方式。

通道：通道是一種通過執行通道程序管理I/O操作的控制器，它使主機與I/O操作之間達到更高的并行程度。在具有通道處理機的系統中，當用戶進程請求啟動外設時，由操作系統根據I/O要求構造通道程序和通道狀態字，將通道程序保存在主存中，并將通道程序的首地址放到通道地址字中，然后執行“啟動I/O”指令。按照所采取的傳送方式，可將通道分為字節多路通道、選擇通道和數組多路通道三種。

輸入輸出處理機（IOP）：也稱為外圍處理機（PPU），它是一個專用處理機，也可以是一個通用的處理機，具有豐富的指令系統和完善的中斷系統。專用于大型、高效的計算機系統處理外圍設備的I/O，并利用共享存儲器或其他共享手段與主機交換信息。從而使大型、高效的計算機系
統更加高效地工作。與通道相比，IOP具有比較豐富的指令系統，結構接近于一般的處理機，有自己的局部存儲器。

2．虛設備與SPOOLING技術

SPOOLING（Simultaneous Peripheral Operation On Line）的意思是外部設備同時聯機操作，又稱為假脫機輸入輸出操作，采用一組程序或進程模擬一臺I/O處理器。SPOOLING系統的組成,如圖所示。

4.文件管理

1.樹型目錄結構

2.位示圖

位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況，如圖2-12所示。當其值為“0”時，表示對應的盤塊空閑；為“1”時表示已分配。由所有盤塊對應的位構成一個集合，稱為位示圖。位示圖也可描述為一個二維數組map：Var map:array[1…m,1…n]of bit;

3.索引文件

索引文件是一種對文件存儲不連續分配的方法。為每個文件建立一張索引表，索引表中的每一表項指出文件信息所在的邏輯塊號和與之對應的物理塊號。

索引文件的優點是既適用于順序存取，又適用于隨機存取。缺點是索引表增加了存儲空間的開銷。另外，在存取文件時需要訪問兩次磁盤，一次是訪問索引表，另一次是根據索引表提供的物理塊號訪問文件信息。為了提高效率，一種改進的方法是，在對某個文件進行操作之前，預先把索引表調入內存。這樣，文件的存取就能直接從在內存的索引表中確定相應的物理塊號，從而只需要訪問一次磁盤。

第三章：程序語言和語言處理程序基礎知識

1.匯編、編譯、解釋系統基礎

1.解釋與編譯

解釋型：接受所輸入的用程序語言編寫的源程序，然后直接解釋執行；這類語言中的最典型代表是BASIC。

編譯型：它是將用某種程序語言編寫的源程序直接翻譯成為另一種語言（目標語言程序），而且兩者在邏輯上等價。如：C語言。

2.編譯過程

3.語言及文法的概念

喬姆斯基分類法

4.詞法分析

詞法分析是整個分析過程的一個子任務，它把構成源程序的字符串轉換成語義上關聯的單詞符號（包括關鍵字、標識符、常數、運算符和分界符等）的序列。詞法分析可以借助于有限自動機的理論與方法進行有效的處理。

4.1有限自動機

有限自動機是一種自動識別裝置，能夠準確地識別正規集。它與3型文法對應，可以分為確定的有限自動機和不確定的有限自動機兩種。

確定的有限自動機DFA

不確定的有限自動機NFA

NFA圖中一個狀態結點可能有一條以上的邊到達其它狀態結點

5.數據類型

要求源程序中的數據必須具有類型的目的主要有以下幾個方面：

第一是方便為數據合理分配存儲單元；第二是規定了數據類型，就知道了其占用的字節數，從而也就規定了數據對象的取值范圍及能夠進行的運算；第三是對參與表達式求值的數據對象可以進行合法性檢查，比如浮點數就不能進行自加操作。

6.表達式

前綴表達式(波蘭式) 中左右

中綴表達式左中右

后綴表達式(逆波蘭式) 左右中

7.程序調用的實現機制

第四章數據結構

1.數組

2.稀疏矩陣

3.線性表

線性結構是n個結點的有窮序列。通常表示為（a1，a2，…，an），a1稱為起始結點，an稱為結束結點，i稱為ai在線性表中的序號或位置，線性表所含結點的個數稱為線性表的長度，長度為0的線性表稱為空表。

線性表主要的存儲結構有兩種：順序存儲結構和鏈式存儲結構。采用順序存儲結構，就稱為順序表（常用數組實現）；采用鏈式存儲結構則稱為線性鏈表（即鏈表）。

順序表

順序存儲是最簡單的存儲方式，通常用一個數組，從數組的第一個元素開始，將線性表的結點依次存儲在數組中，即線性表的第i個結點存儲在數組的第i（0≤i≤n–1）個元素中，用數組元素的順序存儲來體現線性表中結點的先后次序關系。

鏈表

鏈表就是采用鏈式存儲實現的線性表。它是動態分配鏈表結點，通過鏈接指針，將各個節點按邏輯順序連接起來。根據其存儲結構的不同，可以分為單鏈表、循環鏈表和雙鏈表三種.

單鏈表

循環鏈表

循環鏈表與單鏈表的區別僅僅在于其尾結點的指針域值不是null，而是指向頭結點的指針。這樣做的好處是，從表中的任一結點出發都能夠通過后移操作掃描整個循環鏈表。

兩者的比較

4.隊列(先進先出)

隊列也是一種特殊的線性表，只允許在一端進行插入，另一端進行刪除運算。允許刪除運算的那一端稱為隊首，允許插入運算的一端稱為隊尾。稱隊列的結點插入為進隊，結點刪除為出隊。因最先進入隊列的結點將最先出隊，所以隊列具有先進先出的特征。實現隊列，可以使用順序存儲（如：數組方式）也可以用鏈表。

循環隊列

循環隊列就是將實現隊列的數組a[N]的第一個元素a[0]與最后一個元素a[N–1]連接起來。隊空的初態為 head=tail=0。在循環隊列中，當tail 趕上head時，隊列滿。反之，當head趕上tail時，隊列變為空。這樣隊空和隊滿的條件都同為head=tail，這會給程序判別隊空或隊滿帶來不便。因此，可采用當隊列只剩下一個空閑結點的空間時，就認為隊列已滿的簡單辦法，以區別隊空和隊滿。即隊空的判別條件是head=tail，隊滿的判別條件是head=tail+1。

試題

解析

5.棧(先進后出)

棧是另一種特殊的線性表，棧只允許在同一端進行插入和刪除運算。允許插入和刪除的一端稱為棧頂，另一端為棧底。稱棧的結點插入為進棧，結點刪除為出棧。因為最后進棧的結點必定最先出棧，所以棧具有后進先出的特征。

6.字符串

字符串是由某字符集上的字符所組成的任何有限字符序列。當一個字符串不包含任何字符時，稱它為空字符串。一個字符串所包含的有效字符個數稱為這個字符串的長度。一個字符串中任一連續的子序列稱為該字符串的子串。

字符串通常存于足夠大的字符數組中，每個字符串的最后一個有效字符之后有一個字符串結束標志，記為“\0”。通常由系統提供的庫函數形成的字符串的末尾會自動添加“\0”，但當由用戶的應用程序來形成字符串時，必須由程序自行負責在最后一個有效字符之后添加“\0”，以形成字符串。

7.樹

樹是一種典型的非線性數據結構，它能夠很好地應用于描述分支和層次特性的數據集合。樹是由一個或多個結點組成的有限集合T，它滿足以下兩個條件：
（1）有一個特定的結點，稱為根結點；
（2）其余的結點分成m（m≥0）個互不相交的有限集合。其中每個集合又都是一棵樹，稱T1,T2,…,Tm–1為根結點的子樹。

涉及到的概念

在用圖形表示的樹中，對兩個用線段連接的相關聯的結點而言，稱位于上端的結點是位于下端的結點的父結點或雙親結點，稱位于下端的結點是位于上端的結點的（孩）子結點，稱同一父結點的多個子結點為兄弟結點，稱處于同一層次上、不同父結點的子結點為堂兄弟結點。

定義一棵樹的根結點所在的層次為1，其他結點所在的層次等于它的父結點所在的層次加1。樹中各結點的層次的最大值稱為樹的層次。

7.1樹的遍歷

前序遍歷：“根左右”，即先訪問根結點，然后再從左到右按前序遍歷各棵子樹。

后序遍歷：“左右根”，即從左到右遍歷根結點的各棵子樹，最后訪問根結點。

層次遍歷：首先訪問處于0層的根結點，然后從左到右訪問1層上的結點，以此類推，層層向下
訪問

7.2二叉樹

二叉樹是一個有限的結點集合，該集合或者為空，或者由一個根結點及其兩棵互不相交的左、右二叉子樹所組成。

二叉樹的結點中有兩棵子二叉樹，分別稱為左子樹和右子樹。因為二叉樹可以為空，所以二叉樹中的結點可能沒有子結點，也可能只有一個左子結點（右子結點），也可能同時有左右兩個子結點。如圖所示是二叉樹的4種可能形態（如果把空樹計算在內，則共有5種形態）。

總結已知節點求能構造多少種二叉樹

(2n)! / (n! * (n-1)! )

7.3滿二叉樹

一棵深度為k且有2k-1（k≥1）個結點的二叉樹就稱為滿二叉樹。

7.4完全二叉樹

如果深度為k、有n個結點的二叉樹中各結點能夠與深度k的順序編號的滿二叉樹從1到n標號的結點相對應即為完全二叉樹。

7.5叉樹的性質

在二叉樹的第i層上最多有2i-1個結點（i≥1）；

深度為k的二叉樹最多有2k-1個結點（k≥1）；

對任何一棵二叉樹，如果其葉子結點數為n0，度為2的結點數為n2，則n0=n2+1；

具有n個結點的完全二叉樹的深度為，[log2n];

如果對一棵有n個結點的完全二叉樹的結點按層序編號（從第1層到 +1層，每層從左到右），則對任一結點i（1≤i≤n），有：
如果i=1，則結點i無父結點，是二叉樹的根；如果i>1，則父結點是
如果2i>n，則結點i為葉子結點，無左子結點；否則，其左子結點是結點2i；
如果2i+1>n，則結點i無右子結點，否則，其右子結點是結點2i+1。

7.6二叉樹的遍歷

前序遍歷中序后序層次遍歷

7.7二叉查找樹

二叉查找樹，它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分別為二叉查找樹；
當對這樣的二叉樹進行中序遍歷，就可以得到一個排好序的結點序列，因此，二叉查找樹也稱為二叉排序樹。

7.8平衡二叉樹

平衡二叉樹又被稱為AVL樹，它具有以下性質：它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。滿二叉樹就是一種平衡二叉樹。

7.9線索二叉樹

二叉樹在通常情況下是無法直接找到某結點在某種遍歷序列中的前驅和后繼結點的。而線索二叉樹則通過利用二叉樹上空的指針域來存放些“線索”信息，

通常其采用以下做法：

若前驅結點不為空，而且其右指針域為空，則將根結點的地址賦給前驅結點的右指針域，并將前驅結點的右線索標志置1；
若根結點的左指針域為空，則把前驅結點的地址賦給根結點的左指針域，同時將根結點的左線索標志置1；
將根結點地址賦給保存前驅結點指針的變量，以便當訪問下一個結點時，此根結點成為前驅結點。

7.10 哈夫曼樹(最優二叉樹)

在權值相同的n個葉子結點構成的所有二叉樹中，帶權路徑長度最小的二叉樹稱為最優二叉樹，也稱為哈夫曼樹。

8.圖

有向圖：若一個圖中的每條邊都是有方向的，則稱為有向圖。在有向圖中，<Vi，Vj>表示一條有向邊，Vi是始點（起點），Vj是終點。<Vi，Vj>和<Vj，Vi>表示的是兩條不同的邊。有向邊也稱為弧，邊的始點稱為弧頭，終點稱為弧尾。

無向圖：若一個圖中的每條邊都是無方向的，則稱為無向圖。無向圖的邊是頂點的無序對，通常使用（Vi，Vj）來表示一條邊，無向圖的邊沒有起點和終點，（Vi，Vj）和（Vj，Vi）表示的是同一條邊。

無向完全圖：如果限定任何一條邊的兩個頂點都不相同，則有n個頂點的無向圖至多有n(n-1)/2條邊，這樣的無向圖稱為無向完全圖。

有向完全圖：恰好有n(n-1)條邊的有向圖稱為有向完全圖。

連通圖：如果圖中兩個頂點間存在路徑，則稱它們是連通的；而如果圖中任意兩個頂點間都是連通的，則稱該圖為連通圖。

8.1圖的存儲結構

8.2圖的遍歷

8.3最小生成樹

對一個帶權的圖，在一棵生成樹中，各條邊的權植之和為這棵生成樹的代價，其中代價最小的生成樹稱為最小生成樹。普里姆算法（Prim算法）和克魯斯卡爾算法（Kruskal算法）是求連通的帶權無向圖的最小代價樹的常用算法。

第五章數據庫

1.數據庫模式及ER模型

1.三級模式與兩級映射

數據庫系統由外模式、概念模式和內模式三級構成

三級模式

外模式也稱為子模式或用戶模式，它對應的是我們平時所用到的數據庫視圖。外模式用來描述用戶（包括程序員和最終用戶）看到或使用的那部分數據的邏輯結構，是數據庫用戶的數據視圖，是與某一應用有關的數據的邏輯表示。一個數據庫可以有多個外模式，一個應用程序只能使用一個外模式。

概念模式也稱為模式或邏輯模式，它對應我們平時所用到的數據表。概念模式是數據庫中全體數據的邏輯結構和特征的描述，是所有用戶的公共數據視圖，用以描述現實世界中的實體及其性質與聯系，定義記錄、數據項、數據的完整性約束條件及記錄之間的聯系。概念模式通常還包含有訪問控制、保密定義和完整性檢查等方面的內容，以及概念/物理間的映射。一個數據庫只有一個概念模式。

內模式對應于物理級數據庫，是數據物理結構和存儲方式的描述，是數據在數據庫內部的表示方式。內模式不同于物理層，它假設外存是一個無限的線性地址空間。內模式定義的是存儲記錄的類型、存儲域的表示和存儲記錄的物理順序，以及索引和存儲路徑等數據的存儲組織。一個數據庫只有一個內模式。

在數據庫系統的三級模式中，模式是數據庫的中心與關鍵；內模式依賴于模式，獨立于外模式和存儲設備；外模式面向具體的應用，獨立于內模式和存儲設備；應用程序依賴于外模式，獨立于模式和內模式。

兩級映射

外模式與概念模式之間的映射：用于維護數據庫的邏輯獨立性。也就是說，有了這個映射，使得數據的邏輯結構改變時，應用程序不需要改變，只需要改變映射中的對應關系即可達到目的。

概念模式與內模式之間的映射：用于維護數據庫的物理獨立性。也就是說當數據的物理存儲改變時，應用程序不需要改變。

2.ER模型

實體：客觀存在并可相互區別的事物，可以是具體的人、事、物，也可以是抽象的概念或聯系。圖中的“學生”與“課程”便是實體。

屬性：實體所具有的某一特性稱為屬性，通常一個實體可以由多個屬性來描述。圖中“學生”實體旁邊的“學號”、“姓名”、“班級號”便是屬性。

聯系：實體內部的聯系通常是指組成實體的各屬性間的關系。圖中“選課”便是聯系。

聯系

一對一聯系（1:1）：對于實體集A中的每一個實體，實體集B中至多有一個實體與之聯系。例：一個班級只有一個班主任，一個班主任也只在一個班級中任職。

一對多聯系（1:n）：對于實體集A中的每一個實體，實體集B中有n（n>0）個實體與之聯系。反之，實體集B中的每一個實體，實體集A中至多只有一個實體與之聯系。例：一個班級中有許多學生，而每個學生只在一個班級中學習。

多對多聯系（m:n）：對于實體集A中的每一個實體，實體集B中有n（n>0）個實體與之聯系。反之，實體集B中的每一個實體，實體集A中有m（m>0）個實體與之聯系。一門課程同時有許多學生選修，而一個學生也可以選修多門課程。如圖5-2所示，該ER模型便屬于m:n型。

ER圖之間的沖突

屬性沖突。屬性沖突包括屬性域沖突和屬性取值沖突。屬性沖突理論上好解決，只要換成相同的屬性就可以了，但實際上需要各部門協商，解決起來并不簡單。

命名沖突。命名沖突包括同名異義和異名同義。處理命名沖突通常也像處理屬性沖突一樣，通過討論和協商等行政手段加以解。

結構沖突。結構沖突包括同一對象在不同應用中具有不同的抽象，以及同一實體在不同局部E-R圖中所包含的屬性個數和屬性排列次序不完全相同。對于前者的解決辦法是將屬性變換為實體或實體變換為屬性，使同一對象具有相同的抽象。對于后者的解決辦法是使該實體的屬性取各局部E-R圖中屬性的并集，再適當調整屬性的次序。

2.關系運算

并。計算兩個關系在集合理論上的并集，即給出關系R和S（兩者有相同元/列數），R∪S的元組包括R和S所有元組的集合

差。計算兩個關系的區別的集合，即給出關系R和S（兩者有相同元/列數），R-S的元組包括R中有而S中沒有的元組的集合，

交。計算兩個關系集合理論上的交集，即給出關系R和S（兩者有相同元/列數），R∩S的元組包括R和S相同元組的集合，

笛卡爾積。計算兩個關系的笛卡爾乘積，令R為有m元的關系，S為有n元的關系，則R×S是m+n元的元組的集合，其前m個元素來自R的一個元組，而后n個元素來自S的一個元組

投影。從一個關系中抽取指明的屬性（列）。

選擇。從關系R中抽取出滿足給定限制條件的記錄，

3.規范化理論

解決存儲異常問題

（1）數據冗余：如果某門課程有100個學生選修，那么在R的關系中就要出現100個元組，這門課程的任課教師姓名和地址也隨之重復出現100次。

（2）修改異常：由于上述冗余問題，當需要修改這個教師的地址時，就要修改100個元組中的地址值，否則就會出現地址值不一致的現象。

（3）插入異常：如果不知道聽課學生名單，這個教師的任課情況和家庭地址就無法進入數據庫；否則就要在學生姓名處插入空值。

（4）刪除異常：如果某門課程的任課教師要更改，那么原來任課教師的地址將隨之丟失。

4.鍵

超鍵：在關系模式中，能唯一標識元組的屬性集稱為超鍵。

候選鍵：如果一個屬性集能唯一標識元組，且又不含有多余屬性。

主鍵：關系模式中用戶正在使用的候選鍵稱為主鍵。

外鍵：如果公共關鍵字在一個關系中是主關鍵字，那么這個公共關鍵字被稱為另一個關系的外鍵。

5.范式

第一范式（1NF）：在關系模式R中，當且僅當所有域只包含原子值，即每個分量都是不可再分的數據項，則稱實體E是第一范式。

第二范式（2NF）：當且僅當實體E是第一范式（1NF），且每一個非鍵屬性完全依賴主鍵（沒有不完全依賴）時，則稱實體E是第二范式。

第三范式（3NF）：當且僅當實體E是第二范式（2NF），且E中沒有非主屬性傳遞依賴于碼時，則稱實體E是第三范式。

BCNF：如果關系模型R∈1NF，且R中每一個函數依賴關系中的決定因素都包含碼，則R是滿足BC范式的關系。

為了準確的界定某關系模式是否為BCNF，我們需要引入另外的一些判別方
法。

6.關系模式分解

6.1無損連接分解

方法一：公式法
優點：速度快。
缺點：只能應用于一分為二的情況，一個關系模式要分解為三個關系模式就用不上了。
判定定理：設ρ={R1，R2}是R的一個分解，F是R上的函數依賴集，那么分解ρ相對于F是無損聯接分解的充要條件是(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)。要注意的是，這兩個條件只要有任意一個條件成立就可以了。

方法二：表格法。
優點：速度慢。
缺點：適用于所有形式的模式分解。

原表

由于A→B，屬性A的第1行和第3行相同，可以將第1行b12改為a2；又由于B→D，屬性B的第1行和第3行相同，所以需要將屬性D第1行b14和第3行b34，改為同一符號，即取行號值最小的b14。

修改后的表

6.2保持函數依賴分解

設數據庫模式δ={R1，…，RK}是關系模式R的一個分解，F是R上的函數依賴集，δ中每個模式Ri上的函數依賴集是Fi。如果{F1，F2，…，Fk}與F是等價的（即相互邏輯蘊涵），則稱分解δ保持函數依賴。如果分解不能保持函數依賴，則δ的實例上的值就可能有違反函數依賴的現象。

7.SQL語句

單表查詢

結果處理

數據更新操作

第六章計算機網絡

1.OSI模型

2.TCP/IP協議族

3.IP地址

3.1 IP地址

3.2 子網掩碼

子網掩碼是相對特別的IP地址而言的，如果脫離了IP地址就毫無意義。它的出現一般跟著一個特定的IP地址，用來為計算這個IP地址中的網絡號部分和主機號部分提供依據，換句話說，就是在寫一個IP地址后，再指明哪些是網絡號部分，哪些是主機號部分。

3.3 ipv6

現在的IP協議的版本號為4，所以也稱為IPv4。它已經有了20年漫長的歷史，為計算機網絡互聯做出了巨大的貢獻。然而，互聯網以人們不可想像的速度在膨脹，IPv4不論從地址空間上，還是協議的可用性上都無法滿足互聯網的新要求。這樣一個新的IP協議開始孕育而生，這個新版本IP協議，早先被稱為IPng，現在一般被叫做IPv6。

IPv6將原來的32位地址擴展成為128位地址，徹底解決了地址缺乏的問題

ipv6所能表示的IP地址為ipv4 的2^96倍

4.層次化網絡設計

接入層：網絡中直接面向用戶連接或訪問網絡的部分。其目的是允許終端用戶連接到網絡，因此接入層交換機具有低成本和高端口密度特性。

匯聚層：位于接入層和核心層之間的部分。匯聚層用于完成網絡訪問策略控制、數據包處理、過濾、尋址，以及其他數據處理的任務。

核心層：網絡主干部分。其主要目的在于通過高速轉發通信，提供優化、可靠的骨干傳輸結構，因此核心層交換機應擁有更高的可靠性，性能和吞吐量。

5.域名

xinu.cs.purdue.edu中，xinu是主機名、cs和purdue是子域名（分別代表計算機系、普渡大學）、edu是主域名。

常用域名

5.1 DNS系統

5.2 DHCP(動態主機配置協議)

6.常見的網絡命令

ping
ping命令的作用是檢查網絡是否通暢或者網絡連接速度，ping命令只有在安裝了TCP/IP協議以后才可以使用。
例如：ping 192.168.0.4 –l 65000 –t
-l 設置數據包大小，用最大值65000字節（原來為32字節）
–t 不停地執行這個命令，除非人為中止

ipconfig
ipconfig命令用于顯示計算機中網絡適配器的IP地址、子網掩碼及默認網關等信息。該命令有多種參數，不同參數可起到不同作用。
例如：
1直接輸入ipconfig，然后回車，顯示用戶主機IP協議的配置信息。
2ipconfig –all ，更詳細地顯示機器的網絡信息。
3ipconfig /release，歸還DHCP服務器自動分配給本機的IP地址。
4ipconfig /renew，向DHCP服務器重新申請一個新的IP地址。
5ipconfig/flushdns，清理并重設DNS客戶解析器緩存的內容。

tracert
tracert命令是路由跟蹤命令，用于跟蹤路由信息，使用此命令可以查出數據從本地機器傳輸到目標主機所經過的所有途徑，這對我們了解網絡布局和結構很有幫助。
例如：
1輸入tracert www.csai.cn，然后回車，顯示本機至www.csai.cn所經路徑信息。
2輸入tracert –d www.csai.cn，然后回車，效果與之前略有差異，–d的意思是不解析對方主機的名稱，加快查詢速度。

netstat
netstat命令用于查看網絡狀態。
例如：
1輸入netstat –r命令，顯示本機的路由狀況。
2輸入netstat –s命令，顯示每個協議的使用狀態，其中包括途中的TCP、UDP、IP等協議。
3輸入netstat –n命令，以數字、表格形式顯示IP端口，本機沒有聯入互聯網，所以顯示為空。
4輸入netstat –a命令，顯示所有主機的端口號。

第七章軟件工程

1.開發模型

1.1瀑布模型

瀑布模型：嚴格遵循軟件生命周期各階段的固定順序，一個階段完成再進入另一個階段。其優點是：可以使過程比較規范化，有利于評審；缺點在于：過于理想，缺乏靈活性，容易產生需求偏差。所以瀑布模型的應用場合為：需求明確的項目、二次開發項目以及原型法配合使用。

1.2快速原型模型

采用了一種動態定義需求的方法，通過快速地建立一個能夠反映用戶主要需求的軟件原型，讓用戶在計算機上使用它，了解其概要，再根據反饋的結果進行修改，因此能夠充分體現用戶的參與和決策。原型化人員對原型的實施很重要，衡量他們的重要標準是能否從用戶的模糊描述中快速地獲取實際的需求。所以快速原型模型很好的彌補了瀑布模型的缺陷，它適合于需求不夠明確的項目。

1.3演化模型

也是一種原型化開發，但與快速原型不同的是，快速原型模型在獲得真實需求時，就將拋棄原型。而演化模型則不然，它將從初始的模型中逐漸演化為最終軟件產品，是一種“漸進式”原型法。其應用場合也是需求不明確的項目。

1.4增量模型

它采用的是一種“遞增式”模型，它將軟件產品劃分成為一系列的增量構件，分別進行設計、編碼、集成和測試。相對于原型法而言，這種模型其實是從系統開發的另一個方面看待問題，原型法關注點是“制作一個原型”，而增量模型的關注點是“系統的功能模塊不是一次完成的，而是一塊一塊開發，以增加的方式進行的”。在現實開發中，我們會發現，一個項目開發過程既用了原型模型也用了增量模型。所以增量模型仍有利于進行需求不明確的項目開發。

1.5螺旋模型

結合了瀑布模型和演化模型的優點，最主要的特點在于加入了風險分析。它是由制定計劃、風險分析、實施工程、客戶評估這一循環組成的，它最初從概念項目開始第一個螺旋。

1.6噴泉模型

主要用于描述面向對象的開發過程，最核心的特點是迭代。所有的開發活動沒有明顯的邊界，允許各種開發活動交叉進行。

1.7 up（統一過程）

既是一個統一的軟件開發過程，是一個通用過程框架，可以應付種類廣泛的軟件系統、不同的應用領域、不同的組織類型、不同的性能水平和不同的項目規模。UP是基于構件的，這意味著利用它開發的軟件系統是由構件構成的，構件之間通過定義良好的接口相互聯系。在準備軟件系統所有藍圖的時候，UP使用的是統一建模語言UML。與其他軟件過程相比，UP具有三個顯著的特點：用例驅動、以基本架構為中心、迭代和增量。

UP中的軟件過程在時間上被分解為四個順序的階段，分別是初始階段、細化階段、構建階段和交付階段。每個階段結束時都要安排一次技術評審，以確定這個階段的目標是否已經滿足。如果評審結果令人滿意，就可以允許項目進入下一個階段。

1.8 XP 敏捷開發

2.信息系統開發方法

結構化方法是一種傳統的軟件開發方法，它是由結構化分析、結構化設計和結構化程序設計三部分有機組合而成的。它的基本思想：把一個復雜問題的求解過程分階段進行，而且這種分解是自頂向下，逐層分解，使得每個階段處理的問題都控制在人們容易理解和處理的范圍內。

2.1結構化分析基礎

結構化分析方法是以自頂向下，逐步求精為基點，以一系列經過實踐的考驗被認為是正確的原理和技術為支撐，以數據流圖，數據字典，結構化語言，判定表，判定樹等圖形表達為主要手段，強調開發方法的結構合理性和系統的結構合理性的軟件分析方法。

2.2結構化設計基礎

結構化設計是以結構化分析階段所產生的成果為基礎，進一步自頂而下、逐步求精和模塊化的過程。其主要工作內容是進行概要設計與詳細設計

概要設計的主要任務是把需求分析得到的數據流圖轉換為軟件結構和數據結構。設計軟件結構的具體任務是：將一個復雜系統按功能進行模塊劃分、建立模塊的層次結構及調用關系、確定模塊間的接口及人機界面等。數據結構設計包括數據特征的描述、確定數據的結構特性、以及數據庫的
設計。顯然，概要設計建立的是目標系統的邏輯模型，與計算機無關。在概要設計過程中常常會使用結構圖（包括模塊、調用、數據）、層次圖、HIPO（層次圖加輸入/處理/輸出圖）來描述程序的結構。

詳細設計是對概要設計的一個細化，就是詳細設計每個模塊實現算法，所需的局部結構。經常使用的工具包括程序流程圖、盒圖、PAD圖（問題分析圖）、PDL（偽碼）。

2.3模塊設計原則

信息隱蔽：在設計和確定模塊時，使得一個模塊內包含信息（過程或數據），對于不需要這些信息的其他模塊來說，是不能訪問的。這樣做的好處是：讓所有的操作都通過標準的接口進行，這樣避免了隨意調用模塊內部變量產生的混亂與錯誤。通過信息隱蔽可以提高軟件的可修改性、可測試性和可移植性。所以不僅在結構化方法中有信息隱蔽原則，在面向對象方法中，也有相應機制進行信息隱蔽。

模塊獨立：每個模塊完成一個相對獨立的特定子功能，并且與其他模塊之間的聯系最簡單。保持模塊的高度獨立性，也是在設計時的一個很重要的原則。通常我們用耦合（模塊之間聯系的緊密程度）和內聚（模塊內部各元素之間聯系的緊密程度）兩個標準來衡量，我們的目標是高內聚、低耦合。

2.3.1內聚類型

2.3.2耦合類型

3.面向對象概念

1.基本概念

類對象繼承與泛化封裝多態模板消息通信

2.面向對象開發方法

2.1OOA（面向對象的分析）

OOA即面向對象的分析，它的任務是了解問題域所涉及的對象、對象間的關系和操作，然后構造問題的對象模型。問題域是指一個包含現實世界事物與概念的領域，這些事物和概念與所設計的系統要解決的問題有關。在這個過程中，抽象是最本質和最重要的方法針對不同的問題，可以選擇不同的抽象層次，過簡或過繁都會影響到對問題的本質屬性的了解和解決。

2.2OOD（面向對象的設計）

OOD即面向對象的設計，它在分析對象模型的基礎上，設計各個對象、對象之間的關系（例如，層次關系、繼承關系等）和通信方式（例如，消息模式）等，其主要作用是對OOA的結果作進一步的規范化整理，以便能夠被OOP直接接受。

設計原則

單一職責原則：設計目的單一的類；
開放-封閉原則：對擴展開放，對修改封閉；
李氏(Liskov)替換原則：子類可以替換父類；
依賴倒置原則：要依賴于抽象，而不是具體實現；針對接口編程，不要針對實現編程；
接口隔離原則：使用多個專門的接口比使用單一的總接口要好；
組合重用原則：要盡量使用組合，而不是繼承關系達到重用目的；
迪米特(Demeter)原則(最少知識法則)：一個對象應當對其他對象有盡可能少的了解。

2.3OOP

OOP指系統功能的編碼，實現在OOD階段所規定的各個對象所應完成的任務。它包括每個對象的內部功能的實現，確立對象哪一些處理能力應在哪些類中進行描述，確定并實現系統的界面、輸出的形式等。

4.軟件測試

1.測試原則

（1）盡早、不斷的進行測試；
（2）程序員避免測試自己設計的程序；
（3）既要選擇有效、合理的數據，也要選擇無效、不合理的數據；
（4）修改后應進行回歸測試；
（5）尚未發現的錯誤數量與該程序已發現錯誤數成正比。

2.測試分類

軟件測試按階段劃分，可分為：單元測試，集成測試，確認測試，系統測試。

2.1單元測試

單元測試，也稱模塊測試，通常可放在編程階段，由程序員對自己編寫的模塊自行測試，檢查模塊是否實現了詳細設計說明書中規定的功能和算法。單元測試主要發現編程和詳細設計中產生的錯誤，單元測試計劃應該在詳細設計階段制定。

單元測試期間著重從以下幾個方面對模塊進行測試：模塊接口、局部數據結構、重要的執行通路、出錯處理通路、邊界條件等。

2.2集成測試

集成測試，也稱組裝測試，它是對由各模塊組裝而成的程序進行測試，主要目標是發現模塊間的接口和通信問題。例如，數據穿過接口可能丟失；一個模塊對另一個模塊可能由于疏忽而造成有害影響；把子功能組合起來可能不產生預期的主功能；個別看來是可以接受的誤差可能積累到不能接受的程度；全程數據結構可能有問題等。集成測試主要發現設計階段產生的錯誤，集成測試計劃應該在概要設計階段制定。

2.3確認測試

確認測試（Validation Testing）主要依據軟件需求說明書檢查軟件的功能、性能及其他特征是否與用戶的需求一致。確認測試計劃應該在需求分析階段制定。軟件配置復查是確認測試的另一項重要內容。復查的目的是保證軟件配置的所有成分都已齊全，質量符合要求，文檔與程序完全一致，具有完成軟件維護所必須的細節。

如果一個軟件是為某個客戶定制的，最后還要由該客戶來實施驗收測試（acceptancetesting），以便確認其所有需求是否都已得到滿足。由于軟件系統的復雜性，在實際工作中，驗收測試可能會持續到用戶實際使用該軟件之后的相當長的一段時間。

2.4系統測試

系統測試的對象是完整的、集成的計算機系統，系統測試的目的是在真實系統工作環境下，驗證完整的軟件配置項能否和系統正確連接，并滿足系統/子系統設計文檔和軟件開發合同規定的要求。系統測試的技術依據是用戶需求或開發合同，除應滿足一般測試的準入條件外，在進行系統測試前，還應確認被測系統的所有配置項已通過測試，對需要固化運行的軟件還應提供固件。

一般來說，系統測試的主要內容包括功能測試、健壯性測試、性能測試、用戶界面測試、安全性測試、安裝與反安裝測試等，其中，最重要的工作是進行功能測試與性能測試。功能測試主要采用黑盒測試方法，性能測試主要驗證軟件系統在承擔一定負載的情況下所表現出來的特性是否符合客戶的需要，主要指標有響應時間、吞吐量、并發用戶數和資源利用率等。

3.白盒測試（從程序設計者的角度）

白盒測試可以應用于單元測試、集成測試和系統的軟件測試流程，可測試在集成過程中每一單元之間的路徑，或者主系統跟子系統中的測試。

白盒測試主要是從覆蓋源程序語句的詳盡程度來分析。邏輯覆蓋標準包括以下不同的覆蓋標準：語句覆蓋、判定覆蓋、條件覆蓋、條件判定組合覆蓋、多條件覆蓋、路徑覆蓋。

3.1McCabe復雜度

McCabe復雜度屬于白盒測試技術。McCabe復雜度包括環路復雜度（Cyclomaticcomplexity）、基本復雜度、模塊設計復雜度、設計復雜度和集成復雜度等。

計算有向圖G的環路復雜度公式為：
V(G)=m-n+2
說明：其中V(G)是有向圖G中的環路個數，m是G中的有向弧數，n是G中的節點數。

4.黑盒測試

黑盒測試也稱功能測試，它是通過測試來檢測每個功能是否都能正常使用。在測試中，把程序看作一個不能打開的黑盒子，在完全不考慮程序內部結構和內部特性的情況下，在程序接口進行測試，它只檢查程序功能是否按照需求規格說明書的規定正常使用，程序是否能適當地接收輸入數據
而產生正確的輸出信息。黑盒測試著眼于程序外部結構，不考慮內部邏輯結構，主要針對軟件界面和軟件功能進行測試。

常用的黑盒測試法包括：等價類劃分、邊值分析、錯誤推測和因果圖。

5.軟件維護

軟件維護主要是指根據需求變化或硬件環境的變化對應用程序進行部分或全部的修改。在修改時應充分利用源程序，修改后應填寫程序改登記表，并在程序變更通知書上寫明新舊程序的不同之處。

改正性維護：是指改正在系統開發階段已發生而系統測試階尚未發現的錯誤。

適應性維護：是指使用軟件適應信息技術變化和管理需求變化而進行的修改。

完善性維護：這是為擴充功能和改善性能而進行的修改，主要是指對已有的軟件系統增加一些在系統分析和設計階段中沒有規定的功能與性能特征。

預防性維護：為了改進應用軟件的可靠性和可維護性，為了適應未來的軟硬件環境的變化，應主動增加預防性的新的功能，以使應用系統適應各類變化而不被淘汰。

6.軟件質量特性

6.1IEO/IEC 9126模型

6.2McCall質量模型

6.3軟件技術評審

制訂計劃：確定誰參加，一般需要將人數控制在7人之內；確定準備哪些內容。
總體會議：確定評審的背景、假設及目標。
做準備：評審員預先閱讀評審的材料。
評審會議：主持人引導，根據預先準備的檢查表進行評審。
返工：評審會議是為了發現問題，問題應在會后進行返工。
跟蹤：確定錯誤已經修改，并通知所有的評審人。

6.4能力成熟度模型集成（CMMI）

第八章信息安全

1.安全基礎信息

1.1對稱加密

對稱加密是指加密系統的加密密鑰和解密密鑰相同，或者雖然不同，但從其中的任意一個可以很容易地推導出另一個。
對稱加密算法的優點是：使用簡單、加密解密快捷高效，其致命弱點是：加密強度不高、密鑰分發困難。
常見對稱密鑰加密算法包括：DES、3DES、RC-5、IDEA。

1.2非對稱加密

在非對稱加密體系中，密鑰是成對出現的，一對密鑰包括一個公鑰和一個私鑰。如果用公開密鑰對數據進行加密，只有用對應的私有密鑰才能解密；如果用私有密鑰對數據進行加密，那么只有用對應的公開密鑰才能解密。
非對稱加密算法的優點在于：解決了對稱密鑰加密強度不高及密鑰分發困難的問題，其缺點是：加密速度極慢。所以非對稱加密算法通常只對極小的數據量進行加密，如對信息摘要進行加密，或用于加密對稱密鑰。
常見非對稱密鑰加密算法：RSA、ECC。

1.3Hash函數和信息摘要

Hash函數又稱為雜湊函數、散列函數，它提供了這樣的一種計算過程：輸入一個長度不固定的字符串，返回一串定長的字符串（又稱為Hash值），單向Hash函數用于產生信息摘要。

信息摘要簡要地描述了一份較長的信息或文件，它可以被看做是一份長文件的“數字指紋”，信息摘要可以用于創建數字簽名。

對于特定的文件而言，信息摘要是唯一的，而且不同的文件必將產生不同的信息摘要。常見的信息摘要算法包括MD5（產生一個128位的輸出，輸入是以512位的分組進行處理的）和SHA（安全散列算法，也是按512位的分組進行處理，產生一個160位的輸出）。它們可以用來保護數據的完整性。

1.4數字簽名

數字簽名是通過一個單向函數對要傳送的報文進行處理，得到用以認證報文來源并核實報文是否發生變化的一個字母數字串。

1.5數字證書（密鑰與身份信息的結合體）

數字證書的格式一般使用X.509國際標準。X.509是廣泛使用的證書格式之一，X.509用戶公鑰證書是由可信賴的證書權威機構（CA——證書授權中心）創建的，并且由CA或用戶存放在X.500的目錄中。任何一個用戶只要得到CA中心的公鑰，就可以得到該CA中心為該用戶簽署的公鑰。每個用戶的證書上都有CA中心用其私鑰進行的數字簽名，所以只需使用CA中心的公鑰便可驗證數字證書的真偽。

較通行的數字證書格式還有PGP。

2.網絡安全協議

3.網絡攻擊

3.1DDoS攻擊

DDoS攻擊通過很多“肉雞”（被攻擊者入侵過或可間接利用的主機）向受害主機發送大量看似合法的網絡包，從而造成網絡阻塞或服務器資源耗盡而導致拒絕服務，分布式拒絕服務攻擊一旦被實施，攻擊網絡包就會猶如洪水般涌向受害主機，從而把合法用戶的網絡包淹沒，導致合法用戶無法正常訪問服務器的網絡資源。

3.2ARP欺騙攻擊

ARP欺騙攻擊：修改IP地址和MAC地址的映射關系，使發送給正確主機的數據包發送給另外一臺由攻擊者控制的主機。

3.3入侵檢測

入侵檢測技術是為保證計算機系統的安全而設計與配置的一種能夠及時發現并報告系統中未授權或異常現象的技術，是一種用于檢測計算機網絡中違反安全策略行為的技術。違反安全策略的行為有：入侵—非法用戶的違規行為；濫用—用戶的違規行為。

3.6漏洞掃描

漏洞掃描是指基于漏洞數據庫，通過掃描等手段，對指定的遠程或者本地計算機系統的安全脆弱性進行檢測，發現可利用的漏洞的一種安全檢測（滲透攻擊）行為。

漏洞掃描是對電腦進行全方位的掃描，檢查你當前的系統是否有漏洞，如果有漏洞則需要馬上進行修復，否則電腦很容易受到網絡的傷害甚至被黑客借助于電腦的漏洞進行遠程控制那么后果將不堪設想，所以漏洞掃描對于保護電腦和上網安全是必不可少的，而且需要每星期就進行一次掃描，一但發現有漏洞就要馬上修復，有的漏洞系統自身就可以修復，而有些則需要手動修復。

4.計算機病毒

4.1系統引導型病毒

又稱開機型病毒，是藏匿和感染硬盤的第一個扇區，即平常我們所說的引導扇區。引導型病毒籍由引導動作而侵入內存。

系統病毒的前綴為：Win32、PE、Win95、W32、W95等。這些病毒的一般共有的特性是可以感染windows操作系統的 *.exe 和 *.dll 文件，并通過這些文件進行傳播。

4.2文件型病毒

文件型病毒通常寄生在可執行檔（如 .COM，.EXE等）中。當這些文件被執行時，病毒的程序就跟著被執行。

4.3目錄型病毒

這一類型病毒通過裝入與病毒相關的文件進入系統，而不改變相關文件，它所改變的只是相關文件的目錄項。

4.4蠕蟲病毒

蠕蟲病毒是一種常見的計算機病毒。它是利用網絡進行復制和傳播，傳染途徑是通過網絡和電子郵件。最初的蠕蟲病毒定義是因為在DOS環境下，病毒發作時會在屏幕上出現一條類似蟲子的東西，胡亂吞吃屏幕上的字母并將其改形。蠕蟲病毒是自包含的程序（或是一套程序），它能傳播自身功能的拷貝或自身（蠕蟲病毒）的某些部分到其他的計算機系統中（通常是經過網絡連接）。

蠕蟲病毒的前綴是：Worm。這種病毒的共有特性是通過網絡或者系統漏洞進行傳播，很大部分的蠕蟲病毒都有向外發送帶毒郵件，阻塞網絡的特性。比如沖擊波（阻塞網絡），小郵差（發帶毒郵件）等。

4.5宏病毒

一種寄存在Office系統文檔或模板的宏中的計算機病毒。一旦打開這樣的文檔，其中的宏就會被執行，于是宏病毒就會被激活，轉移到計算機上，并駐留在Normal模板上。從此以后，所有自動保存的文檔都會“感染”上這種宏病毒，而且如果其他用戶打開了感染病毒的文檔，宏病毒又會轉移到他的計算機上。

宏病毒也是腳本病毒的一種，由于它的特殊性，因此在這里單獨算成一類。宏病毒的前綴是：Macro，第二前綴是：Word、Excel其中之一。如：Macro.Word.WhiteScreen、美麗莎（Macro.Melissa）。

4.6 后門病毒

后門病毒的前綴是：Backdoor。該類病毒的共有特性是通過網絡傳播，給系統開后門，給用戶電腦帶來安全隱患。

第九章知識產權

1.保護期限

2.產權人的確定

3.侵權判定

區。引導型病毒籍由引導動作而侵入內存。