1、軟件設(shè)計(jì)師筆記一、計(jì)算機(jī)系統(tǒng)基礎(chǔ)知識1. CPU 的功能：程序控制、操作控制、時間控制、數(shù)據(jù)處理。2. 計(jì)算機(jī)系統(tǒng)組成示意圖：3. 數(shù)據(jù)表示：原碼、反碼、補(bǔ)碼、移碼。（0 為正，1 為負(fù)）4. 移碼：如果機(jī)器字長為 N，偏移量為 2N-1，則X移=2N-1+X補(bǔ)(X 為純整數(shù))。X移=1+X（X為純小數(shù)）。5. IEEE754：符號位（1 位,0 正 1 負(fù)）+階碼（8 位,+127）+尾數(shù)（23 位,小數(shù)點(diǎn)在最高位之后，隨后省略最高位）。6. 浮點(diǎn)數(shù)加減：0 操作數(shù)檢查，對階操作(小階變大階)，尾數(shù)加減(階碼用雙符號位，尾數(shù)用單符號位)，結(jié)果規(guī)格化，舍入處理(判定溢出)。7. 常用校驗(yàn)碼：奇

2、偶校驗(yàn)碼（只能檢錯）、海明碼（糾錯加檢錯）、循環(huán)冗余校驗(yàn)碼（CRC）。8. 計(jì)算機(jī)體系結(jié)構(gòu)分類：單處理系統(tǒng)，并行處理與多處理系統(tǒng)，分布式處理系統(tǒng)。9. 指令集的發(fā)展:CISC（復(fù)雜指令集計(jì)算機(jī)）：增強(qiáng)原有指令的功能，用更為復(fù)雜的新指令取而代之；RISC（精簡指令集計(jì)算機(jī)）：減少指令總數(shù)簡化指令功能，優(yōu)化編譯降低復(fù)雜度。10. 指令控制方式：順序方式，重疊方式，流水方式。11.RISC 中的流水線技術(shù)：超流水線技術(shù)，量技術(shù)，超長指令字技術(shù)。12. 并發(fā)性的解決：陣列處理機(jī)，并行處理機(jī)，多處理機(jī)。13. 主存與 cache 地址映射方式：全相聯(lián)映射-將主存一個塊的地址與內(nèi)容一起存入 cache 中

3、，控制總線寄存器組控制器存儲器外存儲器輸出設(shè)備內(nèi)存儲器輸入設(shè)備IDARPCIRPSWDRACALURAMROM指令寄存器程序計(jì)數(shù)器地址寄存器指令譯碼器運(yùn)算器算術(shù)邏輯單元累加寄存器數(shù)據(jù)緩沖寄存器狀態(tài)條件寄存器軟件系統(tǒng)中央處理單元CPU硬件系統(tǒng)計(jì)算機(jī)拷貝靈活但是比較器電路難設(shè)計(jì)實(shí)現(xiàn)；直接映射-一個主存塊只能拷貝到 cache 的特定行上去，硬件簡單成本低但是容易沖突效率下降；組相聯(lián)映射-主存塊放到哪個組是固定的，但是放到哪一行是靈活的，折中辦法廣泛采用。14. 虛擬存儲器：頁式：頁表硬件小，查表速度快但不利于存儲保護(hù)；段式：界限分明便于程序的模塊化設(shè)計(jì)，易于編譯修改和保護(hù)，但主存利用率低，產(chǎn)生大量

4、碎片，查表速度慢； 段頁式：折中辦法，廣泛采用，但地址變換速度比較慢。15. 計(jì)算機(jī)與外設(shè)數(shù)據(jù)交換：無條件傳送，查詢方式傳送，中斷方式傳送，直接存儲器存取方式（DMA）：CPU 僅在過程開始和結(jié)束時有處理，過程中DMA 占用系統(tǒng)總線傳送數(shù)據(jù)。 16.多中斷處理辦法：多中斷信號線法，中斷軟件查詢法，菊花鏈法，總線仲裁法，中斷向量表法。17.總線分類：內(nèi)部總線：芯片的互連，系統(tǒng)總線：CPU，內(nèi)存，接口等的連接；外部總線： 數(shù)據(jù)交換。18.信息安全 5 要素：性，完整性，可用性，可控性，可審查性。19.加密技術(shù)：對稱加密（私人密鑰加密）：數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）+三重 DES+RC-5+國際數(shù)據(jù)加密算

5、法（IDEA）+高級加密標(biāo)準(zhǔn)（AES）；非對稱加密（公開密鑰加密，比如 RSA 算法）：加密模型+認(rèn)證模型。密和恢復(fù)系統(tǒng)、證書作廢系統(tǒng)、應(yīng)用接口。21. 計(jì)算機(jī)可靠性：可靠性：串聯(lián)系統(tǒng) R=R1*R2，并聯(lián)系統(tǒng) R=1-（1-R1）（1-R2）；平均無故障時間：串聯(lián)系統(tǒng) K=K1+K2，并聯(lián)系統(tǒng) K=1/K*(1+1/2)。22. 計(jì)算機(jī)系統(tǒng)性能評測常用方法：時鐘頻率，指令執(zhí)行速度，等效指令速度法，數(shù)據(jù)處理速率（PDR）。二、程序語言基礎(chǔ)知識1. 編程語言之間的翻譯形式：匯編，解釋，編譯。2. 程序設(shè)計(jì)語言的定義：語法，語義，語用。3. 程序語言的分類：命令式程序設(shè)計(jì)語言：FORTRAN，PA

6、SCAL，C 語言；面向?qū)ο蟮某绦蛟O(shè)計(jì)語言（C+，JAVA，smaltalk）；函數(shù)式程序設(shè)計(jì)語言（LISP）；邏輯型程序設(shè)計(jì)語言（PROLOG）。4. 程序語言的基本成分：數(shù)據(jù)，運(yùn)算，控制，傳輸。5. 匯編語言源程序：指令語句，偽指令語句，宏指令語句。6. 匯編程序：將匯編語言所編寫的源程序翻譯成機(jī)器指令程序。7. 編譯過程：源程序-詞法分析-語法分析-語義分析-中間代碼生成-代碼優(yōu)化-目標(biāo)代碼生成-目標(biāo)代碼。（另全過程有符號表管理和出錯處理）8. 解釋程序：分析部分：詞法分析、語法分析、語義分析-中間代碼；解釋部分：解釋執(zhí)行中間代碼。9. 編譯與解釋方式的比較：前者效率高；后者更具有靈活性

7、和可移植性。三、操作系統(tǒng)知識1. 操作系統(tǒng)的作用：通過資源管理提高計(jì)算機(jī)系統(tǒng)的效率；改善人機(jī)界面，向用戶提供友好的工作環(huán)境。2. 操作系統(tǒng)的特征：并發(fā)性、共享性、虛擬性和不確定性3. 操作系統(tǒng)的功能：處理機(jī)管理、文件管理、存儲管理、設(shè)備管理、作業(yè)管理4. 操作系統(tǒng)的類型：批處理操作系統(tǒng)（單道、多道）、分時操作系統(tǒng)（UNIX，多路性、獨(dú)立互性、及時性）、實(shí)時操作系統(tǒng)（快速的相應(yīng)時間、有限的交互能力、高可靠性）、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)、微機(jī)操作系統(tǒng)（Windows，Linux）、嵌入式操作系統(tǒng)5. 程序并發(fā)執(zhí)行的特點(diǎn)：失去了程序的封閉性，程序和機(jī)器的執(zhí)行程序的活動不再一一對應(yīng)，并發(fā)程序間的相

8、互制約性6. 進(jìn)程的組成：程序、數(shù)據(jù)、進(jìn)程控制塊（PCB）7. 進(jìn)程的狀態(tài)：新建、就緒、運(yùn)行、阻塞、終止8. 原語（若干條機(jī)器指令組成）的特點(diǎn)：執(zhí)行時不能被分割，要么都做要么都不做9. 進(jìn)程的同步：進(jìn)程間完成一項(xiàng)任務(wù)時直接發(fā)生相互作用的關(guān)系10 進(jìn)程的互斥：系統(tǒng)中各進(jìn)程互斥使用臨界資源11.信號量的意義：若 S=0 表示某資源的可用數(shù)；若 S具有通信功能的多機(jī)系統(tǒng)-以共享資源為目的的計(jì)算機(jī)網(wǎng)絡(luò)-以局域網(wǎng)及因特網(wǎng)為支撐環(huán)境的分布式計(jì)算機(jī)系統(tǒng)2. 計(jì)算機(jī)網(wǎng)絡(luò)的功能：數(shù)據(jù)通信，資源共享，負(fù)載均衡，高可靠性3. 計(jì)算機(jī)網(wǎng)絡(luò)的分類：局域網(wǎng)（LAN：10m1000m），城域網(wǎng)（MAN：10km），廣域網(wǎng)（

9、WAN：100km 以上）4. 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：總線型，星型，環(huán)型，樹型，分布式（無嚴(yán)格的布線規(guī)定和形狀，各節(jié)點(diǎn)有多條線路相連）5. OSI 七層參考模型：物理層（物理地傳送比特流），數(shù)據(jù)鏈路層（負(fù)責(zé)兩相鄰節(jié)點(diǎn)間無差錯傳送以幀為單位的數(shù)據(jù)），網(wǎng)絡(luò)層（提供端到端的交換網(wǎng)絡(luò)數(shù)據(jù)傳送功能），傳輸層（提供可靠的數(shù)據(jù)傳輸服務(wù)），會話層（提供會話管理服務(wù)），表示層（提供格式化的表示和轉(zhuǎn)換數(shù)據(jù)服務(wù)），應(yīng)用層（提供網(wǎng)絡(luò)與用戶應(yīng)用軟件之間的接口服務(wù)）6. 網(wǎng)絡(luò)互連設(shè)備：中繼器（物理層上實(shí)現(xiàn)局域網(wǎng)網(wǎng)段互連，用于擴(kuò)展局域網(wǎng)網(wǎng)段長度），集線器（特殊的多路中繼器，有信號方能并便于網(wǎng)絡(luò)維護(hù)）；網(wǎng)橋（工作與數(shù)據(jù)鏈路層，用于連

10、接兩個局域網(wǎng)網(wǎng)段），交換機(jī)（按每一個包中的 MAC 地址相對簡單地決策信息轉(zhuǎn)發(fā)）；路由器（網(wǎng)絡(luò)層異構(gòu)互連，連接多個邏輯上分開的網(wǎng)絡(luò)），網(wǎng)關(guān)（在兩個不同類型協(xié)議的網(wǎng)絡(luò)系統(tǒng)之間進(jìn)行通信）7.網(wǎng)絡(luò)傳輸介質(zhì)：有線介質(zhì)（雙絞線，同軸電纜：直接傳輸數(shù)字信號，光纖：傳輸光信號、需信號轉(zhuǎn)換）；無線介質(zhì)（微波：利用無線電波傳輸，紅外線：傳輸紅外光信號，激光：傳激光信號，通信：傳輸電磁波信號）8. 局域網(wǎng)組成部件：服務(wù)器（文件服務(wù)器、打印服務(wù)器、通信服務(wù)器），客戶端（用戶與網(wǎng)絡(luò)應(yīng)用接口設(shè)備），網(wǎng)絡(luò)設(shè)備（網(wǎng)卡，收發(fā)器，中繼器，集中器，網(wǎng)橋，路由器等），通信介質(zhì)（數(shù)據(jù)的傳輸媒體），網(wǎng)絡(luò)軟件（底層協(xié)議軟件、網(wǎng)絡(luò)操作系統(tǒng)

11、等）9. 協(xié)議：規(guī)定通信時的數(shù)據(jù)格式、數(shù)據(jù)傳送時序以及相應(yīng)的控制信息和應(yīng)答信號等內(nèi)容10.網(wǎng)絡(luò)的標(biāo)準(zhǔn)：電信標(biāo)準(zhǔn)，國際標(biāo)準(zhǔn)（IEEE 標(biāo)準(zhǔn)等），Internet 標(biāo)準(zhǔn)（自發(fā)標(biāo)準(zhǔn)非干預(yù)）11. 決定局域性的主要技術(shù)：用以傳輸數(shù)據(jù)的傳輸介質(zhì)，用以連接各種設(shè)備的拓?fù)浣Y(jié)構(gòu)，用以共享資源的介質(zhì)訪問控制方法12. 局域網(wǎng)協(xié)議：LAN 模型（物理層，數(shù)據(jù)鏈路層：邏輯鏈路控制子層、介質(zhì)訪問控制）；以太網(wǎng)（CSMA/CD 技術(shù)：邊發(fā)送邊接收、時刻偵聽信道）；令牌環(huán)網(wǎng)（適用于環(huán)型網(wǎng)絡(luò)結(jié)構(gòu)的分布式介質(zhì)訪問控制：廣播發(fā)送令牌、目標(biāo)站進(jìn)行處理）；FDDI（類似令牌環(huán)網(wǎng)協(xié)議、光纖作為傳輸介質(zhì)）13. 廣域網(wǎng)協(xié)議：點(diǎn)對點(diǎn)協(xié)議

12、（PPP：主要用于撥號上網(wǎng)，建立點(diǎn)對點(diǎn)連接發(fā)送數(shù)據(jù)），數(shù)字用戶線（xDSL：不對稱數(shù)字用戶線ADSL，甚高速數(shù)字用戶線 VDSL），數(shù)字專線（電信數(shù)字?jǐn)?shù)據(jù)網(wǎng)固定專線，電信鋪設(shè)），幀中繼（在用戶網(wǎng)絡(luò)接口之間提供用戶信息流的雙向傳送， 并保持順序不變），異步傳輸模式（ATM：面向分組的快速分組交換模式，使用異步時分復(fù)用技術(shù)），X.25 協(xié)議（在本地?cái)?shù)據(jù)終端設(shè)備和遠(yuǎn)程數(shù)據(jù)終端設(shè)備之間提供一個全雙工、同步的透明信道）14. TCP/IP 協(xié)議簇特性：邏輯編址，路由選擇，域名解析，錯誤檢測和流量控制15. TCP/IP 模型16. Internet 地址格式：域名格式，IP 地址格式17. 解決 IP

13、地址短缺問題：長期（使用 Ipv6），短期（使用網(wǎng)絡(luò)地址翻譯技術(shù) NAT：在子網(wǎng)內(nèi)部使用局部地址，外部使用少量的全局地址，通過路由器進(jìn)行內(nèi)部地址和外部地址的轉(zhuǎn)換）18. Ipv6：40 個字節(jié)的首部長度，16 個字節(jié)的 IP 地址長度19.服務(wù)端口：公共端口（01023）注冊登記端口（102465535）20.Internet 高層協(xié)議：域名服務(wù)（UDP 端口，53，通過 DNS 服務(wù)器將域名變換為 IP 地址）；遠(yuǎn)程登錄服務(wù)（TCP 端口，23，將用戶計(jì)算機(jī)與遠(yuǎn)程主機(jī)連接起來）；電子郵件服務(wù)（TCP端口，25：SMTP and 110：POP3，發(fā)送：SMTP，接收：SMTP+POP3）；W

14、WW 服務(wù)（TCP端口，80，基于客戶端/服務(wù)器模式的信息發(fā)送技術(shù)和超文本技術(shù)的綜合）；文件傳輸服務(wù)（TCP 端口，20：數(shù)據(jù)連接 and 21：控制連接）21.網(wǎng)絡(luò)安全的威脅：計(jì)算機(jī)存儲著國家、機(jī)構(gòu)、組織的信息或個人的隱私成為某類人攻擊的目標(biāo)；軟件規(guī)模的膨脹容易使系統(tǒng)存在缺陷；信息傳輸?shù)陌踩源嬖陔[患；網(wǎng)絡(luò)協(xié)議本身的漏洞也會引發(fā)安全問題22. 網(wǎng)絡(luò)安全：運(yùn)行系統(tǒng)安全，信息系統(tǒng)的安全，信息傳播的安全，信息內(nèi)容的安全23. 信息系統(tǒng)的需求：保密性，完整性，可用性，可控性，可核查性24. 網(wǎng)絡(luò)的安全威脅：物理威脅，網(wǎng)絡(luò)攻擊，身份鑒別，編程威脅，系統(tǒng)漏洞25. 網(wǎng)絡(luò)的信息安全：信息的存儲安全（用戶的

15、標(biāo)識與驗(yàn)證，用戶存取權(quán)限限制，系統(tǒng)安全監(jiān)控，計(jì)算機(jī)病毒防治，數(shù)據(jù)的加密，計(jì)算機(jī)網(wǎng)絡(luò)安全）；信息的傳輸安全（鏈路加密，節(jié)點(diǎn)加密，端到端加密）26.：建立在內(nèi)外網(wǎng)絡(luò)邊界的過濾機(jī)制，防止不良數(shù)據(jù)包進(jìn)出被保護(hù)的內(nèi)部網(wǎng)絡(luò)27. 的分類：包過濾型（直接轉(zhuǎn)發(fā)報(bào)文，對用戶透明），應(yīng)用網(wǎng)關(guān)型（通過服務(wù)器建立連接），狀態(tài)檢測型（建立狀態(tài)連接表，跟蹤檢測每一個會話狀態(tài)）應(yīng)用層文件傳輸協(xié)議 FTP遠(yuǎn)程登錄協(xié)議Telnet電子郵件協(xié)議 SMTP網(wǎng)絡(luò)文件服務(wù)協(xié)議NFS網(wǎng)絡(luò)管理協(xié)議SNMP應(yīng)用層表示層會話層傳輸層TCPUDP傳輸層網(wǎng)絡(luò)層IPICMPARP （地址解析協(xié)議）RARP網(wǎng)際層數(shù)據(jù)鏈路層Ethernet IEEE

16、802.3FDDIToken-Ring/ IEEE 802.5ARCnetPPP/SLIP網(wǎng)絡(luò)接口層物理層硬件層28.典型的體系結(jié)構(gòu)：包過濾路由器（在網(wǎng)絡(luò)層對進(jìn)出內(nèi)部網(wǎng)絡(luò)所有信息進(jìn)行分析限屏屏六、多媒體基礎(chǔ)知識1.媒體：感覺媒體（使人產(chǎn)生感覺的媒體），表示媒體（傳輸感覺媒體的中介媒體），表現(xiàn)媒體（進(jìn)行信息輸入和輸出的媒體），存儲媒體（用于存儲表示媒體的物理介質(zhì)），傳輸媒體（傳輸表示媒體的物理介質(zhì)）2. 多媒體的特性：多樣性，集構(gòu)的動態(tài)性3. 虛擬現(xiàn)實(shí)：運(yùn)用計(jì)算機(jī)對現(xiàn)實(shí)世界進(jìn)行全面仿真，創(chuàng)建與現(xiàn)實(shí)社會類似的環(huán)境，通過多種傳感設(shè)備使用戶“投入到該環(huán)境中”，實(shí)現(xiàn)用戶與該環(huán)境直接進(jìn)行自然交互4. 虛擬

17、現(xiàn)實(shí)技術(shù)的特征：多感知（聽覺感知、力覺感知、觸覺感知、運(yùn)動感知、味覺感知、嗅覺感知），沉浸（用戶感受到的模擬環(huán)境的真實(shí)程度），交互（用戶對模擬環(huán)境內(nèi)物體的可操作程度和從環(huán)境得到反饋的自然程度）5. 虛擬現(xiàn)實(shí)的分類：桌面虛擬現(xiàn)實(shí)，完全沉浸的虛擬現(xiàn)實(shí)，增強(qiáng)現(xiàn)實(shí)性的虛擬現(xiàn)實(shí)，分布式虛擬現(xiàn)實(shí)6. 聲音感覺的三個指標(biāo)：音量，音調(diào)，音色，交互性，非線性，實(shí)時性，信息使用的方便性，信息結(jié)7.聲音信號的數(shù)字化：采樣，量化，編碼8. 數(shù)字語音的數(shù)據(jù)壓縮方法：波形編碼，參數(shù)編碼，混合編碼9. 聲音合成：語音合成（發(fā)音參數(shù)合成、聲道模型參數(shù)合成、波形編輯合成），音樂合成10. MIDI（樂器數(shù)字接口）：數(shù)字音樂的國

18、際標(biāo)準(zhǔn)11. 色彩三要素：亮度，色調(diào)，色飽和度12. 彩色空間：RGB，CMY，YUV 等13. 圖形數(shù)據(jù)表示形式：矢量圖形（用數(shù)學(xué)的方式描述圖像），位圖圖像（用像素點(diǎn)來描述的圖）14. 圖像的屬性：分辨率，圖像深度，真彩色和偽彩色15. 圖像的數(shù)據(jù)量：圖像的總像素*圖像深度/816. 數(shù)據(jù)壓縮：有損壓縮（壓縮過程中損失一定信息），無損壓縮（行程長度編碼，增量調(diào)制編碼，霍夫曼編碼）17. 多媒體數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)：JPEG，MPEG，H.26118. 動畫（本質(zhì)是運(yùn)動）：實(shí)時動畫（用各種算法來實(shí)現(xiàn)運(yùn)動物體的運(yùn)動控制），矢量動畫（由矢量圖衍生出的動畫形式），二維動畫（對傳統(tǒng)動畫的一個改進(jìn)），三維動

19、畫（根據(jù)三維數(shù)據(jù)模型）19. 彩色電視制式：NTSC 制，PAL 制，SECAM 制20. 數(shù)字視頻標(biāo)準(zhǔn)：采樣頻率，分辨率，數(shù)據(jù)量21. 超文本（將文本中遇到的一些相關(guān)內(nèi)容通過鏈接組織在一起）三要素：節(jié)點(diǎn)，鏈，網(wǎng)絡(luò)22. 超媒體：用超文本方式組織和處理多媒體信息23. 流媒體：在網(wǎng)絡(luò)中使用流式傳輸技術(shù)的連續(xù)時基載體。信息經(jīng)過壓縮之后放到專用流服務(wù)器上，讓瀏覽者一邊下載一邊觀看或收聽24. 多媒體計(jì)算機(jī)硬件系統(tǒng)：音頻卡，視頻卡，光盤驅(qū)動器，掃描儀，光學(xué)字符閱讀器，觸摸屏，數(shù)字化儀，操縱桿，繪圖儀、投影儀和激光視盤播放器25.多媒體計(jì)算機(jī)軟件系統(tǒng)：多媒體操作系統(tǒng)，多媒體應(yīng)用軟件的開發(fā)工具，多媒體應(yīng)

20、用軟件七、數(shù)據(jù)庫技術(shù)基礎(chǔ)1. 數(shù)據(jù)庫系統(tǒng)：數(shù)據(jù)庫，硬件，軟件，人員2. DBMS（數(shù)據(jù)庫管理系統(tǒng)）的功能：數(shù)據(jù)定義，數(shù)據(jù)庫操作，數(shù)據(jù)庫運(yùn)行管理，數(shù)據(jù)組織、存儲和管理，數(shù)據(jù)庫的建立和維護(hù)，與其他軟件系統(tǒng)的通信功能等3. DBMS 的特征：數(shù)據(jù)結(jié)構(gòu)化且統(tǒng)一管理，有較高的數(shù)據(jù)獨(dú)立性，數(shù)據(jù)控制功能（數(shù)據(jù)庫的安全性保護(hù)、數(shù)據(jù)的完整性、并發(fā)控制、故障恢復(fù)）4. DBMS 分類：關(guān)系數(shù)據(jù)庫系統(tǒng)（實(shí)體間的聯(lián)系用關(guān)系表示），面向?qū)ο蟮臄?shù)據(jù)庫系統(tǒng)（以對象形式對數(shù)據(jù)建模），對象關(guān)系數(shù)據(jù)庫系統(tǒng)（在關(guān)系數(shù)據(jù)模型基礎(chǔ)上提供處理新的數(shù)據(jù)類型操作的能力）5 數(shù)據(jù)庫系統(tǒng)體系結(jié)構(gòu)：集中式（數(shù)據(jù)、數(shù)據(jù)管理、數(shù)據(jù)庫功能等都集中在一起

21、），分布式（物理上分布+邏輯上分布），C/S 模式（客戶端負(fù)責(zé)數(shù)據(jù)表示服務(wù)、服務(wù)器負(fù)責(zé)數(shù)據(jù)庫服務(wù)），并行結(jié)構(gòu)（多個 CPU 物理上連在一起處理）6. 數(shù)據(jù)庫的三級模式：概念模式（數(shù)據(jù)庫中全部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述、只涉及型的描述而不涉及具體的值），外模式（用戶與數(shù)據(jù)庫系統(tǒng)的接口、用戶用到那部分?jǐn)?shù)據(jù)的描述），內(nèi)模式（數(shù)據(jù)物理結(jié)構(gòu)和存儲方式的描述、數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式）7. 數(shù)據(jù)庫的兩級映像：模式/內(nèi)模式映像（實(shí)現(xiàn)概念模式與內(nèi)模式的轉(zhuǎn)換），外模式/模式映像（實(shí)現(xiàn)外模式與概念模式的轉(zhuǎn)換）8. 數(shù)據(jù)的獨(dú)立性：物理獨(dú)立性（數(shù)據(jù)庫的內(nèi)模式改變時數(shù)據(jù)的邏輯結(jié)構(gòu)不變），邏輯獨(dú)立性（用戶的應(yīng)用程序與數(shù)

22、據(jù)庫的邏輯結(jié)構(gòu)相互獨(dú)立）9. 數(shù)據(jù)模型：概念數(shù)據(jù)模型（E-R 模型等），基本數(shù)據(jù)模型（層次模型：用樹型結(jié)構(gòu)表示數(shù)據(jù)間的聯(lián)系、網(wǎng)狀模型：用網(wǎng)絡(luò)結(jié)構(gòu)表示數(shù)據(jù)間的聯(lián)系、關(guān)系模型：用表格結(jié)構(gòu)表示實(shí)體間的聯(lián)系、面向?qū)ο竽Ｐ停簩ο髽?biāo)識+封裝+對象的屬性+類和類層次+繼承）10. 數(shù)據(jù)模型三要素：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)操作，數(shù)據(jù)的約束條件11.E-R 圖：實(shí)體（矩形），聯(lián)系（菱形），屬性（橢圓形）12. 完整性約束：實(shí)體完整性，參照完整性，用戶自定義完整性13. 關(guān)系代數(shù)運(yùn)算：并，交，差，笛卡爾積，投影，選擇，連接，除14. SQL 語言的特點(diǎn)：綜合統(tǒng)一，高度非過程化，面向集合的操作方式，兩種使用方式（自含式、嵌入

23、式），語言簡潔易學(xué)易用15. SQL 語言的組成：數(shù)據(jù)定義語言，交互式數(shù)據(jù)操縱語言，事務(wù)控制，嵌入式 SQL 和動態(tài)SQL，完整性，權(quán)限管理16. SQL 數(shù)據(jù)定義：創(chuàng)建（create），修改（alter），刪除（drop）：表（table），視圖（viewas select），索引（indexon）17. SQL 數(shù)據(jù)查詢：select.from.where.group by.having.order by.P37518. 插入數(shù)據(jù)：insert into.values.19. 修改數(shù)據(jù)：update.set.=.where.20. 刪除數(shù)據(jù)：delete from.where.21. 授權(quán)

24、：grant.on.to(with grant option)22. 回收權(quán)限：revoke.on.from.23. 函數(shù)依賴：反映屬性間的聯(lián)系（XY）；完全函數(shù)依賴：（學(xué)生 ID，所修課程 ID）成績；部分函數(shù)依賴 ：（學(xué)生 ID，所修課程 ID）學(xué)生姓名；平凡函數(shù)依賴：XY 且 Y 包含于X；非平凡函數(shù)依賴：XY 且Y 不包含于X；傳遞函數(shù)依賴：XY，YZ24. 規(guī)范化：1NF：每個分量都不可再分；2NF：消除非主屬性對碼的部分函數(shù)依賴；3NF：消除非主屬性對碼的傳遞函數(shù)依賴25. 模式分解標(biāo)準(zhǔn)：無損連接，保持函數(shù)依賴26. 事務(wù)的 ACID 性質(zhì)：原子性，一致性，隔離性，持久性27. 事

25、務(wù)管理：事務(wù)開始（begin transaction），事務(wù)提交（commit），事務(wù)回滾（rollback） 28.數(shù)據(jù)庫故障：事務(wù)內(nèi)部故障，系統(tǒng)故障，介質(zhì)故障，計(jì)算機(jī)病毒29. 數(shù)據(jù)備份方法：靜態(tài)轉(zhuǎn)儲和動態(tài)轉(zhuǎn)儲，海量轉(zhuǎn)儲和增量轉(zhuǎn)儲，日志文件30. 數(shù)據(jù)恢復(fù)步驟：反向掃描文件日志，對事物的更新操作執(zhí)行逆操作，繼續(xù)反向掃描和更新，直到事務(wù)的開始標(biāo)志31. 并發(fā)控制的技術(shù)：32. 數(shù)據(jù)不一致性：丟（寫鎖、讀鎖）改，不可重復(fù)讀，讀臟數(shù)據(jù)八、數(shù)據(jù)結(jié)構(gòu)1. 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的集合及元素間的相互關(guān)系和構(gòu)造方法2. 線性表的存儲結(jié)構(gòu)：順序存儲，鏈?zhǔn)酱鎯?. 單鏈表節(jié)點(diǎn)：typedef struct no

26、deint data;struct node *link;NODE,*LinkList; 4.雙向鏈表：每個節(jié)點(diǎn)有兩個指針，分別指出直接前驅(qū)和直接后繼5. 循環(huán)鏈表：尾節(jié)點(diǎn)指針指向第一個節(jié)點(diǎn)6. 靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7. 棧：后進(jìn)先出；初始化棧：InitStack(S) 判?？眨篠tackEmpty(S) 入棧：Push(S,x) 出棧：Pop(S) 讀取棧頂元素：Top(S)順序存儲+鏈?zhǔn)酱鎯?. 隊(duì)列：先進(jìn)先出，尾入頭出；初始化隊(duì)：初始化隊(duì)：InitQueue(Q) 判隊(duì)空：Empty(Q) 入隊(duì)：EnQueue(Q,x) 出隊(duì)：DeQueue(Q) 讀隊(duì)頭元素：F

27、rontQue(Q)順序存儲+鏈?zhǔn)酱鎯?. 串：僅由字符構(gòu)成的有限序列，是取值范圍受限的線性表串的模式匹配10. 數(shù)組：定長線性表在維數(shù)上的擴(kuò)張，一般不做插入刪除運(yùn)算11. 矩陣：特殊矩陣（元素分布有一定的規(guī)律：對稱矩陣、三角矩陣、對角矩陣）；稀疏矩陣（非零元素遠(yuǎn)少于零元素且肺部無規(guī)律：用三元組存儲(行號，列號，值)）12. 廣義表（表中有表）：表頭（表中第一個元素）；表尾（表中除去表頭剩下的部分）13. 樹：遞歸的，元素之間有明顯的層次關(guān)系14. 完全二叉樹應(yīng)采用順序存儲結(jié)構(gòu)，一般二叉樹則應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)15. 二 叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) :typedef struct BiTnode int

28、 data; struct BiTnode *lchild,*rchild;BiTnode,*BiTree;16. 二叉樹的遍歷：先序遍歷（先訪問根節(jié)點(diǎn)），中序遍歷（第二訪問根節(jié)點(diǎn)），后序遍歷（最后訪問根節(jié)點(diǎn)），層序遍歷（利用隊(duì)列、每次出同一層的節(jié)點(diǎn)時進(jìn)他們的子節(jié)點(diǎn)層）17. 線索二叉樹：加上線索（直接前驅(qū)和直接后繼）的二叉樹18. 最優(yōu)二叉樹（哈夫曼樹）：一類帶權(quán)路徑長度最短的樹19. 樹的存儲結(jié)構(gòu)：雙親表示法（順序存儲）；孩子表示法（鏈?zhǔn)酱鎯Γ?；孩子兄弟表示法（鏈?zhǔn)酱鎯Γ瑑蓚€指針分別為第一個孩子和下一個兄弟）20. 圖：一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)數(shù)目沒有任何限制21. 圖的表示：G=(V

29、，E)；V：頂點(diǎn)的集合；E：邊的集合22. 網(wǎng)：邊帶權(quán)值的圖23. 圖的相關(guān)概念網(wǎng)完全圖子圖路徑度連通圖出度有向樹連通分量入度強(qiáng)連通圖強(qiáng)連通分量24. 圖的存儲結(jié)構(gòu)：鄰接矩陣表示法，鄰接鏈表表示法25. 圖的遍歷：深度優(yōu)先搜索，廣度優(yōu)先搜索26. 生成樹：極小連通子圖，針對連通圖27. 最小生成樹（權(quán)值和最小的生成樹）算法：普尼姆算法（在相鄰邊的基礎(chǔ)上求最小，與邊數(shù)無關(guān)，適于邊稠密的網(wǎng)）；克魯斯科爾算法（在不構(gòu)成環(huán)的基礎(chǔ)上找最小邊直至連通，與頂點(diǎn)數(shù)無關(guān)，適于邊稀疏的網(wǎng)）28. AOV 網(wǎng)：有向圖中頂點(diǎn)表示活動，有向邊表示活動間的優(yōu)先關(guān)系29. 拓?fù)渑判颍簩OV 網(wǎng)中所有頂點(diǎn)按優(yōu)先順序排成一個

30、線性序列的過程30. AOE 網(wǎng)：有向圖中有向邊表示活動，邊上的權(quán)值表示該活動持續(xù)的時間31. 關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的路徑中長度最長的32. 最短路徑：從源點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯克拉算法33. 平均查找長度：關(guān)鍵字和給定值進(jìn)行過比較的記錄個數(shù)的平均值34. 靜態(tài)查找方法：順序查找；折半查找；分塊查找35. 動態(tài)查找：表結(jié)構(gòu)本身在查找過程中是動態(tài)生成的36. 二叉排序樹：左子樹上所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，右子樹上所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值37. 平衡二叉樹（AVL 樹）：左子樹和右子樹高度之差的絕對值不超過 138. B_樹（m 階）：每個節(jié)點(diǎn)子樹個數(shù)=2，其他節(jié)點(diǎn)子樹個數(shù)=0或=m

31、/239. 哈希表：通過哈希函數(shù)（以記錄的關(guān)鍵字為自變量）得到記錄的存儲地址；定長按一定函數(shù)規(guī)律存放數(shù)據(jù)；哈希地址+關(guān)鍵字40. 哈希表的重點(diǎn)：構(gòu)造哈希函數(shù)（直接定址法，數(shù)字分析法，平方取中法，折疊法，隨機(jī)數(shù)法，除留余數(shù)法）；解決沖突（開放定址法，鏈地址法，再哈希法）41. 簡單排序（時間復(fù)雜度O(n2)，空間復(fù)雜度 O(1)）：直接插入排序（插入第 i 個時前 i-1 個以排序好）；冒泡排序（相鄰兩個比較排序，每次循環(huán)確定一個極值）；簡單選擇排序（第 i個依次與后面每個元素比較排序，每次循環(huán)確定一個極值，不穩(wěn)定）42. 高端內(nèi)部排序：希爾排序（先將整個序列分割成若干序列分別進(jìn)行直接插入排序，

32、再對有向圖無向圖圖整個序列進(jìn)行一次直接插入排序，不穩(wěn)定）；快速排序（將整個記錄分割成獨(dú)立的兩部分，兩個指針分別指向?qū)?yīng)部分的兩端，往中間移動比較排序，遞歸，不穩(wěn)定）；堆排序（建立初始堆輸出并刪除堆頂關(guān)鍵字，再建立新堆得到新的關(guān)鍵字依次輸出，不穩(wěn)定）；歸并排序（將若干個有序序列合并為新的有序序列）；基數(shù)排序（按組成關(guān)鍵字的各個數(shù)位的值進(jìn)行排序）9、算法設(shè)計(jì)與分析1. 算法的特性：有窮性，確定性，可行性，輸入，輸出2. 算法的表示方法：自然語言，流程圖，程序設(shè)計(jì)語言，偽代碼3. 遞歸算法求時間復(fù)雜度：展開法（將等式依次展開）；代換法（用所猜測的值代替函數(shù)的解）4. 分治法（將一個難以直接解決的大問

33、題分解成一些規(guī)模較小的小問題各個擊破）：分解，求解，合并5. 動態(tài)規(guī)劃法（將待求解問題分解成若干子問題分別求解，再根據(jù)子問題的解得到原問題的解；分解得到的子問題往往不是獨(dú)立的）：找出最優(yōu)解性質(zhì)并刻畫其結(jié)構(gòu)特性；遞歸地定義最優(yōu)解的值；以自底向上的方式求出最優(yōu)值；根據(jù)最優(yōu)值構(gòu)造最優(yōu)解6. 貪心算法（僅根據(jù)當(dāng)前已有信息做出選擇，重點(diǎn)考慮局部最優(yōu)以達(dá)到全局最優(yōu)）：最優(yōu)子結(jié)構(gòu)；貪心選擇性質(zhì)7. 回溯法（以深度優(yōu)先的方式系統(tǒng)地搜索問題）：定義問題的解空間；確定解空間結(jié)構(gòu)；深度優(yōu)先的方式搜索解空間8. 分支限界法（以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間）：隊(duì)列式分支限界法；優(yōu)先隊(duì)列式分支限界法9. 概率

34、算法（把隨機(jī)性的選擇加入到算法中，允許較小概率的錯誤來提高運(yùn)行效率）：數(shù)值概率算法；蒙特卡羅算法；拉斯維加斯算法；舍伍德算法10. 近似算法（放棄求最優(yōu)解，而用近似最優(yōu)解代替）衡量標(biāo)準(zhǔn)：算法的時間復(fù)雜度；解的近似程度11. NP 完全性理論：研究計(jì)算問題難易以及一類特殊的難解問題的理論12. P 類問題：能夠以O(shè)(nk)的時間運(yùn)行一個確定性算法得到準(zhǔn)確答案13. NP 類問題：能夠以 O(nk)的時間運(yùn)行一個不確定性算法得到準(zhǔn)確答案14. NP 完全問題：能夠證明用多項(xiàng)式時間的確定性算法得到準(zhǔn)確答案10、面向?qū)ο蠹夹g(shù)1. 面向?qū)ο蠹夹g(shù)：以客觀世界的對象為中心，其分析和設(shè)計(jì)思想符合人們的思維方式

35、，分析和設(shè)計(jì)的結(jié)果與客觀世界的實(shí)際比較接近，容易被人們所接受2. 面向?qū)ο螅簩ο螅▽ο竺?、屬性、操作），分類（所包含的方法和?shù)據(jù)描述一組對象的共同行為和屬性），繼承（父類與子類之間共享數(shù)據(jù)和方法的機(jī)制），通過消息的通信（對象之間進(jìn)行通信的一種構(gòu)造）3. 多態(tài)：不同的對象收到同意消息產(chǎn)生完全不同的結(jié)果（重載+重寫+類屬）4. 綁定：把過程調(diào)用和響應(yīng)調(diào)用所需要執(zhí)行的代碼加以結(jié)合的過程5. 動態(tài)綁定：當(dāng)一個對象發(fā)送消息請求服務(wù)時，根據(jù)接受對象的具體情況將請求的操作與實(shí)現(xiàn)的方法進(jìn)行連接6. 面向?qū)ο蟪绦蛟O(shè)計(jì)語言應(yīng)支持：被封裝的對象；類和實(shí)例概念；類間的繼承性；多態(tài)7. 程序設(shè)計(jì)范型：人們在程序設(shè)計(jì)時所

36、采用的基本方式模型；（+類+繼承性=面向?qū)ο蟪绦蛟O(shè)計(jì)范型）8. 面向?qū)ο蟮暮锰帲航鉀Q了產(chǎn)品質(zhì)量與生產(chǎn)率之間的權(quán)衡；使系統(tǒng)具有很高的靈活性和易擴(kuò)充性；能管理復(fù)雜性并增強(qiáng)伸縮性；把某一領(lǐng)域分割成各種對象分析設(shè)計(jì)更合理；從概念模型化到分析、設(shè)計(jì)、編碼可以實(shí)現(xiàn)無縫傳遞；通過封裝進(jìn)行信息隱蔽有助于建立安全的系統(tǒng)9.典型的面向?qū)ο笤O(shè)計(jì)語言：Smalltalk，Eiffel，C+，JAVA10.類的特征：同一個類的不同實(shí)例具有相同的數(shù)據(jù)結(jié)構(gòu)和規(guī)律相同的行為；同一個類的不同實(shí)例可以持有不同的值因而可以具有不同的狀態(tài)；實(shí)例的初始狀態(tài)可以在實(shí)例化時確定11.消息傳遞：使對象具有交互能力的主要模型12. 對象自身引

37、用（this）：值使得方法體中引用的成員名與特定的對象相關(guān)；類型則決定了方法體被實(shí)際共享的范圍13. 虛擬函數(shù)：只給出方法的定義不給出實(shí)現(xiàn)過程，供其子類重置（overriding）14. 類屬：類的模版；參數(shù)多態(tài)機(jī)制；不限定成員的類型，具體對象再賦予具體類型15. 類庫：預(yù)先定義的程序庫，以程序模塊的形式按照類層次結(jié)構(gòu)把一組類的定義和實(shí)現(xiàn)組織在一起16. 抽象類：無實(shí)例的類，以供繼承17. 面向?qū)ο蠓治觯赫J(rèn)定對象；組織對象；描述對象間的相互作用；定義對象的操作；定義對象的內(nèi)部信息18. 面向?qū)ο笤O(shè)計(jì)：設(shè)計(jì)分析模型，實(shí)現(xiàn)相應(yīng)源代碼19. 面向?qū)ο筌浖臏y試：算法層，類層，模版層，系統(tǒng)層20. 面

38、向?qū)ο蟮姆椒ǎ篛OA 方法：主題層，對象類層，結(jié)構(gòu)層，屬性層，服務(wù)層；OOD 方法：問題域部件，人機(jī)交互部件，任務(wù)管理部件，數(shù)據(jù)管理部件；Booch 的 OOD 方法：標(biāo)識類和對象，確定他們的含義，標(biāo)識他們之間的關(guān)系，說明每一個類的界面和實(shí)現(xiàn)；OMT（面向?qū)ο蠼＜夹g(shù)）：對象模型，動態(tài)模型，功能模型-分析，系統(tǒng)設(shè)計(jì)，對象設(shè)計(jì)，實(shí)現(xiàn)；UML（統(tǒng)一建模語言）：事務(wù)（結(jié)構(gòu)事務(wù)、行為事務(wù)、分組事務(wù)、注釋事務(wù)），關(guān)系（依賴、關(guān)聯(lián)、泛化、實(shí)現(xiàn)），圖（類圖、對象圖、用例圖、交互圖、狀態(tài)圖、活動圖、構(gòu)建圖、部署圖）21. 設(shè)計(jì)模式四要素：模式名稱，問題，解決方案，效果22.設(shè)計(jì)模式分類：創(chuàng)建型（抽象了實(shí)例化過

39、程，幫助系立于如何創(chuàng)建、組合和表示它的那些對象，如 Singleton 模式：保證類只能有一個實(shí)例），結(jié)構(gòu)型（采用繼承機(jī)制靈活地組合類和對象以獲得更大的結(jié)構(gòu)），行為型（使用繼承機(jī)制在類間分派行為，描述對象或類的模式以及其通信模式，如 Observer 模式：一旦模型發(fā)生變化所有視圖都會得到 P550）1 、標(biāo)準(zhǔn)化和軟件知識產(chǎn)權(quán)基礎(chǔ)1. 標(biāo)準(zhǔn)：對重復(fù)性事務(wù)和概念所做的統(tǒng)一規(guī)定2. 標(biāo)準(zhǔn)化對象：標(biāo)準(zhǔn)化的具體對象（需要指定標(biāo)準(zhǔn)的具體事務(wù)）；標(biāo)準(zhǔn)化的總體對象（各種具體對象的全體所構(gòu)成的整體）3. 標(biāo)準(zhǔn)化活動過程：標(biāo)準(zhǔn)的制定，標(biāo)準(zhǔn)的實(shí)施，標(biāo)準(zhǔn)的更新4. 標(biāo)準(zhǔn)的分類：根據(jù)適用范圍（國際標(biāo)準(zhǔn)，國家標(biāo)準(zhǔn)，區(qū)域標(biāo)準(zhǔn)，行業(yè)標(biāo)準(zhǔn)，企業(yè)標(biāo)準(zhǔn)，項(xiàng)目規(guī)范）；根據(jù)標(biāo)準(zhǔn)的性質(zhì)（技術(shù)標(biāo)準(zhǔn)，管理標(biāo)準(zhǔn)，工作標(biāo)準(zhǔn)）；根據(jù)標(biāo)準(zhǔn)化的對象和作用（基礎(chǔ)標(biāo)準(zhǔn)，產(chǎn)品標(biāo)準(zhǔn)，方法標(biāo)準(zhǔn)，安全標(biāo)準(zhǔn)，衛(wèi)生標(biāo)準(zhǔn)，環(huán)境保護(hù)標(biāo)準(zhǔn)，服務(wù)標(biāo)準(zhǔn)）；根據(jù)法律的約束性（強(qiáng)制性標(biāo)準(zhǔn)，推薦性標(biāo)準(zhǔn)）5. 信息技術(shù)標(biāo)準(zhǔn)化：信息編碼標(biāo)準(zhǔn)化（如 ASCII