信息學(xué)奧賽-計算機基礎(chǔ)知識(完整版)資料

信息學(xué)奧賽-計算機基礎(chǔ)知識（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

信息學(xué)奧賽-計算機基礎(chǔ)知識（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）第一章計算機基礎(chǔ)知識 2第一節(jié)數(shù)制及其轉(zhuǎn)換 2第二節(jié)算術(shù)運算和邏輯運算 3第三節(jié)原碼、反碼和補碼 5第四節(jié)浮點數(shù)的表示方法 6第五節(jié)奇偶校驗 7第六節(jié)ASCII碼表 8第二章計算機硬件基礎(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é)計算機病毒 15第二節(jié)數(shù)據(jù)庫系統(tǒng) 15第五章數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu) 16第一節(jié)線性表 16第二節(jié)棧 17第三節(jié)隊列 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)二叉樹(哈夫曼樹) 30AOE網(wǎng) 32

第一章計算機基礎(chǔ)知識第一節(jié)數(shù)制及其轉(zhuǎn)換一、二、八、十六進制轉(zhuǎ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二、十進制化二進制的方法：整數(shù)部分除二取余法，小數(shù)部分乘二取整法。例一：（43）10=（101011）2例二：（0.375）10=（0.011）2三、二進制轉(zhuǎn)八進制的方法一位數(shù)八進制與二進制對應(yīng)表八進制二進制轉(zhuǎn)換方法:對二進制以小數(shù)點為分隔，往前往后每三位劃為一組，不足三位補0，按上表用對應(yīng)的八進制數(shù)字代入即可。例如：(10111011.01100111)=010,111,011.011,001,110=（273.36）800001001201030114100510161107111三、二進制轉(zhuǎn)十六進制的方法一位數(shù)十六進制與二進制對應(yīng)表十六進制二進制轉(zhuǎn)換方法:對二進制以小數(shù)點為分隔，往前往后每四位劃為一組，不足四位補0，按上表用對應(yīng)的十六進制數(shù)字代入即可。例如：(10111011.01100111)=1011,1011.0110,0111=（BB.67）1600000100012001030011401005010160110701118100091001A1010B1011C1100D1101E1110F1111四、進制的英文表示法：以上都是用括號加數(shù)字的表示方法，另外還有英文表示法，就是以BIN、OCT、HEX、DEC分別代表二、八、十六、十進制?；蛘咧粚懙谝粋€字母。例如1101B表示是二進制。有些地方為了避免“O”跟“0”混淆，把O寫成Q。第二節(jié)算術(shù)運算和邏輯運算一、二進制的算術(shù)運算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

③結(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

⑥互補律

A+=1

A·=0

⑦吸收律

A＋A·B=A

A·（A＋B）=A

A＋·B=A＋B

A·（＋B）=A·B

⑧對合律

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

⑨德·摩根定理

=·

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

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

=·＋A（＋B）

（利用分配律）

=·＋A

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

=A＋

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

①將變量A的d5位清零

A·（11011111）→A

②將變量A的各位置1

A＋（11111111）→A

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

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

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

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

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

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

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

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

計算機中實際上只有加法，減法運算轉(zhuǎn)換成加法運算進行，乘法運算轉(zhuǎn)換成加法運算進行，除法運算轉(zhuǎn)換成減法運算進行。用補碼可以很方便的進行這種運算。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)生的最高位進位將丟掉，所以結(jié)果不是

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ù)的表示范圍

通過上面的學(xué)習，我們就可以知道計算機如果用一個字節(jié)表示一個整數(shù)的時候，如果是無符號數(shù)，可以表示0~255共256個數(shù)（00000000~11111111），如果是有符號數(shù)則能表示-128~127共256個數(shù)（10000000~01111111）。如果兩個字節(jié)表示一個整數(shù)，則共有65536個數(shù)可以表示，大部分程序設(shè)計語言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(shù)，而且是補碼表示的。第四節(jié)浮點數(shù)的表示方法一、浮點數(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ù)應(yīng)該是01XXXX的形式；若尾數(shù)小于零，則規(guī)格化數(shù)應(yīng)為10XXXX的形式。二、機器零

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

奇偶校驗?zāi)馨l(fā)現(xiàn)一位或奇數(shù)位錯誤，且不能糾正錯誤。一般以字節(jié)（八位二進制）為單位加1位奇偶校驗位。奇偶校驗分奇校驗和偶校驗兩種。一、奇校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為奇數(shù)，若八位二進制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“1”；若八位二進制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“0”?！纠?】給11101加奇校驗結(jié)果為1001101101二、偶校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為偶數(shù)，若八位二進制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“0”；若八位二進制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“1”?！纠?】給11101加偶校驗結(jié)果為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個二進位對字符進行編碼，對應(yīng)的ISO標準為ISO646標準。下表展示了基本ASCII字符集及其編碼：

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

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

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

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

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

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

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

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

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

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

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

寄存器數(shù)量增多可以提高CPU運行速度，但是不能太多，太多會使地址編碼和指令長度變長，增加復(fù)雜度。由累加器、通用寄存器組、狀態(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ù)處理指令:算術(shù)運算、邏輯運算、移位、比較等

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

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

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

2、讀取指令

3、指令送指令寄存器

4、指令譯碼

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

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

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

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

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

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

2、編址方式：存儲容量與地址線條數(shù)相對應(yīng)，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，軟盤結(jié)構(gòu)如圖

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

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

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、中斷方式：軟硬件結(jié)合實現(xiàn)

中斷請求-->中斷響應(yīng)-->中斷處理-->中斷返回

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

DMA請求-->CPU響應(yīng)并把總線控制權(quán)交給DMA控制器-->數(shù)據(jù)交換-->交還總線控制權(quán)二、系統(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接口：通用串行總線四、顯示器的有關(guān)知識

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

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

激光打印機速度最快，針式打印機可以打印票據(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ò)拓撲結(jié)構(gòu)第二節(jié)網(wǎng)絡(luò)協(xié)議一、OSI網(wǎng)絡(luò)協(xié)議的層次國際標準化組織（ISO）提出的“開放系統(tǒng)互連模型（OSI）”是計算機網(wǎng)絡(luò)通信的基本協(xié)議。該協(xié)議分為七層。如下表二、網(wǎng)絡(luò)設(shè)備極其作用

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

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

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

2、我國域名管理機構(gòu):CNNIC

3、常見域名含義：

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

org其他組織

cn中國

hk香港

tw臺灣

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

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

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

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

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

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

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

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

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

4、分組交換接入

5、幀中繼接入

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

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

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

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

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

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

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

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

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

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

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

3、沖擊波、震蕩波病毒：利用WINDOWS的漏洞，使計算機自動重啟并堵塞網(wǎng)絡(luò)。第二節(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ù)庫軟件都是關(guān)系型數(shù)據(jù)庫。二、數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)可以認為是多張二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖

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

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

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

多個表之間的數(shù)據(jù)可能存在相互關(guān)聯(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é)構(gòu)之線性結(jié)構(gòu)第一節(jié)線性表一、概念

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

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

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

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

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

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

1、一維數(shù)組

①數(shù)組存儲的結(jié)構(gòu)在數(shù)組聲明時就需要事先分配相應(yīng)的連續(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四、鏈式存儲結(jié)構(gòu)

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

優(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為表的首指針，指向鏈表的第一個結(jié)點。

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

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

定義方法：

Const

m=棧元素的上限；

Type

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

Var

s:stack;

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

1.入棧：過程push(x)，往棧s中壓入一個元素x。procedurepush(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ù)排隊的原則“先來先服務(wù)”。所謂隊列就是允許在一端進行插入，另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個隊尾指針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é)構(gòu)之非線性結(jié)構(gòu)第一節(jié)樹的概念一、樹的定義

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

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

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

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

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

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

結(jié)點一般分成三類:

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

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

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

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

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

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

圖（b）中的樹共有五層。在樹中，父結(jié)點在同一層的所有結(jié)點構(gòu)成兄弟關(guān)系。樹中最大的層次稱為樹的深度，亦稱高度。圖（b）中樹的深度為5。五、森林

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

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

六、有序樹和無序樹

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

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

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

⑵括號表示法：先將根結(jié)點放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結(jié)點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如下圖(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é)點存儲在一個數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n為樹的度)的數(shù)組，分別存儲該結(jié)點的每一個兒子的下標。Const

n=樹的度；

max=結(jié)點數(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)的多重鏈表

由于樹中結(jié)點可以有多個元素，所以可以用多重鏈表來描述比較方便。所謂多重鏈表，就是每個結(jié)點由數(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ù)結(jié)構(gòu)，它的特點是每個結(jié)點最多有兩個后繼，且其子樹有左右之分（次序不能任意顛倒）。

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

⑴有一個特定的結(jié)點稱為根；

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

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

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

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

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

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

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

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

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

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

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

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

⑴T中的結(jié)點與T’中的結(jié)點一一對應(yīng)，即T中每個結(jié)點的序號和值在T’中保持不變；

⑵T中某結(jié)點v的第一個兒子結(jié)點為v1，則在T’中v1為對應(yīng)結(jié)點v的左兒子結(jié)點；

⑶T中結(jié)點v的兒子序列，在T’中被依次鏈接成一條開始于v1的右鏈；由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹轉(zhuǎn)化成二叉樹的根結(jié)點是沒有右子樹的，并且除保留每個結(jié)點的最左分支外，其余分支應(yīng)去掉，然后從最左的兒子開始沿右兒子方向依次鏈接該結(jié)點的全部兒子。五、森林轉(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é)點的子樹森林F1={T11，T12，…T1k}轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F2={T2，T3，…，Tm}轉(zhuǎn)換成的二叉樹。第四節(jié)二叉樹的遍歷一、樹的存儲結(jié)構(gòu)

1.順序存儲結(jié)構(gòu)

將每個結(jié)點依次存放在一維數(shù)組中，用數(shù)組下標指示結(jié)點編號，編號的方法是從根結(jié)點開始編號1，然后由左而右進行連續(xù)編號。每個結(jié)點的信息包括

⑴一個數(shù)據(jù)域（data）；

⑵三個指針域，其中有父結(jié)點編號（prt）、左兒子結(jié)點編號（lch）和右兒子結(jié)點編號（rch）。滿二叉樹和完全二叉樹一般采用順序存儲結(jié)構(gòu)。Const

m=樹中結(jié)點數(shù)上限；Type

node=record{結(jié)點類型}

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

prt，lch，rch：0‥m；{父結(jié)點、左兒子、右兒子編號}

end；

treetype=array[1‥m]ofnode；{二叉樹的順序表類型}Var

Tree：treetype；{二叉樹}

2.鏈式存儲結(jié)構(gòu)

對于一般的二叉樹，通常采用鏈式分配，即用二重鏈表表示一般的二叉樹。這種鏈式分配即可以采用靜態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)組），又可以采用動態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。如果二叉樹的存儲需求量超過64Kb，則采用后者。由于二叉樹中每個結(jié)點通常包括數(shù)據(jù)元素和兩個分支。因此二叉樹對應(yīng)的二重鏈表中每個結(jié)點應(yīng)有三個域：

⑴值域：data

⑵左指針域：lch

⑶右指針域：rch

這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹的根結(jié)點Type

bitrpetr=^node；{結(jié)點指針類型}

node=record{結(jié)點類型}

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

lch，rch：bitreptr；{左指針域和右指針域}

end；Var

bt：bitreptr；{頭指針}二、二叉樹的遍歷

1.二叉樹遍歷的定義

按照一定的規(guī)律不重復(fù)地訪問(或取出結(jié)點中的信息，或?qū)Y(jié)點作其它的處理)二叉樹中的每一個結(jié)點。

2.二叉樹遍歷的順序

如果用L、D、R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，則對二叉樹的遍歷可以有下列六種（3!=6）組合：LDR、LRD、DLR、DRL、RDL、RLD。若再限定先左后右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（后序遍歷）、DLR（前序遍歷）。

以下遍歷以該樹為例三、前序遍歷

規(guī)則如下：

若二叉樹為空，則退出。否則

⑴訪問處理根結(jié)點；

⑵前序遍歷左子樹；

⑶前序遍歷右子樹；

如上圖的前序遍歷結(jié)果為abdehicfg順序結(jié)構(gòu):Proceduepreorder(i:integer);

begin

ifi<>0

thenbegin

訪問處理tree[i].data;

preorder(tree[i].lch);{遞歸遍歷左子樹}

preorder(tree[i].rch);{遞歸遍歷右子樹}

end;

end;鏈式結(jié)構(gòu):Proceduepreorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

訪問處理bt^.data;

preorder(bt^.lch);{遞歸遍歷左子樹}

preorder(bt^.rch);{遞歸遍歷右子樹}

end;

end;四、中序遍歷

規(guī)則如下：

若二叉樹為空，則退出；否則

⑴中序遍歷左子樹；

⑵訪問處理根結(jié)點；

⑶中序遍歷右子樹；

如上圖的中序遍歷結(jié)果為dbheiafcg順序結(jié)構(gòu):Procedueinorder(i:integer);

begin

ifi<>0

thenbegin

inorder(tree[i].lch);{遞歸遍歷左子樹}

訪問處理tree[i].data;

inorder(tree[i].rch);{遞歸遍歷右子樹}

end;

end;鏈式結(jié)構(gòu):Procedueinorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

inorder(bt^.lch);{遞歸遍歷左子樹}

訪問處理bt^.data;

inorder(bt^.rch);{遞歸遍歷右子樹}

end;

end;五、后序遍歷

規(guī)則如下：

若二叉樹為空，則退出；否則

⑴后序遍歷左子樹；

⑵后序遍歷右子樹；

⑶訪問處理根結(jié)點；

如上圖的后序遍歷結(jié)果為dhiebfgca順序結(jié)構(gòu):Proceduepostorder(i:integer);begin

ifi<>0

thenbegin

postorder(tree[i].lch);{遞歸遍歷左子樹}

postorder(tree[i].rch);{遞歸遍歷右子樹}

訪問處理tree[i].data;

end;end;鏈式結(jié)構(gòu):Proceduepostorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

postorder(bt^.lch);{遞歸遍歷左子樹}

postorder(bt^.rch);{遞歸遍歷右子樹}

訪問處理bt^.data;

end;

end;第五節(jié)普通樹的遍歷一、先根次序遍歷樹

規(guī)則：若樹為空，則退出；否則先根訪問樹的根結(jié)點，然后先根遍歷根的每棵子樹。上圖先根遍歷次序為rawxdhebfcstimonju

當普遍有序樹轉(zhuǎn)化為二叉樹時，可借用二叉樹的前序遍歷實現(xiàn)普遍有序樹的先根遍歷。二、后根次序遍歷樹

規(guī)則：若樹為空，則退出；否則先依次后根遍歷每棵子樹，然后訪問根結(jié)點。

上圖后根遍歷次序為whdexafbsmonijtucr

當普遍有序樹轉(zhuǎn)化為二叉樹時，可借用二叉樹的中序遍歷實現(xiàn)普遍有序樹的后根遍歷。三、森林的遍歷

1.先根遍歷森林

若森林非空，則可按下述規(guī)則遍歷之

①訪問森林中第一棵樹的根結(jié)點；

②先根遍歷第一棵樹中根結(jié)點的子樹森林；

③先根遍歷其余樹構(gòu)成的森林；

若對下圖的森林進行先根遍歷，則得到森林的先根序列為ABDCEFGHJI。森林的先根遍歷即為其對應(yīng)的二叉樹的前序遍歷。

2.后根遍歷森林

若森林非空，則可按下述規(guī)則遍歷之

①后根遍歷森林中第一棵樹的根結(jié)點的子樹森林；

②訪問第一棵樹的根結(jié)點；

③后根遍歷其余樹構(gòu)成的森林；

若對上圖(a)中的森林進行先根遍歷，則得到森林的后根序列為BCDAFEHJIG。森林的后根遍歷即為其對應(yīng)的二叉樹的中序遍歷。例如，對上圖(c)中的二叉樹進行中序遍歷，亦可得出對應(yīng)森林（上圖(a)的后根遍歷序列。第六節(jié)根據(jù)兩種遍歷順序確定樹結(jié)構(gòu)一、由兩種順序確定樹結(jié)構(gòu)

遍歷二叉樹有三種規(guī)則：

前序遍歷：根—左子樹—右子樹；

中序遍歷：左子樹—根—右子樹；

后序遍歷：左子樹—右子樹—根；

由于前序遍歷的第一個字符和后序遍歷的最后一個字符為根，中序遍歷中位于根左方的子串和位于根右方的子串分別反映了左子樹和右子樹的結(jié)構(gòu)，因此二叉樹的形態(tài)可以由其中序與后序或者前序與中序唯一確定。但無法反映左子樹和右子樹結(jié)構(gòu)的前序遍歷與后序遍歷卻不能做到這一點，因此這兩個遍歷順序可對應(yīng)多種二叉樹的形態(tài)。二、由中序遍歷與后序遍歷確定前序遍歷

由二叉樹的遍歷規(guī)則可以看出，后序遍歷的最后一個字符為根，中序遍歷中位于該字符左側(cè)的子串為左子樹中序遍歷的結(jié)果；中序遍歷中位于該字符右側(cè)的子串為右子樹中序遍歷的結(jié)果。

設(shè)中序遍歷s1='s1…sk…sn'

后序遍歷s2='s1……sn'

顯然，后序遍歷中的sn為二叉樹的根。按照前序遍歷的規(guī)則輸出sn。在中序遍歷中與sn相同的字符為sk。若k>1，說明左子樹存在，位于sk左側(cè)的子串s1…sk-1為左子樹中序遍歷的結(jié)果，后序遍歷中的前綴s1…sk-1為左子樹后序遍歷的結(jié)果；若k<n，說明右子樹存在，位于sk右側(cè)的子串為右子樹中序遍歷的結(jié)果；后序遍歷中的sk…sn-1為右子樹后序遍歷的結(jié)果。按照按照前序遍歷的規(guī)則分別遞歸二叉樹的左子樹和右子樹。proceduresolve1(s1，s2:string)；{計算和輸出中序遍歷s1和后序遍歷s2對應(yīng)的前序遍歷}var

k:integer；begin

iflength(s2)=1

{若當前子樹僅剩一個節(jié)點，則輸出}

thenwrite(s2)

elsebegin

k:=pos(s2[length(s2)]，s1)；{在中序遍歷中尋找子樹根}

write(s1[k])；

ifk>1

{若左子樹存在，則遞歸遍歷左子樹}

thensolve1(copy(s1，1，k-1)，copy(s2，1，k-1))；

ifk<length(s1)

{若右子樹存在，則遞歸遍歷右子樹}

thensolve1(copy(s1，k+1，length(s1)-k)，copy(s2，k，length(s2)-k))；

end；end;三、由中序遍歷與前序遍歷確定后序遍歷

原理同前，程序略微有些不同，看下面:proceduresolve2(s1，s2:string)；{計算和輸出中序遍歷s1和前序遍歷s2對應(yīng)的后序遍歷}var

k:integer；begin

iflength(s2)=1

{若當前子樹僅剩一個節(jié)點，則輸出}

thenwrite(s2)

elsebegin

k:=pos(s2[1]，s1)；

{在中序遍歷中尋找子樹根}

ifk>1

{若左子樹存在，則遞歸遍歷左子樹}

thensolve2(copy(s1，1，k-1)，copy(s2，2，k-1))；

ifk<length(s1){若右子樹存在，則遞歸遍歷右子樹}

thensolve2(copy(s1，k+1，length(s1)-k)，copy(s2，k+1，length(s2)-k))；

end；

write(s1[k])；{或者輸出子樹根s2[1]}end;第七節(jié)二叉排序樹一、概念

所謂二叉排序樹是指具有下列性質(zhì)的非空二叉樹

⑴若根結(jié)點的左子樹不空，則左子樹的所有結(jié)點值均小于根結(jié)點值；

⑵若根結(jié)點的右子樹不空，則右子樹的所有結(jié)點值均不小于根結(jié)點值；

⑶根結(jié)的左右樹也分別為二叉排序樹；

顯然，對二叉排序樹進行中序遍歷，可得出結(jié)點值遞增的排序序列。{假設(shè)待排序的數(shù)存在數(shù)組a中}procedurecreatetree;begin

fillchar(b，sizeof(b)，0);

b[1].data:=a[1];

{二叉排序樹初始化}

fori:=2tondo

begin

b[i].data:=a[i];

p:=1;

whiletruedo

begin

ifa[i]<b[p]．data

{若a[i]<b[p]．data，順左指針方向?qū)ふ翼旤ci的插入位置}

thenifb[p]．l<>0

thenp:=b[p]．l

elsebeginb[p]．l:=i;break;end

else

{若a[i]≥b[p]．data時順右指針方向?qū)ふ翼旤ci的插入位置}

ifb[p]．r<>0

thenp:=b[p]．r

elsebeginb[p]．r:=i;break;end;

end;{while}

end;{for}end;{createtree}第八節(jié)最優(yōu)二叉樹(哈夫曼樹)一、概念

在具有n個帶權(quán)葉結(jié)點的二叉樹中，使所有葉結(jié)點的帶權(quán)路徑長度之和（即二叉樹的帶權(quán)路徑長度）為最小的二叉樹，稱為最優(yōu)二叉樹（又稱最優(yōu)搜索樹或哈夫曼樹），即最優(yōu)二叉樹使（Wk—第k個葉結(jié)點的權(quán)值；Pk—第k個葉結(jié)點的帶權(quán)路徑長度）達到最小。二、最優(yōu)二叉樹的構(gòu)造方法

假定給出n個結(jié)點ki(i=1‥n)，其權(quán)值分別為Wi(i=1‥n)。要構(gòu)造以此n個結(jié)點為葉結(jié)點的最優(yōu)二叉樹，其構(gòu)造方法如下：

首先，將給定的n個結(jié)點構(gòu)成n棵二叉樹的集合F={T1，T2，……，Tn}。其中每棵二叉樹Ti中只有一個權(quán)值為wi的根結(jié)點ki，其左、右子樹均為空。然后做以下兩步

⑴在F中選取根結(jié)點權(quán)值最小的兩棵二叉樹作為左右子樹，構(gòu)造一棵新的二叉樹，并且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；

⑵在F中刪除這兩棵二叉樹，同時將新得到的二叉樹加入F重復(fù)⑴、⑵，直到在F中只含有一棵二叉樹為止。這棵二叉樹便是最優(yōu)二叉樹。三、最優(yōu)二叉樹的數(shù)據(jù)類型定義

在最優(yōu)二叉樹中非葉結(jié)點的度均為2，為滿二叉樹，因此采用順序存儲結(jié)構(gòu)為宜。如果帶權(quán)葉結(jié)點數(shù)為n個，則最優(yōu)二叉樹的結(jié)點數(shù)為2n-1個。

Constn=葉結(jié)點數(shù)的上限；

m=2*n-1；{最優(yōu)二叉樹的結(jié)點數(shù)}

Type

node=record{結(jié)點類型}

data：<數(shù)據(jù)類型>；{權(quán)值}

prt，lch，rch,lth：0‥m；{父指針、左、右指針和路徑長度}

end；

wtype=array[1‥n]of<數(shù)據(jù)類型>；{n個葉結(jié)點權(quán)值的類型}

treetype=array[1‥m]ofnode；{最優(yōu)二叉樹的數(shù)組類型}

Vartree：treetype；

{其中tree[1‥n]為葉結(jié)點，tree[n+1‥2n-1]為中間結(jié)點，根為tree[2n-1]}四、構(gòu)造最優(yōu)二叉樹的算法procedurehufm(w：wtype；vartree：treetype；varbt：integer)；

functionmin(h：integer)：integer；{在前h個結(jié)點中選擇父指針為0且權(quán)值最小的結(jié)點min}

begin

ml:=∞；

forp:=1tohdo

if(tree[p]．prt=0)and(m1>tree[p]．data)

thenbegini:=p；m1:=tree[p]．data；end；

min:=i；

end；{min}

begin

fillchar(tree，sizeof(tree)，0)；{構(gòu)造初始集合F}

fori:=1tondo

read(tree[i]．Data)；

fork:=n+1tomdo{構(gòu)造最優(yōu)二叉樹}

begin{計算k為根的左兒子和右兒子}

i:=min(k-1)；

tree[i]．prt:=k；

tree[k]．lch:=i；

j:=min(k-1)；

tree[j]．prt:=k；

tree[k]．rch:=j；

tree[k]．data:=tree[i]．data+tree[j]．data；

end；{for}

bt:=m；

end；{hufm}{計算每一個葉結(jié)點的路徑長度}procedureht(t:integer);{通過前序遍歷計算每一個葉結(jié)點的路徑長度}

begin

ift=m{若結(jié)點t為根，則路徑長度為0；否則結(jié)點t的路徑長度為其父結(jié)點的路徑長度+1}

thentree[t].lth:=0

elsetree[t].lth:=tree[tree[t].prt].lth+1；

iftree[t].lch<>0

thenbeginht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分別遞歸左右子樹}

end；{ht}由此可見，葉結(jié)點t（1≤t≤5）的帶權(quán)路徑長度即為tree[t].lth*tree[t].data。AOE網(wǎng)AOE網(wǎng)（ActivityOnEdgNetwork）

在現(xiàn)代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權(quán)有向圖中若以頂點表示事件，有向邊表示活動，邊上的權(quán)值表示該活動持續(xù)的時間，這樣的圖簡稱為AOE網(wǎng),如下圖。

AOE網(wǎng)具有以下性質(zhì)：（1）只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始。（2）只有在進入某點的各有向邊所代表的活動都已結(jié)束，該頂點所代表的時事件才能發(fā)生?？梢詫⑸蠄D假想一個工程有6項活動，網(wǎng)中5個頂點，分別表示5個事件，邊上的權(quán)值分別表示各項活動所需要的時間，事件v1表示工程開始，事件v3表示活動3和4完成后，活動5可以開始，事件v4表示活動2完成活動4和活動6開始，v5表示活動1完成活動3開始，事件v2表示工程結(jié)束。

關(guān)鍵路徑（臨界路徑）：在AOE網(wǎng)絡(luò)中從源點到匯點（結(jié)束頂點）的最長路徑。關(guān)鍵路徑上的活動為關(guān)鍵活動?！渡驶A(chǔ)知識》說課稿《色彩基礎(chǔ)知識》說課稿各位評委老師：你們好！我今天說課的題目是《色彩基礎(chǔ)知識》。下面我從教材分析、學(xué)情分析、教學(xué)目標、教法與學(xué)法、教學(xué)程序、教學(xué)反思等方面做以說明，請各位專家評委指正！教材分析本節(jié)內(nèi)容是高教版中職學(xué)前教育專業(yè)《美術(shù)》上冊第二單元第二章色彩基礎(chǔ)知識前兩節(jié)的內(nèi)容。是在學(xué)習了線描和素描之后開始學(xué)習色彩，為后續(xù)的水彩水粉畫奠定基礎(chǔ)。教材的編寫循序漸進，由易到難，由淺入深，具有承前啟后的作用。對基礎(chǔ)知識講解的較為詳細，適合美術(shù)基礎(chǔ)薄弱甚至沒有基礎(chǔ)的中職學(xué)生。學(xué)情分析我所授課班級是學(xué)前教育一年級學(xué)生，他們活潑好動，凡事都想親自嘗試。通過一段時間的線描和素描練，造型能力有了一定的提高，能夠繪畫出較好的作品。但時間稍長就覺得單調(diào)乏味，同時對學(xué)習的積極性不高，缺乏主動性，持久性差。教學(xué)目標因此根據(jù)大綱要求和教材特點，結(jié)合學(xué)生的基本情況，我確定如下三維目標：1.知識與技能：了解色彩的分類，原色、間色、復(fù)色三者的關(guān)系。2.過程與方法：通過課堂講授、微課示范、實踐操作，讓學(xué)生歸納小結(jié)色彩調(diào)和的規(guī)律。3.情感態(tài)度與價值觀：培養(yǎng)學(xué)生對色彩的的興趣，形成自主探索的學(xué)習態(tài)度，提高自身藝術(shù)修養(yǎng)。4.教學(xué)重點：色彩的分類。5.教學(xué)難點：顏色調(diào)和的規(guī)律。教法與學(xué)法我們生活在一個五彩繽紛的世界里，對色彩有了豐富的直觀感受，雖然司空見慣，但是相關(guān)概念抽象，因此本節(jié)課采用閱讀指導(dǎo)法、講授法、演示法、練習法等教學(xué)方法。采用研究性學(xué)習、小組討論學(xué)習法、自主學(xué)習法、實踐操作法等方法指導(dǎo)學(xué)生。教學(xué)過程結(jié)合教學(xué)設(shè)計，我將本節(jié)課分為準備、導(dǎo)課、新授、總結(jié)、拓展五個環(huán)節(jié)。（一）精心準備，先學(xué)后教課前，我將一個flash小游戲分享到班級群，讓學(xué)生結(jié)合初中物理知識了解色彩產(chǎn)生的原因。復(fù)習光的三原色并做好上課前的材料準備工作。（二）創(chuàng)設(shè)情境，導(dǎo)入新課林徽因說：最美人間四月天。課上，我結(jié)合春暖花開的時令，通過一段優(yōu)美的旋律和美麗的圖片帶領(lǐng)學(xué)生走進美麗的四季。之后讓學(xué)生談?wù)勊募镜拇砩鞘裁础Ｓ纱颂岢錾适窃鯓赢a(chǎn)生的問題，再根據(jù)學(xué)生自學(xué)情況引導(dǎo)學(xué)生結(jié)合初中物理和生活常識討論色彩產(chǎn)生的原因，從而激發(fā)學(xué)生興趣，導(dǎo)入新課。（三）手腦結(jié)合，探究新知（1）、閱讀教材，自主學(xué)習：技能的學(xué)習要堅持理論指導(dǎo)，因此，我安排學(xué)生自主閱讀教材，先掌握理論知識，通過flash動畫演示三原色混合，再通過一個小練習讓學(xué)生把7種顏色與相應(yīng)的類別名稱放在一起。從而