數(shù)據(jù)庫(kù)系統(tǒng)工程師考點(diǎn)知識(shí)精講

2013數(shù)據(jù)庫(kù)系統(tǒng)工程師考點(diǎn)知識(shí)精講一第一篇：計(jì)算機(jī)數(shù)據(jù)庫(kù)系統(tǒng)知識(shí)計(jì)算機(jī)系統(tǒng)由硬件系統(tǒng)和軟件系統(tǒng)組成。硬件由運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備、輸出設(shè)備5部分組成；軟件由系統(tǒng)軟件、應(yīng)用軟件組成。運(yùn)算器：對(duì)數(shù)據(jù)進(jìn)行處理的部件，主要完成算術(shù)和邏輯運(yùn)算；控制器：從主存中取出指令，并指出下一條指令在主存中的位置，取出的指令經(jīng)指令寄存器送往指令譯碼器，經(jīng)過(guò)對(duì)指令的分析發(fā)出相應(yīng)的控制和定時(shí)信息；1.控制器的組成部分為：程序計(jì)數(shù)器；指令寄存器；指令譯碼器；狀態(tài)條件寄存器；時(shí)序產(chǎn)生器；微信號(hào)發(fā)生器。計(jì)算機(jī)硬件的典型結(jié)構(gòu)：?jiǎn)慰偩€、雙總線（以cpu為中心、以存儲(chǔ)器為中心）、采用通道的大型系統(tǒng)。2、二、八、十、十六進(jìn)制間的轉(zhuǎn)換方法。十進(jìn)制轉(zhuǎn)換成二進(jìn)制：十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)通常采用除2取余法，小數(shù)部分乘2取整法。例如，將30D轉(zhuǎn)換成二進(jìn)制數(shù)。2|30…0----最右位215…127…123…11…1----最左位∴30D=11110B八、十六進(jìn)制轉(zhuǎn)二進(jìn)制方法類似。二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)：對(duì)于整數(shù)，從低位到高位將二進(jìn)制數(shù)的每三位分為一組，若不夠三位時(shí)，在高位左面添0,補(bǔ)足三位，然后將每三

位二進(jìn)制數(shù)用一位八進(jìn)制數(shù)替換，小數(shù)部分從小數(shù)點(diǎn)開(kāi)始，自左向右每三位一組進(jìn)行轉(zhuǎn)換即可完成。例如：將二進(jìn)制數(shù)1101001轉(zhuǎn)換成八進(jìn)制數(shù)，則001101001B|||151O1101001B=151O八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：只要將每位八進(jìn)制數(shù)用三位二進(jìn)制數(shù)替換，即可完成轉(zhuǎn)換，例如，把八進(jìn)制數(shù)（643.503）8,轉(zhuǎn)換成二進(jìn)制數(shù)，則（643.503）8||||||（110100011.101000011）2（643.503）8=（110100011.101000011）2二進(jìn)制與十六進(jìn)制之間的轉(zhuǎn)換（1）二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)：由于2的4次方=16,所以依照二進(jìn)制與八進(jìn)制的轉(zhuǎn)換方法，將二進(jìn)制數(shù)的每四位用一個(gè)十六進(jìn)制數(shù)碼來(lái)表示，整數(shù)部分以小數(shù)點(diǎn)為界點(diǎn)從右往左每四位一組轉(zhuǎn)換，小數(shù)部分從小數(shù)點(diǎn)開(kāi)始自左向右每四位一組進(jìn)行轉(zhuǎn)換。（2）十六進(jìn)制轉(zhuǎn)換成二進(jìn)制數(shù)。如將十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，只要將每一位十六進(jìn)制數(shù)用四位相應(yīng)的二進(jìn)制數(shù)表示，即可完成轉(zhuǎn)換。例如：將（163.5B）16轉(zhuǎn)換成二進(jìn)制數(shù)，則（163.5B）16|||||（000101100011.01011011）2（163.5B）16=（101100011.01011011）2二進(jìn)制的算術(shù)、邏輯運(yùn)算。3、數(shù)據(jù)在計(jì)算機(jī)中的表示方法：各種數(shù)據(jù)在計(jì)算機(jī)中表示的形式稱為機(jī)器數(shù)，其特點(diǎn)是用0,1表示，如0表示正號(hào)，1表示負(fù)號(hào)，小數(shù)點(diǎn)隱含表示而不占位置。機(jī)器數(shù)對(duì)應(yīng)的實(shí)際數(shù)據(jù)稱為真值。機(jī)器數(shù)分為無(wú)符號(hào)數(shù)和有符號(hào)數(shù)。無(wú)符號(hào)數(shù)表示正數(shù)。帶符號(hào)的機(jī)器數(shù)可采用原碼、反碼、補(bǔ)碼等碼制進(jìn)行計(jì)算。4、漢字編碼：漢字處理包括漢字的編碼輸入、存儲(chǔ)、輸出等環(huán)節(jié)。輸入碼（數(shù)字編碼、拼音碼、字形編碼）、內(nèi)部碼（簡(jiǎn)稱漢字內(nèi)碼）（GB2312-80用2字節(jié)表示一個(gè)漢字，Unicode用4字節(jié)表示一個(gè)漢字）、字形碼（點(diǎn)陣、矢量函數(shù)，漢字的輸出方式）。5、cpu的功能：程序控制、操作控制、時(shí)間控制、數(shù)據(jù)處理。6、計(jì)算機(jī)系統(tǒng)分類：Flynn分類法（按指令流、數(shù)據(jù)流分類）、馮式分類法（按最大并行度分類）。指令流：機(jī)器執(zhí)行的指令序列；數(shù)據(jù)流：指令調(diào)用的數(shù)據(jù)序列。7、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)和計(jì)算機(jī)組成的區(qū)別：系統(tǒng)結(jié)構(gòu)是指計(jì)算機(jī)系統(tǒng)在總體上、功能上需要解決的問(wèn)題；計(jì)算機(jī)組成是指在邏輯上如何具體實(shí)現(xiàn)的問(wèn)題。8、計(jì)算機(jī)并行的發(fā)展：不同于同時(shí)性的是，并發(fā)性是指兩個(gè)或兩個(gè)以上事件在同一時(shí)間間隔內(nèi)連續(xù)發(fā)生；分為存儲(chǔ)器操作并行，處理器操作步驟并行（流水線處理機(jī)），處理器操作并行（陣列處理機(jī)），指令、任務(wù)、作業(yè)并行（多處理機(jī)、分布式處理系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)）。9、存儲(chǔ)器的層次結(jié)構(gòu)：高速緩存、主存、輔存。（有人將cpu內(nèi)部的寄存器也作為一個(gè)存儲(chǔ)層次）。存儲(chǔ)器的分類：存儲(chǔ)器按位置分為內(nèi)存（主存）和外存（輔存）；按工作方式分為讀寫(xiě)存儲(chǔ)器和只讀存儲(chǔ)器；按訪問(wèn)方式分為按地址訪問(wèn)和按內(nèi)容訪問(wèn)的存儲(chǔ)器；按尋址方式分為隨機(jī)尋址、順序、直接尋址存儲(chǔ)器。相連存儲(chǔ)器是一種按內(nèi)容訪問(wèn)的存儲(chǔ)器。其工作原理是把數(shù)據(jù)作為關(guān)鍵字與存儲(chǔ)器中的每一單元比較，找出與關(guān)鍵字相同的數(shù)據(jù)。相連存儲(chǔ)器可用在高速緩存中；在虛擬存儲(chǔ)器中用來(lái)作段表、頁(yè)表或快表存儲(chǔ)器；用在數(shù)據(jù)庫(kù)和知識(shí)庫(kù)中。高速緩存：由控制部分和cache部分組成。cache部分放主存的部分拷貝信息，控制部分判斷cpu要訪問(wèn)的信息是否在cache中命中，并按替換算法決定主存的哪一塊信息放到cache中的哪一塊里面。一般來(lái)說(shuō)，Cache的功能全部由硬件實(shí)現(xiàn)。高速緩存與主存的地址映像方法有3種，即直接映像，全相連映像，組相連映像（組使用直接相連而組內(nèi)的塊使用全相連方式）在Cache的替換算法中，“近期最少使用LRU算法”是命中率最高的一種算法。10、虛擬存儲(chǔ)器，是由主存、輔存、存儲(chǔ)管理單元和操作系統(tǒng)的存儲(chǔ)管理軟件組成的存儲(chǔ)系統(tǒng)。它將大容量的外存也納入存儲(chǔ)管理器的管理范圍，具體執(zhí)行程序時(shí)要先判斷程序是否在主存中，若不在則需從輔存中調(diào)入。按工作方式分為：頁(yè)式虛擬存儲(chǔ)器；段式虛擬存儲(chǔ)器；段頁(yè)式虛擬存儲(chǔ)器。11、磁盤(pán)陣列raid,是由多臺(tái)磁盤(pán)存儲(chǔ)器組成的，一個(gè)大而快速、可靠的外存子系統(tǒng)。raid0

是不具備容錯(cuò)能力的陣列，N個(gè)磁盤(pán)組成的0級(jí)陣列，其平均故障時(shí)間間隔是單個(gè)磁盤(pán)存儲(chǔ)器的N分之一；但其數(shù)據(jù)傳輸速率是單的N倍。raid1

使用鏡像容錯(cuò)技術(shù)raid2

使用漢明碼容錯(cuò)技術(shù)raid3

一般使用一個(gè)檢驗(yàn)盤(pán)raid4

只使用一個(gè)檢驗(yàn)盤(pán)raid5

沒(méi)有專門的檢驗(yàn)盤(pán)，它在每塊盤(pán)上都寫(xiě)數(shù)據(jù)和檢驗(yàn)信息。12、CISC--復(fù)雜指令集計(jì)算機(jī)，RISC--精簡(jiǎn)指令集計(jì)算機(jī)。RISC的特點(diǎn)：指令種類少；指令長(zhǎng)度固定、格式少；尋址方式少，適合于組合邏輯控制器；設(shè)置最少的訪問(wèn)內(nèi)存指令，訪問(wèn)內(nèi)存比較花時(shí)間；在CPU內(nèi)部設(shè)置大量寄存器，使操作在CPU內(nèi)部快速進(jìn)行；適合于流水線操作，容易并行執(zhí)行。13、輸入輸出技術(shù)。內(nèi)存與接口的編址方式分為內(nèi)存和接口地址獨(dú)立的編址方式，和內(nèi)存、接口地址統(tǒng)一的編址方式。直接程序控制（無(wú)條件傳送方式、程序查詢方式）（整個(gè)輸入輸出過(guò)程是在cpu執(zhí)行程序的控制下完成）中斷方式

（cpu得用中斷方式完成數(shù)據(jù)的輸入輸出操作）直接存儲(chǔ)器存取（DMA）方式，數(shù)據(jù)直接在內(nèi)存與IO設(shè)備間成塊傳送，cpu只需在開(kāi)始和結(jié)束時(shí)進(jìn)行處理，過(guò)程中無(wú)須干涉。DMA傳送的一般過(guò)程為：1）外設(shè)向DMA控制器提出DMA傳送請(qǐng)求；2）DMA控制器向CPU提出請(qǐng)求；3）CPU允許DMA工作，處理總路線控制的轉(zhuǎn)交；輸入輸出處理機(jī)（IOP）方式,由一個(gè)專用的處理機(jī)完成主機(jī)的輸入輸出操作。14、流水線技術(shù)，是將一條指令分解成一連串執(zhí)行的子過(guò)程，在cpu中將一條指令的串行執(zhí)行過(guò)程變?yōu)槿舾蓷l指令的子過(guò)程重疊執(zhí)行。特點(diǎn)是，流水線可分成若干相互聯(lián)系的子過(guò)程；執(zhí)行每個(gè)子過(guò)程的時(shí)間盡量相等；形成流水處理需要準(zhǔn)備時(shí)間；指令流發(fā)生不能順序執(zhí)行時(shí)會(huì)使流水線中斷。兩個(gè)指標(biāo)，吞吐率（單位時(shí)間里流水線處理機(jī)流出的結(jié)果數(shù)，對(duì)指令而言就是單位時(shí)間里執(zhí)行的指令數(shù)）；建立時(shí)間（所有子過(guò)程執(zhí)行一遍用時(shí)之和）15、總線的分類--芯片內(nèi)總線、元件級(jí)總線、內(nèi)總線（即系統(tǒng)總線）、外總線（即通信總線）。常見(jiàn)的幾種內(nèi)總線：ISA總線（長(zhǎng)短兩個(gè)插座，分別有64個(gè)、32個(gè)接點(diǎn)），EISA總線，PCI總線。其中PCI總線的工作與處理器的工作是相對(duì)獨(dú)立的，即總線時(shí)鐘和處理器時(shí)間是獨(dú)立、非同步的，PCI總線上的設(shè)備即插即用。常見(jiàn)的幾種外總線：RS-232C（是一條串行總線），SCSI（是一條并行總線），USB（由4條信號(hào)線組成，兩條用于傳送數(shù)據(jù)，另兩條傳送+5V500mA的電源），IEE1394（是一條串行總線，由6條信號(hào)線組成，兩條傳數(shù)據(jù)兩條傳控制信號(hào)兩條傳電源，支持即插即用和熱插拔）。16、陣列處理機(jī)，又稱并行處理機(jī)，它將重復(fù)設(shè)置的多個(gè)處理單元連成陣列，在控制部件的控制下，對(duì)分配給自己的數(shù)據(jù)進(jìn)行處理，并行地完成一條指令規(guī)定的操作。這是一種單指令多數(shù)據(jù)流計(jì)算機(jī)（SIMD）。17、多處理機(jī)，是由多臺(tái)處理機(jī)組成的系統(tǒng)。每臺(tái)處理機(jī)有自己的控制部件，可以執(zhí)行獨(dú)立的程序，共享一個(gè)主存和所有外設(shè)。它是多指令流多數(shù)據(jù)流計(jì)算機(jī)。按其構(gòu)成分為：異構(gòu)（非對(duì)稱）型多處理機(jī)系統(tǒng)，同構(gòu)（對(duì)稱）型多處理機(jī)系統(tǒng)，分布式處理系統(tǒng)。4種多處理機(jī)的結(jié)構(gòu)：總線結(jié)構(gòu)，交叉開(kāi)關(guān)結(jié)構(gòu)，多端口存儲(chǔ)器結(jié)構(gòu)，開(kāi)關(guān)樞紐式結(jié)構(gòu)。18、并行處理機(jī)，與采用流水結(jié)構(gòu)的單機(jī)系統(tǒng)都是單指令流多數(shù)據(jù)流計(jì)算機(jī)，它們的區(qū)別是，并行處理機(jī)采用資源重復(fù)技術(shù)，而流水結(jié)構(gòu)的單機(jī)系統(tǒng)使用時(shí)間重疊技術(shù)。并行處理機(jī)有2種典型結(jié)構(gòu)：具有分布式存儲(chǔ)器的，具有共享式存儲(chǔ)器的。它們的共同點(diǎn)是在系統(tǒng)中設(shè)置多個(gè)處理單元，各個(gè)處理器按一定。接方式交換信息，在統(tǒng)一的控制部件作用下，各自處理分配來(lái)的數(shù)據(jù)，并行的完成同一指令所規(guī)定的操作。19、信息安全的基本要素。機(jī)密性；完整性；可用性；可控性；可審查性。20、計(jì)算機(jī)安全等級(jí)：技術(shù)安全性、管理安全性、政策法律安全性。一些重要的安全評(píng)估準(zhǔn)則：“美國(guó)國(guó)防部和國(guó)家標(biāo)準(zhǔn)局的《可信計(jì)算機(jī)系統(tǒng)評(píng)測(cè)標(biāo)準(zhǔn)》TCSEC/TDI”、“歐共體的信息技術(shù)安全評(píng)估準(zhǔn)則ITSEC”、“ISO/IEC國(guó)際標(biāo)準(zhǔn)”、“美國(guó)聯(lián)邦標(biāo)準(zhǔn)”。其中TCSEC/TDI分了4個(gè)組7個(gè)等級(jí)，C2是安全產(chǎn)品的最低等級(jí)。21、安全威脅與影響數(shù)據(jù)安全的因素安全威脅是指某個(gè)人、物、事件對(duì)某一資源的機(jī)密性、完整性、可用性或合法性所造成的危害。典型的安全威脅有很多種。影響數(shù)據(jù)安全的因素有內(nèi)部和外部?jī)煞N。內(nèi)部因素：可采取多種技術(shù)對(duì)數(shù)據(jù)加密；制定數(shù)據(jù)安全規(guī)劃；建立安全存儲(chǔ)體系；建立事故應(yīng)急計(jì)劃和容災(zāi)措施；重視安全管理并建立安全管理規(guī)范。外部因素：按密級(jí)劃分使用人員的權(quán)限；使用多種認(rèn)證方式；設(shè)置防火墻；建立入侵檢測(cè)、審計(jì)和追蹤；同時(shí)注意物理環(huán)境的保護(hù)。22、加密技術(shù)包括兩個(gè)元素：算法和密鑰。加解密算法設(shè)計(jì)的關(guān)鍵是滿足3個(gè)條件“可逆性”,“密鑰安全”,“數(shù)據(jù)安全”。數(shù)據(jù)加密技術(shù)分為對(duì)稱加密（以DES算法為代表）、非對(duì)稱加密（以RSA算法為代表）、不可逆加密3種。目前常用的對(duì)稱加密算法有：DES數(shù)據(jù)加密標(biāo)準(zhǔn)算法（使用56位密鑰，對(duì)64位二進(jìn)制數(shù)據(jù)塊加密，基本加密運(yùn)算為置換運(yùn)算、移位運(yùn)算、模加運(yùn)算）；3DES（使用2個(gè)56位密鑰，加、解、加）；RC-5;國(guó)際數(shù)據(jù)加密算法IDEA（類似于3DES,使用128位密鑰，PGP系統(tǒng)在使用該算法）比較有名的非對(duì)稱加密算法：RSA算法，它是建立在大素?cái)?shù)因子分解的理論基礎(chǔ)上的算法。其公鑰密碼長(zhǎng)度大于100位，算法運(yùn)算速度較慢，多用于加密信息量小的場(chǎng)合，可以使用RSA算法來(lái)實(shí)現(xiàn)數(shù)字簽名。23、密鑰管理，主要是指密鑰對(duì)的管理，包括密鑰的產(chǎn)生、選擇、分發(fā)、更換和銷毀、備份和恢復(fù)等。多密鑰的管理可以使用KDC。24、數(shù)據(jù)完整性保護(hù)，是在數(shù)據(jù)中加入一定的冗余信息，從而能發(fā)現(xiàn)對(duì)數(shù)據(jù)的任何增刪改。方法是在發(fā)送或?qū)懭霑r(shí)對(duì)所要保護(hù)的數(shù)據(jù)進(jìn)行檢驗(yàn)和作加密處理，產(chǎn)生報(bào)文驗(yàn)證碼MAC,附在數(shù)據(jù)后面。在接受或讀出數(shù)據(jù)時(shí)根據(jù)約定的密鑰對(duì)數(shù)據(jù)進(jìn)行檢驗(yàn)和作加密運(yùn)算，將所得的結(jié)果與MAC比較，根據(jù)結(jié)果是否一致判斷數(shù)據(jù)是否完整。25、認(rèn)證技術(shù)，主要是解決網(wǎng)絡(luò)通信雙方的身份認(rèn)可。認(rèn)證的過(guò)程涉及到加密和密鑰交換。加密可使用對(duì)稱加密、不對(duì)稱加密和二者混合使用的方法。一般有賬戶名/口令認(rèn)證、使用摘要算法認(rèn)證、基于PKI公開(kāi)密鑰的認(rèn)證。PKI是一種遵守既定標(biāo)準(zhǔn)的密鑰管理平臺(tái)，它能為所有網(wǎng)絡(luò)應(yīng)用提供加密和數(shù)字簽名等密碼服務(wù)及必需的密鑰和證書(shū)管理體系。PKI的基礎(chǔ)技術(shù)包括加密、數(shù)字簽名、數(shù)據(jù)完整性機(jī)制、數(shù)字信封、雙重?cái)?shù)字簽名等。完整的PKI系統(tǒng)必須包括CA、數(shù)字證書(shū)庫(kù)、密鑰備份及恢復(fù)系統(tǒng)、證書(shū)作廢系統(tǒng)、應(yīng)用接口API等基本部分。PKI使用證書(shū)進(jìn)行公鑰管理，通過(guò)CA將用戶的公鑰和用戶其它住處綁在一起，以在因特網(wǎng)上驗(yàn)證用戶身份。26、HASH函數(shù)，輸入一個(gè)不定長(zhǎng)的字符串，返回一個(gè)固定長(zhǎng)度的字符串（即HASH值）。單向HASH函數(shù)用于產(chǎn)生信息摘要；信息摘要簡(jiǎn)要地描述了一份較長(zhǎng)的信息或文件，可以被看作是一份文件的數(shù)字指紋，信息摘要用于創(chuàng)建數(shù)字簽名。27、數(shù)字簽名的過(guò)程：信息發(fā)送者使用一單向HASH函數(shù)對(duì)信息生成信息摘要；信息發(fā)送者使用自己的私鑰加密信息摘要；信息發(fā)送者將信息本身和已簽名的信息摘要一并發(fā)送出去；信息接收者使用發(fā)送者的公鑰對(duì)信息摘要解密，再使用同一單向HASH算法對(duì)信息生成信息摘要并進(jìn)行驗(yàn)證是否一致。28、數(shù)字加密的過(guò)程：信息發(fā)送者先生成一個(gè)對(duì)稱密鑰，使用該密鑰對(duì)信息加密；信息發(fā)送者使用接收者的公鑰加密上述對(duì)稱密鑰；信息發(fā)送者將上兩步的結(jié)果內(nèi)容都傳給接收者（這就是數(shù)字信封）；信息接收者使用私鑰解密對(duì)稱密鑰，并使用對(duì)稱密鑰解密信息本身。29、SSL安全協(xié)議，一個(gè)能夠保證任何安裝了SSL的客戶和服務(wù)器之間事務(wù)安全性的協(xié)議，主要用于提高應(yīng)用程序之間數(shù)據(jù)的安全系數(shù)。SSL提供3方面服務(wù)：客戶和服務(wù)器的合法性認(rèn)證；加密傳送的數(shù)據(jù)；保護(hù)數(shù)據(jù)的完整性。30、數(shù)字時(shí)間戳技術(shù)，就是數(shù)字簽名技術(shù)的一個(gè)變種，不同的是這個(gè)要由認(rèn)證單位DTS提供數(shù)字簽名。它的過(guò)程是：先形成需要加時(shí)間戳的信息的信息摘要；將信息摘要送到DTS,DTS記錄收到的日期及時(shí)間；DTS進(jìn)行數(shù)字簽名，然后送回用戶。31、計(jì)算機(jī)病毒的定義，它是一種程序，具有修改別的程序的特性，并使用被修改的程序也具有這樣的特性。病毒的特點(diǎn)：寄生性，隱畢性，非法性，傳染性，破壞性。按病毒的寄生方式和入侵方式分成：系統(tǒng)引導(dǎo)型病毒，文件外殼型，混合型病毒，目錄型病毒，宏病毒（也叫數(shù)據(jù)病毒）。需要注意的幾點(diǎn)：變種、病毒程序加密、多形性病毒、病毒的偽裝。計(jì)算機(jī)病毒防治的手段：人工預(yù)防；軟件預(yù)防；管理預(yù)防。解決網(wǎng)絡(luò)安全問(wèn)題的技術(shù)包括：劃分網(wǎng)段、局域網(wǎng)交換技術(shù)和VLAN;加密技術(shù)、數(shù)字簽名和認(rèn)證、VPN技術(shù)；防火墻技術(shù)；入侵檢測(cè)技術(shù)；網(wǎng)絡(luò)安全掃描技術(shù)。32、計(jì)算機(jī)的RAS技術(shù)，R（可靠性）、A（可用性）、S（可維修性）。計(jì)算機(jī)可靠性的模型有：串聯(lián)系統(tǒng)模型、并聯(lián)系統(tǒng)、N模冗余系統(tǒng)。串聯(lián)系統(tǒng)可靠性R=R1*R2*…Rn

平均故障率=L1+L2+Ln并聯(lián)系統(tǒng)可靠性R=1-（1-R1）（1-R2）（1-Rn）N模冗余系統(tǒng)由2n+1個(gè)子系統(tǒng)和一個(gè)表決器組成，只要n+1個(gè)子系統(tǒng)工作正常，系統(tǒng)就工作正常。提高可靠性的辦法：提高元件質(zhì)量、改進(jìn)加工工藝與工藝結(jié)構(gòu)、完善電路設(shè)計(jì)、發(fā)展容錯(cuò)講述。33、計(jì)算機(jī)性能評(píng)測(cè)的常用方法：時(shí)鐘頻率法、指令執(zhí)行速度法、等效指令執(zhí)行速度法、數(shù)據(jù)處理速率法、核心程序法?；鶞?zhǔn)測(cè)試程序有，整數(shù)測(cè)試程序、浮點(diǎn)測(cè)試程序、SPEC基準(zhǔn)測(cè)試程序、TPC基準(zhǔn)程序。34、計(jì)算機(jī)故障包括永久故障、間歇性故障和偶然故障。故障診斷分為故障檢測(cè)和故障定位兩方面。容錯(cuò)，就是通過(guò)冗余方法來(lái)消除故障影響。硬件冗余有時(shí)間冗余和器件冗余兩種。故障處理步驟，封閉、檢錯(cuò)、重復(fù)執(zhí)行、診斷、重構(gòu)與恢復(fù)、修復(fù)、重入。35、BCD（Binary-Coded

Decimal）碼又稱為“二-十進(jìn)制編碼”,專門解決用二進(jìn)制數(shù)表示十進(jìn)數(shù)的問(wèn)題。壓縮BCD碼每一位數(shù)采用4位二進(jìn)制數(shù)來(lái)表示，即一個(gè)字節(jié)表示2位十進(jìn)制數(shù)。例如：二進(jìn)制數(shù)10001001B,采用壓縮BCD碼表示為十進(jìn)制數(shù)89D。非壓縮BCD碼每一位數(shù)采用8位二進(jìn)制數(shù)來(lái)表示，即一個(gè)字節(jié)表示1位十進(jìn)制數(shù)。而且只用每個(gè)字節(jié)的低4位來(lái)表示0~9,高4位為0。例如：十進(jìn)制數(shù)89D,采用非壓縮BCD碼表示為二進(jìn)制數(shù)是：0000100000001001B36、ASCII是AmericanStandardCodeforInformationInterchange的縮寫(xiě)，用來(lái)制訂計(jì)算機(jī)中每個(gè)符號(hào)對(duì)應(yīng)的代碼，這也叫做計(jì)算機(jī)的內(nèi)碼（code）。每個(gè)ASCII碼以1個(gè)字節(jié)（Byte）儲(chǔ)存，從0到數(shù)字127代表不同的常用符號(hào)，例如大寫(xiě)A的ASCII碼是65,小寫(xiě)a則是97,阿拉伯?dāng)?shù)字0則是48.由于ASCII字節(jié)的七個(gè)位，最高位并不使用。第0~32號(hào)及第127號(hào)（共34個(gè)）是控制字符或通訊專用字符，如控制符：LF（換行）、CR（回車）、FF（換頁(yè)）、DEL（刪除）、BEL（振鈴）等；通訊專用字符：SOH（文頭）、EOT（文尾）、ACK（確認(rèn)）等；第33~126號(hào)（共94個(gè)）是字符，其中第48~57號(hào)為0~9十個(gè)阿拉伯?dāng)?shù)字；65~90號(hào)為26個(gè)大寫(xiě)英文字母，97~122號(hào)為26個(gè)小寫(xiě)英文字母，其余為一些標(biāo)點(diǎn)符號(hào)、運(yùn)算符號(hào)等。注意：在計(jì)算機(jī)的存儲(chǔ)單元中，一個(gè)ASCII碼值占一個(gè)字節(jié)（8個(gè)二進(jìn)制位），其最高位（b7）用作奇偶校驗(yàn)位。所謂奇偶校驗(yàn)，是指在代碼傳送過(guò)程中用來(lái)檢驗(yàn)是否出現(xiàn)錯(cuò)誤的一種方法，一般分奇校驗(yàn)和偶校驗(yàn)兩種。奇校驗(yàn)規(guī)定：正確的代碼一個(gè)字節(jié)中1的個(gè)數(shù)必須是奇數(shù)，若非奇數(shù)，則在最高位b7添1;偶校驗(yàn)規(guī)定：正確的代碼一個(gè)字節(jié)中1的個(gè)數(shù)必須是偶數(shù)，若非偶數(shù)，則在最高位b7添1。37、按位與的特殊用途：清零。

方法：與一個(gè)各位都為零的數(shù)值相與，結(jié)果為零。取一個(gè)數(shù)x中某些指定位。

方法：找一個(gè)數(shù)，此數(shù)的各位是這樣取值的：對(duì)應(yīng)x數(shù)要取各位，該數(shù)對(duì)應(yīng)位為1,其余位為零。此數(shù)與x相就可以得到x中的某些位。例：設(shè)X=10101110（1）取X的低4位（2）取X的bit2、bit4、bit6位38、某EPROM芯片上有24條地址線A0-A23，8條數(shù)據(jù)線D0-D7,則該芯片的容量為“16M”。EPROM芯片上的地址線決定了該芯片有多少個(gè)存儲(chǔ)單元，數(shù)據(jù)線數(shù)表明每個(gè)存儲(chǔ)單元所存儲(chǔ)的數(shù)據(jù)位數(shù)。24條地址線則有16M個(gè)存儲(chǔ)單元，8條數(shù)據(jù)線決定了每個(gè)存儲(chǔ)單元存1個(gè)字節(jié)。所以容量為16M字節(jié)。39、機(jī)內(nèi)碼、國(guó)標(biāo)碼、區(qū)位碼根據(jù)漢字的國(guó)家標(biāo)準(zhǔn)，用兩個(gè)字節(jié)（16位二進(jìn)制數(shù)）表示一個(gè)漢字。但使用16位二進(jìn)制數(shù)容易出錯(cuò)，比較困難，因而在使用中都將其轉(zhuǎn)換為十六進(jìn)制數(shù)使用。國(guó)標(biāo)碼是一個(gè)四位十六進(jìn)制數(shù)，區(qū)位碼則是一個(gè)四位的十進(jìn)制數(shù)，每個(gè)國(guó)標(biāo)碼或區(qū)位碼都對(duì)應(yīng)著一個(gè)唯一的漢字或符號(hào)，但因?yàn)槭M(jìn)制數(shù)我們很少用到，所以大家常用的是區(qū)位碼，它的前兩位叫做區(qū)碼，后兩位叫做位碼。國(guó)標(biāo)碼規(guī)定，每個(gè)漢字（包括非漢字的一些符號(hào)）由2字節(jié)代碼表示。每個(gè)字節(jié)的最高位為0,只使用低7位，而低7位的編碼中又有34個(gè)適用于控制用的，這樣每個(gè)字節(jié)只有27-34=94個(gè)編碼用于漢字。2個(gè)字節(jié)就有9494=8836個(gè)漢字編碼。在表示一個(gè)漢字的2個(gè)字節(jié)中，高字節(jié)對(duì)應(yīng)編碼表中的行號(hào)，稱為區(qū)號(hào)；低字節(jié)對(duì)應(yīng)編碼表中的列號(hào)，稱為位號(hào)。國(guó)標(biāo)碼與機(jī)內(nèi)碼轉(zhuǎn)換關(guān)系：為了不與7位ASCII碼發(fā)生沖突，把國(guó)標(biāo)碼每個(gè)字節(jié)的最高位由0改為1,其余位不變的編碼就是漢字字符的機(jī)內(nèi)碼。也可以理解為國(guó)標(biāo)碼加上8080H后得到機(jī)內(nèi)碼，或是機(jī)內(nèi)碼減去8080H后得到國(guó)標(biāo)碼。國(guó)標(biāo)碼與區(qū)位碼轉(zhuǎn)換關(guān)系：將國(guó)標(biāo)碼減去2020H后，得到區(qū)位碼。如某漢字機(jī)內(nèi)碼是BFF0H,則國(guó)標(biāo)碼為3F70H,區(qū)位碼為1F50H。40、在采用三總線的運(yùn)算器中，三條總線分別與運(yùn)算器的兩個(gè)輸入一個(gè)輸出相連接，各自有自己的通路。因此執(zhí)行一次操作只需一步即可完成。在運(yùn)算器的兩個(gè)輸入和一個(gè)輸出上不再需要設(shè)置暫存器。41、光盤(pán)上的信號(hào)是記錄在光盤(pán)表面的凹坑及平面上。凹坑與平面的交接處代表1,因此在光盤(pán)上不允許有連續(xù)的兩個(gè)1。42、磁盤(pán)非格式化容量=最大位密度*最內(nèi)圈周長(zhǎng)*總磁道數(shù)--實(shí)際上就是使用磁盤(pán)的面積乘以位密度。格式化容量

=每道扇區(qū)數(shù)*扇區(qū)容量*總磁道數(shù)總磁道數(shù)為：（外半徑-內(nèi)半徑）*磁道密度常識(shí)：有一個(gè)多盤(pán)片組成的盤(pán)組，在向磁盤(pán)記錄一個(gè)文件時(shí)，如果超出了一個(gè)磁道容量，那么剩下的部分將存于其他盤(pán)面的同一編號(hào)的磁道上。因?yàn)楸P(pán)組中的多個(gè)盤(pán)面形成一系列柱面，在向磁盤(pán)寫(xiě)入文件時(shí)會(huì)盡可能記錄在同一柱面上，當(dāng)一個(gè)柱面記錄不下時(shí)，再記錄到相鄰的柱面上。43、微指令根據(jù)編碼方式的不同分為水平微指令和垂直微指令。水平微指令，長(zhǎng)度較長(zhǎng)、操作具有高度并行性、編碼簡(jiǎn)單、執(zhí)行速度快，更多地體現(xiàn)了控制器的硬件細(xì)節(jié)。垂直微指令，長(zhǎng)度較短、并行度低、功能弱、效率低、編程容易但微程序長(zhǎng)。排列組合公式為：求n上數(shù)中m個(gè)數(shù)的組合有多少，C=n（n-1）（n-2）（n-m+1）/m!例如求n個(gè)數(shù)中每2個(gè)數(shù)組合的可能性，C=n（n-1）/2種可能性。第二章：數(shù)據(jù)結(jié)構(gòu)與算法1、線性表的定義及特點(diǎn)線性表是若干數(shù)據(jù)元素組成的有限集合。線性表的特點(diǎn)是，有惟一的起始結(jié)點(diǎn)和惟一的終端結(jié)點(diǎn)，其它元素都有惟一的直接前驅(qū)和惟一的直接后繼。線性表的抽像數(shù)據(jù)類型定義包括2方面：數(shù)據(jù)對(duì)象、關(guān)系的定義；線性表有關(guān)操作的定義；線性表的數(shù)據(jù)對(duì)象是具有相同性質(zhì)數(shù)據(jù)元素的集合。線性表的有關(guān)操作有：基本操作：初始化線性表、撤消線性表、判/置空表、取表長(zhǎng)、取前驅(qū)元素、取后繼元素、取第i個(gè)元素、遍歷等。插刪操作：在順序結(jié)構(gòu)下，結(jié)點(diǎn)的插入（n/2）和刪除[（n-1）/2]主要是進(jìn)行元素的移動(dòng)；在鏈?zhǔn)浇Y(jié)構(gòu)下，結(jié)點(diǎn)的插刪是調(diào)整指針的指向。查找操作：在順序表中可以進(jìn)行折半查找，在鏈表中只能進(jìn)行順序查找。2、線性表的基本存儲(chǔ)結(jié)構(gòu)及特點(diǎn)，線性表有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是：用一組地址任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。（存儲(chǔ)單元節(jié)點(diǎn)可以是連續(xù)的，也可以是不連續(xù)的）。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)包括：?jiǎn)捂湵恚ㄓ址Q線性鏈表），結(jié)點(diǎn)的結(jié)構(gòu)體有兩個(gè)域，分別存儲(chǔ)數(shù)據(jù)元素和當(dāng)前元素有關(guān)系的其它元素所在結(jié)點(diǎn)的指針。雙向鏈表，每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，分別指明直接前驅(qū)和直接后繼元素，可以在兩個(gè)方向上遍歷其后及其前的元素。循環(huán)鏈表，鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向第一個(gè)結(jié)點(diǎn)，開(kāi)成環(huán)狀結(jié)構(gòu)，可以在任意位置上方向不變地遍歷全表。靜態(tài)鏈表，借助數(shù)組描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、棧的定義：是只能通過(guò)訪問(wèn)它的一端來(lái)實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)。棧的特點(diǎn)：是先進(jìn)后出（FILO）。在線結(jié)構(gòu)中，允許進(jìn)行插、刪操作的一端稱為棧頂，相應(yīng)另一端稱為棧底。不含數(shù)據(jù)的棧稱為空棧。棧的基本運(yùn)算有：置空棧、判空棧、元素入棧、出棧和讀取棧頂元素的值。棧的存儲(chǔ)結(jié)構(gòu)：順序棧和鏈棧。順序棧指，用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)自棧頂?shù)綏５椎脑兀瑫r(shí)設(shè)置指針top指示棧頂元素的位置。順序棧的空間容量是有限的，要預(yù)先定義。順序棧的入棧和出棧操作是通過(guò)修改數(shù)組下標(biāo)來(lái)完成。假設(shè)棧底對(duì)應(yīng)于數(shù)組下標(biāo)較大的一端，那么在元素入棧時(shí)就是下標(biāo)減1,而元素出棧時(shí)就是下標(biāo)加1。鏈棧，類似于線性鏈表，棧頂指針就是鏈表首結(jié)點(diǎn)的位置，元素的插刪操作限定在首結(jié)點(diǎn)處進(jìn)行。棧的應(yīng)用：表達(dá)式計(jì)算，數(shù)制轉(zhuǎn)換，括號(hào)匹配，迷宮問(wèn)題，遞歸問(wèn)題。4、隊(duì)列的定義：是一種先進(jìn)先出（FIFO）的線性表。隊(duì)列的特點(diǎn)：它只允許在表的一端插入元素而在表的另一端刪除元素。在隊(duì)列中允許插的一端叫隊(duì)尾（rear），允許刪的一端叫隊(duì)頭（front）。隊(duì)列的基本運(yùn)算：置隊(duì)空、判隊(duì)空、入隊(duì)、出隊(duì)、讀隊(duì)頭元素等。隊(duì)列的存儲(chǔ)結(jié)構(gòu)：順序隊(duì)列和鏈隊(duì)列。順序隊(duì)列，又被叫作循環(huán)隊(duì)列，設(shè)順序隊(duì)列Q,Q.front表示隊(duì)頭指針，Q.rear表示隊(duì)尾指針，則Q.front和Q.rear相等且為0時(shí)為空隊(duì)列；元素入隊(duì)時(shí)Q.rear加1,元素出隊(duì)時(shí)Q.front加1.因?yàn)轫樞蜿?duì)列的空間容量是提前設(shè)定的，所以當(dāng)Q.rear達(dá)到了上限時(shí)表示隊(duì)列滿。

為區(qū)別隊(duì)列空和隊(duì)列滿兩種情況下可能出現(xiàn)的Q.front==Q.rear,有兩種方法。一個(gè)是設(shè)置一個(gè)標(biāo)識(shí)位，以區(qū)別頭尾指針相同時(shí)隊(duì)列是空還是滿；另一個(gè)方法是犧牲一個(gè)元素空間，約定以Q.rear所指的下一個(gè)位置是Q.front時(shí)表示隊(duì)列滿。鏈隊(duì)列，鏈隊(duì)列為空的判定條件是頭尾指針相同且均指向頭結(jié)點(diǎn)。隊(duì)列的應(yīng)用：常用于需要排隊(duì)的場(chǎng)合，如操作系統(tǒng)中的打印隊(duì)列，離散事件的復(fù)讀機(jī)模擬等。5、串的定義：是僅由字符構(gòu)成的有限序列。是取值范圍受限的線性表。一般記為S='a1a2an'。串的幾個(gè)概念：空串、空格串、子串、串相等、串比較。串的幾個(gè)操作：賦值操作StrAssign（s,t）、聯(lián)接操作Concat（s,t）、求串長(zhǎng)StrLength（s）、串比較StrCompare（s,t）、求子串SubString（s,start,len）。串的存儲(chǔ)：靜態(tài)存儲(chǔ)（順序存儲(chǔ)），是定長(zhǎng)的存儲(chǔ)結(jié)構(gòu)。當(dāng)串超長(zhǎng)時(shí)，超過(guò)部分將被截?cái)唷６汛鎯?chǔ)，通過(guò)程序語(yǔ)言提供的字符數(shù)組定義串的存儲(chǔ)空間，事先不限定串的長(zhǎng)度，在程序執(zhí)行過(guò)程中動(dòng)態(tài)地申請(qǐng)地址連續(xù)的串值的空間。塊鏈存儲(chǔ)，使用鏈表存儲(chǔ)串值，每個(gè)結(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)字符，同時(shí)每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)指針指向后繼結(jié)點(diǎn)。串的模式匹配：樸素的模式匹配法、KMP算法。6、數(shù)組：是定長(zhǎng)線性表在維數(shù)上的擴(kuò)張，即線性表中的每個(gè)元素又是一個(gè)線性表。N維數(shù)組是一種同構(gòu)的數(shù)據(jù)結(jié)構(gòu)，其每個(gè)數(shù)據(jù)元素類型相同，結(jié)構(gòu)一致。數(shù)組的特點(diǎn)：數(shù)組元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組結(jié)構(gòu)就不再有元素的增減變化；數(shù)據(jù)元素具有相同的類型；數(shù)據(jù)元素的下標(biāo)關(guān)系受上下界的約束且下標(biāo)有序。數(shù)組的基本運(yùn)算：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素；給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)的值。數(shù)組的存儲(chǔ)：數(shù)組的固定結(jié)構(gòu)適于使用順序存儲(chǔ)。對(duì)于數(shù)組，只要知道它的維數(shù)和長(zhǎng)度，就可以為它分配存儲(chǔ)空間。反之，只要給出一組下標(biāo)就可以求出該數(shù)組元素的存儲(chǔ)位置。就是說(shuō)，在數(shù)組的順序存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)元素的位置是其下標(biāo)的線性函數(shù)。以行為主序；

Loc（Aij）=Loc（Aij）+（（i-1）*n+（j-1））*L以列為主序；

Loc（Aij）=Loc（Aij）+（（j-1）*m+（i-1））*L多維數(shù)組的順序存儲(chǔ)計(jì)算：例如3維數(shù)組A[110,58,-36],數(shù)組空間的起始位置是a,每個(gè)元素占4個(gè)存儲(chǔ)單元，試以行為主存儲(chǔ)和以列為主存儲(chǔ)時(shí)給出數(shù)組元素A[i,j,k]的存儲(chǔ)地址。解：理解上面給出的以行為主序和以列為主序的兩個(gè)線性函數(shù)公式。把3維數(shù)組拆開(kāi)計(jì)算，例如以行為主序時(shí)先將3維數(shù)組看成是有一個(gè)行和2個(gè)列的數(shù)組，算出此時(shí)以行為主占用了多少空間。然后再單獨(dú)看兩個(gè)列的組合B[j,k]又會(huì)占用多少空間。前后結(jié)果相加就是這個(gè)3維數(shù)組元素在以行為主序存儲(chǔ)時(shí)的地址。如下，以行為主序時(shí)，A[i,j,k]前面的元素個(gè)數(shù)是：（i-1）（8-5+1）（6-（-3）+1）+（j-5）（6-（-3）+1）+k-（-3）=40i-40+10j-50+k+3=40i+10j+k-87因此A[i,j,k]的地址為a+（40i+10j+k-87）*4以列為主序時(shí)，A[i,j,k]的地址為a+（40k+10j+i+69）*47、特殊矩陣與稀疏矩陣，稀疏矩陣就是非零元素很少的矩陣，而特殊矩陣是非零元素分布有規(guī)律的一類矩陣。為節(jié)省空間，在存儲(chǔ)它們時(shí)都使用壓縮存儲(chǔ)，特殊矩陣有壓縮算法，稀疏矩陣使用三元組順序表或使用十字鏈表存儲(chǔ)矩陣元素。8、廣義表的定義：是由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的長(zhǎng)度是指廣義表中元素的個(gè)數(shù)，深度是指廣義表展開(kāi)后所含的括號(hào)的最大層數(shù)。廣義表的基本運(yùn)算：取表頭head（LS），非空廣義表的第一個(gè)元素稱為表頭；取表尾tail（LS），非空廣義表中除第一個(gè)元素之外，由其余元素構(gòu)成的表稱為表尾。表尾必定是一個(gè)表。Head（LS）=a1,Tail（LS）=（a2,a3,…，an）9、樹(shù)的定義：樹(shù)是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空樹(shù)。在任一非空樹(shù)中，有且僅有一個(gè)稱為根的結(jié)點(diǎn)；其余m個(gè)結(jié)點(diǎn)可分為m（m>=0）個(gè)互不相交的有限集，其中每個(gè)子集合又都是一棵樹(shù)，稱為根結(jié)點(diǎn)的子樹(shù)。樹(shù)的定義是遞歸的，樹(shù)形結(jié)構(gòu)具有明顯的層次結(jié)構(gòu)。樹(shù)的術(shù)語(yǔ)：雙親和孩子，兄弟，結(jié)點(diǎn)的度，葉子結(jié)點(diǎn)，內(nèi)部結(jié)點(diǎn)，結(jié)點(diǎn)的層次，樹(shù)的高度，有序樹(shù)和無(wú)序樹(shù)，森林。樹(shù)的基本操作是：先根遍歷和后根遍歷。10、二叉樹(shù)的定義：二叉樹(shù)是另一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)并且有左右之分，且左、右子樹(shù)的次序不能顛倒。滿二叉樹(shù)，若二叉樹(shù)上每一層的結(jié)點(diǎn)數(shù)目都達(dá)到最大值，則稱為滿二叉樹(shù)；完全二叉樹(shù)，若二叉樹(shù)的除第H層以外，其余各層的結(jié)點(diǎn)數(shù)目達(dá)到了最大值，而第H層上的結(jié)點(diǎn)集中存放在左側(cè)，則稱為完全二叉樹(shù)；非完全二叉樹(shù)，就是完全二叉樹(shù)的相反情況。二叉樹(shù)的性質(zhì)：

1）二叉樹(shù)第i層（i>=1）上至多有2^（i-1）個(gè)結(jié)點(diǎn)。2）深度為K的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)（k>=1）。3）對(duì)任何一棵二叉樹(shù)，若其終端結(jié)點(diǎn)個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)個(gè)數(shù)為N2,則N0=N2+1。4）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log（2,n）+1。5）對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層次自左至右進(jìn)行編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1<=i<=n）有：若i=1,則i是根結(jié)點(diǎn)；若i>1則其雙親為i/2。若2i>n,,則結(jié)點(diǎn)i無(wú)左孩子，否則其左孩子為2i。若2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子為2i+1。例：一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，最多有多少結(jié)點(diǎn)？N0=N2+1N=N0+N1+N2N1=1綜合上面3個(gè)表達(dá)式可以求解。例2:具有N個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，其葉子結(jié)點(diǎn)個(gè)數(shù)為多少？設(shè)其深度為h,則：N0=2^（h-1）N=2^h-1所以N0=（n+1）/2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，若采用二叉樹(shù)的性質(zhì)5對(duì)樹(shù)中的結(jié)點(diǎn)進(jìn)行編號(hào)，即樹(shù)根結(jié)點(diǎn)的編號(hào)為1,若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則其左孩子的編號(hào)為2i;若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則其右孩子的編號(hào)為2i+1,這樣利用數(shù)組元素的下標(biāo)作為結(jié)點(diǎn)的編號(hào)，表示出結(jié)點(diǎn)間的關(guān)系。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，二叉鏈表（有單向性）和三叉鏈表（有雙向性）。遍歷二叉樹(shù)，有4種方式：先序、中序、后序和層序遍歷。先序遍歷二叉樹(shù)的操作定義為：訪問(wèn)根結(jié)點(diǎn)；先序遍歷根的左子樹(shù)；先序遍歷根的右子樹(shù)。（若二叉樹(shù)為空，則進(jìn)行空操作）。中序遍歷二叉樹(shù)的操作定義為：中序遍歷根的左子樹(shù)；訪問(wèn)根結(jié)點(diǎn)；中序遍歷根的右子樹(shù)。（若二叉樹(shù)為空，則進(jìn)行空操作）。后序遍歷二叉樹(shù)的操作定義為：后序遍歷根的左子樹(shù)；后序遍歷根的右子樹(shù)；訪問(wèn)根結(jié)點(diǎn)。層序遍歷二叉樹(shù)的操作定義為：從根結(jié)點(diǎn)開(kāi)始，從或到右依次訪問(wèn)每層上的結(jié)點(diǎn)。二叉樹(shù)遍歷思想的關(guān)鍵：首先在想象中把二叉樹(shù)補(bǔ)齊為滿二叉樹(shù)，葉子結(jié)點(diǎn)也要被想象為有2個(gè)子結(jié)點(diǎn)。然后，畫(huà)一條路線，從根出發(fā)，逆時(shí)針沿著二叉樹(shù)的外緣移動(dòng)，全程對(duì)每個(gè)結(jié)點(diǎn)均途經(jīng)三次。若第一次經(jīng)過(guò)時(shí)即訪問(wèn)，則是先序遍歷；若是第二次經(jīng)過(guò)結(jié)點(diǎn)時(shí)訪問(wèn)結(jié)點(diǎn)，則是中序遍歷；若是第3次經(jīng)過(guò)時(shí)訪問(wèn)則是后序遍歷。這3種方法的路徑相同，但結(jié)果不同。遍歷二叉樹(shù)的基本操作就是，訪問(wèn)結(jié)點(diǎn)。--遍歷二叉樹(shù)實(shí)質(zhì)上是按一定規(guī)則，將樹(shù)中的結(jié)點(diǎn)排成一個(gè)線性序列。11、線索二叉樹(shù)：對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表存儲(chǔ)表示，其中必有N+1個(gè)空指針。遍歷時(shí)使結(jié)點(diǎn)中原本為空的左孩子指針或（和）右孩子指針指向結(jié)點(diǎn)的前驅(qū)或（和）后繼，這樣的處理稱為對(duì)二叉樹(shù)的線索化，指向前驅(qū)或后繼的指針?lè)Q為線索。加上線索的二叉樹(shù)稱為線索二叉樹(shù)。為了區(qū)分結(jié)點(diǎn)中的指針是孩子還是線索，在結(jié)點(diǎn)結(jié)構(gòu)中增加標(biāo)志域ltag,rtag。兩個(gè)標(biāo)志取值0,則lchild,rchild域分別指向左孩子和右孩子；兩個(gè)標(biāo)志取值1,則lchild,rchild域分別指向直接前驅(qū)和直接后繼。訪問(wèn)線索二叉樹(shù)時(shí)，如何查找結(jié)點(diǎn)的前驅(qū)和后繼？以中序線索二叉樹(shù)為例，令P指向樹(shù)中的某個(gè)結(jié)點(diǎn)。當(dāng)p->ltag=0時(shí)，P的中序直接前驅(qū)一定是其左子樹(shù)進(jìn)行中序遍歷得到的最后一個(gè)結(jié)點(diǎn)，也可以沿P的左子樹(shù)根結(jié)點(diǎn)出發(fā)沿右孩子指針向下查找，直到找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)時(shí)為止，該結(jié)點(diǎn)就是P的直接前驅(qū)結(jié)點(diǎn)，也稱為P的左子樹(shù)中“最右下”的結(jié)點(diǎn)。當(dāng)P->rtag=0時(shí)，P的中序直接后繼一定是其右子樹(shù)進(jìn)行中序遍歷得到的第一個(gè)結(jié)點(diǎn)，

也可以沿P的右子樹(shù)根結(jié)點(diǎn)出發(fā)沿左孩子指針向上查找，直到找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)時(shí)為止，該結(jié)點(diǎn)就是P的直接后繼結(jié)點(diǎn)，也稱為P的右子樹(shù)中“最左下”的結(jié)點(diǎn)。12、二叉樹(shù)的應(yīng)用：最優(yōu)二叉樹(shù)（又稱霍夫曼樹(shù)），是一種帶權(quán)路徑長(zhǎng)度最短的樹(shù)。路徑，是從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度，是從根到每一個(gè)葉子結(jié)點(diǎn)之間的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，是從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度，是樹(shù)的所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL。如何構(gòu)造最優(yōu)二叉樹(shù)？使用霍夫曼算法如下：1）將給定的N個(gè)結(jié)點(diǎn)的權(quán)值構(gòu)成N棵二叉樹(shù)的集合F,其中每棵樹(shù)Ti只有一個(gè)權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹(shù)為空。2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)，并新生成一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)的權(quán)值和。3）從F中刪除被取出的兩棵樹(shù)并將新生成的樹(shù)放入F。4）重復(fù)2,3步驟到只剩一棵樹(shù)為止，這棵樹(shù)就是最優(yōu)二叉樹(shù)。最優(yōu)二叉樹(shù)的形式不唯一，但其WPL值卻是唯一確定的?；舴蚵幋a：若要設(shè)計(jì)長(zhǎng)度不等的編碼，則任一字符的編碼都不是其他字符編碼的前綴，這種編碼稱為“前綴編碼”。要設(shè)計(jì)總長(zhǎng)最短的二進(jìn)制前綴編碼，應(yīng)以N種字符出現(xiàn)的頻率作為權(quán)來(lái)構(gòu)造一棵霍夫曼樹(shù)，由此得到的二進(jìn)制前綴編碼稱為霍夫曼編碼。樹(shù)的左右分枝分別標(biāo)上0和1（或相反）。從根到葉子路徑上的0,1組成的串就是每個(gè)字符的二進(jìn)制編碼。13、樹(shù)的存儲(chǔ)結(jié)構(gòu)1）樹(shù)的雙親表示法，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)樹(shù)的結(jié)點(diǎn)，并在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在該存儲(chǔ)結(jié)構(gòu)中的位置；2）樹(shù)的孩子表示法，是在存儲(chǔ)結(jié)構(gòu)中用指針指出結(jié)點(diǎn)的每個(gè)孩子。要為樹(shù)的每個(gè)結(jié)點(diǎn)的孩子建立一個(gè)鏈表，則N個(gè)結(jié)點(diǎn)的樹(shù)具有N個(gè)單鏈表，這N個(gè)單鏈表的頭指針又排成了一個(gè)線性表（頭指針即樹(shù)的存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的指示器）。將上兩種方法結(jié)合起來(lái)可以形成樹(shù)的雙親孩子表示法。3）樹(shù)的孩子兄弟表示法，是指用二叉鏈表表示樹(shù)。在鏈表的結(jié)點(diǎn)中設(shè)置兩個(gè)指針域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟。

|firstchild|data|nextbrother|

若將樹(shù)的孩子指針解釋為左孩子、兄弟指針解釋為右孩子，則可以得到這棵樹(shù)的二叉樹(shù)結(jié)構(gòu)。14、樹(shù)的遍歷：先根遍歷；后根遍歷。樹(shù)進(jìn)行先根遍歷也就是對(duì)轉(zhuǎn)換得到的二叉樹(shù)進(jìn)行先序遍歷；對(duì)樹(shù)進(jìn)行后根遍歷也就是對(duì)轉(zhuǎn)換得到的二叉樹(shù)進(jìn)行中序遍歷。（先根遍歷的順序是：由根出發(fā)從左至右遍歷每棵子樹(shù)。后根遍歷的順序是從左至右從每棵子樹(shù)的葉子結(jié)點(diǎn)向根的方向訪問(wèn)子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。）15、森林的遍歷：先序遍歷森林；中序遍歷森林。先序遍歷森林，若森林非空，訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)，先序遍歷第一棵子樹(shù)根結(jié)點(diǎn)的子樹(shù)森林，再先序遍歷除第一棵樹(shù)之外的樹(shù)所構(gòu)成的森林。中序遍歷森林，若森林非空，中序遍歷森林中第一棵樹(shù)的子樹(shù)森林，再訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)，再中序遍歷除第一棵樹(shù)以外的樹(shù)所構(gòu)成的森林。16、樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換利用樹(shù)的孩子兄弟表示法可以由一棵樹(shù)轉(zhuǎn)成唯一的一棵二叉樹(shù)。森林如何轉(zhuǎn)換成二叉樹(shù)呢？因?yàn)闃?shù)根沒(méi)有兄弟，所以樹(shù)轉(zhuǎn)換成二叉樹(shù)后一定沒(méi)有右子樹(shù)，所以森林轉(zhuǎn)換成二叉樹(shù)的方法是：1）先將森林中的每棵樹(shù)全轉(zhuǎn)成二叉樹(shù)；2）用第一棵樹(shù)的根做新二叉樹(shù)的根，第一棵樹(shù)轉(zhuǎn)為二叉樹(shù)后得到的左子樹(shù)做為新二叉樹(shù)的左子樹(shù)，第二棵樹(shù)作為新二叉樹(shù)的右子樹(shù)，第三棵樹(shù)作為新二叉樹(shù)的右子樹(shù)的右子樹(shù)，依此類推，森林便轉(zhuǎn)為了一棵二叉樹(shù)。17、圖的定義：在數(shù)據(jù)結(jié)構(gòu)中，圖是一個(gè)由頂點(diǎn)集合和邊集合構(gòu)成的二元組，其中邊表示頂點(diǎn)之間的關(guān)系。圖的主要術(shù)語(yǔ)：有向圖，圖中每條邊都是有方向的，弧、弧尾、弧頭；無(wú)向圖，圖中的邊是沒(méi)有方向的，邊；無(wú)向完全圖，圖中的N個(gè)結(jié)點(diǎn)之間每?jī)蓚€(gè)結(jié)點(diǎn)間都有邊，共有n（n-1）/2條邊；有向完全圖，圖中的N個(gè)結(jié)點(diǎn)之間每?jī)蓚€(gè)結(jié)點(diǎn)間都有方向相反的兩條弧，共有n（n-1）條弧；度、入度、出度，頂點(diǎn)v的度是指關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記作D（v）。若是有向圖則以該頂點(diǎn)為終點(diǎn)的有向邊數(shù)目稱為入度，從該頂點(diǎn)出發(fā)的有向邊的數(shù)目稱為出度，有向圖的度是入庫(kù)和出度的和。路徑，兩個(gè)頂點(diǎn)之間由邊組成的一條通路。若是有向圖則路徑也有方向。路徑長(zhǎng)度是路徑上邊或弧的數(shù)目。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路。若首尾頂點(diǎn)以外的頂點(diǎn)均不相同則是簡(jiǎn)單路徑，若只有首尾頂點(diǎn)相同則稱為簡(jiǎn)單回路。子圖，一個(gè)圖的頂點(diǎn)集合與邊集合都從屬于另一個(gè)圖，則稱之為另一個(gè)圖的子圖；連通圖與連通分量，在無(wú)向圖中若兩個(gè)頂點(diǎn)之間有路徑則稱為這兩個(gè)頂點(diǎn)是連通的。若無(wú)向圖中任兩個(gè)頂點(diǎn)間都是連通的則稱其為連通圖。該無(wú)向圖的最大連通子圖稱為它的連通分量。強(qiáng)連通圖與強(qiáng)連通分量，是有向圖的連通概念；網(wǎng)，邊（?。?quán)值的圖稱為網(wǎng)；生成樹(shù)，是一個(gè)極小的連通子圖，它包括圖中的全部頂點(diǎn)，但只有構(gòu)成一棵樹(shù)的n-1條邊；有向樹(shù)和生成森林，一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0其它頂點(diǎn)的入度均為1,則這是一棵有向樹(shù)。生成森林是一個(gè)有向圖中的若干棵有向樹(shù)組成，特點(diǎn)是含有全部頂點(diǎn)但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧。圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示法，用于表示圖有頂點(diǎn)之間的關(guān)系。對(duì)于個(gè)有n個(gè)頂點(diǎn)的圖G=（V,E）來(lái)說(shuō)，其鄰接矩陣就是一個(gè)n階方陣。依靠判斷圖的兩頂點(diǎn)間是否存在邊或弧來(lái)決定Aij=1或Aij=0;網(wǎng)的鄰接矩陣，當(dāng)兩頂點(diǎn)間存在邊或弧時(shí)Aij等于權(quán)值否則Aij等于無(wú)窮。鄰接鏈表表示法，為圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中的結(jié)點(diǎn)表示依附于相應(yīng)頂點(diǎn)的邊或弧，有表頭結(jié)點(diǎn)和表結(jié)點(diǎn)兩種結(jié)構(gòu)類型。圖的遍歷：深度優(yōu)先搜索；廣度優(yōu)先搜索。一個(gè)類似于先根遍歷，一個(gè)類似于層序遍歷。生成樹(shù)的概念：生成樹(shù)是連通圖的一個(gè)子圖，它由全部頂點(diǎn)和一次遍歷圖所經(jīng)過(guò)的邊組成。圖的生成樹(shù)不惟一，按深度優(yōu)先搜索得到深度優(yōu)先生成樹(shù)，按廣度優(yōu)先搜索得到廣度優(yōu)先生成樹(shù)。一個(gè)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊集一起構(gòu)成若干棵生成樹(shù)，稱為非連通圖的生成樹(shù)森林。18、最小生成樹(shù)：連通網(wǎng)的邊是帶有權(quán)值的，將生成樹(shù)的各邊權(quán)值和稱為生成樹(shù)的權(quán)。其中權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)。構(gòu)造最小生成樹(shù)的兩種算法：普里母算法：以一個(gè)頂點(diǎn)集合U作為初態(tài)，不斷尋找與U中頂點(diǎn)相鄰且代價(jià)最小的邊的另一個(gè)頂點(diǎn)，擴(kuò)充U至U=V時(shí)為止。例如初始只給U一個(gè)頂點(diǎn)且邊的集合TE={};這種算法的時(shí)間復(fù)雜度為O（n^2），因?yàn)樗身旤c(diǎn)推算出的，所以適合于邊稠密的網(wǎng)的最小生成樹(shù)?？唆斔箍査惴ǎ杭僭O(shè)連通網(wǎng)N=（V,E），令最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=（V,{}），圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。信此類推，直至T中所有頂點(diǎn)都在一個(gè)連通分量上為止。這種算法與頂點(diǎn)數(shù)無(wú)關(guān)，所以適合計(jì)算頂點(diǎn)多而邊稀疏的網(wǎng)的最小生成樹(shù)。19、AOV網(wǎng)（activeonvertex）：在有向圖中，以頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的網(wǎng)稱為AOV網(wǎng)。在AOV網(wǎng)中不應(yīng)出現(xiàn)有向環(huán)。拓樸排序：是將AOV網(wǎng)中所有頂點(diǎn)排成一個(gè)線性序列的過(guò)程，并且該序列滿足：若在AOV網(wǎng)中從頂點(diǎn)Vi到Vj有一條路徑，則在該線性序列中，頂點(diǎn)Vi必然在Vj之前。拓樸排序的方法：在AOV網(wǎng)中選一個(gè)入度為0的頂點(diǎn)并輸出它；從網(wǎng)中刪除該頂點(diǎn)及與其有關(guān)的邊；重復(fù)前兩步至網(wǎng)中不存在入度為0的頂點(diǎn)為止。這樣操作會(huì)有兩種結(jié)果：一個(gè)是所有頂點(diǎn)已輸出，也就是拓樸排序完成，說(shuō)明網(wǎng)中不存在回路；另一個(gè)可能結(jié)果是尚有未輸出的結(jié)點(diǎn)，剩余頂點(diǎn)均有前驅(qū)頂點(diǎn)，表明網(wǎng)中存在回路！也可以進(jìn)行逆拓樸排序，即計(jì)算出度為0的頂點(diǎn)。拓樸算法的時(shí)間復(fù)雜度為O（n+e）。AOE網(wǎng)（activeonedge）：,在帶權(quán)有向圖中，以事件表示頂點(diǎn)，以邊表示活動(dòng)，以邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間，則這種網(wǎng)稱為用邊表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOE網(wǎng)。AOE網(wǎng)特點(diǎn)：1）頂點(diǎn)所表示的事件是指該頂點(diǎn)的所有進(jìn)入邊所表示的活動(dòng)已完成，所有發(fā)出邊表示的活動(dòng)可以開(kāi)始的一種狀態(tài)。2）對(duì)一個(gè)工程來(lái)說(shuō)，要有一個(gè)開(kāi)始狀態(tài)和一個(gè)結(jié)束狀態(tài)，所以在AOE網(wǎng)中有一個(gè)入度為0的開(kāi)始頂點(diǎn)，稱為源點(diǎn)；有一個(gè)出度為0的結(jié)束頂點(diǎn)，稱為匯點(diǎn)。AOE網(wǎng)中也不允許存在回路。3）完成整個(gè)工程的時(shí)間是從開(kāi)始頂點(diǎn)到結(jié)束頂點(diǎn)間的最長(zhǎng)路徑的長(zhǎng)度（指該路徑上的權(quán)值和）?；顒?dòng)的松馳時(shí)間：用活動(dòng)的持續(xù)時(shí)間和該活動(dòng)兩側(cè)的兩個(gè)事件的關(guān)鍵路徑時(shí)間，二者取差。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的路徑長(zhǎng)度最長(zhǎng)路徑稱為關(guān)鍵路徑。關(guān)鍵路徑上的所有活動(dòng)均是關(guān)鍵活動(dòng)。最短路徑？？？20、查找的基本概念1）查找是一種常用的基本運(yùn)算。查找表是由同一類型數(shù)據(jù)元素構(gòu)成的集合；2）靜態(tài)查找表，指在進(jìn)行查找運(yùn)算時(shí)不再修改的已經(jīng)構(gòu)造好的查找表。靜態(tài)查找表只進(jìn)行兩種操作：查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中；檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性。3）動(dòng)態(tài)查找表，是可以進(jìn)行另兩種操作的查找表，即在查找表中插入一個(gè)數(shù)據(jù)元素；從查找表中刪除一個(gè)數(shù)據(jù)元素。4）關(guān)鍵字，是數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它來(lái)識(shí)別這個(gè)數(shù)據(jù)元素；5）主關(guān)鍵字，指能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字；6）次關(guān)鍵字，指能標(biāo)識(shí)多個(gè)數(shù)據(jù)元素的關(guān)鍵字；7）查找，根據(jù)給定的某個(gè)值，在查找表中確定是否存在一個(gè)其關(guān)鍵字等于給定值的記錄，并返回結(jié)果。順序查找，從表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若找到一個(gè)記錄的關(guān)鍵字和給定值相等則查找成功；若整個(gè)表均比較過(guò)仍未找到則查找失敗。若要查找的記錄不在表中則需進(jìn)行n+1次查找。平均查找長(zhǎng)度為（n+1）/2。折半查找（二分查找），可以用二叉樹(shù)進(jìn)行分析，以中間記錄為根，左子表為左子樹(shù)，右子表為右子樹(shù)，依此類推。關(guān)鍵字的比較次數(shù)即為被查找結(jié)點(diǎn)在樹(shù)中的層數(shù)。查找成功或失敗時(shí)所比較的關(guān)鍵字?jǐn)?shù)不超過(guò)樹(shù)的層數(shù)。折半查找只適用于有序順序表（以數(shù)組方式存儲(chǔ)的有序表）。n=2^k-1,k=log（n+1）分塊查找，又稱為索引順序查找，綜合使用上面兩種方法。將長(zhǎng)度為n的表均勻分為b塊，每塊含有s個(gè)記錄，按順序查找確定元素所在的塊，則ASL=Lb+Lw,即塊內(nèi)查找與索引查找之和。ASL=（b+1）/2+（s+1）/2,當(dāng)s取n的平方根時(shí)，ASL取得最小值“n的平方根加1”。21、二叉排序樹(shù)（又稱二叉查找樹(shù)）：二叉查找樹(shù)或者是一棵空樹(shù)，或者具有這樣的特性，1）若二叉查找樹(shù)的左子樹(shù)非空，則左子樹(shù)上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)的值；2）若它的右子樹(shù)非空，則右子樹(shù)上的結(jié)點(diǎn)值均大于根結(jié)點(diǎn)的值；3）左、右子樹(shù)的子身就是一棵二叉查找樹(shù)。二叉查找樹(shù)的查找過(guò)程從根結(jié)點(diǎn)開(kāi)始，過(guò)程類似于折半查找（二分查找）。二叉查找樹(shù)的插入操作按它的特性法則進(jìn)行插入，若是空樹(shù)則作根結(jié)點(diǎn)，否則會(huì)成為一個(gè)新的葉子結(jié)點(diǎn)。在二叉查找樹(shù)中刪除一個(gè)結(jié)點(diǎn)時(shí)不能把該結(jié)點(diǎn)的子樹(shù)也刪掉，只能刪除這個(gè)結(jié)點(diǎn)但仍要保持二叉查找樹(shù)的特性，相當(dāng)于是從一個(gè)有序序列中刪除一個(gè)元素，不能破壞其它元素的有序性。一種方法是，如果刪除結(jié)點(diǎn)*P,則可以用*P的直接前驅(qū)或直接后繼代替*P,同時(shí)刪除它的直接前驅(qū)（或直接后繼）。二叉排序樹(shù)順序存儲(chǔ)在一地址連續(xù)的空間內(nèi)，則序列按中序遞增存儲(chǔ)。22、平衡二叉樹(shù)：它或者是一棵空樹(shù)，或者具有這樣的性質(zhì)：它的左右子樹(shù)都是平衡二叉樹(shù)，且左右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1。平衡因子：某結(jié)點(diǎn)的平衡因子定義為該結(jié)點(diǎn)的左子樹(shù)深度減去它的右子樹(shù)深度。平衡二叉樹(shù)上的所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。為了得到樹(shù)形均勻的二叉排序樹(shù)，在構(gòu)造二叉排序樹(shù)的過(guò)程中可以使用幾種辦法讓它保持為一棵平衡二叉樹(shù)。每插入一個(gè)新結(jié)點(diǎn)時(shí)，就檢查是否打破了平衡。若是，則找出最小不平衡二叉樹(shù)，在保持二叉排序樹(shù)特性的情況下，調(diào)整最小不平衡二叉樹(shù)中結(jié)點(diǎn)間關(guān)系，達(dá)到新的平衡。最小不平衡二叉樹(shù)是指離插入結(jié)點(diǎn)最近且以平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)作為根的子樹(shù)。平衡二叉樹(shù)上的插入操作引起不平衡的解決方法：1）單向右旋平衡處理--用于在根的左子樹(shù)根結(jié)點(diǎn)的左子樹(shù)上插入新結(jié)點(diǎn)情況。2）單向左旋平衡處理--用于在根的右子樹(shù)根結(jié)點(diǎn)的右子樹(shù)上插入新結(jié)點(diǎn)情況。3）雙向旋轉(zhuǎn)（先左旋后右旋）操作--用于在根的左子樹(shù)根結(jié)點(diǎn)的右子樹(shù)上插入新結(jié)點(diǎn)的情況。4）雙向旋轉(zhuǎn)（先右旋后左旋）操作--用于在根的右子樹(shù)根結(jié)點(diǎn)的左子樹(shù)上插入新結(jié)點(diǎn)的情況。B樹(shù)，有幾個(gè)比較鮮明的特點(diǎn)。如：一棵m階的B樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；非終結(jié)點(diǎn)（根除外）至少有m/2棵樹(shù)；根至少有兩棵子樹(shù)（當(dāng)根不是葉子時(shí)）；所有葉子結(jié)點(diǎn)出現(xiàn)在同一層次上。23、哈希表的定義：根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法，將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)地址集上，并以關(guān)健字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表。這一映射過(guò)程稱為哈希造表或散列，所得的存儲(chǔ)位置稱為哈希地址或散列地址。哈希函數(shù)是從關(guān)鍵字集合到地址集合的映像。對(duì)于哈希表主要考慮兩個(gè)問(wèn)題：一是如何構(gòu)造哈希函數(shù)；一是如何解決沖突。構(gòu)造哈希函數(shù)要解決好兩個(gè)問(wèn)題：首先哈希函數(shù)是一個(gè)壓縮映像函數(shù)；其次哈希函數(shù)應(yīng)具有較好的散列性。前者為節(jié)省空間，后者為減少?zèng)_突。常用的哈希函數(shù)構(gòu)造方法有直接定址法、數(shù)字分析法、平方取中法、折疊法、隨機(jī)數(shù)法和除留余數(shù)法。處理沖突的方法：1）開(kāi)放地址法Hi=（H（key）+Di）%m

i=1,2,…，k（k<=m-1）H（key）為哈希函數(shù)；m為哈希表的表長(zhǎng)；Di為增量序列。Di=1,2,3,…，m-1稱為線性探測(cè)再散列；Di=1^2,-1^2,2^2,-2^2…，k^2（k<=m/2）

稱為二次探測(cè)再散列；Di=偽隨機(jī)序列，稱為隨機(jī)探測(cè)再散列。最簡(jiǎn)單的產(chǎn)生探測(cè)序列的方法是線性探測(cè)，即當(dāng)沖突時(shí)順序?qū)ο乱粏卧M(jìn)行探測(cè)并存儲(chǔ)。在用線性探測(cè)法解決沖突構(gòu)造的哈希表中進(jìn)行查找時(shí)有3種可能結(jié)果：一是在某一位置上找到關(guān)鍵字等于key的記錄，查找成功；一是按探測(cè)序列查找不到而又遇到了空單元，查找失敗，此時(shí)可進(jìn)行插入操作；一是查遍全表，未查到指定關(guān)鍵字且存儲(chǔ)區(qū)已滿，要進(jìn)行溢出處理。線性探測(cè)法的缺點(diǎn)是“溢出處理需別編程序”,“很容易產(chǎn)生聚集現(xiàn)象”。2）鏈地址法,它在符號(hào)表的每一個(gè)記錄增加一個(gè)鏈域，鏈域中存放下一個(gè)有相同哈希函數(shù)值的記錄的的存儲(chǔ)地址。3）再哈希法,Hi=RHi（key）

i=1,2,,k

RHi均是不同的哈希函數(shù)，即在同義詞發(fā)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到解決。4）建立一個(gè)公共溢出區(qū)，一溢出全放這里去；哈希表的裝填因子，a=（表中添入的記錄數(shù)/哈希表長(zhǎng)度）

--a越小，發(fā)生沖突的可能越小雖然哈希表在關(guān)鍵字與記錄的存儲(chǔ)位置之間建立了直接映像，但由于“沖突”的產(chǎn)生，使得哈希表的查找過(guò)程仍是一個(gè)給定值和關(guān)鍵字進(jìn)行比較的過(guò)程。仍須以平均查找長(zhǎng)度衡量哈希表的查找效率。在查找過(guò)程中須與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于3個(gè)因素：哈希函數(shù)、處理沖突方法、哈希表的裝填因子。24、排序：穩(wěn)定的排序、不穩(wěn)定的排序。內(nèi)部排序、外部排序。簡(jiǎn)單排序法：包括直接插入排序、冒泡排序和簡(jiǎn)單選擇排序。它們的算法復(fù)雜度為O（n^2），在元素已經(jīng)基本有序的情況下，使用直接排序方法可獲得較高的效率O（n）。直接插入排序和冒泡排序是穩(wěn)定的排序方法，簡(jiǎn)單選擇排序是不穩(wěn)定的排序方法。直接插入排序適用于“在文件局部有序或文件長(zhǎng)度較小的情況下的一種最佳內(nèi)部排序方法”.直接插入排序的時(shí)間復(fù)雜度為O（n*n），若記錄序列為正序時(shí)其時(shí)間復(fù)雜度可提高到O（n）。正序？？冒泡排序算法：voidbubblesort（intdata[],intn）{inti,j,tag,temp;for（i=0,tag=1;tag==1&&i<n-1;i++）{tag=0;for（j=0;j<n-i-1;j++）if（data[j]>data[j+1]）{temp=data[j];data[j]=data[j+1];data[j+1]=temp;tag=1;}}}簡(jiǎn)單選擇排序算法：voidselectsort（intdata[],intn）{inti,j,k,temp;for（i=0;i<n-1;i++）{k=i;for（j=i+1;j<n;j++）if（data[j]<data[k]）k=j;if（k!=j）{temp=data[i];data[i]=data[k];data[k]=temp;}}}希爾排序，又稱為縮小增量排序。它是在直接插入排序的基礎(chǔ)上加以改進(jìn)得到的排序方法?；舅枷刖褪牵涸O(shè)定一個(gè)初始間隔d,d<n,按間隔d將元素分組，在每一組內(nèi)進(jìn)行直接插入排序，可以使得最小元素跳躍式向前移動(dòng)。然后縮小增量d的值，重復(fù)上述操作到d=1時(shí)為止。快速排序，基本思想是通過(guò)一趟排序?qū)⒋判虻挠涗浄指顬楠?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分小，然后再分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序。具體做法：在頭尾設(shè)兩個(gè)指針low,high,分別指向第一個(gè)元素和最后一個(gè)元素。設(shè)樞軸記錄為正向（返向）的第一個(gè)記錄。當(dāng)初始序列有序時(shí)，快速排序蛻變?yōu)槊芭菖判颍藭r(shí)算法的時(shí)間復(fù)雜度為n*n。例如，對(duì)50個(gè)整數(shù)進(jìn)行快速排序時(shí)，因?yàn)槌跏夹蛄杏行颍耘判蜻^(guò)程退化為冒泡排序，總過(guò)程中的比較次數(shù)為49+48+…+1=49*50/2堆排序，基本思想是對(duì)一組待排序記錄的關(guān)鍵字，首選把它們按堆的定義排成一個(gè)序列，從而輸出堆頂?shù)淖钚￡P(guān)鍵字。然后將剩余關(guān)鍵字再調(diào)整成堆，便得到次小關(guān)鍵字，反復(fù)進(jìn)行，直至全部關(guān)鍵字排成有序序列。歸并排序，是將兩個(gè)或多個(gè)有序表合并成一個(gè)新的有序表。是一種穩(wěn)定的排序。基數(shù)排序，是一種借助多關(guān)鍵字排序思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法。它不是基于關(guān)鍵字比較的排序方法，其平均時(shí)間復(fù)雜度為O（d*n），適合于n值很大而關(guān)鍵字較少的序列?；陉P(guān)鍵字比較的內(nèi)部排序方法的時(shí)間復(fù)雜度的下限為O（nlogn），簡(jiǎn)單排序、希爾排序、快速排序、堆排序和歸并排序是要熟練掌握的排序方法。（重要）排序方法好壞的兩條因素：執(zhí)行算法的時(shí)間；執(zhí)行算法所需要的附加空間。常用的外部排序方法是歸并排序。25、分治法，將一個(gè)規(guī)模為n的問(wèn)題逐步分解為k個(gè)規(guī)模更小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題性質(zhì)相同，逐個(gè)解決分解出的子問(wèn)題，由這些子問(wèn)題的解構(gòu)造出原問(wèn)題的解，當(dāng)k=2時(shí)稱為二分法。如解決棋盤(pán)覆蓋問(wèn)題。分治法適用的問(wèn)題一般具有這些特征：原問(wèn)題可以分解成多個(gè)子問(wèn)題，這些子問(wèn)題與原問(wèn)題相比只是規(guī)模的下降而其結(jié)構(gòu)和求解方法與原問(wèn)題相同；若子問(wèn)題的規(guī)模足夠小，則直接求解，否則遞歸地求解子問(wèn)題；在得到各子問(wèn)題的解后，能采用某種方法構(gòu)造出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃法，與分治法類似也是先將待求解的問(wèn)題分解成若個(gè)個(gè)子問(wèn)題，先求解子問(wèn)題，然后從子問(wèn)題的解得到原問(wèn)題的解。不同的是適合于動(dòng)態(tài)規(guī)劃法求解的問(wèn)題所分解得到的子問(wèn)題之間往往不是獨(dú)立的。動(dòng)態(tài)規(guī)劃法常用來(lái)求解具有最優(yōu)性質(zhì)的問(wèn)題。即問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。如求解多邊形游戲問(wèn)題。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟為：1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；2）遞歸地定義最優(yōu)值；3）以向前或向后處理方式計(jì)算出最優(yōu)值；4）根據(jù)計(jì)算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解。貪心法，通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解，它所做的每一次選擇都是當(dāng)前情況下某種意義的最好選擇，即貪心選擇。如果待求解的問(wèn)題具有最優(yōu)子結(jié)構(gòu)特征，也就是原問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解，并且可以通過(guò)局部的貪心選擇來(lái)達(dá)到問(wèn)題的全局最優(yōu)解時(shí)，可通過(guò)貪心法進(jìn)行求解。貪心標(biāo)準(zhǔn)的選擇和問(wèn)題的結(jié)構(gòu)決定是否可以使用貪心法。如用于二分最小覆蓋問(wèn)題?；厮莘?，又被稱為通用解題法，用它可以系統(tǒng)地搜索問(wèn)題的所有解?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在問(wèn)題的解空間中按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索到解空間樹(shù)的任意結(jié)點(diǎn)時(shí)，首先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果不包含則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則進(jìn)入這棵子樹(shù)繼續(xù)按深度優(yōu)先搜索。如收費(fèi)公路重建問(wèn)題。分支限界法，它類似于回溯法，也是在解空間中搜索問(wèn)題解的算法，但分支限界法求解的目標(biāo)是找出滿足條件的一個(gè)解，如有多個(gè)解則要找出某種意義下的最優(yōu)解。分支限界法以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。如最大完備子圖問(wèn)題。26、算法的幾個(gè)基本特征有窮性，確定性，能行性，輸入，輸出。程序=數(shù)據(jù)結(jié)構(gòu)+算法內(nèi)容關(guān)鍵字：線性表、棧、隊(duì)、串、數(shù)組樹(shù)、二叉樹(shù)、森林、線索二叉樹(shù)、霍夫曼樹(shù)圖、有向圖、無(wú)向圖、最小生成樹(shù)、拓樸排序、關(guān)鍵路徑查找、靜態(tài)查找（順序、折半、分塊）、動(dòng)態(tài)查找（二叉排序樹(shù)、平衡二叉樹(shù)、哈希表）排序、直接插入、簡(jiǎn)單選擇、冒泡、希爾、快速、堆、歸并、基數(shù)第三章：操作系統(tǒng)知識(shí)1、操作系統(tǒng)的定義：是管理計(jì)算機(jī)中各種軟件、硬件資源的程序和相關(guān)文檔的集合，是一種系統(tǒng)軟件。操作系統(tǒng)能有效的組織和管理系統(tǒng)中的各種軟、硬件資源，合理地組織計(jì)算機(jī)工作流程，控制程序的執(zhí)行，并且向用戶提供一個(gè)良好的工作環(huán)境和友好的接口。操作系統(tǒng)的兩個(gè)重要作用：通過(guò)資源管理，提高系統(tǒng)的使用效率。改善人機(jī)界面，向用戶提供友好的工作環(huán)境。操作系統(tǒng)的4個(gè)特征：并發(fā)性、共享性、虛擬性、不確定性。操作系統(tǒng)的5個(gè)管理功能：進(jìn)程管理、文件管理、存儲(chǔ)管理、設(shè)備管理、作業(yè)管理。操作系統(tǒng)的分類：批處理系統(tǒng)，計(jì)算機(jī)自動(dòng)、順序地執(zhí)行作業(yè)流產(chǎn)生的每一個(gè)作業(yè)，以節(jié)省人工操作時(shí)間和提高機(jī)器的使用效率。分為單道批處理系統(tǒng)和多道批處理系統(tǒng)。優(yōu)點(diǎn)是同一批內(nèi)的各作業(yè)次次執(zhí)行，改善了cpu,io的使用效率，提高了吞吐量。缺點(diǎn)是磁盤(pán)需要人工裝卸，作業(yè)需要人工分類，監(jiān)督程序易受用戶程序破壞，缺少交互性。分時(shí)系統(tǒng)，

具有如下特征：多路性、獨(dú)立性、交互性、及時(shí)性。實(shí)時(shí)系統(tǒng)，分為實(shí)時(shí)控制系統(tǒng)和實(shí)時(shí)信息處理系統(tǒng)。主要特點(diǎn)有：快速的響應(yīng)時(shí)間、有限的交互能力、高可靠性。網(wǎng)絡(luò)操作系統(tǒng)，使得計(jì)算機(jī)更有效地共享網(wǎng)絡(luò)資源，為網(wǎng)絡(luò)用戶提供所需各種服務(wù)的軟件和有關(guān)協(xié)議的集合。分布式操作系統(tǒng)，是由多個(gè)分散的計(jì)算機(jī)經(jīng)網(wǎng)絡(luò)連接而成，各主機(jī)無(wú)主次之分。為分布式計(jì)算機(jī)配置的操作系統(tǒng)稱為分布式操作系統(tǒng)。微機(jī)操作系統(tǒng)嵌入式操作系統(tǒng)2、研究操作系統(tǒng)的觀點(diǎn)資源管理的觀點(diǎn)：從這種觀點(diǎn)看，操作系統(tǒng)的管理對(duì)象是計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)則是管理計(jì)算機(jī)系統(tǒng)的程序集合。這種觀點(diǎn)是在共享的前提下以資源分配、使用和回收為出發(fā)點(diǎn)，考慮操作系統(tǒng)各部分程序的功能和算法。虛擬機(jī)的觀點(diǎn)：操作系統(tǒng)加裸機(jī)構(gòu)成虛擬計(jì)算機(jī)。虛擬機(jī)的觀點(diǎn)是從功能分解的角度出發(fā)，考慮操作系統(tǒng)的結(jié)構(gòu)，將操作系統(tǒng)分成若干層次，每一層完成特定的功能。3、順序程序執(zhí)行時(shí)的特征：順序性、封閉性、可再現(xiàn)性。并發(fā)程序執(zhí)行時(shí)的特征：非封閉性、程序和機(jī)器執(zhí)行程序的活動(dòng)不在一一對(duì)應(yīng)、并發(fā)程序間的相互制約性。引入進(jìn)程的原因：由于程序并發(fā)執(zhí)行破壞了程序的封閉性和可再現(xiàn)性，使得程序和執(zhí)行程序的活動(dòng)不在一一對(duì)應(yīng)，此時(shí)用靜態(tài)的程序概念已經(jīng)不能描述系統(tǒng)中程序動(dòng)態(tài)執(zhí)行的過(guò)程，所以引入了進(jìn)程。4、進(jìn)程的定義：就是程序的一次執(zhí)行，該程序可以和其它程序并發(fā)執(zhí)行。進(jìn)程的組成：進(jìn)程通常是由程序、數(shù)據(jù)及進(jìn)程控制塊（PCB）組成的。進(jìn)程的程序部分是進(jìn)程執(zhí)行時(shí)不可修改部分，它描述了進(jìn)程需要完成的功能；進(jìn)程的數(shù)據(jù)部分是進(jìn)程的可修改部分；進(jìn)程控制塊是進(jìn)程的描述信息和控制信息，是進(jìn)程存在的惟一標(biāo)志。進(jìn)程和程序的區(qū)別是：進(jìn)程具有狀態(tài)而程序沒(méi)有。5、進(jìn)程的狀態(tài)及狀態(tài)間的切換三態(tài)模型：運(yùn)行、就緒、阻塞。五態(tài)模型：新建態(tài)、終止態(tài)、運(yùn)行、就緒、阻塞。新建態(tài)：對(duì)應(yīng)于進(jìn)程剛剛被創(chuàng)建時(shí)還沒(méi)有被提交，并等待系統(tǒng)完成創(chuàng)建進(jìn)程的所有必要信息的狀態(tài)。整個(gè)過(guò)程分為兩個(gè)階段，一是為一個(gè)新建進(jìn)程創(chuàng)建必要的管理信息，另一是讓進(jìn)程進(jìn)入就緒狀態(tài)。因?yàn)橛辛诵陆☉B(tài)，操作系統(tǒng)可以根據(jù)系統(tǒng)的性能和主存的容量限制而推遲新建態(tài)的提交。終止態(tài)也分為兩個(gè)階段，一是等待操作系統(tǒng)進(jìn)行善后處理，另一是釋放主存。具有掛起狀態(tài)的進(jìn)程狀態(tài)：當(dāng)系統(tǒng)資源不能滿足所有進(jìn)程的運(yùn)行要求時(shí)，必須將某些進(jìn)程掛起，放在磁盤(pán)對(duì)換區(qū)，暫時(shí)不參加調(diào)度，以平衡系統(tǒng)負(fù)載。有這樣幾個(gè)狀態(tài)：活躍就緒、靜止就緒、活躍阻塞、靜止阻塞。6、進(jìn)程的控制，就是對(duì)系統(tǒng)中所有進(jìn)程從創(chuàng)建到消亡的全過(guò)程實(shí)施有效的控制。操作系統(tǒng)的內(nèi)核為系統(tǒng)實(shí)現(xiàn)進(jìn)程控制和存儲(chǔ)管理提供了有效的控制機(jī)制。大多數(shù)操作系統(tǒng)內(nèi)核均包含支撐功能和資源管理功能。支撐功能：中斷處理、時(shí)鐘管理、原語(yǔ)操作。原語(yǔ)是由若干條機(jī)器指令構(gòu)成的，用于完成特定功能的一段程序。內(nèi)核在執(zhí)行某些基本操作時(shí)往往是通過(guò)原語(yǔ)操作實(shí)現(xiàn)的。原語(yǔ)在執(zhí)行過(guò)程中不可分割。內(nèi)核中包含的原語(yǔ)有進(jìn)程控制、進(jìn)程通信、資源管理等。資源管理功能：進(jìn)程管理、存儲(chǔ)器管理、設(shè)備管理。7、進(jìn)程間通信進(jìn)程間的同步：一般來(lái)說(shuō)，一個(gè)進(jìn)程相對(duì)于另一個(gè)進(jìn)程的運(yùn)行速度是不確定的，即進(jìn)程是在異步環(huán)境下運(yùn)行。每個(gè)進(jìn)程都以各自獨(dú)立的不可預(yù)知的速度向前推進(jìn)，但相互合作的進(jìn)程需要在某些確定點(diǎn)上協(xié)調(diào)它們的工作，當(dāng)一個(gè)進(jìn)程到達(dá)了這些點(diǎn)后，除非另一進(jìn)程已完成了某些操作，否則就不得不停下來(lái)等等這些操作結(jié)束。進(jìn)程間的互斥：在多道程序系統(tǒng)中，各進(jìn)程可以共享各類資源，但有些資源一次只能供一個(gè)進(jìn)程使用，稱為臨界資源（critial

resource）。同步是進(jìn)程間的直接制約問(wèn)題，互斥是進(jìn)程間的間接制約問(wèn)題。臨界區(qū)（critial

section）是對(duì)臨界資源實(shí)施操作的那段程序?；コ馀R界區(qū)管理的原則為：有空即進(jìn)、無(wú)空則等、有限等待、讓權(quán)等待。8、整形信號(hào)量與PV操作整形信號(hào)量是一個(gè)整形變量，根據(jù)控制對(duì)象的不同賦不同的值。信號(hào)量分為兩類：公用信號(hào)量：實(shí)現(xiàn)進(jìn)程間的互斥，每個(gè)相關(guān)進(jìn)程即可對(duì)它施行P操作也可以進(jìn)行V操作，初值為1或資源的數(shù)目。私用信號(hào)量：實(shí)現(xiàn)進(jìn)程間的同步，只有一個(gè)進(jìn)程可以對(duì)它施行P操作，其它進(jìn)程只能做V操作，初值為0或某個(gè)正整數(shù)。信號(hào)量S的物理意義：S>=0表示某資源的可用數(shù)，S<0則其絕對(duì)值表示阻塞隊(duì)列中等待該資源的進(jìn)程數(shù)。PV操作是實(shí)現(xiàn)進(jìn)程同步與互斥的常用方法。PV操作是低級(jí)通信原語(yǔ)，其中P操作表示申請(qǐng)一個(gè)資源，V操作表示釋放一個(gè)資源。P操作定義：S:=S-1,若S>=0,則執(zhí)行P操作的進(jìn)程繼續(xù)執(zhí)行；否則若S<0,則該進(jìn)程為阻塞狀態(tài)，并將其插入阻塞隊(duì)列。V操作定義：S:=S+1,若S>0,則執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行；否則，若S<=0，則從阻塞狀態(tài)喚醒一個(gè)進(jìn)程，并將其插入就緒隊(duì)列，執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行。利用PV操作實(shí)現(xiàn)進(jìn)程的互斥：令信號(hào)量mutex的初值為1,當(dāng)進(jìn)入臨界區(qū)時(shí)執(zhí)行P操作，臨界區(qū)時(shí)執(zhí)行V操作。P（mutex）臨界區(qū)V（mutex）怎樣利用PV操作實(shí)現(xiàn)進(jìn)程的同步：可用一個(gè)信號(hào)量與消息聯(lián)系起來(lái)，當(dāng)信號(hào)量的值為0時(shí)表示希望的消息未產(chǎn)生，當(dāng)信號(hào)量的值為非0時(shí)表示希望的消息已經(jīng)存在。假定用信號(hào)量S表示某條消息，進(jìn)程可以通過(guò)調(diào)用P操作測(cè)試消息是否到達(dá)，調(diào)用V操作通知消息已準(zhǔn)備好。最典型的是單緩沖區(qū)的生產(chǎn)者和消費(fèi)者的同步問(wèn)題。如果采用PV操作來(lái)實(shí)現(xiàn)進(jìn)程PA和進(jìn)程PB間的管道通信，并且保證這兩個(gè)進(jìn)程并發(fā)執(zhí)行的正確性，則至少需要2個(gè)信號(hào)量，信號(hào)量的初值分別為0、1。9、高級(jí)通信原語(yǔ)，因?yàn)镻V操作不足以描述復(fù)雜的進(jìn)程間的信息交換，所以引入高級(jí)通信原語(yǔ)。高級(jí)通信原語(yǔ)有這么幾種：共享存儲(chǔ)系統(tǒng)、消息傳遞系統(tǒng)、管道通信。進(jìn)程通信有直接和間接兩種方式。間接方式是以信箱以為媒介。10、管程（monitor）：另一種同步機(jī)制，采用資源集中管理的方法，將系統(tǒng)中的資源用某種數(shù)據(jù)結(jié)構(gòu)抽象地表示出來(lái)。由于臨界區(qū)是訪問(wèn)共享資源的代碼段，因而建立一個(gè)管程來(lái)管理進(jìn)程提出的訪問(wèn)請(qǐng)求。采用這種方式對(duì)共享資源的管理就可以借助數(shù)據(jù)結(jié)構(gòu)及在其上實(shí)施操作的若干過(guò)程來(lái)進(jìn)行。對(duì)共享資源的申請(qǐng)和釋放可以通過(guò)過(guò)程在數(shù)據(jù)結(jié)構(gòu)上的操作來(lái)實(shí)現(xiàn)。11、進(jìn)程調(diào)度，在某些系統(tǒng)中一個(gè)作業(yè)從提交到完成需要經(jīng)歷高、中、低三級(jí)的調(diào)度。高級(jí)調(diào)度（又稱長(zhǎng)調(diào)度、作業(yè)調(diào)度或接納調(diào)度），它決定輸入池中的哪個(gè)后備作業(yè)可以調(diào)入主系統(tǒng)做好運(yùn)行的準(zhǔn)備，成為一個(gè)或一組就緒進(jìn)程。中級(jí)調(diào)度（又稱對(duì)換調(diào)度），它決定處于交換區(qū)中的哪個(gè)就緒進(jìn)程可以調(diào)入主存，以便直接參與CPU的競(jìng)爭(zhēng)。低級(jí)調(diào)度（又稱進(jìn)程調(diào)度），它決定處于主存中的哪個(gè)進(jìn)程使用CPU.調(diào)度方式，是指當(dāng)有更高優(yōu)先級(jí)的進(jìn)程來(lái)到時(shí)如何分配CPU.調(diào)度的方式分為可剝奪式和不可剝奪式兩種。常用的調(diào)度算法：先來(lái)先服務(wù)，主要用于宏觀調(diào)度，有利于長(zhǎng)作業(yè)，有利于CPU繁忙的作業(yè)；時(shí)間片輪轉(zhuǎn)，主要用于微觀調(diào)度，提高了并發(fā)性和響應(yīng)時(shí)間，最終提高了資源利用率；優(yōu)先級(jí)調(diào)度，

分為靜態(tài)和動(dòng)態(tài)兩種；多級(jí)反饋調(diào)度，是在時(shí)間片輪轉(zhuǎn)和優(yōu)先級(jí)算法的基礎(chǔ)上改進(jìn)得到。其特點(diǎn)是：照顧了短進(jìn)程以提高系統(tǒng)吞吐量，照顧I/O型進(jìn)程以獲得較好的I/O設(shè)備利用率并縮短響應(yīng)時(shí)間，不必估計(jì)進(jìn)程的執(zhí)行時(shí)間和動(dòng)態(tài)調(diào)節(jié)優(yōu)先級(jí)。12、死鎖：就是指兩個(gè)以上的進(jìn)程相互請(qǐng)求對(duì)方已經(jīng)占有的資源時(shí)而導(dǎo)致無(wú)法繼續(xù)運(yùn)行下去的現(xiàn)象。幾種會(huì)產(chǎn)生死鎖的情況：進(jìn)程推進(jìn)程順序不當(dāng)，同類資源分配不當(dāng)，PV使用不當(dāng)。進(jìn)程資源有向圖：由方框、圓圈和有向邊3部分組成。其中資源用方框表示，進(jìn)程用圓圈表示。在方框中每一個(gè)小圓圈代表一個(gè)資源。有向邊分別代表請(qǐng)求資源和分配資源。死鎖產(chǎn)生的原因：因?yàn)楦?jìng)爭(zhēng)資源或進(jìn)程推進(jìn)順序非法。進(jìn)程推進(jìn)順序仍是關(guān)于進(jìn)程請(qǐng)求和釋放資源的順序。死鎖產(chǎn)生的4個(gè)必要條件：互斥條件、請(qǐng)求保持條件、不可剝奪條件、環(huán)路條件?；コ馐钦f(shuō)進(jìn)程對(duì)所要求的資源有排它性控制。請(qǐng)求保持是說(shuō)進(jìn)程斷續(xù)地請(qǐng)求資源，但后續(xù)的資源被阻塞。環(huán)路是指在發(fā)生死鎖時(shí)在進(jìn)程資源有向圖中，每個(gè)進(jìn)程都占有了下一個(gè)進(jìn)程請(qǐng)求的一個(gè)或多個(gè)資源。死鎖的4種處理：鴕鳥(niǎo)策略。預(yù)防策略，即破壞死鎖產(chǎn)生的4個(gè)必要條件之一。避免策略，即精心分配資源，主動(dòng)回避死鎖。檢測(cè)與解除死鎖13、線程傳統(tǒng)的進(jìn)程有兩個(gè)基本屬性，即可擁有資源的獨(dú)立單位，和可獨(dú)立調(diào)度、分配的基本單位。引入線程后，將傳統(tǒng)進(jìn)程的兩個(gè)屬性分開(kāi)，線程作為可獨(dú)立調(diào)度和