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