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

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

信息學(xué)奧賽-計(jì)算機(jī)基礎(chǔ)知識（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）第一章計(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)二叉樹(哈夫曼樹) 30AOE網(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）800001001201030114100510161107111三、二進(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）1600000100012001030011401005010160110701118100091001A1010B1011C1100D1101E1110F1111四、進(jìn)制的英文表示法：以上都是用括號加數(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=11+1=102、減法運(yùn)算規(guī)則：

0-0=0

0-1=1（向高位借1）1-0=11-1=03、乘法運(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=11+1=1

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

=02、常用運(yùn)算

異或運(yùn)算：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

⑥互補(bǔ)律

A+=1

A·=0

⑦吸收律

A＋A·B=A

A·（A＋B）=A

A＋·B=A＋B

A·（＋B）=A·B

⑧對合律

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

⑨德·摩根定理

=·

=+三、邏輯代數(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，其余各位照抄?！纠?】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]反=三、補(bǔ)碼求補(bǔ)碼的方法：設(shè)X；若X≥0，則符號位（原碼最高位）為0，X其余各位取值照抄；若X≤0，則符號位為1，其余各位按位取反后，最低位加1?！纠?】X=+1001001

[X]補(bǔ)=0【例6】X=-1001001

[X]補(bǔ)=四、補(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”?！纠?】X=+0111001,Y=+1001101，求[X-Y]補(bǔ)

[X]補(bǔ)=00111001

[Y]補(bǔ)=01001101

[-Y]補(bǔ)=

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

通過上面的學(xué)習(xí)，我們就可以知道計(jì)算機(jī)如果用一個(gè)字節(jié)表示一個(gè)整數(shù)的時(shí)候，如果是無符號數(shù)，可以表示0~255共256個(gè)數(shù)（00000000~11111111），如果是有符號數(shù)則能表示-128~127共256個(gè)數(shù)（10000000~01111111）。如果兩個(gè)字節(jié)表示一個(gè)整數(shù)，則共有65536個(gè)數(shù)可以表示，大部分程序設(shè)計(jì)語言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(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ù)符號尾數(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è)極小值來代替。三、實(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)表示形式。

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

第五節(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)：一個(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”?！纠?】給11101加奇校驗(yàn)結(jié)果為1001101101二、偶校驗(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】給11101加偶校驗(yàn)結(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的縮寫），它同時(shí)也被國際標(biāo)準(zhǔn)化組織（InternationalOrganizationforStandardization,ISO）批準(zhǔn)為國際標(biāo)準(zhǔn)。

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

字母和數(shù)字的ASCII碼的記憶是非常簡單的。我們只要記住了一個(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é)來存放一個(gè)ASCII字符。每一個(gè)字節(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個(gè)字符，這些擴(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)算的部件，控制器是整個(gè)計(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、立即尋址：ADDAH,78

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

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

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

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

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

4、相對尋址：ADDAH,*78

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

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

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

AH是一個(gè)寄存器名,即寄存器直接尋址

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

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

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

INAH,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í)鐘周期

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

計(jì)算機(jī)完成一個(gè)操作（如讀取指令等）所需時(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個(gè)單元，每個(gè)單元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、硬盤：硬盤由多個(gè)盤面組成一個(gè)柱形結(jié)構(gòu)，其原來跟軟盤類似，但是磁道更多。

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

①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

②UltraDMA

③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é)議一、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地址

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

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

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（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專線接入：速度快，費(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、宏病毒：專門感染MicrosoftOffice系列文件的病毒

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

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

1、CIH病毒:文件型病毒，4月26日發(fā)作時(shí)破壞性最大，首個(gè)能破壞硬件系統(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、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)可以認(rèn)為是多張二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖

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

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

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

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

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

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é)線性表一、概念

線性表是指由有限個(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è)后繼。二、線性表的存儲結(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ù)。

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

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

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

2、二維數(shù)組

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

②對于行為n，列為m的二維數(shù)組的元素訪問方法：若第一個(gè)元素的地址是a，每個(gè)元素占用的存儲空間為L，則數(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)酱鎯Y(jié)構(gòu)

鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù)部分存放結(jié)點(diǎn)的有關(guān)信息，指針部分存放下一個(gè)結(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)以外至少增加一個(gè)指向后繼元素的指針類型的數(shù)據(jù)項(xiàng)，查找其中的某個(gè)元素時(shí)必須中從第一個(gè)元素開始逐個(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é)棧一、棧的概念

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

定義方法：

Const

m=棧元素的上限；

Type

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

Var

s:stack;

t:integer;二、棧的基本運(yùn)算

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

begin

ift=m

thenwriteln(‘overflow’)

elsebegin

t:=t+1;

s[t]:=x;

end;

end;

2.出棧：函數(shù)pop(x)，從棧s中彈出一個(gè)元素。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é)隊(duì)列一、棧的概念

隊(duì)列是從日常生活中的排隊(duì)抽象出來的，根據(jù)排隊(duì)的原則“先來先服務(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.過程add(x)：隊(duì)列q插入元素xProcedureadd(x:integer);

begin

ifr=m

thenwriteln(‘overflow’)

elsebegin

r:=r+1;

q[r]:=x;

end;

end;

2.過程del(x)：取出隊(duì)列q的隊(duì)首元素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)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件：

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

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

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

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

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

⑴根結(jié)點(diǎn)：沒有前驅(qū)的結(jié)點(diǎn)。在樹中有且僅有一個(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)亦是其子樹的根；

⑶葉結(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)到每一個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。例如上圖（b）中，從根r到結(jié)點(diǎn)i的唯一路徑為rcti。三、有關(guān)度的定義

⑴結(jié)點(diǎn)的度：一個(gè)結(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)在第一層，根的后件在第二層，其余各層依次類推。即若某個(gè)結(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)存儲在一個(gè)數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n為樹的度)的數(shù)組，分別存儲該結(jié)點(diǎn)的每一個(gè)兒子的下標(biāo)。Const

n=樹的度；

max=結(jié)點(diǎn)數(shù)的上限；Type

node=record

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

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

end；

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

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

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

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

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)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)后繼，且其子樹有左右之分（次序不能任意顛倒）。

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

⑴有一個(gè)特定的結(jié)點(diǎn)稱為根；

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

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

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

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

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

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

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

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

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

性質(zhì)2：在深度為k(k≥1)的二叉樹中最多有2k-1個(gè)結(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個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；(3)對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1；(4)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int（log2n）+1(5)有N個(gè)結(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個(gè)節(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中每個(gè)結(jié)點(diǎn)的序號和值在T’中保持不變；

⑵T中某結(jié)點(diǎn)v的第一個(gè)兒子結(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)是沒有右子樹的，并且除保留每個(gè)結(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)

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

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

⑵三個(gè)指針域，其中有父結(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]ofnode；{二叉樹的順序表類型}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，則采用后者。由于二叉樹中每個(gè)結(jié)點(diǎn)通常包括數(shù)據(jù)元素和兩個(gè)分支。因此二叉樹對應(yīng)的二重鏈表中每個(gè)結(jié)點(diǎn)應(yīng)有三個(gè)域：

⑴值域：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)作其它的處理)二叉樹中的每一個(gè)結(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é)果為abdehicfg順序結(jié)構(gòu):Proceduepreorder(i:integer);

begin

ifi<>0

thenbegin

訪問處理tree[i].data;

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

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

end;

end;鏈?zhǔn)浇Y(jié)構(gòu):Proceduepreorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

訪問處理bt^.data;

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

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

end;

end;四、中序遍歷

規(guī)則如下：

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

⑴中序遍歷左子樹；

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

⑶中序遍歷右子樹；

如上圖的中序遍歷結(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;鏈?zhǔn)浇Y(jié)構(gòu):Procedueinorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

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

訪問處理bt^.data;

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

end;

end;五、后序遍歷

規(guī)則如下：

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

⑴后序遍歷左子樹；

⑵后序遍歷右子樹；

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

如上圖的后序遍歷結(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;鏈?zhǔn)浇Y(jié)構(gòu):Proceduepostorder(bt:bitreptr);

begin

ifbt<>nil

thenbegin

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

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

訪問處理bt^.data;

end;

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

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

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

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

上圖后根遍歷次序?yàn)閣hdexafbsmonijtucr

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

1.先根遍歷森林

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

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

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

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

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

2.后根遍歷森林

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

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

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

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

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

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

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

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

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

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

由二叉樹的遍歷規(guī)則可以看出，后序遍歷的最后一個(gè)字符為根，中序遍歷中位于該字符左側(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)；{計(jì)算和輸出中序遍歷s1和后序遍歷s2對應(yīng)的前序遍歷}var

k:integer；begin

iflength(s2)=1

{若當(dāng)前子樹僅剩一個(gè)節(jié)點(diǎn)，則輸出}

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)；{計(jì)算和輸出中序遍歷s1和前序遍歷s2對應(yīng)的后序遍歷}var

k:integer；begin

iflength(s2)=1

{若當(dāng)前子樹僅剩一個(gè)節(jié)點(diǎn)，則輸出}

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é)點(diǎn)的左子樹不空，則左子樹的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值；

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

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

顯然，對二叉排序樹進(jìn)行中序遍歷，可得出結(jié)點(diǎn)值遞增的排序序列。{假設(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ū)ふ翼旤c(diǎn)i的插入位置}

thenifb[p]．l<>0

thenp:=b[p]．l

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

else

{若a[i]≥b[p]．data時(shí)順右指針方向?qū)ふ翼旤c(diǎn)i的插入位置}

ifb[p]．r<>0

thenp:=b[p]．r

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

end;{while}

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

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

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

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

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

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

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

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

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

Type

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

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

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

end；

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

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

Vartree：treetype；

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

functionmin(h：integer)：integer；{在前h個(gè)結(jié)點(diǎn)中選擇父指針為0且權(quán)值最小的結(jié)點(diǎn)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{計(jì)算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}{計(jì)算每一個(gè)葉結(jié)點(diǎn)的路徑長度}procedureht(t:integer);{通過前序遍歷計(jì)算每一個(gè)葉結(jié)點(diǎn)的路徑長度}

begin

ift=m{若結(jié)點(diǎn)t為根，則路徑長度為0；否則結(jié)點(diǎn)t的路徑長度為其父結(jié)點(diǎn)的路徑長度+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é)點(diǎn)t（1≤t≤5）的帶權(quán)路徑長度即為tree[t].lth*tree[t].data。AOE網(wǎng)AOE網(wǎng)（ActivityOnEdgNetwork）

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

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

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