【正文】 元素。 棧的應(yīng)用；表達(dá)式求值，括號(hào)匹配等，在計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)一將遞歸過(guò)程轉(zhuǎn)變非遞歸過(guò)程的處理中，棧有重要的作用。順序隊(duì)列； 隊(duì)列；是只允許在一端進(jìn)行插入元素，而在另一端進(jìn)行刪除元素的線性表。 在隊(duì)列中，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列又稱“先進(jìn)先出”“后進(jìn)后出”隊(duì)列的鏈?zhǔn)酱鎯?chǔ)也稱鏈隊(duì)列。 隊(duì)列為空的條件；頭指針和尾指針的值相同，且均指向頭結(jié)點(diǎn)。樹；是一種簡(jiǎn)單的非線性結(jié)構(gòu)。 特點(diǎn)； 1，樹中至少有一個(gè)結(jié)點(diǎn) 根； 2，樹中各子樹是互不相交的。 基本術(shù)語(yǔ)；結(jié)點(diǎn)，節(jié)點(diǎn)的度，葉子，孩子，雙親，兄弟，樹的度，結(jié)點(diǎn)的層次，深度，森林。二叉樹；是一種特殊的樹 特點(diǎn)； 1，每個(gè)結(jié)點(diǎn)至多 有兩顆子樹； 2，二叉樹的子樹有左、右之分，且其次序不能任意顛倒。性質(zhì)； 滿二叉樹；定義； 特點(diǎn)；每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。完全二叉樹； 定義；深度為 k，有 n 個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號(hào)從 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。特點(diǎn)；葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)，二叉樹的遍歷； 先序遍歷；先訪問(wèn)根結(jié)點(diǎn)，然后分別訪問(wèn)左子樹、右子樹。中序遍歷；先訪問(wèn)左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹。后序遍歷；先訪問(wèn)左子樹、右子樹，然后訪問(wèn)根結(jié)點(diǎn)圖 圖是比 樹結(jié)構(gòu)更復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。（圖中一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的數(shù)是沒(méi)有限制的） 圖由兩個(gè)集合 V(G)和 E(G)組成的，記為 G=（ V,E）。其中； V(G)是頂點(diǎn)的非空有限集， E(G)是邊的有限集合，即圖由邊和頂點(diǎn)組成。邊表示為頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)?。圖的遍歷； 1；深度有限遍歷； 2；廣度優(yōu)先遍歷；查找與排序方法； 查找表；被查找的對(duì)象是由一組相同類型的數(shù)據(jù)元素的有限集合。 查找；給定一個(gè)值 k，在含有 n 個(gè)數(shù)據(jù)元素的表中找出關(guān)鍵字等于給定值 k 的數(shù)據(jù)元素；查找方法； 對(duì)于數(shù)據(jù)量小的線性表，可以采用順序查找算法。當(dāng)數(shù)據(jù)量較大時(shí)，采用分塊查找算法。靜態(tài)查找表和動(dòng)態(tài)查找表 如果不需要對(duì)一個(gè)查找表進(jìn)行插入、刪除操作，則該查找表稱為靜態(tài)查找表；反之稱為動(dòng)態(tài)查找表 順序查找；從表中的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較，若找到，記錄的關(guān)鍵字與給定值相等，則查找成功；優(yōu)點(diǎn)；算法簡(jiǎn)單、對(duì)待查找的集合結(jié)構(gòu)沒(méi)有要求，無(wú)論記錄是否按關(guān)鍵字有序排列均可應(yīng)用。折半查找；也稱二分查找二叉排序樹機(jī)器查找算法； 又稱二叉查找樹。它可以是一棵空樹，若非空時(shí)具有下述性 質(zhì)；所有結(jié)點(diǎn)的關(guān)鍵字互相不同。 若根結(jié)點(diǎn)的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值。 若根結(jié)點(diǎn)的右子樹非空。則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值。 根結(jié)點(diǎn)的左，右子樹也分別為二叉排序樹。二叉排序樹的特點(diǎn)； 二叉排序樹中任一結(jié)點(diǎn) x，其左（右）子樹中任一結(jié)點(diǎn) y（若存在）的關(guān)鍵字必?。ù螅┯?x的關(guān)鍵字。 按中序遍歷樹所得到的中序序列是一個(gè)遞增有序序列。排序； 排序；是將若干數(shù)據(jù)元素按關(guān)鍵字的值以遞增（或遞減）次序排列的過(guò)程。 數(shù)據(jù)序列是待排序的數(shù)據(jù)元素的有限集合。 關(guān)鍵字；通常數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，以其中某個(gè)數(shù)據(jù)項(xiàng)作為排序依據(jù)，則該數(shù)據(jù)項(xiàng)稱為關(guān)鍵字 排序算法的穩(wěn)定性；在數(shù)據(jù)序列中，如果有兩個(gè)數(shù)據(jù)元素 ri 和rj，它們的關(guān)鍵字 ki 等于 kj，且在未排序時(shí)， ri 位于 rj 之前。如果排序后，元素 ri 仍在 rj 之前，則稱這樣的排序算法是穩(wěn)定的，否則是不穩(wěn)定的排序算法。內(nèi)排序與外排序； 內(nèi)排序；在待排序的數(shù)據(jù)序列中，數(shù)據(jù)元素個(gè)數(shù)少，整個(gè)排序過(guò)程中所有的數(shù)據(jù)元素都可以保存在內(nèi)存，則這樣的排序成為內(nèi)排序 外 排序；待排序的數(shù)據(jù)元素非常多，以至于它們必須存儲(chǔ)磁盤等外部存儲(chǔ)介質(zhì)上，則這樣的排序稱為外排序（過(guò)程中需要多次訪問(wèn)外存） 排序算法的性能評(píng)價(jià)； 排序算法的時(shí)間復(fù)雜度；指算法執(zhí)行中的數(shù)據(jù)比較次數(shù)、數(shù)據(jù)移 動(dòng)次數(shù)與待排序數(shù)據(jù)序列的元素個(gè)數(shù) n之間的關(guān)系。 排序算法的空間復(fù)雜度；指算法執(zhí)行中，除待排序數(shù)據(jù)序列本身所占用的內(nèi)存空間外，需要的附加內(nèi)存空間與待排序數(shù)據(jù)序列的元素個(gè)數(shù) n 之間的關(guān)系。 1，直接插入排序； 2，冒泡排序；（最好情況是移動(dòng)零次記錄，最壞情況將移動(dòng) n（ n1）/2） 3，簡(jiǎn)單選擇排序； 4，快速排序； 5，堆排序結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序的基本結(jié)構(gòu)； 1，順序結(jié)構(gòu)； 2，選擇結(jié)構(gòu)； 3，循環(huán)結(jié)構(gòu)；結(jié)構(gòu)化程序設(shè)計(jì)的基本原則； 1，自頂向下； 2，逐步求精； 3，模塊化； 4，限制使用 goto 語(yǔ)句； 面向?qū)ο蟪绦蛟O(shè)計(jì)；（ 231）面向?qū)ο蟪绦蛟O(shè)計(jì)的思想； 1，從現(xiàn)實(shí)世界中客觀存在的事物出發(fā)，盡可能運(yùn)用人類自然的思維方式去構(gòu)造軟件系統(tǒng)； 2，將事物的本質(zhì)特征經(jīng)抽象后表示為軟件系統(tǒng)的對(duì)象，以此作為系統(tǒng)構(gòu)造的基本單位； 3，使軟件系統(tǒng)能直 接映射問(wèn)題，并保持問(wèn)題中事物及其相互關(guān)系的本來(lái)面貌；軟件工程；軟件測(cè)試； 軟件測(cè)試的目的； 1983年 IEEE，其目的在于檢驗(yàn)它是否滿足規(guī)定的需要或能清預(yù)期結(jié)果與實(shí)際結(jié)果的差別。測(cè)試的方法； 測(cè)試性質(zhì)來(lái)分；靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。 靜態(tài)測(cè)試；就是測(cè)試人員閱讀、分析文檔或源程序及批注時(shí)所發(fā)現(xiàn)的問(wèn)題。 靜態(tài)測(cè)試；分為文檔測(cè)試和代碼測(cè)試。 動(dòng)態(tài)測(cè)試；是基于計(jì)算機(jī)的測(cè)試，就是在計(jì)算機(jī)或網(wǎng)絡(luò)上運(yùn)行被測(cè)試的系統(tǒng)，按照事先規(guī)定的測(cè)試計(jì)劃，運(yùn)行事先準(zhǔn)備的測(cè)試范例，取得運(yùn)行的數(shù)據(jù)，再將此數(shù)據(jù) 與測(cè)試計(jì)劃中的計(jì)劃數(shù)據(jù)相比較。若兩者一致，則測(cè)試通過(guò)；否則，發(fā)現(xiàn)有錯(cuò)誤，則找出錯(cuò)誤。測(cè)試的策略； 1，單元測(cè)試； 2，集成測(cè)試； 3，確認(rèn)測(cè)試； 4，系統(tǒng)測(cè)試；軟件維護(hù)： 1，糾正性維護(hù)； 2，適應(yīng)性維護(hù)； 3，完善性維護(hù)； 4，預(yù)防性維護(hù)； 目前軟件企業(yè)一般把自己的軟件產(chǎn)品維護(hù)活動(dòng)分為面向缺陷維護(hù)和面向功能維護(hù)兩類。 面向功能維護(hù)的條件是；該軟件產(chǎn)品在功能、性能、接口上存在某些不足，不能滿足用戶的某些需求，因而需要增加某些功能、性能、接口。第七章 計(jì)算機(jī)網(wǎng)絡(luò)；地理上分散的自主計(jì)算機(jī)通過(guò)通信線路和通信設(shè)備相互連接起來(lái)，在通信協(xié)議的控制下，進(jìn)行信息交換和資源共享或協(xié)同工作的計(jì)算機(jī)系統(tǒng)。 計(jì)算機(jī)網(wǎng)絡(luò)由通信子網(wǎng)和資源子網(wǎng)構(gòu)成計(jì)算機(jī)網(wǎng)絡(luò)的形成及發(fā)展；1，面向終端的計(jì)算機(jī)網(wǎng)絡(luò)； 2，計(jì)算機(jī) 計(jì)算機(jī)網(wǎng)絡(luò)； 3，開放式標(biāo)準(zhǔn)化網(wǎng)絡(luò)； 4，網(wǎng)絡(luò)互聯(lián)時(shí)代；計(jì)算機(jī)功能； 基本功能；信息交換、資源共享、協(xié)同工作 網(wǎng)絡(luò)應(yīng)用角度； 1，資源共享； 2，平衡負(fù)荷及分布處理； 3，信息快速傳輸與集中處理； 4，綜合信息服務(wù)。計(jì)算機(jī)網(wǎng)絡(luò)的分類； 按覆蓋 地理范圍； 1，局域網(wǎng)； 2，廣域網(wǎng)； 3，城域網(wǎng)網(wǎng)絡(luò)拓?fù)洌皇怯删W(wǎng)絡(luò)節(jié)點(diǎn)設(shè)備和通信介質(zhì)構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)圖。常見(jiàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；總線型、星型、環(huán)型、樹型和網(wǎng)狀等。 1，總線型拓?fù)洌徊捎脝胃鶄鬏斁€作為傳輸介質(zhì)，它將所有入網(wǎng)的計(jì)算機(jī)通過(guò)相應(yīng)的硬件接口直接接入到一條通信線路上。為防止信號(hào)反射，一般在總線兩端連有終結(jié)器匹配線路 阻抗。 優(yōu)點(diǎn)；結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)容易，易于安裝和維護(hù)；價(jià)格便宜，用戶結(jié)點(diǎn)入網(wǎng)靈活。 缺點(diǎn)；同一時(shí)刻只能有兩個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)相互通信，網(wǎng)絡(luò)延伸距離有限，網(wǎng)絡(luò)容納結(jié)點(diǎn)數(shù)有限任何一處故障都會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓。 2，星型拓?fù)?；是以一個(gè)結(jié)點(diǎn)為中心的處理系統(tǒng)，各種類型的入網(wǎng)計(jì)算機(jī)均與該中心節(jié)點(diǎn)通過(guò)物理鏈路直接相連，其他結(jié)點(diǎn)間不能直接通信，通信時(shí)需要通過(guò)該中心點(diǎn)轉(zhuǎn)發(fā)。優(yōu)點(diǎn)；結(jié)構(gòu)簡(jiǎn)單，管理方便，可擴(kuò)成性強(qiáng)，組網(wǎng)容易。 缺點(diǎn)；屬于集中控制，主結(jié)點(diǎn)負(fù)載過(guò)重，如果中央結(jié)點(diǎn)產(chǎn)生故障，則全網(wǎng)不能工作，所以對(duì)中央結(jié)點(diǎn)的可靠性和冗余度要求很高。環(huán)狀拓?fù)?；是將各臺(tái)聯(lián)網(wǎng)的計(jì)算機(jī)用通信線路鏈接成一個(gè)閉合的環(huán)。 優(yōu)點(diǎn)；一次通信信息在網(wǎng)中傳輸?shù)淖畲髠鬏斞舆t是固定的‘每個(gè)網(wǎng)上結(jié)點(diǎn)只與其他兩個(gè)結(jié)點(diǎn)有物理鏈路直接互聯(lián)。傳輸機(jī)制較為簡(jiǎn)單，實(shí)時(shí)性強(qiáng)。 缺點(diǎn)；環(huán)中任何一個(gè)結(jié)點(diǎn)出現(xiàn)故障都可能會(huì)終止全網(wǎng)運(yùn)行，因此可靠性較差。樹狀結(jié)構(gòu)； 優(yōu)點(diǎn)；易于擴(kuò)展和故障隔離。 缺點(diǎn)；對(duì)根的依賴性太大，如果根發(fā)生故障，則全網(wǎng)不能正常工 作，對(duì)根的可靠性要求很高。按用途；公用網(wǎng)和專用網(wǎng) 交換方式；電路交換網(wǎng)，報(bào)文交換網(wǎng)，分組交換網(wǎng)傳輸媒介；雙絞線網(wǎng)，同軸電纜網(wǎng)，光纖網(wǎng)，無(wú)線網(wǎng)；信道的帶寬；窄帶網(wǎng)，寬帶網(wǎng)； 拓?fù)浣Y(jié)構(gòu)；星形網(wǎng)，環(huán)形網(wǎng)，總線形網(wǎng)，樹形網(wǎng)； OIS/RM 模型分為七層；物理層（正確利用傳輸介質(zhì)）；數(shù)據(jù)鏈路層（連通每個(gè)結(jié)點(diǎn)）；網(wǎng)絡(luò)層（選擇路由）；傳輸層（找到對(duì)方主機(jī)）；會(huì)話層（指出對(duì)方實(shí)體是誰(shuí)）；表示成（決定用什么語(yǔ)言交談）；應(yīng)用層（指出做什么事）；傳輸層是整個(gè)分層體系協(xié)議的核心計(jì)算機(jī)網(wǎng)絡(luò)互聯(lián)設(shè)備； 1，中繼器； 優(yōu)點(diǎn)；安裝簡(jiǎn)單，使用方便，借個(gè)相對(duì)低廉。他不僅起到擴(kuò)展網(wǎng)絡(luò)距離的作用，還可以將不同傳輸介質(zhì)的網(wǎng)絡(luò)連接在一起。中繼器工作在物理層，對(duì)于高層協(xié)議完全透明。 2，網(wǎng)橋； 擴(kuò)展局域網(wǎng)最常見(jiàn)的方法是使用網(wǎng)橋優(yōu)點(diǎn)；過(guò)濾通信量。路由器； 當(dāng)兩個(gè)不同類型的網(wǎng)絡(luò)彼此相連時(shí)，必須使用路由器。路由器比網(wǎng)橋智能性更強(qiáng)，有路徑選擇能力，選擇最短路徑的能 力。網(wǎng)關(guān)； 當(dāng)連接兩個(gè)完全不同結(jié)構(gòu)的網(wǎng)絡(luò)時(shí)，必須使用網(wǎng)關(guān)。網(wǎng)關(guān)設(shè)在服務(wù)器、微機(jī)和大型機(jī)上。 常見(jiàn)的網(wǎng)關(guān)； 1，電子郵件網(wǎng)關(guān)； 2， IBM主機(jī)網(wǎng)關(guān)； 3，因特網(wǎng)網(wǎng)關(guān)； 4，局域網(wǎng)網(wǎng)關(guān)；集線器； 是中繼器的一中，主要以優(yōu)化網(wǎng)絡(luò)布線結(jié)構(gòu)，簡(jiǎn)化網(wǎng)絡(luò)管理為目標(biāo)而設(shè)計(jì)的。交換機(jī)；？？？ 網(wǎng)絡(luò)傳輸介質(zhì)； 有線傳 輸；雙絞線，同軸電纜，光纖。無(wú)線傳輸；紅外線，激光，衛(wèi)星通信 網(wǎng)絡(luò)操作系統(tǒng)；是指能夠控制和管理網(wǎng)絡(luò)資源的軟件系統(tǒng)。它的主要功能；控制和管理網(wǎng)絡(luò)的運(yùn)行、資源管理、文件管理、通信管理、用戶管理和系統(tǒng)管理等。 網(wǎng)絡(luò)服務(wù)必須安裝網(wǎng)絡(luò)操作系統(tǒng)，以便對(duì)網(wǎng)絡(luò)資源進(jìn)行管理，并為用戶機(jī)提供各種網(wǎng)絡(luò)服務(wù) 常見(jiàn)系統(tǒng)； UNIX、 Linux、 WindowsServer200 Novellware等 1， 數(shù)據(jù)信號(hào)； 數(shù)據(jù)可分為模擬數(shù)據(jù)和數(shù)字?jǐn)?shù)據(jù)； 模擬數(shù)據(jù)；在通信系統(tǒng)中，表示模擬數(shù)據(jù)的信號(hào)稱作模擬信號(hào)（在時(shí)間和幅度取值是連續(xù)的） 數(shù)字信號(hào)；在通信系統(tǒng)中，表示數(shù)字?jǐn)?shù)據(jù)的信號(hào)稱作數(shù)字信號(hào) (在時(shí)間上是離散的，在幅值上是經(jīng)過(guò)量化的、有二進(jìn)制代碼組成數(shù)字序列 )兩者可以相互轉(zhuǎn)化， 電話通信信道是傳輸音頻的模擬信號(hào)， 所謂調(diào)制；就是把數(shù)字信號(hào)轉(zhuǎn)換成電話線上傳輸?shù)哪M信號(hào)；解調(diào)；即把模擬信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)。合稱調(diào)制解調(diào)器模擬信號(hào)的數(shù)字化；采樣，量化，編碼。信道；信息傳輸?shù)谋亟?jīng)之路。信道（物理信道）（邏輯信道） 物理信道；是指用 來(lái)傳送信號(hào)或數(shù)據(jù)的物理通路。物理信道；傳輸介質(zhì)和有關(guān)設(shè)備組成 通信鏈路；網(wǎng)絡(luò)中有兩個(gè)結(jié)點(diǎn)之間的物理通路。通常把邏輯信道稱為“鏈接”。 數(shù)據(jù)通信方式； 1，單工通信； 2，半雙工通信； 3，雙工通信；單工通信；數(shù)據(jù)只能沿一個(gè)固定方向傳輸， 半雙工通信；允許數(shù)據(jù)沿兩個(gè)方向傳輸，但在任一時(shí)刻信息只能在一個(gè)方向傳輸。 雙工通信；允許數(shù)據(jù)同時(shí)沿兩個(gè)方向傳播 多路復(fù)用數(shù)；人們研究出在一條物理線路上建立多個(gè)通信信道的技術(shù) 通常分為； 1，頻分多路復(fù)用； 2，時(shí)分多路復(fù)用； 3，波分多路 復(fù)用； 4，碼分多址； 5，空分多址 頻分多路復(fù)用的主要特點(diǎn)；信號(hào)被劃分稱若干通道（頻道，波段），每個(gè)通道互不重疊，獨(dú)立進(jìn)行數(shù)據(jù)傳遞，（在無(wú)線電廣播和電視領(lǐng)域中應(yīng)用較多） ADSL是頻分多路復(fù)用。 時(shí)分多路復(fù)用 。是以信道傳輸時(shí)間作為分個(gè)對(duì)象，通過(guò)為多個(gè)信道分配互不重疊的時(shí)間片的方法來(lái)實(shí)現(xiàn)多路復(fù)用。 波分多路復(fù)用；就是在同一根光纖內(nèi)傳輸多路不同波長(zhǎng)的光信號(hào)，以提高單根光纖的傳輸能力。 碼分多址；又稱 CDMA采用地址碼和時(shí)間、頻率共同區(qū)分信道的方式。 特征；每個(gè)用戶具有特定的地 址碼，而地址碼之間相互具有正交性。（是有效資源頻率得到利用） 空分多址； SDMA 這種技術(shù)是將空間分割構(gòu)成不同的信道，從而實(shí)現(xiàn)頻率的重復(fù)使用，達(dá)到信道增容的目的。數(shù)據(jù)交換技術(shù)； 換； ； ；電路交換； 線路接續(xù)；當(dāng)用戶要發(fā)送信息時(shí)，由源交換機(jī)根據(jù)信息要達(dá)到的目的地址，把線路接到那個(gè)目的交換機(jī)。優(yōu)點(diǎn)；數(shù)據(jù)傳輸可靠、迅速且保持原來(lái)的序列。 缺點(diǎn)；在有的環(huán)境下，電路空閑時(shí)的信道容量被浪費(fèi)，而且數(shù)據(jù)傳輸階段的持續(xù)時(shí)間不長(zhǎng)的話，電路建立和拆除所用的時(shí)間也得不償失。報(bào)文交換； 在報(bào)文交換中，不需要在兩個(gè)站之間建立一條專用