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

第一章 計(jì)算機(jī)基礎(chǔ)知識(shí) 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é) 存儲(chǔ)器系統(tǒng) 10 第三節(jié) 輸入輸出系統(tǒng) 11 第三章 網(wǎng)絡(luò)基礎(chǔ)知識(shí) 12 第一節(jié) 網(wǎng)絡(luò)的組成與結(jié)構(gòu) 12 第二節(jié) 網(wǎng)絡(luò)協(xié)議 13 第三節(jié) Internet相關(guān)知識(shí) 13 第三節(jié) Internet相關(guān)知識(shí) 14 第四章 其他相關(guān)基礎(chǔ)知識(shí) 15 第一節(jié) 計(jì)算機(jī)病毒 15 第二節(jié) 數(shù)據(jù)庫(kù)系統(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é) 樹(shù)的概念 19 第二節(jié) 樹(shù)的表示方法和存儲(chǔ)結(jié)構(gòu) 20 第三節(jié) 二叉樹(shù)的概念 22 第四節(jié) 二叉樹(shù)的遍歷 24 第五節(jié) 普通樹(shù)的遍歷 27 第六節(jié) 根據(jù)兩種遍歷順序確定樹(shù)結(jié)構(gòu) 28 第七節(jié) 二叉排序樹(shù) 29 第八節(jié) 最優(yōu)二叉樹(shù)(哈夫曼樹(shù)) 30 AOE網(wǎng) 32 第一章 計(jì)算機(jī)基礎(chǔ)知識(shí) 第一節(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)制對(duì)應(yīng)表 八進(jìn)制 二進(jìn)制 轉(zhuǎn)換方法:對(duì)二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每三位劃為一組， 不足三位補(bǔ)0，按上表用對(duì)應(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)制對(duì)應(yīng)表 十六進(jìn)制 二進(jìn)制 轉(zhuǎn)換方法:對(duì)二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每四位劃 為一組，不足四位補(bǔ)0，按上表用對(duì)應(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)制的英文表示法： 以上都是用括號(hào)加數(shù)字的表示方法，另外還有英文表示法，就是以BIN、OCT、HEX、DEC分別代表二、八、十六、十進(jìn)制?；蛘咧粚懙谝粋€(gè)字母。例如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)算符是在邏輯值或變量符號(hào)上加“—” = 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 ?? ⑧ 對(duì)合律 ????? 對(duì)一個(gè)邏輯變量?jī)纱稳》慈允撬旧? ?? ⑨ 德·摩根定理 ????? = · ??????= + 三、邏輯代數(shù)的應(yīng)用 1、邏輯表達(dá)式化簡(jiǎn) ?? 例如： F = ·＋A·＋A·B? ??????????=·＋A（＋B）???? （利用分配律） ??????????=·＋A???????????? （利用互補(bǔ)律以及0，1律） ????????? = A＋??????????????（利用吸收律） 2、對(duì)指定位進(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ù)號(hào)也是用二進(jìn)制表示的。用二進(jìn)制數(shù)表示符號(hào)的數(shù)稱為機(jī)器碼。常用的機(jī)器碼有原碼、反碼和補(bǔ)碼。 一、原碼 求原碼的方法：設(shè)X；若X≥0，則符號(hào)位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號(hào)位為1，其余各位照抄。 【例1】X=+1001001?? [X]原 = 01001001 【例2】X=-1001001?? [X]原 = 11001001 二、反碼 求反碼的方法：設(shè)X；若X≥0，則符號(hào)位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號(hào)位為1，其余各位按位取反。 【例3】X=+1001001?? [X]反 = 01001001 【例4】X=-1001001?? [X]反 = 10110110 三、補(bǔ)碼 求補(bǔ)碼的方法：設(shè)X；若X≥0，則符號(hào)位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號(hào)位為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)算器的位長(zhǎng)是固定的，上述運(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ǔ)的方法是：對(duì)補(bǔ)碼的每一位（包括符號(hào)位）求反，最后末位加“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ù)的表示范圍 ??? 通過(guò)上面的學(xué)習(xí)，我們就可以知道計(jì)算機(jī)如果用一個(gè)字節(jié)表示一個(gè)整數(shù)的時(shí)候，如果是無(wú)符號(hào)數(shù)，可以表示0~255共256個(gè)數(shù)（00000000~11111111），如果是有符號(hào)數(shù)則能表示-128~127共256個(gè)數(shù)（10000000~01111111）。如果兩個(gè)字節(jié)表示一個(gè)整數(shù)，則共有65536個(gè)數(shù)可以表示，大部分程序設(shè)計(jì)語(yǔ)言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號(hào)數(shù)，而且是補(bǔ)碼表示的。 第四節(jié) 浮點(diǎn)數(shù)的表示方法 一、浮點(diǎn)數(shù)表示 ??? 一個(gè)數(shù)的浮點(diǎn)形式（設(shè)基數(shù)是2）可寫成： ??????????????????? N = M × 2E ??? 其中:M代表尾數(shù),E代表階碼。 ??? 計(jì)算機(jī)中浮點(diǎn)數(shù)只用尾數(shù)和階碼表示，其形式如下： ??? 階碼 尾數(shù)符號(hào) 尾數(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ù)是否為零，通?？梢杂眯∮谀硞€(gè)極小值來(lái)代替。 三、實(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ù)左移一位（不包括符號(hào)位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼減1即可，否則繼續(xù)左移和調(diào)整階碼；若尾數(shù)大于1，則把尾數(shù)右移一位（不包括符號(hào)位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼加1即可，否則繼續(xù)右移和調(diào)整階碼。 上例中，00110左移一位為01100，符合規(guī)則化標(biāo)準(zhǔn)，此時(shí)階碼減1，為010即得到浮點(diǎn)表示形式。 ??? 這個(gè)數(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)行存儲(chǔ)和傳輸過(guò)程中可能會(huì)發(fā)生錯(cuò)誤。為了及時(shí)發(fā)現(xiàn)和糾正這類錯(cuò)誤，在數(shù)據(jù)傳輸（存儲(chǔ)）過(guò)程中要進(jìn)行校驗(yàn)，常用的校驗(yàn)方法就是奇偶校驗(yàn)。 ?? 奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)一位或奇數(shù)位錯(cuò)誤，且不能糾正錯(cuò)誤。一般以字節(jié)（八位二進(jìn)制）為單位加1位奇偶校驗(yàn)位。奇偶校驗(yàn)分奇校驗(yàn)和偶校驗(yàn)兩種。 一、奇校驗(yàn)：一個(gè)字節(jié)前面加一位校驗(yàn)位使得“1”的個(gè)數(shù)保持為奇數(shù)，若八位二進(jìn)制數(shù)中“1”的個(gè)數(shù)為偶數(shù)，則校驗(yàn)位為“1”；若八位二進(jìn)制數(shù)中“1”的個(gè)數(shù)為奇數(shù)，則校驗(yàn)位為“0”。 【例1】給1001100101101101加奇校驗(yàn)結(jié)果為110011001001101101 二、偶校驗(yàn)：一個(gè)字節(jié)前面加一位校驗(yàn)位使得“1”的個(gè)數(shù)保持為偶數(shù)，若八位二進(jìn)制數(shù)中“1”的個(gè)數(shù)為偶數(shù)，則校驗(yàn)位為“0”；若八位二進(jìn)制數(shù)中“1”的個(gè)數(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í)也被國(guó)際標(biāo)準(zhǔn)化組織（ International Organization for Standardization, ISO ）批準(zhǔn)為國(guó)際標(biāo)準(zhǔn)。 ??? 基本的 ASCII 字符集共有 128 個(gè)字符，其中有 96 個(gè)可打印字符，包括常用的字母、數(shù)字、標(biāo)點(diǎn)符號(hào)等，另外還有 32 個(gè)控制字符。標(biāo)準(zhǔn) ASCII 碼使用 7 個(gè)二進(jìn)位對(duì)字符進(jìn)行編碼，對(duì)應(yīng)的 ISO 標(biāo)準(zhǔn)為 ISO646 標(biāo)準(zhǔn)。下表展示了基本 ASCII 字符集及其編碼： ??? 字母和數(shù)字的 ASCII 碼的記憶是非常簡(jiǎn)單的。我們只要記住了一個(gè)字母或數(shù)字的 ASCII 碼（例如記住 A 為 65 ， 0 的 ASCII 碼為 48 ），知道相應(yīng)的大小寫字母之間差 32 ，就可以推算出其余字母、數(shù)字的 ASCII 碼。 ??? 雖然標(biāo)準(zhǔn) ASCII 碼是 7 位編碼，但由于計(jì)算機(jī)基本處理單位為字節(jié)（ 1byte = 8bit ），所以一般仍以一個(gè)字節(jié)來(lái)存放一個(gè) ASCII 字符。每一個(gè)字節(jié)中多余出來(lái)的一位（最高位）在計(jì)算機(jī)內(nèi)部通常保持為 0 （在數(shù)據(jù)傳輸時(shí)可用作奇偶校驗(yàn)位）。 由于標(biāo)準(zhǔn) ASCII 字符集字符數(shù)目有限，在實(shí)際應(yīng)用中往往無(wú)法滿足要求。為此，國(guó)際標(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 個(gè)字符，這些擴(kuò)充字符的編碼均為高位為 1 的 8 位代碼（即十進(jìn)制數(shù) 128~255 ），稱為擴(kuò)展 ASCII 碼。下表展示的是最流行的一套擴(kuò)展 ASCII 字符集和編碼： 第二章 計(jì)算機(jī)硬件基礎(chǔ) 第一節(jié) 中央處理器 一、中央處理器的組成 ??? 中央處理器簡(jiǎn)稱CPU，由控制器、運(yùn)算器組成。 ???運(yùn)算器及控制器的基本功能：運(yùn)算器是計(jì)算機(jī)進(jìn)行算術(shù)和邏輯運(yùn)算的部件，控制器是整個(gè)計(jì)算機(jī)中統(tǒng)一指揮和控制計(jì)算機(jī)各部件進(jìn)行工作的控制中心。 二、運(yùn)算器 ??? 運(yùn)算器是負(fù)責(zé)對(duì)數(shù)據(jù)進(jìn)行算術(shù)運(yùn)算或邏輯運(yùn)算的部件。運(yùn)算器由算術(shù)邏輯單元（ALU）、累加器、狀態(tài)寄存器、通用寄存器組等組成。如圖：????? ??? 算術(shù)邏輯運(yùn)算單元、累加器和通用寄存器的位數(shù)決定了CPU的字長(zhǎng)。 三、控制器 ??? 是計(jì)算機(jī)的指令執(zhí)行部件，其工作是取指令、解釋指令以及完成指令的執(zhí)行。 ??? 控制器由指令指針寄存器、指令寄存器、控制邏輯電路和時(shí)鐘控制電路等組成。 ??? 指令指針寄存器（IP）用于?? 產(chǎn)生及存放一條待取指令的地址。 ??? 指令寄存器用于存放指令。指令從內(nèi)存取出后放入指令寄存器。 四、寄存器 ??? 寄存器數(shù)量增多可以提高CPU運(yùn)行速度，但是不能太多，太多會(huì)使地址編碼和指令長(zhǎng)度變長(zhǎng)，增加復(fù)雜度。由累加器、通用寄存器組、狀態(tài)寄存器、指令寄存器、地址寄存器、其他寄存器等組成。 五、指令基本格式 ??? 單目運(yùn)算：操作碼 地址碼 ??? 二目運(yùn)算：操作碼 第一地址 第二地址 六、尋址方式：CPU執(zhí)行指令時(shí)尋找數(shù)據(jù)地址的方式 ?? 1、立即尋址：ADD AH,78? 其中ADD是操作碼，表示做加法；AH是寄存器名；78是個(gè)常數(shù)；該指令的意思是寄存器AH的值加上78。 ?? 2、直接尋址：ADD AH,(78)? 78表示操作數(shù)的地址 ?? 3、間接尋址：ADD AH,((78))? 78表示操作數(shù)地址的地址 ?? 4、相對(duì)尋址：ADD AH,*78?? *78表示本指令地址+78，78稱偏移量 ?? 5、變址尋址：ADD AH,(DI+78) DI是變址寄存器,存放一個(gè)地址,操作數(shù)地址是寄存器地址+78 ?? 6、寄存器直接尋址:ADD AH,78? AH是一個(gè)寄存器名,即寄存器直接尋址 ?? 7、寄存器直接尋址:ADD AH,(BX)? BX是一個(gè)寄存器名,存放操作數(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í)行過(guò)程 ?? 1、CPU發(fā)出指令地址 ?? 2、讀取指令 ?? 3、指令送指令寄存器 ?? 4、指令譯碼 ?? 5、按指令操作碼執(zhí)行 ?? 6、形成下條要執(zhí)行的指令的地址 九、時(shí)鐘周期 ??? 一個(gè)指令執(zhí)行的時(shí)間稱為指令周期 ??? 計(jì)算機(jī)完成一個(gè)操作（如讀取指令等）所需時(shí)間稱為總線周期 ??? 計(jì)算機(jī)中最基本的時(shí)間單位是時(shí)鐘周期，有CPU的主頻決定。 第二節(jié) 存儲(chǔ)器系統(tǒng) 一、存儲(chǔ)器的分類 分類方法 名稱 舉例 按存儲(chǔ)介質(zhì)分 半導(dǎo)體存儲(chǔ)器 ROM、RAM（內(nèi)存）、閃存（優(yōu)盤） 磁表面存儲(chǔ)器 硬盤、軟盤、磁帶 光存儲(chǔ)器 CD-ROM、DVD-ROM 按工作方式分 隨機(jī)存儲(chǔ)器 RAM（內(nèi)存）、硬盤、軟盤 只讀存儲(chǔ)器 ROM、CD-ROM 順序存儲(chǔ)器 磁帶 二、多層次存儲(chǔ)體系: 如圖 三、主存儲(chǔ)器 ??? 1、特點(diǎn)：容量小、讀寫速度快、價(jià)格高 ??? 2、編址方式：存儲(chǔ)容量與地址線條數(shù)相對(duì)應(yīng)，64M的存儲(chǔ)器至少需要26跟地址線（226=64M） ??? 注：我們目前的計(jì)算機(jī)大都是32位，也就是地址線條數(shù)有32條，所以其支持的最大內(nèi)存容量為4G ??? 3、分類： ??? ① 隨機(jī)存儲(chǔ)器（RAM）：就是我們通常稱的內(nèi)存，主要參數(shù)是存儲(chǔ)容量和工作頻率。 ?????? 例如：一條64M×8的內(nèi)存條表示該內(nèi)存條有64M個(gè)單元，每個(gè)單元8位。 ??? ② 只讀存儲(chǔ)器（ROM）：只能讀不能寫，一般用于存放計(jì)算機(jī)啟動(dòng)所需的最基本程序。 ??? ③ 緩沖存儲(chǔ)器（Cache）：速度最快，一般集成于CPU中。 四、輔助存儲(chǔ)器 ?? 1、磁帶：順序存儲(chǔ)，一般只用在小型機(jī)以上的計(jì)算機(jī)中，用作數(shù)據(jù)備份。 ?? 2、軟盤：目前常見(jiàn)的一般為3.5寸高密盤，容量為1.44MB，軟盤結(jié)構(gòu)如圖 ????? 注意：盤面最外層的磁道稱為0磁道，0磁道如果損壞，則盤片報(bào)廢。 ?? 3、硬盤：硬盤由多個(gè)盤面組成一個(gè)柱形結(jié)構(gòu)，其原來(lái)跟軟盤類似，但是磁道更多。 ?? 4、光盤：利用光信號(hào)讀取或?qū)懭氲拇鎯?chǔ)器。 ????? ① 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) ????? 中斷請(qǐng)求-->中斷響應(yīng)-->中斷處理-->中斷返回 ?? 3、直接存儲(chǔ)器訪問(wèn)方式（DMA）：硬件實(shí)現(xiàn) ????? DMA請(qǐng)求-->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)知識(shí) ??? 1、屏幕尺寸：15寸、17寸、19寸等 ??? 2、點(diǎn)間距：屏幕上象素與象素之間的距離，決定了顯示器能顯示的最大分辨率。 越小表示能顯示的最大分辨率越大。 五、打印機(jī)：針式打印機(jī)、噴墨打印機(jī)、激光打印機(jī)。 ??? 激光打印機(jī)速度最快，針式打印機(jī)可以打印票據(jù)。 第三章 網(wǎng)絡(luò)基礎(chǔ)知識(shí) 第一節(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)型、樹(shù)型 三、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 第二節(jié) 網(wǎng)絡(luò)協(xié)議 第 33 頁(yè) 共 33 頁(yè) 應(yīng)用層 表達(dá)層 會(huì)話層 傳輸層 網(wǎng)絡(luò)層 數(shù)據(jù)鏈路層 物理層 一、OSI網(wǎng)絡(luò)協(xié)議的層次 國(guó)際標(biāo)準(zhǔn)化組織（ISO）提出的“開(kāi)放系統(tǒng)互連模型（OSI）” 是計(jì)算機(jī)網(wǎng)絡(luò)通信的基本協(xié)議。 該協(xié)議分為七層。如下表 二、網(wǎng)絡(luò)設(shè)備極其作用 第三節(jié) Internet相關(guān)知識(shí) 一、IP地址 ??? 每臺(tái)與Internet連接的主機(jī)都必須有一個(gè)IP地址，IP地址采用分段式表示：共分4段，每段用一個(gè)字節(jié)即八個(gè)二進(jìn)制位表示，實(shí)際的IP把二進(jìn)制轉(zhuǎn)換成十進(jìn)制書寫。如61.153.238.132，因?yàn)槊慷螘r(shí)一個(gè)字節(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是樹(shù)形結(jié)構(gòu)的。 域名跟IP地址是多對(duì)一的關(guān)系 ??? 1、域名分級(jí)系統(tǒng)：一個(gè)域名最右邊的部分通常叫頂級(jí)域名，往前依次為二級(jí)域名、三級(jí)域名等。 ??? 2、我國(guó)域名管理機(jī)構(gòu):CNNIC ??? 3、常見(jiàn)域名含義： ??? gov 政府 edu 教育 int 國(guó)際組織 com 商業(yè)組織 mil 軍事部門 net 網(wǎng)絡(luò)運(yùn)行? org 其他組織 ??? cn 中國(guó)? hk 香港? tw 臺(tái)灣? uk 英國(guó) jp 日本 三、一些常見(jiàn)名詞解釋 ??? 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撥號(hào)接入：必須設(shè)備MODEM，電話線，速度慢 ??? 2、DDN專線接入：速度快，費(fèi)用高。 ??? 3、ISDN專線接入：利用傳統(tǒng)電話網(wǎng)絡(luò)的綜合業(yè)務(wù)數(shù)字網(wǎng)。 ??? 4、分組交換接入 ??? 5、幀中繼接入 第四章 其他相關(guān)基礎(chǔ)知識(shí) 第一節(jié) 計(jì)算機(jī)病毒 一、特點(diǎn) ??? 寄生性、隱蔽性、非法性、傳染性、破壞性 二、分類： ??? 1、引導(dǎo)型病毒：寄生在系統(tǒng)引導(dǎo)區(qū)，比較容易被清除，現(xiàn)在已經(jīng)很少見(jiàn)。 ??? 2、文件型病毒：寄生在可執(zhí)行文件中，感染速度快，較易清除。 ??? 3、目錄型病毒：寄生在系統(tǒng)目錄結(jié)構(gòu)中 ??? 4、混合型病毒：多種類型的混合 ??? 5、宏病毒：專門感染Microsoft Office 系列文件的病毒 ??? 6、蠕蟲病毒：感染網(wǎng)絡(luò)，使網(wǎng)速大大降低。 ??? 目前流行的病毒大多集成了黑客技術(shù)、木馬技術(shù)和病毒技術(shù)三種，非常難以清除而且很容易中。 三、一些常見(jiàn)危害較大的病毒 ??? 1、CIH病毒:文件型病毒，4月26日發(fā)作時(shí)破壞性最大，首個(gè)能破壞硬件系統(tǒng)的病毒。 ??? 2、Melissa病毒：宏病毒，郵件傳播 ??? 3、沖擊波、震蕩波病毒：利用WINDOWS的漏洞，使計(jì)算機(jī)自動(dòng)重啟并堵塞網(wǎng)絡(luò)。 第二節(jié) 數(shù)據(jù)庫(kù)系統(tǒng) 一、數(shù)據(jù)庫(kù)是數(shù)據(jù)的一種組織形式，目前存儲(chǔ)大量數(shù)據(jù)基本都采用數(shù)據(jù)庫(kù) ?? 常見(jiàn)的數(shù)據(jù)庫(kù)軟件有：FoxBase、FoxPro、Access、Sql Server、MySql、Sybase、Oracel等。除了最早的如FoxBase等軟件，目前流行的數(shù)據(jù)庫(kù)軟件都是關(guān)系型數(shù)據(jù)庫(kù)。 二、數(shù)據(jù)庫(kù)數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)可以認(rèn)為是多張二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖 ??? 二、數(shù)據(jù)操作 ??? 用以對(duì)數(shù)據(jù)庫(kù)進(jìn)行檢索和更新（添加、刪除、更新等）操作?? 三、數(shù)據(jù)的完整性約束條件 ?? 多個(gè)表之間的數(shù)據(jù)可能存在相互關(guān)聯(lián)，必須保證其完整性 四、數(shù)據(jù)庫(kù)操作語(yǔ)言SQL ??? 數(shù)據(jù)庫(kù)常用的操作語(yǔ)言稱為SQL語(yǔ)言，是一種更高級(jí)化的語(yǔ)言，只須告訴計(jì)算機(jī)做什么事情即可。下面例舉幾條常用的語(yǔ)句。 ??? 1、SELECT 語(yǔ)句 ??? 語(yǔ)法：select <列名> from <表名> where <條件> ??? 功能：從表中選出滿足條件的記錄列 ??? 2、INSERT 語(yǔ)句 ??? 語(yǔ)法：insert into <表名>[(列名表)] values(<值表>) ??? 功能：在表中插入一條新記錄。 ??? 3、DELETE 語(yǔ)句 ??? 語(yǔ)法：delete * from <表名> where <條件> ??? 功能：刪除滿足條件的記錄 ??? 4、UPDATE 語(yǔ)句 ??? 語(yǔ)法：update <表名>? set <列名>=<值> where <條件> 功能：修改滿足條件的表中某記錄某字段的值? 第五章 數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu) 第一節(jié) 線性表 一、概念 ??? 線性表是指由有限個(gè)類型相同的數(shù)據(jù)元素組成的集合，它有以下的特點(diǎn)： ??? 1.有唯一的頭結(jié)點(diǎn)(即第一個(gè)數(shù)據(jù)元素)和尾結(jié)點(diǎn)(即最后一個(gè)數(shù)據(jù)元素)； ??? 2.除結(jié)點(diǎn)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)； ??? 3.除尾結(jié)點(diǎn)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。 二、線性表的存儲(chǔ)結(jié)構(gòu) ??? 1、順序結(jié)構(gòu)：是通過(guò)數(shù)組說(shuō)明分配連續(xù)地址的存儲(chǔ)區(qū)，通過(guò)下標(biāo)引用數(shù)組的相應(yīng)元素。 ??? 2、鏈?zhǔn)浇Y(jié)構(gòu)：通過(guò)指引元素類型的變量對(duì)線性表中元素進(jìn)行動(dòng)態(tài)分配存儲(chǔ)。 三、順序存儲(chǔ)結(jié)構(gòu) ?? 1、一維數(shù)組 ?? ① 數(shù)組存儲(chǔ)的結(jié)構(gòu)在數(shù)組聲明時(shí)就需要事先分配相應(yīng)的連續(xù)內(nèi)存空間用來(lái)存放數(shù)據(jù)。 ?? ② 按首地址（表中第一個(gè)元素的地址）的位移來(lái)訪問(wèn)數(shù)組每一個(gè)元素的。 ?? 若第一個(gè)元素的地址是a，每個(gè)元素占用的存儲(chǔ)空間為L(zhǎng)，則數(shù)組的第i個(gè)元素的地址可以用如下公式計(jì)算： ?????????????????????? d(i)=a+(i-1)*L ?? 2、二維數(shù)組 ?? ① 定義方法：<數(shù)組名>:array[1..n,1..m] of <元素類型> ?? ② 對(duì)于行為n，列為m的二維數(shù)組的元素訪問(wèn)方法： 若第一個(gè)元素的地址是a，每個(gè)元素占用的存儲(chǔ)空間為L(zhǎng)，則數(shù)組的第(i,j)個(gè)元素的地址可以用如下公式計(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)酱鎯?chǔ)結(jié)構(gòu)　 ??? 鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù)部分存放結(jié)點(diǎn)的有關(guān)信息，指針部分存放下一個(gè)結(jié)點(diǎn)的位置。 ??? 優(yōu)點(diǎn)：可根據(jù)需要分配數(shù)據(jù)元素的存儲(chǔ)區(qū)，也可隨時(shí)撤消鏈表中數(shù)據(jù)元素的存儲(chǔ)區(qū)，插入刪除操作只須改變指針，無(wú)須移動(dòng)數(shù)據(jù)。 ??? 缺點(diǎn)：它的數(shù)據(jù)元素必須在數(shù)據(jù)項(xiàng)以外至少增加一個(gè)指向后繼元素的指針類型的數(shù)據(jù)項(xiàng)，查找其中的某個(gè)元素時(shí)必須中從第一個(gè)元素開(kāi)始逐個(gè)往后找。 一個(gè)實(shí)例： Type ?pointer=^node; ?node=Record; ?????? data:real; ?????? next:pointer; ????? End; Var ? head,next:pointer; ? ? 1.Head為表的首指針，指向鏈表的第一個(gè)結(jié)點(diǎn)。 ? 2.整個(gè)鏈表的存取必須從head指針出發(fā)，沿著每個(gè)結(jié)點(diǎn)的next指針順序進(jìn)行，最后個(gè)結(jié)點(diǎn)的next指針為“空”（nil）. 第二節(jié) 棧 一、棧的概念 ?? 棧是一種線性表，對(duì)它的插入和刪除操作都限制在表的同一端進(jìn)行。這一端叫做棧頂，另一個(gè)端叫做棧底。 棧又被成為“后進(jìn)先出表”（LIFO）。 ?? 定義方法： ?? Const ???? m=棧元素的上限； ?? Type ???? stack=array[1..m] of <元素類型> ?? Var ???? s:stack; ???? t:integer; 二、棧的基本運(yùn)算 　? 1.入棧：過(guò)程push(x)，往棧s中壓入一個(gè)元素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中彈出一個(gè)元素。 　 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ì)抽象出來(lái)的，根據(jù)排隊(duì)的原則“先來(lái)先服務(wù)”。 所謂隊(duì)列就是允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一個(gè)隊(duì)尾指針r指向隊(duì)尾元素；允許刪除的一端稱為隊(duì)首，通常也用一個(gè)隊(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.過(guò)程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.過(guò)程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ù)的概念 一、樹(shù)的定義 ??? 樹(shù)是一種常見(jiàn)的非線性的數(shù)據(jù)結(jié)構(gòu)。 ??? 樹(shù)的定義：樹(shù)是n(n>0)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件： ??? ⑴ 有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹(shù)的根； ??? ⑵ 除根外，其余的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)； ??? ⑶ 除根外，每一個(gè)結(jié)點(diǎn)都通過(guò)唯一的路徑連到根上。這條路徑由根開(kāi)始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后驅(qū)（兒子結(jié)點(diǎn)）； 二、結(jié)點(diǎn)的分類 ??? 在樹(shù)中，一個(gè)結(jié)點(diǎn)包含一個(gè)元素以及所有指向其子樹(shù)的分支。 ??? 結(jié)點(diǎn)一般分成三類: ??? ⑴ 根結(jié)點(diǎn)：沒(méi)有前驅(qū)的結(jié)點(diǎn)。在樹(shù)中有且僅有一個(gè)根結(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)亦是其子樹(shù)的根； ??? ⑶ 葉結(jié)點(diǎn)：沒(méi)有后驅(qū)的結(jié)點(diǎn)稱為樹(shù)葉。如上圖（b）中的w，h，e，f，s，m，o，n，j，u為葉結(jié)點(diǎn)。由樹(shù)的定義可知，樹(shù)葉本身也是其父結(jié)點(diǎn)的子樹(shù)。 根結(jié)點(diǎn)到每一個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。例如上圖（b）中，從根r到結(jié)點(diǎn)i的唯一路徑為rcti。 三、有關(guān)度的定義 ??? ⑴ 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱為該結(jié)點(diǎn)的度。在上圖（b）中，結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1。顯然，所有樹(shù)葉的度為0。 ??? ⑵ 樹(shù)的度：所有結(jié)點(diǎn)中最大的度稱為該樹(shù)的度。圖（b）中的樹(shù)的度為3。 四、樹(shù)的深度（高度） ??? 樹(shù)是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的后件在第二層，其余各層依次類推。即若某個(gè)結(jié)點(diǎn)在第k層，則該結(jié)點(diǎn)的后件均處在第k+1層。 ??? 圖（b）中的樹(shù)共有五層。在樹(shù)中，父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。樹(shù)中最大的層次稱為樹(shù)的深度，亦稱高度。圖（b）中樹(shù)的深度為5。 五、森林 ??? 所謂森林，是指若干棵互不相交的樹(shù)的集合。 ??? 如圖（b）去掉根結(jié)點(diǎn)r，其原來(lái)的三棵子樹(shù)Ta，Tb，Tc的集合{Ta，Tb，Tc}就為森林，這三棵子樹(shù)的具體形態(tài)如圖（c）。? 六、有序樹(shù)和無(wú)序樹(shù) ??? 按照樹(shù)中同層結(jié)點(diǎn)是否保持有序性，可將樹(shù)分為有序樹(shù)和無(wú)序樹(shù)。如果樹(shù)中同層結(jié)點(diǎn)從左而右排列，其次序不容互換，這樣的樹(shù)稱為有序樹(shù)；如果同層結(jié)點(diǎn)的次序任意，這樣的樹(shù)稱為無(wú)序樹(shù)。 第二節(jié) 樹(shù)的表示方法和存儲(chǔ)結(jié)構(gòu) 一、樹(shù)的表示方法 ??? 樹(shù)的表示方法一般有兩種： ??? ⑴ 自然界的樹(shù)形表示法：用結(jié)點(diǎn)和邊表示樹(shù)，例如下圖采用的就是自然界的樹(shù)形表示法。樹(shù)形表示法一般用于分析問(wèn)題。 ?? ?⑵ 括號(hào)表示法：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)按由左而右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣方法處理：同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。例如下圖(b)可寫成如下形式 （r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u））） 二、樹(shù)的存儲(chǔ)結(jié)構(gòu) ??? 樹(shù)的存儲(chǔ)結(jié)構(gòu)一般有兩種 ??? 1.靜態(tài)的記錄數(shù)組 ??? 所有結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長(zhǎng)度為n(n為樹(shù)的度)的數(shù)組，分別存儲(chǔ)該結(jié)點(diǎn)的每一個(gè)兒子的下標(biāo)。 Const ? n=樹(shù)的度； ? 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.動(dòng)態(tài)的多重鏈表 ??? 由于樹(shù)中結(jié)點(diǎn)可以有多個(gè)元素，所以可以用多重鏈表來(lái)描述比較方便。所謂多重鏈表，就是每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和n(n 為樹(shù)的度)個(gè)指針域共n+1個(gè)域組成，其表示方法如下： ? 　 Const ? n=樹(shù)的度； Type ? treetype=^node； ? node=record ??????? data：datatype；{數(shù)據(jù)域} ??????? next：array[1‥n] of treetype；{指向各兒子的指針域} ?????? end； Var ? root：treetype； 　 上圖用多重鏈表表示如下： 第三節(jié) 二叉樹(shù)的概念 一、二叉樹(shù)的遞歸定義和基本形態(tài) ??? 1.二叉樹(shù)是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)后繼，且其子樹(shù)有左右之分（次序不能任意顛倒）。 ??? 2.二叉樹(shù)是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件： ??? ⑴ 有一個(gè)特定的結(jié)點(diǎn)稱為根； ??? ⑵ 余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹(shù)；R是根的右子樹(shù)；L和R又是二叉樹(shù)； ?? 由上述定義可以看出，二叉樹(shù)和樹(shù)是兩個(gè)不同的概念: ??? ⑴ 樹(shù)的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)后繼，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)的后繼不能超過(guò)2； ??? ⑵ 樹(shù)的子樹(shù)可以不分次序（除有序樹(shù)外）；而二叉樹(shù)的子樹(shù)有左右之分。我們稱二叉樹(shù)中結(jié)點(diǎn)的左后繼為左兒子，右后繼為右兒子。 ??? 3.二叉樹(shù)的五種基本形態(tài) 二、二叉樹(shù)的兩個(gè)特殊形態(tài) ?? 1.滿二叉樹(shù)：如果一棵二叉樹(shù)的任何結(jié)點(diǎn)，或者是樹(shù)葉，或者恰有兩棵非空子樹(shù)，則此二叉樹(shù)稱作滿二叉樹(shù)。（例如下圖(a)）可以驗(yàn)證具有n個(gè)葉結(jié)點(diǎn)的滿二叉樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。 ?? 2.完全二叉樹(shù)：如果一棵二叉樹(shù)最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹(shù)為完全二叉樹(shù)（例如下圖(b)） ?? 三、二叉樹(shù)的三個(gè)主要性質(zhì) ? ?性質(zhì)1：在二叉樹(shù)的第i（≥1）層上，最多有 2i-1個(gè)結(jié)點(diǎn)。 ?? 性質(zhì)2：在深度為k(k≥1)的二叉樹(shù)中最多有2k-1個(gè)結(jié)點(diǎn)。 ?? 性質(zhì)3：在任何二叉樹(shù)中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。 二叉樹(shù)的性質(zhì) (1) 在二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò)2^(i-1)； (2) 深度為h的二叉樹(shù)最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)； (3) 對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2， 則N0=N2+1； (4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）+1 (5)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系： 若I為結(jié)點(diǎn)編號(hào)則 如果I<>1，則其父結(jié)點(diǎn)的編號(hào)為I/2； 如果2*I<=N，則其左兒子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2*I；若2*I>N，則無(wú)左兒子； 如果2*I+1<=N，則其右兒子的結(jié)點(diǎn)編號(hào)為2*I+1；若2*I+1>N，則無(wú)右兒子。 (6)給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹(shù)。 h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。 四、普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù) ?? 普通樹(shù)為有序樹(shù)T，將其轉(zhuǎn)化成二叉樹(shù)T’的規(guī)則如下： ??? ⑴ T中的結(jié)點(diǎn)與T’中的結(jié)點(diǎn)一一對(duì)應(yīng)，即T中每個(gè)結(jié)點(diǎn)的序號(hào) 和值在T’中保持不變； ??? ⑵ T中某結(jié)點(diǎn)v的第一個(gè)兒子結(jié)點(diǎn)為v1，則在T’中v1為對(duì)應(yīng)結(jié)點(diǎn)v的左兒子結(jié)點(diǎn)； ??? ⑶ T中結(jié)點(diǎn)v的兒子序列，在T’中被依次鏈接成一條開(kāi)始于v1的右鏈； 由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的根結(jié)點(diǎn)是沒(méi)有右子樹(shù)的，并且除保留每個(gè)結(jié)點(diǎn)的最左分支外，其余分支應(yīng)去掉，然后從最左的兒子開(kāi)始沿右兒子方向依次鏈接該結(jié)點(diǎn)的全部?jī)鹤印? 五、森林轉(zhuǎn)換成二叉樹(shù) ??? 如果m棵互不相交的普遍有序樹(shù)組成了森林F={T1，…Tm}。我們可以按下述規(guī)則將森林F轉(zhuǎn)換成一棵二叉樹(shù)b={R，LB，RB}： ??? ⑴ 若F為空（m=0），則b為空樹(shù)； ??? ⑵ 若F非空（m≠0），則b的根R即為森林中第一棵樹(shù)的根R(T1)；b的左子樹(shù)LB是從T1的根結(jié)點(diǎn)的子樹(shù)森林F1={T11，T12，…T1k}轉(zhuǎn)換而成的二叉樹(shù)；其右子樹(shù)RB是從森林F2={T2，T3，…，Tm}轉(zhuǎn)換成的二叉樹(shù)。 第四節(jié) 二叉樹(shù)的遍歷 一、樹(shù)的存儲(chǔ)結(jié)構(gòu) ? ?1.順序存儲(chǔ)結(jié)構(gòu) ??? 將每個(gè)結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號(hào)，編號(hào)的方法是從根結(jié)點(diǎn)開(kāi)始編號(hào)1，然后由左而右進(jìn)行連續(xù)編號(hào)。每個(gè)結(jié)點(diǎn)的信息包括 ?? ⑴ 一個(gè)數(shù)據(jù)域（data）； ?? ⑵ 三個(gè)指針域，其中有父結(jié)點(diǎn)編號(hào)（prt）、左兒子結(jié)點(diǎn)編號(hào)（lch）和右兒子結(jié)點(diǎn)編號(hào)（rch）。 滿二叉樹(shù)和完全二叉樹(shù)一般采用順序存儲(chǔ)結(jié)構(gòu)。 　 Const ? m=樹(shù)中結(jié)點(diǎn)數(shù)上限； Type ? node=record{結(jié)點(diǎn)類型} ??????? data：<數(shù)據(jù)類型>；{數(shù)據(jù)值} ??????? prt，lch，rch：0‥m； {父結(jié)點(diǎn)、左兒子、右兒子編號(hào)} ?????? end； ? treetype=array[1‥m] of node；{二叉樹(shù)的順序表類型} Var ? Tree：treetype；{二叉樹(shù)} ?? 2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ??? 對(duì)于一般的二叉樹(shù)，通常采用鏈?zhǔn)椒峙?，即用二重鏈表表示一般的二叉?shù)。這種鏈?zhǔn)椒峙浼纯梢圆捎渺o態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)組），又可以采用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。如果二叉樹(shù)的存儲(chǔ)需求量超過(guò)64Kb，則采用后者。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)通常包括數(shù)據(jù)元素和兩個(gè)分支。因此二叉樹(shù)對(duì)應(yīng)的二重鏈表中每個(gè)結(jié)點(diǎn)應(yīng)有三個(gè)域： ?? ⑴ 值域： data ?? ⑵ 左指針域：lch ?? ⑶ 右指針域：rch ? 這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹(shù)的根結(jié)點(diǎn) 　 　 Type ? bitrpetr=^node；{結(jié)點(diǎn)指針類型} ? node=record{結(jié)點(diǎn)類型} ??????? data：<數(shù)據(jù)類型>；{值域} ??????? lch，rch：bitreptr；{左指針域和右指針域} ?????? end； Var ? bt：bitreptr；{頭指針} 　 二、二叉樹(shù)的遍歷 ??? 1.二叉樹(shù)遍歷的定義 ??? 按照一定的規(guī)律不重復(fù)地訪問(wèn)(或取出結(jié)點(diǎn)中的信息，或?qū)Y(jié)點(diǎn)作其它的處理)二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)。 ??? 2.二叉樹(shù)遍歷的順序 ??? 如果用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，則對(duì)二叉樹(shù)的遍歷可以有下列六種（3!=6）組合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（后序遍歷）、DLR（前序遍歷）。 ? 以下遍歷以該樹(shù)為例 三、前序遍歷 ??? 規(guī)則如下： ??? 若二叉樹(shù)為空，則退出。否則 ???? ⑴ 訪問(wèn)處理根結(jié)點(diǎn)； ???? ⑵ 前序遍歷左子樹(shù)； ???? ⑶ 前序遍歷右子樹(shù)； ?? 如上圖的前序遍歷結(jié)果為 a b d e h i c f g 順序結(jié)構(gòu): Procedue preorder(i:integer); ?begin ? if i<>0 ?? then begin ??? 訪問(wèn)處理tree[i].data; ??? preorder(tree[i].lch);{遞歸遍歷左子樹(shù)} ??? preorder(tree[i].rch);{遞歸遍歷右子樹(shù)} ?? end; ?end; 鏈?zhǔn)?