信息學(xué)奧賽-計(jì)算機(jī)基礎(chǔ)知識.doc

《信息學(xué)奧賽-計(jì)算機(jī)基礎(chǔ)知識.doc》由會員分享，可在線閱讀，更多相關(guān)《信息學(xué)奧賽-計(jì)算機(jī)基礎(chǔ)知識.doc（33頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第一章 計(jì)算機(jī)基礎(chǔ)知識 2 第一節(jié) 數(shù)制及其轉(zhuǎn)換 2 第二節(jié) 算術(shù)運(yùn)算和邏輯運(yùn)算 3 第三節(jié) 原碼、反碼和補(bǔ)碼 5 第四節(jié) 浮點(diǎn)數(shù)的表示方法 6 第五節(jié) 奇偶校驗(yàn) 7 第六節(jié) ASCII碼表 8 第二章 計(jì)算機(jī)硬件基礎(chǔ) 9 第一節(jié) 中央處理器 9 第二節(jié) 存儲器系統(tǒng) 10 第三節(jié) 輸入輸出系統(tǒng) 11 第三章 網(wǎng)絡(luò)基礎(chǔ)知識 12 第一節(jié) 網(wǎng)絡(luò)的組成與結(jié)構(gòu) 12 第二節(jié) 網(wǎng)絡(luò)協(xié)議 13 第三節(jié) Internet相關(guān)知識 13 第三節(jié) Internet相關(guān)知識 14 第四章 其他相關(guān)基礎(chǔ)知識 15 第一節(jié) 計(jì)算機(jī)病毒 15 第二節(jié) 數(shù)據(jù)庫系統(tǒng) 15 第五章 數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu) 16 第一節(jié) 線性表 16 第二節(jié) 棧 17 第三節(jié) 隊(duì)列 18 第六章 數(shù)據(jù)結(jié)構(gòu)之非線性結(jié)構(gòu) 19 第一節(jié) 樹的概念 19 第二節(jié) 樹的表示方法和存儲結(jié)構(gòu) 20 第三節(jié) 二叉樹的概念 22 第四節(jié) 二叉樹的遍歷 24 第五節(jié) 普通樹的遍歷 27 第六節(jié) 根據(jù)兩種遍歷順序確定樹結(jié)構(gòu) 28 第七節(jié) 二叉排序樹 29 第八節(jié) 最優(yōu)二叉樹(哈夫曼樹) 30 AOE網(wǎng) 32 第一章 計(jì)算機(jī)基礎(chǔ)知識 第一節(jié) 數(shù)制及其轉(zhuǎn)換 一、二、八、十六進(jìn)制轉(zhuǎn)十進(jìn)制的方法：乘權(quán)相加法。 例如： （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 二、十進(jìn)制化二進(jìn)制的方法：整數(shù)部分除二取余法，小數(shù)部分乘二取整法。 例一：（43）10 = （101011）2 例二：（0.375）10 = （0.011）2 三、二進(jìn)制轉(zhuǎn)八進(jìn)制的方法 一位數(shù)八進(jìn)制與二進(jìn)制對應(yīng)表 八進(jìn)制 二進(jìn)制 轉(zhuǎn)換方法:對二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每三位劃為一組， 不足三位補(bǔ)0，按上表用對應(yīng)的八進(jìn)制數(shù)字代入即可。 例如：(10111011.01100111) = 010,111,011.011,001,110 = （273.36）8 0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 三、二進(jìn)制轉(zhuǎn)十六進(jìn)制的方法 一位數(shù)十六進(jìn)制與二進(jìn)制對應(yīng)表 十六進(jìn)制 二進(jìn)制 轉(zhuǎn)換方法:對二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每四位劃 為一組，不足四位補(bǔ)0，按上表用對應(yīng)的十六進(jìn) 制數(shù)字代入即可。 例如：(10111011.01100111) = 1011,1011.0110,0111 = （BB.67）16 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 A 1010 B 1011 C 1100 D 1101 E 1110 F 1111 四、進(jìn)制的英文表示法： 以上都是用括號加數(shù)字的表示方法，另外還有英文表示法，就是以BIN、OCT、HEX、DEC分別代表二、八、十六、十進(jìn)制?；蛘咧粚懙谝粋€字母。例如1101B表示是二進(jìn)制。有些地方為了避免“O”跟“0”混淆，把O寫成Q。 第二節(jié) 算術(shù)運(yùn)算和邏輯運(yùn)算 一、二進(jìn)制的算術(shù)運(yùn)算 1、加法運(yùn)算規(guī)則： ?? 0+0=0?? 0+1=1? 1+0=1 1+1=10 2、減法運(yùn)算規(guī)則： ?? 0-0=0? 0-1=1（向高位借1） 1-0=1 1-1=0 3、乘法運(yùn)算規(guī)則： ?? 0×0=0? 0×1=0? 1×0=0? 1×1=1 二、邏輯運(yùn)算 1、基本運(yùn)算 ?? ① 邏輯乘，也稱“與”運(yùn)算，運(yùn)算符為“·”或“∧” ????? 0·0=0? 0·1=0? 1·0=0? 1·1=1 ????? 使用邏輯變量時(shí)，A·B可以寫成AB ?? ② 邏輯加，也乘“或”運(yùn)算，運(yùn)算符為“+”或“∨” ????? 0+0=0?? 0+1=1? 1+0=1 1+1=1 ?? ③ 邏輯非，也稱“反”運(yùn)算，運(yùn)算符是在邏輯值或變量符號上加“—” = 1? ? = 0 2、常用運(yùn)算 ?? 異或運(yùn)算：A⊕B =A·＋·B 2、基本公式 ?? ① 0，1律 ????? A·0=0 ????? A·1=A ????? A＋0=A ????? A＋1=1 ???② 交換律 ????? A＋B=B＋A ????? A·B=B·A ???③ 結(jié)合律 ????? 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 ?? ⑥ 互補(bǔ)律 ????? A + = 1????? A· = 0 ?? ⑦ 吸收律 ????? A＋A·B = A?????? A·（A＋B） = A ????? A＋·B = A＋B????? A·（＋B） = A·B ?? ⑧ 對合律 ????? 對一個邏輯變量兩次取反仍是它本身 ?? ⑨ 德·摩根定理 ????? = · ??????= + 三、邏輯代數(shù)的應(yīng)用 1、邏輯表達(dá)式化簡 ?? 例如： F = ·＋A·＋A·B? ??????????=·＋A（＋B）???? （利用分配律） ??????????=·＋A???????????? （利用互補(bǔ)律以及0，1律） ????????? = A＋??????????????（利用吸收律） 2、對指定位進(jìn)行運(yùn)算，假設(shè)變量A有八位，內(nèi)容是d7d6d5d4d3d2d1d0 ?? ① 將變量A的d5位清零 ????? A·（11011111）→A ?? ② 將變量A的各位置1 ????? A＋（11111111）→A ??? 第三節(jié) 原碼、反碼和補(bǔ)碼 ??? 計(jì)算機(jī)中參與運(yùn)算的數(shù)有正負(fù)之分，計(jì)算機(jī)中的數(shù)的正負(fù)號也是用二進(jìn)制表示的。用二進(jìn)制數(shù)表示符號的數(shù)稱為機(jī)器碼。常用的機(jī)器碼有原碼、反碼和補(bǔ)碼。 一、原碼 求原碼的方法：設(shè)X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位照抄。 【例1】X=+1001001?? [X]原 = 01001001 【例2】X=-1001001?? [X]原 = 11001001 二、反碼 求反碼的方法：設(shè)X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位按位取反。 【例3】X=+1001001?? [X]反 = 01001001 【例4】X=-1001001?? [X]反 = 10110110 三、補(bǔ)碼 求補(bǔ)碼的方法：設(shè)X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位按位取反后，最低位加1。 【例5】X=+1001001?? [X]補(bǔ) = 01001001 【例6】X=-1001001?? [X]補(bǔ) = 10110111 四、補(bǔ)碼加減法 ?? 計(jì)算機(jī)中實(shí)際上只有加法，減法運(yùn)算轉(zhuǎn)換成加法運(yùn)算進(jìn)行，乘法運(yùn)算轉(zhuǎn)換成加法運(yùn)算進(jìn)行，除法運(yùn)算轉(zhuǎn)換成減法運(yùn)算進(jìn)行。用補(bǔ)碼可以很方便的進(jìn)行這種運(yùn)算。 1、補(bǔ)碼加法 ?? [X+Y]補(bǔ) = [X]補(bǔ) + [Y]補(bǔ) 【例7】X=+0110011,Y=-0101001，求[X+Y]補(bǔ) ??? [X]補(bǔ)=00110011? [Y]補(bǔ)=11010111 ??? [X+Y]補(bǔ) = [X]補(bǔ) + [Y]補(bǔ) = 00110011+11010111=00001010 ??? 注：因?yàn)橛?jì)算機(jī)中運(yùn)算器的位長是固定的，上述運(yùn)算中產(chǎn)生的最高位進(jìn)位將丟掉，所以結(jié)果不是 ??????? 100001010，而是00001010。 2、補(bǔ)碼減法 ?? [X-Y]補(bǔ) = [X]補(bǔ) - [Y]補(bǔ) = [X]補(bǔ) + [-Y]補(bǔ) ?? 其中[-Y]補(bǔ)稱為負(fù)補(bǔ)，求負(fù)補(bǔ)的方法是：對補(bǔ)碼的每一位（包括符號位）求反，最后末位加“1”。 【例8】X=+0111001,Y=+1001101，求[X-Y]補(bǔ) ??? [X]補(bǔ)=00111001? [Y]補(bǔ)=01001101? [-Y]補(bǔ) = 10110011 ??? [X-Y]補(bǔ) = [X]補(bǔ) + [-Y]補(bǔ) = 00111001+10110011=11101100 五、數(shù)的表示范圍 ??? 通過上面的學(xué)習(xí)，我們就可以知道計(jì)算機(jī)如果用一個字節(jié)表示一個整數(shù)的時(shí)候，如果是無符號數(shù)，可以表示0~255共256個數(shù)（00000000~11111111），如果是有符號數(shù)則能表示-128~127共256個數(shù)（10000000~01111111）。如果兩個字節(jié)表示一個整數(shù)，則共有65536個數(shù)可以表示，大部分程序設(shè)計(jì)語言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(shù)，而且是補(bǔ)碼表示的。 第四節(jié) 浮點(diǎn)數(shù)的表示方法 一、浮點(diǎn)數(shù)表示 ??? 一個數(shù)的浮點(diǎn)形式（設(shè)基數(shù)是2）可寫成： ??????????????????? N = M × 2E ??? 其中:M代表尾數(shù),E代表階碼。 ??? 計(jì)算機(jī)中浮點(diǎn)數(shù)只用尾數(shù)和階碼表示，其形式如下： ??? 階碼 尾數(shù)符號 尾數(shù) ??? 浮點(diǎn)數(shù)的精度由尾數(shù)決定，數(shù)的表示范圍由階碼的位數(shù)決定。 ?　 為了最大限度提高精度，尾數(shù)采用規(guī)格化形式，既1/2≤M<1。采用二進(jìn)制表示時(shí)，若尾數(shù)大于零，則規(guī)格化數(shù)應(yīng)該是01XXXX的形式；若尾數(shù)小于零，則規(guī)格化數(shù)應(yīng)為10XXXX的形式。 二、機(jī)器零 ??? 當(dāng)浮點(diǎn)數(shù)的尾數(shù)為0或階碼為最小值時(shí)，計(jì)算機(jī)通常把該數(shù)當(dāng)作零，因此程序中進(jìn)行浮點(diǎn)運(yùn)算時(shí)，判斷某數(shù)是否為零，通?？梢杂眯∮谀硞€極小值來代替。 三、實(shí)例 【例1】設(shè)X=0.0110×23 ,用補(bǔ)碼、浮點(diǎn)數(shù)形式表示階碼為Xj=011，尾數(shù)為00110，這時(shí)由于X尾數(shù)不符合01XXXX的形式，因此不是規(guī)格化數(shù)，必須先進(jìn)行規(guī)格化處理。 方法：若尾數(shù)小于1/2，把尾數(shù)左移一位（不包括符號位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼減1即可，否則繼續(xù)左移和調(diào)整階碼；若尾數(shù)大于1，則把尾數(shù)右移一位（不包括符號位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼加1即可，否則繼續(xù)右移和調(diào)整階碼。 上例中，00110左移一位為01100，符合規(guī)則化標(biāo)準(zhǔn)，此時(shí)階碼減1，為010即得到浮點(diǎn)表示形式。 ??? 這個數(shù)具體在計(jì)算機(jī)中如何表示要看計(jì)算機(jī)中規(guī)定的階碼和尾數(shù)的位數(shù)，若階碼和尾數(shù)均為16位，則上面的數(shù)X在計(jì)算機(jī)內(nèi)部表示就是 00000000000000100110000000000000 ，不足均用零填充。??? 第五節(jié) 奇偶校驗(yàn) ?? 計(jì)算機(jī)中數(shù)據(jù)在進(jìn)行存儲和傳輸過程中可能會發(fā)生錯誤。為了及時(shí)發(fā)現(xiàn)和糾正這類錯誤，在數(shù)據(jù)傳輸（存儲）過程中要進(jìn)行校驗(yàn)，常用的校驗(yàn)方法就是奇偶校驗(yàn)。 ?? 奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)一位或奇數(shù)位錯誤，且不能糾正錯誤。一般以字節(jié)（八位二進(jìn)制）為單位加1位奇偶校驗(yàn)位。奇偶校驗(yàn)分奇校驗(yàn)和偶校驗(yàn)兩種。 一、奇校驗(yàn)：一個字節(jié)前面加一位校驗(yàn)位使得“1”的個數(shù)保持為奇數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗(yàn)位為“1”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗(yàn)位為“0”。 【例1】給1001100101101101加奇校驗(yàn)結(jié)果為110011001001101101 二、偶校驗(yàn)：一個字節(jié)前面加一位校驗(yàn)位使得“1”的個數(shù)保持為偶數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗(yàn)位為“0”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗(yàn)位為“1”。 【例2】給1001100101101101加偶校驗(yàn)結(jié)果為010011001101101101 第六節(jié) ASCII碼表 代碼 字符 代碼 字符 代碼 字符 代碼 字符 代碼 字符 32 ? 52 4 72 H 92 \ 112 p 33 ! 53 5 73 I 93 ] 113 q 34 ” 54 6 74 J 94 ^ 114 r 35 # 55 7 75 K 95 _ 115 s 36 $ 56 8 76 L 96 ` 116 t 37 % 57 9 77 M 97 a 117 u 38 & 58 : 78 N 98 b 118 v 39 ’ 59 ; 79 O 99 c 119 w 40 ( 60 < ? 80 P 100 d 120 x 41 ) 61 = 81 Q 101 e 121 y 42 * 62 > ? 82 R 102 f 122 z 43 + 63 ? 83 S 103 g 123 { 44 , 64 @ 84 T 104 h 124 | 45 - 65 A 85 U 105 i 125 } 46 . 66 B 86 V 106 j 126 ~ 47 / 67 C 87 W 107 k ? ? 48 0 68 D 88 X 108 l ? ? 49 1 69 E 89 Y 109 m ? ? 50 2 70 F 90 Z 110 n ? ? 51 3 71 G 91 [ 111 o ? ? ??? 目前使用最廣泛的西文字符集及其編碼是 ASCII 字符集和 ASCII 碼（ ASCII 是 American Standard Code for Information Interchange 的縮寫），它同時(shí)也被國際標(biāo)準(zhǔn)化組織（ International Organization for Standardization, ISO ）批準(zhǔn)為國際標(biāo)準(zhǔn)。 ??? 基本的 ASCII 字符集共有 128 個字符，其中有 96 個可打印字符，包括常用的字母、數(shù)字、標(biāo)點(diǎn)符號等，另外還有 32 個控制字符。標(biāo)準(zhǔn) ASCII 碼使用 7 個二進(jìn)位對字符進(jìn)行編碼，對應(yīng)的 ISO 標(biāo)準(zhǔn)為 ISO646 標(biāo)準(zhǔn)。下表展示了基本 ASCII 字符集及其編碼： ??? 字母和數(shù)字的 ASCII 碼的記憶是非常簡單的。我們只要記住了一個字母或數(shù)字的 ASCII 碼（例如記住 A 為 65 ， 0 的 ASCII 碼為 48 ），知道相應(yīng)的大小寫字母之間差 32 ，就可以推算出其余字母、數(shù)字的 ASCII 碼。 ??? 雖然標(biāo)準(zhǔn) ASCII 碼是 7 位編碼，但由于計(jì)算機(jī)基本處理單位為字節(jié)（ 1byte = 8bit ），所以一般仍以一個字節(jié)來存放一個 ASCII 字符。每一個字節(jié)中多余出來的一位（最高位）在計(jì)算機(jī)內(nèi)部通常保持為 0 （在數(shù)據(jù)傳輸時(shí)可用作奇偶校驗(yàn)位）。 由于標(biāo)準(zhǔn) ASCII 字符集字符數(shù)目有限，在實(shí)際應(yīng)用中往往無法滿足要求。為此，國際標(biāo)準(zhǔn)化組織又制定了 ISO2022 標(biāo)準(zhǔn)，它規(guī)定了在保持與 ISO646 兼容的前提下將 ASCII 字符集擴(kuò)充為 8 位代碼的統(tǒng)一方法。 ISO 陸續(xù)制定了一批適用于不同地區(qū)的擴(kuò)充 ASCII 字符集，每種擴(kuò)充 ASCII 字符集分別可以擴(kuò)充 128 個字符，這些擴(kuò)充字符的編碼均為高位為 1 的 8 位代碼（即十進(jìn)制數(shù) 128~255 ），稱為擴(kuò)展 ASCII 碼。下表展示的是最流行的一套擴(kuò)展 ASCII 字符集和編碼： 第二章 計(jì)算機(jī)硬件基礎(chǔ) 第一節(jié) 中央處理器 一、中央處理器的組成 ??? 中央處理器簡稱CPU，由控制器、運(yùn)算器組成。 ???運(yùn)算器及控制器的基本功能：運(yùn)算器是計(jì)算機(jī)進(jìn)行算術(shù)和邏輯運(yùn)算的部件，控制器是整個計(jì)算機(jī)中統(tǒng)一指揮和控制計(jì)算機(jī)各部件進(jìn)行工作的控制中心。 二、運(yùn)算器 ??? 運(yùn)算器是負(fù)責(zé)對數(shù)據(jù)進(jìn)行算術(shù)運(yùn)算或邏輯運(yùn)算的部件。運(yùn)算器由算術(shù)邏輯單元（ALU）、累加器、狀態(tài)寄存器、通用寄存器組等組成。如圖：????? ??? 算術(shù)邏輯運(yùn)算單元、累加器和通用寄存器的位數(shù)決定了CPU的字長。 三、控制器 ??? 是計(jì)算機(jī)的指令執(zhí)行部件，其工作是取指令、解釋指令以及完成指令的執(zhí)行。 ??? 控制器由指令指針寄存器、指令寄存器、控制邏輯電路和時(shí)鐘控制電路等組成。 ??? 指令指針寄存器（IP）用于?? 產(chǎn)生及存放一條待取指令的地址。 ??? 指令寄存器用于存放指令。指令從內(nèi)存取出后放入指令寄存器。 四、寄存器 ??? 寄存器數(shù)量增多可以提高CPU運(yùn)行速度，但是不能太多，太多會使地址編碼和指令長度變長，增加復(fù)雜度。由累加器、通用寄存器組、狀態(tài)寄存器、指令寄存器、地址寄存器、其他寄存器等組成。 五、指令基本格式 ??? 單目運(yùn)算：操作碼 地址碼 ??? 二目運(yùn)算：操作碼 第一地址 第二地址 六、尋址方式：CPU執(zhí)行指令時(shí)尋找數(shù)據(jù)地址的方式 ?? 1、立即尋址：ADD AH,78? 其中ADD是操作碼，表示做加法；AH是寄存器名；78是個常數(shù)；該指令的意思是寄存器AH的值加上78。 ?? 2、直接尋址：ADD AH,(78)? 78表示操作數(shù)的地址 ?? 3、間接尋址：ADD AH,((78))? 78表示操作數(shù)地址的地址 ?? 4、相對尋址：ADD AH,*78?? *78表示本指令地址+78，78稱偏移量 ?? 5、變址尋址：ADD AH,(DI+78) DI是變址寄存器,存放一個地址,操作數(shù)地址是寄存器地址+78 ?? 6、寄存器直接尋址:ADD AH,78? AH是一個寄存器名,即寄存器直接尋址 ?? 7、寄存器直接尋址:ADD AH,(BX)? BX是一個寄存器名,存放操作數(shù)的地址 七、指令分類 ?? 1、數(shù)據(jù)傳送指令：MOV AH,BH ?????????????????? IN AH,378 ?? 2、數(shù)據(jù)處理指令:算術(shù)運(yùn)算、邏輯運(yùn)算、移位、比較等 ?? 3、程序控制指令：轉(zhuǎn)移、調(diào)用、返回 ?? 4、狀態(tài)管理指令：中斷、屏蔽中斷 八、指令的執(zhí)行過程 ?? 1、CPU發(fā)出指令地址 ?? 2、讀取指令 ?? 3、指令送指令寄存器 ?? 4、指令譯碼 ?? 5、按指令操作碼執(zhí)行 ?? 6、形成下條要執(zhí)行的指令的地址 九、時(shí)鐘周期 ??? 一個指令執(zhí)行的時(shí)間稱為指令周期 ??? 計(jì)算機(jī)完成一個操作（如讀取指令等）所需時(shí)間稱為總線周期 ??? 計(jì)算機(jī)中最基本的時(shí)間單位是時(shí)鐘周期，有CPU的主頻決定。 第二節(jié) 存儲器系統(tǒng) 一、存儲器的分類 分類方法 名稱 舉例 按存儲介質(zhì)分 半導(dǎo)體存儲器 ROM、RAM（內(nèi)存）、閃存（優(yōu)盤） 磁表面存儲器 硬盤、軟盤、磁帶 光存儲器 CD-ROM、DVD-ROM 按工作方式分 隨機(jī)存儲器 RAM（內(nèi)存）、硬盤、軟盤 只讀存儲器 ROM、CD-ROM 順序存儲器 磁帶 二、多層次存儲體系: 如圖 三、主存儲器 ??? 1、特點(diǎn)：容量小、讀寫速度快、價(jià)格高 ??? 2、編址方式：存儲容量與地址線條數(shù)相對應(yīng)，64M的存儲器至少需要26跟地址線（226=64M） ??? 注：我們目前的計(jì)算機(jī)大都是32位，也就是地址線條數(shù)有32條，所以其支持的最大內(nèi)存容量為4G ??? 3、分類： ??? ① 隨機(jī)存儲器（RAM）：就是我們通常稱的內(nèi)存，主要參數(shù)是存儲容量和工作頻率。 ?????? 例如：一條64M×8的內(nèi)存條表示該內(nèi)存條有64M個單元，每個單元8位。 ??? ② 只讀存儲器（ROM）：只能讀不能寫，一般用于存放計(jì)算機(jī)啟動所需的最基本程序。 ??? ③ 緩沖存儲器（Cache）：速度最快，一般集成于CPU中。 四、輔助存儲器 ?? 1、磁帶：順序存儲，一般只用在小型機(jī)以上的計(jì)算機(jī)中，用作數(shù)據(jù)備份。 ?? 2、軟盤：目前常見的一般為3.5寸高密盤，容量為1.44MB，軟盤結(jié)構(gòu)如圖 ????? 注意：盤面最外層的磁道稱為0磁道，0磁道如果損壞，則盤片報(bào)廢。 ?? 3、硬盤：硬盤由多個盤面組成一個柱形結(jié)構(gòu)，其原來跟軟盤類似，但是磁道更多。 ?? 4、光盤：利用光信號讀取或?qū)懭氲拇鎯ζ鳌? ????? ① CD-ROM：只讀，容量650MB左右，一倍速為150KB/s ????? ② DVD-ROM：只讀，容量4.7GB左右，一倍速為1200KB/s ????? ③ CD-RW、DVD-RW：可擦寫的光盤，但必須專門的刻錄機(jī)。? 第三節(jié) 輸入輸出系統(tǒng) 一、輸入輸出控制方式 ?? 1、程序查詢方式：軟件實(shí)現(xiàn)，效率低 ?? 2、中斷方式：軟硬件結(jié)合實(shí)現(xiàn) ????? 中斷請求-->中斷響應(yīng)-->中斷處理-->中斷返回 ?? 3、直接存儲器訪問方式（DMA）：硬件實(shí)現(xiàn) ????? DMA請求-->CPU響應(yīng)并把總線控制權(quán)交給DMA控制器-->數(shù)據(jù)交換-->交還總線控制權(quán) 二、系統(tǒng)總線 ??? 分類：數(shù)據(jù)總線、地址總線、控制總線 ??? 總線標(biāo)準(zhǔn)：ISA總線、PCI局部總線、MCA總線 三、I/O接口 ??? 1、顯卡：分辨率、顏色數(shù)決定顯示效果和所需顯存 ?????? 例如：顯示分辨率為1280×1024的32位真彩色，所需顯卡顯存最少為 ????????????? 1280×1024×32÷8 = 5MB ??? 2、硬盤接口： ????? ① IDE、EIDE ????? ② Ultra DMA ????? ③ SCSI ????? ④ SATA ??? 3、串行口 ??? 4、并行口：通常接針式打印機(jī) ??? 5、USB接口：通用串行總線 四、顯示器的有關(guān)知識 ??? 1、屏幕尺寸：15寸、17寸、19寸等 ??? 2、點(diǎn)間距：屏幕上象素與象素之間的距離，決定了顯示器能顯示的最大分辨率。 越小表示能顯示的最大分辨率越大。 五、打印機(jī)：針式打印機(jī)、噴墨打印機(jī)、激光打印機(jī)。 ??? 激光打印機(jī)速度最快，針式打印機(jī)可以打印票據(jù)。 第三章 網(wǎng)絡(luò)基礎(chǔ)知識 第一節(jié) 網(wǎng)絡(luò)的組成與結(jié)構(gòu) 一、網(wǎng)絡(luò)組成 ?? 1、通信主體：服務(wù)器和工作站 ?? 2、通信設(shè)備：傳輸介質(zhì)、網(wǎng)絡(luò)設(shè)備 ?? 3、通信協(xié)議：通常是TCP/IP 二、網(wǎng)絡(luò)分類 ??? 按傳輸距離分：局域網(wǎng)（LAN）、城域網(wǎng)（MAN）、廣域網(wǎng)（WAN） ??? 按網(wǎng)絡(luò)結(jié)構(gòu)分：總線型、星型、環(huán)型、樹型 三、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 第二節(jié) 網(wǎng)絡(luò)協(xié)議 第 33 頁 共 33 頁 應(yīng)用層 表達(dá)層 會話層 傳輸層 網(wǎng)絡(luò)層 數(shù)據(jù)鏈路層 物理層 一、OSI網(wǎng)絡(luò)協(xié)議的層次 國際標(biāo)準(zhǔn)化組織（ISO）提出的“開放系統(tǒng)互連模型（OSI）” 是計(jì)算機(jī)網(wǎng)絡(luò)通信的基本協(xié)議。 該協(xié)議分為七層。如下表 二、網(wǎng)絡(luò)設(shè)備極其作用 第三節(jié) Internet相關(guān)知識 一、IP地址 ??? 每臺與Internet連接的主機(jī)都必須有一個IP地址，IP地址采用分段式表示：共分4段，每段用一個字節(jié)即八個二進(jìn)制位表示，實(shí)際的IP把二進(jìn)制轉(zhuǎn)換成十進(jìn)制書寫。如61.153.238.132，因?yàn)槊慷螘r(shí)一個字節(jié)，因此IP每段的數(shù)字大小最大為255。 ??? IP地址分類如下表：目前32位IP地址資源幾近枯竭，有人提出用48位表示IP，即IPV6 。 分類 二進(jìn)制表示 十進(jìn)制表示第一段數(shù)字 A類 0 七位網(wǎng)絡(luò)地址 24位主機(jī)地址 <128 B類 10 14位網(wǎng)絡(luò)地址 16位主機(jī)地址 128~191 C類 110 21位網(wǎng)絡(luò)地址 8位主機(jī)地址 192~223 二、域名：Internet的域名系統(tǒng)叫做DNS，DNS是樹形結(jié)構(gòu)的。 域名跟IP地址是多對一的關(guān)系 ??? 1、域名分級系統(tǒng)：一個域名最右邊的部分通常叫頂級域名，往前依次為二級域名、三級域名等。 ??? 2、我國域名管理機(jī)構(gòu):CNNIC ??? 3、常見域名含義： ??? gov 政府 edu 教育 int 國際組織 com 商業(yè)組織 mil 軍事部門 net 網(wǎng)絡(luò)運(yùn)行? org 其他組織 ??? cn 中國? hk 香港? tw 臺灣? uk 英國 jp 日本 三、一些常見名詞解釋 ??? 1、Intranet:企業(yè)內(nèi)部網(wǎng) ??? 2、ISP（Internet Service Provider）：因特網(wǎng)服務(wù)供應(yīng)商 ??? 3、ICP（Internet Content Provider）：因特網(wǎng)內(nèi)容供應(yīng)商 ??? 4、IAP（Internet Acess Provider）：因特網(wǎng)接入供應(yīng)商，目前一般都被ISP包含 ??? 5、BBS：電子公告欄，目前通常叫論壇 四、接入Internet的方法 ??? 1、PSTN撥號接入：必須設(shè)備MODEM，電話線，速度慢 ??? 2、DDN專線接入：速度快，費(fèi)用高。 ??? 3、ISDN專線接入：利用傳統(tǒng)電話網(wǎng)絡(luò)的綜合業(yè)務(wù)數(shù)字網(wǎng)。 ??? 4、分組交換接入 ??? 5、幀中繼接入 第四章 其他相關(guān)基礎(chǔ)知識 第一節(jié) 計(jì)算機(jī)病毒 一、特點(diǎn) ??? 寄生性、隱蔽性、非法性、傳染性、破壞性 二、分類： ??? 1、引導(dǎo)型病毒：寄生在系統(tǒng)引導(dǎo)區(qū)，比較容易被清除，現(xiàn)在已經(jīng)很少見。 ??? 2、文件型病毒：寄生在可執(zhí)行文件中，感染速度快，較易清除。 ??? 3、目錄型病毒：寄生在系統(tǒng)目錄結(jié)構(gòu)中 ??? 4、混合型病毒：多種類型的混合 ??? 5、宏病毒：專門感染Microsoft Office 系列文件的病毒 ??? 6、蠕蟲病毒：感染網(wǎng)絡(luò)，使網(wǎng)速大大降低。 ??? 目前流行的病毒大多集成了黑客技術(shù)、木馬技術(shù)和病毒技術(shù)三種，非常難以清除而且很容易中。 三、一些常見危害較大的病毒 ??? 1、CIH病毒:文件型病毒，4月26日發(fā)作時(shí)破壞性最大，首個能破壞硬件系統(tǒng)的病毒。 ??? 2、Melissa病毒：宏病毒，郵件傳播 ??? 3、沖擊波、震蕩波病毒：利用WINDOWS的漏洞，使計(jì)算機(jī)自動重啟并堵塞網(wǎng)絡(luò)。 第二節(jié) 數(shù)據(jù)庫系統(tǒng) 一、數(shù)據(jù)庫是數(shù)據(jù)的一種組織形式，目前存儲大量數(shù)據(jù)基本都采用數(shù)據(jù)庫 ?? 常見的數(shù)據(jù)庫軟件有：FoxBase、FoxPro、Access、Sql Server、MySql、Sybase、Oracel等。除了最早的如FoxBase等軟件，目前流行的數(shù)據(jù)庫軟件都是關(guān)系型數(shù)據(jù)庫。 二、數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)可以認(rèn)為是多張二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖 ??? 二、數(shù)據(jù)操作 ??? 用以對數(shù)據(jù)庫進(jìn)行檢索和更新（添加、刪除、更新等）操作?? 三、數(shù)據(jù)的完整性約束條件 ?? 多個表之間的數(shù)據(jù)可能存在相互關(guān)聯(lián)，必須保證其完整性 四、數(shù)據(jù)庫操作語言SQL ??? 數(shù)據(jù)庫常用的操作語言稱為SQL語言，是一種更高級化的語言，只須告訴計(jì)算機(jī)做什么事情即可。下面例舉幾條常用的語句。 ??? 1、SELECT 語句 ??? 語法：select <列名> from <表名> where <條件> ??? 功能：從表中選出滿足條件的記錄列 ??? 2、INSERT 語句 ??? 語法：insert into <表名>[(列名表)] values(<值表>) ??? 功能：在表中插入一條新記錄。 ??? 3、DELETE 語句 ??? 語法：delete * from <表名> where <條件> ??? 功能：刪除滿足條件的記錄 ??? 4、UPDATE 語句 ??? 語法：update <表名>? set <列名>=<值> where <條件> 功能：修改滿足條件的表中某記錄某字段的值? 第五章 數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu) 第一節(jié) 線性表 一、概念 ??? 線性表是指由有限個類型相同的數(shù)據(jù)元素組成的集合，它有以下的特點(diǎn)： ??? 1.有唯一的頭結(jié)點(diǎn)(即第一個數(shù)據(jù)元素)和尾結(jié)點(diǎn)(即最后一個數(shù)據(jù)元素)； ??? 2.除結(jié)點(diǎn)外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)； ??? 3.除尾結(jié)點(diǎn)外，集合中的每一個數(shù)據(jù)元素均只有一個后繼。 二、線性表的存儲結(jié)構(gòu) ??? 1、順序結(jié)構(gòu)：是通過數(shù)組說明分配連續(xù)地址的存儲區(qū)，通過下標(biāo)引用數(shù)組的相應(yīng)元素。 ??? 2、鏈?zhǔn)浇Y(jié)構(gòu)：通過指引元素類型的變量對線性表中元素進(jìn)行動態(tài)分配存儲。 三、順序存儲結(jié)構(gòu) ?? 1、一維數(shù)組 ?? ① 數(shù)組存儲的結(jié)構(gòu)在數(shù)組聲明時(shí)就需要事先分配相應(yīng)的連續(xù)內(nèi)存空間用來存放數(shù)據(jù)。 ?? ② 按首地址（表中第一個元素的地址）的位移來訪問數(shù)組每一個元素的。 ?? 若第一個元素的地址是a，每個元素占用的存儲空間為L，則數(shù)組的第i個元素的地址可以用如下公式計(jì)算： ?????????????????????? d(i)=a+(i-1)*L ?? 2、二維數(shù)組 ?? ① 定義方法：<數(shù)組名>:array[1..n,1..m] of <元素類型> ?? ② 對于行為n，列為m的二維數(shù)組的元素訪問方法： 若第一個元素的地址是a，每個元素占用的存儲空間為L，則數(shù)組的第(i,j)個元素的地址可以用如下公式計(jì)算： ??? ?按行尋址：d(i,j)=a+(i-1)*m*L+(j-1)*L ???? 按列尋址：d(i,j)=a+(j-1)*n*L+(i-1)*L 四、鏈?zhǔn)酱鎯Y(jié)構(gòu)　 ??? 鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù)部分存放結(jié)點(diǎn)的有關(guān)信息，指針部分存放下一個結(jié)點(diǎn)的位置。 ??? 優(yōu)點(diǎn)：可根據(jù)需要分配數(shù)據(jù)元素的存儲區(qū)，也可隨時(shí)撤消鏈表中數(shù)據(jù)元素的存儲區(qū)，插入刪除操作只須改變指針，無須移動數(shù)據(jù)。 ??? 缺點(diǎn)：它的數(shù)據(jù)元素必須在數(shù)據(jù)項(xiàng)以外至少增加一個指向后繼元素的指針類型的數(shù)據(jù)項(xiàng)，查找其中的某個元素時(shí)必須中從第一個元素開始逐個往后找。 一個實(shí)例： Type ?pointer=^node; ?node=Record; ?????? data:real; ?????? next:pointer; ????? End; Var ? head,next:pointer; ? ? 1.Head為表的首指針，指向鏈表的第一個結(jié)點(diǎn)。 ? 2.整個鏈表的存取必須從head指針出發(fā)，沿著每個結(jié)點(diǎn)的next指針順序進(jìn)行，最后個結(jié)點(diǎn)的next指針為“空”（nil）. 第二節(jié) 棧 一、棧的概念 ?? 棧是一種線性表，對它的插入和刪除操作都限制在表的同一端進(jìn)行。這一端叫做棧頂，另一個端叫做棧底。 棧又被成為“后進(jìn)先出表”（LIFO）。 ?? 定義方法： ?? Const ???? m=棧元素的上限； ?? Type ???? stack=array[1..m] of <元素類型> ?? Var ???? s:stack; ???? t:integer; 二、棧的基本運(yùn)算 　? 1.入棧：過程push(x)，往棧s中壓入一個元素x。 　 procedure push(x:<元素類型>); ? begin ??? if t=m ?????? then writeln(‘overflow’) ?????? else begin ???????????? t:=t+1; ???????????? s[t]:=x; ??????????? end; ? end; ??? 2.出棧：函數(shù)pop(x)，從棧s中彈出一個元素。 　 function pop:<元素類型>; ? begin ??? if t=0 ?????? then writeln('empty') ?????? else begin ????????????? pop:=s[t]; ????????????? t:=t-1; ??????????? end; ? end; ??? 3.讀棧頂元素：函數(shù)top，讀取棧s的棧頂元素。 　 function top:<元素類型>; ? begin ??? if t=0 ?????? then writeln('empty') ?????? else top:=s[t]; ? end; 第三節(jié) 隊(duì)列 一、棧的概念 ?? 隊(duì)列是從日常生活中的排隊(duì)抽象出來的，根據(jù)排隊(duì)的原則“先來先服務(wù)”。 所謂隊(duì)列就是允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一個隊(duì)尾指針r指向隊(duì)尾元素；允許刪除的一端稱為隊(duì)首，通常也用一個隊(duì)首指針f指向排頭元素的前面。初始時(shí)，f=r=0。 隊(duì)列又稱為“先進(jìn)先出（FIFO）”線性表。 ?? 定義方法： ?? Const ???? m=隊(duì)列元素上限; ?? Type ???? duilie=array[1..m] of <元素類型>; ?? Var ???? q:duilie; r,f:integer; 二、隊(duì)列的基本運(yùn)算 　? 1.過程add(x)：隊(duì)列q插入元素x 　 Procedure add(x:integer); ? begin ??? if r=m ?????? then writeln(‘overflow’) ?????? else begin ????????????? r:=r+1; ????????????? q[r]:=x; ??????????? end; ? end; ??? 2.過程del(x)：取出隊(duì)列q的隊(duì)首元素y 　 Procedure del(var y:integer); ? begin ??? if f=r ?????? then writeln(‘empty’) ?????? else begin ????????????? f:=f+1; ????????????? y:=q[f]; ??????????? end; ? end; 第六章 數(shù)據(jù)結(jié)構(gòu)之非線性結(jié)構(gòu) 第一節(jié) 樹的概念 一、樹的定義 ??? 樹是一種常見的非線性的數(shù)據(jù)結(jié)構(gòu)。 ??? 樹的定義：樹是n(n>0)個結(jié)點(diǎn)的有限集，這個集合滿足以下條件： ??? ⑴ 有且僅有一個結(jié)點(diǎn)沒有前驅(qū)（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹的根； ??? ⑵ 除根外，其余的每個結(jié)點(diǎn)都有且僅有一個前驅(qū)； ??? ⑶ 除根外，每一個結(jié)點(diǎn)都通過唯一的路徑連到根上。這條路徑由根開始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個結(jié)點(diǎn)都是前一個結(jié)點(diǎn)的后驅(qū)（兒子結(jié)點(diǎn)）； 二、結(jié)點(diǎn)的分類 ??? 在樹中，一個結(jié)點(diǎn)包含一個元素以及所有指向其子樹的分支。 ??? 結(jié)點(diǎn)一般分成三類: ??? ⑴ 根結(jié)點(diǎn)：沒有前驅(qū)的結(jié)點(diǎn)。在樹中有且僅有一個根結(jié)點(diǎn)。如上圖（b）中的r； ??? ⑵ 分支結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有后驅(qū)的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。如上圖（b）中的a，b，c，x，t，d，i。分支結(jié)點(diǎn)亦是其子樹的根； ??? ⑶ 葉結(jié)點(diǎn)：沒有后驅(qū)的結(jié)點(diǎn)稱為樹葉。如上圖（b）中的w，h，e，f，s，m，o，n，j，u為葉結(jié)點(diǎn)。由樹的定義可知，樹葉本身也是其父結(jié)點(diǎn)的子樹。 根結(jié)點(diǎn)到每一個分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。例如上圖（b）中，從根r到結(jié)點(diǎn)i的唯一路徑為rcti。 三、有關(guān)度的定義 ??? ⑴ 結(jié)點(diǎn)的度：一個結(jié)點(diǎn)的子樹數(shù)目稱為該結(jié)點(diǎn)的度。在上圖（b）中，結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1。顯然，所有樹葉的度為0。 ??? ⑵ 樹的度：所有結(jié)點(diǎn)中最大的度稱為該樹的度。圖（b）中的樹的度為3。 四、樹的深度（高度） ??? 樹是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的后件在第二層，其余各層依次類推。即若某個結(jié)點(diǎn)在第k層，則該結(jié)點(diǎn)的后件均處在第k+1層。 ??? 圖（b）中的樹共有五層。在樹中，父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。樹中最大的層次稱為樹的深度，亦稱高度。圖（b）中樹的深度為5。 五、森林 ??? 所謂森林，是指若干棵互不相交的樹的集合。 ??? 如圖（b）去掉根結(jié)點(diǎn)r，其原來的三棵子樹Ta，Tb，Tc的集合{Ta，Tb，Tc}就為森林，這三棵子樹的具體形態(tài)如圖（c）。? 六、有序樹和無序樹 ??? 按照樹中同層結(jié)點(diǎn)是否保持有序性，可將樹分為有序樹和無序樹。如果樹中同層結(jié)點(diǎn)從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結(jié)點(diǎn)的次序任意，這樣的樹稱為無序樹。 第二節(jié) 樹的表示方法和存儲結(jié)構(gòu) 一、樹的表示方法 ??? 樹的表示方法一般有兩種： ??? ⑴ 自然界的樹形表示法：用結(jié)點(diǎn)和邊表示樹，例如下圖采用的就是自然界的樹形表示法。樹形表示法一般用于分析問題。 ?? ?⑵ 括號表示法：先將根結(jié)點(diǎn)放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結(jié)點(diǎn)用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如下圖(b)可寫成如下形式 （r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u））） 二、樹的存儲結(jié)構(gòu) ??? 樹的存儲結(jié)構(gòu)一般有兩種 ??? 1.靜態(tài)的記錄數(shù)組 ??? 所有結(jié)點(diǎn)存儲在一個數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n為樹的度)的數(shù)組，分別存儲該結(jié)點(diǎn)的每一個兒子的下標(biāo)。 Const ? n=樹的度； ? max=結(jié)點(diǎn)數(shù)的上限； Type ? node=record ??????? data：<數(shù)據(jù)類型>； {數(shù)據(jù)域}s ??????? ch：array[1‥n] of integer；{指向各兒子的下標(biāo)} ?????? end； ? treetype=array[1..max]of node； Var ? tree：treetype； 該圖用靜態(tài)數(shù)組方法保存如右表 下標(biāo) 數(shù)據(jù)域 tree[i].data 兒子的下標(biāo)序列 tree[i].ch 1 r 2 3 4 2 a 5 6 0 3 b 7 0 0 4 c 8 9 10 5 w 0 0 0 6 x 11 12 0 7 f 0 0 0 8 s 0 0 0 9 t 13 14 0 10 u 0 0 0 11 d 15 0 0 12 e 0 0 0 13 i 16 17 18 14 j 0 0 0 15 h 0 0 0 16 m 0 0 0 17 o 0 0 0 18 n 0 0 0 ?? 2.動態(tài)的多重鏈表 ??? 由于樹中結(jié)點(diǎn)可以有多個元素，所以可以用多重鏈表來描述比較方便。所謂多重鏈表，就是每個結(jié)點(diǎn)由數(shù)據(jù)域和n(n 為樹的度)個指針域共n+1個域組成，其表示方法如下： ? 　 Const ? n=樹的度； Type ? treetype=^node； ? node=record ??????? data：datatype；{數(shù)據(jù)域} ??????? next：array[1‥n] of treetype；{指向各兒子的指針域} ?????? end； Var ? root：treetype； 　 上圖用多重鏈表表示如下： 第三節(jié) 二叉樹的概念 一、二叉樹的遞歸定義和基本形態(tài) ??? 1.二叉樹是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)最多有兩個后繼，且其子樹有左右之分（次序不能任意顛倒）。 ??? 2.二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件： ??? ⑴ 有一個特定的結(jié)點(diǎn)稱為根； ??? ⑵ 余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹； ?? 由上述定義可以看出，二叉樹和樹是兩個不同的概念: ??? ⑴ 樹的每一個結(jié)點(diǎn)可以有任意多個后繼，而二叉樹中每個結(jié)點(diǎn)的后繼不能超過2； ??? ⑵ 樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結(jié)點(diǎn)的左后繼為左兒子，右后繼為右兒子。 ??? 3.二叉樹的五種基本形態(tài) 二、二叉樹的兩個特殊形態(tài) ?? 1.滿二叉樹：如果一棵二叉樹的任何結(jié)點(diǎn)，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。（例如下圖(a)）可以驗(yàn)證具有n個葉結(jié)點(diǎn)的滿二叉樹共有2n-1個結(jié)點(diǎn)。 ?? 2.完全二叉樹：如果一棵二叉樹最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹（例如下圖(b)） ?? 三、二叉樹的三個主要性質(zhì) ? ?性質(zhì)1：在二叉樹的第i（≥1）層上，最多有 2i-1個結(jié)點(diǎn)。 ?? 性質(zhì)2：在深度為k(k≥1)的二叉樹中最多有2k-1個結(jié)點(diǎn)。 ?? 性質(zhì)3：在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。 二叉樹的性質(zhì) (1) 在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1)； (2) 深度為h的二叉樹最多有2^h-1個結(jié)點(diǎn)(h>=1)，最少有h個結(jié)點(diǎn)； (3) 對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2， 則N0=N2+1； (4) 具有n個結(jié)點(diǎn)的完全二叉樹的深度為int（log2n）+1 (5)有N個結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲，則結(jié)點(diǎn)之間有如下關(guān)系： 若I為結(jié)點(diǎn)編號則 如果I<>1，則其父結(jié)點(diǎn)的編號為I/2； 如果2*I<=N，則其左兒子（即左子樹的根結(jié)點(diǎn)）的編號為2*I；若2*I>N，則無左兒子； 如果2*I+1<=N，則其右兒子的結(jié)點(diǎn)編號為2*I+1；若2*I+1>N，則無右兒子。 (6)給定N個節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。 h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。 四、普通有序樹轉(zhuǎn)換成二叉樹 ?? 普通樹為有序樹T，將其轉(zhuǎn)化成二叉樹T’的規(guī)則如下： ??? ⑴ T中的結(jié)點(diǎn)與T’中的結(jié)點(diǎn)一一對應(yīng)，即T中每個結(jié)點(diǎn)的序號 和值在T’中保持不變； ??? ⑵ T中某結(jié)點(diǎn)v的第一個兒子結(jié)點(diǎn)為v1，則在T’中v1為對應(yīng)結(jié)點(diǎn)v的左兒子結(jié)點(diǎn)； ??? ⑶ T中結(jié)點(diǎn)v的兒子序列，在T’中被依次鏈接成一條開始于v1的右鏈； 由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹轉(zhuǎn)化成二叉樹的根結(jié)點(diǎn)是沒有右子樹的，并且除保留每個結(jié)點(diǎn)的最左分支外，其余分支應(yīng)去掉，然后從最左的兒子開始沿右兒子方向依次鏈接該結(jié)點(diǎn)的全部兒子。 五、森林轉(zhuǎn)換成二叉樹 ??? 如果m棵互不相交的普遍有序樹組成了森林F={T1，…Tm}。我們可以按下述規(guī)則將森林F轉(zhuǎn)換成一棵二叉樹b={R，LB，RB}： ??? ⑴ 若F為空（m=0），則b為空樹； ??? ⑵ 若F非空（m≠0），則b的根R即為森林中第一棵樹的根R(T1)；b的左子樹LB是從T1的根結(jié)點(diǎn)的子樹森林F1={T11，T12，…T1k}轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F2={T2，T3，…，Tm}轉(zhuǎn)換成的二叉樹。 第四節(jié) 二叉樹的遍歷 一、樹的存儲結(jié)構(gòu) ? ?1.順序存儲結(jié)構(gòu) ??? 將每個結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號，編號的方法是從根結(jié)點(diǎn)開始編號1，然后由左而右進(jìn)行連續(xù)編號。每個結(jié)點(diǎn)的信息包括 ?? ⑴ 一個數(shù)據(jù)域（data）； ?? ⑵ 三個指針域，其中有父結(jié)點(diǎn)編號（prt）、左兒子結(jié)點(diǎn)編號（lch）和右兒子結(jié)點(diǎn)編號（rch）。 滿二叉樹和完全二叉樹一般采用順序存儲結(jié)構(gòu)。 　 Const ? m=樹中結(jié)點(diǎn)數(shù)上限； Type ? node=record{結(jié)點(diǎn)類型} ??????? data：<數(shù)據(jù)類型>；{數(shù)據(jù)值} ??????? prt，lch，rch：0‥m； {父結(jié)點(diǎn)、左兒子、右兒子編號} ?????? end； ? treetype=array[1‥m] of node；{二叉樹的順序表類型} Var ? Tree：treetype；{二叉樹} ?? 2.鏈?zhǔn)酱鎯Y(jié)構(gòu) ??? 對于一般的二叉樹，通常采用鏈?zhǔn)椒峙?，即用二重鏈表表示一般的二叉樹。這種鏈?zhǔn)椒峙浼纯梢圆捎渺o態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)組），又可以采用動態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。如果二叉樹的存儲需求量超過64Kb，則采用后者。由于二叉樹中每個結(jié)點(diǎn)通常包括數(shù)據(jù)元素和兩個分支。因此二叉樹對應(yīng)的二重鏈表中每個結(jié)點(diǎn)應(yīng)有三個域： ?? ⑴ 值域： data ?? ⑵ 左指針域：lch ?? ⑶ 右指針域：rch ? 這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹的根結(jié)點(diǎn) 　 　 Type ? bitrpetr=^node；{結(jié)點(diǎn)指針類型} ? node=record{結(jié)點(diǎn)類型} ??????? data：<數(shù)據(jù)類型>；{值域} ??????? lch，rch：bitreptr；{左指針域和右指針域} ?????? end； Var ? bt：bitreptr；{頭指針} 　 二、二叉樹的遍歷 ??? 1.二叉樹遍歷的定義 ??? 按照一定的規(guī)律不重復(fù)地訪問(或取出結(jié)點(diǎn)中的信息，或?qū)Y(jié)點(diǎn)作其它的處理)二叉樹中的每一個結(jié)點(diǎn)。 ??? 2.二叉樹遍歷的順序 ??? 如果用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，則對二叉樹的遍歷可以有下列六種（3!=6）組合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（后序遍歷）、DLR（前序遍歷）。 ? 以下遍歷以該樹為例 三、前序遍歷 ??? 規(guī)則如下： ??? 若二叉樹為空，則退出。否則 ???? ⑴ 訪問處理根結(jié)點(diǎn)； ???? ⑵ 前序遍歷左子樹； ???? ⑶ 前序遍歷右子樹； ?? 如上圖的前序遍歷結(jié)果為 a b d e h i c f g 順序結(jié)構(gòu): Procedue preorder(i:integer); ?begin ? if i<>0 ?? then begin ??? 訪問處理tree[i].data; ??? preorder(tree[i].lch);{遞歸遍歷左子樹} ??? preorder(tree[i].rch);{遞歸遍歷右子樹} ?? end; ?end; 鏈?zhǔn)?