計算機信息系統(tǒng)災難恢復計劃(完整版)資料

計算機信息系統(tǒng)災難恢復計劃（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

計算機信息系統(tǒng)災難恢復計劃（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）災難恢復計劃TOC\o"1-2"\h\z版本歷史記錄 31．簡介 41.1計劃的使用 41.2災難定義 41.3概述 41.4原則 42．恢復策略 52.1自然災難（包括：火、地震等等） 52.2硬件故障 52.3軟件故障 52.4病毒 63．職責 63.1災難恢復小組成員 63.2公司員工在災難恢復時的職責 64．信息系統(tǒng)詳細內(nèi)容及設備列表 74.1網(wǎng)關、防火墻服務器 74.2域服務系統(tǒng) 74.3文件服務器系統(tǒng) 74.郵件、防病毒系統(tǒng) 85.QADlinux系統(tǒng) 86QADwindows系統(tǒng) 97備份系統(tǒng) 94.9網(wǎng)絡服務設備列表 95．備份 105.1系統(tǒng)配置備份 105.2數(shù)據(jù)資料備份 105.3備份步驟 106．災難恢復內(nèi)容及順序 116.1主要恢復內(nèi)容 116.2主要軟件及系統(tǒng)恢復步驟 116.3恢復備份數(shù)據(jù)的條件： 126.4恢復時間及順序 127．主要硬件及軟件供應商聯(lián)系方式 138．風險分析 148.1風險等級： 148.2風險分析列表： 148.3風險評價 168.4降低風險的發(fā)生 179．培訓 191．簡介1.1計劃的使用計算機信息系統(tǒng)發(fā)生災難時激活這個計劃，由IT小組按照本計劃標準的操作程序組織實施災難恢復，直到全部數(shù)據(jù)和功能被修復。1.2災難定義災難包括自然災難和人為災難，自然災難是指由不可抗力造成的網(wǎng)絡癱瘓、信息服務被強制中斷，這種災難是不可預測的。人為災難是指除自然災難以外的信息系統(tǒng)的全部或部分出現(xiàn)癱瘓、信息服務被強制中斷。1.3概述災難恢復計劃是做準備、定計劃，以使災難發(fā)生后能及時恢復計算機網(wǎng)絡系統(tǒng)的文件。它是一個管理公司潛在的數(shù)據(jù)丟失及災難發(fā)生時執(zhí)行的計劃，它的主要目的是保護公司數(shù)據(jù)和信息資源，現(xiàn)在公司越來越多的應用了計算機及通信資源，當災難發(fā)生時，這些資源的損失可能會使公司陷入癱瘓狀態(tài)，它會在一段時間內(nèi)直接或間接的影響到公司的運營狀況，給公司造成損失。制定災難恢復計劃，可以使災難被有計劃、有步驟的得到恢復。1.4原則災難恢復計劃文件是準備進行災難恢復及測試計劃有效性的文件，它必須能保證在災難發(fā)生前、中、后都能使災難在最短的時間內(nèi)被恢復，它的詳細內(nèi)容是根據(jù)可能對公司網(wǎng)絡通訊、計算機及數(shù)據(jù)資源造成損失的事件，做出實際、完整的響應步驟，使得災難發(fā)生后能做到：保證將災難的影響降低到最小的程度。在預定的時間內(nèi)恢復網(wǎng)絡系統(tǒng)和數(shù)據(jù)資源。災難恢復計劃必須包括：網(wǎng)絡系統(tǒng)內(nèi)容的詳細列表。軟件及硬件故障的應急響應方法。員工職責。根據(jù)公司對網(wǎng)絡和數(shù)據(jù)資源的要求定期做備份。網(wǎng)絡和數(shù)據(jù)資源的恢復順序。和相關人員及提供服務人員進行通信的方法。風險評估及分析進行災難恢復計劃的維護和測試。將災難恢復計劃形成文件，并保證實時更新。保證每年對災難恢復計劃進行測試。2．恢復策略2.1自然災難（包括：火、地震等等）在發(fā)生自然災難后，公司全體員工在保證人身安全的情況下做出緊急響應，應首先將本部門計算機轉移到安全地點，在條件許可的情況下，盡力將計算機網(wǎng)絡設備及附屬設備（如打印機服務器、HUB等）轉移到安全地點，然后等待災難恢復小組進行修復。2.2硬件故障使用硬件設備的人員及時通知IT工程師，由IT工程師確定發(fā)生故障的原因，如有備件應及時更換，否則應立即與銷售商聯(lián)系，維修或更換設備。2.3軟件故障使用軟件的人員及時通知IT工程師，由IT工程師確定發(fā)生故障的原因，如果是一般應用軟件故障，則應立即重新安裝應用軟件。其它應用軟件故障（如QAD）應立即與軟件供應商聯(lián)系，通過支持或要求供應商上門服務的方式解決軟件故障。操作系統(tǒng)故障應先備份數(shù)據(jù)信息，然后由IT工程師重新安裝操作系統(tǒng)。2.4病毒每位員工發(fā)現(xiàn)病毒后應立即將感染病毒的計算機與計算機網(wǎng)絡斷開，并通知IT工程師清除病毒。3．職責3.1災難恢復小組成員3.2公司員工在災難恢復時的職責發(fā)生自然災難后依據(jù)人力資源部《SP-EHS-02應急準備與響應程序》執(zhí)行，計算機網(wǎng)絡系統(tǒng)的災難由IT人員報行政人事部，由行政人事部對內(nèi)、外宣布災難。發(fā)生災難后，公司辦公樓無法使用時，由公司管理層和行政人事部門負責租用新的辦公地點。公司全體員工都有在發(fā)生災難時做出緊急響應的責任。3.2.4IT小組和管理層一起制定一個詳細、完整的恢復計算機網(wǎng)絡系統(tǒng)的計劃。3.2.5IT工程師定期進行網(wǎng)絡系統(tǒng)信息和數(shù)據(jù)資源的多重備份，保證信息資料的完整性和可靠性。3.2.6IT小組對網(wǎng)絡系統(tǒng)內(nèi)部失效的部件（包括硬件和軟件），及時進行維修和維護。災難發(fā)生后，災難恢復小組成員協(xié)同工作，共同完成信息網(wǎng)絡的搭建及操作系統(tǒng)、應用系統(tǒng)的安裝。完成計算機網(wǎng)絡信息數(shù)據(jù)的恢復工作。4．信息系統(tǒng)詳細內(nèi)容及設備列表4.1網(wǎng)關、防火墻服務器計算機名稱：gateway軟件：Windows2003server操作系統(tǒng)MicrosoftISAServer2006中文標準版硬件：IBMX3250（IT機房）XeonX31104*1G內(nèi)存2*146GSASHDD硬盤2*1000Mb網(wǎng)絡適配器4.2域服務系統(tǒng)計算機名稱：ActiveDirectory軟件：Windows2003server操作系統(tǒng)硬件：DELL320(IT機房)酷睿雙核2.0G1G內(nèi)存160G硬盤10/100Mb網(wǎng)絡適配器4.3文件服務器系統(tǒng)計算機名稱：file-server軟件：Windows2003server操作系統(tǒng)硬件：IBMX3550(IT機房)至強四核5150/2G/500G*2/RAID1/2G內(nèi)存500G*2硬盤1000Mb網(wǎng)絡適配器4.郵件、防病毒系統(tǒng)計算機名稱：mail-server軟件：Windows2003server操作系統(tǒng)VisNeticMailServerSymantec11企業(yè)網(wǎng)絡版硬件：DELL840雙核至強2.13G2G內(nèi)存500G*2硬盤1000Mb網(wǎng)絡適配器5.QADlinux系統(tǒng)計算機名稱：qad-batabase軟件：redhatlinux操作系統(tǒng)硬件：IBMX3650XeonX54502G*4內(nèi)存146G*4SAS硬盤1000Mb網(wǎng)絡適配器6QADwindows系統(tǒng)計算機名稱：qad-app軟件：Windows2003server操作系統(tǒng)硬件：IBMX3650XeonX54502G*4內(nèi)存146G*2SAS硬盤1000Mb網(wǎng)絡適配器7備份系統(tǒng)軟件：Windows2003系統(tǒng)中的備份硬件：BMLTO2400-800G磁帶機4.9網(wǎng)絡服務設備列表華為3COMS3600-28TP-SI交換機(IT機房)華為3COMS1050T交換機兩臺（IT機房）光纖收發(fā)器四臺（IT機房）華為3COMS1008A交換機（廠房南邊機柜）華為3COMS1008A交換機（廠房北邊機柜）光纖收發(fā)器一臺（廠房南邊機柜）光纖收發(fā)器一臺（廠房北邊機柜）光纖收發(fā)器一臺（北門門衛(wèi)室）光纖收發(fā)器一臺（功能實驗室）NETGEAR無線路由兩臺（辦公樓二樓）TP-LinkR403M路由器（IT機房）5．備份5.1系統(tǒng)配置備份網(wǎng)關服務器IP策略、DHCP策略、ISA防火墻策略、域服務器策略由磁帶機和硬盤做兩份備份，其中一份存于服務器硬盤，另一份存于遠離計算機中心的交通銀行開發(fā)區(qū)支行的保險柜內(nèi)。當硬盤損壞時可由磁帶機或其它硬盤中恢復系統(tǒng)最新狀態(tài)。5.2數(shù)據(jù)資料備份文件服務器中的所有存放文件及QAD每天的生產(chǎn)數(shù)據(jù)庫由磁帶備份和硬盤備份兩份，其中一份存于服務器硬盤，另一份存于遠離計算機中心的交通銀行開發(fā)區(qū)支行的保險柜內(nèi)。5.3備份步驟在兩臺服務器中每周進行相關系統(tǒng)配置的備份，并用U盤將所有文件COPY到fileserver機器中d:\中，等待進行磁帶備份。批處理程序(qad-database機器中)每天會將QAD系統(tǒng)中的生產(chǎn)數(shù)據(jù)庫備份到/backup/db/prod/文件夾中，IT工程師每天早晨上班后在fileserver機器中用FTP軟件COPYqad-database機器的/backup/db/prod/中的所有文件到fileserver機器的D:/QADProductionbackup目錄中，再用磁帶對此目錄進行備份；Fileserver機器中的D盤每周用磁帶全備份一次，每月完全備份一次。每天\每周使用磁帶備份，將磁帶放入磁帶機中，對公司內(nèi)所有數(shù)據(jù)進行全備份（QAD數(shù)據(jù)庫文件每天備份），每月進行一次完全備份。6．災難恢復內(nèi)容及順序6.1主要恢復內(nèi)容文件服務器(Windows2003server)備份系統(tǒng)網(wǎng)關服務器(Windows2003server)網(wǎng)絡防火墻(ISA2006)域服務器(Windows2003server)電子郵件系統(tǒng)(VisNeticMailServer)病毒防護系統(tǒng)(SymantecNortonAntivirus)qad-database系統(tǒng)qad-app系統(tǒng)6.2主要軟件及系統(tǒng)恢復步驟根據(jù)Windows2003server安裝時的提示，進行一步一步的安裝，安裝后使用備份好的”系統(tǒng)配置”文件恢復系統(tǒng)配置信息及安全策略。各系統(tǒng)的配置文件如下：網(wǎng)關服務器：\\file-server\D:\gatewaybackup\DHCP域服務器：\\file-server\D:\ADbackup根據(jù)Linux和Windows2003server安裝時的提示，進行一步一步的安裝。包括“ISA2006”、“Visneticmailserver”、“Symantec”、“QAD軟件”都根據(jù)軟件的安裝提示進行安裝，安裝后使用備份好的各系統(tǒng)配置文件恢復系統(tǒng)配置。以下為各軟件配置文件的保存路徑：ISA2006：\\file-server\D:\gatewaybackup\ISAQAD正式數(shù)據(jù)庫：\\file-server\D:\QADProductionbackup6.3恢復備份數(shù)據(jù)的條件：具備計算機一臺，具有Windows2003server操作系統(tǒng)。IBMLTO3磁帶機一臺。6.4恢復時間及順序總恢復時間網(wǎng)關服務器郵件服務器文件服務器域服務器QAD系統(tǒng)順序時間順序時間順序時間順序時間順序時間0-24Windows2003server操作系統(tǒng)0-24Windows2003server操作系統(tǒng)0-24Windows2003server操作系統(tǒng)0-24Windows2003server操作系統(tǒng)0-24Linuxwindows0-2424-124124小時后可全部恢復網(wǎng)絡內(nèi)的服務器系統(tǒng)網(wǎng)絡防火墻24-28電子郵件系統(tǒng)24-28文件資料數(shù)據(jù)24-48域策略配置24-48QAD軟件24-100恢復系統(tǒng)策略配置28-30病毒防護系統(tǒng)28-32備份系統(tǒng)48-52QAD數(shù)據(jù)庫數(shù)據(jù)100-124恢復防火墻數(shù)據(jù)28-50恢復系統(tǒng)配置32-40網(wǎng)絡布局和各單機系統(tǒng)視緩急程度決定恢復順序及時間7．主要硬件及軟件供應商聯(lián)系方式主要硬件名稱公司名稱聯(lián)系人聯(lián)系IBM磁帶機、服務器IBM中國DELL服務器DELL中國QADSE2021軟件上海企安達MicrosoftISAServer2006Microsoft中國公司8．風險分析風險是指對計算機網(wǎng)絡系統(tǒng)潛在的威脅，風險評估是分析和評估可能發(fā)生的全部風險。它包括風險等級、風險分析、風險評價三部分。8.1風險等級：通過對潛在的風險進行分析，確定風險發(fā)生的可能性（高、中、低、），以及風險發(fā)生后可能造成的威脅（高、中、低）。通過對兩者的分析來確定風險的等級。見下表：風險等級發(fā)生風險的可能性造成威脅的高低等級HMLN/AHMLN/AXX*****XX****XX****XX***XX**XX*XX**XX*XX-8.2風險分析列表：下表中所包含的風險依據(jù)以下信息：中國統(tǒng)計局美國大使館中國平安保險公司中國2004年災難報告中國2004年統(tǒng)計報告風險分析表潛在的風險發(fā)生風險的可能性造成威脅的高低等級HMLN/AHMLN/A地震xx**颶風xx-暴風雨xx-火山爆發(fā)xx-洪水/山洪暴發(fā)xx***暴風雪xx-泥石流xx-雷擊xx***海嘯xx-森林火災xx-干旱xx-建筑物失火/爆炸/漏氣xx****水管破裂xx**氣候條件惡劣（如：溫度過高）xx*網(wǎng)絡設備故障xx**硬件故障xx***軟件故障xx-媒體故障（磁帶、光驅(qū)等）xx*人為的操作失誤xx-黑客的陰謀破壞xx*數(shù)據(jù)無法打開xx-機密數(shù)據(jù)泄露xx****未被授權的訪問xx*個人丟失鑰匙xx*害蟲侵擾(物理設備)xx-感染計算機病毒xx****電磁影響xx***干擾特性xx-通訊故障xx-油管斷裂xx-搶掠xx*入室行竊/非法挪用xx*戰(zhàn)爭xx*8.3風險評價根據(jù)上表所列出的各種風險類型進行分析，綜合考慮各方面的因素，列出下表，有四種基本的控制方法，每種方法可以單獨使用，也可以共同使用。風險“A.T.E.R”定義控制方法接受(Accept)當控制風險的成本明顯高于財務成本時，接受可能發(fā)生的風險如果從成本角度考慮，對可能發(fā)生的風險可以不做控制。轉移(Transfer)把財務責任轉移到第三方購買保險;消除(Eliminate)完全去除可能導致災難或網(wǎng)絡中斷的因素重新部署設施;改變程序文件;清除易燃材料等降低(Reduce)把可能導致災難或網(wǎng)絡中斷的因素最小化安將防盜門、建立防火墻;安裝病毒防護系統(tǒng);進行多重備份;認真考慮風險和實施成本，實行有效緩解措施，可以避免小問題逐漸升級成大災難。下表中每項風險的評估（風險分析摘要）在下表作了概述。風險按優(yōu)先順序列出，其中包括風險管理和應對策略：風險評價（\）潛在的風險風險等級風險管理策略適用范圍建筑物失火/爆炸/氣體泄漏****ARTSLWH機密數(shù)據(jù)泄露****RSLWH感染計算機病毒****RSLWH硬件故障***ARSLWH電磁干擾***RSLWH洪水/山洪暴發(fā)***ARTSLWH雷擊***ARTSLWH地震**ARTSLWH水管破裂**ARESLWH網(wǎng)絡設備故障**ARESLWH氣候條件惡劣（如：溫度過高）*RESLWH媒體故障（磁帶、光驅(qū)等）*RESLWH搶掠*RTSLWH入室行竊/非法挪用*RESLWH戰(zhàn)爭*ARSLWH黑客的陰謀破壞*RESLWH未被授權的訪問*RESLWH個人丟失鑰匙*RESLWH8.4降低風險的發(fā)生:所有公司的財產(chǎn)都在保險公司投保，在財產(chǎn)被盜或遇到災難時，不會在財務上發(fā)生困難:機房24小時關門關閉并鎖上窗戶在IT機房放置滅火器進出機房必須添寫登記表，并有計算機管理人員陪同保持房間清潔:為每一盤磁帶標記序號，并標記備份日期及形式備份磁帶定期放到遠離IT機房的交通銀行開發(fā)區(qū)支行對備份磁帶定期做測試:網(wǎng)絡用戶密碼的長度必須大于7位，并符合復雜性要求（包含數(shù)字、字母、符號）用戶必須每30天更改一次密碼，一年內(nèi)密碼不能重復網(wǎng)絡用戶應定期清理，刪除不再使用的用戶名:公司內(nèi)所有計算機都必須設置開機口令和屏幕保護口令所有的屏幕保護口令必須設置在10分鐘以內(nèi)對一些機密文件也應該設置保護口令將公司內(nèi)重要數(shù)據(jù)保存在服務器上，防止丟失:每個月抽查每個部門的計算機，檢查是否有非法軟件，如果發(fā)現(xiàn)非法軟件應當立即將其刪除9．培訓災難恢復小組成員每年進行一次培訓。培訓內(nèi)容為最新的”災難恢復計劃”。第一章計算機基礎知識 2第一節(jié)數(shù)制及其轉換 2第二節(jié)算術運算和邏輯運算 3第三節(jié)原碼、反碼和補碼 5第四節(jié)浮點數(shù)的表示方法 6第五節(jié)奇偶校驗 7第六節(jié)ASCII碼表 8第二章計算機硬件基礎 9第一節(jié)中央處理器 9第二節(jié)存儲器系統(tǒng) 10第三節(jié)輸入輸出系統(tǒng) 11第三章網(wǎng)絡基礎知識 12第一節(jié)網(wǎng)絡的組成與結構 12第二節(jié)網(wǎng)絡協(xié)議 13第三節(jié)Internet相關知識 13第三節(jié)Internet相關知識 14第四章其他相關基礎知識 15第一節(jié)計算機病毒 15第二節(jié)數(shù)據(jù)庫系統(tǒng) 15第五章數(shù)據(jù)結構之線性結構 16第一節(jié)線性表 16第二節(jié)棧 17第三節(jié)隊列 18第六章數(shù)據(jù)結構之非線性結構 19第一節(jié)樹的概念 19第二節(jié)樹的表示方法和存儲結構 20第三節(jié)二叉樹的概念 22第四節(jié)二叉樹的遍歷 24第五節(jié)普通樹的遍歷 27第六節(jié)根據(jù)兩種遍歷順序確定樹結構 28第七節(jié)二叉排序樹 29第八節(jié)最優(yōu)二叉樹(哈夫曼樹) 30AOE網(wǎng) 32

第一章計算機基礎知識第一節(jié)數(shù)制及其轉換一、二、八、十六進制轉十進制的方法：乘權相加法。例如：（11010110）2=1×27+1×26+0×25+1×24+0×23+1×22+1×21+0×20=（214）10（2365）8=2×83+3×82+6×81+5×80=（1269）10（4BF）16=4×162+11×161+15×160=(1215)10帶小數(shù)的情況：（110.011）2=1×22+1×21+1×20+0×2-1+1×2-2+1×2-3=（6.375）10（5.76）8=5×80+7×8-1+6×8-2=（5.96875）10（D.1C）16=13×160+1×16-1+12*16-2=（13.109375）10二、十進制化二進制的方法：整數(shù)部分除二取余法，小數(shù)部分乘二取整法。例一：（43）10=（101011）2例二：（0.375）10=（0.011）2三、二進制轉八進制的方法一位數(shù)八進制與二進制對應表八進制二進制轉換方法:對二進制以小數(shù)點為分隔，往前往后每三位劃為一組，不足三位補0，按上表用對應的八進制數(shù)字代入即可。例如：(10111011.01100111)=010,111,011.011,001,110=（273.36）800001001201030114100510161107111三、二進制轉十六進制的方法一位數(shù)十六進制與二進制對應表十六進制二進制轉換方法:對二進制以小數(shù)點為分隔，往前往后每四位劃為一組，不足四位補0，按上表用對應的十六進制數(shù)字代入即可。例如：(10111011.01100111)=1011,1011.0110,0111=（BB.67）1600000100012001030011401005010160110701118100091001A1010B1011C1100D1101E1110F1111四、進制的英文表示法：以上都是用括號加數(shù)字的表示方法，另外還有英文表示法，就是以BIN、OCT、HEX、DEC分別代表二、八、十六、十進制。或者只寫第一個字母。例如1101B表示是二進制。有些地方為了避免“O”跟“0”混淆，把O寫成Q。第二節(jié)算術運算和邏輯運算一、二進制的算術運算1、加法運算規(guī)則：

0+0=0

0+1=1

1+0=11+1=102、減法運算規(guī)則：

0-0=0

0-1=1（向高位借1）1-0=11-1=03、乘法運算規(guī)則：

0×0=0

0×1=0

1×0=0

1×1=1二、邏輯運算1、基本運算

①邏輯乘，也稱“與”運算，運算符為“·”或“∧”

0·0=0

0·1=0

1·0=0

1·1=1

使用邏輯變量時，A·B可以寫成AB

②邏輯加，也乘“或”運算，運算符為“+”或“∨”

0+0=0

0+1=1

1+0=11+1=1

③邏輯非，也稱“反”運算，運算符是在邏輯值或變量符號上加“—”=1

=02、常用運算

異或運算：A⊕B=A·＋·B2、基本公式

①0，1律

A·0=0

A·1=A

A＋0=A

A＋1=1

②交換律

A＋B=B＋A

A·B=B·A

③結合律

A＋B＋C=（A＋B）＋C=A＋（B＋C）

A·B·C=（A·B）·C=A·（B·C）

④分配律

A·（B＋C）=A·B＋A·C

⑤重疊律

A＋A＋...＋A=A

A·A·...·A=A

⑥互補律

A+=1

A·=0

⑦吸收律

A＋A·B=A

A·（A＋B）=A

A＋·B=A＋B

A·（＋B）=A·B

⑧對合律

對一個邏輯變量兩次取反仍是它本身

⑨德·摩根定理

=·

=+三、邏輯代數(shù)的應用1、邏輯表達式化簡

例如：F=·＋A·＋A·B

=·＋A（＋B）

（利用分配律）

=·＋A

（利用互補律以及0，1律）

=A＋

（利用吸收律）2、對指定位進行運算，假設變量A有八位，內(nèi)容是d7d6d5d4d3d2d1d0

①將變量A的d5位清零

A·（11011111）→A

②將變量A的各位置1

A＋（11111111）→A

第三節(jié)原碼、反碼和補碼

計算機中參與運算的數(shù)有正負之分，計算機中的數(shù)的正負號也是用二進制表示的。用二進制數(shù)表示符號的數(shù)稱為機器碼。常用的機器碼有原碼、反碼和補碼。一、原碼求原碼的方法：設X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位照抄?！纠?】X=+1001001

[X]原=0【例2】X=-1001001

[X]原=11001001二、反碼求反碼的方法：設X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位按位取反?！纠?】X=+1001001

[X]反=0【例4】X=-1001001

[X]反=三、補碼求補碼的方法：設X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位按位取反后，最低位加1?！纠?】X=+1001001

[X]補=0【例6】X=-1001001

[X]補=四、補碼加減法

計算機中實際上只有加法，減法運算轉換成加法運算進行，乘法運算轉換成加法運算進行，除法運算轉換成減法運算進行。用補碼可以很方便的進行這種運算。1、補碼加法

[X+Y]補=[X]補+[Y]補【例7】X=+0110011,Y=-0101001，求[X+Y]補

[X]補=00110011

[Y]補=11010111

[X+Y]補=[X]補+[Y]補=00110011+11010111=00001010

注：因為計算機中運算器的位長是固定的，上述運算中產(chǎn)生的最高位進位將丟掉，所以結果不是

100001010，而是00001010。2、補碼減法

[X-Y]補=[X]補-[Y]補=[X]補+[-Y]補

其中[-Y]補稱為負補，求負補的方法是：對補碼的每一位（包括符號位）求反，最后末位加“1”?！纠?】X=+0111001,Y=+1001101，求[X-Y]補

[X]補=00111001

[Y]補=01001101

[-Y]補=

[X-Y]補=[X]補+[-Y]補=00111001+10110011=11101100五、數(shù)的表示范圍

通過上面的學習，我們就可以知道計算機如果用一個字節(jié)表示一個整數(shù)的時候，如果是無符號數(shù)，可以表示0~255共256個數(shù)（00000000~11111111），如果是有符號數(shù)則能表示-128~127共256個數(shù)（10000000~01111111）。如果兩個字節(jié)表示一個整數(shù)，則共有65536個數(shù)可以表示，大部分程序設計語言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(shù)，而且是補碼表示的。第四節(jié)浮點數(shù)的表示方法一、浮點數(shù)表示

一個數(shù)的浮點形式（設基數(shù)是2）可寫成：

N=M×2E

其中:M代表尾數(shù),E代表階碼。

計算機中浮點數(shù)只用尾數(shù)和階碼表示，其形式如下：

階碼尾數(shù)符號尾數(shù)

浮點數(shù)的精度由尾數(shù)決定，數(shù)的表示范圍由階碼的位數(shù)決定。

為了最大限度提高精度，尾數(shù)采用規(guī)格化形式，既1/2≤M<1。采用二進制表示時，若尾數(shù)大于零，則規(guī)格化數(shù)應該是01XXXX的形式；若尾數(shù)小于零，則規(guī)格化數(shù)應為10XXXX的形式。二、機器零

當浮點數(shù)的尾數(shù)為0或階碼為最小值時，計算機通常把該數(shù)當作零，因此程序中進行浮點運算時，判斷某數(shù)是否為零，通?？梢杂眯∮谀硞€極小值來代替。三、實例【例1】設X=0.0110×23,用補碼、浮點數(shù)形式表示階碼為Xj=011，尾數(shù)為00110，這時由于X尾數(shù)不符合01XXXX的形式，因此不是規(guī)格化數(shù)，必須先進行規(guī)格化處理。方法：若尾數(shù)小于1/2，把尾數(shù)左移一位（不包括符號位），觀察結果是否滿足規(guī)格化條件，滿足則在把階碼減1即可，否則繼續(xù)左移和調(diào)整階碼；若尾數(shù)大于1，則把尾數(shù)右移一位（不包括符號位），觀察結果是否滿足規(guī)格化條件，滿足則在把階碼加1即可，否則繼續(xù)右移和調(diào)整階碼。上例中，00110左移一位為01100，符合規(guī)則化標準，此時階碼減1，為010即得到浮點表示形式。

這個數(shù)具體在計算機中如何表示要看計算機中規(guī)定的階碼和尾數(shù)的位數(shù)，若階碼和尾數(shù)均為16位，則上面的數(shù)X在計算機內(nèi)部表示就是0001000000，不足均用零填充。

第五節(jié)奇偶校驗

計算機中數(shù)據(jù)在進行存儲和傳輸過程中可能會發(fā)生錯誤。為了及時發(fā)現(xiàn)和糾正這類錯誤，在數(shù)據(jù)傳輸（存儲）過程中要進行校驗，常用的校驗方法就是奇偶校驗。

奇偶校驗能發(fā)現(xiàn)一位或奇數(shù)位錯誤，且不能糾正錯誤。一般以字節(jié)（八位二進制）為單位加1位奇偶校驗位。奇偶校驗分奇校驗和偶校驗兩種。一、奇校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為奇數(shù)，若八位二進制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“1”；若八位二進制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“0”。【例1】給11101加奇校驗結果為1001101101二、偶校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為偶數(shù)，若八位二進制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“0”；若八位二進制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“1”?！纠?】給11101加偶校驗結果為01

第六節(jié)ASCII碼表32

52472H92\112p33!53573I93]113q34”54674J94^114r35#55775K95_115s36$56876L96`116t37%57977M97a117u38&58:78N98b118v39’59;79O99c119w40(60<

80P100d120x41)61=81Q101e121y42*62>

82R102f122z43+63?83S103g123{44,64@84T104h124|45-65A85U105i125}46.66B86V106j126~47/67C87W107k

48068D88X108l

49169E89Y109m

50270F90Z110n

51371G91[111o

目前使用最廣泛的西文字符集及其編碼是ASCII字符集和ASCII碼（ASCII是AmericanStandardCodeforInformationInterchange的縮寫），它同時也被國際標準化組織（InternationalOrganizationforStandardization,ISO）批準為國際標準。

基本的ASCII字符集共有128個字符，其中有96個可打印字符，包括常用的字母、數(shù)字、標點符號等，另外還有32個控制字符。標準ASCII碼使用7個二進位對字符進行編碼，對應的ISO標準為ISO646標準。下表展示了基本ASCII字符集及其編碼：

字母和數(shù)字的ASCII碼的記憶是非常簡單的。我們只要記住了一個字母或數(shù)字的ASCII碼（例如記住A為65，0的ASCII碼為48），知道相應的大小寫字母之間差32，就可以推算出其余字母、數(shù)字的ASCII碼。

雖然標準ASCII碼是7位編碼，但由于計算機基本處理單位為字節(jié)（1byte=8bit），所以一般仍以一個字節(jié)來存放一個ASCII字符。每一個字節(jié)中多余出來的一位（最高位）在計算機內(nèi)部通常保持為0（在數(shù)據(jù)傳輸時可用作奇偶校驗位）。由于標準ASCII字符集字符數(shù)目有限，在實際應用中往往無法滿足要求。為此，國際標準化組織又制定了ISO2022標準，它規(guī)定了在保持與ISO646兼容的前提下將ASCII字符集擴充為8位代碼的統(tǒng)一方法。ISO陸續(xù)制定了一批適用于不同地區(qū)的擴充ASCII字符集，每種擴充ASCII字符集分別可以擴充128個字符，這些擴充字符的編碼均為高位為1的8位代碼（即十進制數(shù)128~255），稱為擴展ASCII碼。下表展示的是最流行的一套擴展ASCII字符集和編碼：第二章計算機硬件基礎第一節(jié)中央處理器一、中央處理器的組成

中央處理器簡稱CPU，由控制器、運算器組成。

運算器及控制器的基本功能：運算器是計算機進行算術和邏輯運算的部件，控制器是整個計算機中統(tǒng)一指揮和控制計算機各部件進行工作的控制中心。二、運算器

運算器是負責對數(shù)據(jù)進行算術運算或邏輯運算的部件。運算器由算術邏輯單元（ALU）、累加器、狀態(tài)寄存器、通用寄存器組等組成。如圖：

算術邏輯運算單元、累加器和通用寄存器的位數(shù)決定了CPU的字長。三、控制器

是計算機的指令執(zhí)行部件，其工作是取指令、解釋指令以及完成指令的執(zhí)行。

控制器由指令指針寄存器、指令寄存器、控制邏輯電路和時鐘控制電路等組成。

指令指針寄存器（IP）用于

產(chǎn)生及存放一條待取指令的地址。

指令寄存器用于存放指令。指令從內(nèi)存取出后放入指令寄存器。四、寄存器

寄存器數(shù)量增多可以提高CPU運行速度，但是不能太多，太多會使地址編碼和指令長度變長，增加復雜度。由累加器、通用寄存器組、狀態(tài)寄存器、指令寄存器、地址寄存器、其他寄存器等組成。五、指令基本格式

單目運算：操作碼地址碼

二目運算：操作碼第一地址第二地址六、尋址方式：CPU執(zhí)行指令時尋找數(shù)據(jù)地址的方式

1、立即尋址：ADDAH,78

其中ADD是操作碼，表示做加法；AH是寄存器名；78是個常數(shù)；該指令的意思是寄存器AH的值加上78。

2、直接尋址：ADDAH,(78)

78表示操作數(shù)的地址

3、間接尋址：ADDAH,((78))

78表示操作數(shù)地址的地址

4、相對尋址：ADDAH,*78

*78表示本指令地址+78，78稱偏移量

5、變址尋址：ADDAH,(DI+78)DI是變址寄存器,存放一個地址,操作數(shù)地址是寄存器地址+78

6、寄存器直接尋址:ADDAH,78

AH是一個寄存器名,即寄存器直接尋址

7、寄存器直接尋址:ADDAH,(BX)

BX是一個寄存器名,存放操作數(shù)的地址七、指令分類

1、數(shù)據(jù)傳送指令：MOVAH,BH

INAH,378

2、數(shù)據(jù)處理指令:算術運算、邏輯運算、移位、比較等

3、程序控制指令：轉移、調(diào)用、返回

4、狀態(tài)管理指令：中斷、屏蔽中斷八、指令的執(zhí)行過程

1、CPU發(fā)出指令地址

2、讀取指令

3、指令送指令寄存器

4、指令譯碼

5、按指令操作碼執(zhí)行

6、形成下條要執(zhí)行的指令的地址九、時鐘周期

一個指令執(zhí)行的時間稱為指令周期

計算機完成一個操作（如讀取指令等）所需時間稱為總線周期

計算機中最基本的時間單位是時鐘周期，有CPU的主頻決定。第二節(jié)存儲器系統(tǒng)一、存儲器的分類分類方法名稱舉例按存儲介質(zhì)分半導體存儲器ROM、RAM（內(nèi)存）、閃存（優(yōu)盤）磁表面存儲器硬盤、軟盤、磁帶光存儲器CD-ROM、DVD-ROM按工作方式分隨機存儲器RAM（內(nèi)存）、硬盤、軟盤只讀存儲器ROM、CD-ROM順序存儲器磁帶二、多層次存儲體系:如圖三、主存儲器

1、特點：容量小、讀寫速度快、價格高

2、編址方式：存儲容量與地址線條數(shù)相對應，64M的存儲器至少需要26跟地址線（226=64M）

注：我們目前的計算機大都是32位，也就是地址線條數(shù)有32條，所以其支持的最大內(nèi)存容量為4G

3、分類：

①隨機存儲器（RAM）：就是我們通常稱的內(nèi)存，主要參數(shù)是存儲容量和工作頻率。

例如：一條64M×8的內(nèi)存條表示該內(nèi)存條有64M個單元，每個單元8位。

②只讀存儲器（ROM）：只能讀不能寫，一般用于存放計算機啟動所需的最基本程序。

③緩沖存儲器（Cache）：速度最快，一般集成于CPU中。四、輔助存儲器

1、磁帶：順序存儲，一般只用在小型機以上的計算機中，用作數(shù)據(jù)備份。

2、軟盤：目前常見的一般為3.5寸高密盤，容量為1.44MB，軟盤結構如圖

注意：盤面最外層的磁道稱為0磁道，0磁道如果損壞，則盤片報廢。

3、硬盤：硬盤由多個盤面組成一個柱形結構，其原來跟軟盤類似，但是磁道更多。

4、光盤：利用光信號讀取或?qū)懭氲拇鎯ζ鳌?/p>

①CD-ROM：只讀，容量650MB左右，一倍速為150KB/s

②DVD-ROM：只讀，容量4.7GB左右，一倍速為1200KB/s

③CD-RW、DVD-RW：可擦寫的光盤，但必須專門的刻錄機。

第三節(jié)輸入輸出系統(tǒng)一、輸入輸出控制方式

1、程序查詢方式：軟件實現(xiàn)，效率低

2、中斷方式：軟硬件結合實現(xiàn)

中斷請求-->中斷響應-->中斷處理-->中斷返回

3、直接存儲器訪問方式（DMA）：硬件實現(xiàn)

DMA請求-->CPU響應并把總線控制權交給DMA控制器-->數(shù)據(jù)交換-->交還總線控制權二、系統(tǒng)總線

分類：數(shù)據(jù)總線、地址總線、控制總線

總線標準：ISA總線、PCI局部總線、MCA總線三、I/O接口

1、顯卡：分辨率、顏色數(shù)決定顯示效果和所需顯存

例如：顯示分辨率為1280×1024的32位真彩色，所需顯卡顯存最少為

1280×1024×32÷8=5MB

2、硬盤接口：

①IDE、EIDE

②UltraDMA

③SCSI

④SATA

3、串行口

4、并行口：通常接針式打印機

5、USB接口：通用串行總線四、顯示器的有關知識

1、屏幕尺寸：15寸、17寸、19寸等

2、點間距：屏幕上象素與象素之間的距離，決定了顯示器能顯示的最大分辨率。越小表示能顯示的最大分辨率越大。五、打印機：針式打印機、噴墨打印機、激光打印機。

激光打印機速度最快，針式打印機可以打印票據(jù)。第三章網(wǎng)絡基礎知識第一節(jié)網(wǎng)絡的組成與結構一、網(wǎng)絡組成

1、通信主體：服務器和工作站

2、通信設備：傳輸介質(zhì)、網(wǎng)絡設備

3、通信協(xié)議：通常是TCP/IP二、網(wǎng)絡分類

按傳輸距離分：局域網(wǎng)（LAN）、城域網(wǎng)（MAN）、廣域網(wǎng)（WAN）

按網(wǎng)絡結構分：總線型、星型、環(huán)型、樹型三、網(wǎng)絡拓撲結構第二節(jié)網(wǎng)絡協(xié)議一、OSI網(wǎng)絡協(xié)議的層次國際標準化組織（ISO）提出的“開放系統(tǒng)互連模型（OSI）”是計算機網(wǎng)絡通信的基本協(xié)議。該協(xié)議分為七層。如下表二、網(wǎng)絡設備極其作用

第三節(jié)Internet相關知識一、IP地址

IP地址分類如下表：目前32位IP地址資源幾近枯竭，有人提出用48位表示IP，即IPV6。分類二進制表示十進制表示第一段數(shù)字A類<128B類128~191C類192~223二、域名：Internet的域名系統(tǒng)叫做DNS，DNS是樹形結構的。域名跟IP地址是多對一的關系

1、域名分級系統(tǒng)：一個域名最右邊的部分通常叫頂級域名，往前依次為二級域名、三級域名等。

2、我國域名管理機構:CNNIC

3、常見域名含義：

gov政府edu教育int國際組織com商業(yè)組織mil軍事部門net網(wǎng)絡運行

org其他組織

cn中國

hk香港

tw臺灣

uk英國jp日本三、一些常見名詞解釋

1、Intranet:企業(yè)內(nèi)部網(wǎng)

2、ISP（InternetServiceProvider）：因特網(wǎng)服務供應商

3、ICP（InternetContentProvider）：因特網(wǎng)內(nèi)容供應商

4、IAP（InternetAcessProvider）：因特網(wǎng)接入供應商，目前一般都被ISP包含

5、BBS：電子公告欄，目前通常叫論壇四、接入Internet的方法

1、PSTN撥號接入：必須設備MODEM，線，速度慢

2、DDN專線接入：速度快，費用高。

3、ISDN專線接入：利用傳統(tǒng)網(wǎng)絡的綜合業(yè)務數(shù)字網(wǎng)。

4、分組交換接入

5、幀中繼接入

第四章其他相關基礎知識第一節(jié)計算機病毒一、特點

寄生性、隱蔽性、非法性、傳染性、破壞性二、分類：

1、引導型病毒：寄生在系統(tǒng)引導區(qū)，比較容易被清除，現(xiàn)在已經(jīng)很少見。

2、文件型病毒：寄生在可執(zhí)行文件中，感染速度快，較易清除。

3、目錄型病毒：寄生在系統(tǒng)目錄結構中

4、混合型病毒：多種類型的混合

5、宏病毒：專門感染MicrosoftOffice系列文件的病毒

6、蠕蟲病毒：感染網(wǎng)絡，使網(wǎng)速大大降低。

目前流行的病毒大多集成了黑客技術、木馬技術和病毒技術三種，非常難以清除而且很容易中。三、一些常見危害較大的病毒

1、CIH病毒:文件型病毒，4月26日發(fā)作時破壞性最大，首個能破壞硬件系統(tǒng)的病毒。

2、Melissa病毒：宏病毒，郵件傳播

3、沖擊波、震蕩波病毒：利用WINDOWS的漏洞，使計算機自動重啟并堵塞網(wǎng)絡。第二節(jié)數(shù)據(jù)庫系統(tǒng)一、數(shù)據(jù)庫是數(shù)據(jù)的一種組織形式，目前存儲大量數(shù)據(jù)基本都采用數(shù)據(jù)庫

常見的數(shù)據(jù)庫軟件有：FoxBase、FoxPro、Access、SqlServer、MySql、Sybase、Oracel等。除了最早的如FoxBase等軟件，目前流行的數(shù)據(jù)庫軟件都是關系型數(shù)據(jù)庫。二、數(shù)據(jù)庫數(shù)據(jù)結構數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)結構可以認為是多張二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖

二、數(shù)據(jù)操作

用以對數(shù)據(jù)庫進行檢索和更新（添加、刪除、更新等）操作

三、數(shù)據(jù)的完整性約束條件

多個表之間的數(shù)據(jù)可能存在相互關聯(lián)，必須保證其完整性四、數(shù)據(jù)庫操作語言SQL

數(shù)據(jù)庫常用的操作語言稱為SQL語言，是一種更高級化的語言，只須告訴計算機做什么事情即可。下面例舉幾條常用的語句。

1、SELECT語句

語法：select<列名>from<表名>where<條件>

功能：從表中選出滿足條件的記錄列

2、INSERT語句

語法：insertinto<表名>[(列名表)]values(<值表>)

功能：在表中插入一條新記錄。

3、DELETE語句

語法：delete*from<表名>where<條件>

功能：刪除滿足條件的記錄

4、UPDATE語句

語法：update<表名>

set<列名>=<值>where<條件>功能：修改滿足條件的表中某記錄某字段的值

第五章數(shù)據(jù)結構之線性結構第一節(jié)線性表一、概念

線性表是指由有限個類型相同的數(shù)據(jù)元素組成的集合，它有以下的特點：

1.有唯一的頭結點(即第一個數(shù)據(jù)元素)和尾結點(即最后一個數(shù)據(jù)元素)；

2.除結點外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；

3.除尾結點外，集合中的每一個數(shù)據(jù)元素均只有一個后繼。二、線性表的存儲結構

1、順序結構：是通過數(shù)組說明分配連續(xù)地址的存儲區(qū)，通過下標引用數(shù)組的相應元素。

2、鏈式結構：通過指引元素類型的變量對線性表中元素進行動態(tài)分配存儲。三、順序存儲結構

1、一維數(shù)組

①數(shù)組存儲的結構在數(shù)組聲明時就需要事先分配相應的連續(xù)內(nèi)存空間用來存放數(shù)據(jù)。

②按首地址（表中第一個元素的地址）的位移來訪問數(shù)組每一個元素的。

若第一個元素的地址是a，每個元素占用的存儲空間為L，則數(shù)組的第i個元素的地址可以用如下公式計算：

d(i)=a+(i-1)*L

2、二維數(shù)組

①定義方法：<數(shù)組名>:array[1..n,1..m]of<元素類型>

②對于行為n，列為m的二維數(shù)組的元素訪問方法：若第一個元素的地址是a，每個元素占用的存儲空間為L，則數(shù)組的第(i,j)個元素的地址可以用如下公式計算：

按行尋址：d(i,j)=a+(i-1)*m*L+(j-1)*L

按列尋址：d(i,j)=a+(j-1)*n*L+(i-1)*L四、鏈式存儲結構

鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù)部分存放結點的有關信息，指針部分存放下一個結點的位置。

優(yōu)點：可根據(jù)需要分配數(shù)據(jù)元素的存儲區(qū)，也可隨時撤消鏈表中數(shù)據(jù)元素的存儲區(qū)，插入刪除操作只須改變指針，無須移動數(shù)據(jù)。

缺點：它的數(shù)據(jù)元素必須在數(shù)據(jù)項以外至少增加一個指向后繼元素的指針類型的數(shù)據(jù)項，查找其中的某個元素時必須中從第一個元素開始逐個往后找。一個實例：Type

pointer=^node;

node=Record;

data:real;

next:pointer;

End;Var

head,next:pointer;

1.Head為表的首指針，指向鏈表的第一個結點。

2.整個鏈表的存取必須從head指針出發(fā)，沿著每個結點的next指針順序進行，最后個結點的next指針為“空”（nil）.第二節(jié)棧一、棧的概念

棧是一種線性表，對它的插入和刪除操作都限制在表的同一端進行。這一端叫做棧頂，另一個端叫做棧底。棧又被成為“后進先出表”（LIFO）。

定義方法：

Const

m=棧元素的上限；

Type

stack=array[1..m]of<元素類型>

Var

s:stack;

t:integer;二、棧的基本運算

1.入棧：過程push(x)，往棧s中壓入一個元素cedurepush(x:<元素類型>);

begin

ift=m

thenwriteln(‘overflow’)

elsebegin

t:=t+1;

s[t]:=x;

end;

end;

2.出棧：函數(shù)pop(x)，從棧s中彈出一個元素。functionpop:<元素類型>;

begin

ift=0

thenwriteln('empty')

elsebegin

pop:=s[t];

t:=t-1;

end;

end;

3.讀棧頂元素：函數(shù)top，讀取棧s的棧頂元素。functiontop:<元素類型>;

begin

ift=0

thenwriteln('empty')

elsetop:=s[t];

end;第三節(jié)隊列一、棧的概念

隊列是從日常生活中的排隊抽象出來的，根據(jù)排隊的原則“先來先服務”。所謂隊列就是允許在一端進行插入，另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個隊尾指針r指向隊尾元素；允許刪除的一端稱為隊首，通常也用一個隊首指針f指向排頭元素的前面。初始時，f=r=0。隊列又稱為“先進先出（FIFO）”線性表。

定義方法：

Const

m=隊列元素上限;

Type

duilie=array[1..m]of<元素類型>;

Var

q:duilie;r,f:integer;二、隊列的基本運算

1.過程add(x)：隊列q插入元素xProcedureadd(x:integer);

begin

ifr=m

thenwriteln(‘overflow’)

elsebegin

r:=r+1;

q[r]:=x;

end;

end;

2.過程del(x)：取出隊列q的隊首元素yProceduredel(vary:integer);

begin

iff=r

thenwriteln(‘empty’)

elsebegin

f:=f+1;

y:=q[f];

end;

end;第六章數(shù)據(jù)結構之非線性結構第一節(jié)樹的概念一、樹的定義

樹是一種常見的非線性的數(shù)據(jù)結構。

樹的定義：樹是n(n>0)個結點的有限集，這個集合滿足以下條件：

⑴有且僅有一個結點沒有前驅(qū)（父親結點），該結點稱為樹的根；

⑵除根外，其余的每個結點都有且僅有一個前驅(qū)；

⑶除根外，每一個結點都通過唯一的路徑連到根上。這條路徑由根開始，而未端就在該結點上，且除根以外，路徑上的每一個結點都是前一個結點的后驅(qū)（兒子結點）；二、結點的分類

在樹中，一個結點包含一個元素以及所有指向其子樹的分支。

結點一般分成三類:

⑴根結點：沒有前驅(qū)的結點。在樹中有且僅有一個根結點。如上圖（b）中的r；

⑵分支結點：除根結點外，有后驅(qū)的結點稱為分支結點。如上圖（b）中的a，b，c，x，t，d，i。分支結點亦是其子樹的根；

⑶葉結點：沒有后驅(qū)的結點稱為樹葉。如上圖（b）中的w，h，e，f，s，m，o，n，j，u為葉結點。由樹的定義可知，樹葉本身也是其父結點的子樹。根結點到每一個分支結點或葉結點的路徑是唯一的。例如上圖（b）中，從根r到結點i的唯一路徑為rcti。三、有關度的定義

⑴結點的度：一個結點的子樹數(shù)目稱為該結點的度。在上圖（b）中，結點i度為3，結點t的度為2，結點b的度為1。顯然，所有樹葉的度為0。

⑵樹的度：所有結點中最大的度稱為該樹的度。圖（b）中的樹的度為3。四、樹的深度（高度）

樹是分層次的。結點所在的層次是從根算起的。根結點在第一層，根的后件在第二層，其余各層依次類推。即若某個結點在第k層，則該結點的后件均處在第k+1層。

圖（b）中的樹共有五層。在樹中，父結點在同一層的所有結點構成兄弟關系。樹中最大的層次稱為樹的深度，亦稱高度。圖（b）中樹的深度為5。五、森林

所謂森林，是指若干棵互不相交的樹的集合。

如圖（b）去掉根結點r，其原來的三棵子樹Ta，Tb，Tc的集合{Ta，Tb，Tc}就為森林，這三棵子樹的具體形態(tài)如圖（c）。

六、有序樹和無序樹

按照樹中同層結點是否保持有序性，可將樹分為有序樹和無序樹。如果樹中同層結點從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結點的次序任意，這樣的樹稱為無序樹。第二節(jié)樹的表示方法和存儲結構一、樹的表示方法

樹的表示方法一般有兩種：

⑴自然界的樹形表示法：用結點和邊表示樹，例如下圖采用的就是自然界的樹形表示法。樹形表示法一般用于分析問題。

⑵括號表示法：先將根結點放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如下圖(b)可寫成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））二、樹的存儲結構

樹的存儲結構一般有兩種

1.靜態(tài)的記錄數(shù)組

所有結點存儲在一個數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n為樹的度)的數(shù)組，分別存儲該結點的每一個兒子的下標。Const

n=樹的度；

max=結點數(shù)的上限；Type

node=record

data：<數(shù)據(jù)類型>；{數(shù)據(jù)域}s

ch：array[1‥n]ofinteger；{指向各兒子的下標}

end；

treetype=array[1..max]ofnode；Var

tree：treetype；該圖用靜態(tài)數(shù)組方法保存如右表下標數(shù)據(jù)域tree[i].data兒子的下標序列tree[i].ch1r2342a5603b7004c89105w0006x111207f0008s0009t1314010u00011d150012e00013i16171814j00015h00016m00017o00018n000

2.動態(tài)的多重鏈表

由于樹中結點可以有多個元素，所以可以用多重鏈表來描述比較方便。所謂多重鏈表，就是每個結點由數(shù)據(jù)域和n(n為樹的度)個指針域共n+1個域組成，其表示方法如下：

Const

n=樹的度；Type

treetype=^node；

node=record

data：datatype；{數(shù)據(jù)域}

next：array[1‥n]oftreetype；{指向各兒子的指針域}

end；Var

root：treetype；上圖用多重鏈表表示如下：第三節(jié)二叉樹的概念一、二叉樹的遞歸定義和基本形態(tài)

1.二叉樹是一種很重要的非線性數(shù)據(jù)結構，它的特點是每個結點最多有兩個后繼，且其子樹有左右之分（次序不能任意顛倒）。

2.二叉樹是以結點為元素的有限集，它或者為空，或者滿足以下條件：

⑴有一個特定的結點稱為根；

⑵余下的結點分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；

由上述定義可以看出，二叉樹和樹是兩個不同的概念:

⑴樹的每一個結點可以有任意多個后繼，而二叉樹中每個結點的后繼不能超過2；

⑵樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結點的左后繼為左兒子，右后繼為右兒子。

3.二叉樹的五種基本形態(tài)二、二叉樹的兩個特殊形態(tài)

1.滿二叉樹：如果一棵二叉樹的任何結點，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。（例如下圖(a)）可以驗證具有n個葉結點的滿二叉樹共有2n-1個結點。

2.完全二叉樹：如果一棵二叉樹最多只有最下面兩層結點度數(shù)可以小于2，并且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹（例如下圖(b)）

三、二叉樹的三個主要性質(zhì)

性質(zhì)1：在二叉樹的第i（≥1）層上，最多有2i-1個結點。

性質(zhì)2：在深度為k(k≥1)的二叉樹中最多有2k-1個結點。

性質(zhì)3：在任何二叉樹中，葉子結點數(shù)總比度為2的結點多1。二叉樹的性質(zhì)(1)在二叉樹中，第i層的結點總數(shù)不超過2^(i-1)；(2)深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點；(3)對于任意一棵二叉樹，如果其葉結點數(shù)為N0，而度數(shù)為2的結點總數(shù)為N2，則N0=N2+1；(4)具有n個結點的完全二叉樹的深度為int（log2n）+1(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：若I為結點編號則如果I<>1，則其父結點的編號為I/2；如果2*I<=N，則其左兒子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N，則其右兒子的結點編號為2*I+1；若2*I+1>N，則無右兒子。(6)給定N個節(jié)點，能構成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項。h(n)=C(n,2*n)/(n+1)。四、普通有序樹轉換成二叉樹

普通樹為有序樹T，將其轉化成二叉樹T’的規(guī)則如下：

⑴T中的結點與T’中的結點一一對應，即T中每個結點的序號和值在T’中保持不變；

⑵T中某結點v的第一個兒子結點為v1，則在T’中v1為對應結點v的左兒子結點；

⑶T中結點v的兒子序列，在T’中被依次鏈接成一條開始于v1的右鏈；由上述轉化規(guī)則可以看出，一棵有序樹轉化成二叉樹的根結點是沒有右子樹的，并且除保留每個結點的最左分支外，其余分支應去掉，然后從最左的兒子開始沿右兒子方向依次鏈接該結點的全部兒子。五、森林轉換成二叉樹

如果m棵互不相交的普遍有序樹組成了森林F={T1，…Tm}。我們可以按下述規(guī)則將森林F轉換成一棵二叉樹b={R，LB，RB}：

⑴若F為空（m=0），則b為空樹；

⑵若F非空（m≠0），則b的根R即為森林中第一棵樹的根R(T1)；b的左子樹LB是從T1的根結點的子樹森林F1={T11，T12，…T1