NOIP初賽復(fù)習(xí)打印c++

分區(qū)聯(lián)賽初賽復(fù)習(xí)初賽考的知識(shí)點(diǎn)就是計(jì)算機(jī)基本常識(shí)、基本操作和程序設(shè)計(jì)基礎(chǔ)知識(shí)。其中選擇題考查的是知識(shí)，而問題解決類型的題目更加重視能力的考查。一般說來，選擇題只要多用心積累就可以了。問題解決題目的模式比較固定，大家應(yīng)當(dāng)做做以前的題目。寫運(yùn)行結(jié)果和程序填空也需要多做題目，并且培養(yǎng)良好的程序閱讀和分析能力，就像語文的閱讀理解一樣。近幾年來，初賽的考查范圍有了很大的變化，越來越緊跟潮流了。這就需要大家有比較廣泛的知識(shí)，包括計(jì)算機(jī)硬件、軟件、網(wǎng)絡(luò)、簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)（例如棧、隊(duì)列、樹和圖等）和簡(jiǎn)單的算法（例如排序、查找和搜索等），程序設(shè)計(jì)語言以及一些基本的數(shù)學(xué)知識(shí)和技巧（例如排列組合）。但最主要的，還是取決于你對(duì)程序設(shè)計(jì)語言的熟悉程度，再加上認(rèn)真仔細(xì)的心態(tài)。選擇題一、硬件計(jì)算機(jī)發(fā)展可劃分：年代元件第一代1946－1958電子管第二代1959－1964晶體管第三代1965－1970集成電路第四代1971－？大規(guī)模集成電路1946年2月，在美國賓夕法尼亞大學(xué)誕生了世界上第一臺(tái)電子計(jì)算機(jī)ENIAC（ElectronicNumericalIntegratorAndComputer），這臺(tái)計(jì)算機(jī)占地170平方米，重30噸，用了18000多個(gè)電子管，每秒能進(jìn)行5000次加法運(yùn)算。馮·諾依曼理論1944年，美籍匈牙利數(shù)學(xué)家馮·諾依曼提出計(jì)算機(jī)基本結(jié)構(gòu)和工作方式的設(shè)想，為計(jì)算機(jī)的誕生和發(fā)展提供了理論基礎(chǔ)。時(shí)至今日，盡管計(jì)算機(jī)軟硬件技術(shù)飛速發(fā)展，但計(jì)算機(jī)本身的體系結(jié)構(gòu)并沒有明顯的突破，當(dāng)今的計(jì)算機(jī)仍屬于馮·諾依曼架構(gòu)。其理論要點(diǎn)如下：1、計(jì)算機(jī)硬件設(shè)備由存儲(chǔ)器、運(yùn)算器、控制器、輸入設(shè)備和輸出設(shè)備5部分組成。2、存儲(chǔ)程序思想——把計(jì)算過程描述為由許多命令按一定順序組成的程序，然后把程序和數(shù)據(jù)一起輸入計(jì)算機(jī)，計(jì)算機(jī)對(duì)已存入的程序和數(shù)據(jù)處理后，輸出結(jié)果。我國的計(jì)算機(jī)發(fā)展情況·我國從1956年開始計(jì)算機(jī)的科研和教學(xué)工作；·1960年我國第一臺(tái)自行設(shè)計(jì)的通用電子計(jì)算機(jī)107機(jī)誕生；1964年我國研制成大型通用電子計(jì)算機(jī)119機(jī)；·1983年每秒運(yùn)行一億次的銀河巨型計(jì)算機(jī)在國防科技大學(xué)誕生；1992年研制成功每秒運(yùn)行10億次的“銀河Ⅱ”巨型計(jì)算機(jī)；1997年又研制成功每秒運(yùn)行130億次的“銀河Ⅲ”巨型計(jì)算機(jī)；·我國較有名的微型計(jì)算機(jī)品牌有：“聯(lián)想”、“長(zhǎng)城”、“方正”等；微型機(jī)的主要技術(shù)指標(biāo)1、字長(zhǎng)：知己算計(jì)能夠直接處理的二進(jìn)制數(shù)據(jù)的位數(shù)。單位為位（BIT）2、主頻：指計(jì)算機(jī)主時(shí)鐘在一秒鐘內(nèi)發(fā)出的脈沖數(shù)，在很大程度上決定了計(jì)算機(jī)的運(yùn)算速度。3、內(nèi)存容量：是標(biāo)志計(jì)算機(jī)處理信息能力強(qiáng)弱的一向技術(shù)指標(biāo)。單位為字節(jié)（BYTE）。8BIT=1BYTE1024B=1KB1024KB=1MB4、外存容量：一般指軟盤、硬盤、光盤。計(jì)算機(jī)的特點(diǎn)：運(yùn)算速度快，運(yùn)算精度高，具有記憶能力，具有邏輯判斷能力，具有自動(dòng)控制能力；計(jì)算機(jī)的應(yīng)用：1、數(shù)值計(jì)算：彈道軌跡、天氣預(yù)報(bào)、高能物理等等2、信息管理：企業(yè)管理、物資管理、電算化等3、過程控制：工業(yè)自動(dòng)化控制，衛(wèi)星飛行方向控制4、輔助工程：CAD、CAM、CAT、CAI等計(jì)算機(jī)硬件由五大部分組成：運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備、輸出設(shè)備。中央處理器（CPU——CentralProcessingUnit）由運(yùn)算器、控制器和一些寄存器組成；運(yùn)算器進(jìn)行各種算術(shù)運(yùn)算和邏輯運(yùn)算；控制器是計(jì)算機(jī)的指揮系統(tǒng)；CPU的主要性能指標(biāo)是主頻和字長(zhǎng)。存儲(chǔ)器內(nèi)部存儲(chǔ)器中央處理器能直接訪問的存儲(chǔ)器稱為內(nèi)部存儲(chǔ)器，它包括快速緩沖存儲(chǔ)器和主存儲(chǔ)器，中央處理器不能直接訪問的存儲(chǔ)器稱為外部存儲(chǔ)器，外部存儲(chǔ)器中的信息必須調(diào)入內(nèi)存后才能為中央處理器處理。主存儲(chǔ)器：內(nèi)存也常泛稱主存，但嚴(yán)格上說，只有當(dāng)內(nèi)存中只有主存，而沒有快速緩沖存儲(chǔ)器時(shí)，才能稱為主存。主存儲(chǔ)器按讀寫功能，可分只讀存儲(chǔ)器（ROM）和隨機(jī)存儲(chǔ)器（RAM）兩種。外部存儲(chǔ)器外存儲(chǔ)器：也稱為輔助存儲(chǔ)器，一般容量較大，速度比主存較慢。硬盤（Harddisk）：目前的硬盤大多采用了溫徹斯特技術(shù)，所以又稱為“溫盤”；溫氏技術(shù)的特點(diǎn)是：將盤片、讀寫磁頭及驅(qū)動(dòng)裝置精密地組裝在一個(gè)密封盒里；采用接觸式起停，非接觸式讀寫的方式（磁盤不工作時(shí)，磁頭停在磁盤表面的起停區(qū)，一旦加電后，磁頭隨著盤片旋轉(zhuǎn)的氣流“飛”起來，懸浮在磁盤表面，進(jìn)行讀寫）。軟盤（FloppyDisk）：目前常見的是3.5英寸/1.44MB的軟盤。光盤存儲(chǔ)器（CD-ROM）：普通的CD-ROM，只能讀，不能寫；CD盤片的存儲(chǔ)量大約是650MB。輸入設(shè)備·鍵盤（Keyboard）：目前大多使用104或108鍵盤·鼠標(biāo)（Mouse）：主要有機(jī)械型鼠標(biāo)和光電型鼠標(biāo)兩種·手寫筆·觸摸屏·麥克風(fēng)·掃描儀（Scanner）·視頻輸入設(shè)備·條形碼掃描器輸出設(shè)備·顯示器（Monitor）：目前主要有CRT（陰極射線管）顯示器和LCD液晶顯示器?！ご蛴C(jī)（Printer）：主要有針式打印機(jī)、噴墨打印機(jī)、激光打印機(jī)?！だL圖儀·音箱例題微型計(jì)算機(jī)的問世是由于(C)的出現(xiàn)。A)中小規(guī)模集成電路B)晶體管電路C)(超)大規(guī)模集成電路D)電子管電路中央處理器(CPU)能訪問的最大存儲(chǔ)器容量取決于(A)。地址總線B)數(shù)據(jù)總線C)控制總線D)實(shí)際內(nèi)存容量微型計(jì)算機(jī)中，(C)的存取速度最快。A)高速緩存B)外存儲(chǔ)器C)寄存器D)內(nèi)存儲(chǔ)器在計(jì)算機(jī)硬件系統(tǒng)中，cache是(D)存儲(chǔ)器。A)只讀B)可編程只讀C)可擦除可編程只讀D)高速緩沖若我們說一個(gè)微機(jī)的CPU是用的PII300，此處的300確切指的是(A)。A)CPU的主時(shí)鐘頻率B)CPU產(chǎn)品的系列號(hào)C)每秒執(zhí)行300百萬條指令D)此種CPU允許最大內(nèi)存容量計(jì)算機(jī)主機(jī)是由CPU與（D）構(gòu)成的。A.控制器B.輸入、輸出設(shè)備C.運(yùn)算器D.內(nèi)存儲(chǔ)器計(jì)算機(jī)系統(tǒng)總線上傳送的信號(hào)有（B）。A.地址信號(hào)與控制信號(hào)B.數(shù)據(jù)信號(hào)、控制信號(hào)與地址信號(hào)C.控制信號(hào)與數(shù)據(jù)信號(hào)D.數(shù)據(jù)信號(hào)與地址信號(hào)不同類型的存儲(chǔ)器組成了多層次結(jié)構(gòu)的存儲(chǔ)器體系，按存取速度從快到慢的排列是（C）。A.快存/輔存/主存B.外存/主存/輔存C.快存/主存/輔存D.主存/輔存/外存微機(jī)內(nèi)存儲(chǔ)器的地址是按（C）編址的。二進(jìn)制位B.字長(zhǎng)C.字節(jié)D.微處理器的型號(hào)在微機(jī)中，通用寄存器的位數(shù)是（C）。A8位B．16位C.計(jì)算機(jī)字長(zhǎng)D．32位不同的計(jì)算機(jī)，其指令系統(tǒng)也不同，這主要取決于（C）。A所用的操作系統(tǒng)B.系統(tǒng)的總體結(jié)構(gòu)C．所用的CPUD．所用的程序設(shè)計(jì)語言下列說法中，哪個(gè)（些）是錯(cuò)誤的（

BDE

）。

A）程序是指令的序列，它有三種結(jié)構(gòu)：順序、分支和循環(huán)。

B）數(shù)據(jù)總線決定了中央處理器CPU所能訪問的最大內(nèi)存空間的大小。

C）中央處理器CPU內(nèi)部有寄存器組，用來儲(chǔ)存數(shù)據(jù)。

D）不同廠家生產(chǎn)的CPU所能處理的指令集是相同的。

E）數(shù)據(jù)傳輸過程中可能會(huì)出錯(cuò)，奇偶校驗(yàn)法可以檢測(cè)出數(shù)據(jù)中哪一位在傳輸中出了差錯(cuò)。CPU訪問內(nèi)存的速度比訪問下列哪個(gè)（些）存儲(chǔ)設(shè)備要慢（

AD

）。

A）寄存器

B）硬盤

C）軟盤

D）高速緩存

E）光盤下列哪個(gè)（些）不是個(gè)人計(jì)算機(jī)的硬件組成部分（

B

）。

A）主板

B）虛擬內(nèi)存

C）電源

D）硬盤

E）總線美籍匈牙利數(shù)學(xué)家馮·諾依曼對(duì)計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)是（C）。提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。是世界上第一個(gè)編寫計(jì)算機(jī)程序的人。提出存儲(chǔ)程序工作原理，并設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC。采用集成電路作為計(jì)算機(jī)的主要功能部件。指出計(jì)算機(jī)性能將以每?jī)赡攴环乃俣认蚯鞍l(fā)展。下列哪個(gè)不是CPU（中央處理單元）（B）。A.IntelItaniumB.DDRSDRAMC.AMDAthlon64D.AMDOpteronE.IBMPower5下列說法中錯(cuò)誤的是（B）。CPU的基本功能就是執(zhí)行指令。CPU訪問內(nèi)存的速度快于訪問高速緩存的速度。CPU的主頻是指CPU在1秒內(nèi)完成的指令周期數(shù)。在一臺(tái)計(jì)算機(jī)內(nèi)部，一個(gè)內(nèi)存地址編碼對(duì)應(yīng)唯一的一個(gè)內(nèi)存單元。數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，是影響計(jì)算機(jī)性能的因素之一。用靜電吸附墨粉后轉(zhuǎn)移到紙張上，是哪種輸出設(shè)備的工作方式（C）。A.針式打印機(jī)B.噴墨打印機(jī)C.激光打印機(jī)D.筆式繪圖儀E.噴墨繪圖儀處理器A每秒處理的指令數(shù)是處理器B的2倍。某一特定程序P分別編譯為處理器A和處理器B的指令，編譯結(jié)果處理器A的指令數(shù)是處理器B的4倍。已知程序P在處理器A上執(zhí)行需要1個(gè)小時(shí)，那么在輸入相同的情況下，程序P在處理器B上執(zhí)行需要（D）小時(shí)。A.4 B.2 C.1 D.1/2 E.1/4以下哪個(gè)不是計(jì)算機(jī)的輸出設(shè)備（D）。A.音箱B.顯示器C.打印機(jī)D.掃描儀E.繪圖儀進(jìn)制與編碼四種常用的數(shù)制及它們之間的相互轉(zhuǎn)換：進(jìn)制基數(shù)基數(shù)個(gè)數(shù)權(quán)進(jìn)數(shù)規(guī)律十進(jìn)制0、1、2、3、4、5、6、7、8、91010i逢十進(jìn)一二進(jìn)制0、122i逢二進(jìn)一八進(jìn)制0、1、2、3、4、5、6、788i逢八進(jìn)一十六進(jìn)制0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F1616i逢十六進(jìn)一十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)的方法：二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的方法：按權(quán)展開求和法1．二進(jìn)制與十進(jìn)制間的相互轉(zhuǎn)換：（1）二進(jìn)制轉(zhuǎn)十進(jìn)制方法：“按權(quán)展開求和”例：（1011.01）2＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10＝（8＋0＋2＋1＋0＋0.25）10＝（11.25）10規(guī)律：個(gè)位上的數(shù)字的次數(shù)是0，十位上的數(shù)字的次數(shù)是1，......，依獎(jiǎng)遞增，而十分位的數(shù)字的次數(shù)是-1，百分位上數(shù)字的次數(shù)是-2，......，依次遞減。注意：不是任何一個(gè)十進(jìn)制小數(shù)都能轉(zhuǎn)換成有限位的二進(jìn)制數(shù)。（2）十進(jìn)制轉(zhuǎn)二進(jìn)制·十進(jìn)制整數(shù)轉(zhuǎn)二進(jìn)制數(shù)：“除以2取余，逆序排列”（短除反取余法）例：（89）10＝（1011001）2289244 ……1222 ……0211 ……025 ……122 ……121 ……00 ……1·十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制數(shù)：“乘以2取整，順序排列”（乘2取整法）例：(0．625)10=(0．101)20．625X21．251X20．50X21．012．八進(jìn)制與二進(jìn)制的轉(zhuǎn)換：二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)：從小數(shù)點(diǎn)開始，整數(shù)部分向左、小數(shù)部分向右，每3位為一組用一位八進(jìn)制數(shù)的數(shù)字表示，不足3位的要用“0”補(bǔ)足3位，就得到一個(gè)八進(jìn)制數(shù)。八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：把每一個(gè)八進(jìn)制數(shù)轉(zhuǎn)換成3位的二進(jìn)制數(shù)，就得到一個(gè)二進(jìn)制數(shù)。例：將八進(jìn)制的37.416轉(zhuǎn)換成二進(jìn)制數(shù)：37．416011111．100001110即：（37.416）8＝（11111.10000111）2例：將二進(jìn)制的10110.0011轉(zhuǎn)換成八進(jìn)制：010110.00110026.14即：（10110.011）2＝（26.14）83．十六進(jìn)制與二進(jìn)制的轉(zhuǎn)換：二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)：從小數(shù)點(diǎn)開始，整數(shù)部分向左、小數(shù)部分向右，每4位為一組用一位十六進(jìn)制數(shù)的數(shù)字表示，不足4位的要用“0”補(bǔ)足4位，就得到一個(gè)十六進(jìn)制數(shù)。十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：把每一個(gè)八進(jìn)制數(shù)轉(zhuǎn)換成4位的二進(jìn)制數(shù)，就得到一個(gè)二進(jìn)制數(shù)。例：將十六進(jìn)制數(shù)5DF.9轉(zhuǎn)換成二進(jìn)制：5DF．9010111011111．1001即：（5DF.9）16＝（10111011111.1001）2例：將二進(jìn)制數(shù)1100001.111轉(zhuǎn)換成十六進(jìn)制：01100001．111061．E即：（1100001.111）2＝（61.E）16注意：以上所說的二進(jìn)制數(shù)均是無符號(hào)的數(shù)。這些數(shù)的范圍如下表：無符號(hào)位二進(jìn)制數(shù)位數(shù)數(shù)值范圍十六進(jìn)制范圍表示法8位二進(jìn)制數(shù)0~255（255=28-1）00~0FFH16位二進(jìn)制數(shù)0~65535（65535=216-1）0000H~0FFFFH32位二進(jìn)制數(shù)0~232-100000000H~0FFFFFFFFH

帶符號(hào)數(shù)的機(jī)器碼表示方法1．帶符號(hào)二進(jìn)制數(shù)的表示方法：帶符號(hào)二進(jìn)制數(shù)用最高位的一位數(shù)來表示符號(hào)：0表示正，1表示負(fù)。含符號(hào)位二進(jìn)制數(shù)位數(shù)數(shù)值范圍十六進(jìn)制范圍表示法8位二進(jìn)制數(shù)-128~+12780H~7FH16位二進(jìn)制數(shù)-32768~+327678000H~7FFFH32位二進(jìn)制數(shù)-2147483648~+214748364780000000H~7FFFFFFFH2、符號(hào)位的表示：最常用的表示方法有原碼、反碼和補(bǔ)碼。（1）原碼表示法：一個(gè)機(jī)器數(shù)x由符號(hào)位和有效數(shù)值兩部分組成，設(shè)符號(hào)位為x0，x真值的絕對(duì)值|x|=x1x2x3...xn，則x的機(jī)器數(shù)原碼可表示為：[x]原=，當(dāng)x>=0時(shí)，x0=0，當(dāng)x<0時(shí)，x0=1。例如：已知：x1=-1011B，x2=+1001B，則x1，x2有原碼分別是[x1]原=11011B，[x2]原=01001B規(guī)律：正數(shù)的原碼是它本身，負(fù)數(shù)的原碼是取絕對(duì)值后，在最高位（左端）補(bǔ)“1”。（2）反碼表示法：一個(gè)負(fù)數(shù)的原碼符號(hào)位不變，其余各位按位取反就是機(jī)器數(shù)的反碼表示法。正數(shù)的反碼與原碼相同。按位取反的意思是該位上是1的，就變成0，該位上是0的就變成1。即1=0，0=1例：，，求和。解：=，=（3）補(bǔ)碼表示法：首先分析兩個(gè)十進(jìn)制數(shù)的運(yùn)算：78-38=41，79+62=141如果使用兩位數(shù)的運(yùn)算器，做79+62時(shí)，多余的100因?yàn)槌隽诉\(yùn)算器兩位數(shù)的范圍而自動(dòng)丟棄，這樣在做78-38的減法時(shí)，用79+62的加法同樣可以得到正確結(jié)果。模是批一個(gè)計(jì)量系統(tǒng)的測(cè)量范圍，其大小以計(jì)量進(jìn)位制的基數(shù)為底數(shù)，位數(shù)為指數(shù)的冪。如兩位十進(jìn)制數(shù)的測(cè)量范圍是1——9，溢出量是100，模就是102=100，上述運(yùn)算稱為模運(yùn)算，可以寫作：79+（-38）=79+62（mod100)進(jìn)一步寫為-38=62，此時(shí)就說–38的補(bǔ)法（對(duì)模100而言）是62。計(jì)算機(jī)是一種有限字長(zhǎng)的數(shù)字系統(tǒng)，因此它的運(yùn)算都是有模運(yùn)算，超出模的運(yùn)算結(jié)果都將溢出。n位二進(jìn)制的模是2n,一個(gè)數(shù)的補(bǔ)碼記作[x]補(bǔ)，設(shè)模是M，x是真值，則補(bǔ)碼的定義如下：例：設(shè)字長(zhǎng)n=8位，x=-1011011B，求[x]補(bǔ)。解：因?yàn)閚=8，所以模M=28=100000000B，x<0，所以[x]補(bǔ)=M+x=100000000B-1011011B=10100101B注意：這個(gè)x的補(bǔ)碼的最高位是“1”，表明它是一個(gè)負(fù)數(shù)。對(duì)于二進(jìn)制數(shù)還有一種更加簡(jiǎn)單的方法由原碼求出補(bǔ)碼：（1）正數(shù)的補(bǔ)碼表示與原碼相同；（2）負(fù)數(shù)的補(bǔ)碼是將原碼符號(hào)位保持“1”之后，其余各位按位取反，末位再加1便得到補(bǔ)碼，即取其原碼的反碼再加“1”：[x]補(bǔ)=[x]反+1。下表列出的8位二進(jìn)制原碼，反碼和補(bǔ)碼并將補(bǔ)碼用十六進(jìn)制表示。真值原碼（B）反碼（B）補(bǔ)碼（B）補(bǔ)碼（H）+1270111111101111111011111117F+3900100111001001110010011127+000000000000000000000000000-010000000111111110000000000-39101001111101100011011001D9-12711111111100000001000000181-128無法表示無法表示1000000080從上可看出，真值+0和-0的補(bǔ)碼表示是一致的，但在原碼和反碼表示中具有不同形式。8位補(bǔ)碼機(jī)器數(shù)可以表示-128，但不存在+128的補(bǔ)碼與之對(duì)應(yīng)，由此可知，8位二進(jìn)制補(bǔ)碼能表示數(shù)的范圍是-128——+127。還要注意，不存在-128的8位原碼和反碼形式。定點(diǎn)數(shù)和浮點(diǎn)數(shù)（一）定點(diǎn)數(shù)（Fixed-PointNumber）計(jì)算機(jī)處理的數(shù)據(jù)不僅有符號(hào)，而且大量的數(shù)據(jù)帶有小數(shù)，小數(shù)點(diǎn)不占有二進(jìn)制一位而是隱含在機(jī)器數(shù)里某個(gè)固定位置上。通常采取兩種簡(jiǎn)單的約定：一種是約定所有機(jī)器數(shù)的小數(shù)的小數(shù)點(diǎn)位置隱含在機(jī)器數(shù)的最低位之后，叫定點(diǎn)純整機(jī)器數(shù)，簡(jiǎn)稱定點(diǎn)整數(shù)。另一種約定所有機(jī)器數(shù)的小數(shù)點(diǎn)隱含在符號(hào)位之后、有效部分最高位之前，叫定點(diǎn)純小數(shù)機(jī)器數(shù)，簡(jiǎn)稱定點(diǎn)小數(shù)。無論是定點(diǎn)整數(shù)，還是定點(diǎn)小數(shù)，都可以有原碼、反碼和補(bǔ)碼三種形式。（二）浮點(diǎn)數(shù)（Floating-PointNumber）計(jì)算機(jī)多數(shù)情況下采作浮點(diǎn)數(shù)表示數(shù)值，它與科學(xué)計(jì)數(shù)法相似，把一個(gè)二進(jìn)制數(shù)通過移動(dòng)小數(shù)點(diǎn)位置表示成階碼和尾數(shù)兩部分： 其中：E——N的階碼（Expoent），是有符號(hào)的整數(shù) S——N的尾數(shù)（Mantissa），是數(shù)值的有效數(shù)字部分，一般規(guī)定取二進(jìn)制定點(diǎn)純小數(shù)形式。例：1011101B=2+7*0.1011101，101.1101B=2+3*0.1011101，0.01011101B=2-1*0.1011101 浮點(diǎn)數(shù)的格式如下：E0E1E2……………En

E0E1E2……………En階符階尾符尾數(shù) 浮點(diǎn)數(shù)由階碼和尾數(shù)兩部分組成，底數(shù)2不出現(xiàn)，是隱含的。階碼的正負(fù)符號(hào)E0，在最前位，階反映了數(shù)N小數(shù)點(diǎn)的位置，常用補(bǔ)碼表示。二進(jìn)制數(shù)N小數(shù)點(diǎn)每左移一位，階增加1。尾數(shù)是這點(diǎn)小數(shù)，常取補(bǔ)碼或原碼，碼制不一定與階碼相同，數(shù)N的小數(shù)點(diǎn)右移一位，在浮點(diǎn)數(shù)中表現(xiàn)為尾數(shù)左移一位。尾數(shù)的長(zhǎng)度決定了數(shù)N的精度。尾數(shù)符號(hào)叫尾符，是數(shù)N的符號(hào)，也占一位。例：寫出二進(jìn)制數(shù)-101.1101B的浮點(diǎn)數(shù)形式，設(shè)階碼取4位補(bǔ)碼，尾數(shù)是8位原碼。-101.1101=-0.1011101*2+3浮點(diǎn)形式為：階碼0011尾數(shù)11011101補(bǔ)充解釋：階碼0011中的最高位“0”表示指數(shù)的符號(hào)是正號(hào)，后面的“011”表示指數(shù)是“3”；尾數(shù)11011101的最高位“1”表明整個(gè)小數(shù)是負(fù)數(shù)，余下的1011101是真正的尾數(shù)。例：計(jì)算機(jī)浮點(diǎn)數(shù)格式如下，寫出x=0.0001101B的規(guī)格化形式，階碼是補(bǔ)碼，尾數(shù)是原碼。x=0.0001101=0.1101*10-3又[-3]補(bǔ)=[-001B]補(bǔ)=[1011]補(bǔ)=1101B所以浮點(diǎn)數(shù)形式是110101101000ASCII碼(AmericanStandardCodeforInformationInterchange)美國標(biāo)準(zhǔn)信息交換代碼將每個(gè)字符用7位的二進(jìn)制數(shù)來表示，共有128種狀態(tài)大小字母、0…9、其它符號(hào)、控制符‘0’――48‘A’――65‘a(chǎn)’――97漢字信息編碼漢字輸入碼漢字輸入方法大體可分為：區(qū)位碼（數(shù)字碼）、音碼、形碼、音形碼?！^(qū)位碼：優(yōu)點(diǎn)是無重碼或重碼率低，缺點(diǎn)是難于記憶；·音碼：優(yōu)點(diǎn)是大多數(shù)人都易于掌握，但同音字多，重碼率高，影響輸入的速度；·形碼：根據(jù)漢字的字型進(jìn)行編碼，編碼的規(guī)則較多，難于記憶，必須經(jīng)過訓(xùn)練才能較好地掌握；重碼率低；·音形碼：將音碼和形碼結(jié)合起來，輸入漢字，減少重碼率，提高漢字輸入速度。2．漢字交換碼漢字交換碼是指不同的具有漢字處理功能的計(jì)算機(jī)系統(tǒng)之間在交換漢字信息時(shí)所使用的代碼標(biāo)準(zhǔn)。自國家標(biāo)準(zhǔn)GB2312－80公布以來，我國一直延用該標(biāo)準(zhǔn)所規(guī)定的國標(biāo)碼作為統(tǒng)一的漢字信息交換碼。GB2312－80標(biāo)準(zhǔn)包括了6763個(gè)漢字，按其使用頻度分為一級(jí)漢字3755個(gè)和二級(jí)漢字3008個(gè)。一級(jí)漢字按拼音排序，二級(jí)漢字按部首排序。此外，該標(biāo)準(zhǔn)還包括標(biāo)點(diǎn)符號(hào)、數(shù)種西文字母、圖形、數(shù)碼等符號(hào)682個(gè)。由于GB2312－80是80年代制定的標(biāo)準(zhǔn)，在實(shí)際應(yīng)用時(shí)常常感到不夠，所以，建議處理文字信息的產(chǎn)品采用新頒布的GB18030信息交換用漢字編碼字符集，這個(gè)標(biāo)準(zhǔn)繁、簡(jiǎn)字均處同一平臺(tái)，可解決兩岸三地間GB碼與BIG5碼間的字碼轉(zhuǎn)換不便的問題。3．字形存儲(chǔ)碼字形存儲(chǔ)碼是指供計(jì)算機(jī)輸出漢字（顯示或打?。┯玫亩M(jìn)制信息，也稱字模。通常，采用的是數(shù)字化點(diǎn)陣字模。如下圖：

123456789101112131415161

2

3

4

5

6

7

8

9

1616×16點(diǎn)表示10

11

12

13

14

15

16

一般的點(diǎn)陣規(guī)模有16×16，24×24，32×32，64×64等，每一個(gè)點(diǎn)在存儲(chǔ)器中用一個(gè)二進(jìn)制位（bit）存儲(chǔ)。例如，在16×16的點(diǎn)陣中，需16×16bit=32byte的存儲(chǔ)空間。在相同點(diǎn)陣中，不管其筆劃繁簡(jiǎn)，每個(gè)漢字所占的字節(jié)數(shù)相等。為了節(jié)省存儲(chǔ)空間，普遍采用了字形數(shù)據(jù)壓縮技術(shù)。所謂的矢量漢字是指用矢量方法將漢字點(diǎn)陣字模進(jìn)行壓縮后得到的漢字字形的數(shù)字化信息。例題十進(jìn)制數(shù)11/128可用二進(jìn)制數(shù)碼序列表示為(D)A)1011/1000000B)1011/100000000C)0.001011D)0.0001011算式(2047)10－(3FF)16＋(2000)8的結(jié)果是(A)A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16已知x=(0.1011010)2,則[x/2]=(C)2。A)0.1011101.B)11110110C)0.0101101D)0.100110已知A=35H,則A∧05H∨A∧3OH的結(jié)果是:(C)。A)3OHB)05HC)35HD)53H[x]補(bǔ)碼=10011000，其原碼為(B)A)011001111B)11101000C)11100110D)01100101下列無符號(hào)數(shù)中，最小的數(shù)是（C）A.（11011001）2B.(75)10C.(37)8D.(2A)16計(jì)算機(jī)的運(yùn)算速度取決于給定的時(shí)間內(nèi)，它的處理器所能處理的數(shù)據(jù)量。處理器一次能處理的數(shù)據(jù)量叫字長(zhǎng)。已知64位的奔騰處理器一次能處理64個(gè)信息位，相當(dāng)于（A）字節(jié)。A.8個(gè)B.1個(gè)C.16個(gè)D.2個(gè)在24*24點(diǎn)陣的“字庫”中，漢字“一”與“編”的字模占用字節(jié)數(shù)分別是（C）A.32，32B.32，72C.72，72D.72，32計(jì)算機(jī)中的數(shù)有浮點(diǎn)數(shù)與定點(diǎn)數(shù)兩種，其中用浮點(diǎn)數(shù)表示的數(shù)，通常由（C）這兩部分組成。A.指數(shù)與基數(shù)B.尾數(shù)與小數(shù)C.階碼與尾數(shù)D.整數(shù)與小數(shù)十進(jìn)制算術(shù)表達(dá)式：3*512+7*64＋4*8＋5的運(yùn)算結(jié)果，用二進(jìn)制表示為（B）．A.10111100101B.11111100101C1111l0100101D.11111101101十進(jìn)制數(shù)100.625等值于二進(jìn)制數(shù)（B）。A.1001100.101B.1100100.101C.1100100.011D.1001100.11E.1001100.01組成’教授’（jiaoshou）’副教授’（fujiaoshou）與’講師’（jiangshi）這三個(gè)詞的漢字，在GB2312－80字符集中都是一級(jí)漢字．對(duì)這三個(gè)詞排序的結(jié)果是（D）．A教授，副教授，講師B．副教授，教授，講師C講師，副教授，教授D．副教授，講師，教授GB2312-80規(guī)定了一級(jí)漢字3755個(gè)，二級(jí)漢字3008個(gè)，其中二級(jí)漢字字庫中的漢字是以（B）為序排列的。A.以筆劃多少B.以部首C.以ASCⅡ碼D.以機(jī)內(nèi)碼十進(jìn)制數(shù)2004等值于八進(jìn)制數(shù)（B）。A.3077B.3724C.2766D.4002E.3755(2004)10+(32)16的結(jié)果是（D）。A.(2036)10B.(2054)16C.(4006)10D.(100000000110)2E.(2036)16以下二進(jìn)制數(shù)的值與十進(jìn)制數(shù)23.456的值最接近的是（D）。A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.1111三、軟件與操作系統(tǒng)計(jì)算機(jī)軟件可分為系統(tǒng)軟件和應(yīng)用軟件兩大類?！は到y(tǒng)軟件：用來支持應(yīng)用軟件的開發(fā)和運(yùn)行的，主要是操作系統(tǒng)軟件，如：DOS、Windows95/98/2000、Unix、Linux、WindowsNT；·應(yīng)用軟件：為了某個(gè)應(yīng)用目的而編寫的軟件，主要有文字處理軟件、電子表格軟件、數(shù)據(jù)庫管理軟件等。操作系統(tǒng)（OS——OperatingSystem）操作系統(tǒng)是控制與管理計(jì)算機(jī)系統(tǒng)資源的軟件，是硬件的第一層擴(kuò)充，任何應(yīng)用軟件的運(yùn)行都必須依靠操作系統(tǒng)的支持。Windows系列操作系統(tǒng)Windows是Microsoft公司開發(fā)的圖形化界面的操作系統(tǒng)?！せ靖拍睿簣D標(biāo)、任務(wù)欄、標(biāo)題欄、菜單欄、滾動(dòng)條、工具欄、對(duì)話框、開始菜單……·基本操作：（1）鼠標(biāo)單擊、雙擊、拖動(dòng)，左鍵、右鍵功能；（2）窗口操作：最大（?。┗?、大小調(diào)整、拖動(dòng)、關(guān)閉、排列、切換；（3）菜單操作：激活、選擇；★命令項(xiàng)的約定——正常顯示和灰色顯示；命令后帶“…”：執(zhí)行命令則彈出對(duì)話框；帶快捷鍵：某些菜單命令的后面標(biāo)有對(duì)應(yīng)的鍵盤命令，稱為該命令的快捷鍵或熱鍵；選中標(biāo)志：某些命令選項(xiàng)的左側(cè)有用打勾表示的選中標(biāo)志，說明此命令功能正在起作用；命令后帶“?”：級(jí)聯(lián)：此命令后會(huì)有下一級(jí)的子命令菜單彈出供用戶作進(jìn)一步選擇；★快捷菜單——當(dāng)鼠標(biāo)位于某個(gè)對(duì)象上，單擊鼠標(biāo)右鍵，可打開有關(guān)對(duì)象的快捷菜單；（4）剪貼板：復(fù)制（Ctrl－C）、粘貼（Ctrl－V）、剪切（Ctrl－X）復(fù)制屏幕圖像：可將當(dāng)前屏幕圖形以BMP格式傳送到剪貼板……（5）其它：查找、運(yùn)行、切換Windows、進(jìn)入DOS環(huán)境、文件夾選項(xiàng)輸入法切換，中、英文切換，半角/全角切換軟鍵盤：是在屏幕上顯示的一個(gè)鍵盤圖形，用戶可用鼠標(biāo)點(diǎn)擊其中某個(gè)鍵以替代實(shí)際的按鍵；·各種文件的后綴名：bat、com、exe、sys、tmp、zip、……doc、xls、txt、htm、……bmp、gif、jpg、psd、……wav、avi、mp3、swf……DOS（DiskOperatingSystem）操作系統(tǒng)由美國Microsoft公司發(fā)行的DOS稱為MS－DOS，主要由IO.sys、MSDOS.sys、COMMAND.COM三個(gè)基本文件和幾十個(gè)內(nèi)、外部命令文件組成。*主要命令：·DIR——顯示磁盤文件目錄·CD——改變當(dāng)前目錄·MD——建立目錄·RD——?jiǎng)h除目錄·DATE——顯示和設(shè)置系統(tǒng)日期內(nèi)部命令·TIME——顯示和設(shè)置系統(tǒng)時(shí)間·COPY——復(fù)制文件·DEL——?jiǎng)h除文件·REN——文件重命名·TYPE——顯示文本文件內(nèi)容·FORMAT——磁盤格式化·DISKCOPY——全盤復(fù)制外部命令·BACKUP——文件備份·CHKDSK——檢查磁盤……例題在磁盤上建立子目錄有許多優(yōu)點(diǎn),下列描述中不屬于建立子目錄優(yōu)點(diǎn)的是(D)。A)便于文件管理B)解決根目錄中目錄項(xiàng)個(gè)數(shù)有限問題C)加快文件查找速度D)節(jié)省磁盤使用空間資源管理器的目錄前圖標(biāo)中增加"+"號(hào),這個(gè)符號(hào)的意思是(B)。A)該目錄下的子目錄已經(jīng)展開B)該目錄下還有子目錄未展開C)該目錄下沒有子目錄D)該目錄為空目錄在樹型目錄結(jié)構(gòu)中，不允許兩個(gè)文件名相同主要指的是(D)A)同一個(gè)磁盤的不同目錄下B)不同磁盤的同一個(gè)目錄下C)不同磁盤的不同目錄下C)同一個(gè)磁盤的同一個(gè)目錄下以下對(duì)Windows的敘述中，正確的是(A)A)從軟盤上刪除的文件和文件夾，不送到回收站B)在同一個(gè)文件夾中，可以創(chuàng)建兩個(gè)同類、同名的文件C)刪除了某個(gè)應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件D)不能打開兩個(gè)寫字板應(yīng)用程序WINDOWS9X是一種（D）操作系統(tǒng)單任務(wù)字符方式B.單任務(wù)圖形方式C.多任務(wù)字符方式D.多任務(wù)圖形方式在config.sys文件中，裝入特定的可安裝設(shè)備驅(qū)動(dòng)程序的命令是（D）．A．bufferB.filesC．xcopyD．Device下列文件名中，屬于DOS中的保留設(shè)備名的為（A）A.auxB.comC.conlD.prnl啟動(dòng)計(jì)算機(jī)引導(dǎo)DOS是將操作系統(tǒng)（D）A.從磁盤調(diào)入中央處理器B.從內(nèi)存儲(chǔ)器調(diào)入高速緩沖存儲(chǔ)器C.從軟盤調(diào)入硬盤D.從系統(tǒng)盤調(diào)入內(nèi)存儲(chǔ)器DOS暫駐區(qū)中的程序主要是用于(A)A)執(zhí)行DOS內(nèi)部命令B)執(zhí)行DOS外部命令C)執(zhí)行DOS所有命令D)基本輸入輸出下列哪個(gè)軟件屬于操作系統(tǒng)軟件（E）。A.MicrosoftWordB.金山詞霸C.FoxmailD.WinRARE.RedHatLinux下列哪個(gè)不是數(shù)據(jù)庫軟件的名稱（D）。A.MySQLB.SQLServerC.OracleD.金山影霸E.Foxpro以下哪個(gè)軟件不是即時(shí)通信軟件（D）。A.網(wǎng)易泡泡 B.MSNMessenger C.GoogleTalk D.3DSMax E.QQ四、信息安全計(jì)算機(jī)安全(computersecurity)是指防范與保護(hù)計(jì)算機(jī)系統(tǒng)及其信息資源在生存過程中免受蓄意攻擊、人為失誤和自然災(zāi)害等引起的損失和破壞。計(jì)算機(jī)病毒是人類自己想像和發(fā)明出來的，它是一種特殊的程序，有著與生物病毒極為相似的特點(diǎn)。一是寄生性，它們大多依附在別的程序上面。二是隱蔽性，它們是悄然進(jìn)入系統(tǒng)的，人們很難察覺。三是潛伏性，它們通常是潛伏在計(jì)算機(jī)程序中，只在一定條件下才發(fā)作的。四是傳染性，它們能夠自我復(fù)制繁殖，通過傳輸媒介蔓延。五是破壞性，輕則占用一定數(shù)量的系統(tǒng)資源，重則破壞整個(gè)系統(tǒng)。對(duì)于計(jì)算機(jī)病毒，我們不必談虎變色，而應(yīng)采取積極的防治態(tài)度。首先，要防止“病從口入”，因?yàn)椴《静皇亲陨?，而是外來的。另外，要用?yōu)秀的防殺病毒軟件，對(duì)外來的軟件和資料要進(jìn)行嚴(yán)格的檢查和殺毒。注意，防殺病毒軟件需要及時(shí)更新(主要是其中的數(shù)據(jù)文件)，一般每周一次，不更新基本上等于沒有防殺毒功能。20世紀(jì)50、60年代，黑客(hacker)曾是編程高手的代名詞。后來，黑客成為一個(gè)獨(dú)特的群體，他們通過各種渠道交流技藝，不少人以攻擊計(jì)算機(jī)及其網(wǎng)絡(luò)系統(tǒng)為樂趣。黑客們的膽大妄為已經(jīng)給社會(huì)造成了很大的影響，一些黑客已經(jīng)蛻變?yōu)橥{社會(huì)安全的罪犯。要防止“黑客”攻擊，主要方法是加強(qiáng)安全措施，例如設(shè)置防火墻（見圖3.1.1）。防火墻是一種計(jì)算機(jī)設(shè)備，它設(shè)置在內(nèi)部網(wǎng)絡(luò)與外部網(wǎng)絡(luò)之間，起一個(gè)隔離的作用，既可以阻止外部信息非法進(jìn)入內(nèi)部系統(tǒng)，也可以阻止內(nèi)部人員非法訪問外部系統(tǒng)。例題計(jì)算機(jī)病毒傳染的必要條件是(B)。A)在內(nèi)存中運(yùn)行病毒程序B)對(duì)磁盤進(jìn)行讀寫操作C)在內(nèi)存中運(yùn)行含有病毒的程序D)復(fù)制文件計(jì)算機(jī)病毒是(B)A)通過計(jì)算機(jī)傳播的危害人體健康的一種病毒B)人為制造的能夠侵入計(jì)算機(jī)系統(tǒng)并給計(jì)算機(jī)帶來故障的程序或指令集合C)一種由于計(jì)算機(jī)元器件老化而產(chǎn)生的對(duì)生態(tài)環(huán)境有害的物質(zhì)D)利用計(jì)算機(jī)的海量高速運(yùn)算能力而研制出來的用于疾病預(yù)防的新型病毒計(jì)算機(jī)病毒的特點(diǎn)是（C）A.傳播性、潛伏性、易讀性與隱蔽性B.破壞性、傳播性、潛伏性與安全性C.傳播性、潛伏性、破壞性與隱蔽性D.傳播性、潛伏性、破壞性與易讀性一臺(tái)計(jì)算機(jī)如果要利用電話線上網(wǎng)，就必須配置能夠?qū)?shù)字信號(hào)和模擬信號(hào)進(jìn)行相互轉(zhuǎn)換的設(shè)備，這種設(shè)備是（A）。A.調(diào)制解調(diào)器B.路由器C.網(wǎng)卡D.網(wǎng)關(guān)E.網(wǎng)橋五、網(wǎng)絡(luò)1．關(guān)于網(wǎng)絡(luò)的一些定義：所謂計(jì)算機(jī)網(wǎng)絡(luò)，就是利用通信線路和設(shè)備，把分布在不同地理位置上的多臺(tái)計(jì)算機(jī)連接起來。計(jì)算機(jī)網(wǎng)絡(luò)是現(xiàn)代通信技術(shù)與計(jì)算機(jī)技術(shù)相結(jié)合的產(chǎn)物。網(wǎng)絡(luò)中計(jì)算機(jī)與計(jì)算機(jī)之間的通信依靠協(xié)議進(jìn)行。協(xié)議是計(jì)算機(jī)收、發(fā)數(shù)據(jù)的規(guī)則。1、TCP/IP：用于網(wǎng)絡(luò)的一組通訊協(xié)議。包括IP(InternetProtocol)和TCP(TransmissionControlProtocol)。TCP/IP是一組協(xié)議，包括上百個(gè)各種功能的協(xié)議，其中TCP和IP是最核心的兩個(gè)協(xié)議。TCP/IP協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有四個(gè)層次功能的網(wǎng)絡(luò)模型。1.鏈路層：這是TCP/IP結(jié)構(gòu)的第一層，也叫網(wǎng)絡(luò)接口層，其功能是提供網(wǎng)絡(luò)相鄰節(jié)點(diǎn)間的信息傳輸以及網(wǎng)絡(luò)硬件和設(shè)備驅(qū)動(dòng)。2.網(wǎng)絡(luò)層：（IP協(xié)議層）其功能是提供源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能。3.傳輸屋：（TCP協(xié)議）其功能是提供網(wǎng)絡(luò)上的各應(yīng)用程序之間的通信服務(wù)。4.應(yīng)用層：這是TCP/IP最高層，其功能是為用戶提供訪問網(wǎng)絡(luò)環(huán)境的手段，主要提供FTP、TELNET、GOPHER等功能軟件。IP協(xié)議適用于所有類型網(wǎng)絡(luò)。TCP協(xié)議則處理IP協(xié)議所遺留的通信問題，為應(yīng)用程序提供可靠的通信連接，并能自動(dòng)適應(yīng)網(wǎng)絡(luò)的變化。TCP/IP目前成為最為成功的網(wǎng)絡(luò)體系結(jié)構(gòu)和協(xié)議規(guī)范。2、Netbeui：一種非常簡(jiǎn)單的協(xié)議，MICROSOFT開發(fā)。3、IPX：用于NOVELL網(wǎng)絡(luò)。2．網(wǎng)絡(luò)的發(fā)展計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展過程大致可以分為三個(gè)階段：遠(yuǎn)程終端聯(lián)機(jī)階段：主機(jī)—終端計(jì)算機(jī)網(wǎng)絡(luò)階段：計(jì)算機(jī)—計(jì)算機(jī)Internet階段：Internet3．網(wǎng)絡(luò)的主要功能：（1）資源共享（2）信息傳輸（3）分布處理（4）綜合信息服務(wù)4．網(wǎng)絡(luò)的分類計(jì)算機(jī)網(wǎng)絡(luò)的分類方式有很多種,可以按地理范圍、拓?fù)浣Y(jié)構(gòu)、傳輸速率和傳輸介質(zhì)等分類。⑴按地理范圍分類①局域網(wǎng)LAN(LocalAreaNetwork)局域網(wǎng)地理范圍一般幾百米到10km之內(nèi),屬于小范圍內(nèi)的連網(wǎng)。如一個(gè)建筑物內(nèi)、一個(gè)學(xué)校內(nèi)、一個(gè)工廠的廠區(qū)內(nèi)等。局域網(wǎng)的組建簡(jiǎn)單、靈活,使用方便。②城域網(wǎng)MAN(MetropolitanAreaNetwork)城域網(wǎng)地理范圍可從幾十公里到上百公里,可覆蓋一個(gè)城市或地區(qū),是一種中等形式的網(wǎng)絡(luò)。③廣域網(wǎng)WAN(WideAreaNetwork)廣域網(wǎng)地理范圍一般在幾千公里左右,屬于大范圍連網(wǎng)。如幾個(gè)城市,一個(gè)或幾個(gè)國家,是網(wǎng)絡(luò)系統(tǒng)中的最大型的網(wǎng)絡(luò),能實(shí)現(xiàn)大范圍的資源共享,如國際性的Internet網(wǎng)絡(luò)。⑵按傳輸速率分類網(wǎng)絡(luò)的傳輸速率有快有慢,傳輸速率快的稱高速網(wǎng),傳輸速率慢的稱低速網(wǎng)。傳輸速率的單位是b/s(每秒比特?cái)?shù),英文縮寫為bps)。一般將傳輸速率在Kb/s—Mb/s范圍的網(wǎng)絡(luò)稱低速網(wǎng),在Mb/s—Gb/s范圍的網(wǎng)稱高速網(wǎng)。也可以將Kb/s網(wǎng)稱低速網(wǎng),將Mb/s網(wǎng)稱中速網(wǎng),將Gb/s網(wǎng)稱高速網(wǎng)。網(wǎng)絡(luò)的傳輸速率與網(wǎng)絡(luò)的帶寬有直接關(guān)系。帶寬是指?jìng)鬏斝诺赖膶挾?帶寬的單位是Hz(赫茲)。按照傳輸信道的寬度可分為窄帶網(wǎng)和寬帶網(wǎng)。一般將KHz—MHz帶寬的網(wǎng)稱為窄帶網(wǎng),將MHz—GHz的網(wǎng)稱為寬帶網(wǎng),也可以將kHz帶寬的網(wǎng)稱窄帶網(wǎng),將MHz帶寬的網(wǎng)稱中帶網(wǎng),將GHz帶寬的網(wǎng)稱寬帶網(wǎng)。通常情況下,高速網(wǎng)就是寬帶網(wǎng),低速網(wǎng)就是窄帶網(wǎng)。⑶按傳輸介質(zhì)分類傳輸介質(zhì)是指數(shù)據(jù)傳輸系統(tǒng)中發(fā)送裝置和接受裝置間的物理媒體,按其物理形態(tài)可以劃分為有線和無線兩大類。①有線網(wǎng)傳輸介質(zhì)采用有線介質(zhì)連接的網(wǎng)絡(luò)稱為有線網(wǎng),常用的有線傳輸介質(zhì)有雙絞線、同軸電纜和光導(dǎo)纖維。●雙絞線是由兩根絕緣金屬線互相纏繞而成,這樣的一對(duì)線作為一條通信線路,由四對(duì)雙絞線構(gòu)成雙絞線電纜。雙絞線點(diǎn)到點(diǎn)的通信距離一般不能超過100m。目前,計(jì)算機(jī)網(wǎng)絡(luò)上使用的雙絞線按其傳輸速率分為三類線、五類線、六類線、七類線,傳輸速率在10Mbps到600Mbps之間,雙絞線電纜的連接器一般為RJ-45?！裢S電纜由內(nèi)、外兩個(gè)導(dǎo)體組成,內(nèi)導(dǎo)體可以由單股或多股線組成,外導(dǎo)體一般由金屬編織網(wǎng)組成。內(nèi)、外導(dǎo)體之間有絕緣材料,其阻抗為50Ω。同軸電纜分為粗纜和細(xì)纜,粗纜用DB-15連接器,細(xì)纜用BNC和T連接器?！窆饫|由兩層折射率不同的材料組成。內(nèi)層是具有高折射率的玻璃單根纖維體組成,外層包一層折射率較低的材料。光纜的傳輸形式分為單模傳輸和多模傳輸,單模傳輸性能優(yōu)于多模傳輸。所以,光纜分為單模光纜和多模光纜,單模光纜傳送距離為幾十公里,多模光纜為幾公里。光纜的傳輸速率可達(dá)到每秒幾百兆位。光纜用ST或SC連接器。光纜的優(yōu)點(diǎn)是不會(huì)受到電磁的干擾,傳輸?shù)木嚯x也比電纜遠(yuǎn)，傳輸速率高。光纜的安裝和維護(hù)比較困難,需要專用的設(shè)備。②無線網(wǎng)采用無線介質(zhì)連接的網(wǎng)絡(luò)稱為無線網(wǎng)。目前無線網(wǎng)主要采用三種技術(shù)：微波通信,紅外線通信和激光通信。這三種技術(shù)都是以大氣為介質(zhì)的。其中微波通信用途最廣,目前的衛(wèi)星網(wǎng)就是一種特殊形式的微波通信,它利用地球同步衛(wèi)星作中繼站來轉(zhuǎn)發(fā)微波信號(hào),一個(gè)同步衛(wèi)星可以覆蓋地球的三分之一以上表面,三個(gè)同步衛(wèi)星就可以覆蓋地球上全部通信區(qū)域。⑷按拓?fù)浣Y(jié)構(gòu)分類計(jì)算機(jī)網(wǎng)絡(luò)的物理連接形式叫做網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu)。連接在網(wǎng)絡(luò)上的計(jì)算機(jī)、大容量的外存、高速打印機(jī)等設(shè)備均可看作是網(wǎng)絡(luò)上的一個(gè)節(jié)點(diǎn),也稱為工作站。計(jì)算機(jī)網(wǎng)絡(luò)中常用的拓?fù)浣Y(jié)構(gòu)有總線型、星型、環(huán)型等。①總線拓?fù)浣Y(jié)構(gòu)總線拓?fù)浣Y(jié)構(gòu)是一種共享通路的物理結(jié)構(gòu)。這種結(jié)構(gòu)中總線具有信息的雙向傳輸功能，普遍用于局域網(wǎng)的連接,總線一般采用同軸電纜或雙絞線。總線拓?fù)浣Y(jié)構(gòu)的優(yōu)點(diǎn)是：安裝容易,擴(kuò)充或刪除一個(gè)節(jié)點(diǎn)很容易,不需停止網(wǎng)絡(luò)的正常工作,節(jié)點(diǎn)的故障不會(huì)殃及系統(tǒng)。由于各個(gè)節(jié)點(diǎn)共用一個(gè)總線作為數(shù)據(jù)通路,信道的利用率高。但總線結(jié)構(gòu)也有其缺點(diǎn)：由于信道共享,連接的節(jié)點(diǎn)不宜過多，并且總線自身的故障可以導(dǎo)致系統(tǒng)的崩潰。②星型拓?fù)浣Y(jié)構(gòu)星型拓?fù)浣Y(jié)構(gòu)是一種以中央節(jié)點(diǎn)為中心,把若干外圍節(jié)點(diǎn)連接起來的輻射式互聯(lián)結(jié)構(gòu)。這種結(jié)構(gòu)適用于局域網(wǎng),特別是近年來連接的局域網(wǎng)大都采用這種連接方式。這種連接方式以雙絞線或同軸電纜作連接線路。星型拓?fù)浣Y(jié)構(gòu)的特點(diǎn)是：安裝容易,結(jié)構(gòu)簡(jiǎn)單,費(fèi)用低,通常以集線器(Hub)作為中央節(jié)點(diǎn),便于維護(hù)和管理。中央節(jié)點(diǎn)的正常運(yùn)行對(duì)網(wǎng)絡(luò)系統(tǒng)來說是至關(guān)重要的。③環(huán)型拓?fù)浣Y(jié)構(gòu)環(huán)型拓?fù)浣Y(jié)構(gòu)是將網(wǎng)絡(luò)節(jié)點(diǎn)連接成閉合結(jié)構(gòu)。信號(hào)順著一個(gè)方向從一臺(tái)設(shè)備傳到另一臺(tái)設(shè)備,每一臺(tái)設(shè)備都配有一個(gè)收發(fā)器,信息在每臺(tái)設(shè)備上的延時(shí)時(shí)間是固定的。這種結(jié)構(gòu)特別適用于實(shí)時(shí)控制的局域網(wǎng)系統(tǒng)。環(huán)型拓?fù)浣Y(jié)構(gòu)的特點(diǎn)是：安裝容易,費(fèi)用較低,電纜故障容易查找和排除。有些網(wǎng)絡(luò)系統(tǒng)為了提高通信效率和可靠性,采用了雙環(huán)結(jié)構(gòu),即在原有的單環(huán)上再套一個(gè)環(huán),使每個(gè)節(jié)點(diǎn)都具有兩個(gè)接收通道。環(huán)型網(wǎng)絡(luò)的弱點(diǎn)是,當(dāng)節(jié)點(diǎn)發(fā)生故障時(shí),整個(gè)網(wǎng)絡(luò)就不能正常工作。5．網(wǎng)絡(luò)的體系結(jié)構(gòu)OSI的七層體系結(jié)構(gòu)：應(yīng)用層表示層會(huì)話層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層6．局域網(wǎng)的工作方式通常有兩種：?客戶機(jī)/服務(wù)器(Client/Server):提供資源并管理資源的計(jì)算機(jī)稱為服務(wù)器；使用共享資源的計(jì)算機(jī)稱客戶機(jī)；?對(duì)等(Peer-to-Peer):不使用服務(wù)器來管理網(wǎng)絡(luò)共享資源，所以的計(jì)算機(jī)處于平等的地位。7．Internet的形成與發(fā)展又稱國際互聯(lián)網(wǎng)，規(guī)范的譯名是“因特網(wǎng)”，指當(dāng)前各國、各地區(qū)眾多開發(fā)的網(wǎng)絡(luò)連接在一起而形成的全球性網(wǎng)絡(luò)?！の覈鳬nternet的發(fā)展情況：八十年代末，九十年代初才起步。1989年我國第一個(gè)公用分組交換網(wǎng)CNPAC建成運(yùn)行?！の覈殃懤m(xù)建成與Internet互聯(lián)的四個(gè)全國范圍的公用網(wǎng)絡(luò)：中國公用計(jì)算機(jī)互聯(lián)網(wǎng)（CHINANET）、中國金橋信息網(wǎng)（CHINAGBN）中國教育和科研計(jì)算機(jī)網(wǎng)（CERNET）、中國科學(xué)技術(shù)網(wǎng)（CSTNET）8．IP地址：我們把整個(gè)Internet看作一個(gè)單一的、抽象的網(wǎng)絡(luò)，所謂IP地址，就是為Internet中的每一臺(tái)主機(jī)分配一個(gè)在全球范圍唯一地址。IPv4地址是由32位二進(jìn)數(shù)碼表示的，為方便記記憶，把這32位二進(jìn)制數(shù)每8個(gè)一段用“.”隔開，再把每一段的二進(jìn)制數(shù)化成十進(jìn)制數(shù)，也就得到我們現(xiàn)在所看到的IP地址形式。IP地址是用“.”隔開地四個(gè)十進(jìn)制整數(shù)，每個(gè)數(shù)字取值為0—255。IP地址分A、B、C、D；E五類，目前大量使用的是A、B、C三類，D類為Internet體系結(jié)構(gòu)委員會(huì)IAB專用，E類保留在今后使用。最高位1..126為A類，128..191是B類，192..223是C類。9．域名：域名地址采用層次結(jié)構(gòu)，一個(gè)域名一般有3－5個(gè)子段，中間用“.”隔開。IP地址作為Internet上主機(jī)的數(shù)字標(biāo)識(shí)，對(duì)計(jì)算機(jī)網(wǎng)絡(luò)來說是非常有效的。但對(duì)于使用者來說，很難記憶這些由數(shù)字組成的IP地址了。為此，人們研究出一種字符型標(biāo)識(shí)，在Internet上采用“名稱”尋址方案，為每臺(tái)計(jì)算機(jī)主機(jī)都分配一個(gè)獨(dú)有的“標(biāo)準(zhǔn)名稱”，這個(gè)用字符表示的“標(biāo)準(zhǔn)名稱”就是我們現(xiàn)在所廣泛使用的域名（DN，domainname）。因此主機(jī)的域名和IP地址一樣，也采用分段表示的方法。其結(jié)構(gòu)一般是如下樣式：計(jì)算機(jī)名.組織結(jié)構(gòu)名.網(wǎng)絡(luò)名.最高層域名。頂級(jí)域名有三類：?國家頂級(jí)域名,如cn（中國）、us（美國）、uk（英國）；?國際頂級(jí)域名——int，國際性組織可在int下注冊(cè)；?通用頂級(jí)域名，如：com、net、edu、gov、org、……有了域名標(biāo)識(shí)，對(duì)于計(jì)算機(jī)用戶來說，在使用上的確方便了很多。但計(jì)算機(jī)本身并不能自動(dòng)識(shí)別這些域名標(biāo)識(shí)，于是域名管理服務(wù)器DNS（domainnamesystem）就應(yīng)運(yùn)而生了。所謂的域名管理系統(tǒng)DNS（domainnamesystem）就是以主機(jī)的域名來代替其在Internet上實(shí)際的IP地址的系統(tǒng)，它負(fù)責(zé)將Internet上主機(jī)的域名轉(zhuǎn)化為計(jì)算機(jī)能識(shí)別的IP地址。從DNS的組織結(jié)構(gòu)來看，它是一個(gè)按照層次組織的分布式服務(wù)系統(tǒng)；從它的運(yùn)行機(jī)制來看，DNS更像一個(gè)龐大的數(shù)據(jù)庫，只不過這個(gè)數(shù)據(jù)庫并不存儲(chǔ)在任一計(jì)算機(jī)上，而是分散在遍布于整個(gè)Internet上數(shù)以千計(jì)的域名服務(wù)器中而已。通過上面的IP地址、域名DN和域名管理系統(tǒng)DNS，就把Internet上面的每一臺(tái)主機(jī)給予了唯一的定位。三者之間的具體聯(lián)系過程如下：當(dāng)連接網(wǎng)絡(luò)并輸入想訪問主機(jī)的域名后，由本地機(jī)向域名服務(wù)器發(fā)出查詢指令，域名服務(wù)器通過連接在整個(gè)域名管理系統(tǒng)查詢對(duì)應(yīng)的IP地址，如找到則返回相應(yīng)的IP地址，反之則返回錯(cuò)誤信息。說到這里，想必大家都明白了為什么當(dāng)我們?cè)跒g覽時(shí)，瀏覽器左下角的狀態(tài)條上會(huì)有這樣的信息：“正在查找xxxxxx”、“xxxxxx已經(jīng)發(fā)現(xiàn)，正在連接xxxxxx”，其實(shí)這也就是域名通過DNS轉(zhuǎn)化為IP地址的過程。當(dāng)然域名通過DNS轉(zhuǎn)化為IP地址需要等待一段時(shí)間，因?yàn)槿绻闼褂玫挠蛎?wù)器上如果沒有你所需要域名的對(duì)應(yīng)IP地址，它就會(huì)向上級(jí)域名服務(wù)器查詢，如此類推，直至查到結(jié)果，或返回?zé)o效信息。一般而言，這個(gè)查詢過程都非常短，你很難察覺到。10．Internet（譯為因特網(wǎng)或國際互聯(lián)網(wǎng)）的服務(wù)與工具Internet的服務(wù)有：電子郵件、遠(yuǎn)程登陸、文件傳輸、信息服務(wù)等；·電子郵件（E-Mail）：電子郵件地址格式為：收信人郵箱名@郵箱所在主機(jī)的域名。例：winner01@21，qfit168@·遠(yuǎn)程登陸（Telnet）：指通過Internet與其它主機(jī)連接。登陸上另一主機(jī)，你就可以使用該主機(jī)對(duì)外開放的各種資源，如聯(lián)機(jī)檢索、數(shù)據(jù)查詢?！の募鬏敚‵TP）：用于在計(jì)算機(jī)間傳輸文件。如下載軟件等。11．全球信息網(wǎng)（WWW－WorldWideWeb）：又稱萬維網(wǎng)，是一個(gè)全球規(guī)模的信息服務(wù)系統(tǒng)，由遍布于全世界的數(shù)以萬計(jì)的Web站點(diǎn)組成。例題在使用E-mail前，需要對(duì)OUTLOOK進(jìn)行設(shè)置，其中接收電子郵件的服務(wù)器稱為(A)服務(wù)器。A)POP3B)SMTPC)DNSD)FTPIpv4地址是由(B)位二進(jìn)制數(shù)碼表示的。A)16B)32C)24fD)8Email郵件本質(zhì)上是一個(gè)(A)A)文件B)電報(bào)C)電話D)傳真TCP/IP協(xié)議共有(B)層協(xié)議A)3B)4C)5D)6Internet的規(guī)范譯名應(yīng)為（B）A.英特爾網(wǎng)B.因特網(wǎng)C.萬維網(wǎng)D.以太網(wǎng)計(jì)算機(jī)網(wǎng)絡(luò)是一個(gè)（D）A.管理信息系統(tǒng)B.管理數(shù)據(jù)系統(tǒng)C.編譯系統(tǒng)D.在協(xié)議控制下的多機(jī)互連系統(tǒng)下面哪些計(jì)算機(jī)網(wǎng)絡(luò)不是按覆蓋地域劃分的（D）A.局域網(wǎng)B.都市網(wǎng)C.廣域網(wǎng)D.星型網(wǎng)下列網(wǎng)絡(luò)上常用的名字縮寫對(duì)應(yīng)的中文解釋錯(cuò)誤的是（D）。WWW（WorldWideWeb）：萬維網(wǎng)。URL（UniformResourceLocator）：統(tǒng)一資源定位器。HTTP（HypertextTransferProtocol）：超文本傳輸協(xié)議。FTP（FileTransferProtocol）：快速傳輸協(xié)議。TCP（TransferControlProtocol）：傳輸控制協(xié)議。常見的郵件傳輸服務(wù)器使用（B）協(xié)議發(fā)送郵件。A.HTTP B.SMTP C.TCP D.FTP E.POP3不能在Linux上使用的網(wǎng)頁瀏覽器是（A）。A.InternetExplore B.Netscape C.Opera D.Firefox E.Mozilla六、數(shù)據(jù)結(jié)構(gòu)與算法第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)簡(jiǎn)單的解釋：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)間的聯(lián)系有邏輯關(guān)系、存儲(chǔ)聯(lián)系，通常的數(shù)據(jù)結(jié)構(gòu)指的是邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)通常有如下四種關(guān)系：（1）集合結(jié)構(gòu)（2）線性結(jié)構(gòu)（3）樹形結(jié)構(gòu)（4）圖狀結(jié)構(gòu)線性結(jié)構(gòu)一、線性表（一）――N個(gè)數(shù)據(jù)元素的有限序列（1）（2）（3）（4）（5）（6）（7）（8）121315223438432020當(dāng)在這種線性表中插入一個(gè)數(shù)據(jù)元素時(shí)，需要順序移動(dòng)后續(xù)的元素以“騰”出某個(gè)合適的位置放置新元素。刪除元素呢？二、線性表（二）――鏈表插入新元素的時(shí)候只需要改變指針?biāo)赶虻牡刂??！疃S數(shù)組與線性表如果某一線性表，它的每一個(gè)數(shù)據(jù)元素分別是一個(gè)線性表，這樣的二維表在數(shù)據(jù)實(shí)現(xiàn)上通常使用二維數(shù)組。二維數(shù)組的一個(gè)形象比喻——m*n的隊(duì)列方塊☆數(shù)組地址計(jì)算問題題目描述：已知N*(N+1)/2個(gè)數(shù)據(jù)，按行的順序存入數(shù)組b[1],b[2],…中。第一個(gè)下標(biāo)表示行，第二個(gè)下標(biāo)表示列。若aij(i>=j,j=1,2,…,,n)存于b[k]中，問：k,i,j之間的關(guān)系如何表示？棧及其應(yīng)用一.棧的定義：

堆棧（stack）是一種“特殊的”線性表，對(duì)于它所有的插入和刪除都限制在表的同一端進(jìn)行，這一端叫做棧的“頂”（top），另一端則叫做棧的“底”（bottom）。當(dāng)表中沒有元素時(shí)稱為空棧。棧為后進(jìn)先出（lastinfirstout）的線性表，簡(jiǎn)稱LIFO表。棧的修改時(shí)后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中“最新”的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要最后才能刪除。圖中元素是以a1，a2，…an的順序進(jìn)棧，退棧的次序卻是an，an-1，…，a1。二.棧的基本操作

（1）InitStack（S）：初始化操作，設(shè)定一個(gè)空棧S。（2）EmptyStack（S）：判空棧操作，若S為空棧，則返回True，否則返回False。（3）FullStack（S）：判滿棧。若S為滿棧，則返回True，否則返回False。注意：該運(yùn)算只適用于棧的順序存儲(chǔ)結(jié)構(gòu)。（4）push(s,x)：進(jìn)棧。若棧S不滿，在棧頂推入一個(gè)元素x，棧頂位置由top指針指出。（5）pop(s)：出棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）GetTop(s)：取棧頂元素。若棧s非空，則返回s的棧頂元素，但不改變棧的狀態(tài)。（7）clearstack（s）：置?？詹僮?，已知s為棧，不論操作之前的棧是否為空棧，本操作的結(jié)果都是將s置為空棧。（8）currentstack（s）：求當(dāng)前棧中元素的個(gè)數(shù)。（9）destroystack（s）：銷毀s棧(10)top(s,x)：讀棧頂元素。把棧頂元素的值讀到變量x中，棧保持不變。三、表達(dá)式的計(jì)算表達(dá)式的二種形式

1、中綴表達(dá)式：運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象中間，如：(2+1)*3；

2、后綴表達(dá)式（逆波蘭表示法）：運(yùn)算符緊跟在兩個(gè)操作數(shù)之后，實(shí)現(xiàn)無括號(hào)和無優(yōu)先處理，只須從左到右完成計(jì)算。如：表達(dá)式(2+1)*3表示為后綴表達(dá)式為21+3*；練習(xí)：1、編號(hào)分別為1~4的4輛列車進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)?？墒沟瞄_出車站列車的次序?yàn)?431，如何進(jìn)行進(jìn)出操作2、將8-(3+2*6)/5+4表示為后綴表達(dá)式四、隊(duì)列1.隊(duì)列的特點(diǎn)：

隊(duì)列也是一種線性表，對(duì)于它所有的插入都在隊(duì)列的一端進(jìn)行，所有的刪除都在另一端進(jìn)行，進(jìn)行刪除的一端叫隊(duì)列的“頭”(front)，進(jìn)行插入的一端叫隊(duì)列的“尾”(rear)，其操作特點(diǎn)是“先進(jìn)先出”。(FIFO,FirstInFirstOut)2.隊(duì)列的基本操作：

(1)隊(duì)列的插入enq(q,x)：在隊(duì)列q中插入一個(gè)值為x的元素，也稱為進(jìn)隊(duì)；

(2)隊(duì)列的刪除deq(q)：從隊(duì)列q中刪除一個(gè)元素，也稱為出隊(duì)；

(3)讀隊(duì)頭元素front(q,x)：將隊(duì)列q中頭部元素的值讀到x中；

3、循環(huán)隊(duì)列頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，尾指針指示隊(duì)尾元素在隊(duì)列中的當(dāng)前位置。樹及其應(yīng)用一、樹的定義樹是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合。如果n=0，稱為空樹；如果n>0，則（1）有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；（2）除根以外的其它結(jié)點(diǎn)劃分為m(m>=0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。結(jié)點(diǎn)(node):各元素及其子樹的分支結(jié)點(diǎn)的度(degree)：子樹的數(shù)目分支(branch)結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)：度為0的結(jié)點(diǎn)子女(child)、雙親(parent)結(jié)點(diǎn)：如B、C、D為A的子女，A是B、C、D的雙親兄弟(sibling)、祖先(ancestor)、子孫(descendant)結(jié)點(diǎn)：EF為兄弟，L的祖先是EBA，結(jié)點(diǎn)所處層次(level)樹的高度(depth)：樹的最大層次數(shù)樹的度(degree)：各結(jié)點(diǎn)度的最大值二、二叉樹(BinaryTree)一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。二叉樹的五種不同形態(tài)二叉樹的性質(zhì)性質(zhì)1若二叉樹的層次從0開始,則在二叉樹的第i層最多有2i個(gè)結(jié)點(diǎn)。(i>=0)性質(zhì)2高度為k的二叉樹最多有2k+1-1個(gè)結(jié)點(diǎn)。(k＞＝1)性質(zhì)3對(duì)任何一棵二叉樹,如果其葉結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0＝n2＋1兩種特殊的二叉樹：滿二叉樹(FullBinaryTree)完全二叉樹(CompleteBinaryTree)三、二叉樹的抽象數(shù)據(jù)表示1．?dāng)?shù)組表示鏈表表示四、二叉樹遍歷(BinaryTreeTraversal)所謂樹的遍歷，就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。其目標(biāo)是通過完整而有規(guī)則的遍歷方法，使得對(duì)非線性的二叉樹結(jié)構(gòu)能獲得其中各結(jié)點(diǎn)信息的一個(gè)線性排列?，F(xiàn)設(shè)訪問根結(jié)點(diǎn)記作V、訪問根的左子樹記作L、訪問根的右子樹記作R則可能的遍歷次序有6種：前序:VLR/VRL中序:LVR/RVL后序:LRV/RLV1、中根遍歷(InorderTraversal)中根遍歷二叉樹的方法是：左－根－右右圖所示樹的中根遍歷結(jié)果：a+b*c-d-e/f2、前序遍歷(PreorderTraversal)前根遍歷二叉樹的方法是：根－左－右遍歷結(jié)果：－+a*b-cd/ef3、后根遍歷(PostorderTraversal)后根遍歷二叉樹的方法是：左－右－根如右圖所示樹的遍歷結(jié)果：abcd-*+ef/-習(xí)題一棵二叉樹的中根遍歷為DBGEACHFI后根遍歷為DGEBHIFCA，畫出此二叉樹。已知某二叉樹的前根遍歷為ABDEGCFHIJ，中根遍歷為DBGEAHFIJC，試給出它的后根遍歷。按中根遍歷二叉樹所得的結(jié)點(diǎn)序列為ABC，試給出所有可能的二叉樹。對(duì)于表達(dá)式（a+b）*(c+d)*(e-f)，要求（1）給出它的中根二叉樹；（2）給出它的前綴表達(dá)式；（3）給出它的后綴表達(dá)式。圖的問題一、圖的定義：圖（graph）由一些點(diǎn)和連線所組成，即圖是點(diǎn)和邊集合。二、圖的有關(guān)術(shù)語１、結(jié)點(diǎn)和連線：圖中的點(diǎn)稱為結(jié)點(diǎn)，結(jié)點(diǎn)之間連線稱為邊。

２、相鄰：若兩結(jié)點(diǎn)之間有邊，則稱兩結(jié)點(diǎn)相鄰。３、有向圖（digraph）和無向圖（undigraph）：結(jié)點(diǎn)之間的邊無方向稱無向圖；反之稱有向圖。（如圖1）４、帶權(quán)圖：結(jié)點(diǎn)之間的邊有數(shù)量關(guān)系（如兩地的距離）稱權(quán)５、結(jié)點(diǎn)的度數(shù)：某結(jié)點(diǎn)的邊的條數(shù)稱為該結(jié)點(diǎn)的度數(shù)。６、路：某結(jié)點(diǎn)到另外某個(gè)結(jié)點(diǎn)所經(jīng)過的邊和點(diǎn)的序列。圖1三、圖的抽象表示圖11、用兩維數(shù)組（鄰接矩陣）來表示；對(duì)有向圖要N＊N個(gè)單元來存儲(chǔ)矩陣，對(duì)無向圖，其鄰接矩陣是對(duì)稱的，只須存儲(chǔ)上三角或下三角部分即可。（如圖2）2、鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。具體表示時(shí)，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用來存儲(chǔ)與該頂點(diǎn)鄰接的頂點(diǎn)。各單鏈表的表頭結(jié)點(diǎn)一般采用順序結(jié)構(gòu)的形式存儲(chǔ)，以便可以隨意訪問各頂點(diǎn)的鏈表。四、圖的遍歷圖21、深度優(yōu)先搜索:類似樹的前根遍歷，是樹的前根遍歷的推廣。圖2假設(shè)初始狀態(tài)時(shí)所有結(jié)點(diǎn)都未曾訪問，深度優(yōu)先搜索方法如下：（1）從圖中某個(gè)結(jié)點(diǎn)V0出發(fā)，訪問V0（2）依次從V0的鄰接點(diǎn)中未被訪問的頂點(diǎn)深度優(yōu)先訪問，直至遍歷中圖所有與V0有路徑相連的結(jié)點(diǎn)。（3）若圖中還有結(jié)點(diǎn)未被訪問，則從另一未訪問的結(jié)點(diǎn)開始，重復(fù)類似（2）的訪問過程。如圖3所示，深度優(yōu)先遍歷的結(jié)點(diǎn)順序是V1－V2－V4－V8－V5－V3－V6－V72、廣度優(yōu)先搜索廣度優(yōu)先搜索類似樹的按層次遍歷的過程。它是先訪問所有與V0（當(dāng)前訪問過的結(jié)點(diǎn)）相鄰的未被訪問過的結(jié)點(diǎn)。然后又從這些結(jié)點(diǎn)出發(fā)按廣度優(yōu)先搜索。顯然，這也是遞歸的。圖3的頂點(diǎn)訪問序列為：V1－V2－V3－V4－V5－V6－V7－V8。例題一個(gè)高度為h的二叉樹最小元素?cái)?shù)目是（

B

）。A）2h+1

B）h

C）2h-1

D）2h

E）2h-1一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度是2,則第5個(gè)元素的地址是(B)。A)110B)108C)100D)109按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有(C)種。A)3B)4C)5D)6設(shè)有一個(gè)含有13個(gè)元素的Hash表(0~12),Hash函數(shù)是:H(key)=key%13,其中%是求余數(shù)運(yùn)算。用線性探查法解決沖突,則對(duì)于序列(2、８、31、20、19、18、53、27),18應(yīng)放在第幾號(hào)格中(B)。A)5B)9C)4D)0在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的(B)倍。A)1/2B)1C)2D)4要使1...8號(hào)格子的訪問順序?yàn)?8、2、6、5、7、3、1、4,則下圖中的空格中應(yīng)填入(C)。12345678461-1732A)6B)OC)5D)3設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)閑2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該為(B)。A)2B)3C)4D)5設(shè)有一棵k叉樹,其中只有度為0和k兩種結(jié)點(diǎn),設(shè)n0,nk分別表示度為0和度為k的結(jié)點(diǎn)個(gè)數(shù),試求出n0,nk之間的關(guān)系(n0=數(shù)學(xué)表達(dá)式,數(shù)學(xué)表達(dá)式僅含nk,k和數(shù)字)N0=(K－1)Nk+1若已知一個(gè)棧的入棧順序是1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn，若P1是n，則Pi是(C)A)iB)n-1C)n-i+1D)不確定以下哪一個(gè)不是棧的基本運(yùn)算(B)A)刪除棧頂元素B)刪除棧底的元素C)判斷棧是否為空D)將棧置為空棧下面關(guān)于算法的錯(cuò)誤說法是(B)A)算法必須有輸出B)算法必須在計(jì)算機(jī)上用某種語言實(shí)現(xiàn)C)算法不一定有輸入D)算法必須在有限步執(zhí)行后能結(jié)束在順序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為(C)A)2B)3C)4D)5一棵二叉樹的高度為h，所有結(jié)點(diǎn)的度為0，或?yàn)?，則此樹最少有(B)個(gè)結(jié)點(diǎn)A)2h-1B)2h-1C)2h+1D)h+1無向圖G=(V，E)，其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是(D)A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,e,d,f,c已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序?yàn)椋篈BCEGDFHIJ在有N個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為（B）A.不確定B.2N-1C.2N+1D.2N某數(shù)列有1000個(gè)各不相同的單元，由低至高按序排列；現(xiàn)要對(duì)該數(shù)列進(jìn)行二分法檢索（binary-search），在最壞的情況下，需檢視（B）個(gè)單元。A.1000B.10C.100D.500線性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址（D）A.必須連續(xù)B.部分地址必須連續(xù)C.一定不連續(xù)D.連續(xù)不連續(xù)均可下列敘述中，正確的是（D）A.線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)B.隊(duì)列的操作方式是先進(jìn)后出C.棧的操作方式是先進(jìn)先出D.二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。5種設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走1級(jí)，也可走2級(jí)，也可走3級(jí)，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即1+1+1，1+2，2+1，3。F(n)=f(n-1)+f(n-2)+f(n-3),n>=4;F(1)=1;f(2)=2;f(3)=4;在磁盤的目錄結(jié)構(gòu)中，我們將與某個(gè)子目錄有關(guān)聯(lián)的目錄數(shù)稱為度．例如下圖：該圖表達(dá)了A盤的目錄結(jié)構(gòu)：DI，Dll，……D2均表示子目錄的名字.在這里，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D12，D2，D111，D112，D113的度均為1。又不考慮子目錄的名字，則可簡(jiǎn)單的圖示為如下的樹結(jié)構(gòu)：若知道一個(gè)磁盤的目錄結(jié)構(gòu)中，度為2的子目錄有2個(gè)，度為3的子目錄有1個(gè)，度為4的子目錄有3個(gè)。試問：度為1的子目錄有幾個(gè)？2*2+3*1+4*3+1*x=(2+1+3+x-1)*2根據(jù)Nocomachns定理，任何一個(gè)正整數(shù)n的立方一定可以表示成n個(gè)連續(xù)的奇數(shù)的和。例如：13＝123＝3+533＝7+9+1143＝13+15+17+19在這里，若將每一個(gè)式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請(qǐng)寫出X與n之間的關(guān)系表達(dá)式：n^2-n+1設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（D）A.r-fB.r-f+1C.(r-f)MODn+1D.(r-f+n)MODn有2×n的一個(gè)長(zhǎng)方形方格，用一個(gè)1×2的骨牌鋪滿方格。例如n=3時(shí)，為2×3方格。此時(shí)用一個(gè)1×2的骨牌鋪滿方格，共有3種鋪法：試對(duì)給出的任意一個(gè)n(n)0)，求出鋪法總數(shù)的遞推公式。F(1)=1F(2)=2F(n)=F(n-1)+F(n-2),n>=3FUNCTIONACK(M，N：INTEGER)：INTEGER；BEGINIFM=0THENACK：=N+1ELSEIFN=0THENACK:=ACK(M-1，1)ELSEACK:=ACK(M-1，ACK(M，N-1))END；BEGINWRITELN(ACK(3，4))；READLN；END.輸出125表達(dá)式(1+34)*5-56/7的后綴表達(dá)式為（

C

）。

A）1+34*5-56/7

B）-*+1345/567

C）134+5*567/-

D）1345*+567/-

E）134+5567-*/已知元素（8，25，14，87，51，90，6，19，20），問這些元素以怎樣的順序進(jìn)入棧，才能使出棧的順序滿足：8在51前面；90在87的后面；20在14的后面；25在6的前面