58同城鹽城網(wǎng)站建設(shè)東莞網(wǎng)站排名提升
前言：全國計算機技術(shù)與軟件專業(yè)技術(shù)資格（水平）考試（以下簡稱IT職業(yè)資格考試）是由中華人民共和國人事部主管，國家計算機網(wǎng)絡與信息安全管理中心主辦的一項國家級、權(quán)威性的計算機職業(yè)技能水平認證考試。主要為企事業(yè)單位和社會培訓機構(gòu)提供了一個可以測試、認證計算機和軟件專業(yè)技能水平的途徑。
在IT職業(yè)資格考試中，軟件設(shè)計師考試（簡稱軟考）是一個重要的考試類別，資格證書被認為是軟件行業(yè)人才的重要標志和職業(yè)資格證明。
軟考中級軟件設(shè)計師是軟考的一個等級，屬于軟件工程師職業(yè)級別，是一項高級軟件設(shè)計和開發(fā)領(lǐng)域的專業(yè)資格認證，是軟件行業(yè)職業(yè)人員的核心能力證明之一。軟考中級軟件設(shè)計師考試內(nèi)容包括軟件開發(fā)、需求分析、軟件測試、軟件項目管理、軟件質(zhì)量保證等多個方面。通過此證書考試，證明了考生在軟件設(shè)計和開發(fā)方面的專業(yè)知識和實踐經(jīng)驗，能夠在軟件項目中發(fā)揮重要的作用，為企業(yè)和組織提供高質(zhì)量的軟件應用解決方案。
?
以下是學長為大家整理的軟件設(shè)計師知識點，希望能幫助大家取得一個好成績~
第 1 章 計算機系統(tǒng)知識
計算機系統(tǒng)由兩部分組成：硬件、軟件。
? 計算機硬件系統(tǒng)五大組成部分
控制器、運算器、存儲器、輸入設(shè)備、輸出設(shè)備
存儲器分為內(nèi)部存儲器（內(nèi)存、容量小、速度快、存放臨時數(shù)據(jù)，斷 電消失）和外部存儲器（硬盤、光盤、容量大、速度慢、長期數(shù)據(jù)保 存）
輸入設(shè)備、輸出設(shè)備統(tǒng)稱外設(shè)
主機（ CPU + 主存儲器）
? 中央處理單元 CPU
CPU 組成：由運算器、控制器、寄存器組（讀取速度最快）、內(nèi)部 總線組成
CPU 功能：實現(xiàn)程序控制、操作控制、時間控制、數(shù)據(jù)處理功能
運算器組成（?？?#xff09;：
算數(shù)邏輯單元 ALU(Arithmetic logic unit)：實現(xiàn)對數(shù)據(jù)的算 數(shù)和邏輯運算，提供一個工作區(qū)
累加寄存器 AC(Accumulator): 運算結(jié)果或者源操作數(shù)的存放 區(qū)
數(shù)據(jù)緩沖寄存器 DR(Data Register): 暫時存放內(nèi)存的指令或數(shù) 據(jù)
狀態(tài)條件寄存器 PSW(Program Status Word): 保存指令運行結(jié) 果的條件嗎內(nèi)容，如溢出標志等
運算器功能：執(zhí)行算數(shù)運算和邏輯運算
控制器：
指令寄存器 IR （ Instruction Register ） : 暫存當前
CPU正在執(zhí)行的指令
程序計數(shù)器 PC （ Program Counter ）：存檔指令執(zhí)行地址
地址寄存器 AR （ Address Register ）：保存當前 CPU所訪 問的內(nèi)存地址
指令譯碼器 ID （ Instruction Decoder）：分析指令操作碼
控制器功能：控制整個 CPU的工作，最為重要，包括程序控制、時序 控制
程序員可以訪問通用寄存器存取數(shù)據(jù)，也可以訪問狀態(tài)寄存器和程序 計數(shù)器，但是不能訪問指令寄存器
? 數(shù)據(jù)進制轉(zhuǎn)換
二進制、十六進制（ 0x18F、 18FH ）
R 進制轉(zhuǎn) 10 進制 案例： 6 進制 5043 轉(zhuǎn)為十進制 => 36^0 + 46^1 + 06^2 + 56^3 => 1107
十進制轉(zhuǎn) R 進制 案例：十進制 200 轉(zhuǎn) 6 進制 => 200/6 = 33 余 2 => 33/6 = 5 余 3 => 5/6 = 0 余 5 => 6 進制為余數(shù)的 從后向前排列 532
m 進制轉(zhuǎn)為 n 進制：通過十進制中轉(zhuǎn)
? 數(shù)的表示 （考得少）
最小數(shù)據(jù)單位 b( 比特 bit)
最小存儲單位 1B(字節(jié) byte)=8b
1KB=1024B; 1MB=1024KB; 1GB=1024MB
機器數(shù)：各種數(shù)值在計算機中表示的形式，特點是使用二進制計數(shù)制， 數(shù) 的 符 號 用 0 和 1 表 示 ， 小 數(shù) 點 隱 含 不 占 位 置 （ 例 如 +0 （ 0 0000000 ） -0(1 0000000) ）其中第一位是符號為，后七 位表示數(shù)值位
定點表示法：分為純小數(shù)與純整數(shù)兩種，其中小數(shù)點不占存儲位
純小數(shù)：約定小數(shù)點在機器數(shù)的最高數(shù)值位之前
純整數(shù)：約定小數(shù)點的位置在機器數(shù)的最低數(shù)值位之后
真值：機器數(shù)對應的實際數(shù)值
? 數(shù)的編碼方式（不怎么考）
原碼：一個數(shù)的正常二進制表示 例如 +0 （ 0 0000000 ） -0(1 0000000)
反碼：正數(shù)的反碼即為原碼；負數(shù)的反碼是在原碼的基礎(chǔ)上，除了符 號位以外，其他各位按位取反（例如如上數(shù)值的反碼為 +0 （ 0 0000000） -0 （ 1 1111111 ））
補碼：正數(shù)的補碼即原碼；負數(shù)的補碼是在原碼基礎(chǔ)上，除了符號位 以外，其他各位按位取反，而后在末位 +1 ，若有進位則產(chǎn)生進位 +0 （ 0 0000000 ） -0 （ 0 0000000 ）） -0 的補碼有溢出
移碼：用作浮點運算的階碼，無論正數(shù)負數(shù)，都是將該原碼的補碼的 首位（符號位）取反得到
計算機系統(tǒng)中常采用補碼來表示和運算數(shù)據(jù)，原因是采用補碼可以簡 化計算機運算部件的設(shè)計
? 浮點表示（常考）
浮點數(shù) N = F * 2^E, 其中 E 稱為階碼 ( 帶符號的純整數(shù) ) ， F 稱為尾數(shù)（帶符號的純小數(shù)），類似于十進制的科學記數(shù)法 例如 101.011=0.101011*2^3
浮點數(shù)所能表示的數(shù)值范圍由階碼確定，所表示的數(shù)值精度由尾數(shù)確 定
浮點數(shù)運算需要先 1. 對階，即將階碼換算成相同的后再計算，小階 向大階對接，否則會損失尾數(shù)的精度 》 2. 尾數(shù)計算 》 3. 結(jié)果 格式化
浮點數(shù)存儲格式： | 階符 | 階碼 | 數(shù)符 | 尾數(shù) | ，一般尾數(shù)用補碼，階碼用移碼規(guī)格化浮點數(shù)：將尾數(shù)的絕對值限定在 [0.5, 1]
浮點數(shù)的范圍： M: 尾數(shù)補碼位 ( 包括數(shù)符 ) ， R: 階碼補碼位 ( 包括階符 ) ，則最大正數(shù) +(1-2^-M+1) * 2(2R-1 - 1), 最小負 數(shù) -1 * 2(2R-1 - 1)
定點表示法與浮點表示法：定點表示法分為定點整數(shù)和定點小數(shù)，定 點表示法的小數(shù)點不需要占用存儲位，總位數(shù)相同時浮點表示法可以 表示更大的數(shù)
定點小數(shù)在機器字長為 n 的表示范圍是定點整數(shù)表示范圍除以
2^n-1
? 尋址
立即尋址：操作數(shù)包含在指令中
直接尋址：操作數(shù)存在內(nèi)存單元中，指令中給出操作數(shù)所在存儲單元 的地址
寄存器尋址：操作數(shù)存在某一個寄存器中，指令中給出存放操作數(shù)的 寄存器名，比直接尋址要快，寄存器 " 距離 " CPU 更近
寄存器間接尋址：操作數(shù)存在內(nèi)存單元中，寄存器中存放了操作數(shù)所 在的內(nèi)存地址，指令中則存了寄存器名，也就是說尋址路徑 指令 - > 寄存器 -> 內(nèi)存
間接尋址：指令中給出操作數(shù)地址的地址
尋址效率：立即尋址 > 寄存器尋址 > 直接尋址 > 寄存器間 接尋址 > 間接尋址
采用不同尋址方式的目的：擴大尋址空間，提高編程靈活性
? 校驗碼
碼距：指一個編碼系統(tǒng)中，兩個合法編碼之間至少有多少個二進制不 同
奇偶校驗碼：在編碼中增加一個校驗位來使 1 的個數(shù)為奇數(shù)或者為偶 數(shù)，碼距為 2奇偶校驗只能校驗錯誤不能糾正錯誤
海明碼：一種利用奇偶性來糾錯的校驗方法，碼距為 3 ，設(shè)數(shù)據(jù)位有 n 位，校驗位有 k 位，則 n 與 k 必須滿足以下關(guān)系： 2^k-1 >= n+k
循環(huán)冗余校驗碼(CRC)：可以檢錯但不能糾錯，碼距為 2 ，由 k 個 數(shù)據(jù)位 + r個校驗位組成，校驗碼由信息碼產(chǎn)生，校驗碼位數(shù)越多 校驗能力越強，求 CRC 編碼時，采用模二運算
? RISC 和 CISC
RISC: 精簡指令集計算機，指令少，復雜度低，指令長度固定，尋址 方式少，通用寄存器數(shù)量多，支持流水線技術(shù)，采用硬布線控制邏輯， 組合邏輯控制器
CISC ：復雜指令集計算機，指令多，復雜，指令長度變化，尋址方 式復雜多樣，通用寄存器數(shù)量一般，也支持流水線技術(shù)，使用微程序 控制技術(shù)
? 流水線技術(shù)
流水線：多條指令重疊進行操作的一種準并行處理實現(xiàn)技術(shù)
指令分為三個部分：取指 -> 分析 -> 執(zhí)行
一條完整指令的執(zhí)行時間 = 取指時間 + 分析時間 + 執(zhí)行 時間
流水線周期：指令步驟中所花時間最長的一段，例如：取指 1ms -> 分析 3ms -> 執(zhí)行 2ms 則流水線周期為 3ms，表示除了第一條外， 后邊的指令都只需要多花 3ms 就能完成
流水線總共用時：理論公式：一條完整指令完成時間 + (指令總數(shù) - 1)*流水線周期；實踐公式：給第一條指令充分的時間，及第一條指令的每一個步驟都用一個流水線周期的時間
吞吐率：指單位時間內(nèi)流水線所完成的任務數(shù)量，計算公式：指令條 數(shù) / 流水線總共用時，最大吞吐率 = 1 / 流水線周期
異步控制會延長時間，降低性能，每次操作結(jié)束后要發(fā)出結(jié)束信號
? 存儲器
按照所處位置分類：內(nèi)存；外存
按工作方式分類： 讀 \ 寫存儲器 RAM；只讀存儲器 ROM
按訪問方式分類：按內(nèi)容訪問存儲器（例如：相連存儲器），按地址 訪問存儲器
按尋址訪問存儲器：隨機存儲器、順序存儲器、直接存儲器
閃存，一種只讀存儲器 ROM ，刪除時以塊為單位刪除，類比為 U 盤
虛擬存儲器，由主存 + 輔存 組成
存儲系統(tǒng)的層次結(jié)構(gòu)，由內(nèi)而外： CPU 內(nèi)部通用寄存器 》 Cache(SRAM 靜態(tài)隨機存儲器 ) 》主 \ 內(nèi)存儲器 (DRAM 動態(tài)隨 機存儲器，需要周期性刷新來保持數(shù)據(jù) ) 》外存儲器
空間局部性：若一個存儲單元被訪問，則其臨近的存儲單元在不久的 將來也很可能被訪問，這種特性就是空間局部性
時間局部性：若一個存儲單元被訪問，則這個單元在以后也可能被再 次訪問，這種特性就是時間局部性
? Cache 高速緩存
Cache 高速緩存：位于 CPU 與 主存之間，用來存放當前最活躍的 程序和數(shù)據(jù)（主存的部分拷貝信息），速度比主存塊 5~10 倍，對程 序員來說是透明的（程序員不可操作）
Cache 容量越大，命中率越高，逐漸接近 100% ，但是隨著容量變 大， Cache 成本和命中時間也在增大
替換算法：目標是使 Cache 獲得更高的命中率
隨機替換算法
先進先出算法
近期最少使用算法
優(yōu)化替換算法
Cache 中的地址映像方法
地址映像： CPU 工作時送出的主存地址，而要從 Cache 中讀 寫信息，就需要將主存地址換算成 Cache 地址，這種轉(zhuǎn)換稱為 地址映像
直接映像：主存分區(qū)， Cache分塊，主存每個區(qū)有與 Cache 相 同的分塊，主存每個區(qū)的塊與 Cache 的塊的對應關(guān)系時固定的， 硬件電路簡單，但是沖突率高
全聯(lián)映像：主存不分區(qū)，主存與 Cache按照相同的大小分塊 Cache 的塊可以對應任意的主存上的塊，電路設(shè)計難，只適用于 小容量的 Cache，沖突率低
組相連映像：是直接相連與全聯(lián)映像的折中，先分組，組與組之 間的直接映像，組內(nèi)是全聯(lián)映像
發(fā)生沖突概率：全聯(lián)映像《 組相連映像 《 直接映像
Cache 與 主存之間的映射是由硬件自動完成的
? 中斷
中斷：遇到急需處理的事件時，暫停當前正在運行的程序，轉(zhuǎn)去執(zhí)行 有關(guān)程序，處理完后返回源程序，這個過程稱為中斷
中斷向量：提供中斷服務程序的入口地址
中斷響應時間：發(fā)出中斷請求開始到進入中斷服務程序，這一段時間
保存現(xiàn)場目的：為了能正確的返回被中斷的程序然后繼續(xù)執(zhí)行
7第 1 章 計算機系統(tǒng)知識
? 輸入輸出（ I/O ）控制方式
程序查詢方式（程序直接控制方式）：
CPU 和 I/O 只能串行工作， CPU 需要一直輪詢檢查狀態(tài)， 長期處于忙等狀態(tài)， CPU 利用率低
一次只能讀寫一個字
由 CPU 將數(shù)放入內(nèi)存
中斷驅(qū)動方式：
I/O 設(shè)備通過中斷信號，主動向 CPU 報告 I/O 操作已完成
CPU 與 I/O 外設(shè)可并行操作， CPU 利用率提升
一次只能讀寫一個字
由 CPU 將數(shù)據(jù)放入內(nèi)存
直接存儲器存儲方式（ DMA方式）：
CPU 向 I/O 模塊發(fā)出數(shù)據(jù)讀寫的命令，然后 CPU 就可以做其 他事情， I/O 模塊與內(nèi)存建立直接的數(shù)據(jù)通路， I/O 模塊操 作完成后，通過中斷信號告知 CPU
CPU 與 I/O 外設(shè)可并行工作
由外設(shè)直接將數(shù)據(jù)放入內(nèi)存
一次讀寫的單位是塊而不是字
僅在傳輸數(shù)據(jù)塊的起始和結(jié)束需要 CPU 的干預
CPU 在一個總線周期結(jié)束時響應 DMA 的請求，每傳輸一個數(shù) 據(jù)都要占用一個存儲周期
由 I/O 設(shè)備提出的中斷請求是可屏蔽中斷，電源掉電是不可屏 蔽中斷
? 總線
總線：鏈接計算機有關(guān)部件的一組信號線，是計算機用來傳送信息代 碼的公共通道
總線分類：數(shù)據(jù)總線，地址總線，控制總線
8第 1 章 計算機系統(tǒng)知識
總線的優(yōu)點：簡化系統(tǒng)結(jié)構(gòu)，減少連接線數(shù)目，便于接口設(shè)計，便于 故障診斷和維修，同時降低了成本
總線帶寬計算：時鐘頻率 * 每秒傳送的字節(jié)
地址總線寬度計算：地址總線的寬度表明 CPU 的尋址能力，與內(nèi) 存大小相關(guān)，內(nèi)存多大就需要多寬的地址總線，例如：內(nèi)存容量為 4GB -> 2^32 B -> 地址總線寬度為 32
數(shù)據(jù)總線寬度計算：數(shù)據(jù)總線寬度就是處理機的字長
PCI：并行內(nèi)總線，系統(tǒng)總線； SCSI: 并行外總線
? 加密技術(shù)與認證技術(shù)
加密解決的問題：竊聽
認證解決的問題：篡改、假冒、否認
加密技術(shù)
對稱加密：加密解密用的是同一把秘鑰，且只有一把秘鑰；加解 密速度快，適合大量明文數(shù)據(jù)，秘鑰分發(fā)有缺陷
非對稱加密：加解密不是同一把秘鑰，一共有兩把秘鑰（公鑰私 鑰）；加解密速度慢，秘鑰分發(fā)沒缺陷，公鑰私鑰之間不可推算
混合加密：就是將對稱加密與非對稱加密混合使用：先用對稱加 密將大量明文數(shù)據(jù)加密，再用非對稱公鑰對“對稱加密的秘鑰” 加密，并隨著加密明文一起傳給接收方，接收方使用非對稱的私 鑰解密出 “對稱加密的秘鑰”，再用 “對稱加密的秘鑰” 解密 明文
認證技術(shù)
摘要：將發(fā)送的明文 Hash 算法后得到摘要，放在密文后一起發(fā) 送過去，與接收方解密后的明文 Hash 算法的摘要結(jié)果對比，一 致則沒有篡改
數(shù)字簽名：在摘要的基礎(chǔ)上，對摘要進行私鑰簽名，接收方通過
公鑰對數(shù)字簽名進行解密，可以判定是否被篡改，假冒，否認， 用來驗證消息來源的真實性
數(shù)字證書：使用第三方機構(gòu) CA 的私鑰來對用戶的公鑰進行數(shù)字 簽名，來保證公鑰不被篡改，接收方用 CA 的公鑰解密來得到發(fā) 送方的公鑰
用數(shù)字證書來認證用戶身份，用數(shù)字簽名來防篡改、假冒、否認
加密算法
對稱加密算法（私鑰，私有秘鑰加密，共享秘鑰加密算法）
DES 3DES RC-5 IDEA AES RC4
非對稱加密算嗎（公鑰，公開秘鑰加密）
ECC RSA DSA
Hash 函數(shù)、 MD5摘要算法、 SHA-1 安全散列算法
? 系統(tǒng)可靠性
設(shè)一個系統(tǒng)由 N 個子系統(tǒng)組成，子系統(tǒng)的可靠性分別為 R1 R2 R3
串聯(lián)系統(tǒng)可靠性： R = R1R2R3
并聯(lián)的系統(tǒng)可靠性： R = 1 - (1-R1)(1-R2)(1-R3)
? 其他
指令寄存器的位數(shù)取決于指令字長
計算機分級存儲速度依次為： CPU 內(nèi)部通用寄存器 》 Cache 》內(nèi) 存 》外存
安全需求：
物理線路安全 – 機房安全
網(wǎng)絡安全 – 入侵檢測
系統(tǒng)安全 – 漏洞補丁管理
應用安全 – 數(shù)據(jù)庫安全
10第 1 章 計算機系統(tǒng)知識
第 2章 程序設(shè)計語言
? 低級語言與高級語言
低級語言：機器語言與匯編語言
高級語言：面向應用的各類程序設(shè)計語言，例如 C JAVA Python , 與自然語言比較接近，提高程序設(shè)計效率
高級語言或者匯編語言編寫的叫源程序，源程序不能直接在計算機上 執(zhí)行
? 解釋器（解釋程序）
翻譯源程序時不生成獨立的目標程序
解釋程序和源程序需要參與到程序的運行過程中
? 編譯器（編譯程序）
翻譯時，將源程序翻譯成獨立保存的目標程序
機器上運行的時與源程序等價的目標程序
編譯器與源程序都不參與目標程序的運行過程
? 程序設(shè)計語言的數(shù)據(jù)成分
標識符：由數(shù)字、字母、下劃線組成的標記
常量與變量：按照程序運行時數(shù)據(jù)的值能否改變來區(qū)分，常量存儲在 池中，沒有自己的存儲單元
全局量和局部量：按照數(shù)據(jù)在程序代碼中的作用范圍來劃分
控制結(jié)構(gòu)：順序結(jié)構(gòu)、循環(huán)結(jié)構(gòu)、選擇結(jié)構(gòu)
程序中的數(shù)據(jù)具有類型的作用： 1. 便于為數(shù)據(jù)分配存儲單元； 2. 便于對參與表達式計算的數(shù)據(jù)對象進行檢查； 3. 規(guī)定數(shù)據(jù)對象的取
11第 1 章 計算機系統(tǒng)知識
值范圍以及能夠進行的運算
表達式的左結(jié)合：由左向右執(zhí)行例如： a && b
表達式的右結(jié)合：由右向左執(zhí)行例如： x = y = z
? 傳值調(diào)用和傳址調(diào)用
函數(shù)定義：函數(shù)首部（返回值類型 函數(shù)名 ( 形參 ) ） + 函數(shù)體 ({})
傳值調(diào)用：將實參的值傳給形參，實參可以是常量、變量、表達式，
不可以實現(xiàn)實參形參之間雙向傳遞數(shù)據(jù)的效果
傳址調(diào)用：將實參的地址傳給形參，實參必須有地址，實參不能是常 量（值）或者表達式，可以實現(xiàn)實參形參之間雙向傳遞數(shù)據(jù)的效果， 即改形參的值，實參的值也同時改掉了
? 編譯、解釋程序翻譯階段
編譯方式各個階段：詞法分析 – 語法分析 – 語義分析 – 中間代 碼生成（可省略） – 代碼優(yōu)化（可省略） – 目標代碼生成
解釋方式各個階段：詞法分析 – 語法分析 – 語義分析
編譯器與解釋器都不可省略且變換順序的階段是 詞法分析、語法分析、 語義分析
編譯器的中間代碼生成和代碼優(yōu)化階段不是必要的，可省略
? 符號表的作用
不斷收集、記錄和使用源程序中一些符號的類型和特征信息，將其存 入符號表中
記錄源程序中各個字符的必要信息，以輔助語義的正確性檢查和代碼
生成
12第 1 章 計算機系統(tǒng)知識
? 詞法分析
將源程序看做一個多行的字符串，從上到下、由左到右進行逐個字符 掃描，從中識別出一個個單詞符號（如關(guān)鍵字、標識符、運算符等）
詞法分析分析出的單詞常常以 二元組的形式輸出即 單詞種別和單詞 的值
詞法分析的依據(jù)是語言的詞法規(guī)則
詞法分析輸入的是源程序，輸出的時記號流
詞法分析的主要作用：分析構(gòu)成程序的字符及由字符按照構(gòu)造規(guī)則構(gòu) 成的符號是否符合程序語言的規(guī)定
? 語法分析
在詞法分析基礎(chǔ)上，根據(jù)語言的語法規(guī)則將單詞符號序列分解成各類 語法單位，如 ’表達式‘ ’語句‘ ’程序‘ 等
如果沒有語法錯誤，語法分析后會構(gòu)造出一個語法樹，否則指出錯誤， 給出診斷信息
語法分析輸入的是詞法分析產(chǎn)生的記號流，輸出的時語法樹
語法分析主要作用：對各條語句的結(jié)構(gòu)進行合法性分析，發(fā)現(xiàn)程序中 的所有語法錯誤
? 語義分析
用來檢查源程序是否包含靜態(tài)語義錯誤，主要用來類型分析和檢查
語義分析輸入的是語法分析階段產(chǎn)生的語法樹
語義分析階段不能發(fā)現(xiàn)所有的語義錯誤，只能分析出靜態(tài)的語義錯誤， 動態(tài)的語義錯誤要在運行時才能發(fā)現(xiàn)
動態(tài)語義錯誤常見的有死循環(huán)
13第 1 章 計算機系統(tǒng)知識
? 目標代碼生成
這一個階段的任務是把中間代碼變成特定機器上的絕對指令代碼、可 重定位的指令代碼或匯編指令代碼
目標代碼生成階段的工作與具體的機器密切相關(guān)
寄存器的分配處于目標代碼生成階段
? 中間代碼生成
根據(jù)語義分析的輸出生成中間代碼，是一種簡單的記號系統(tǒng)，可以有 多種形式，其特征是與具體的機器無關(guān)
語義分析和中間代碼生成所依據(jù)的時語言的語義規(guī)則
常見的中間代碼：后綴式、三地址碼、三元式、四元式、樹（圖）等 形式
可以將不同的高級語言編譯成同一種中間代碼
中間代碼可以跨平臺
中間代碼有利于進行與機器無關(guān)的優(yōu)化處理和提高編譯程序的可移植 性
? 正規(guī)式
正規(guī)式是詞法分析的工具
大致可以類比 JS 中的正則的基本規(guī)則，主要記住 * 代表的取值 范圍時 [0, 無窮大 ] ,然后將選項帶入看看符不符合規(guī)則即可
? 有限自動機
有限自動機是詞法分析的工具，他能正確的識別正規(guī)集
狀態(tài)，分為初態(tài)和終態(tài)，一個狀態(tài)既可以是初態(tài)也可以是終態(tài)
識別成功的依據(jù)是：狀態(tài)機的路跑的通并且跑完后的終點是終態(tài)
確定的有限自動機：對每一個字符來說識別字符后的轉(zhuǎn)移狀態(tài)是唯一
14第 1 章 計算機系統(tǒng)知識
的
不確定的有限自動機：對每一個字符來說識別字符，后的轉(zhuǎn)移狀態(tài)是 不唯一的
區(qū)分確定的有限自動機和不確定的有限自動機在于給定一個數(shù)字或者 字母，它只有一條路可以跑，那就是確定的，反之是不確定的
空串
? 上下文無關(guān)文法
被廣泛的用于表示各種程序設(shè)計語言的語法規(guī)則 – 上下文無關(guān)文法
做題：由開始符號起始，推到出選項中的終結(jié)符號，一個選項一個選 項的嘗試
? 后綴式、中綴式
中綴式就是常見的表達式： 1*2
后綴式的符號放在后邊： 12*
中綴式轉(zhuǎn)后綴式：按照 () 、 * /、 + - 的優(yōu)先級，一個表達式 一個表達式的轉(zhuǎn)換成后綴式，同等優(yōu)先級的從右向左轉(zhuǎn)換
后綴式轉(zhuǎn)中綴式：使用棧的方式（先進后出、后進先出）
語法樹中綴遍歷 -> 生成中綴式：左根右
語法樹后綴遍歷 -> 生成后綴式：左右根
后綴式又稱逆波蘭式
? 其他
反編譯通常不能將可執(zhí)行文件還原成高級語言源代碼，只能轉(zhuǎn)換成功 能等價的匯編程序
動態(tài)語言指的是程序運行時可以改變其結(jié)構(gòu)
指針變量：變量是內(nèi)存單元的抽象，用于在程序中保持數(shù)據(jù)，當變量
15第 1 章 計算機系統(tǒng)知識
存儲的時內(nèi)存單元地址時，稱為指針變量
鏈表中的節(jié)點控件需要程序員申請和釋放，數(shù)據(jù)控件應采用堆存儲分 配策略
可視化程序設(shè)計特點：
基于面向?qū)ο笏枷?#xff0c;引入控件概念和事件驅(qū)動
研發(fā)過程遵循，先界面繪制，再基于事件編寫程序代碼
設(shè)計人員可以不用補編寫或者少量編寫代碼
編譯過程中為變量分配存儲單元所用的是邏輯地址，程序運行時再映 射為物理地址
C 中全局變量的存儲空間在靜態(tài)數(shù)據(jù)區(qū)
語法指導翻譯是一種靜態(tài)語義分析方法
語法分析方法：
遞歸下降分析法和預測分析法都是屬于自上而下的分析法
移進 - 歸約分析法屬于自下而上的分析法
16第 1 章 計算機系統(tǒng)知識
第 3章 知識產(chǎn)權(quán)
? 著作權(quán)
著作權(quán)分為人身權(quán)和財產(chǎn)權(quán)
人身權(quán)分為：發(fā)表權(quán)、署名權(quán)、修改權(quán)、保護作品完整權(quán)
除發(fā)表權(quán)外，其他權(quán)利的時限都是永久，發(fā)表權(quán)的時限是終生 + 死后 50 年
知識產(chǎn)權(quán)的地域性：在哪里授予的知識產(chǎn)權(quán)，只在授予國家有效，在 外部國家不受保護
? 計算機軟件著作權(quán)
計算機軟件著作權(quán)受《中華人民共和國著作權(quán)法》和《計算機軟件保 護條例》保護
計算機軟件著作權(quán)的主體是公民
計算機軟件著作權(quán)的客體的是指受保護的計算機程序（源程序和目標 程序）和相關(guān)文檔（流程圖、說明書、用戶手冊）
計算機軟件著作人身權(quán)：發(fā)表權(quán)、開發(fā)者身份權(quán)（署名權(quán)、永久）
計算機軟件著作權(quán)的保護期：自軟件開發(fā)完成之日起，保護期為 50 年，保護期滿，除了開發(fā)者身份權(quán)外，其他權(quán)利終止
《計算機軟件保護條例》是國務院頒布的
侵權(quán)行為鑒別：未經(jīng)著作權(quán)人的同意，發(fā)表、登記、署名、更改、翻 譯、復制、出售、出租
? 職務作品
職務軟件作品指公民在單位任職期間為執(zhí)行本單位的工作所開發(fā)的計 算機軟件作品
17第 1 章 計算機系統(tǒng)知識
公民在單位任職期間所開發(fā)的軟件，著作權(quán)屬于單位。如果開發(fā)軟件 不是職務工作，那著作權(quán)就不是單位所有，但是如果用了單位設(shè)備， 則不能歸個人享有
如果是職務軟件作品，那開發(fā)者只有署名權(quán)
? 委托開發(fā)
委托開發(fā)的作品，著作權(quán)由委托方和受委托方訂立的合同決定，無合 同約定的，著作權(quán)為受委托方所有
? 商業(yè)秘密
商業(yè)秘密的基本內(nèi)容：經(jīng)營秘密和技術(shù)秘密
商業(yè)秘密的構(gòu)成條件：
具有未公開性，不為公眾所知悉
具有實用性，能給權(quán)利人帶來利益
具有保密性，即采取了保密措施
? 專利權(quán)
由書面形式申請的，一份申請一項發(fā)明
專利權(quán)保護期限 20 年（實用新型專利是 10 年）
專利權(quán)就申請之日起算，兩人以上申請，現(xiàn)申請先獲得，同一天申請，
由兩人協(xié)商決定
? 商標權(quán)
自核準之日起， 10 年有效，屆滿前可以續(xù)，每次續(xù) 10 年
誰先注冊，誰享有商標；同時注冊，誰先使用，誰享有商標；同時注 冊，都沒有使用，則協(xié)商或者抓鬮決定
18第 1 章 計算機系統(tǒng)知識
? 軟件許可使用
獨占許可使用：軟件著作權(quán)人不能再給他人許可，軟件著作權(quán)人也不 可使用
獨家許可使用：軟件著作權(quán)人不能再給他人許可，但是軟件著作權(quán)人
可以使用
普通許可使用：軟件著作權(quán)人可以再給他人許可，軟件著作權(quán)人也可 以使用
? 軟件著作權(quán)中的翻譯權(quán)
將軟件從一種程序設(shè)計語言轉(zhuǎn)化成另一種程序設(shè)計語言
19第 1 章 計算機系統(tǒng)知識
第 4章 數(shù)據(jù)庫知識
? 數(shù)據(jù)模型的分類
概念數(shù)據(jù)模型：從信息世界中抽象的數(shù)據(jù)模型，獨立與計算機系統(tǒng)， 一般采用 實體 - 聯(lián)系方法（ E-R 方法）來表示，用于信息世界建 模
結(jié)構(gòu)數(shù)據(jù)模型 ( 數(shù)據(jù)模型 DBSM)：直接面向數(shù)據(jù)庫的邏輯結(jié)構(gòu)，一般 會考察數(shù)據(jù)模型中的關(guān)系模型和相應的關(guān)系模式
? 概念數(shù)據(jù)模型常用術(shù)語
實體：客觀存在相互區(qū)別的事務，例如 一個人，一個單位，一個外部 系統(tǒng)
屬性：用來描述實體的特性，例如 人的姓名，單位的地址
碼 | 鍵：唯一標識實體的屬性或?qū)傩约?/strong>
域：屬性的取值范圍
聯(lián)系：實體之間的對應關(guān)系
? 實體之間的聯(lián)系分為三種
一對一（一個班級對應一個班長）
一對多（一個班級對應多個學生）
多對多（一個老師可以對應多個班級，一個班級也可以有多個老師）
? E-R 圖（實體 - 聯(lián)系）
實體 – 矩形表示
屬性 – 橢圓表示
聯(lián)系 – 菱形表示
20第 1 章 計算機系統(tǒng)知識
使用無向邊鏈接，用 1:n, n:1, n:m 來表示聯(lián)系的類型
結(jié)構(gòu)數(shù)據(jù)模型主要分為：層次模型，網(wǎng)狀模型，關(guān)系模型和面向?qū)ο?模型
? 三級模式和兩級映射
外模式（用戶模式或者子模式）：對應外部視圖，和用戶交互
概念模式：對應數(shù)據(jù)庫基本表
內(nèi)模式（存儲模式）：實際數(shù)據(jù)庫存儲文件
模式 - 內(nèi)模式映像：實現(xiàn)了概念模式和內(nèi)模式之間的轉(zhuǎn)換，保持數(shù)據(jù) 的物理獨立性
外模式 - 模式映像：實現(xiàn)了外模式和概念模式之間的轉(zhuǎn)換，保持數(shù)據(jù) 的邏輯獨立性
? 關(guān)系模型中基本術(shù)語
關(guān)系：一個關(guān)系就是一個二維表
元祖：表中的一行就是一個元祖，對應一個記錄值
屬性：表中的一個列就是一個屬性，列的第一行就是屬性名，其他為 屬性值
域：屬性的取值范圍
關(guān)系模式：對關(guān)系的描述，格式：實體（屬性 1 ，屬性 2 ，…屬性 n ）
候選碼 | 候選鍵：能夠唯一標識一個元祖的屬性或者屬性組合
主碼 | 主鍵：一個關(guān)系中可能會有多個候選碼，從中選擇一個作為主 碼
外碼 | 外鍵：一個關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的碼，但是是別 的關(guān)系中的主碼，則稱其為該關(guān)系的外碼 | 外鍵
全碼：一個候選碼，包含關(guān)系中的所有屬性，則該候選碼為全碼
超碼：包含候選碼的屬性集
21第 1 章 計算機系統(tǒng)知識
主屬性：候選碼中的都是主屬性，其他的時非主屬性
? 關(guān)系模型完整性約束
實體完整性：主鍵的值不能空
參照完整性：外鍵的值可以為空，但是如果有值，則其值一定能在對 應的表中找到
用戶定義完整性：用戶定義的對某一數(shù)據(jù)的指定約束條件
? 關(guān)系代數(shù)運算
∪ ( 并集 ) ： R ∪ S, R,S 所有元祖 | 記錄 合并，刪除重復記 錄后的結(jié)果
－ ( 差 ) ： R-S, 從 R 中刪除存在于 S 中的記錄
∩ ( 交集 ) ： R ∩ S, R,S 中同時存在的記錄組成
× ( 笛卡爾積 ): R × S, R 中每條記錄與 S 中的每條記錄拼接組 合成新的記錄
π ( 投影 ) ： π 1,3 ? 從關(guān)系 R 中抽取第 1 ， 3 列屬 性，組成新的關(guān)系，（其中 1 ， 3 列號，也可以用對一個屬性名 代替）
6 (選擇 ) ： 6 1=5 ? 從關(guān)系 R 中選擇所有第 1 列的值等于 第 5 列值的記錄，組成新的記錄
鏈接：鏈接就是在兩個關(guān)系的笛卡爾積中選擇符合條件的行
等值鏈接：連接條件為兩列值相等
自然鏈接（ |><| ）：不需要寫鏈接條件，自然鏈接中會選出兩個表 中同名屬性對應值相同的記錄，并且生成的新關(guān)系中去除了重復的屬 性列
左外鏈接： R 自然鏈接 S ，在自然鏈接基礎(chǔ)上，將左側(cè)關(guān)系 R 中在自然鏈接結(jié)果中丟失的記錄與自然鏈接結(jié)過拼接的結(jié)果，用空值 NULl 來填充右側(cè)屬性
22第 1 章 計算機系統(tǒng)知識
右外鏈接：與左側(cè)鏈接相反
全外鏈接：左外鏈接與右外鏈接的結(jié)果疊加
? 關(guān)系模式
R 也就是 關(guān)系名 < 屬性組 , 屬性的域 , 屬性到域 的映射 , 屬性組中屬性的數(shù)據(jù)依賴關(guān)系 > 通常 D dom 可以省略， 例如： R<{A, B, C, D}, {A->B, A->C, C->D}> “->” 可以理解為 “推導出”或者“決定”的意思
完整函數(shù)依賴：例如 ( 學號，課程 ) -> 成績，但是單獨的 學號 或 者 課程不能直接推導出 成績，這就是完整函數(shù)依賴
部分函數(shù)依賴：例如（學號，課程號） -> 姓名，單獨的 學號 也可 以推導出 姓名，這就是部分函數(shù)依賴
依賴傳遞： A->B , B->C , 則稱 C 對 A 傳遞依賴
屬性閉包計算（挑選主鍵），由推導關(guān)系選出可以完全推導出所有屬 性集的某個屬性或者某幾個屬性組合，例如： R<{A, B, C, D}, {A- >B, A->C, C->D}> 中 A 屬性可以完全推導出 {A, B, C, D}， A 就是主鍵，有多個情況，則可以有多個候選鍵
冗余函數(shù)依賴：例如 {A->B, B->C, A->C, C->D} 中 A->C 即為冗 余，因為 A->B->C 有傳遞依賴，傳遞依賴優(yōu)先（自己的理解）
? 范式 – 應試技巧
1NF -> 2NF: 消除非主屬性對碼的部分函數(shù)依賴
2NF -> 3NF: 消除非主屬性對碼的傳遞函數(shù)依賴
3NF -> BCNF: 消除主屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴
BCNF -> 4NF: 消除非平凡且非函數(shù)依賴的多值依賴
結(jié)題技巧：
一般都滿足 1NF，除非有類似 工資（基本工資，加班工資，實發(fā) 工資）這種可在細分的屬性
23第 1 章 計算機系統(tǒng)知識
通過函數(shù)依賴集，找到 “碼”，以及主屬性與非主屬性（能被推 導出的屬性都不是主屬性或者碼）
判斷非主屬性是否對碼有部分函數(shù)依賴，即非主屬性是否能通過 碼的一部分就推導出來（如果是 碼中的成員 + 非主屬性 A -> 非主屬性 B 這種則不算部分函數(shù)依賴）符合則至少是 2NF
看有沒有傳遞函數(shù)依賴（類似 A->B, B->C; 或者是偽傳遞時的 某些情況： A->B, BC->D 那么可以有 AC->D），符合則至少是 3NF,
查看主屬性對候選碼是否有部分函數(shù)依賴或者傳遞依賴 , 符合 則至少是 BCNF
看有沒有多值依賴，并且多值依賴的左邊是碼，例如 A->B,A->C, 并且 A 是碼，那就符合第四范式
? 判斷是否為無損連接
直接把分解后的關(guān)系，通過“自然鏈接”鏈接，看看得到的結(jié)果是否 與原來一致，不一致則是有損
? 判斷是否為“保持函數(shù)依賴”
就看分解后的兩個關(guān)系中是有原來函數(shù)依賴集的那些依賴關(guān)系，如果 沒有就是不保持
? 數(shù)據(jù)庫設(shè)計步驟
用戶需求分析 – 數(shù)據(jù)流圖；
概念設(shè)計 – E-R 圖；
邏輯設(shè)計 – 關(guān)系模式
24第 1 章 計算機系統(tǒng)知識
? E-R 模型
實體：矩形表示；
弱實體：雙邊矩形表示，一個實體的存在必須依賴另外一個實體為前 提，這類實體就是弱實體
聯(lián)系：菱形表示，無向邊上標明聯(lián)系的類型 1:n n:1 n:m ，弱實體 的聯(lián)系為雙邊菱形
屬性：橢圓形表示；
簡單屬性：不可再分的屬性；復合屬性：可以細分為更小的部分
多值屬性：雙邊橢圓表示，多值屬性就是一個屬性可以對應一組值，
派生屬性：虛線橢圓表示，可以通過其他屬性計算得來的屬性
? E-R 圖之間的沖突類型
屬性沖突：屬性的類型、取值范圍、數(shù)據(jù)單位沖突
命名沖突：相同意義屬性在不同 E-R 圖中有不同命名
結(jié)構(gòu)沖突：同一個對象在某個 E-R 圖中抽象為實體，在另一個 E-R 圖中抽象為屬性，或者同一實體在不同 E-R 中有不同屬性
? 關(guān)系模型轉(zhuǎn)換
1:1 關(guān)系轉(zhuǎn)換為關(guān)系模式：把聯(lián)系對應的屬性放到任意一個實體中， 同時將另外的實體的主鍵也放到這個實體中
1:n 關(guān)系轉(zhuǎn)換為關(guān)系模式：把聯(lián)系對應的屬性放到 n 對應的實體 中，同時將另外的實體的主鍵也放到這個實體中
n:n 關(guān)系轉(zhuǎn)換為關(guān)系模式：把聯(lián)系單獨作為一個新的關(guān)系 , 其他 實體的主鍵組合為這個新關(guān)系的主鍵
關(guān)系模式規(guī)范化的要求：至少滿足 3NF
25第 1 章 計算機系統(tǒng)知識
? 事務管理的特性
原子性：事務是原子的，要么都做，要么都不做
一致性：事務執(zhí)行的結(jié)果必須保證從一個一致性狀態(tài) 變到另一個一致 性狀態(tài)
隔離性：事務間互相隔離，多個事務并發(fā)時，任意事務的變更操作知 道其成功提交的整個過程對其他事務都是不可見的
持久性：一旦事務成功提交，即使數(shù)據(jù)庫崩潰，其對數(shù)據(jù)庫的更新操 作也永久有效
? 數(shù)據(jù)庫備份方法
靜態(tài)轉(zhuǎn)儲與動態(tài)轉(zhuǎn)儲，動態(tài)指在轉(zhuǎn)儲期間允許對數(shù)據(jù)庫的存取修改操 作，靜態(tài)則不允許
海量存儲與增量存儲，增量是指僅轉(zhuǎn)儲距離上次轉(zhuǎn)儲更新的數(shù)據(jù)
日志文件，把對數(shù)據(jù)庫的每次操作寫入日志文件，一旦發(fā)生故障，則 利用日志文件撤銷事務，回退到事務前的數(shù)據(jù)狀態(tài)
? 封鎖
排它鎖：就是加了這個鎖那么其他的排它鎖和共享鎖都不能加了，直 到這個鎖被釋放了才可以加其他的排它鎖和共享鎖
共享鎖：就是加了這個鎖那么不能加排它鎖，但是可以加共享鎖，直 到這個鎖被釋放了才可以加排它鎖
? 分布式數(shù)據(jù)庫
分片透明：指不需要知道表具體是如何分塊存儲的
復制透明：采用復制技術(shù)的分布式方法時，用戶不需要知道復制到了 那些節(jié)點，和如何復制的
位置透明：無需知道數(shù)據(jù)存放的物理位置
26第 1 章 計算機系統(tǒng)知識
邏輯透明：無需知道局部使用的時那種數(shù)據(jù)模型
共享性：數(shù)據(jù)存儲在不同的節(jié)點數(shù)據(jù)共享
自治性：每個節(jié)點對本地數(shù)據(jù)獨立管理
可用性：某一個場地故障，系統(tǒng)可以使用其他場地的副本而不至于整 個系統(tǒng)癱瘓
分布性：數(shù)據(jù)在不同場地存儲
? 存儲過程
存儲過程是在大型數(shù)據(jù)庫系統(tǒng)中，一組為完成特定功能的 SQL語句集
通過提供存儲過程讓第三方調(diào)用，將需要更新的數(shù)據(jù)傳入存儲過程， 從而避免了向第三方提供系統(tǒng)的表結(jié)構(gòu)，保證了系統(tǒng)的數(shù)據(jù)安全
27第 1 章 計算機系統(tǒng)知識
第 5章 面向?qū)ο蠡A(chǔ)
? 面向?qū)ο蠡靖拍?/strong>
如何識別是面向?qū)ο?#xff1a;對象 + 分類 + 繼承 + 通過消息的通 信
類：定義了一組大體上相似的對象，是一組對象的抽象
類分為三種
實體類：表示顯示世界中的真實實體，如人物等
接口類（邊界類）：為用戶提供一種與系統(tǒng)合作交互的方式，例 如 二維碼、條形碼等
控制類：用來控制活動流，充當協(xié)調(diào)者
對象：是基本的運行時實體，一個對象中既有屬性又有行為（作用于 數(shù)據(jù)的操作），一個對象通?？捎?strong>對象名、屬性、方法組成
消息：是對象之間通信的一種構(gòu)造
重載：是在同一個位置上一系列 方法名相同，但是形參類型或者個數(shù) 不同的方法
封裝：是一種信息隱蔽技術(shù)，目的是使對象的使用者和生產(chǎn)者分離， 使對象的定義和實現(xiàn)分開
繼承：是父類和子類之間共享數(shù)據(jù)和方法的機制，一個父類可以有多 個子類，這些子類都是父類的特例，父類描述了子類的公共屬性和方 法
一個子類有一個父類叫單重繼承，一個子類有多個父類叫多重繼承， 多重繼承可能導致子類中存在二義性的成員
覆蓋：一個繼承關(guān)系中，子類以更具體的方式實現(xiàn)從父類繼承的方法， 稱為覆蓋或者重寫
多態(tài)：收到消息是對象要予以響應，不同的對象收到同一個消息可以 產(chǎn)生完全不同的結(jié)果，這個現(xiàn)象稱為多態(tài)，
多態(tài)的實現(xiàn)受繼承支持，利用繼承的層次關(guān)系，將具有通用功能的消
28第 1 章 計算機系統(tǒng)知識
息放在高層次，將不同的實現(xiàn)放在低層次，這些低層次生成的對象能 夠給消息不同的響應
多態(tài)的四類形式：
通用多態(tài)：參數(shù)多態(tài)（應用最廣泛）、包含多態(tài)（常見的例子： 子類型化）
特定多態(tài)：過載多態(tài)（同一個名字在不同的上下文所代表含義不 同）、強制多態(tài)
? 靜態(tài)綁定和動態(tài)綁定
綁定就是一個方法的調(diào)用與調(diào)用這個方法的類連接在一起的過程
靜態(tài)綁定，就是在程序運行前，編譯階段就能夠確定方法由誰調(diào)用
動態(tài)綁定，在運行時根據(jù)具體的對象類型進行綁定，動態(tài)綁定支持繼 承和多態(tài)
? 面向?qū)ο笤O(shè)計原則
單一職責原則：一個類僅有一個引起他變化的原因，一個類只做一種 類型責任
開放 - 封閉原則：軟件實體應該是可擴展的（開放），但是不可修改
（封閉）
里式替換原則：子類必須要能夠完全替代父類
依賴倒置原則：抽象不應該依賴于細節(jié)，細節(jié)應該依賴于抽象；高層 模塊不應依賴于低層模塊，二者都應該依賴于抽象
接口分離原則：接口屬于客戶，不屬于它所在的類層次結(jié)構(gòu)，抽象級 別不應有對細節(jié)的依賴
共同封閉原則：一個變化如果對一個包產(chǎn)生影響，則將對該包中的所 有類產(chǎn)生影響，而對于其他包不產(chǎn)生影響
共同重用原則：如果重用包中的一個類，那么就要重用包中的所有類
29第 1 章 計算機系統(tǒng)知識
? 面向?qū)ο蠓治?/strong>
面向?qū)ο蠓治龅哪康?#xff1a;為了獲得對應用問題的理解
面向?qū)ο蠓治龅奈鍌€活動：認定對象 – 組織對象 – 描述對象間的 相互作用 – 確定對象的操作 – 定義對象的內(nèi)部信息
認定對象：用來定義問題域，以自然存在的 名詞作為一個對象
定義領(lǐng)域模型是面向?qū)ο蠓治龅年P(guān)鍵步驟之一，它按照對象分類的角 度來創(chuàng)建對象領(lǐng)域的描述，包括定義概念、屬性和重要的關(guān)聯(lián)，其結(jié) 果用類圖來組織
? 面向?qū)ο笤O(shè)計
基于面向?qū)ο蠓治龅慕Y(jié)果，將分析結(jié)果，轉(zhuǎn)化為設(shè)計模型，定義系統(tǒng) 構(gòu)造藍圖
面向?qū)ο笤O(shè)計：獲得對應問題的解決方案，實現(xiàn)系統(tǒng)，關(guān)注技術(shù)及實 現(xiàn)層面的細節(jié)
面向?qū)ο笤O(shè)計的五個活動：識別類及對象 – 定義屬性 – 定義服務 – 識別關(guān)系 – 識別包
? 面向?qū)ο蟪绦蛟O(shè)計
實質(zhì)是選用一種面向?qū)ο笳Z言，采用 對象、類等相關(guān)概念所進行的程 序設(shè)計
? 面向?qū)ο鬁y試
面向?qū)ο鬁y試的四個層次：算法層 – 類層 – 模板層 – 系統(tǒng)層
30第 1 章 計算機系統(tǒng)知識
第 6章 UML
? UML 概念
UML 詞匯表包含三種構(gòu)造塊：事務（對模型中最具代表性的成分抽 象）、關(guān)系（把事務結(jié)合在一起）、圖（聚集相關(guān)的事務）
? UML 事務
結(jié)構(gòu)事務：模型的靜態(tài)部分，名詞，描述概念或物理元素，包括 類、 接口、用例、構(gòu)件等
行為事務：模型的動態(tài)部分，動詞，描述跨越時間空間的行為，包括 交互、狀態(tài)機、活動等
分組事務：模型的組織部分，最主要的分組事務是包，結(jié)構(gòu)事務、行 為事務或者其他分組事務都可以放在包里
注釋事務：模型的解釋部分，用來描述、說明、標注，注解是最主要 的注釋事務
? UML 關(guān)系
依賴關(guān)系：是兩個事務之間的語義關(guān)系，一個事務（獨立事務）發(fā)生 變化，會影響另一個事務（依賴事務）的語義；
- 圖形上通過虛線 + 箭頭實現(xiàn)
- A( 依賴事務 ) ·······> B( 獨立事務 ) A 依賴于 B ， B 事務的變化會引起 A 事務的語義變化
關(guān)聯(lián)關(guān)系：是一種結(jié)構(gòu)關(guān)系，描述了一組鏈，鏈是對象之間的鏈接， 通常分為聚合關(guān)系和組合關(guān)系，描述了整體和部分之間的關(guān)聯(lián)
- 單向關(guān)聯(lián)：實線 + 箭頭 A() ——————> B() ，它使得一個 類知道另一個類的屬性和方法， A 類依賴于 B 對象，并把 B 作
31第 1 章 計算機系統(tǒng)知識
為 A 的一個成員變量，則 A ， B 存在關(guān)聯(lián)關(guān)系，關(guān)聯(lián)可以是單 向的也可以是雙向的（雙向關(guān)聯(lián)不用箭頭）
- 雙向關(guān)聯(lián)： 實線 A —————— B ，關(guān)聯(lián)多重度位于實線的 上方，表示一個 A 類實例可以關(guān)聯(lián)多少個 B 類實例，一個 B 類 實例又可以關(guān)聯(lián)多少個 A 類實例，通常多重度可以用 （ 1 *） （ 1 1…* ）等表示 , 多對多的雙向關(guān)聯(lián)，一般可以將關(guān)聯(lián)關(guān) 系提取出一個“關(guān)聯(lián)類” - 聚合關(guān)系 : 實線 + 空菱形 A( 部分 ) ——————<> B( 整體 ) 整體的生命周期與部分不同步，整體消失，部分依 然可以存在 - 組合關(guān)系：實線 + 實心菱形 A( 部分 ) ——————<+>( 實 心菱形不好畫，用 <+>代替 ) B( 整體 ) 整體生命周期與部 分同步，整體消失，部分也消失
泛化關(guān)系：是一種 “特殊” 和 “一般” 之間的關(guān)系，特殊元素 （子）的對象可以替代一般元素（父）的對象，子元素共享了父元素 的結(jié)構(gòu)和行為 - 圖形上通過 實線 + 空心三角箭頭 - A( 特殊、子 ) ———————|> B( 一般、父 )
實現(xiàn)關(guān)系：是類元之間的語義關(guān)系，其中一個類元指定了由另一個類 元保證執(zhí)行的契約
- 通常的使用情況: 1. 接口和實現(xiàn)他們的類或構(gòu)件之間； 2. 用 例和實現(xiàn)他們的協(xié)作之間 - 圖形上通過 虛線 + 空心三角箭頭 - A( 類 ) ········|> B( 接口 )
? 類圖（靜態(tài)）
類圖：展現(xiàn)了一組對象、接口、協(xié)作和他們之間的關(guān)系，類圖中可以 包含注解和約束，也可以有包或子系統(tǒng)
類圖對靜態(tài)設(shè)計視圖建模的三種方式
32第 1 章 計算機系統(tǒng)知識
對系統(tǒng)詞匯建模
對簡單的協(xié)作建模
對邏輯數(shù)據(jù)庫模式建模
類圖中類的組成
第一層 類名
第二層 屬性名 ( 屬性名 1: 屬性的類型 )
第三層 方法名 （方法名 1(): 方法返回值類型），其中屬性名 和方法名前可以有修飾符 + public 公有的； - private 私 有的； # protected 受保護的；
? 對象圖（靜態(tài)）
對象圖：展現(xiàn)了某一時刻，一組對象及他們之間的關(guān)系
對象圖中對象與類圖中類的區(qū)別：對象分為兩層，第一層是 對象名
( 對象名 : 類名 ) ， 第二層 屬性
? 用例圖（靜態(tài)）
用例圖：展現(xiàn)了一組用例、參與者、以及他們之間的關(guān)系
參與者：參與者是與系統(tǒng)交互的外部實體，可以是使用者或者參 與系統(tǒng)交互的外部系統(tǒng)，基礎(chǔ)設(shè)備等
用例：是從用戶角度描述的系統(tǒng)行為，用例是一個類，代表了一 類功能，而不是該功能的某一個具體實現(xiàn)
包含關(guān)系：用例與用例之間的關(guān)系，圖形上使用虛線 + 箭頭 + 《 include 》 表 示 ： A （ 基 本 用 例 ） ··· 《 include》 ···> B （被包含用例） , 箭頭指向被包含的用 例， A 用例包含 B 用例，則 A 執(zhí)行用例 B 一定也會被執(zhí)行
擴展關(guān)系：用例與用例之間的關(guān)系，圖形上使用虛線 + 箭頭 + 《 extend 》 表 示 ： A （ 擴 展 用 例 ） ··· 《 extend 》 ···> B （被擴展用例） , 箭頭指向被擴展的
33第 1 章 計算機系統(tǒng)知識
用例，被擴展后的用例 B 在執(zhí)行時可能會遇到特殊的情況或者可選的 情況，這個時候就可以用 擴展用例
包含關(guān)系與擴展關(guān)系區(qū)分：
區(qū)分包含關(guān)系：使用某個用例，必然會使用另外一個用例
區(qū)分擴展關(guān)系：當執(zhí)行某個用例，不一定要去執(zhí)行另外一個用例
? 序列圖（動態(tài)）
序列圖，描述了以時間順序組織的對象之間的交互活動，序列圖是對 一個用例進行詳細過程的分解
圖形上，參與交互的對象放在圖的上方，沿水平方向排列，發(fā)起交互 的對象放左邊；然后把對象間發(fā)送和接收的消息，按照時間順序由上 到下排列
對象生命線：由對象起始的一條垂直向下的虛線，表示對象在一段時 間內(nèi)存在
控制焦點：對象生命線之上的一段瘦高的矩形，表示對象執(zhí)行一個動 作所經(jīng)歷的時間段
調(diào)用消息用實線 + 箭頭表示，返回消息用 虛線 + 箭頭表示
調(diào)用消息所要執(zhí)行此消息方法的是箭頭指向的對象
? 通信圖（動態(tài)）
通信圖也成協(xié)作圖，強調(diào)收發(fā)消息對象的結(jié)構(gòu)組織
通信圖與序列圖的不同，在于通信圖有路徑、通信圖有順序號，延同 一個鏈可以展示許多消息，每個消息都有唯一的順序號
通信圖與順序圖是同構(gòu)的，可以相互轉(zhuǎn)換
通信圖展現(xiàn)了對象間的消息流及其順序
34第 1 章 計算機系統(tǒng)知識
? 狀態(tài)圖（動態(tài)）
狀態(tài)圖展現(xiàn)了一個狀態(tài)機，它由狀態(tài)、轉(zhuǎn)換、事件和活動組成
狀態(tài)圖對系統(tǒng)的動態(tài)方面建模
當對系統(tǒng)、類或用例的動態(tài)方面建模時。通常是對反應型對象建模
狀態(tài)：任何可以被觀察到的系統(tǒng)行為模式，一個狀態(tài)代表系統(tǒng)的一種 行為模式
狀態(tài)分為初態(tài)（實心圓）終態(tài)（實心圓外再加一層圓）和中間狀 態(tài)
狀態(tài)圖中的狀態(tài)是一個圓角矩形，第一層是狀態(tài)名，中間一層時
狀態(tài)變量（可以沒有），最后一層為活動表（也可以沒有）
狀態(tài)之間用帶箭頭的線表示 “轉(zhuǎn)換（遷移）” 箭頭線上的事件 發(fā)生時，轉(zhuǎn)換開始
一個狀態(tài)圖只能有一個初態(tài)，可以有多個終態(tài)或者沒有終態(tài)
活動：由 “事件名 / 動作表達式” 組成 位于狀態(tài)的活動表中 , 有 如下三種標準事件
entry: 入口動作，進入狀態(tài)，立即執(zhí)行
do: 內(nèi)部活動，占用有限時間，可以中斷工作
exit:出口動作，退出狀態(tài)，立即執(zhí)行
事件：某個特定時刻發(fā)生的時間，它是對引起系統(tǒng)做動作，和一個狀 態(tài)轉(zhuǎn)換成另一個狀態(tài)的事件的抽象
轉(zhuǎn)換由 “事件（監(jiān)護條件） / 動作” 組成
轉(zhuǎn)換包括兩個狀態(tài)
事件觸發(fā)轉(zhuǎn)換
活動（動作）可以在狀態(tài)內(nèi)執(zhí)行也可以在狀態(tài)轉(zhuǎn)換時執(zhí)行
監(jiān)護條件是一個 boolean 表達式
“事件”發(fā)生且“監(jiān)護條件為真”狀態(tài)轉(zhuǎn)換才發(fā)生，狀態(tài)轉(zhuǎn)換開 始后才會執(zhí)行“動作”
組合狀態(tài)：一組狀態(tài)轉(zhuǎn)換作用矩形包圍，作為另一個狀態(tài)圖中的一個
35第 1 章 計算機系統(tǒng)知識
狀態(tài)存在
組合狀態(tài)中的所有子狀態(tài)完成，才會走組合狀態(tài)外的其他狀態(tài)
? 活動圖（動態(tài)）
活動圖展現(xiàn)了系統(tǒng)從一個活動到另外一個活動的流程，對系統(tǒng)的功能 建模很重要，強調(diào)了對象間的控制流程
活動圖有起始、終止、圓角矩形組成的活動、實線 + 箭頭組成的流、 并發(fā)分叉、并發(fā)匯合、分支、分支上的監(jiān)護表達式組成
用活動圖來對工作流建模、對操作建模
并發(fā)分叉后直接相連的活動可同時執(zhí)行
? 構(gòu)件圖（靜態(tài)）
構(gòu)件圖也稱為組件圖，展現(xiàn)了一組構(gòu)件之間的組織和依賴
與類圖相關(guān)，通常把構(gòu)件映射為一個或多個類、接口或者協(xié)作
構(gòu)件圖有特殊的標記，構(gòu)件圖之間通過 供接口（空心圓）和 需接口 （圓弧）對接，供接口提供相應的方法實現(xiàn)，需接口來調(diào)用這個方法
? 部署圖
部署圖用來對系統(tǒng)物理層面建模
部署圖立體圖形，《 artifact 》表示制品
部署圖展現(xiàn)了系統(tǒng)軟件和硬件間關(guān)系，在實施階段使用
部署組件之間的關(guān)系類似包依賴
? 總結(jié)
靜態(tài)建模：類圖、對象圖、用例圖
動態(tài)建模：序列圖、通信圖、狀態(tài)圖、活動圖
物理建模：構(gòu)件圖、部署圖
36第 1 章 計算機系統(tǒng)知識
交互圖：序列圖（順序圖、時序圖）、通信圖（協(xié)作圖）
37第 1 章 計算機系統(tǒng)知識
第 7章 設(shè)計模式
? 創(chuàng)造型設(shè)計模式
概念：創(chuàng)造型設(shè)計模式抽象了實例化過程，幫助一個系統(tǒng)如何創(chuàng)建、 組合、和表示那些對象
? 簡單工廠模式
定義一個工廠類，可以根據(jù)傳入的參數(shù)的不同，返回不同類的實例， 這些“不同類”繼承自同一個父類
工廠類中創(chuàng)建實例的方法通常是一個靜態(tài)方法，因此又稱為靜態(tài)工廠
使用者無需知道產(chǎn)品對象是如何創(chuàng)建的
? 工廠方法模式（ Factory Method ）
在簡單工廠基礎(chǔ)上，定義一個用于創(chuàng)建對象的工廠接口，讓實現(xiàn)這個 接口的子類來決定實例化哪個類
工廠方法模式使一個類的實例化延遲到了子類
適用性：
當一個類不知道它所必須創(chuàng)建的對象的類的時候
當一個類希望由他的子類來指定它所創(chuàng)建的對象的時候
? 抽象工廠模式 (Abstract Factory)
意圖：提供一個創(chuàng)建一系列相關(guān)或相互依賴對象的接口，而無需指定 他們具體的類
可以理解為：“工廠方法” 創(chuàng)建的是一中對象，“抽象工廠” 創(chuàng)建 的是一系列對象
適用性：（抽工獨立組合多個產(chǎn)品，聯(lián)合顯示接口不實現(xiàn)）
38第 1 章 計算機系統(tǒng)知識
一個系統(tǒng)要獨立于它的產(chǎn)品創(chuàng)建、組合和表示時
一個系統(tǒng)要由多個產(chǎn)品系列中的一個來配置時
當要強調(diào)一系列相關(guān)產(chǎn)品對象的設(shè)計以便進行聯(lián)合使用時
當提供一個產(chǎn)品類庫，只想顯示他們的接口而不是實現(xiàn)時
? 生成器模式 (Builder)
意圖：將一個復雜對象的構(gòu)建和他的表示分離，使得同樣的構(gòu)建過程
可以創(chuàng)建不同的表示
理解：定義一個抽象的生成器；再定義多個具體的生成器類（封裝對 象復雜的算法）來繼承它；定義一個管理者（對象裝配）來操作生成 器，這樣管理者與不同的生成器類組合就可以創(chuàng)建不同的產(chǎn)品表示
適用性：（生成復雜算法，構(gòu)造對象不同）
當創(chuàng)建對象的復雜的算法應該獨立于該對象的組成部分和裝配方 式時
當構(gòu)造過程必須允許被構(gòu)造對象有不同表示時
? 原型模式 (Prototype)
意圖：用原型實例指定創(chuàng)建對象的種類，通過復制這些原型創(chuàng)建新的 對象
適用性：（原型獨立構(gòu)成，運行指定，不同組合狀態(tài)）
當一個系統(tǒng)應該獨立于它的產(chǎn)品創(chuàng)建、構(gòu)成和表示時
當要實例化的類是在運行時刻指定的，例如動態(tài)裝載
當一個類的實例只能有幾個不同狀態(tài)組合中的一種
? 單例模式 (Singleton)
意圖：保證一個類僅有一個實例，并提供一個訪問它的全局訪問點
適用性：（單例有一個實例）
39第 1 章 計算機系統(tǒng)知識
當類只能有一個實例，且客戶從一個眾所周知的訪問點訪問它時
? 結(jié)構(gòu)型設(shè)計模式
概念：涉及如何組合類和對象，以獲得更大的結(jié)構(gòu)
? 適配器模式 (Adapter)
意圖：將一個類的接口轉(zhuǎn)換成用戶希望的另一個接口，使得原本由于 接口不兼容不能一起工作的那些類可以一起工作
適用性：（適配接口不符合）
想使用一個已存在的類，但是接口不符合要求
? 橋接模式 (Bridge)
意圖：將抽象部分與實現(xiàn)部分分離，使他們都可以獨立的變化
理解：通過聚合或組合關(guān)系，將一個有多種組合情況的類拆分成幾個 相互關(guān)聯(lián)的類，這個每個類各自可以獨立變化
適用性：（橋接綁定以擴充，不影響不編譯類層次）
不希望在抽象和他的實現(xiàn)部分之間有一個固定的綁定關(guān)系
類的抽象和它的實現(xiàn)都可以通過生成子類的方法加以擴充
對抽象的實現(xiàn)部分的修改應該對客戶不產(chǎn)生影響，不必重新編譯
有許多類要生成的類層次結(jié)構(gòu)
? 組合模式 (Composite)
意圖：將對象組合成樹型結(jié)構(gòu)，以表示 部分–整體 的層次結(jié)構(gòu)，使 得用戶對單個對象和組合對象的使用具有一致性
理解：以文件夾與文件間的關(guān)系去理解
適用性：（組合部分整體，使用組合對象）
想要表示對象的部分–整體層次結(jié)構(gòu)
40第 1 章 計算機系統(tǒng)知識
希望用戶忽略組合對象與單個對象間的不同，統(tǒng)一的使用組合中 的所有對象
? 裝飾器模式 (Decorator)
意圖：動態(tài)的給一個類添加一些額外的職責
適用性：（裝飾添加和撤銷職責，不能擴充）
在不影響其他對象的情況下，動態(tài)透明的方式給單個對象添加職 責
處理那些可以撤銷的職責
當不能采用生成子類的方式進行擴充時
? 外觀模式 (Facade)
意圖：為子系統(tǒng)中的一組接口提供一個一致的界面，定義一個高層接 口，使得子系統(tǒng)更加容易使用
適用性：（外觀子系統(tǒng)簡單接口，依賴構(gòu)建層次結(jié)構(gòu)入口點）
要為一個復雜的子系統(tǒng)提供一個簡單的接口時
客戶程序與抽象類的實現(xiàn)部分之間存在很大的依賴性
當需要構(gòu)建一個層次結(jié)構(gòu)的子系統(tǒng)時，使用外觀模式定義子系統(tǒng) 每層的入口點
? 享元模式 (Flyweight)
意圖：運用共享技術(shù)，有效的支持大量細粒度的對象
理解：用一個享元工廠來創(chuàng)建并維護實例，一種實例只創(chuàng)建一個，后 續(xù)創(chuàng)建都是直接返回已創(chuàng)建的實例
適用性：（享元大量開銷，外部狀態(tài)取代多組對象）
一個應用程序使用了大量的對象
由于使用了大量的對象，造成了很大的存儲開銷
41第 1 章 計算機系統(tǒng)知識
對象的大多數(shù)狀態(tài)都可以變?yōu)?strong>外部狀態(tài)
如果刪除對象的外部狀態(tài)，那么可以用相對較少的共享對象取代 很多組對象
? 代理模式 (Proxy)
理解：為其他對象提供一種代理，以控制對這個對象的訪問
適用性：（代理簡單的指針）
在需要比較通用和復雜的對象指針代替簡單的指針的時候
? 行為型設(shè)計模式
概念：涉及算法和對象間職責的分配，描述了它們之間的通信模式， 使用繼承機制在對象間分配行為
? 責任鏈模式 (Chain of Responsibility)
意圖：使多個對象都有機會處理請求，從而避免請求的發(fā)送者和接收 者之間的耦合關(guān)系，將對象連城一條鏈，沿著鏈傳遞請求，直到有一 個對象處理它為止
適用性：（責任鏈請求自動確定，不明確接收者動態(tài)指定）
有多個對象處理一個請求，哪個對象處理該請求在運行時自動確定
想在不明確指定接受者的前提下向多個對象中的一個提交請求
可處理一個請求的對象集合被應動態(tài)指定
? 命令模式 (Command)
意圖：將一個請求封裝成一個對象，從而使得可以用不同的請求對客
42第 1 章 計算機系統(tǒng)知識
戶進行參數(shù)化，對請求排隊、記錄請求日志、以及支持可撤銷的操作
適用性：（命令參數(shù)化，指定排列，取消操作修改）
抽象出待執(zhí)行的動作以參數(shù)化某對象
在不同的時刻指定、排列和執(zhí)行請求
支持取消操作、修改日志
? 解釋器模式 (Interpreter)
意圖：給定一個語言，定義它的文法的一種表示，并定義一個解釋器， 解釋語言中的句子
適用性：（解釋抽象語法樹）
當一個語言需要解釋執(zhí)行時，可將語言中的句子表現(xiàn)為一個抽象 語法樹
? 迭代器模式 (Iterator)
意圖：提供一種方法順序的訪問一個聚合對象中的各個元素，且不需 要暴露該對象的內(nèi)部表示
適用性：（迭代聚合無需暴露。多種遍歷統(tǒng)一接口）
訪問一個聚合對象的內(nèi)容而無需暴露它的內(nèi)部表示
支持對聚合對象的多種遍歷
為遍歷不同的聚合結(jié)構(gòu)提供一個統(tǒng)一的接口
? 中介模式 (Mediator)
意圖：用一個中介對象來封裝一系列的對象交互，中介者使得各個對 象不需要顯示的相互引用，從而使其耦合松散，而且可以獨立的改變 它們之間的交互
適用性：（中介復雜通信，依賴難以理解）
一組對象定義良好，但是以復雜的方式進行通信，產(chǎn)生的相互依
43第 1 章 計算機系統(tǒng)知識
賴關(guān)系結(jié)構(gòu)混亂且難以理解
? 備忘錄模式 (Memento)
意圖：在不破壞封裝性的前提下，捕獲一個對象的內(nèi)部狀態(tài)，并在對 象之外保存，這樣以后就可以將對象恢復到原先保存的狀態(tài)
適用性：（備忘錄某一時刻狀態(tài)，破壞封裝性）
必須保存一個對象在某一時刻的（部分）狀態(tài)，這樣以后在需要 時才能恢復之前的狀態(tài)
如果用一個接口來讓其他對象直接得到這些狀態(tài)，將會暴露對象 的實現(xiàn)細節(jié)，并破壞對象的封裝性
? 觀察者模式 (Observer)
意圖：定義對象間的一對多的依賴關(guān)系，當一個對象發(fā)生改變時，所 有依賴它的對象都得到通知，并自動更新
適用性：（觀察者改變其他對象，不是耦合的）
當一個對象的改變需要同時改變其他對象，而不知道具體有多少 對象待改變時
當一個對象必須通知其他對象，而它又不能假定其他對象是誰， 即不希望這些對象是緊耦合的
? 狀態(tài)模式 (State)
意圖：允許一個對象再其內(nèi)部狀態(tài)改變時改變它的行為，對象似乎修 改了它的類
適用性：（狀態(tài)改變行為，多分支語句依賴狀態(tài)）
一個對象的行為決定于它的狀態(tài)，并且必須在運行時刻根據(jù)狀態(tài) 改變它的行為
一個操作中含有龐大的多分支條件語句，這些分支依賴于該對象
44第 1 章 計算機系統(tǒng)知識
的狀態(tài)。
? 策略模式 (Strategy)
意圖：定義一系列算法，把他們一個個封裝起來，并使得他們可以相 互替換，此模式使得算法可以獨立于使用他們的客戶而變化
適用性：（策略多個行為，算法變體避免暴露，多條件語句）
許多相關(guān)的類僅僅是行為有異，策略提供了一種用多個行為中的 一個行為來配置一個類的方法
需要使用一個算法的不同變體
使用算法的客戶不應該知道數(shù)據(jù)結(jié)構(gòu)，避免暴露
一個類中定義了多種行為，這些行為在這個類的操作中以多個條 件語句的形式出現(xiàn)，將相關(guān)的條件分支移入他們各自的策略類中 以代替這些條件語句
? 模板方法 (Template Method)
定義一個操作中的算法骨架，而將一些步驟延遲到子類中，使得一個 子類可以不改變一個算法的結(jié)構(gòu)即可重新定義該算法的某些步驟
適用性：（模板可變給子類，避免代碼重復，子類擴展）
一次性實現(xiàn)一個算法的不變的部分，并將可變的行為留給子類實 現(xiàn)
各子類中的公共行為應被提取出來并集中到一個公共的父類，以 避免代碼重復
控制子類擴展，模板方法僅允許在特定點進行擴展
? 訪問者模式 (Visitor)
意圖：表示一個作用于某對象結(jié)構(gòu)中的各元素的操作。允許在不改變 各元素類的前提下，定義作用于這些元素的新操作
45第 1 章 計算機系統(tǒng)知識
適用性：（訪問者依賴具體類，不相關(guān)對象的類，定義新的操作）
一個對象結(jié)構(gòu)包含很多類對象，他們有不同的接口，而用戶想對 這些對象實施一些依賴于其具體類的操作
需要對一個對象結(jié)構(gòu)中的對象，進行很多不同的并且不相關(guān)的操 作，而有不想這些操作污染這些對象的類
定義對象的類很少改變，但經(jīng)常需要在此結(jié)構(gòu)上定義新的操作
46第 1 章 計算機系統(tǒng)知識
第 8章 信息安全
? 防火墻
防火墻建立在內(nèi)外網(wǎng)絡邊界上的過濾封鎖機制，認為內(nèi)部網(wǎng)絡是安全 可信賴的，外部網(wǎng)絡是不安全和不可信任的
防火墻對通過受控干線的任何通信進行安全處理，例如：控制、審計、 報警、反應等
DMZ（屏蔽子網(wǎng)防火墻）：位于內(nèi)網(wǎng)與外網(wǎng)之間，通常作為隔離區(qū)， 在 這 里 可 以 放 置 一 些 公 用 服 務 器 ， 例 如 web 服 務 器 、 Email 、 FTP 等
包過濾防火墻：通過一個包過濾器，根據(jù)數(shù)據(jù)的包頭中各項信息來控 制站點、網(wǎng)絡之間的訪問性
包過濾防火墻對用戶完全透明、訪問速度快、低水平控制
包過濾防火墻處在網(wǎng)絡層和數(shù)據(jù)鏈路層之間
每個 IP 字段都被檢查：源地址、目的地址、協(xié)議、端口
缺點：不能防黑客攻擊、不支持應用層協(xié)議、訪問控制粒度粗糙、 不能處理新的安全威脅
應用代理網(wǎng)關(guān)防火墻：徹底隔絕內(nèi)外網(wǎng)之間的直接通信，內(nèi)外網(wǎng)之間 的互相訪問需要經(jīng)過應用層代理軟件轉(zhuǎn)發(fā)
優(yōu)點：可以檢查應用層、傳輸層、網(wǎng)絡層的協(xié)議特征，對數(shù)據(jù)包 的檢測能力較強
缺點：難以配置、處理速度較慢
狀態(tài)檢測技術(shù)防火墻：結(jié)合了包過濾防火墻和應用代理網(wǎng)關(guān)防火墻兩 者的優(yōu)點，即安全性和高速度
? 病毒
計算機病毒特性：傳播性、隱蔽性、感染性、潛伏性、觸發(fā)性、破壞
47第 1 章 計算機系統(tǒng)知識
性
Worm: 蠕蟲病毒； Trojan: 特洛伊木馬； Backdoor: 后門病毒； Macro: 宏病毒
宏病毒感染對象：文本文檔、電子表格
木馬軟件：冰河
木馬感染流程：通過軟件下載捆綁等方式，在用戶主機上建立木馬病 毒的服務器端，這個木馬病毒的服務器端再與攻擊者主機上的木馬病 毒客戶端建立網(wǎng)絡連接，這樣攻擊者就可以借由此來盜取或者破壞用 戶主機數(shù)據(jù)
蠕蟲病毒：歡樂時光、熊貓燒香、紅色代碼、愛蟲病毒、震網(wǎng)
? 網(wǎng)絡攻擊
拒絕服務攻擊 (Dos 攻擊 ) ：通過不斷向計算機發(fā)起請求，讓目標服 務器沒有資源去接收其他正常的請求，從而達到“使計算機或者網(wǎng)絡 無法提供正常服務”的目的
重放攻擊：攻擊者發(fā)送一個目標主機已經(jīng)接收過的報文來達到攻擊目 的，主要用于身份認證過程、破壞認證正確性 ; 可通過在報文中增加 時間戳來防范
口令入侵攻擊：使用某些合法的用戶賬號和口令登錄到目的主機，然 后實施攻擊活動
特洛伊木馬：用戶下載了含有木馬的軟件后，這個木馬程序就會向黑 客發(fā)起連接請求，建立連接后，黑客就可以實施攻擊
端口欺騙攻擊：采用端口掃描找到系統(tǒng)漏洞，從而實施攻擊
網(wǎng)絡監(jiān)聽：攻擊者可接口某一網(wǎng)段在統(tǒng)一物理通道上傳輸?shù)乃行畔?/strong>，
截取賬號和口令
IP 欺騙攻擊：偽造源 IP 地址，冒充其他系統(tǒng)或發(fā)件人身份
SQL注入攻擊：通過注入某些 SQL查詢代碼，獲得數(shù)據(jù)庫權(quán)限，從而 竊取及修改信息
入侵檢測技術(shù)：專家系統(tǒng)、模型檢測、簡單匹配
48第 1 章 計算機系統(tǒng)知識
? 網(wǎng)路安全
SSL( 安全套接層 ): 傳輸層安全協(xié)議 端口號 443
TLS( 傳輸層安全協(xié)議 ) ：也是傳輸層安全協(xié)議，是 SSL 3.0 的后 續(xù)版本
SSH: 用于終端設(shè)備與遠程站點之間建立連接的安全協(xié)議，建立在應 用層和傳輸層基礎(chǔ)上的按全協(xié)議
HTTPS: 使用 SSL 加密的 http
MIME: 電子郵件擴展相關(guān)協(xié)議，不具有安全性
PGP: 通過 RSA 非對稱加密的郵件協(xié)議
IPSec: 對 IP 數(shù)據(jù)報文進行加密
ARP: 地址解析成物理地址協(xié)議
Telnet: 不安全的遠程登錄協(xié)議
WEP: 有限等效保密協(xié)議
TFTP: 簡單文件傳輸協(xié)議
PP2P: 鏈路加密
RFB：遠程登錄圖形化用戶界面協(xié)議
IGMP: 因特網(wǎng)組管理協(xié)議
信息安全的五個基本要素：機密性、完整性、可用性、可控性、審可 查性
49第 1 章 計算機系統(tǒng)知識
第 9章 計算機網(wǎng)絡
? 網(wǎng)絡設(shè)備
物理層的互連設(shè)備：中繼器 (Repeater)和集線器 (Hub), 其中集線器 可以看做是一種多端口的中繼器
數(shù)據(jù)鏈路層互連設(shè)備：網(wǎng)橋（ Bridge ）和交換機（ Switch ） , 其 中交換機是多端口的網(wǎng)橋
網(wǎng)絡層互連設(shè)備：路由器
應用層互連設(shè)備：網(wǎng)關(guān)
物理層設(shè)備不能隔離廣播域和沖突域，數(shù)據(jù)鏈路層設(shè)備可以隔離沖突 域不能隔離廣播域，網(wǎng)絡層可以隔離廣播域與沖突域
? TCP/IP 協(xié)議簇分類
網(wǎng)絡層協(xié)議 IP ：一種盡力傳送的通信協(xié)議，傳送的數(shù)據(jù)可能丟失 ICMP: Internet 控制信息協(xié)議，利用 IP 傳送報文
傳輸層協(xié)議：TCP UDP，都是基于 IP 之上的
應用層協(xié)議
FTP: 文件上傳協(xié)議，文件上傳的端口是 20 ，控制端口為 21
SNMP ：網(wǎng)絡管理協(xié)議
方便記憶： 1. 名字帶 "IP" “AP” 的都是網(wǎng)絡層，2. 應用層 協(xié)議所有帶 "T" 的，除了 TFTP 都是基于 TCP的，其他是基于 UDP的，不帶 “ T” 的只有 POP3 是 TCP 的，其他都是 UDP 的
50第 1 章 計算機系統(tǒng)知識
? 網(wǎng)絡層協(xié)議 IP TCP UDP
IP 提供的服務，是無連接（指沒有確定目標系統(tǒng)在已做好接收準備 前就發(fā)送數(shù)據(jù)）、不可靠的（目的系統(tǒng)不對成功接收的分組進行確 認）
TCP 面向連接、可靠的傳輸控制協(xié)議，采用三次握手實現(xiàn)可靠性
可靠傳輸、連接管理、差錯校驗、重傳、流量控制（可變大小滑動窗 口協(xié)議）、端口尋址、
UDP 無連接、不可靠的傳輸協(xié)議，可以保證應用程序進程間的通信， 有助于提高傳輸?shù)母咝?/p>
端口尋址
? 電子郵件服務協(xié)議
SMTP: 簡單郵件傳輸協(xié)議，用來發(fā)送郵件，端口 25 ，基于 TCP，只能傳輸文本和 ASCII碼的文件
SMTP 基于 C/S 模式，即 客戶端 / 服務器模式來進行通信
MIME 郵件附件擴展類型
PEM 私密郵件
POP3 用來接收郵件的協(xié)議，基于 TCP ，端口號 110 基于 C/S 模式通信
? 地址解析 ARP RARP
ARP: 地址解析協(xié)議，將 IP 地址轉(zhuǎn)換為物理地址（ MAC 地址，每 個網(wǎng)卡唯一）
RARP ：反地址解析協(xié)議，將物理地址轉(zhuǎn)換為 IP 地址
計算機間使用 ARP 通信流程 PC1向 PC2通信
查詢 ARP 高速緩存
如果有 PC2的 IP 地址緩存，則直接使用其對應的物理地址發(fā)送
51第 1 章 計算機系統(tǒng)知識
數(shù)據(jù)
如果沒有緩存，則在局域網(wǎng)以廣播形式發(fā)送 ARP 請求包
如果局域網(wǎng)上某個計算機 IP 地址一致，則那臺計算會響應一 個 ARP 應答，包含對應的物理地址
ARP 將 IP 及應答的物理地址存到高速緩存中
? DHCP
動態(tài)主機配置協(xié)議，集中管理分配 IP 地址，使網(wǎng)絡中的主機獲得， IP 地址、網(wǎng)關(guān)地址、 DNS地址、 DHCP 服務器地址等
? URL
協(xié)議名 ://主機名 . 域名 . 域名后綴 . 域名分類 / 目錄 / 網(wǎng)頁文 件
? DNS 域名查詢次序
本地 hosts 文件 》 本地 DNS 緩存 》本地 DNS服務器 》根域名 服務器
? 主域名服務器在接收到請求后的查詢次序
本地緩存 》 本地 hosts 文件 》本地數(shù)據(jù)庫 》 轉(zhuǎn)發(fā)域名服務器
? IP 地址和子網(wǎng)劃分
Internet 中網(wǎng)絡分為 5 類 A 、 B 、 C 、 D 、 E
A 類網(wǎng)絡，網(wǎng)絡地址 8 位（第一位為 0 ），其余為主機地址
B 類網(wǎng)絡，網(wǎng)絡地址 16 為（前兩位為 10 ），其余為主機地址
C 類網(wǎng)絡，網(wǎng)絡地址 24 為（前兩位為 110），其余為主機地址
52第 1 章 計算機系統(tǒng)知識
子網(wǎng)掩碼：識別報文是只存放在網(wǎng)絡內(nèi)部，還是被路由轉(zhuǎn)發(fā)到其他地 方，用 1 表示網(wǎng)絡地址， 0 表示主機地址，例如 C 類掩碼為 11111111.11111111.11111111.00000000 即 255.255.255.0
子網(wǎng)劃分：
將一個網(wǎng)絡劃分成多個子網(wǎng)：取部分主機號當子網(wǎng)號，取了多少位 k 就有 2^k 個子網(wǎng)
將多個網(wǎng)絡合并成一個大網(wǎng)絡：去部分網(wǎng)絡號主機號
222.125.80.128/26 中 /26 表示由 26 位的網(wǎng)絡地址，有 32-26 位的主機地址
全 1 是廣播地址，全 0 是網(wǎng)絡地址
? IPv6
IPv4 為 32 位， IPv6 128 位，地址空間 不可用完
? 無線網(wǎng)路
無限網(wǎng)絡中藍牙覆蓋范圍最小，通信距離最短
? Windows 命令
ipconfig: 顯示所有網(wǎng)絡適配器的 IP 地址、子網(wǎng)掩碼和缺省網(wǎng)關(guān)值
ipconfig/release: 釋放 IP 地址
ipconfig/flushdns: 清除 dns 緩存，或刷新 dns
ipconfig/displaydns: 顯示 dns
ipconfig/registerdns: DNS 客戶端手工向服務器注冊
ipconfig/all: 顯示所有 所有網(wǎng)絡適配器的完整 TCP/IP 配置信息， 包括 DHCP 服務是否啟動
ipconfig/renew: DHCP 客戶端刷新，重新申請 IP
53第 1 章 計算機系統(tǒng)知識
? 路由
五種路由類型
主機路由：子網(wǎng)掩碼 255.255.255.255
直連網(wǎng)絡
遠程網(wǎng)絡
默認路由：目標網(wǎng)絡和網(wǎng)絡掩碼都是 0.0.0.0
持久路由
服務器接收到一個 IP 數(shù)據(jù)包時先查找主機路由，在查找網(wǎng)絡路 由（直連網(wǎng)絡、遠程網(wǎng)絡）、最后查找默認路由
如果路由器收到關(guān)于某個目標的多條路由，那么要比較各個路由的管 理距離，并采用管理距離最小的
? 其他
網(wǎng)絡的可用性：用戶可利用網(wǎng)絡時間的百分比
園區(qū)子系統(tǒng)：鏈接各個建筑物的通信系統(tǒng)
DNS 實現(xiàn)負載均衡：為同一個域名設(shè)置多個主機記錄，啟用循環(huán)，添 加每個 web 服務器的主機記錄
要使得兩個 IPv6 通過現(xiàn)有的 IPv4 網(wǎng)路通信需要使用“隧道技 術(shù)”
要使得 IPv6 與 IPv4 通信，需要使用 “翻譯技術(shù)”
DNS 服務器與計算機不在一個子網(wǎng)，不會導致計算機網(wǎng)絡不可訪問， 只要路由可達 DNS都可以正常工作
層次化局域網(wǎng)模型核心層的主要功能：將分組從一個區(qū)域高速的轉(zhuǎn)發(fā) 到另一個區(qū)域
默認網(wǎng)關(guān)要和當前 IP 地址在同一個子網(wǎng)段中
54第 1 章 計算機系統(tǒng)知識
第 10章 操作系統(tǒng)
? 操作系統(tǒng)地位
計算機系統(tǒng)由軟件、硬件組成，沒有配置軟件的稱為裸機
操作系統(tǒng)地位：計算機硬件 》操作系統(tǒng) 》 系統(tǒng)軟件 》 應用軟件 》 用戶
所有其他軟件，如編譯程序、匯編程序、數(shù)據(jù)庫管理系統(tǒng)等，以及大 量應用軟件都是建立在操作系統(tǒng)之上的
把操作系統(tǒng)看做用戶與計算機之間的接口
? 進程管理
進程是源分配和獨立運行的基本單位
進程管理重點是要研究諸進程之間的并發(fā)特性，以及進程間相互合作 與資源競爭產(chǎn)生的問題
? 前趨圖
有向無循環(huán)圖，由節(jié)點和單向邊組成，節(jié)點代表各個程序段的操作， 單向邊表示前前趨關(guān)系 Pi(節(jié)點、前趨 ) -——> Pj(節(jié)點、后繼 ) ， Pi 執(zhí)行結(jié)束 Pj 才能執(zhí)行
前趨圖，有 n 個箭頭就要設(shè)置 n 個信號量，按照從小到大順序?qū)?到圖中，箭頭方向是 P 操作，箭頭尾部是 V 操作
程序順序執(zhí)行的主要特征：順序性、封閉性（獨享資源）、可再現(xiàn)性
程序并發(fā)執(zhí)行的主要特征：失去程序封閉性、程序和機器執(zhí)行程序的 活動不再一一對應、并發(fā)程序之間的相互制約性
55第 1 章 計算機系統(tǒng)知識
? 進程的三態(tài)模型
在多道程序系統(tǒng)中，進程在處理器上交替運行，一般由三種狀態(tài) 運行 就緒、阻塞
運行：當一個進程在處理機（ CPU）上運行時，就是運行態(tài)
就緒：一個進程獲得了除了處理機（ CPU）外的所有資源 , 一旦得 到處理機即可運行，這個時候就是就緒態(tài)
阻塞：等待、睡眠，一個進程正在等待某個事件（例如等待 I/O 完 成）發(fā)生而停止運行
? 同步與互斥
同步是合作資源進程之間直接制約的問題
互斥是申請臨界資源進程間的間接制約問題
? 臨界區(qū)管理原則
有空即進，臨界區(qū)無進程，則允許進入，且只能在臨界區(qū)運行有限時 間
無空則等，臨界區(qū)有進程，其他進程則要等待
有限等待，在外等待的進程，要保證在有限時間可進入
讓權(quán)等待，進程有 CPU 沒有資源時，不能進入自己的臨界區(qū)，要立 即釋放 CPU 資源，避免忙等
? 信號量機制
信號量 S 的物理意義， S>=0 表示資源的可用數(shù)， S<0 表示等待該 資源的進程數(shù)
56第 1 章 計算機系統(tǒng)知識
? PV 操作是實現(xiàn)同步和互斥的常用方法
P 表示申請一個資源（ S = S-1，可以理解為從信號量 S 中申請 出一個來使用，申請后 S<0 則進程轉(zhuǎn)為阻塞態(tài)，插入阻塞隊列），
V 表示釋放一個資源（ S = S+1，可以理解為 釋放一個資源到信號 量，釋放后， S<=0 則從阻塞隊列喚起一個進程，插入就緒隊列）
? PV 操作實現(xiàn)進程互斥
令信號量 mutex 初值為 1 ，當進入臨界區(qū)時 執(zhí)行 P 操作，退出 臨界區(qū)時執(zhí)行 V 操作，這兩就利用 PV 實現(xiàn)代碼互斥
? PV 操作實現(xiàn)進程的同步
單緩沖區(qū)同步 ( 緩沖區(qū)只能放一個產(chǎn)品 ) ：分為生產(chǎn)者和消費者，需 要設(shè)置兩個信號量 , S1 初值為 1 表示可放入緩沖區(qū)的產(chǎn)品數(shù)， S2 初值為 0 ，表示可從緩沖區(qū)取出的產(chǎn)品數(shù)；每次生產(chǎn)產(chǎn)品 要進行 P(S1) 和 V(S2), 每次消費產(chǎn)品要進行 P(S2) V(S1)
多緩沖區(qū)同步 ( 緩沖區(qū)可以放多個產(chǎn)品 ) ：在 單緩沖區(qū)的基礎(chǔ)上增 加一個信號量 S, 名為互斥信號量，初始值為 1 ，標記緩沖區(qū)可 操作的量（緩沖區(qū)是個互斥資源）；每次生產(chǎn)產(chǎn)品及消費產(chǎn)品是都要 增加一個 P(S1) P(S) V(S) V(S2) 操作 , S 的 PV 操作放中間
? 死鎖
同類資源分配不當引起的死鎖：若采用的資源分配策略是，輪流的為 每個進程分配，則可能會導致分配幾輪后，沒有一個進程達到所需的 資源數(shù)，這個時候，每個進程都在等待資源分配，形成死鎖；
同類資源分配不當引起的死鎖的解法： m 為資源總量、 n 為進程 數(shù)、 k 為每個進程需要的資源，滿足 m >= n * (k-1) + 1 就可 以避免死鎖
57第 1 章 計算機系統(tǒng)知識
? 進程資源圖
Pi 代表進程， Ri 代表資源類型；每個 Ri 可以有多個資源； 指向 進程的箭頭表示分配資源；指向資源的箭頭表示申請資源；
先分配資源再申請資源，經(jīng)過分配申請后沒有滿足資源的進程即為 “阻塞”
是否可化簡：取決于是否可以在某個進程完成后釋放資源，并使得后 續(xù)進程得以完成
可化簡的就是非死鎖的
? 死鎖避免
死鎖處理策略：鴕鳥策略（不理睬）、預防策略、避免策略、檢測與 解除死鎖
死鎖避免算法：銀行家算法，即在每次分配資源前檢測分配資源后系 統(tǒng)是否安全（是否安全取決與分配資源后，系統(tǒng)是否可以有某種進行 序列，來將所有的進程都執(zhí)行完），資源利用率高，但增加了檢測的 開銷
銀行家算法題計算：， 1. 先算出仍需資源數(shù)， 2. 在算出，剩余資 源數(shù)
? 線程
進程在創(chuàng)建、撤銷、切換中，系統(tǒng)會付出較大的時空開銷，故系統(tǒng)引 入的進程不易過多，進程切換頻率不易太高，因此引入了線程
線程作為調(diào)度和分配的基本單位，進程作為獨立分配資源的單位，線 程是進程中的一個實體
線程與線程之間不可見，但是線程與線程可以共享進程的資源
58第 1 章 計算機系統(tǒng)知識
? 局部性原理
時間局限性：程序的某一條指令執(zhí)行，那在不久的將來該指令可能被 再次執(zhí)行，如果某個存儲單元被訪問，那不久的將來還可能被再次訪 問
空間局限性：程序訪問了某個存儲單元，不久的將來其附近的存儲單 元也可能被訪問
? 相關(guān)題型“淘汰”問題
在內(nèi)存中才能被淘汰
先淘汰未訪問過的
再淘汰未修改過的
? 分頁存儲管理
純分頁存儲管理的地址結(jié)構(gòu)： n 位的頁號 + m位的頁內(nèi)地址
計算機的頁面大小為 4k => 則代表 n 位頁內(nèi)地址 2^n = 4 * 1024 => n=12
頁面變換表邏輯地址轉(zhuǎn)物理地址 => 邏輯地址即為純分頁存儲管理的 地址結(jié)構(gòu)，由 n 位的頁號 + m位的頁內(nèi)地址組成 => 頁內(nèi)地址組成 不變，將頁號替換成“頁面變換表”中對應的物理塊號即可
? 段頁式存儲管理
段頁式存儲管理地址結(jié)構(gòu)： n 位段號 + k位段內(nèi)頁號 + m位的頁內(nèi) 地址
? 單緩沖區(qū)
緩沖區(qū)只能有一個“作業(yè)”，緩沖區(qū)為空時可以輸入，緩沖區(qū)有作業(yè)
59第 1 章 計算機系統(tǒng)知識
時可以傳送
I/O設(shè)備 —輸入 (T)—> 緩沖區(qū) —傳送 (M)—> 工作區(qū) ( 處理 C)
計算 n 個作業(yè)單緩沖區(qū)所花時間： (T+M)*n + C
? 雙緩沖區(qū)
緩沖區(qū)有兩個，每個可存一個”作業(yè)“
計算 n 個作業(yè)雙緩沖區(qū)所花時間： T*n + M + C
? 磁盤調(diào)度算法
先來先服務（ FCFS ） : 按請求訪問者的先后順序來啟動磁盤驅(qū)動 器，平均尋道長度大
最短尋道時間優(yōu)先（ SSTF ） : 讓距離當前磁道位置最短的先執(zhí)行， 不考慮訪問者的先后順序
掃描算法或者電梯調(diào)度算法（ SCAN ） : 從磁頭當前位置開始，沿 著磁頭移動方向，選擇最近的柱面，如果磁頭移動方向無請求柱面， 則調(diào)轉(zhuǎn)方向，選擇最近的
循環(huán)掃描算法（CSCAN） : 在掃描算法的基礎(chǔ)上，調(diào)轉(zhuǎn)方向后不再 選擇最近的柱面，而是移動到最里端
? 旋轉(zhuǎn)調(diào)度算法
磁盤旋轉(zhuǎn)不會停下，磁盤旋轉(zhuǎn)完一個扇區(qū)，就代表讀取了一個扇區(qū)的 記錄，記錄讀取后的處理時間內(nèi)，磁盤不會停下
如果是順序處理 n ，總時間 = (讀時間 + 扇區(qū)一圈時間 )*(n-1) + 第一個扇區(qū)的讀時間 + 第一個扇區(qū)的處理時間
優(yōu)化處理：重排扇區(qū)，讓第一個扇區(qū)處理后所停在的位置，在第二個 記錄所在扇區(qū)的起始位置，所耗時 = (讀時間 + 處理時間 )*n
60第 1 章 計算機系統(tǒng)知識
? 多級索引結(jié)構(gòu)
直接地址索引：索引從 0 開始，一個地址項指向一個磁盤數(shù)據(jù)塊
一級間接地址索引：一個地址項指向一個磁盤索引塊（也可以叫一級 索引塊），一個磁盤索引塊又包含很多個地址項，磁盤索引塊中的地 址項指向一個磁盤數(shù)據(jù)塊
二級間接地址索引：比一級間接地址索引，多了一級磁盤索引塊
? 文件目錄
為了實現(xiàn)按名存取，系統(tǒng)為每個文件設(shè)置用于描述和控制的數(shù)據(jù)結(jié)構(gòu)， 至少包含文件名和存放文件的物理地址，這個結(jié)構(gòu)稱為文件數(shù)據(jù)塊 FCB
文件目錄是由文件控制塊組成的，用來文件檢索
文件控制塊包含三類信息
基本信息：文件名、文件物理地址、文件長度、文件塊數(shù)等
存取控制信息：文件存取權(quán)限
使用信息：建立日期、最后修改日期、當前使用信息
目錄文件的修改時發(fā)生崩潰對系統(tǒng)的影響很大
? 目錄結(jié)構(gòu)
多級目錄結(jié)構(gòu)：倒置的有根樹，也稱為樹形目錄結(jié)構(gòu)
全路徑名：從根目錄開始，一直到文件名 D:\
絕對路徑：從根目錄開始，最后是 /
相對路徑：從當前目錄開始，最后是 /
? 位視圖
位視圖用二進制來表示一個物理塊的使用情況， 0 表示空閑 1 表 示使用
61第 1 章 計算機系統(tǒng)知識
位視圖的大小由磁盤空間大小（物理塊數(shù)）決定，位視圖描述能力強， 適合各種物理結(jié)構(gòu)
假設(shè)計算機系統(tǒng) n 位，那位視圖第 0 個字能對應存儲器上的第 0~n-1 號物理塊，第 1 個字能對應存儲器上的第 n~2n-1 號物理塊后邊以 此類推
? 其他
可變式分區(qū)分配方案：進程 P 有上鄰空閑區(qū) 或 有下鄰空閑區(qū)，那 么 P 進程釋放后，空閑區(qū)合并成一個
當用戶通過鼠標或鍵盤進入某應用系統(tǒng)時，中斷處理程序最先獲得鍵 盤或鼠標的輸入信息
實時操作系統(tǒng)的實時是指，計算機對于外來信息能夠以足夠快的速度 處理，并在被控制對象允許的時間范圍內(nèi)做出快速響應
I/O 系統(tǒng)的層次結(jié)構(gòu)：硬件 - 》中斷處理程序 - 》設(shè)備驅(qū)動程序 - 》設(shè)備無關(guān)程序 - 》用戶進程
I/O 軟件隱藏了 I/O操作的實現(xiàn)細節(jié)，方便用戶使用
磁盤調(diào)度管理中，先進行移臂調(diào)度在進行旋轉(zhuǎn)，訪問不同柱面信息時 要先移臂調(diào)度，訪問同一磁道只需要進行旋轉(zhuǎn)
62第 1 章 計算機系統(tǒng)知識
第 11章 結(jié)構(gòu)化開發(fā)
? 模塊化
模塊化是指將一個待開發(fā)的軟件分解成若干個小的簡單部分–模塊， 每個模塊獨立開發(fā)測試
? 模塊獨立
模塊獨立是指每個模塊完成一個相對獨立的特定子功能，并且與其他 模塊間的聯(lián)系簡單，衡量模塊獨立的標準有兩個：內(nèi)聚性、耦合性
? 耦合
耦合是模塊之間相對獨立性（互相連接的緊密程度）的度量，耦合程 度越高，模塊獨立性越弱
耦合的七種類型由低到高排序
無直接耦合：兩個模塊之間沒有直接關(guān)系（沒有調(diào)用、不傳遞任 何信息）
數(shù)據(jù)耦合：兩個模塊間有調(diào)用關(guān)系，傳遞簡單的數(shù)據(jù)值（值傳 遞）
標記耦合：有調(diào)用關(guān)系，傳遞的是數(shù)據(jù)結(jié)構(gòu)
控制耦合：有調(diào)用關(guān)心，傳遞的是控制變量，控制變量可以讓被 調(diào)用方有選擇的執(zhí)行某一功能
外部耦合：模塊間通過軟件之外的環(huán)境聯(lián)結(jié)
公共耦合：通過公共數(shù)據(jù)環(huán)境相互作用的那些模塊間的耦合
內(nèi)容耦合：一個模塊直接使用另一個模塊的內(nèi)部數(shù)據(jù)，或通過非 正常入口傳入另一模塊內(nèi)部時
63第 1 章 計算機系統(tǒng)知識
? 內(nèi)聚
內(nèi)聚是對一個模塊內(nèi)部各個元素之間彼此結(jié)合緊密程度的度量，內(nèi)聚 程度越高，模塊獨立性越強
內(nèi)聚的其中類型由低到高排序
偶然內(nèi)聚（巧合內(nèi)聚）：模塊內(nèi)各元素間沒有任何聯(lián)系
邏輯內(nèi)聚：指模塊內(nèi)執(zhí)行若干個結(jié)邏輯相似的功能，通過參數(shù)來 確定要執(zhí)行哪一個
時間內(nèi)聚：特定時間需要同時執(zhí)行的動作組合在一起形成的模塊、
過程內(nèi)聚：一個模塊完成多個任務，這些任務必須按照指定過程 執(zhí)行
通信內(nèi)聚：模塊內(nèi)的處理元素都在同一個數(shù)據(jù)結(jié)構(gòu)上操作
順序內(nèi)聚：單一功能，模塊內(nèi)各個處理元素密切相關(guān)，且需要順 序執(zhí)行
功能內(nèi)聚：模塊內(nèi)所有元素共同完成同一功能，缺一不可
? 系統(tǒng)結(jié)構(gòu)設(shè)計原則
分解 - 協(xié)調(diào)原則：大問題分解成小問題
自頂向下原則：抓住系統(tǒng)的主功能，由上到下分層分解
信息隱蔽 - 抽象原則：上層規(guī)定下層做什么和模塊間協(xié)調(diào)，但不規(guī)定 怎么做
一致性原則：統(tǒng)一規(guī)范、統(tǒng)一標準、統(tǒng)一的文件模式
明確性原則：每個模塊功能明確、接口明確，消除多重功能、無用接 口，避免病態(tài)鏈接、消除接口復雜度
高內(nèi)聚低耦合
扇入扇出適中：模塊調(diào)用其他模塊稱為扇出，被其他模塊調(diào)用稱為扇 如
模塊規(guī)模適中：過大，則是分解的不充分，過小，則可能降低模塊獨 立性
64第 1 章 計算機系統(tǒng)知識
模塊的作用范圍應該再其控制范圍之內(nèi)
? 系統(tǒng)文檔
系統(tǒng)文檔是系統(tǒng)建設(shè)過程的”痕跡“，是系統(tǒng)維護人員的指南，是開 發(fā)人員與用戶的交流工具
系統(tǒng)文檔在系統(tǒng)開發(fā)人員、項目管理人員、系統(tǒng)維護人員、系統(tǒng)評價 人員、用戶之間的作用
用戶–系統(tǒng)分析人員：可行性研究報告、總體規(guī)劃報告、系統(tǒng)開 發(fā)合同、系統(tǒng)方案說明書
系統(tǒng)開發(fā)人員–項目管理人員：系統(tǒng)開發(fā)計劃、系統(tǒng)開發(fā)月報、 系統(tǒng)開發(fā)總結(jié)報告、項目管理文件
系統(tǒng)測試人員–系統(tǒng)開發(fā)人員：系統(tǒng)方案說明書、系統(tǒng)開發(fā)合同、 系統(tǒng)設(shè)計說明書、測試計劃文檔
系統(tǒng)開發(fā)人員–用戶：用戶手冊、操作指南
系統(tǒng)開發(fā)人員–系統(tǒng)維護人員：系統(tǒng)設(shè)計說明書、系統(tǒng)開發(fā)總結(jié) 報告、技術(shù)手冊
用戶–維修人員：系統(tǒng)運行報告、維護修改建議
? 數(shù)據(jù)流圖
基本圖形元素
外部實體：矩形，一般用 Ei 表示
數(shù)據(jù)存儲：兩條橫線或者缺邊矩形，一般用 Di 表示
數(shù)據(jù)流：有向邊，起點 ———— > 終點
加工：圓角矩形或圓，一般用 Pi 表示
頂層數(shù)據(jù)流圖描述了系統(tǒng)的輸入輸出， 0 層數(shù)據(jù)流圖是對頂層數(shù)據(jù)流 圖的細分
外部實體：當前系統(tǒng)之外的人、物、外部系統(tǒng)
人：學生、老師、員工、主管
65第 1 章 計算機系統(tǒng)知識
物 : 傳感器、控制器、車輛、采購部門
外部系統(tǒng)：支付系統(tǒng)、車輛交易系統(tǒng)、庫存管理系統(tǒng)
數(shù)據(jù)存儲：存儲數(shù)據(jù)、提供數(shù)據(jù)
存儲加工后的輸出數(shù)據(jù)，提供加工的輸入數(shù)據(jù)
例如： xxx表、 xxx文件
加工 : 將輸入數(shù)據(jù)處理后得到輸出數(shù)據(jù)
一個加工至少有一個輸入數(shù)據(jù)流和一個輸出數(shù)據(jù)里
只有輸入沒有輸出稱為”黑洞“
只有輸出沒有輸入稱為”白洞“
加工的數(shù)據(jù)不足以產(chǎn)生輸出”灰洞“
數(shù)據(jù)流：數(shù)據(jù)流的起點或者重點必有一個是加工
? 父圖子圖平衡
父圖中的數(shù)據(jù)流，子圖中也要有，其實就是根據(jù)父圖去子圖里一個個 找看看有沒有是父圖里有的數(shù)據(jù)流但是子圖沒有
找出丟失數(shù)據(jù)流的技巧
父圖子圖平衡
加工既要有輸入數(shù)據(jù)里、也要有輸出數(shù)據(jù)流
數(shù)據(jù)守恒（到題目的內(nèi)容中去找圖中有哪些丟失的部分）
數(shù)據(jù)建模 – E-R圖；行為建模 – UML；功能建模 – 數(shù)據(jù)流圖
? 數(shù)據(jù)字典
數(shù)據(jù)字典為數(shù)據(jù)流圖中的每個數(shù)據(jù)流、文件、加工，以及組成數(shù)據(jù)流 的數(shù)據(jù)項做出說明
數(shù)據(jù)字典有四類條目：數(shù)據(jù)流、數(shù)據(jù)存儲、基本加工、數(shù)據(jù)項
數(shù)據(jù)項是組成數(shù)據(jù)流和數(shù)據(jù)存儲的最小元素，外部實體不再字典中說 明
常用的加工邏輯描述方法：結(jié)構(gòu)化語言、判定表、判定樹
66第 1 章 計算機系統(tǒng)知識
? 結(jié)構(gòu)化開發(fā)方法
總的指導思想是自頂而下，逐層分解（從抽象到具體）
基本原則是功能的分解與抽象
軟件工程中最早提出的方法，特別適合數(shù)據(jù)處理領(lǐng)域的問題
不適合解決大規(guī)模的、特別復雜的項目，難以適應需求的變化
? 結(jié)構(gòu)化設(shè)計
體系結(jié)構(gòu)設(shè)計：定義軟件的主要結(jié)構(gòu)元素及關(guān)系
數(shù)據(jù)設(shè)計：確定文件系統(tǒng)結(jié)構(gòu)和數(shù)據(jù)庫表結(jié)構(gòu)
接口設(shè)計：描述軟件使用放的外部接口，及各種構(gòu)件間的內(nèi)部接口
過程設(shè)計：定義各組成部分內(nèi)的算法及內(nèi)部數(shù)據(jù)結(jié)構(gòu)
界面設(shè)計黃金原則
用戶操縱控制
減少用戶記憶負擔
保持界面一致
構(gòu)造分層數(shù)據(jù)流圖時需要注意的問題
適當命名
圖中要表示出數(shù)據(jù)流
一個加工不適合過多數(shù)據(jù)流
分解盡可能均勻
67第 1 章 計算機系統(tǒng)知識
第 12章 軟件工程
? CMM( 能力成熟度模型 )
CMM 將軟件過程改進分為以下五個級別
初始級：雜亂無章，沒有明確定義的步驟
可重復級：建立了基本的項目管理過程和實踐，有必要的過程準則來 重復以前在同類項目中的成功
已定義級：軟件過程文檔化、標準化
已管理級：制定了軟件過程和產(chǎn)品質(zhì)量的詳細度量標準
優(yōu)化級：加強了質(zhì)量分析，通過過程質(zhì)量反饋、新觀念、新技術(shù)等不 斷改進
? CMMI( 能力成熟度集成模型 )
階段式模型，結(jié)構(gòu)類似 CMM，關(guān)注組織的成熟度
初始的，過程不可預測缺乏控制
已管理的，過程為項目服務
已定義的，過程為組織服務
定量管理的，過程已度量和控制
優(yōu)化的，集中于過程改進
連續(xù)式模型，關(guān)注每個過程域的能力
CL0( 未完成的 ) ：表明過程域的一個或多個目標沒有被滿足
CL1( 已執(zhí)行的 ) ：過程域特定目標完成，轉(zhuǎn)化可識別的輸入目標 產(chǎn)品，產(chǎn)生可識別的輸出目標產(chǎn)品
CL2( 已管理的 ) ：已管理的過程制度化，關(guān)注針對單個過程實例 的能力
CL3( 已定義級 ) ：已定義的過程制度化，關(guān)注過程的組織標準化 及部署
68第 1 章 計算機系統(tǒng)知識
CL4( 定量管理級 ) ：可定量管理的過程制度化
CL5( 優(yōu)化的 ) ：優(yōu)化的過程制度化，持續(xù)改進優(yōu)化
? 瀑布模型
瀑布模型是將軟件生命周期中各個活動，規(guī)定為依線性順序鏈接的若 干階段模型
需求分析 》 設(shè)計 》 編碼 》 測試 》 運行與維護，由前至后，相 互銜接的固定次序
瀑布模型假設(shè)，一個待開發(fā)的系統(tǒng)需求是完整的，簡明的，一致的， 而且可以先于設(shè)計和實現(xiàn)之前完成
以項目的階段評審和文檔控制來對開發(fā)過程進行指導
優(yōu)點：
容易理解，管理成本低
強調(diào)開發(fā)早期計劃，需求調(diào)研，和產(chǎn)品測試
適合開發(fā)需求明確的，大致固定不會隨意變更的系統(tǒng)
缺點：
客戶必須要完整的，正確的，清晰的表達出需求
開始的兩到三個階段很難評估進度
接近項目結(jié)束時，出現(xiàn)大量的集成和測試工作
項目結(jié)束之前都不能演示系統(tǒng)能力
需求或者設(shè)計中的錯誤，到了項目后期才能發(fā)現(xiàn)
項目風險控制能力較弱
V 模型是瀑布模型的一個變體，重點在于質(zhì)量保證活動和溝通，將 基本問題逐步細化，實際上執(zhí)行了一系列測試
? 增量模型
融合了瀑布模型的基本成分，和原型實現(xiàn)的迭代特征，它假設(shè)可以將 需求分段為一系列的增量，每一個增量可以分別開發(fā)
69第 1 章 計算機系統(tǒng)知識
第一個增量往往是核心產(chǎn)品，客戶對每個增量的使用和評估都作為下 一個增量的新特征和功能
每個增量均發(fā)布一個可操作版本
優(yōu)點：
具有瀑布模型的所有優(yōu)點
第一個可交付版本所需的成本時間很少
開發(fā)由增量表示的小系統(tǒng)所承擔的風險不大
缺點：
如果沒有對用戶的變更要求有規(guī)劃，那么產(chǎn)生的初始增量可能造 成后續(xù)增量的不穩(wěn)定
管理成本、進度、復雜性
? 演化模型
演化模型是迭代的過程模型，使得軟件開發(fā)人員能夠逐步的開發(fā)出更 完整的軟件版本
演化模型特別適合對軟件需求缺乏準確認識的情況，
典型的演化模型有，原型模型和螺旋模型
演化模型與增量模型區(qū)別：增量每次開發(fā)的時小的功能模塊，演化每 次開發(fā)整個產(chǎn)品
? 原型模型
原型模型比較適合用戶需求不清、需求經(jīng)常發(fā)生變化的情況，當系統(tǒng) 規(guī)模不是很大，也不太復雜時采用比較合適
一個原型不必滿足目標軟件的所有約束，其目的是能快速、低成本的 構(gòu)建原型，迅速的開發(fā)出一個看得見摸得著的系統(tǒng)框架
步驟：交流溝通 》 快速計劃 》 快速設(shè)計方式建模 》構(gòu)建原型 》 部署交付和反饋 – 完成后繼續(xù)循環(huán)步驟
原型始于溝通其目的是為了定義軟件的總體，有效的捕獲用戶需求
70第 1 章 計算機系統(tǒng)知識
原型模式不適合大規(guī)模的系統(tǒng)開發(fā)
? 螺旋模型
螺旋模型將瀑布模型和演化模型相結(jié)合，加入了兩個模型都忽略了的 風險分析
每個螺旋周期和瀑布模型大致相符合
每個螺旋周期分為四個步驟
制定計劃：確定軟件目標，制定實施方案，明確項目開發(fā)的限制 條件
風險分析：識別風險、消除風險
實施工程：軟件開發(fā)、驗證階段性產(chǎn)品
用戶評估：提出修正建議，制定下一周期開發(fā)計劃
螺旋模型的特點是加入了風險分析，適合大規(guī)模、高風險、需求變化 的系統(tǒng)
缺點：過多的迭代次數(shù)，會增加開發(fā)成本，延遲提交時間
? 噴泉模型
噴泉模型是一種以用戶需求為動力，以對象作為驅(qū)動的模型，適合與 面向?qū)ο蟮拈_發(fā)方法
噴泉模型克服了瀑布模型不支持軟件重用，和多項開發(fā)活動集成的局 限性
噴泉模型的開發(fā)過程具有迭代性和無間隙性
無間隙是指在開發(fā)活動（分析、設(shè)計、編碼）之間不存在明顯邊界， 允許活動交叉、迭代進行
優(yōu)點：
軟件開發(fā)效率高，節(jié)省開發(fā)時間
缺點：
開發(fā)階段重疊，需要大量開發(fā)人員，管理成本高
71第 1 章 計算機系統(tǒng)知識
需要嚴格的管理文檔，審核難度大
? 統(tǒng)一過程模型（ UP ）
是一種 用例和風險驅(qū)動，以架構(gòu)為中心，迭代并增量的開發(fā)過程
每次迭代有 5 個核心工作流
統(tǒng)一過程的四個技術(shù)階段及里程碑
起始階段：專注于項目初創(chuàng)；里程碑：生命周期目標
精化階段：需求分析和架構(gòu)演進；里程碑：生命周期架構(gòu)
構(gòu)建階段：關(guān)注系統(tǒng)的構(gòu)建，產(chǎn)生實現(xiàn)模型；里程碑：初試運作 功能
移交階段：關(guān)注軟件提交方面的工作，產(chǎn)生軟件增量；里程碑： 產(chǎn)品發(fā)布
? 敏捷開發(fā)
總體目標是盡可能早、持續(xù)地對有價值的軟件交付
敏捷開發(fā)使用戶能夠在開發(fā)周期的后期增加或改變需求
極限編程 (XP)
XP 是一種輕量級（敏捷）、高效、低風險、柔性、可預測、科學 的軟件開發(fā)方式
XP 的四大價值觀：溝通、簡單性、反饋、勇氣
5 個原則：快速反饋、簡單性假設(shè)、逐步修改、提倡更改和優(yōu)質(zhì)工 作
12 個最佳實踐：計劃游戲、小型發(fā)布、隱喻、簡單設(shè)計、測試先 行、重構(gòu)、結(jié)對編程、集體代碼所有制、持續(xù)集成、每周 40h、 現(xiàn)場客戶和編碼標準
水晶法 (Crystal) ：每一個不同的項目都需要一套不同的策略、約 定和方法論
并列征求法 (Scrum)：使用迭代的方法，每 30 天一個沖刺，按需求
72第 1 章 計算機系統(tǒng)知識
級別來實現(xiàn)產(chǎn)品
自適應軟件開發(fā)(ASD)： 6 個基本原則
有一個使命作為指導
特征被視為客戶價值的關(guān)鍵點
”重做“與”做“同樣關(guān)鍵
變化不被視為改正，而是 ”調(diào)整“
交付時間迫使考慮每一個生產(chǎn)版本的關(guān)鍵需求
風險包含
敏捷統(tǒng)一過程（ AUP ） : 采用 ”在大型上連續(xù)，在小型上迭代 “的原理來構(gòu)建
每個 AUP 執(zhí)行以下活動：建模、實現(xiàn)、測試、部署、配置及項 目管理、環(huán)境管理
? 需求分析
軟件需求：指用戶對目標軟件在功能、行為、性能、設(shè)計約束等方面 的期望
功能需求 : 考慮系統(tǒng)做什么、何時做
性能需求
用戶或人因素：用戶理解使用系統(tǒng)難度、錯誤操作的可能性
環(huán)境需求：硬件或軟件環(huán)境，機型，操作系統(tǒng)，平臺
界面需求：考慮來自其他系統(tǒng)輸入輸出，數(shù)據(jù)格式存儲介質(zhì)規(guī)定
文檔需求：文檔針對那些讀者
數(shù)據(jù)需求：接收發(fā)送數(shù)據(jù)格式
資源使用需求：運行所需計算機資源，維護所需人力
安全保密需求：數(shù)據(jù)隔離，系統(tǒng)備份
可靠性需求：隔離錯誤，出錯重啟等待
軟件成本消耗和開發(fā)進度
其他非功能性需求
73第 1 章 計算機系統(tǒng)知識
? 概要設(shè)計
設(shè)計軟件系統(tǒng)的總體結(jié)構(gòu)：將復雜系統(tǒng)按功能分成模塊，并確定模塊 的功能、調(diào)用關(guān)系、接口、結(jié)構(gòu)和質(zhì)量
數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計：數(shù)據(jù)庫設(shè)計（概念設(shè)計 E-R、邏輯設(shè)計、物 理設(shè)計）
編寫概要設(shè)計文檔：概要設(shè)計說明書、數(shù)據(jù)庫設(shè)計說明書、用戶手冊、 修訂測試計劃
評審
? 詳細設(shè)計
對每個模塊進行詳細的算法設(shè)計
對模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進行設(shè)計
對數(shù)據(jù)庫進行物理設(shè)計
其他設(shè)計
編寫詳細設(shè)計說明書
評審
? 系統(tǒng)測試
系統(tǒng)測試的意義：為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，成功的測試就是 發(fā)現(xiàn)了至今為發(fā)現(xiàn)的錯誤
測試的目的：以最小的人力和時間發(fā)現(xiàn)潛在的各種錯誤和缺陷
測試的基本原則：
盡早和不斷的測試，貫穿整個開發(fā)階段
避免由原開發(fā)人員進行測試
測試時要有預期的輸出結(jié)果，與測試結(jié)果作比較
關(guān)心不合理的輸入或操作造成的結(jié)果
不僅要檢查程序是否做了該做的事，還要檢查程序是否做了不該
74第 1 章 計算機系統(tǒng)知識
做的事
嚴格按照計劃測試，避免隨意性
妥善保存測試用例及相關(guān)文檔
后續(xù)測試以前次測試的基礎(chǔ)上修改
系統(tǒng)測試的測試目標來源于需求分析階段
? 單元測試
單元測試又稱為模塊測試，在模塊編寫完成且沒有編譯錯誤后開始執(zhí) 行
單元測試側(cè)重于模塊內(nèi)部的處理邏輯與數(shù)據(jù)結(jié)構(gòu)
單元測試檢查模塊的 5 個特征
模塊接口：保證測試模塊的數(shù)據(jù)流可以正常輸入輸出；測試：形 參與實參是否匹配，全局變量使用， I/O格式 , 文件處理等
局部數(shù)據(jù)結(jié)構(gòu)：測試：變量定義及使用
重要的執(zhí)行路徑
出錯處理
邊界條件
單元測試過程
由于模塊不是獨立運行的，各模塊之間存在調(diào)用與被調(diào)用關(guān)系， 因此測試時需要開發(fā)兩種模塊
? 驅(qū)動模塊：相當于一個主程序，接收測試用例的數(shù)據(jù)，將數(shù)據(jù) 輸入到被測試模塊，輸出測試結(jié)果
? 樁模塊（存根模塊）：用來代替 被測試模塊所調(diào)用的子模塊， 檢測測試模塊的輸入
高內(nèi)聚可以簡化單元測試
? 集成測試
集成測試就是將模塊按照系統(tǒng)說明書組合起來測試，旨在發(fā)現(xiàn)與接口
75第 1 章 計算機系統(tǒng)知識
相關(guān)錯誤
集成后可能出現(xiàn)的問題：
穿過模塊的數(shù)據(jù)丟失
一個模塊的功能對其他模塊造成有害影響
模塊集成后沒有達到預期功能
全局數(shù)據(jù)結(jié)構(gòu)出現(xiàn)問題
模塊組合后誤差累積
自頂向下集成測試：屬于增量方法，模塊集成順序從主控模塊開始， 沿著控制層次逐步向下，不用編寫驅(qū)動模塊，需要編寫樁模塊
自底向上集成測試：模塊集成順序從底層原子模塊開始，沿著控制層 次逐步向上，不用編寫樁模塊，需要編寫驅(qū)動模塊
? 回歸測試
軟件發(fā)生變更，可能會使原來正常的功能產(chǎn)生問題，這時需要回歸測 試重新執(zhí)行一下已經(jīng)測試過的某些子集，確保沒有傳播不期望的副作 用
回歸測試有助于保證不引入無意識的行為或者額外的錯誤
? 冒煙測試
將已經(jīng)轉(zhuǎn)換為代碼的軟件構(gòu)件集成到構(gòu)件中
設(shè)計一系列測試以暴露影響構(gòu)建正確的完成其功能的錯誤
? 測試方法
靜態(tài)測試：被測程序不在機器上運行，采用人工檢測和計算機輔助靜 態(tài)分析來對程序進行檢測
動態(tài)測試：通過運行程序發(fā)現(xiàn)錯誤，可以采用黑盒測試和白盒測試
測試用例：由測試的輸入數(shù)據(jù)和預期輸出結(jié)果組成，設(shè)計用例時應包
76第 1 章 計算機系統(tǒng)知識
含合理的輸入條件和不合理的輸入條件
? 黑盒測試
不考慮軟件內(nèi)部結(jié)構(gòu)和特性，把軟件當做和黑盒子，測試軟件的外部 特性
常用的黑盒測試技術(shù)
等價類劃分：將程序輸入輸出劃分為若干等價類，然后每個等價 類中取一個代表性數(shù)據(jù)作為測試用例，測試時需要同時測試有效 等價類和無效等價類
邊界值分析：輸入的邊界比中間更容易發(fā)生錯誤，應測試邊界值 和剛剛超過邊界值的值
錯誤推測：基于經(jīng)驗推測
因果圖：通過因果圖轉(zhuǎn)換判定表
? McCabe 度量法
通過定義環(huán)路復雜度，建立程序復雜度的度量，它基于一個程序模塊 的程序圖中環(huán)路的個數(shù)
計算公式為 V(G) = m - n + 2 ; G 表示程序圖， V(G) 表示程序圖 的環(huán)路復雜度， m 表示有向弧的個數(shù)， n 表示節(jié)點的個數(shù)
也可以通過查找圖中有多少個閉合區(qū)域 k , 然后 V(G) = k + 1
? 白盒測試
白盒測試也稱結(jié)構(gòu)測試，根據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計測試用例
白盒測試的常用技術(shù)是：邏輯覆蓋、循環(huán)覆蓋、基本路徑測試
白盒測試原則：
程序模塊中的所有獨立路徑至少執(zhí)行一次
邏輯判斷中 取”真“ 和 ”假“的情況都至少執(zhí)行一次
77第 1 章 計算機系統(tǒng)知識
每個循環(huán)都要在邊界條件和一般條件下各執(zhí)行一次
測試程序內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性
邏輯覆蓋
語句覆蓋：選擇足夠的測試數(shù)據(jù)，使得被測試程序中每條語句至 少執(zhí)行一次（只要保證每條語句執(zhí)行，因此可能錯過一些判斷邏 輯分支），語句覆蓋對程序執(zhí)行邏輯的覆蓋程度很低，是很弱的 邏輯覆蓋
判定覆蓋：設(shè)計足夠的測試用例，是的測試程序的每個判定表達 式至少獲得一次 ”真“值和”假“值，每個取”真“和”假“的 分支都至少跑一次，因此也稱為分支覆蓋
條件覆蓋：創(chuàng)造一組測試用例，是的每一個判斷語句中的每個邏 輯條件的各種可能的值都至少滿足一次
判定 / 條件覆蓋：需要同時滿足判定覆蓋和條件覆蓋的要求
條件覆蓋組合：在 判定 / 條件覆蓋 的要求前提下，判定表達式 的所有真假不同組合都要測試一遍，例如 A>0 && b>0 就要測 試四種 T&&T, F&&F, T&&F, F&&T
路徑覆蓋：指測試用例要覆蓋程序中所有可能路徑
? 路徑覆蓋： 每一條路徑可能都要有
? 如何覆蓋所有路徑：只要能把路徑都走一遍就行
如果有偽代碼則先將其轉(zhuǎn)換成流程圖，然后計算
? 運行和維護
軟件維護是軟件生命周期最后一個階段，不屬于系統(tǒng)開發(fā)過程
系統(tǒng)可維護性評價指標：可理解性、可測試性、可修改性
文檔是軟件可維護性的決定因素
可維護性在開發(fā)階段就需要考慮到，此后的每個階段也都需要考慮
78第 1 章 計算機系統(tǒng)知識
? 軟件文檔
編寫高質(zhì)量的文檔可以提高軟件開發(fā)質(zhì)量
文檔也是軟件產(chǎn)品的一部分，沒有文檔的軟件不能稱之為軟件
軟件文檔的編制在軟件開發(fā)中占有突出的地位，和相當大的工作量
高質(zhì)量的文檔對軟件產(chǎn)品的效益有著重要意義
總的來說軟件文檔只好不壞
? 軟件維護內(nèi)容
正確性維護：改正在系統(tǒng)開發(fā)和測試階段未發(fā)現(xiàn)的問題
適應性維護：適應行業(yè)環(huán)境變化和管理需求而做出的修改
完善性維護：為擴充功能和改善性能而做出的修改
預防性維護：為了適應未來的軟硬件環(huán)境變化而主動做出的預防
? 軟件可靠性、可用性、可維護性公式
可靠性：給定時間間隔、給定條件下無失效運作的概率 MTTF/ (1+MTTF) MTTF: 平均無故障時間
可用性：給定時間，系統(tǒng)正確運作的概率 MTBF/(1+MTBF) MTBF: 平均失效間隔時間
可維護性：給定時間，使用規(guī)定的過程和資源完成維護活動的概率 1/(1+MTTR) MTTR: 平均修復時間
? 溝通路徑計算
n 個程序員，無主程序員： (n-1)*n/2
n 個程序員，一個主程序員： n-1
79第 1 章 計算機系統(tǒng)知識
? 軟件項目估算
COCOMO 估算模型：精確的易于使用的成本估算模型，按精細程度分為 基本 COCMO、中級 COCOMO 、詳細 COCOMO
基本 COCOMO 模型 : 靜態(tài)單變量模型
中級 COCOMO 模型：靜態(tài)多變量模型，將系統(tǒng)模型分為系統(tǒng)和部 件兩個層次
詳細 COCOMO 模型：將軟件系統(tǒng)模型分為系統(tǒng)、子系統(tǒng)和模塊三 個部分
COCOMOII 估算模型：層級結(jié)構(gòu)的估算模型，分為三個階段
應用組裝模型：軟件開發(fā)的前期階段使用，使用對象點估算
早期設(shè)計階段模型：在需求已經(jīng)穩(wěn)定，并且基本的軟件體系結(jié)構(gòu) 已經(jīng)建立的時期使用，使用功能點估算
體系結(jié)構(gòu)階段模型：軟件構(gòu)造過程中使用，使用代碼行估算
? Gannt 圖（甘特圖）
一種簡單的水平條形圖，以日歷為基準描述項目任務，水平軸展示日 歷時間線，每個橫條表示一個任務，水平條的起點終點對應日歷時間， 表示任務的開始和結(jié)束，其長度代表任務持續(xù)時間，同一時間段的多 個水平條間是并發(fā)關(guān)系
優(yōu)點：清晰描述任務的開始結(jié)束時間，任務進展情況，和任務間的并 行關(guān)系
缺點：不能清晰的反應出任務間的依賴關(guān)系，不能反映項目的關(guān)鍵， 不能反應計劃中有潛力的部分
? PERT 圖
PERT 圖是一個有向圖
圖中的箭頭表示”任務“，箭頭上的時間表示完成”任務“所需時間
80第 1 章 計算機系統(tǒng)知識
圖中的節(jié)點表示”事件“，表示指向當前節(jié)點的”任務“結(jié)束。并且 由當前節(jié)點指出的”任務“開始
當流入該節(jié)點的所有任務都結(jié)束時，由當前節(jié)點指出的任務才會開始
事件本身不消耗時間和資源，僅表示一個時間點
”事件“節(jié)點由三部分組成：事件號、出現(xiàn)事件的最早時刻、最遲時 刻
開始節(jié)點：沒有流入的任務的節(jié)點，可以有多個，開始節(jié)點的最早時 刻為 0
結(jié)束節(jié)點：沒有流出的任務的節(jié)點，只能有一個，結(jié)束節(jié)點的最遲時 刻等于其自身的最早時刻
最早時刻計算要從開始節(jié)點向結(jié)束節(jié)點推算，最晚時刻要從結(jié)束節(jié)點 向開始節(jié)點推算
最早時刻：能開始該事件節(jié)點出發(fā)的后續(xù)任務的最早時刻，有多個流 入的任務時，則選擇計算后的最大的那個
節(jié)點的最早時刻計算：流入的任務的所需時間 + 流入前一個節(jié)點 的最早時刻
最遲時刻：從此節(jié)點出發(fā)的任務，必須在此時刻前開始，否則工程不 能如期完成，有多個流出的任務時，則選擇計算后最小的那個
節(jié)點的最遲時刻計算：流出任務指向的節(jié)點的最晚時刻 - 流出任務 所需時間
松弛時間：在不影響工期的前提下，完成該任務有多少機動余地，是 掛在任務下的
松弛時間計算：鏈接任務的兩個節(jié)點中，箭頭指向的節(jié)點的最遲時刻 - 任務的耗時 - 箭頭尾部的節(jié)點的最早時刻
關(guān)鍵路徑：從開始節(jié)點到結(jié)束節(jié)點，松弛時間都是 0 的路徑
PERT 圖優(yōu)點：給出任務開始結(jié)束時間，還能給出任務建的依賴關(guān)系、 關(guān)鍵路徑
PRET 圖缺點：不能反映出任務鍵的并行關(guān)系
81第 1 章 計算機系統(tǒng)知識
? 項目活動圖
與 PERT 圖類似，其中：頂點表示里程碑，鏈接定點的變表示活動， 邊上的數(shù)字表示活動所需時間
除了圖形及命名與 PERT 圖不一樣，其他計算方面基本相似
? 軟件配置管理
軟件配置管理主要目標：變更標識、變更控制、版本控制、確保變更 正確的實現(xiàn)、變更報告
軟件配置管理內(nèi)容：版本管理、配置支持、變更支持、過程支持、團 隊支持、變化報告、審計支持
軟件配置管理內(nèi)容（第二版）：軟件配置標識、變更管理、版本控制、 系統(tǒng)建立、配置審核、配置狀態(tài)報告
配置數(shù)據(jù)庫分為三類 : 開發(fā)庫、受控庫、產(chǎn)品庫
? 風險管理
軟件風險的特性：不確定性（可能發(fā)生也可能不發(fā)生）和損失（如果 發(fā)生就會產(chǎn)生惡性后果）
軟件風險的分類
項目風險：拖延項目進度、增加項目成本。例如：預算、進度、 人員、資源、項目復雜度、規(guī)模及結(jié)構(gòu)不確定
技術(shù)風險：質(zhì)量和交付時間。例如：設(shè)計、實現(xiàn)、接口、維護等 方面的問題
商業(yè)風險：威脅軟件生存能力
? 風險識別
系統(tǒng)的指出對項目計劃（估算、進度、資源分配等）的威脅，識別出 已知風險和可預測風險后，項目管理者要回避這些風險，必要時控制
82第 1 章 計算機系統(tǒng)知識
這些風險
識別風險的一種方法是建立 ”風險條目檢查表“
風險條目檢查表格式：列出每一種類型的有關(guān)特性，最終給出一組風 險因素和驅(qū)動因子及發(fā)生概率，風險因素包含性能、成本、支持、進 度
? 風險預測
又稱風險估計，通過兩個方面進行評估， 1. 風險發(fā)生概率 2. 風 險發(fā)生后果
風險預測活動：
建立一個尺度或者標準，反應風險發(fā)生的可能性
描述風險產(chǎn)生的后果
估算風險對項目和產(chǎn)品的影響
標注風險預測的精確度，以免產(chǎn)生誤解
風險預測技術(shù)：建立風險表
影響風險產(chǎn)生后果的三個因素：風險的本質(zhì)、范圍、時間
整體風險顯露度 = 風險發(fā)生的概率 * 風險發(fā)生給項目帶來的成 本
風險評估：一種對風險評估很有用的技術(shù)是定義風險參照水準
? 風險控制
風險控制的目的：輔助項目組建立處理風險的策略
風險避免：應對風險的最好辦法，就是主動的避免風險
風險監(jiān)測：項目管理者應監(jiān)控某些因素，這些因素可以提供風險是否 正在變低或者變高的指示
RMMM 計劃：將所有風險分析工作文檔化，并由項目管理者作為整個項 目計劃的一部分來使用
風險緩解是一種問題規(guī)避活動，風險監(jiān)測是一種項目跟蹤活動
83第 1 章 計算機系統(tǒng)知識
風險監(jiān)測的另一個任務就是找到“起源”
? 軟件質(zhì)量
ISO/IEC 9126 軟件質(zhì)量模型：由三層組成：質(zhì)量特性 》 質(zhì)量子特 性 》 質(zhì)度量指標
功能性：滿足規(guī)定或隱含需求的那些功能
適應性：是否適合有關(guān)的軟件屬性
準確性：能夠得到正確的結(jié)果
互用性：與其他系統(tǒng)進行交互的能力
依從性：服從有關(guān)標準、法規(guī)
安全性：避免非授權(quán)訪問，和意外訪問
可靠性：一定時間內(nèi)軟件維持性能水平的能力
成熟性：軟件故障引起失效的頻率
容錯性：在軟件錯誤或違反指定接口的情況下維持指定的性能水 平
易恢復性：故障后，回復的能力
易使用性：是否容易使用，使用付出學習成本
易理解性：
易學性
易操作性
效率：軟件性能水平和所占資源
時間特性：響應處理時間
資源特性：所使用的資源量
可維護性
易分析性：診斷所需要的成本
易改變性：缺陷改正成本
穩(wěn)定性：不發(fā)生風險的能力 4. 易測試性
可移植性
84第 1 章 計算機系統(tǒng)知識
適應性：軟件轉(zhuǎn)移到不同環(huán)境耗時和成本
易安裝性：指定環(huán)境下安裝軟件成本
一致性：不同環(huán)境安裝后軟件能力一致
易替換性
? 軟件評審 （低概率考）
設(shè)計質(zhì)量：設(shè)計的規(guī)格說明書符合用戶要求
程序質(zhì)量：程序按照規(guī)格說明書所規(guī)定的情況正確執(zhí)行
設(shè)計質(zhì)量評審內(nèi)容：
評價軟件的規(guī)格說明是否符合用戶要求
評審可靠性，即是否能避免輸入異常
評審保密措施實施情況
評審性能實現(xiàn)情況
評審軟件可修改性、可擴充性、可互換性、和可移植性
評審軟件可測試性
評審軟件復用性
程序質(zhì)量評審內(nèi)容： 從開發(fā)者角度進行評審，與開發(fā)技術(shù)直接相關(guān)， 著眼于軟件本身結(jié)構(gòu)
功能結(jié)構(gòu)
功能的通用性
模塊的層次
模塊結(jié)構(gòu)：控制流結(jié)構(gòu)、數(shù)據(jù)流結(jié)構(gòu)、模塊結(jié)構(gòu)與功能結(jié)構(gòu)之間 的對應關(guān)系
處理過程的結(jié)構(gòu)
與運行環(huán)境的接口：與硬件的接口、與用戶的接口
完成質(zhì)量評估的中心活動是技術(shù)評審，目的是揭露質(zhì)量問題
85第 1 章 計算機系統(tǒng)知識
? 軟件容錯技術(shù)
對無可避免的差錯，使其影響減到最小
容錯軟件的定義
對自身錯誤具有屏蔽能力的軟件
一定程度上能從錯誤狀態(tài)恢復到正常狀態(tài)的軟件
發(fā)生錯誤仍能完成預期任務的軟件
一定程度上具有容錯能力
容錯的一般方法：實現(xiàn)容錯的主要手段是冗余，冗余是指對于實現(xiàn)系 統(tǒng)功能的多余的那部分資源
? 四類冗余技術(shù)
結(jié)構(gòu)冗余：靜態(tài)冗余、動態(tài)冗余、混合冗余
信息冗余：為檢測或糾正信息在運算或傳輸中的錯誤而外加的一部分 信息
時間冗余：重復執(zhí)行程序或指令來先出瞬時錯誤的影響
冗余附加技術(shù)：
屏蔽硬件錯誤的附加技術(shù)： 1. 關(guān)鍵程序和數(shù)據(jù)的冗余存儲。 2. 檢測、表決、切換、重構(gòu)、糾錯、復算
屏蔽軟件錯誤的附加技術(shù)： 1. 冗余備份程序的存儲及調(diào)用。 2. 實現(xiàn)錯誤檢查和錯誤恢復。 3. 實現(xiàn)容錯軟件所需的固化程序
? 軟件工具
軟件開發(fā)工具
需求分析工具
設(shè)計工具
編碼與排錯工具
測試工具
86第 1 章 計算機系統(tǒng)知識
軟件維護工具
版本控制工具
文檔分析工具
開發(fā)信息庫工具
逆向工程工具
再工程工具
? 其他
高質(zhì)量文檔特性：針對性、精確性、清晰性、完整性、靈活性、可追 溯性
軟件工程基本要素：方法、工具和過程
數(shù)據(jù)處理領(lǐng)域不太復雜的軟件適合結(jié)構(gòu)化開發(fā)方法
軟件調(diào)試方法：
試探法：猜測問題所在位置，通過輸出語句獲得錯誤線索
回溯法：從發(fā)現(xiàn)問題的位置開始，沿著程序的控制流程往回跟蹤 代碼
對分查找法：通過縮小錯誤范圍，找出問題
歸納法：收集正確的與不正確的數(shù)據(jù)，分析他們之間的關(guān)系，提 出假想的錯誤原因
演繹法：列出所有可能的錯誤原因，排除、嘗試
87第 1 章 計算機系統(tǒng)知識
第 13章 數(shù)據(jù)結(jié)構(gòu)與算法
? 復雜度
大 O 表示法：以算法中基本操作重復執(zhí)行的次數(shù)（頻度）作為算法時 間點的度量，一般只要大致的計算出數(shù)量級即可
O(1) < O(log2 n) < O(n) < O(nlog2 n) < O(n^2) < O(n^3) < O(n!) < O(n^n)
常數(shù)階 < 對數(shù)階 < 線性階 < 線性對數(shù)階 < 平方階 < 立 方階 < 階乘階 < n 次方階
復雜度計算規(guī)則：多項相加保留最高項；多項相乘都保留；加乘混合， 則按照計算規(guī)則；系數(shù)化為 1
時間復雜度，與循環(huán)相關(guān)
空間復雜度，看有沒有開辟新空間，比如數(shù)組
? 漸進符號
O(g(n)): 表示漸進上界， 10n^2+4n+2 = O(n^2) 是成立的，因為 漸進上界括號內(nèi)的復雜度要大于等于等式左邊的計算結(jié)果
Ω(g(n)): 表示漸進下界， 10n^2+4n+2 = O(n^3) 是不成立的，因 為漸進下界括號內(nèi)的復雜度要小于等于等式左邊的計算結(jié)果
Θ(g(n)): 表示漸進緊致界， 10n^2+4n+2 = O(n^3) 是不成立的， 因為漸進緊致界括號內(nèi)的復雜度要等于等式左邊的計算結(jié)果
? 遞歸的時間空間復雜度
遞歸的時間復雜度 = 遞歸的次數(shù) * 每次遞歸的時間復雜度
遞歸的空間復雜度：如果遞歸中有變量聲明賦值，則相當于 長度為遞 歸次數(shù)的數(shù)組
88第 1 章 計算機系統(tǒng)知識
遞歸式主方法：
假如題目給了一個遞歸式的表達式長得像 T(n) = aT(n/b) + f(n) 那么可以按照下邊方法嘗試一下
比如給了個題目 T(n) = 2T(n/2) + nlgn 讓求復雜度
那么按照公式換算得出 a=2; b=2; f(n) = nlgn;
如果 f(n) 中有 lg 相關(guān)那么就套這個公式 f(n) = Θ(n^(logb a)lgk n); 將換算的數(shù)據(jù)代入， 即 nlgn = (n^(log2 2)lgk n); 得到 k = 1; 然后再代入到 這個公式 T(n) = Θ(n^(logb a)lgk+1 n) 得出 T(n) 復雜度為 nlg2n
若果 f(n) 中沒有 lg 則直接代入到 T(n) = Θ(n^(logb a))
? 線性表
線性關(guān)系：具有單一前趨和后繼的數(shù)據(jù)關(guān)系，元素一個接一個的排列
線性表：最簡單基本常見的線性數(shù)據(jù)結(jié)構(gòu)，通常表示為 (a1,a2,…an)
線性表特點：‘第一個元素’、‘最后一個元素’都是唯一且只有一 個的；除第一個元素只有后繼，最后一個元素只有前趨外，其余元素 都含有前趨和后繼
線性表順序存儲：指用一組連續(xù)的存儲單元，一次存儲線性表中的數(shù) 據(jù)，也就是說物理位置相鄰
優(yōu)點：可隨機存取表中元素，查詢效率高
缺點：插入和刪除需要移動元素，刪除插入效率低，表長為 n, 插 入新的值平均移動 n/2; 刪除值平均移動 (n-1)/2
順序表插入元素時間復雜度：順序表最后插入 O(1); 順序表首位插 入 O(n);平均復雜度 O(n)
順序表刪除元素時間復雜度：順序表最后一位刪除 O(1); 順序表首 位刪除 O(n); 平均復雜度 O(n)
查找元素時間復雜度：直接根據(jù)數(shù)組下標查詢，所以為 O(1)
89第 1 章 計算機系統(tǒng)知識
? 線性表鏈式存儲
通過指針鏈接起來節(jié)點，來存儲數(shù)據(jù)元素，分為數(shù)據(jù)域 + 指針域；數(shù) 據(jù)元素的節(jié)點地址不是連續(xù)的，節(jié)點空間在需要的時候才申請
若節(jié)點只有一個指針域，則成為線性鏈表或單鏈表
頭節(jié)點：不存儲數(shù)據(jù) (!!也可以存儲鏈表長度 ) ，只存儲鏈表第一 個節(jié)點的地址
頭指針、尾指針：有了尾指針就可以直接從尾部遍歷查找，有了尾指 針時間復雜度會有變化
連式存儲插入元素時間復雜度：首位插入 O(1); 末位插入 O(n); 平均復雜度 O(n)
連式存儲刪除元素時間復雜度：首位刪除 O(1); 末位刪除 O(n); 平均復雜度 O(n)
連式存儲查找元素時間復雜度：首位查找 O(1); 末位查找 O(n); 平均復雜度 O(n)
循環(huán)單鏈表：就是在單鏈表的基礎(chǔ)上，尾部節(jié)點的指針指向頭部節(jié)點， 時間復雜度與單鏈表一致
雙鏈表：每個節(jié)點指針不但指向后驅(qū)節(jié)點，還會指向前趨節(jié)點，也就 是一個節(jié)點即知道前一個節(jié)點地址也知道后一個節(jié)點的地址
? 棧
棧的定義：只能通過訪問它的一端來實現(xiàn)數(shù)據(jù)存儲和檢索的一種線性 數(shù)據(jù)結(jié)構(gòu)
棧的修改按照先進后出，后進先出的原則進行，插入和刪除操作的一 端稱為棧頂 Top, 另外一端稱為棧底，不含元素的稱為空棧
理解：可以將棧想象成一個杯子，先進先出，與 遞歸的執(zhí)行過程類似
棧的鏈式存儲：用鏈表作為存儲結(jié)構(gòu)的棧，也稱為 鏈棧，不必設(shè)置頭 指針，鏈表的頭指針就是棧頂指針
90第 1 章 計算機系統(tǒng)知識
? 隊列
隊列的定義：一種先進先出的線性表，只允許在表的一端插入值，在 另一端刪除元素
順序隊列：使用順序存儲的隊列，需要設(shè)置隊頭指針和隊尾指針
循環(huán)隊列：可處理順序隊列中插入值溢出越界，只需要改變隊頭和隊 尾指針即可，避免采用線性表插值導致的遍歷
? 隊列鏈式存儲
雙端隊列：入隊出隊在兩端都可以進行
兩個?？梢阅M一個隊列，但是兩個隊列無法模擬一個棧
? 串
串是一種特殊的線性表，其數(shù)據(jù)元素為字符，是由字符構(gòu)成的有限序 列，例如： ‘ abc’
空串：長度為零，不包含字符
子串：串中任意長度的連續(xù)子串構(gòu)成的序列 ‘ abc’ 的 子串可以 是 ‘ ab’ 但不能是 ‘ ac’
串比較：兩個串比較時以字符的 ASCII 碼值作為依據(jù)
串的模式匹配：可以理解為 JS 中所要的效果 a.indexOf(b)
復雜度：主串長度 n , 子串長度 m
最好情況（首位即匹配成功）：復雜度 O(m) | O(1)
最壞請款（比較到最后 m 位）：復雜度 O(nm) => (n-m+1)m
平均復雜度： O(n+m)
? 串的模式匹配 KMP 算法
串的前綴：包含第一個字符，但是不包含最后一個字符的子串
串的后綴：包含最后一個字符，但是不包含第一個字符的子串
91第 1 章 計算機系統(tǒng)知識
KMP：可以提高串的模式匹配效率，時間復雜度為： O(n+m)
KMP next 的數(shù)值計算：第 i 個字符的 next 值 = 第 i 個字符 前的字符串中，”串前綴 ===串后綴“最長的那個的長度 + 1；其 中 next[1] = 0
? 一維數(shù)組
LOC: 表示第一個元素的首地址； L: 表示每個元素的大小
計算數(shù)組中某個元素 i 的地址： ai = LOC + i*L
? 二維數(shù)組
二維數(shù)組的存儲，會將將第二行在第一行后邊連續(xù)存儲（列優(yōu)先存儲， 則第二列在第一列存儲之后連續(xù)存儲）
LOC: 表示第一個元素的首地址； L: 表示每個元素的大小 ; N: 行 數(shù) ; M: 列數(shù)；
計算二維數(shù)組 i 的地址 = LOC + (i 前有多少個元素 ) * L
行優(yōu)先存儲： LOC + (i*M + j) * L
列優(yōu)先存儲： LOC + (j*N + i) * L
N == M 且 i == j 時，按行還是按列的地址都是一樣的，偏移量也 是一樣的
? 對稱矩陣
矩陣內(nèi)任意元素具有 Ai,j = Aj,i 的特點
按照主對角線對稱，分為上三角區(qū)和下三角區(qū)
存儲時只需要存儲下三角區(qū) + 主對角線即可，一般使用一個一維 數(shù)組存儲
按行存儲： i >=j 時 Ai,j = (i+1)i/2 + j + 1; i < j 時，因為
92第 1 章 計算機系統(tǒng)知識
是主對角線堆成 則可以改為計算 Aj,i
? 三對角矩陣
只有主對角線兩側(cè)緊鄰區(qū)域有值，其他區(qū)域都是 0
存儲時只存中間區(qū)域的值，不存 0 的位置，存到一個一維數(shù)組中
按行存儲： Ai,j = 2i+j+1
? 稀疏矩陣
矩陣很大，但是存的非 0 元素很少
壓縮存儲方式：使用三元組順序表存儲 [i, j, data] [行 , 列， 值 ]
另一種壓縮方式：十字鏈表
? 樹
一種非常重要的非線性結(jié)構(gòu)，一個元素可以有 0 個或多個的后繼元素
樹是 n 個節(jié)點的有限結(jié)合， n=0 時稱為空樹，有且只有一個根節(jié) 點
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點
節(jié)點的度：一個節(jié)點的子樹的個數(shù)計為該節(jié)點的度
葉子節(jié)點：終端節(jié)點，沒有子節(jié)點的節(jié)點，度為 0 的節(jié)點
內(nèi)部節(jié)點：分支節(jié)點，度不為 0 的節(jié)點
節(jié)點的層次： 根為第一層，跟的子為第二層，以此類推
樹的高度：一棵樹最大的層數(shù)計為樹的高度或者樹的深度
樹的度：樹中所有節(jié)點度的最大值
? 樹的性質(zhì)
樹中節(jié)點總數(shù) = 所有節(jié)點的度數(shù)之和 + 1
93第 1 章 計算機系統(tǒng)知識
度為 m 的樹中第 i 層上最多有 m^(i-1) 個節(jié)點，最多的情況就是 每層都有 m 個節(jié)點
高度為 h 的 度為 m 的樹，最多有 (m^h - 1)/(m-1) 個節(jié)點， 最多的情況就是每層都有 m 個節(jié)點，一共 h 層
具有 n 個節(jié)點度為 m 的樹的最小高度為 logm (n(m-1) + 1) ，要想高度最小，那還是每層都要有 m 個節(jié)點
? 二叉樹
n 個節(jié)點的有限集合， n=0 時為空樹，或者是由一個根節(jié)點及兩 個不想交的且分別稱為左右子樹的二叉樹組成
樹和二叉樹的區(qū)別
二叉樹中子樹分為左子樹和右子樹，即使只有一個子樹也要區(qū)分 左右
二叉樹中節(jié)點最大度數(shù)為 2
? 二叉樹的性質(zhì)
二叉樹第 i 層最多有 2^(i-1) 個節(jié)點，實際就是樹的公式中國將 度 ==2 后代入
高度為 h 的二叉樹最多有 2^h - 1 個節(jié)點；最多的情況下，每一 層的節(jié)點數(shù)都是前邊所有層的節(jié)點數(shù) +1
任意一個二叉樹，度數(shù)為 0 的葉子節(jié)點個數(shù) = 度數(shù)為 2 的節(jié)點個 數(shù) + 1；由 ”樹中節(jié)點總數(shù) = 所有節(jié)點的度數(shù)之和 + 1“ 推 斷出來的
有 n 個節(jié)點的完全二叉樹的高度為 (log2 n + 1)的向下取整或者 (log2 (n+1)) 的向上取整
94第 1 章 計算機系統(tǒng)知識
? 滿二叉樹
高度為 k 的二叉樹，如果有 2^k -1 個節(jié)點，那就是滿二叉樹，可 以從上往下，從左往右編號
? 完全二叉樹
除最后一層外，其他層都是”滿的“，最后一層的節(jié)點也是從左至右 依次放置；這個情況下，完全二叉樹中的每一個節(jié)點都能與同樣深度 的滿二叉樹一一對應
? 卡特蘭數(shù)
n 個節(jié)點的二叉樹有多少種 : (C2n n)/(n+1); 其中 (Cn m) = n!/m!*(n-m)!
? 二叉樹的順序存儲
用一組連續(xù)的存儲單元，存儲二叉樹中的節(jié)點
樹節(jié)點與編號 i 間關(guān)系
求父節(jié)點： i=1, 則為根節(jié)點，根節(jié)點沒有父節(jié)點；若 i>1 則 該節(jié)點的父節(jié)點為 i/2 的向下取整
求左子節(jié)點： 2i<=n 則該節(jié)點左子節(jié)點編號為 2i, 否則無左 子節(jié)點
求右子節(jié)點： 2i+1<=n 則該節(jié)點右子節(jié)點編號為 2i+1, 否則 無右子節(jié)點
順序存儲對完全二叉樹比較合適，對普通二叉樹來說則為了保持關(guān)系， 會有很多”虛節(jié)點“
單支樹，除了葉子節(jié)點，其他節(jié)點的度都為 1
95第 1 章 計算機系統(tǒng)知識
? 二叉樹鏈式存儲
二叉鏈表存儲，每個二叉鏈表節(jié)點存儲 [ 當前節(jié)點的數(shù)據(jù)元素 , 左子節(jié)點指針，右子節(jié)點指針 ] ，如果沒有對應的子節(jié)點則存 NULL
二叉鏈表存儲中的有效指針域數(shù)量：即為樹結(jié)構(gòu)中的有效關(guān)聯(lián)數(shù)量， 每個子節(jié)點都僅有一個父節(jié)點 ( 除了根節(jié)點 ) ，因此有效的數(shù)量 = 總的節(jié)點數(shù) - 1 個
三叉列表：在 二叉鏈表的基礎(chǔ)上增加了一個指向父節(jié)點的指針域
? 二叉樹的遍歷
先序遍歷：按照 根左右的次序遍歷
中序遍歷：按照 左根右的次序遍歷
后序遍歷：按照 左右根的次序遍歷
層次遍歷：從根節(jié)點開始，每一層從左往右訪問
? 還原二叉樹
單獨一種遍歷結(jié)果沒法還原出樹
先序遍歷和層次遍歷的的首位就是根節(jié)點，后序遍歷的末位也是根節(jié) 點，因此 中序遍歷與其他任意一種遍歷結(jié)合就能還原二叉樹
? 平衡二叉樹
二叉樹中任意節(jié)點的左右子樹高度只差不大于 1 ，完全二叉樹一定是 平衡二叉樹
? 二叉排序樹
又稱二叉檢查樹
根節(jié)點關(guān)鍵字：就是根節(jié)點的值
96第 1 章 計算機系統(tǒng)知識
根節(jié)點的關(guān)鍵字大于左子樹的所有節(jié)點關(guān)鍵字
根節(jié)點的關(guān)鍵字小于右子樹的所有節(jié)點關(guān)鍵字
左右子樹也是二叉排序樹，依次遞歸
二叉排序樹的中序遍歷是一個有序序列
計算題：會給一個關(guān)鍵字序列，關(guān)鍵字序列的收個元素就是根節(jié)點， 后邊數(shù)字比根大就放右邊，比根小就放左邊，節(jié)點為空就直接插入， 不為空就與其比較后向下層插入，其他的元素依次判斷插入二叉排序 樹中即可
二叉排序樹查找的效率，是受查找的層數(shù)相關(guān)的，層數(shù)越高效率越差
? 最優(yōu)二叉樹
又稱哈弗曼樹 它是一類帶權(quán)路徑長度最短的樹
路徑：從樹的一個節(jié)點，到另一個節(jié)點之間的通路
路徑長度：路徑上的分支數(shù)目（幾條線）
樹的路徑長度：從根節(jié)點到每一個葉子節(jié)點路徑長度之和，乘以權(quán)值 則代表樹的帶權(quán)路徑長度
? 最優(yōu)二叉樹構(gòu)造
題：將一個權(quán)值集合（例如： {1,3,3,4} ），構(gòu)造成一個二叉樹
構(gòu)造方法：
從前往后找兩個權(quán)值最小的
這兩個里邊小的作為左子樹，大的作為右子樹，構(gòu)造新的二叉樹， 這個二叉樹的根的權(quán)值等于兩者相加
將計算后的根加入權(quán)值集合末尾
繼續(xù)上述步驟，直到集合中只剩下一個
權(quán)值大的距離根節(jié)點近，權(quán)值小的距離根節(jié)點遠
最優(yōu)二叉樹只有度為 0 的節(jié)點和度為 2 的節(jié)點
總節(jié)點個數(shù) = (權(quán)值數(shù)量 * 2) - 1
97第 1 章 計算機系統(tǒng)知識
? 哈夫曼編碼
等長編碼：對每個字符編制相同長度的二進制碼，例如英文 26 個字 符，需要 2^5 即需要 5 位二進制串表示
哈夫曼編碼不是等長編碼
接收方按照 5 位一組將電文進行分割后，通過對應實現(xiàn)譯碼
題：一般會給一串字符并說明字符的權(quán)重
我們根據(jù)權(quán)重畫出哈夫曼樹，并將節(jié)點替換為相應的字符
根節(jié)點與左子節(jié)點的連線為 0 ，與右子節(jié)點的連線為 1 ，將每條 節(jié)點間連線標出
某個字符的編碼就是從根節(jié)點開始到當前字符節(jié)點所經(jīng)過路徑上的 0,1 組成
哈夫曼編碼壓縮比：即每個字符從等長編碼到哈夫曼編碼的壓縮情況
哈夫曼編碼是基于貪心策略的
? 線索二叉樹
普通二叉樹，采用二叉鏈表做存儲結(jié)構(gòu)，則鏈表中會有空指針域，利 用這個空指針域來存放節(jié)點的前驅(qū)后繼信息
? 圖
圖中，任意兩個節(jié)點之間都可能有關(guān)系，一個節(jié)點可能有多個前趨或 者多個后繼
圖，標記為 G(V,E) V 表示頂點的非空有限集合； E 是圖中邊的有限 集合
有向圖：每個邊是有方向的，那么頂點關(guān)系用 v1 是起點， v2 是終點
無向圖：每個邊是無方向的，那么頂點關(guān)系用 (v1,v2)
完全圖：每個頂點都與其他頂點有一個邊，則稱為完全圖
98第 1 章 計算機系統(tǒng)知識
假設(shè)無向完全圖有 n 個頂點，那完全圖的邊一共有 n(n-1)/2
有向完全圖的邊總數(shù)則為 n(n-1) ，因為每兩個頂點間有來回兩 條邊
無向圖頂點的度：關(guān)聯(lián)于該頂點的邊的數(shù)量
有向圖的出度與入度：出度–從該頂點指出去的邊的數(shù)量；入度–指 向該頂點的邊的數(shù)量；總度數(shù) = 出度 + 入度
圖的總度數(shù) = 邊數(shù) * 2
路徑：就是通過那幾條邊的組合，實現(xiàn)從一個頂線到另一個頂點；路 徑長度就是路徑上邊或弧的數(shù)目
第一個頂點和最后一個頂點相同的路徑稱為回路或者環(huán)
簡單路徑：路徑上，除了起點和終點可以相同外，其余頂點都不 相同的路徑
? 連通圖
連通圖：無向圖中，任意兩個頂點間都有至少一條的路徑可以連通， 則稱為連通圖
對于 n 個頂點的無向圖，最少有 n-1條邊就可以實現(xiàn)連通，最多 n(n-1)/2
強連通圖：有向圖中，任意兩個頂點間都有來回的兩條路徑連通，稱 為強連通圖
對于 n 個頂點的有向圖，最少有 n 條邊就可以實現(xiàn)連通，最多 n(n-1)
? 圖的存儲結(jié)構(gòu)
鄰接矩陣表示法：使用一個矩陣來表示圖中頂點間的關(guān)系，有 n 個定 點的圖，其鄰接矩陣就是 n 階的，矩陣中值為 1 表示有邊，為 0 表示無邊
無向圖的鄰接矩陣是對稱的，有向圖則不一定是
99第 1 章 計算機系統(tǒng)知識
無向圖鄰接矩陣計算某個定點的度數(shù)：定點 vi 的度數(shù)就是第 i 行非 0 元素的個數(shù)
有向圖鄰接矩陣計算某個定點的度數(shù)：定點 vi 的出度–第 i 行 非 0 元素的個數(shù) ; 入度：第 i 列非 0 元素的個數(shù)
鄰接鏈表表示法：為圖的每個節(jié)點建一個單鏈表，具體的還得看圖， 這里不做詳解
有向圖的鄰接鏈表，有幾個指出來的表結(jié)點就有幾條邊；無向圖的鄰 接鏈表，有 n 指出來的表結(jié)點就有 n/2條邊
稠密圖和稀疏圖，邊多的就是稠密圖，邊少的就是稀疏圖
鄰接矩陣表示法適合稠密圖，鄰接鏈表適合稀疏圖
網(wǎng)：邊或弧帶有權(quán)值的圖，稱為網(wǎng)；網(wǎng)的鄰接矩陣中有邊的會用權(quán)值 表示，沒有邊的用 oo 無窮表示
? 圖的遍歷
深度優(yōu)先搜素：從一個頂點 A 按照出度向另一個頂點 B ， B 在按 照出度向頂點 C, 這樣先從路徑的起始遍歷到路徑的末尾，然后在通 過回溯，換一個路徑遍歷
深度優(yōu)先搜素的時間復雜度： n 表示頂點數(shù)， e 表示邊數(shù)，鄰接矩 陣存儲的復雜度為 O(n^2) ；鄰接鏈表的時間復雜度 O(n+e) ，用 棧的方式
廣度優(yōu)先搜索：先遍歷一個頂點 A 的所有出度的節(jié)點，在遍歷出度節(jié) 點的所有出度節(jié)點，以此類推，相當于一層層遍歷
廣度優(yōu)先搜素的時間復雜度： n 表示頂點數(shù)， e 表示邊數(shù)，鄰接矩 陣存儲的復雜度為 O(n^2) ；鄰接鏈表的時間復雜度 O(n+e) ，用 隊列的方式
? 拓撲排序
AOV 網(wǎng)：一種有向無環(huán)圖
100第 1 章 計算機系統(tǒng)知識
AOV 網(wǎng)中 弧的尾部是前趨，弧指向的是后繼，前趨對后繼有制約關(guān) 系
拓撲排序：是 AOV 網(wǎng)中所有定點排出的線性序列，并且網(wǎng)中任意路 徑 的前后頂點在這個線性序列中 vi 排在 vj 前
假設(shè) AOV 圖是一個工程的計劃，那 AOV網(wǎng)的一個拓撲排序就是工程 順利完成的可行方案
拓撲排序計算方式：
在 AOV 網(wǎng)中選擇一個入度為 0 的頂點，且輸出它
在網(wǎng)中刪除該頂點及與該頂點相關(guān)的所有弧
重復上述兩步直到不存在入度為 0 的頂點為止
例如：得到 614325 這個拓撲序列，那么對于 6 與 4 來 說，可能存在弧6->4;不可能存在弧 4->6;可能存在 6->4 的路徑， 一定不存在 4->6 的路徑
? 查找
查找表：由同一類型元素構(gòu)成的集合，集合元素之間存在著完全松散 的關(guān)系
靜態(tài)查找表只進行以下兩種操作
查詢某個特定元素是否在查找表中
檢索某個特定元素的各種屬性
動態(tài)查找表，除了靜態(tài)查找表的功能還進行如下操作
在查找表中插入一個數(shù)據(jù)
從查找表中刪除一個數(shù)據(jù)
關(guān)鍵字是數(shù)據(jù)元素某個數(shù)據(jù)項的值，可以用來標記數(shù)據(jù)元素
靜態(tài)查找表有：順序查找、二分查找、分塊查找
動態(tài)查找表有：二叉排序樹、平衡二叉樹、 B_ 樹、哈希表
查找的基本操作：將記錄的關(guān)鍵字與給定的值進行比較
順序查找：就是從左向右查找，不需要有序，適用于順序存儲和鏈式 存儲方式，平均查找長度為 (n+1)/2
101第 1 章 計算機系統(tǒng)知識
? 二分查找
又稱折半查找，就是將給定的值與查找表中間的值進行比較，下標求 中間值（比較值），中間值為小數(shù)則向下取整，比較后舍棄中間值進 行下一輪比較
例 如 10 個 值 ， 則 依 次 取 (1+10)/2 => 5 ； (6+10) => 8; (9+10)/2 => 9; (10+10)/2 => 10;
需要順序存儲，且要有序存儲
二分查找成功時，給定值的比較次數(shù)最多為 [log2 n) + 1 向下取 整
二分查找的平均查找長度為： (log2 (n+1)) - 1
? 哈希表
哈希表：通過計算一個已記錄的關(guān)鍵字為自變量的函數(shù)（哈希函數(shù)）， 來得到該記錄的存儲地址
根據(jù)設(shè)定的哈希函數(shù) H(key) 和處理沖突的方法，將一組關(guān)鍵字映射 到一個有限的連續(xù)地址集上
對于一個哈希函數(shù)，兩個不同的關(guān)鍵字，經(jīng)過哈希函數(shù)查找后的地址 相同時，稱為沖突，具有相同哈希函數(shù)值的關(guān)鍵詞稱為同義詞
一般情況下，沖突可以盡可能的減少，而不能避免，要減少沖突，就 要盡可能均勻的將關(guān)鍵字映射到存儲區(qū)的各個存儲單元
對于哈希表來說，主要考慮兩個問題，一個是如何構(gòu)造哈希函數(shù)，一 個是如何解決沖突
哈希函數(shù)構(gòu)造方法：
構(gòu)造哈希函數(shù)時，一般都會對關(guān)鍵字進行計算，盡可能的使得關(guān) 鍵字的所有成分都起作用
除留余數(shù)法： H(key) = key % m = 地址； 求關(guān)鍵字 key 的 余數(shù)作為地址，其中 m 是一個接近 n 但不大于 n 的質(zhì)數(shù)， n 是散列表的長度，地址一般從 0 開始
102第 1 章 計算機系統(tǒng)知識
解決沖突的方法
解決沖突就是在沖突時，給沖突的關(guān)鍵字再找個地址存儲
線性探測法：如果 H(key) 沖突了 那就按照 Hi = (H(key) + i) % m ；再計算一個地址，其中 i=1,2,3,... 表示再次計算如 果還是沖突就，加碼再次計算，直到不沖突為止
二次探測法：如果 H(key) 沖突了 那就按照 Hi = (H(key) + di) % m；再計算一個地址，其中 i=1^2,-1^2,2^2,-2^2,... 表示再次計算如果還是沖突就，就按照 1^2,-1^2,2^2,-2^2,... 的方式依次嘗試，直到不沖突為止 , 與線性探測法相比，是在 H(key) 地址的左右來回試探
裝填因子： a = 表中裝入的記錄樹 / 哈希表長度， a 代表 哈希表的裝滿程度， a 越大沖突概率越大
? 堆
n 個關(guān)鍵碼構(gòu)成的序列 {k1,k2,…kn}，滿足以下關(guān)系稱為堆
小頂堆： ki <= k2i && ki <= k(2i+1) 即 根節(jié)點比子節(jié)點小的二 叉樹，層次遍歷的結(jié)果
大頂堆： ki >= k2i && ki >= k(2i+1) 即 根節(jié)點比子節(jié)點大的二 叉樹，層次遍歷的結(jié)果
將一個序列調(diào)整為一個大頂堆或者小頂堆
先按照層次遍歷的結(jié)果將其還原成一個二叉樹
從葉子節(jié)點開始向上依次判斷，比如說要還原成一個小頂堆，就 要使得局部根節(jié)點的值比子節(jié)點要小，不符合的就互換一下
? 排序
通過排序使得關(guān)鍵字滿足遞增或者遞減的關(guān)系
穩(wěn)定的：原序列中有 Ri 和 Rj 的關(guān)鍵字相同，且 Ri 在 Rj 之 前，經(jīng)過排序算法后，還能保持 Ri 在 Rj 之前，那就是穩(wěn)定的，
103第 1 章 計算機系統(tǒng)知識
否則是不穩(wěn)定的
歸位：在排序時能確定最終排序位置，比如 Ri 排序后應該放在位 置 3 ，那在計算時如果開始沒將它放在 3 這個位置就是不歸位
? 直接插入排序
新序列中以 R1 開始，遍歷 原序列 R, 每個 Ri, 依次與新序列中 從后開始的關(guān)鍵字相比較，大的直接插入到后邊，小的繼續(xù)往前判斷， 直到插入
直接插入排序，穩(wěn)定、不歸位，平均復雜度 O(n^2), 最大復雜度 O(n^2), 最小復雜度 O(n), 空間復雜度 O(1)
適用于基本有序的情況
? 希爾排序
是直接插入排序算法的改進
方法：
設(shè)定一個增量序列，例如： 5 ， 3 ， 1
按照增量序列依次將原序列切割成多段，比如增量為 5 時，將第 0, 5, 10 位置的元素分為一組， 1 ， 6, 11 分為一組，以此 類推
每組間元素進行直接插入排序，排序后的值互換位置，插入回原 序列
按照增量序列依次處理，直到增量為 1
希爾排序：不穩(wěn)定、不歸位，平均復雜度 O(n^1.3), 最大復雜度 O(n^2), 最小復雜度 O(n), 空間復雜度 O(1)
? 計數(shù)排序
適合比較少數(shù)據(jù)量的排序
104第 1 章 計算機系統(tǒng)知識
就是將把要排序的數(shù)統(tǒng)計一下每種數(shù)據(jù)有多少個，然后依次添加到序 列中
? 簡單選擇排序
從首位開始，依次用后邊的關(guān)鍵字與當前的關(guān)鍵字比較，選出最小的 那個與當前位替換順序，直到最后一位為止
簡單選擇排序 : 不穩(wěn)定、歸位，平均復雜度 O(n^2), 最大復雜度 O(n^2), 最小復雜度 O(n^2), 空間復雜度 O(1)
? 堆排序
先將原序列，按照層級遍歷，成一個二叉樹；然后構(gòu)造一個大根堆或 者小根堆；將堆的根與堆的末位進行交換，然后再次構(gòu)造大根堆或者 小根堆；重復進行操作，直到整個堆變成一個新的序列
堆排序：不穩(wěn)定、歸位，平均復雜度 O(nlog2 n), 最大復雜度 O(nlog2 n), 最小復雜度 O(nlog2 n), 空間復雜度 O(1)
? 冒泡排序
從原序列首位開始，分別進行 ki 與 k(i+1) 位的比較，如果 如果 ki 更大則交換順序，這樣直到交換到最后一位，可以保證最后一位 是最大的，重復進行
冒泡排序：穩(wěn)定、歸位，平均復雜度 O(n^2), 最大復雜度 O(n^2), 最小復雜度 O(n), 空間復雜度 O(1)
? 快速排序
基于分治的思想，通過一趟排序?qū)⒋判虻挠涗浄譃閮蓚€部分（前半 區(qū)、后半?yún)^(qū)），前半?yún)^(qū)的關(guān)鍵字都不大于后半?yún)^(qū)的關(guān)鍵字，然后載分 別對兩部分進行快速排序，依次遞歸操作
105第 1 章 計算機系統(tǒng)知識
基本有序序列的快速排序效率最低，時間復雜度最大 O(n^2)
快速排序：不穩(wěn)定、歸位，平均復雜度 O(nlog2 n), 最大復雜度 O(n^2), 最小復雜度 O(nlog2 n), 空間復雜度 O(log2 n)
? 歸并排序
基于分治的思想，將一個序列一分為二，每一半再一分為二，如此遞 歸，直到每一項為 1 個，在從從底向上，每兩項間進行比較、每四項 間進行比較，如此向上遞歸，直到最外層；
歸并排序：穩(wěn)定、歸位，平均復雜度 O(nlog2 n), 最大復雜度 O(nlog2 n), 最小復雜度 O(nlog2 n), 空間復雜度 O(n)
? 回溯法
N 皇后問題：給定 N * N 的棋盤，要在棋盤上擺放 N 個皇后，皇 后中的任意兩個都不處于同一行，同一列，同一對角線上
判斷是否同一列： Qi 列 == Qj列；判斷是否在一個對角線： |Qi 行 - Qj 行 | == |Qi 列 - Qj 列 |
代碼求解 N 皇后問題
非遞歸（循環(huán)、迭代）
遞歸
深度優(yōu)先
主要考的是下午 C 語言計算題，放棄。。。
? 分治法
用遞歸來實現(xiàn)的
遞歸是指自己調(diào)用自己，或者間接的自己調(diào)用自己，有兩個基本要素： 1. 需要有邊界條件（遞歸出口）， 2. 遞歸模式（遞歸體）
分治法的基本思想：
106第 1 章 計算機系統(tǒng)知識
規(guī)模越小，解題所需時間越少，越容易處理
將一個難以解決的大問題，分解成一些規(guī)模較小的相同問題，以 便各個擊破，分而治之
分治算法三個步驟：
3. 分解：原問題分解為子問題
4. 求解：遞歸求解各個子問題
5. 合并：子問題的解合并成原問題的解
? 動態(tài)規(guī)劃法
與分治法類似，基本思想都是將問題分解為若干個子問題，然后求解 子問題，在通過子問題的解得到原問題的解
不同點：適合動態(tài)規(guī)劃法的問題分解為的子問題往往不是獨立的（有 相同的子問題）
操作上，將動態(tài)規(guī)劃法會用一個表記錄所有已解決的子問題答案，在 后續(xù)計算中如果有相同的問題，則直接找出已求解的答案，避免重復 計算
動態(tài)規(guī)劃算法，通常用來求解某種最優(yōu)性質(zhì)的問題（全局最優(yōu)解）
適合動態(tài)規(guī)劃法求解的問題的兩個特征：
最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解中包含其子問題的最優(yōu)解（需要 注意，貪心算法也有這個特性）
重疊子問題：原問題的遞歸算法可反復的解同樣的子問題，對每 個子問題只解一次，保存在表中，需要時查表
? 0-1 背包問題
問題詳情表： n 個物品，第 i 個物品價值為 vi, 重量 wi, 背包容量 W ，如何裝，使得背包物品價值最大
0-1 表示物品要么裝入，要么不裝入
代碼實現(xiàn)：放棄~~~
107第 1 章 計算機系統(tǒng)知識
背包問題時間復雜度： O(n * w); 空間復雜度： O(n * w)
? 矩陣連乘
由動態(tài)規(guī)劃法實現(xiàn)
時間復雜度： O(n^3); 空間復雜度： O(n^2)
計算方法 :
矩陣 A(mn) 與 B(np) 相乘所需的乘法次數(shù)為 m * n * p
相乘后的結(jié)果可以類似表示為 AB(mp) ，再次與 C(pk) 相乘 則所需乘法次數(shù)為 m * p * k
因此 A(mn), B(np), C(p*k) 三者相乘的乘法次數(shù)可以為 m * n * p + m * p * k
多個矩陣連乘，最優(yōu)的計算次序是先將 m, n, p, k 中最大的那 個乘以，消除掉
? 貪心法
貪心法與動態(tài)規(guī)劃法類似，也用來解決最優(yōu)化問題，但是在解決問題 的策略上，貪心法不是從整體最優(yōu)上考慮，而是局部最優(yōu)
適合貪心法求解的問題的兩個特征：
最優(yōu)子結(jié)構(gòu) : 一個問題的最優(yōu)解中包含其子問題的最優(yōu)解（需 要注意，貪心算法也有這個特性）
貪心選擇性質(zhì)：問題的整體最優(yōu)解，可以通過一系列局部最優(yōu)的 選擇，即貪心選擇來實現(xiàn)
部分背包問題
在 0-1 背包問題基礎(chǔ)上，物品可以部分裝入背包
? 分支限界法
類似于回溯法，也是一種在問題的解空間樹 T 上搜索問題解的方法，
108第 1 章 計算機系統(tǒng)知識
用來找出滿足約束條件的一個解
搜索方式上采用廣度優(yōu)先或以最小消耗優(yōu)先