【正文】 成：明文空間（明文的集合）、密文空間（密文集合）、加密密鑰空間、解密密鑰空間、加密和解密算法集單鑰加密體制分為兩類：流密碼（明文逐位加密）和分組密碼（明文分組，逐組加密）。密鑰的分配和存儲(chǔ)是最關(guān)鍵和困難的問題。（2）信息認(rèn)證有關(guān)認(rèn)證的實(shí)用技術(shù)中，主要的有數(shù)字簽名技術(shù)、身份識(shí)別技術(shù)和信息的完整性校驗(yàn)技術(shù)（消息認(rèn)證）（3）惡意軟件：特洛依木馬、登錄陷阱（網(wǎng)絡(luò)釣魚，虛假頁面）、邏輯炸彈（在程序中設(shè)置的破環(huán)代碼）后門陷阱（在程序中設(shè)置的繞開登錄進(jìn)入系統(tǒng)）、緩沖區(qū)溢出、僵尸網(wǎng)絡(luò)：一對(duì)多進(jìn)行控制網(wǎng)絡(luò)防病毒軟件：允許用戶設(shè)置3中掃描方式： 實(shí)時(shí)掃描、預(yù)置掃描、人工掃描（4）網(wǎng)絡(luò)安全 網(wǎng)絡(luò)安全服務(wù)的主要內(nèi)容：安全攻擊、安全機(jī)制、安全服務(wù)網(wǎng)絡(luò)服務(wù)攻擊分類： 服務(wù)攻擊和非服務(wù)攻擊服務(wù)攻擊：對(duì)服務(wù)器發(fā)起攻擊，喪失服務(wù)能力，比如對(duì)WWW服務(wù)器攻擊，主頁被篡改。拒絕服務(wù)DoS或DdoS分布式拒絕服務(wù)。 非服務(wù)攻擊：對(duì)通信設(shè)備攻擊，使設(shè)備癱瘓網(wǎng)絡(luò)信息攻擊： 攻擊類型：截獲、竊聽、篡改和偽造等1操作系統(tǒng)安全操作系統(tǒng)的安全措施一般可以從隔離、分層和內(nèi)控3個(gè)方面來進(jìn)行考慮。隔離可分為：（注意后面的解釋）①物理隔離：使不同安全要求的進(jìn)程使用不同物理實(shí)體。②時(shí)間隔離：使不同進(jìn)程在不同時(shí)間運(yùn)行。③邏輯隔離：限制程序存取。④密碼隔離：進(jìn)程以其他進(jìn)程不知的方式隱蔽數(shù)據(jù)和計(jì)算。操作系統(tǒng)安全措施：訪問控制、存儲(chǔ)保護(hù)及文件保護(hù)與保密。訪問控制：認(rèn)證、訪問權(quán)限、文件保護(hù)、審計(jì)。存儲(chǔ)保護(hù)：防止地址越界、防止操作越權(quán)。第二章 數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)：數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算主要的數(shù)據(jù)存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)（邏輯和物理相鄰，存儲(chǔ)密度大）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)計(jì)算公式 Li＝L0＋(i－1)K 順序結(jié)構(gòu)可以進(jìn)行隨機(jī)存??；插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)的大量移動(dòng) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：a、指針域可以有多個(gè)，可以指向空，比比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 b、邏輯上相鄰的節(jié)點(diǎn)物理上不一定相鄰。 c、插人、刪除等不需要大量移動(dòng)節(jié)點(diǎn)順序表：一般情況下，若長度為n的順序表，在任何位置插入或刪除的概率相等，元素移動(dòng)的平均次數(shù)為n/2（插入）和（n1）/2（刪除）。鏈表：線性鏈表（單鏈表和雙向鏈表等等）和非線性鏈表線性鏈表也稱為單鏈表，其每個(gè)一節(jié)點(diǎn)中只包含一個(gè)指針域，雙鏈表中，每個(gè)節(jié)點(diǎn)中設(shè)置有兩個(gè)指針域。（注意結(jié)點(diǎn)的插入和刪除操作）棧：“后進(jìn)先出”(LIFO)表。棧的應(yīng)用：表達(dá)式求解、二叉樹對(duì)稱序周游、快速排序算法、遞歸過程的實(shí)現(xiàn)等隊(duì)列：“先進(jìn)先出”線性表。應(yīng)用：樹的層次遍歷串：由零個(gè)或多個(gè)字符組成的有限序列。多維數(shù)組的順序存儲(chǔ)：稀疏矩陣的存儲(chǔ)：下三角矩陣順序存儲(chǔ)其他常見的存儲(chǔ)方法還有三元組法和十字鏈表法1廣義表：由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表1樹型結(jié)構(gòu)：非線性結(jié)構(gòu)。常用的樹型結(jié)構(gòu)有樹和二叉樹。二叉樹與樹的區(qū)別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區(qū)別是：二叉樹的節(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使在節(jié)點(diǎn)只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。1樹（森林）與二叉樹之間的轉(zhuǎn)換（要會(huì)轉(zhuǎn)換）1二叉樹和樹的周游（遍歷） 二叉樹的周游主要有以下3種方式：前序法(NLR)、對(duì)稱序法(LNR)、后序法(LRN) 周游樹和樹林：深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。深度優(yōu)先方式又可分為按先根次序和按后根次序周游 樹與二叉樹周游之間的對(duì)應(yīng)關(guān)系：按先根次序周游樹正好與按前序法周游樹對(duì)應(yīng)的二叉樹等同，后根次序周游樹正好與按對(duì)稱序法周游對(duì)應(yīng)的二叉樹等同 按廣度優(yōu)先方式就是層次次序周游1二叉樹的存儲(chǔ)和線索 二叉樹的存儲(chǔ)結(jié)構(gòu)：二叉樹的llink一rlink法存儲(chǔ)表示 線索二叉樹：在有n個(gè)節(jié)點(diǎn)的二叉樹的且llink rlink法存儲(chǔ)表示中，必定有n+1個(gè)空指針域1哈夫曼樹：一類帶權(quán)路徑長度最短的樹。樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和WPL。1查找：（1）順序查找：平均查找長度為(n +1 )/2次，時(shí)間復(fù)雜度為O(n)（2）二分法查找：線性表節(jié)點(diǎn)必須按關(guān)鍵碼值排序，且線性表是以順序存儲(chǔ)方式存儲(chǔ)的。查找成功比較次數(shù)log2n，查找失敗比較次數(shù)log2n+1（3）分塊查找：先是塊間查找，然后塊內(nèi)查找。（4）散列表（哈希表Hash）的存儲(chǔ)和查找：處理沖突的方法：開地址法（線性探測(cè)法）、拉鏈法等負(fù)載因子(裝填因子)=表實(shí)際存儲(chǔ)的結(jié)點(diǎn)個(gè)數(shù)/表的最大能存儲(chǔ)結(jié)點(diǎn)個(gè)數(shù)（即表長）二叉排序樹：每個(gè)結(jié)點(diǎn)左子樹的所有關(guān)鍵碼值都小于該結(jié)點(diǎn)關(guān)鍵碼值，右子樹所有結(jié)點(diǎn)關(guān)鍵碼值都大于該結(jié)點(diǎn)關(guān)鍵碼值。對(duì)稱周游二叉排序樹，得到一個(gè)有序序列，時(shí)間復(fù)雜度O（log2n）B樹和B+樹：M階樹，每個(gè)結(jié)點(diǎn)至多有M1個(gè)關(guān)鍵碼，至少有M/2(取上界)1個(gè)關(guān)鍵碼。B樹適合隨機(jī)查找，不適合順序查找。B+樹適合順序查找。1排序 直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法要了解。直接選擇排序、希爾排序、快速排序和堆排序是不穩(wěn)定排序，其他排序?yàn)榉€(wěn)定排序第三章 操作系統(tǒng)操作系統(tǒng)概念：一是管理系統(tǒng)中的各種資源；二是給用戶提供一個(gè)友好的界面。操作系統(tǒng)包括以下3個(gè)基本特征：并發(fā)性、共享性、隨機(jī)性。功能：進(jìn)程管理、存儲(chǔ)管理、作業(yè)管理、文件管理、設(shè)備管理操作系統(tǒng)類型（1）批處理操作系統(tǒng)：成批、多道，交互性不強(qiáng)。系統(tǒng)目標(biāo)：提高資源利用率、作業(yè)吞吐量和作業(yè)流程自動(dòng)化。（2）分時(shí)操作系統(tǒng)：多路、交互性、獨(dú)立性、及時(shí)性（3）實(shí)時(shí)系統(tǒng)（實(shí)時(shí)控制、實(shí)時(shí)信息處理）：及時(shí)、可靠（4）嵌入式操作系統(tǒng)：高可靠性、實(shí)時(shí)性、占資源少、智能化、易連接、低成本等。操作系統(tǒng)與用戶的接口：程序級(jí)接口：系統(tǒng)調(diào)用命令組成。操作級(jí)接口：提供操作命令操作系統(tǒng)的硬件環(huán)境（CPU、存儲(chǔ)體系、中斷系統(tǒng)、I/O控制和時(shí)鐘）（1）CPU：CPU狀態(tài)：管態(tài)（CPU執(zhí)行操作系統(tǒng)程序）和目態(tài)（CPU執(zhí)行用戶程序） 目態(tài)到管態(tài)的轉(zhuǎn)變的唯一途徑是中斷，通過修改程序狀態(tài)字實(shí)現(xiàn)管態(tài)和目態(tài)的轉(zhuǎn)換（2）中斷機(jī)制：中斷的實(shí)現(xiàn)需要硬件和軟件結(jié)合完成。中斷類型：強(qiáng)迫性中斷和自愿性中斷。強(qiáng)迫性中斷：：輸入輸出中斷、硬件故障中斷、時(shí)鐘中斷、程序性中斷。自愿性中斷：程序有意安排的訪管指令或系統(tǒng)調(diào)用。中斷向量：中斷處理程序的入口地址及運(yùn)行環(huán)境（程序狀態(tài)字PSW）中斷優(yōu)先級(jí)由硬件規(guī)定，中斷屏蔽由程序狀態(tài)字的中斷屏蔽位決定。通過中斷屏蔽可以調(diào)整中斷事件的響應(yīng)次序 （3）定時(shí)裝置：定時(shí)裝置硬件時(shí)鐘通常分為兩類：即絕對(duì)時(shí)鐘和相對(duì)時(shí)鐘。 CPU對(duì)外部設(shè)備的控制方式：循環(huán)測(cè)試I/O 中斷 DMA（直接內(nèi)存存?。焊咚偻庠O(shè)與內(nèi)存批量處理數(shù)據(jù) 通道處理（I/O處理機(jī)）進(jìn)程管理（1）進(jìn)程與程序的區(qū)別與聯(lián)系：，是動(dòng)態(tài)的；而程序是指令的集合，是靜態(tài)的。 ，即進(jìn)程的存在是有限的，從運(yùn)行到結(jié)束，是暫時(shí)的；而程序則是永久存在的。 、數(shù)據(jù)和進(jìn)程控制塊(PCB)。 ，一個(gè)進(jìn)程也可以包含多個(gè)程序。進(jìn)程控制塊PCB是一個(gè)數(shù)據(jù)結(jié)構(gòu)，進(jìn)程在內(nèi)存中存在的唯一標(biāo)志(2)進(jìn)程狀態(tài): 運(yùn)行態(tài), 就緒態(tài),等待狀態(tài)（阻塞狀態(tài)）(3)線程：CPU調(diào)度和分派的基本單位。共享進(jìn)程資源。（4）進(jìn)程的通信 臨界資源是指一次只允許一個(gè)進(jìn)程使用的資源：一個(gè)進(jìn)程中訪問臨界資源的那段程序代碼稱為臨界區(qū)。它們不允許兩個(gè)及以上的進(jìn)程同時(shí)訪問或修改。 進(jìn)程同步：多個(gè)進(jìn)程協(xié)同完成任務(wù)。進(jìn)程互斥：多個(gè)進(jìn)程使用同一資源（臨界資源)。 低級(jí)通信：少量信息的交換(P操作和V操作) 高級(jí)通信：大信息交換（消息機(jī)制（消息緩沖、信箱通信）、共享內(nèi)存，管道） 進(jìn)程（線程）調(diào)度：先來先服務(wù)、時(shí)間片輪轉(zhuǎn)、最高優(yōu)先級(jí)（緊迫度高的進(jìn)程）、 多級(jí)隊(duì)列反饋算法：綜合了FCFS、時(shí)間片輪轉(zhuǎn)和可搶占最高優(yōu)先數(shù)算法。（5）死鎖：產(chǎn)生死鎖的必要條件：互斥條件、不可剝奪條件、部分分配、循環(huán)等待 死鎖的預(yù)防： 破環(huán)必要條件之一：靜態(tài)預(yù)分配（破壞部分分配）、資源有序分配（破壞環(huán)路等待）、 可剝奪資源（破壞不可剝奪性）死鎖的避免：銀行家算法死鎖的檢測(cè)：進(jìn)程等待時(shí)檢測(cè)、定時(shí)檢測(cè)、系統(tǒng)利用率降低時(shí)檢測(cè)死鎖的解除：資源剝奪和撤銷進(jìn)程存儲(chǔ)管理（1）功能：內(nèi)存的分配和回收、內(nèi)存共享、存儲(chǔ)保護(hù)（防止地址越界和操作越權(quán)）、地址映射（地址重定位）內(nèi)存擴(kuò)充：讓外存當(dāng)作內(nèi)存來使用（2）碎片管理：解決碎片的方法是移動(dòng)技術(shù)或緊湊(拼接)技術(shù)（3）靜態(tài)地址重定位：程序裝入內(nèi)存時(shí)，進(jìn)行邏輯地址轉(zhuǎn)換物理地址轉(zhuǎn)換動(dòng)態(tài)地址重地位：程序運(yùn)行過程中，要訪問指令和數(shù)據(jù)才進(jìn)行地址轉(zhuǎn)換，需要硬件地址映射機(jī)制（基址寄存器和限長寄存器）（4）空閑分區(qū)的分配策略：最先適應(yīng)算法（地址從小到大找第一個(gè)滿足進(jìn)程空間大小的分區(qū)） 最佳適應(yīng)算法：分區(qū)表按容量從小到排序；最壞適應(yīng)算法：分區(qū)按容量從大到小排序。（5）虛擬存儲(chǔ)管理：虛擬存儲(chǔ)得以實(shí)現(xiàn)是由程序的局部性原理來決定的。程序的局部性原理包括時(shí)間局部性和空間局部 （6）頁面淘汰算法包括以下幾種：最佳淘汰算法(OPT)、先進(jìn)先出淘汰算法(FIFO)、最近最久末使用淘汰算法(LRU)最近使用最少淘汰算法(LFU)（訪問次數(shù)少） （7）影響缺頁中斷次數(shù)因素：a、分配給進(jìn)程的物理頁面數(shù) c、頁面淘汰算法：最佳淘汰算法(OPT)能使缺頁中斷率最低(8)顛簸（抖動(dòng)）：缺頁率高引起。工作集模型解決顛簸(抖動(dòng)）文件管理（1）邏輯結(jié)構(gòu)：流式文件（基本單位字符）（如：源程序文件、目標(biāo)代碼文件，Unix的文件）和記錄文件（定長和不定長記錄），記錄包含一個(gè)記錄鍵和其他屬性（2）文件的物理結(jié)構(gòu)：連續(xù)結(jié)鉤、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)及Hash結(jié)構(gòu)等，文件的存取方式與物理結(jié)構(gòu)有關(guān)。UNIX三級(jí)索引表的計(jì)算：如果一個(gè)物理塊可以存放256個(gè)塊號(hào)，則三級(jí)索引表表示文件的大小 2563+2562+256+10（3）文件目錄：文件系統(tǒng)的最大特點(diǎn)就是“按名”存取（4）文件控制塊FCB是文件在內(nèi)存中存在的唯一標(biāo)志，文件目錄是文件控制塊的有序集合。（5）多級(jí)目錄結(jié)構(gòu)，有利于避免文件重名；當(dāng)前目錄：可以提高檢索速度。目錄項(xiàng)分解法，它可以提高文件檢索速度（6）記錄的成組：若干個(gè)邏輯記錄合成在一個(gè)物理塊中，每個(gè)塊中的邏輯記錄個(gè)數(shù)為塊因子。 設(shè)備管理 （1）按設(shè)備的工作特性可以分為存儲(chǔ)設(shè)備和輸人／輸出設(shè)備兩種 （2）按照資源分配方式可以分為獨(dú)享設(shè)備、共享設(shè)備和虛擬設(shè)備3種 虛設(shè)備技術(shù)，一類設(shè)備模擬另一類設(shè)備的技術(shù)。在高速設(shè)備（如高速大容量磁盤）上模擬低速設(shè)備 ：SPOOLING是典型的虛設(shè)備技術(shù)，被模擬的設(shè)備稱為虛擬設(shè)備。 （3）按設(shè)備的數(shù)據(jù)組織分類：塊設(shè)備（磁盤、磁帶）和字符設(shè)備（打印機(jī)）。 （4）通道可以分為以下3種類型：字節(jié)多路通道、選擇通道和成組多路通道。 （5）單緩沖區(qū)，雙緩沖區(qū)，多緩沖區(qū)和緩沖池：解決外設(shè)與CPU速度不匹配問題 （6）磁盤調(diào)度： 訪問磁盤時(shí)間：尋道時(shí)間、旋轉(zhuǎn)定位時(shí)間和數(shù)據(jù)傳輸時(shí)間。 磁盤調(diào)度由移臂調(diào)度和旋轉(zhuǎn)調(diào)度組成。移臂調(diào)度：先來先服務(wù)FCFS（大幅度移動(dòng))、最短尋道時(shí)間優(yōu)先(饑餓，考慮了尋道優(yōu)化），掃描算法（考慮方向和距離，考慮了尋道優(yōu)化） 旋轉(zhuǎn)調(diào)度：目的較少旋轉(zhuǎn)延遲時(shí)間。第四章 數(shù)據(jù)庫系統(tǒng)技術(shù)基礎(chǔ)信息與數(shù)據(jù)的關(guān)系：數(shù)據(jù)是信息的符號(hào)表示，或稱載體；信息是數(shù)據(jù)的內(nèi)涵，是數(shù)據(jù)的語義解釋數(shù)據(jù)庫系統(tǒng)：一般由數(shù)據(jù)庫、操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)(及其工具)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理人員和用戶構(gòu)成。數(shù)據(jù)模型: 數(shù)據(jù)模型是數(shù)據(jù)庫系統(tǒng)的數(shù)學(xué)形式框架，是數(shù)據(jù)庫系統(tǒng)的核心和基礎(chǔ).數(shù)據(jù)模型的分類：概念模型，也稱信息模型；邏輯模型，主要包括網(wǎng)狀模型、層次模型和關(guān)系模型等；物理模型 。數(shù)據(jù)模型的三要素：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和完整性約束。概念模型，信息世界建模，ER模型是常用的概念模型。EER擴(kuò)充ER模型，面向?qū)ο竽Ｐ?、謂詞模型。ER圖提供了表示實(shí)體型、屬性和聯(lián)系的方法。 (1)實(shí)體型：用矩形表示，矩形框內(nèi)寫明實(shí)體名。 (2)屬性：用橢圓形表示，并用無向邊將其與相應(yīng)的實(shí)體連接起來。 (3)聯(lián)系：用菱形表示，菱形框內(nèi)寫明聯(lián)系名，并用無向邊分別與有關(guān)實(shí)體連接起來，同時(shí)在無向邊旁標(biāo)上聯(lián)系的類型邏輯模型，面向數(shù)據(jù)庫管理系統(tǒng)。傳統(tǒng)邏輯模型（層次、網(wǎng)狀、關(guān)系）基于記錄的模型。層次、網(wǎng)狀模型用記錄和鏈接表示數(shù)據(jù)和聯(lián)系，關(guān)系模型用二維表表示數(shù)據(jù)，記錄值表示表間聯(lián)系。面向?qū)ο蟮哪Ｐ?，?duì)象關(guān)系模型都屬于邏輯模型，面向?qū)ο竽Ｐ图仁歉拍钅Ｐ陀质沁壿嬆Ｐ?。?shù)據(jù)庫系統(tǒng)的三級(jí)模式結(jié)構(gòu)：由外模式、模式和內(nèi)模式三級(jí)構(gòu)成的。模式(Schema)：一個(gè)數(shù)據(jù)庫只有一個(gè)模式；外模式也稱子模式或用戶模式，一個(gè)數(shù)據(jù)庫可以有多個(gè)外模式。外模式是保證數(shù)據(jù)庫安全性的一個(gè)有力措施。內(nèi)模式也稱存儲(chǔ)模式或物理模式，一個(gè)數(shù)據(jù)庫只有一個(gè)內(nèi)模式。10. 數(shù)據(jù)庫的二層映像與數(shù)據(jù)獨(dú)立性：外模式／模式映像，包含在各自的外模式描述中。外模式／模式映像保證了數(shù)據(jù)與程序的邏輯獨(dú)立性（模式變，外模式不變）；模式／內(nèi)模式映像，包含在模式描述中，模式／內(nèi)模式映像保證了數(shù)據(jù)與程序的物理獨(dú)立性（物理模式變，模式不變，外模式不變）。第五章 關(guān)系數(shù)據(jù)庫系統(tǒng)關(guān)系模型由關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合和關(guān)系完整性約束3部分組成。關(guān)系模型中的關(guān)系操作的理論依據(jù)為關(guān)系代數(shù)和關(guān)系演算。關(guān)系操作的特點(diǎn)是集合操作方式。關(guān)系數(shù)據(jù)語言可以分為如下3類：關(guān)系代數(shù)語言、關(guān)系演算語言(包括元組關(guān)系演算語言和域關(guān)系演算語言)及具有關(guān)系代數(shù)和關(guān)系演算雙重特點(diǎn)的SQL語言。關(guān)系模型中有3類完整性約束：實(shí)體完整性、參照完整性（引用完整性）和域完整性約束（用戶自定義的完整性）關(guān)系數(shù)據(jù)庫對(duì)關(guān)系的限定 當(dāng)關(guān)系作為關(guān)系數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)時(shí)，關(guān)系數(shù)據(jù)庫對(duì)關(guān)系有如下的限制。 (1)列是同質(zhì)的．即每一列中的分量是同一類型的數(shù)據(jù)，來自同一個(gè)域。 (2)不同的列可以出自同一個(gè)域，稱其中的每一列為一個(gè)屬性，不同的屬性要給予不同的屬性名。