數據庫系統(tǒng)工程師考點知識精講

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

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

是不具備容錯能力的陣列，N個磁盤組成的0級陣列，其平均故障時間間隔是單個磁盤存儲器的N分之一；但其數據傳輸速率是單的N倍。raid1

使用鏡像容錯技術raid2

使用漢明碼容錯技術raid3

一般使用一個檢驗盤raid4

只使用一個檢驗盤raid5

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

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

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

方法：與一個各位都為零的數值相與，結果為零。取一個數x中某些指定位。

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

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

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

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

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

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

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

|firstchild|data|nextbrother|

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

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

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

i=1,2,,k

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

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

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

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

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

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