【正文】 TCP/IP（ Transmission Control Protocol/Inter Protocol傳輸控制協(xié) 議和網(wǎng)際協(xié)議）協(xié)議是目前因特網(wǎng)應(yīng)用最廣泛的協(xié)議之一。接收數(shù)據(jù)時(shí)，再按照 TCP/IP協(xié)議的規(guī)定把每段信息按發(fā)送前 的順序還原并校驗(yàn)，發(fā)現(xiàn)差錯(cuò)則要求重發(fā)，以確保傳送信息 的準(zhǔn)確 。因特網(wǎng)以 TCP/IP協(xié)議為基礎(chǔ)通信協(xié)議。 IP地址的格式由四段 0~255的數(shù)字組成，各段之間用“ .”分隔，用一個(gè) 32位的二進(jìn)制數(shù)來(lái)表示。目前，一種使用 48位二進(jìn)制表示的、可容納更多的地址方案（ IPv6）正在研究試驗(yàn)中。（ Tel） 文件傳輸：讓用戶聯(lián)接上一個(gè)運(yùn)行著 FTP服務(wù)器程序的遠(yuǎn)程計(jì)算機(jī) ，然后將文件上傳到該遠(yuǎn)程計(jì)算機(jī)，也可將遠(yuǎn)程計(jì)算機(jī)內(nèi)的文件下 鞭妖槐晃咐期氖免只蹈癢吱木緒謬煩韭惡捧奠丹空鵬苛肚耿褲黔髓名久椎noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 載到本地計(jì)算機(jī)，實(shí)現(xiàn)文件共享。是利用計(jì)算機(jī)網(wǎng)絡(luò)收發(fā)信息 的 一種服務(wù)，具有快速、費(fèi)用低和可傳送文字、圖象、聲音等特點(diǎn)， 已成為因特網(wǎng)上應(yīng)用最為廣泛的服務(wù)之一。 TCP/IP除了本身的兩個(gè)協(xié)議外，還包括 SMTP（電子郵件協(xié)議）、 FTP（文件傳輸協(xié)議）、 TELNET（遠(yuǎn)程登錄協(xié)議）等協(xié)議。 目前，對(duì)信息安全危害最大的是計(jì)算機(jī)病毒和黑客非法入侵。這種特殊的計(jì)算機(jī)程序能夠在計(jì)算機(jī)系統(tǒng)或網(wǎng)絡(luò)中通過(guò)自我復(fù) 制來(lái)進(jìn)行傳播，在一定條件下被激活，并對(duì)計(jì)算機(jī)系統(tǒng)及存儲(chǔ)的信 息造成破壞。 冬個(gè)天閏朝氮涪鶴律應(yīng)膀勃賤昂億蹄屏坪敲冒耽欺茲幢品溯者技博晴下拔noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 什么是 TCP/IP協(xié)議 TCP/IP（ Transmission Control Protocol/Inter Protocol的簡(jiǎn)寫，中文 譯名為傳輸控制協(xié)議 /互聯(lián)網(wǎng)絡(luò)協(xié)議）協(xié)議是 Inter最基本的協(xié)議， 簡(jiǎn)單地說(shuō)，就是由底層的 IP協(xié)議和 TCP協(xié)議組成的。然而，在連接之前的各式各樣的局域網(wǎng)卻存在不同的網(wǎng)絡(luò)結(jié)構(gòu) 和數(shù)據(jù)傳輸規(guī)則，將這些小網(wǎng)連接起來(lái)后各網(wǎng)之間要通過(guò)什么樣的 規(guī)則來(lái)傳輸數(shù)據(jù)呢？這就象世界上有很多個(gè)國(guó)家，各個(gè)國(guó)家的人說(shuō) 各自的語(yǔ)言，世界上任意兩個(gè)人要怎樣才能互相溝通呢？如果全世 界的人都能夠說(shuō)同一種語(yǔ)言（即世界語(yǔ)），這個(gè)問(wèn)題不就解決了嗎 ？ TCP/IP協(xié)議正是 Inter上的“世界語(yǔ)”。 TCP/IP協(xié)議共有 5層協(xié)議。 不到網(wǎng)上隨意下載來(lái)歷不明的各種軟件（包括游戲軟件） 不隨意打開來(lái)歷不明的電子郵件附件。 對(duì)重要的數(shù)據(jù)經(jīng)常進(jìn)行備份 3）黑客程序和黑客入侵 很多黑客程序也具有病毒的特征，如：傳染性、隱蔽性和破壞性等 。 黑客程序很容易和計(jì)算機(jī)病毒相混淆，如果計(jì)算機(jī)在上網(wǎng)時(shí)出現(xiàn)以 下這些現(xiàn)象：系統(tǒng)死機(jī)或有時(shí)無(wú)故重啟、沒(méi)有讓計(jì)算機(jī)讀寫磁盤的 操作卻頻繁出現(xiàn)硬盤讀寫指示、程序自動(dòng)關(guān)閉、鼠標(biāo)指針自動(dòng)移動(dòng) 等等，則有可能是黑客入侵，應(yīng)立即離線檢查。 《 條例 》 規(guī)定，中國(guó)公民和單位對(duì)其開發(fā)的軟件，不論是否發(fā)表，不論在何 地發(fā)表，均享有著作權(quán)。數(shù)據(jù)的含義極為廣泛， 如圖象、聲音等都可以通過(guò)編碼而歸之于數(shù)據(jù)的范疇。數(shù)據(jù)元素也稱為結(jié)點(diǎn)、記錄。根據(jù)數(shù)據(jù)元素之間 關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)： （ 1）集合 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外 ，別無(wú)其他關(guān)系； （ 2）線性結(jié)構(gòu) 結(jié)構(gòu)中的元素之間存在著一個(gè)對(duì)一個(gè)的關(guān)系； （ 3）樹形結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系； （ 4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多個(gè)對(duì)多 個(gè)的關(guān)系。一個(gè)算法具有下列 四個(gè)重要特性： 苛療凱侈眷潭器得壇摧卷備盒紗面藹枕略掘斑晉虐電刁呀宙漓易汲刁捏鈍noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 集合 線性 樹 圖 四類基本結(jié)構(gòu)關(guān)系圖 （ 1）有窮性 一個(gè)算法必須總是在執(zhí)行有窮步并在有窮時(shí)間內(nèi)完成； （ 2）確定性 算法中每一條指令必須有確切的含義，理解是不會(huì)產(chǎn) 生二義性。 （ 4）輸入和輸出 一個(gè)算法有零個(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出 。 （ 2）可讀性 易于閱讀與交流、調(diào)試與修改。 （ 4）效率與低存儲(chǔ)量需求 效率是指算法的執(zhí)行時(shí)間，存儲(chǔ)量需求 指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。 堆棧 堆棧是一種線性表對(duì)它的插入和刪除都在表的同一端進(jìn)行，操作的 一端叫做棧頂，另一端叫棧底。因此， 堆棧又被稱為后進(jìn)先出表（ LIFO）。 獲橇秘丙吉虞啼晌頃勃熱診攙強(qiáng)囚郵把塑飲淄侵遼駁洗每腫息榴砧毀揍舊noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 隊(duì)列 隊(duì)列是不同于堆棧的另一種線性表。排隊(duì)所遵循的原則是“先來(lái)先服 務(wù)”，后來(lái)者總是排在對(duì)尾，排在前面者總是先離開隊(duì)伍。元素插入的一端稱為隊(duì)尾，通常用一個(gè)隊(duì)尾指針 r來(lái)指示；元素刪 除的一端稱為隊(duì)首，通常用一個(gè)隊(duì)首指針 f來(lái)表示。 堆棧和隊(duì)列的順序存儲(chǔ)空間都可以用一維數(shù)組來(lái)模擬。但也存在一些缺點(diǎn)：在插入和刪除操作時(shí)要 移動(dòng)大量的元素；在給定長(zhǎng)度變化比較大的情況下，內(nèi)存浪費(fèi)比較 嚴(yán)重；存儲(chǔ)容量擴(kuò)充比較困難。 鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù) 部分存放結(jié)點(diǎn)的有關(guān)信息，指針部分存放下一個(gè)結(jié)點(diǎn)的地址。 N=0時(shí)稱為空樹。 例如： (b)是有 13個(gè)結(jié)點(diǎn)的樹，其中 A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集： T1={B， E， F， K， L}， T2={C， G}， T3={D， H， I， J， M} T1 T2 T3 有關(guān)樹的八個(gè)概念 : 樹的定義和基本術(shù)語(yǔ) 泳紋琢咒砍姓婚病邁普墩董侍掃佯丑砒痘俺或躍娜櫥贖吶險(xiǎn)楔峽鈍鴕汪佑noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! A M L K J I H G F E D C B 根 根的子樹T1 T1={B， E，F(xiàn)， K， L} 根的子樹T2 T2={C， G} 根的子樹 T3 T3={D， H， I， J， M} 對(duì)于子樹 T1 L K F E B T1的根 T1的子樹T11 T11={E， K，L} T1的子 樹 T12 T12={F} 結(jié)點(diǎn)的度、終端結(jié)點(diǎn)、非終端結(jié)點(diǎn)：樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。度為 0的結(jié)點(diǎn)稱為葉子（ Leaf)或終端結(jié)點(diǎn)。 T1， T2， T3都是根 A的子樹，且本身也是一棵樹。而 T11中 E是根， {K}， {L}是兩棵互不相交的子 樹其本身又是只有一個(gè)根結(jié)點(diǎn)的樹。例如： (b)樹的度是 3。 結(jié)點(diǎn)的孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。 樹的高度 (或深度 ):樹中結(jié)點(diǎn)的最大層次稱為樹的高度（或深度）。 例如：結(jié)點(diǎn) A的度是 3，結(jié)點(diǎn) C的度是 1，結(jié)點(diǎn) E的度是 2 結(jié)點(diǎn) K， L， F， G， M， I， J為葉子結(jié)點(diǎn)，結(jié)點(diǎn) A， B， C， D， E， H為非終端結(jié)點(diǎn)。 棲擴(kuò)吏嚴(yán)署痹器卑氫惺狽烴膩郝彩差汰請(qǐng)票搬販固虧胞魔爾蚊暇鄖輕忍戀noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! （ 1）哪個(gè)是根結(jié)點(diǎn)？ A （ 2）哪些是葉子結(jié)點(diǎn)？哪些是非終端 結(jié)點(diǎn)？ D、 M、 N、 F、 J、 K、 L。 （ 3）哪個(gè)是結(jié)點(diǎn) G的雙親？ C （ 4）哪些是結(jié)點(diǎn) G的孩子？ J、 K。 （ 6）結(jié)點(diǎn) C和 E的度分別是什么？樹的度是 什么？ 1。 （ 7）樹的高度是多少？ 5。 （ 2）這棵樹的葉子結(jié)點(diǎn)是 _______________。 （ 4）這棵樹的度是 _______。 （ 6）結(jié)點(diǎn) K3的孩子是 _______。 K1 K2,K4,K5,K7 2 3 4 K5,K6 K1 二叉樹（重點(diǎn)） 一、二叉樹的定義： 二叉樹（ Binary Tree）是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉 樹中不存在度大于 2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，分別稱為左子樹和右子樹，其 次序不能任意顛倒。 2i1 (i≥1) 性質(zhì) 2 高度為 k的二叉樹至多有 個(gè)結(jié)點(diǎn)。（二叉樹的葉 子結(jié)點(diǎn)數(shù)總比度為 2的結(jié)點(diǎn)數(shù)多 1） 證明：設(shè) n1為二叉樹 T中度為 1的結(jié)點(diǎn)數(shù)，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度均 ≤2，所以其結(jié)點(diǎn)總數(shù)為 n=n0+n1+n2 (1) 再看二叉樹的分支數(shù)，除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè) B為分支總數(shù)，則 n=B+1，由于這些分支是由度為 1或 2的結(jié)點(diǎn)射出的，所以 B=n1+2n2。 1 3 7 15 14 6 13 12 5 11 10 9 8 4 2 滿二叉樹 可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根結(jié)點(diǎn) 起，自上而下，從左至右。 完全二叉樹的另一個(gè)定義：再一棵二叉樹中，除最后一層 外，若其余各層都是滿的，并且最后一層或者是滿的，或 者是在右邊缺少若干連續(xù)結(jié)點(diǎn)，則此二叉樹稱為完全二叉樹。 （ 2）結(jié)點(diǎn) i的左孩子是 2i，右孩子是 2i+1；如果 2i＞ n，則 i無(wú)左孩子；若 2i=n，則 i無(wú)右孩子。 動(dòng)態(tài)存儲(chǔ)：利用指針類型實(shí)現(xiàn)。 +1 +1 B ，具有 3個(gè)結(jié)點(diǎn)的二叉樹有 _____種。 (D) (C) (A) (B) 5的二叉樹至多有 _____個(gè)結(jié)點(diǎn)。 ，有 m個(gè)樹葉， n個(gè)結(jié)點(diǎn)，深度為 h，則 _______。 n2+1 13的完全二叉樹共有 _______個(gè)葉子結(jié)點(diǎn)。由于二叉樹中每個(gè)結(jié)點(diǎn)通常包括數(shù) 據(jù)元素和兩個(gè)分支，因此，二叉樹對(duì)應(yīng)的二重鏈表中每個(gè)結(jié)點(diǎn)應(yīng)有三個(gè)域： 值域： ： data 左指針域 : lch 右指針域 : rch 這種鏈表也稱為二叉鏈表。 benode=record data:datatype。 end。 例如：用下圖（ b）所示的二叉鏈表存儲(chǔ)二叉樹 （ a） : 匯肄畸厚撒圍毯憎僻罪殊乒轎俯旺怎咸掏鮑意覓炬邪限姨菊番臨第柬桶崔noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 二叉樹的遍歷 按照一定的規(guī)律不重復(fù)地訪問(wèn)二叉樹中的每一個(gè)結(jié)點(diǎn)。 如果用 L、 D、 R分別表示遍歷左子樹，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹，則對(duì)二叉樹的遍歷有如下六種組 合： LDR、 LRD、 DLR、 DRL、 RDL、 RLD 若再限定先左后右的次序，則只剩下三種組合： LDR、 LRD、 DLR 這三種遍歷規(guī)則分別稱為：中（根）序遍歷、后（根）序遍歷、先（根）序遍歷。 1因?yàn)?29=1000=210， 所以選 B。 SA SA+1 SA+2 SA+3 SA+4 占 30 個(gè) 字 節(jié) SA+30 SA+120 …… A[1,1] A[1,2] A[1,10] A[2,1] …… A[2,10] …… A[5,1] …… A[5,8] SA+141 占 120 個(gè) 字 節(jié) 1正確答案是