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