【正文】 數(shù)的反碼與原碼相同，負(fù)數(shù)反碼為原碼按位取反（符號(hào)位不變）。c) 移碼（增碼）：將補(bǔ)碼的符號(hào)位求反。b) 海明校驗(yàn)碼：i. 根據(jù)信息位數(shù)，確定校驗(yàn)位數(shù)，2r≥k+r+1。第二章 數(shù)據(jù)結(jié)構(gòu)與算法1. 數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)元素的組織形式。b) 查找表中第i個(gè)元素 LOC(ai) = LOC(a1)+(i1)*L3. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：a) 用一組任意的存儲(chǔ)單元來(lái)存放線性表的數(shù)據(jù)元素，鏈表中的結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。（先進(jìn)先出）7. 子串包含在它的主串中的位置是子串的第一個(gè)字符首次出現(xiàn)的位置。b) 深度為K的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)（k≥1）。d) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（向下取整）。如：11. 樹(shù)的前序遍歷與二叉樹(shù)的先序遍歷一樣；樹(shù)的后序與二叉樹(shù)的中序遍歷一樣。13. 二分查找（折半查找）：要求關(guān)鍵字必須采用順序存儲(chǔ)結(jié)構(gòu)，并且必須按關(guān)鍵字的大小有序排序。b) 若查找樹(shù)的左子樹(shù)非空，則其左子樹(shù)上各節(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。d) 平衡二叉樹(shù)：或者是空樹(shù)，或者是滿(mǎn)足：樹(shù)中任一節(jié)點(diǎn)左右子樹(shù)的深度相差不超過(guò)1。15. 有向圖中所有頂點(diǎn)的出度數(shù)之和等于入度數(shù)之和。18. C語(yǔ)言中，struct中各成員都占有自己的內(nèi)存空間，總長(zhǎng)度為所有成員的長(zhǎng)度之和，而union中的長(zhǎng)度等于最長(zhǎng)的成員的長(zhǎng)度。c) 實(shí)時(shí)系統(tǒng)——高可靠性d) 網(wǎng)絡(luò)操作系統(tǒng)e) 分布式操作系統(tǒng)f) 微機(jī)操作系統(tǒng)g) 嵌入式操作系統(tǒng)2. 利用PV操作實(shí)現(xiàn)進(jìn)程的互斥和同步。5. 中斷響應(yīng)時(shí)間＝關(guān)中斷的最長(zhǎng)時(shí)間 ＋保護(hù)CPU內(nèi)部寄存器的時(shí)間 ＋進(jìn)入中斷服務(wù)函數(shù)的執(zhí)行時(shí)間 ＋開(kāi)始執(zhí)行中斷服務(wù)例程(ISR)的第一條指令時(shí)間。7. 高速緩存的組成：Cache由兩個(gè)部分組成：控制部分和Cache存儲(chǔ)器部分。有三種方式：a) 直接映像：它把主存空間按Cache大小等分成區(qū)，每區(qū)內(nèi)的各塊只能按位置一一對(duì)應(yīng)到Cache的相應(yīng)塊位置上。主存地址：塊號(hào)B+塊內(nèi)地址WCache地址：塊號(hào)b +塊內(nèi)地址w 對(duì)應(yīng)關(guān)系：塊號(hào)B通過(guò)地址變換表對(duì)應(yīng)于塊號(hào)b ， 塊內(nèi)地址W = 塊內(nèi)地址 wc) 組相聯(lián)映像：是直接映像和全相聯(lián)映像的折中方案。主存地址：區(qū)號(hào)E+組號(hào)G+組內(nèi)塊號(hào)B+塊內(nèi)地址WCache地址：組號(hào)g + 組內(nèi)塊號(hào)b + 塊內(nèi)地址w組間是直接映射關(guān)系，組內(nèi)是全相連映射關(guān)系對(duì)應(yīng)關(guān)系：組號(hào)G=組號(hào)g，組內(nèi)塊號(hào)B通過(guò)地址變換表對(duì)應(yīng)于組內(nèi)塊號(hào)b ， 塊內(nèi)地址W = 塊內(nèi)地址 w9. Cache存儲(chǔ)器：a) 命中率：t3＝μt1﹢﹙1－μ﹚t2。b) 使用Cache后提高的倍數(shù)： r = t2/t3。常用算法如下：a) 隨機(jī)替換算法。就是將最先進(jìn)入Cache的信息塊替換出去。這種方法是將近期最少使用的Cache中的信息塊替換出去。但此法也不能保證過(guò)去不常用將來(lái)也不常用。使用這種方法時(shí)必須先執(zhí)行一次程序，統(tǒng)計(jì)Cache的替換情況。時(shí)間局部性是指最近被訪問(wèn)的存儲(chǔ)單元可能馬上又要被訪問(wèn)。b) 根據(jù)程序的局部性理論，Denning提出了工作集理論：在進(jìn)程運(yùn)行時(shí)，如果能保證它的工作集頁(yè)面都在主存儲(chǔ)器內(nèi)，就會(huì)大大減少進(jìn)程的缺頁(yè)次數(shù)，使進(jìn)程高效地運(yùn)行；否則將會(huì)因某些工作頁(yè)面不在內(nèi)存而出現(xiàn)頻繁的頁(yè)面調(diào)入/調(diào)出現(xiàn)象，造成系統(tǒng)性能急劇下降，嚴(yán)重時(shí)會(huì)出現(xiàn)“抖動(dòng)”現(xiàn)象。14. 前趨圖是一個(gè)有向無(wú)循環(huán)圖。a) 臨界資源：諸進(jìn)程間需要互斥方式對(duì)其進(jìn)行共享的資源，如打印機(jī)。c) s:信號(hào)量；P操作：使S = S1，若S0，進(jìn)程暫停執(zhí)行，放入信號(hào)量的等待隊(duì)列；V操作：使s = s+1，若s≤0，喚醒等待隊(duì)列中的一個(gè)進(jìn)程。16. 進(jìn)程通信（間接通信）a) 發(fā)送信件:如果指定信箱未滿(mǎn),則將信件送入信箱中由指針?biāo)甘镜奈恢?并釋放等待該信箱中信件的等待者。b) 接收信件:如果指定信箱中有信,則取出一封信件,并釋放等待信箱的等待者,否則接收信件者被置成等待信箱中信件的狀態(tài)進(jìn)程通信。物理地址 = 塊號(hào)+頁(yè)內(nèi)地址。即：P=INT[A/L]。頁(yè)面大小為L(zhǎng)頁(yè)號(hào)P，頁(yè)內(nèi)地址d?；穼?duì)應(yīng)內(nèi)存地址。c) 段頁(yè)式存儲(chǔ)管理方式：邏輯地址分為 段號(hào)（s）+段內(nèi)頁(yè)號(hào)（P）+頁(yè)內(nèi)地址（w）。物理地址 = 塊號(hào)+頁(yè)內(nèi)地址。那么物理地址 = (基號(hào)+段號(hào)+頁(yè)號(hào))*2n+頁(yè)內(nèi)地址。18. 文件系統(tǒng)的主要功能是：實(shí)現(xiàn)對(duì)文件的按名存取，使用打開(kāi)文件（open）將文件的控制信息從輔存讀到內(nèi)存。20. Spooling技術(shù)是用一類(lèi)物理設(shè)備模擬另一類(lèi)物理設(shè)備的技術(shù),實(shí)現(xiàn)這種技術(shù)的功能模塊稱(chēng)做斯普林系統(tǒng)。b) 將獨(dú)占設(shè)備改造成共享設(shè)備。21.第四章 程序設(shè)計(jì)基礎(chǔ)1. 程序設(shè)計(jì)語(yǔ)言的種類(lèi)：a) 命令式程序設(shè)計(jì)語(yǔ)言：基于動(dòng)作的語(yǔ)言，如fortran、pascal和c。c) 函數(shù)式程序設(shè)計(jì)語(yǔ)言：主要用于符號(hào)數(shù)據(jù)處理，如積分演算、數(shù)理邏輯、游戲推演和人工智能等領(lǐng)域。2. 程序語(yǔ)言的基本成分：a) 數(shù)據(jù)成分：常量和變量、全局量和局部量、數(shù)據(jù)類(lèi)型。d) 函數(shù)：函數(shù)定義、函數(shù)聲明、函數(shù)調(diào)用。c) 支持動(dòng)態(tài)性；d) 支持繼承——與其它語(yǔ)言的主要區(qū)別。4. C語(yǔ)言的特點(diǎn)是過(guò)程式程序設(shè)計(jì)屬于靜態(tài)語(yǔ)言所有成分可在編譯時(shí)確定。6. 編寫(xiě)程序時(shí)的錯(cuò)誤有：a) 動(dòng)態(tài)錯(cuò)誤：指源程序中的邏輯錯(cuò)誤，發(fā)生在程序運(yùn)行時(shí)錯(cuò)誤，如除數(shù)為0數(shù)組下標(biāo)出界。第五章 網(wǎng)絡(luò)基礎(chǔ)知識(shí)1. TCP是第四層（傳輸層）的傳輸控制協(xié)議；IPSec是第三層（網(wǎng)絡(luò)層）的VPN協(xié)議；PPOE工作于第二層（數(shù)據(jù)鏈路層）；SSL是工作于TCP協(xié)議之上的安全協(xié)議。b) 數(shù)據(jù)連接：文件的傳輸，主動(dòng)模式由服務(wù)器端主動(dòng)連接，被動(dòng)模式服務(wù)器等待客戶(hù)端來(lái)連接?？沟仲?lài)性防止參與此交易的一方否認(rèn)曾經(jīng)發(fā)生過(guò)此次交易5. 網(wǎng)絡(luò)安全技術(shù)：信息存取的保障有用戶(hù)的標(biāo)識(shí)和驗(yàn)證、用戶(hù)存取權(quán)限控制、系統(tǒng)安全監(jiān)控、計(jì)算機(jī)病毒的防治、數(shù)據(jù)加密。b) 防火墻技術(shù)：類(lèi)型有i. 包過(guò)濾防火墻（屏蔽路由器）：將路由器放置于內(nèi)部網(wǎng)絡(luò)中，網(wǎng)絡(luò)層安全。iii. 狀態(tài)檢測(cè)技術(shù)防火墻：以上兩種技術(shù)的綜合，屏蔽路由器置于外部網(wǎng)絡(luò)，雙宿主機(jī)置于內(nèi)部網(wǎng)絡(luò)。6. 多模光纖的特點(diǎn)是：成本低、寬芯線、聚光好、耗散大、低效，用于低速短距離的通信。7. ping命令：判斷用戶(hù)與外部站點(diǎn)的連通性，一、（本地循環(huán)地址），無(wú)法ping則說(shuō)明本機(jī)TCP/IP協(xié)議不能正常工作，二、ping+本機(jī)IP不通則說(shuō)明網(wǎng)絡(luò)適配器（網(wǎng)卡/MODEM）出現(xiàn)故障，三、ping+同一網(wǎng)段計(jì)算機(jī)的IP不通則說(shuō)明網(wǎng)絡(luò)線路出現(xiàn)故障；netstat命令：用于顯示TCP、UDP、IP、ICMP協(xié)議相關(guān)統(tǒng)計(jì)數(shù)據(jù)，一般用于檢驗(yàn)本機(jī)網(wǎng)絡(luò)端口的連接情況；ARP命令：可以查看和修改本地計(jì)算機(jī)的ARP表項(xiàng)，和查看ARP緩存和解決地址解析問(wèn)題非常使用。8. DHCP（動(dòng)態(tài)主機(jī)配置協(xié)議）：用于網(wǎng)絡(luò)中的主機(jī)動(dòng)態(tài)分配IP地址，默認(rèn)情況下客戶(hù)機(jī)采用最先達(dá)到的DHCP服務(wù)器分配的IP地址。ARP將IP地址轉(zhuǎn)換為物理地址（MAC地址）。第六章 多媒體基礎(chǔ)知識(shí) 1. 衡量聲音特性的屬性（三要素）：a) 音量：也叫音強(qiáng)，衡量聲音的強(qiáng)弱程度。c) 音色： 由混入基音的泛音決定。a) 人耳能聽(tīng)到(其它聲音)的音頻范圍：20HZ~20KHZb) 人的說(shuō)話聲音音頻范圍：300~3400HZc) 樂(lè)器的音頻范圍：20HZ~20KHZ3. 聲音信號(hào)的數(shù)字化：——取樣量化法a) 采樣：信號(hào)測(cè)量記錄。b) 數(shù)字信號(hào)是離散的，模擬信號(hào)是連續(xù)的。5. 色彩的三要素：a) 亮度：明亮程度的感覺(jué)。c) 飽和度：顏色的純度，即摻入白光的程度，顏色的鮮明程度。紅黃綠b) CMY彩色空間：打印。7. 圖像文件的大小計(jì)算：a) 已知像素和位數(shù)：容量=像素*位數(shù)/8Bb) 已知像素和色數(shù)：容量=像素*位數(shù)/8B（2位數(shù)=色數(shù)即n位數(shù)能表示2位數(shù)種顏色）8. 音頻文件的大小計(jì)算：a) 未經(jīng)過(guò)壓縮的 ：數(shù)據(jù)傳輸率（b/s）=采樣頻率（Hz）*量化位數(shù)（采樣位數(shù)）（b）*聲道數(shù)（如果求的是字節(jié)則應(yīng)再除以8）b) 經(jīng)過(guò)數(shù)字化后所需的存儲(chǔ)空間（容量）：聲音信號(hào)數(shù)據(jù)量=數(shù)據(jù)傳輸率（b/s）*持續(xù)時(shí)間/8（B）9. 視頻文件的大小計(jì)算：a) 存儲(chǔ)容量的（字節(jié)數(shù)）=每幀圖像的容量（B）*每秒幀數(shù)*時(shí)間注：每幀圖像的容量（B）與圖像文件容量計(jì)算方式一樣。數(shù)字電視標(biāo)準(zhǔn)。DVD，數(shù)字電視標(biāo)準(zhǔn)。多媒體應(yīng)用的標(biāo)準(zhǔn)。e) MPEG21: “多媒體框架”或“數(shù)字視聽(tīng)框架”，它以將標(biāo)準(zhǔn)集成起來(lái)支持協(xié)調(diào)的技術(shù)以管理多媒體商務(wù)為目標(biāo)，目的就是理解如何將不同的技術(shù)和標(biāo)準(zhǔn)結(jié)合在一起需要什么新的標(biāo)準(zhǔn)以及完成不同標(biāo)準(zhǔn)的結(jié)合工作。11. 圖像文件格式g) 靜態(tài)格式：GIF/BMP/TIF/PCX/JPG/PSDh) 動(dòng)態(tài)格式：AVI/MPG/AVSi) 目前圖像使用的編碼和壓縮標(biāo)準(zhǔn)：JPEG/MPEG/。聲音文件是通過(guò)聲音錄入設(shè)備錄制的原始聲音；MIDI是一種音樂(lè)演奏指令序列，相當(dāng)于樂(lè)譜，由電子樂(lè)器進(jìn)行演奏，不包含聲音數(shù)據(jù)，文件較小。b) 視頻圖像壓縮技術(shù)基本思想和方法：在空間上，圖像數(shù)據(jù)壓縮采用JPEG壓縮方法來(lái)去除冗余信息，主要方法包括幀內(nèi)預(yù)測(cè)編碼和變換編碼；在時(shí)間上，圖像數(shù)據(jù)壓縮采用幀間預(yù)測(cè)編碼和運(yùn)動(dòng)補(bǔ)償算法來(lái)去除冗余信息。區(qū)別是無(wú)損壓縮可以還原。d) 熵編碼：熵編碼即編碼過(guò)程中按熵原理不丟失任何信息的編碼，常見(jiàn)的熵編碼有：LZW編碼、香農(nóng)(Shannon)編碼、哈夫曼(Huffman)編碼和算術(shù)編碼(arithmetic coding)。2. 數(shù)據(jù)庫(kù)系統(tǒng)（DBS）由數(shù)據(jù)庫(kù)、硬件、軟件和人員組成。對(duì)權(quán)限的操作有DCL語(yǔ)言。7. 實(shí)體屬性a) 簡(jiǎn)單屬性（不可再分）和復(fù)合屬性（可分如地址（省份、市…））b) 單值屬性（只有一個(gè)值）和多值屬性（如電話號(hào)碼可有多個(gè)）c) NULL屬性（沒(méi)有或是未知）d) 派生屬性（從其他屬性可推出來(lái)）8. ER法的構(gòu)件：9. 擴(kuò)充的ER模型a) 弱實(shí)體（要依賴(lài)另一個(gè)實(shí)體而存在）b) 特殊化————P37510. 數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)a) 三級(jí)模式結(jié)構(gòu)（三層兩映像）i. 數(shù)據(jù)物理獨(dú)立性ii. 數(shù)據(jù)邏輯獨(dú)立性b) 集中式數(shù)據(jù)庫(kù)系統(tǒng)：兩段提交協(xié)議：封鎖階段（擴(kuò)展階段）和解鎖階段（收縮階段）c) 客戶(hù)/服務(wù)器數(shù)據(jù)庫(kù)體系結(jié)構(gòu)d) 并行數(shù)據(jù)庫(kù)系統(tǒng)（多個(gè)CPU）————P387i. 共享內(nèi)存式多處理器ii. 無(wú)共享式并行體系結(jié)構(gòu)e) 分布式數(shù)據(jù)庫(kù)系統(tǒng)：兩段提交協(xié)議：表決階段和執(zhí)行階段f) Web數(shù)據(jù)庫(kù)11. 全碼：指關(guān)系模型中所有的屬性組是這個(gè)關(guān)系模式的候選鍵。ii. 并發(fā)控制的技術(shù)：封鎖，排他鎖（X鎖）和共享鎖（S鎖）iii. 三級(jí)封鎖協(xié)議：一級(jí)：解決丟失更新；二級(jí)：解決讀臟數(shù)據(jù)；三級(jí)：解決不可重復(fù)讀iv. 并發(fā)調(diào)度的可串行性：可串行化是并發(fā)事物正確性準(zhǔn)則，當(dāng)且僅當(dāng)可串行化時(shí)才是正確的并發(fā)調(diào)度v. 封鎖的粒度：封鎖的范圍vi. 事物是不能嵌套的，因?yàn)檫`背了事物的原子性；當(dāng)且僅當(dāng)當(dāng)前沒(méi)有事物執(zhí)行時(shí)才能開(kāi)始執(zhí)行事物。b) 部分提交狀態(tài)：全部執(zhí)行完。然后事物就進(jìn)入了中止態(tài)。e) 提交狀態(tài)：當(dāng)事物成功完成后，事物處于提交狀態(tài)，只有事物處于提交狀態(tài)，才能說(shuō)明事物已經(jīng)提交。b) 數(shù)據(jù)模式——事實(shí)表,多維數(shù)據(jù)模式包括（星型模式、雪花模式、事實(shí)星狀模式）c) 數(shù)據(jù)倉(cāng)庫(kù)體系結(jié)構(gòu)i. 通常采用：數(shù)據(jù)倉(cāng)庫(kù)服務(wù)器、OLAP（聯(lián)機(jī)分析處理）、前端服務(wù)器ii. 從結(jié)構(gòu)的角度：企業(yè)倉(cāng)庫(kù)、數(shù)據(jù)集市、虛擬倉(cāng)庫(kù)16. 數(shù)據(jù)倉(cāng)庫(kù)的設(shè)計(jì)：a) 數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)模型與操作行數(shù)據(jù)庫(kù)的區(qū)別：不包含純操作型的數(shù)據(jù)；擴(kuò)充了碼結(jié)構(gòu)，增加了時(shí)間屬性作為碼的一部分；增加了一些導(dǎo)出數(shù)據(jù)。17. 數(shù)據(jù)挖掘技術(shù)：海量數(shù)據(jù)搜集、強(qiáng)大的多處理計(jì)算機(jī)和數(shù)據(jù)挖掘算法。19. 數(shù)據(jù)挖掘的應(yīng)用過(guò)程a) 確定挖掘?qū)ο骲) 準(zhǔn)備數(shù)據(jù)（數(shù)據(jù)挖掘工作量的60%），包括數(shù)據(jù)選擇；數(shù)據(jù)預(yù)處理（清洗）；數(shù)據(jù)轉(zhuǎn)換。a) 動(dòng)態(tài)轉(zhuǎn)儲(chǔ)： 指轉(zhuǎn)儲(chǔ)期間允許對(duì)數(shù)據(jù)庫(kù)進(jìn)行存取或修改。b) 靜態(tài)轉(zhuǎn)儲(chǔ)：在系統(tǒng)中無(wú)運(yùn)行事務(wù)時(shí)進(jìn)行的轉(zhuǎn)儲(chǔ)操作。d) 海量轉(zhuǎn)儲(chǔ)：指每次轉(zhuǎn)儲(chǔ)全部數(shù)據(jù)庫(kù)。但如果數(shù)據(jù)庫(kù)很大，事務(wù)處理又十分頻繁，則增量轉(zhuǎn)儲(chǔ)方式更實(shí)用更有效。OLAP沒(méi)有嚴(yán)格的時(shí)間要求，OLTP是面向業(yè)務(wù)的，對(duì)時(shí)效要求比較高。第八章 關(guān)系數(shù)據(jù)庫(kù)1. 關(guān)系模型是關(guān)系數(shù)據(jù)庫(kù)的基礎(chǔ)，由關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合和關(guān)系完整性規(guī)則組成。3. 在關(guān)系模型中所有的域都應(yīng)該是原子數(shù)據(jù)（1NF）。6. 在關(guān)系代數(shù)中對(duì)傳統(tǒng)的的集合運(yùn)算要求參與運(yùn)算的關(guān)系具有相同的度且對(duì)應(yīng)屬性取自同一個(gè)域。9. 關(guān)系模式的設(shè)計(jì)問(wèn)題：a) 數(shù)據(jù)冗余：同一數(shù)據(jù)重復(fù)出現(xiàn)多次。c) 規(guī)范化的一個(gè)原則：“關(guān)系模式有冗余問(wèn)題，就分解它”。b) 盡可能的不出現(xiàn)插入、刪除和操作異常。d) 盡可能的使等值連接在主鍵和外鍵上進(jìn)行，并保證不會(huì)產(chǎn)生額外的元組。c) 若存在FD W→A，如果W的任一個(gè)子集X沒(méi)有X→A，則稱(chēng)W→A是完全函數(shù)依賴(lài)。d) 傳遞函數(shù)依賴(lài)：如果X→Y,Y→A,且Y不→X, A不∈Y,則X→A是傳遞函數(shù)依賴(lài)。如果X→U在R上成立，但是對(duì)于任一真子集X1都有X1→U不成立（說(shuō)明：不含多余屬性），那么X是R的一個(gè)候選鍵。g) 最小函