2023年全國三級數(shù)據(jù)庫筆試部分

第一章計算機基礎知識1、計算機的發(fā)展階段：經(jīng)歷了以下5個階段(它們是并行關系)：大型機階段(經(jīng)歷四小階段它們是取代關系)、小型機階段、微型機階段、客戶機/服務器階段（對等網(wǎng)絡與非對等網(wǎng)絡的概念）和互聯(lián)網(wǎng)階段（Arpanet是在1983年第一個使用TCP/IP協(xié)議的。在1991年6月我國第一條與國際互聯(lián)網(wǎng)連接的專線建成它從中國科學院高能物理研究所接到美國斯坦福大學的直線加速器中心。在1994年實現(xiàn)4大主干網(wǎng)互連(中國公用計算機互聯(lián)網(wǎng)Chinanet、中國科學技術網(wǎng)Cstnet、中國教育和科研計算機網(wǎng)Cernet、中國金橋信息網(wǎng)ChinaGBN)）2、計算機種類：按照傳統(tǒng)的分類方法：計算機可以分為6大類：大型主機、小型計算機、個人計算機、工作站、巨型計算機、小巨型機。按照現(xiàn)實的分類方法：計算機可以分為5大類：服務器、工作站、臺式機、筆記本、手持設備。3、計算機的公共配置：CPU、內(nèi)存（RAM）、高速緩存（Cache）、硬盤、光驅(qū)、顯示器(CRT、LCD)、操作系統(tǒng)(OS)4、計算機的指標：位數(shù)指CPU寄存器中可以保存數(shù)據(jù)的位數(shù)、速度(MIPS、MFLOPS)指CPU每秒鐘解決的指令數(shù)通常用主頻來表達CPU的解決速度、容量（B、KB、MB、GB、TB）、數(shù)據(jù)傳輸率（Bps）、版本和可靠性（MTBF、MTTR）。5、計算機的應用領域：科學計算、事務解決、過程控制、輔助工程、人工智能、網(wǎng)絡應用。（補充實例）6、計算機系統(tǒng)的組成:硬件系統(tǒng)具有原子特性(芯片、板卡、設備、網(wǎng)絡)與軟件系統(tǒng)具有比特特性。且它們具有同步性。7、奔騰芯片的技術特點:奔騰32位芯片，重要用于臺式機和筆記本，奔騰采用了RISC和CISC技術(技術特點10個請看書P8)8、安騰芯片的技術特點：安騰是64位芯片，重要用于服務器和工作站。安騰采用簡明并行指令計算（EPIC）技術9、主機板與插卡的組成：(1)主機板簡稱主板(mainboard)或母板(motherboard)。由5部分組成（CPU、存儲器、總線、插槽和電源）與主板的分類(2)網(wǎng)絡卡又稱為適配器卡代號NIC，其功能為：（見書P11）10、軟件的基本概念：軟件由程序(功能實現(xiàn)部分)與文檔(功能說明部分)組成。軟件是用戶與計算機硬件系統(tǒng)之間的橋梁。11、應用軟件涉及：桌面應用軟件、演示出版軟件、瀏覽工具軟件、管理效率軟件、通信協(xié)作軟件和系統(tǒng)維護軟件。12、程序與文檔：程序是由指令序列組成的，告訴計算計如何完畢一個具體的任務。文檔是軟件開發(fā)、使用和維護中的必備資料。13、軟件開發(fā)：軟件的生命周期中，通常分為三大階段，每個階段又分若干子階段：⑴計劃階段：分為問題定義、可行性研究（是決定軟件項目是否開發(fā)的關鍵）。⑵開發(fā)階段：在開發(fā)前期分為需求分析、總體設計、具體設計三個子階段，在開發(fā)后期分為編碼、測試兩個子階段。前期必須形成的文檔有：軟件需求說明書，軟件設計規(guī)格說明書。⑶運營階段：重要任務是軟件維護。為了排除軟件系統(tǒng)中仍然也許隱含的錯誤，擴充軟件功能。14、編程語言：（機器語言與匯編語言都依賴于具體的機器，匯編語言與高級語言都需要編譯）⑴機器語言：能被計算機直接理解和執(zhí)行，速度快，但該種語言難記、難學、難懂。⑵匯編語言：用英文助記符和十進制數(shù)代替二進制碼，使機器語言變成了匯編語言。匯編語言屬于低檔語言。匯編語言要通過匯編程序把匯編語言翻譯成機器語言程序計算機才干執(zhí)行。⑶高級語言：高級語言是一種面向問題或過程的語言。它是近似于平常會話的語言。它不僅直觀、易學，并且通用性強。高級語言要通過編譯（或解釋）翻譯成機器語言才干執(zhí)行。15、媒體的概念與分類:(1)媒體的概念:信息的載體(2)媒體的分類：傳輸媒體、表現(xiàn)媒體、表達媒體、感覺媒體16、多媒體的基本概念：指有聲有色的信息解決與運用技術。多媒體技術可劃分為偏硬件技術和偏軟件技術兩部分。17、MPC的組成：具有CD-ROM、具有A/D和D/A轉(zhuǎn)換功能、具有高清楚的彩色顯示器、具有數(shù)據(jù)壓縮與解壓縮的硬件支持18、多媒體的關鍵技術：數(shù)據(jù)壓縮與解壓縮技術、芯片與插卡技術、多媒體操作系統(tǒng)技術、多媒體數(shù)據(jù)管理技術。19、超文本與超媒體的概念：(1)超文本是非線性非順序的而傳統(tǒng)文本是線性的順序的。(2)超文本概念：超文本是收集、存儲和瀏覽離散信息以及建立和表現(xiàn)信息之間關系的技術。(3)超媒體的組成：當信息載體不限于文本時，稱之為超媒體。超媒體技術是一種典型的數(shù)據(jù)管理技術，它是由稱之為結(jié)點(node)和表達結(jié)點之間聯(lián)系的鏈(link)組成的有向圖（網(wǎng)絡），用戶可以對其進行瀏覽、查詢和修改等操作。(4)超媒體系統(tǒng)的組成：編輯器、導航工具、超媒體語言第二章網(wǎng)絡的基本概念1、信息技術涉及內(nèi)容：信息的收集、儲存、解決、傳輸與運用。2、計算機網(wǎng)絡形成與發(fā)展大體分為如下4個階段：（1）第一個階段20世紀50年代（2）第二個階段以20世紀60年代美國的APPANET與分組互換技術為重要標志。（3）第三個階段從20世紀70年代中期開始。（4）第四個階段是20世紀90年代開始。3、計算機網(wǎng)絡的基本特性：資源共享。4、計算機網(wǎng)絡的定義：把分布在不同地理位置上的自治計算機通過通信設備和通信協(xié)議進行互聯(lián)實現(xiàn)共享資源信息傳輸。5、初期計算機網(wǎng)絡結(jié)構(gòu)實質(zhì)上是廣域網(wǎng)的結(jié)構(gòu)。廣域網(wǎng)的功能：數(shù)據(jù)解決與數(shù)據(jù)通信。邏輯功能上可分為：資源子網(wǎng)與通信子網(wǎng)。資源子網(wǎng)負責全網(wǎng)的數(shù)據(jù)解決，向網(wǎng)絡用戶提供各種網(wǎng)絡資源與網(wǎng)絡服務。重要涉及主機和終端。主機通過高速通信線路與通信子網(wǎng)的通信控制解決機相連接。終端是用戶訪問網(wǎng)絡的界面。通信子網(wǎng)由通信控制解決機、通信線路與其他通信設備組成，完畢網(wǎng)絡數(shù)據(jù)傳輸、轉(zhuǎn)發(fā)等通信解決任務。通信控制解決機在網(wǎng)絡拓撲結(jié)構(gòu)中被稱為網(wǎng)絡節(jié)點。通信線路為通信解決機之間以及通信解決機與主機之間提供通信信道。6、現(xiàn)代網(wǎng)絡機構(gòu)的特點：微機通過局域網(wǎng)連入廣域網(wǎng)，局域網(wǎng)與廣域網(wǎng)、廣域網(wǎng)與廣域網(wǎng)的互聯(lián)是通過路由器實現(xiàn)的。7、按傳輸技術分為：廣播式網(wǎng)絡（通過一條公共信道實現(xiàn)）點--點式網(wǎng)絡（通過存儲轉(zhuǎn)發(fā)實現(xiàn)）。采用分組存儲轉(zhuǎn)發(fā)與路由選擇是點-點式網(wǎng)絡與廣播網(wǎng)絡的重要區(qū)別之一。8、按規(guī)模分類：局域網(wǎng)（LAN）、城域網(wǎng)（MAN）、廣域網(wǎng)（WAN）（1）廣域網(wǎng)的通信子網(wǎng)采用分組互換技術，運用公用分組互換網(wǎng)、衛(wèi)星通信網(wǎng)和無線分組互換網(wǎng)互聯(lián)。（2）廣域網(wǎng)（遠程網(wǎng)）以下特點：1適應大容量與突發(fā)性通信的規(guī)定。2適應綜合業(yè)務服務的規(guī)定。3開放的設備接口與規(guī)范化的協(xié)議。4完善的通信服務與網(wǎng)絡管理。（3）幾種常見的廣域網(wǎng)的特點：X．25、FR、SMDS、B-ISDN、N-ISDN、ATM（4）廣域網(wǎng)擴大了資源共享的范圍，局域網(wǎng)增強了資源共享的深度。（5）期的城域網(wǎng)產(chǎn)品重要是光纖分布式數(shù)據(jù)接口(FDDI)（6）各種城域網(wǎng)建設方案有幾個相同點：傳輸介質(zhì)采用光纖，互換接點采用基于IP互換的高速路由互換機或ATM互換機，在體系結(jié)構(gòu)上采用核心互換層，業(yè)務匯聚層與接入層三層模式。城域網(wǎng)MAN介于廣域網(wǎng)與局域網(wǎng)之間的一種高速網(wǎng)絡。9、計算機網(wǎng)絡拓撲是通過網(wǎng)中結(jié)點與通信線路之間的幾何關系表達網(wǎng)絡結(jié)構(gòu)，反映出網(wǎng)絡中各實體間的結(jié)構(gòu)關系。重要是指通信子網(wǎng)的拓撲構(gòu)型。10、網(wǎng)絡拓撲可以根據(jù)通信子網(wǎng)中通信信道類型分為：（1）點-點線路通信子網(wǎng)的拓撲：星型，環(huán)型，樹型，網(wǎng)狀型。（2）廣播式通信子網(wǎng)的拓撲：總線型，樹型，環(huán)型，無線通信與衛(wèi)星通信型。11、描述數(shù)據(jù)通信的基本技術參數(shù)有兩個：數(shù)據(jù)傳輸率與誤碼率。（1）數(shù)據(jù)傳輸速率:在數(shù)值上等于每秒鐘傳輸構(gòu)成數(shù)據(jù)代碼的二進制比特數(shù),單位為比特/秒(bit/second),記作bps.對于二進制數(shù)據(jù),數(shù)據(jù)傳輸速率為:S1/T(bps),其中,T為發(fā)送每一比特所需要的時間.（2）奈奎斯特準則：信號在無噪聲的信道中傳輸時,對于二進制信號的最大數(shù)據(jù)傳輸率Rmax與通信信道帶寬B（B=f，單位是Hz）的關系可以寫為：Rmax=2*f(bps)（3）香農(nóng)定理：香農(nóng)定理則描述了有限帶寬;有隨機熱噪聲信道的最大傳輸速率與信道帶寬;信號噪聲功率比之間的關系.在有隨機熱噪聲的信道上傳輸數(shù)據(jù)信號時，數(shù)據(jù)傳輸率Rmax與信道帶寬B，信噪比S/N關系為：Rmax=B*LOG⒉（1+S/N）其中：B為信道帶寬，S為信號功率，n為噪聲功率。（4）誤碼率是二進制碼元在數(shù)據(jù)傳輸系統(tǒng)中被傳錯的概率，它在數(shù)值上近似等于：Pe=Ne/N（傳錯的除以總的）a、誤碼率應當是衡量數(shù)據(jù)傳輸系統(tǒng)正常工作狀態(tài)下傳輸可靠性的參數(shù).b、對于一個實際的數(shù)據(jù)傳輸系統(tǒng),不能籠統(tǒng)地說誤碼率越低越好,要根據(jù)實際傳輸規(guī)定提出誤碼率規(guī)定;在數(shù)據(jù)傳輸速率擬定后,誤碼率越低,傳輸系統(tǒng)設備越復雜,造價越高.c、對于實際數(shù)據(jù)傳輸系統(tǒng),假如傳輸?shù)牟皇嵌M制碼元,要折合成二進制碼元來計算.d、差錯的出現(xiàn)具有隨機性,在實際測量一個數(shù)據(jù)傳輸系統(tǒng)時,只有被測量的傳輸二進制碼元數(shù)越大,才會越接近于真正的誤碼率值.12、網(wǎng)絡協(xié)議（1）概念：為網(wǎng)絡數(shù)據(jù)傳遞互換而指定的規(guī)則，約定與標準被稱為網(wǎng)絡協(xié)議。（2）協(xié)議分為三部分：(1)語法,即用戶數(shù)據(jù)與控制信息的結(jié)構(gòu)和格式;(2)語義,即需要發(fā)出何種控制信息,以及完畢的動作與做出的響應;(3)時序,即對事件實現(xiàn)順序的具體說明.13、計算機網(wǎng)絡體系結(jié)構(gòu)（1）概念：將計算機網(wǎng)絡層次模型和各層協(xié)議的集合定義為計算機網(wǎng)絡體系結(jié)構(gòu)。（體現(xiàn)出的兩個內(nèi)涵請補充）（2）計算機網(wǎng)絡中采用層次結(jié)構(gòu)，可以有以下好處：各層之間互相獨立、靈活性好、各層都可以采用最合適的技術來實現(xiàn)各層實現(xiàn)技術的改變不影響其他各層、易于實現(xiàn)和維護、有助于促進標準化。14、ISO/OSI（國際標準化組織/開放系統(tǒng)互連參考模型）（1）功能：構(gòu)建網(wǎng)絡和設計網(wǎng)絡時提供統(tǒng)一的標準（2）概述：采用分層的體系結(jié)構(gòu)將整個龐大而復雜的問題劃分為若干個容易解決的小問題，采用了三級抽象，既體系結(jié)構(gòu)，服務定義，協(xié)議規(guī)格說明。實現(xiàn)了開放系統(tǒng)環(huán)境中的互連性，互操作性與應用的可移植性。（3）ISO將整個通信功能劃分為七個層次,劃分層次的原則是:網(wǎng)中各結(jié)點都有相同的層次、不同結(jié)點的同等層具有相同的功能、同一結(jié)點內(nèi)相鄰層之間通過接口通信、每一層使用下層提供的服務,并向其上層提供服務、不同結(jié)點的同等層按照協(xié)議實現(xiàn)對等層之間的通信（補充服務、接口、協(xié)議的概念）.（4）OSI七層：1物理層：重要是運用物理傳輸介質(zhì)為數(shù)據(jù)鏈路層提供物理連接，以便透明的傳遞比特流。（NIC、HUB）2數(shù)據(jù)鏈路層：分為MAC和LLC，傳送以幀為單位的數(shù)據(jù)，采用差錯控制，流量控制方法。（NIC、SWITCH）3網(wǎng)絡層：實現(xiàn)路由選擇、擁塞控制和網(wǎng)絡互連功能，使用TCP和UDP協(xié)議（ROUTER）4傳輸層：是向用戶提供可靠的端到端服務，透明的傳送報文，使用TCP協(xié)議。5會話層：組織兩個會話進程之間的通信，并管理數(shù)據(jù)的互換使用NETBIOS和WINSOCK協(xié)議。6表達層：解決在兩個通信系統(tǒng)中互換信息的表達方式。7應用層：應用層是OSI參考模型中的最高層。擬定進程之間通信的性質(zhì)，以滿足用戶的需要。15、TCP/IP參考模型（1）TCP/IP協(xié)議的特點：a、開放的協(xié)議標準，可以免費使用，并且獨立于特定的計算機硬件與操作系統(tǒng)。b、獨立于特定的網(wǎng)絡硬件，可以運營在局域網(wǎng)、廣域網(wǎng)，更合用于互聯(lián)網(wǎng)。c、統(tǒng)一的網(wǎng)絡地址分派方案，使得整個TCP/IP設備在網(wǎng)中都具有唯一的地址。d、標準化的高層協(xié)議，可以提供多種可靠的用戶服務。（2）TCP/IP參考模型可以分為：應用層，傳輸層，互連層，主機-網(wǎng)絡層。（各層功能見教材P33）（3）應用層協(xié)議分為:a、依賴于面向連接的TCP協(xié)議：重要有:文獻傳送協(xié)議FTP、電子郵件協(xié)議SMTP以及超文本傳輸協(xié)議HTTP等b、依賴于面向連接的UDP協(xié)議：重要有簡樸網(wǎng)絡管理協(xié)議SNMP;簡樸文獻傳輸協(xié)議TFTP.c、既依賴于TCP協(xié)議，也可以依賴于UDP協(xié)議：域名服務DNS等.16、ISO/OSI參考模型與TCP/IP參考模型的比較17、NSFNET采用的是一種層次結(jié)構(gòu)，可以分為主干網(wǎng)，地區(qū)網(wǎng)與校園網(wǎng)。18、Internet2的初始運營速率可達10Gbps.Internet2在網(wǎng)絡層運營的是IPv4，同時也支持IPv6業(yè)務.19、移動計算網(wǎng)絡P3920、多媒體網(wǎng)絡是指可以傳輸多媒體數(shù)據(jù)的通信網(wǎng)絡。多媒體網(wǎng)絡需要支持多媒體傳輸所需要的交互性和實時性規(guī)定。網(wǎng)絡視頻會議系統(tǒng)是一種典型的網(wǎng)絡多媒體系統(tǒng)。多媒體網(wǎng)絡應用對數(shù)據(jù)通信的規(guī)定：1高傳輸帶寬規(guī)定；2不同類型的數(shù)據(jù)對傳輸?shù)囊?guī)定不同；3網(wǎng)絡中的多媒體流傳輸?shù)倪B續(xù)性與實時性規(guī)定；4網(wǎng)絡中多媒體數(shù)據(jù)傳送的低時延規(guī)定；5網(wǎng)絡中的多媒體傳輸同步規(guī)定；6網(wǎng)絡中的多媒體的多方參與通信的特點。改善傳統(tǒng)網(wǎng)絡的方法是：增大帶寬與改善協(xié)議。增大帶寬可從傳輸介質(zhì)和路由器性能兩方面入手。改善協(xié)議重要表現(xiàn)在支持IP多播、資源預留協(xié)議、區(qū)分服務與多協(xié)議標記互換等方面。21、機群系統(tǒng)的分類與計算與存儲區(qū)域網(wǎng)絡P42-43第三章局域網(wǎng)基礎1、局域網(wǎng)重要技術特點是：P452、共享介質(zhì)訪問控制方式重要為：（1）帶有沖突檢測的載波偵聽多路訪問CSMA/CD方法。（2）令牌總線方法（TOKENBUS）。（3）令牌環(huán)方法（TOKENRING）。3、局域網(wǎng)參考模型（IEEE802）（1）IEEE802參考模型：IEEE802參考模型是美國電氣電子工程師協(xié)會在1980年2月制訂的，稱為IEEE802標準，這個標準相應于OSI參考模型的物理層和數(shù)據(jù)鏈路層，數(shù)據(jù)鏈路層又劃分為邏輯鏈路控制子層（LLC）和介質(zhì)訪問控制子層（MAC）。（2）IEEE803標準(P49)（3）IEEE802.2標準定義的共享局域網(wǎng)有三類：a、采用CSMA/CD介質(zhì)訪問控制方法的總線型局域網(wǎng)。(ETHERNET)b、采用TOKENBUS介質(zhì)訪問控制方法的總線型局域網(wǎng)。c、采用TOKENRING介質(zhì)訪問控制方法的環(huán)型局域網(wǎng)。（4）CSMA/CD的發(fā)送流程可以簡樸的概括為：先聽先發(fā)、邊聽邊發(fā)、沖突停止、延遲重發(fā)。沖突檢測是發(fā)送結(jié)點在發(fā)送的同時，將其發(fā)送信號波形與接受到的波形相比較。（5）TOKENBUS（令牌總線方法）是一種在總線拓撲中運用“令牌”作為控制結(jié)點訪問公共傳輸介質(zhì)的擬定型介質(zhì)訪問控制方法。所謂正常穩(wěn)態(tài)操作是網(wǎng)絡已經(jīng)完畢初始化，各結(jié)點進入正常傳遞令牌與數(shù)據(jù)，并且沒有結(jié)點要加入與撤除，沒有發(fā)生令牌丟失或網(wǎng)絡故障的正常工作狀態(tài)。令牌傳遞規(guī)定由高地址向低地址，最后由低地址向高地址傳遞。令牌總線網(wǎng)在物理上是總線網(wǎng)，而在邏輯上是環(huán)網(wǎng)。交出令牌的條件：1該結(jié)點沒有數(shù)據(jù)幀等待發(fā)送。2該結(jié)點已經(jīng)發(fā)完。3令牌持有最大時間到。環(huán)維護工作：1環(huán)初始化2新接點加入環(huán)3接點從環(huán)中撤出4環(huán)恢復5優(yōu)先級（6）TOKENRING（令牌環(huán)方法）4、CSMA/CD與TOKENBUS、TOKENRING的比較5、ETHERNET物理地址的基本概念（1）地址與尋址的概念（2）ETHERNET物理地址的長度（48位）、構(gòu)成、表達方法6、共享介質(zhì)局域網(wǎng)可分為Ethernet，TokenBus，TokenRing與FDDI以及在此基礎上發(fā)展起來的100MbpsFastEthernet、1Gbps與10GbpsGigabitEthernet。7、互換式局域網(wǎng)可分為SwitchEthernet與ATMLAN，以及在此基礎上發(fā)展起來的虛擬局域網(wǎng)。8、光纖分布式數(shù)據(jù)接口FDDI是一種以光纖作為傳輸介質(zhì)的高速主干網(wǎng)。FDDI重要技術特點:(1)使用基于IEEE802.5的單令牌的環(huán)網(wǎng)介質(zhì)訪問控制MAC協(xié)議;(2)使用IEEE802.2協(xié)議,與符合IEEE802標準的局域網(wǎng)兼容;(3)數(shù)據(jù)傳輸速率為100Mbps,連網(wǎng)的結(jié)點數(shù)小于等于1000,環(huán)路長度為100km;(4)可以使用雙環(huán)結(jié)構(gòu),具有容錯能力;(5)可以使用多?；騿文９饫w;(6)具有動態(tài)分派帶寬的能力,能支持同步和異步數(shù)據(jù)傳輸.9、快速以太網(wǎng)（100MbpsFastEthernet）IEEE802.3U10、千兆位以太網(wǎng)（1GbpsGigabitEthernet）IEEE802.3ZGigabitEthernet的傳輸速率比FastEthernet（100Mbps）快10倍，達成1000Mbps，將傳統(tǒng)的Ethernet每個比特的發(fā)送時間由100ns減少到1ns。11、10GbpsGigabitEthernet12、互換機的的幀轉(zhuǎn)發(fā)方式：（各自特點）（1）直接互換方式。（2）存儲轉(zhuǎn)發(fā)互換方式。（3）改善直接互換方式。13、局域網(wǎng)互換機的特性：低互換傳輸延遲、高傳輸帶寬、允許10Mbps/100Mbps、局域網(wǎng)互換機可以支持虛擬局域網(wǎng)服務。14、虛擬網(wǎng)絡（VLAN）（1）是建立在互換技術基礎上（局域網(wǎng)互換機或ATM互換機）的，以軟件的形式來實現(xiàn)邏輯組的劃分與管理，邏輯工作組的結(jié)點組成不受物理位置的限制。（2）對虛擬網(wǎng)絡成員的定義方法上，有以下4種：用互換機端標語定義虛擬局域網(wǎng)、用MAC地址定義虛擬局域網(wǎng)、用網(wǎng)絡層地址定義虛擬局域網(wǎng)（用IP地址來定義）、IP廣播組虛擬局域網(wǎng)這種虛擬局域網(wǎng)的建立是動態(tài)的，它代表一組IP地址。15、無線局域網(wǎng)（1）無線局域網(wǎng)的應用領域（P64）（2）紅外無線局域網(wǎng)的重要特點及數(shù)據(jù)傳輸?shù)娜N技術（P65）（3）擴頻無線局域網(wǎng)：FHSS、DSSS（P66）（4）無線局域網(wǎng)標準：IEEE802.1116、IEEE802.3物理層標準類型（請補充完整P67）17、網(wǎng)卡是網(wǎng)絡接口卡簡稱NIC是構(gòu)成網(wǎng)絡的基本部件。（1）網(wǎng)卡分類：①按網(wǎng)卡支持的計算機種類：標準以太網(wǎng)卡。PCMCIA網(wǎng)卡（用于便攜式計算機）。②按網(wǎng)卡支持的傳輸速率分類：普通的10Mbps。高速的100Mbps網(wǎng)卡。10/100Mbps自適應網(wǎng)卡。1000Mbps網(wǎng)卡。③按網(wǎng)卡支持的傳輸介質(zhì)類型分類：雙絞線網(wǎng)卡。粗纜網(wǎng)卡。細纜網(wǎng)卡。光纖網(wǎng)卡。(它們所使用的接口)18、局域集線器(HUB)普通的集線器兩類端口：一類是用于連接接點的RJ-45端口，這類端口數(shù)可以是8，12，16，24等。另一類端口可以是用于連接粗纜的AUI端口，用于連接細纜的BNC端口，也可以是光纖連接端口，這類端口稱為向上連接端口。按傳輸速率分類：1。10Mbps集線器。2。100Mbps集線器。3。10Mbps/100Mbps自適應集線器。按集線器是或可以堆疊分類：1。普通集線器。2。可堆疊式集線器。按集線器是或支持網(wǎng)管功能：1。簡樸集線器。2。帶網(wǎng)管功能的集線器。19、局域網(wǎng)互換機（SWITCH）專用端口，共享端口。局域網(wǎng)互換機可以分為：1簡樸的10Mbps互換機。210Mbps/100Mbps自適應的局域網(wǎng)互換機。3大型局域網(wǎng)互換機。20、各種組網(wǎng)方法21、結(jié)構(gòu)化布線的地位及與傳統(tǒng)布線的區(qū)別結(jié)構(gòu)化布線系統(tǒng)與傳統(tǒng)的布線系統(tǒng)最大的區(qū)別在于：結(jié)構(gòu)化布線系統(tǒng)的結(jié)構(gòu)與當前所連接的設備位置無關。結(jié)構(gòu)化布線系統(tǒng)先預先按建筑物的結(jié)構(gòu)，將建筑物中所有也許放置計算機及其外部設備的位置都布好了線，然后再根據(jù)實際所連接的設備情況，通過調(diào)整內(nèi)部跳線裝置，將所有計算機設備以及外部設備連接起來。22、智能大樓的組成:結(jié)構(gòu)化布線系統(tǒng)、辦公自動化系統(tǒng)（OA）、通信自動化系統(tǒng)（CA）、樓宇自動化系統(tǒng)（BA）、計算機網(wǎng)絡（CN）23、結(jié)構(gòu)化布線系統(tǒng)的應用環(huán)境：建筑物綜合布線系統(tǒng)、智能大樓布線系統(tǒng)、工業(yè)布線系統(tǒng)（各自特點）24、網(wǎng)絡互連（1）同種局域網(wǎng)使用網(wǎng)橋就可以將分散在不同地理位置的多個局域網(wǎng)互連起來。（2）異型局域網(wǎng)可以用網(wǎng)橋、路由器或網(wǎng)關互連起來。（3）ATM局域網(wǎng)與傳統(tǒng)共享介質(zhì)局域網(wǎng)互連必須解決局域網(wǎng)仿真問題。（4）路由器或網(wǎng)關是實現(xiàn)局域網(wǎng)與廣域網(wǎng)、廣域網(wǎng)與廣域網(wǎng)互連的重要設備。（5）數(shù)據(jù)鏈路層互連的設備是網(wǎng)橋。網(wǎng)橋在網(wǎng)絡互連中起到數(shù)據(jù)接受，地址過渡與數(shù)據(jù)轉(zhuǎn)發(fā)的作用，它是實現(xiàn)多個網(wǎng)絡系統(tǒng)之間的數(shù)據(jù)互換。（6）網(wǎng)絡層互連的設備是路由器。假如網(wǎng)絡層協(xié)議不同，采用多協(xié)議路由器。（7）傳輸層以上各層協(xié)議不同的網(wǎng)絡之間的互連屬于高層互連。實現(xiàn)高層互連的設備是網(wǎng)關。高層互連的網(wǎng)關很多是應用層網(wǎng)關，通常簡稱為應用網(wǎng)關。（8）網(wǎng)絡互連指將分布在不同地理位置的網(wǎng)絡，設備相連接，以構(gòu)成更大規(guī)模的互聯(lián)網(wǎng)絡系統(tǒng)，實現(xiàn)互聯(lián)系統(tǒng)網(wǎng)絡資源的共享。（9）網(wǎng)絡互連的規(guī)定（P80）（10）網(wǎng)絡互連的問題（P80）（11）網(wǎng)絡互連的功能有以下兩類：1基本功能。2擴展功能。（12）網(wǎng)橋是在數(shù)據(jù)鏈路層上實現(xiàn)不同網(wǎng)絡互連的設備。（網(wǎng)橋的基本特性（P81）。網(wǎng)橋在局域網(wǎng)中經(jīng)常被用來將一個大型局域網(wǎng)提成既獨立又能互相通信的多個子網(wǎng)的互連結(jié)構(gòu)，從而可以改善各個子網(wǎng)的性能與安全性?；谶@兩種標準的網(wǎng)橋分別是：透明網(wǎng)橋（IEEE802.1合用于ETHERNET）、源路選網(wǎng)橋（IEEE802.5合用于TOKENRING）（13）路由器是在網(wǎng)絡層上實現(xiàn)多個網(wǎng)絡互連的設備。（14）網(wǎng)關可以完畢不同網(wǎng)絡協(xié)議之間的轉(zhuǎn)換。實現(xiàn)協(xié)議轉(zhuǎn)換的方法重要是：直接將網(wǎng)絡信息包格式轉(zhuǎn)化成輸出網(wǎng)絡信息包格式N(N-1)；將輸入網(wǎng)絡信息包的格式轉(zhuǎn)化成一種統(tǒng)一的標準網(wǎng)間信息包的格式2N。一個網(wǎng)關可以由兩個半網(wǎng)關構(gòu)成。第四章網(wǎng)絡操作系統(tǒng)1、網(wǎng)絡操作系統(tǒng)的三大陣營：UNIX、NOVELL公司Netware、Microsoft公司W(wǎng)indowsNT2、單機操作系統(tǒng)的功能：（1）進程管理：對CPU的管理，在DOS中啟動進程機制函數(shù)為EXEC在WINDOWS或OS/2中是Createprocess（2）內(nèi)存管理：對RAM用戶區(qū)的管理，DOS中的內(nèi)存管理運營在實模式下而WINDOWS或OS/2中的運營在保護模式下（3）文獻I/O管理：對硬盤的管理重要涉及文獻的保護、保密、、共享等。（文獻名柄、FAT、VFAT、HPFS）3、網(wǎng)絡操作系統(tǒng)（NOS）：（1）概述：是網(wǎng)絡用戶與計算機之間的接口一般具有硬件獨立性的特性即獨立于具體的硬件平臺支持多平臺。（2）概念：能使網(wǎng)絡上各個計算機方便而有效的共享網(wǎng)絡資源，為用戶提供所需要的各種服務的操作系統(tǒng)軟件。（3）功能：使連網(wǎng)的計算機可以方便而有效的共享網(wǎng)絡資源，為網(wǎng)絡用戶提供所需要的各種服務的軟件與協(xié)議的集合。（4）任務：屏蔽本地資源與網(wǎng)絡資源的差異性、為用戶提供各種基本網(wǎng)絡服務功能、完畢網(wǎng)絡共享系統(tǒng)資源的管理、提供網(wǎng)絡系統(tǒng)的安全性服務。4、網(wǎng)絡操作系統(tǒng)分為兩類：面向任務型NOS與通用型NOS。通用型又可以分為：變形系統(tǒng)與基礎級系統(tǒng)。5、網(wǎng)絡操作系統(tǒng)的發(fā)展經(jīng)歷了從對等結(jié)構(gòu)與非對等結(jié)構(gòu)演變的過程。（1）對等結(jié)構(gòu)網(wǎng)絡操作系統(tǒng)的特點、優(yōu)點、缺陷、提供服務（2）非對等結(jié)構(gòu)網(wǎng)絡操作系統(tǒng)，將連網(wǎng)結(jié)點分為以下兩類：1網(wǎng)絡服務器。2網(wǎng)絡工作站。虛擬盤體可以分為以下三類：專用盤體（分派給不同用戶，用戶通過網(wǎng)絡命令將專用盤體鏈接到工作站）、共用盤體（具有只讀屬性，允許多用戶同時操作）與共享盤體（具有可讀可寫屬性，允許多用戶同時操作）（3）基于文獻服務的網(wǎng)絡操作系統(tǒng)，分為兩部分：文獻服務器（具有分時系統(tǒng)文獻管理的所有功能，能為用戶提供數(shù)據(jù)、文獻、目錄服務）、工作站軟件。6、局域網(wǎng)軟硬件的典型構(gòu)成典型的局域網(wǎng)可以當作由以下三個部分組成：網(wǎng)絡服務器，工作站與通信設備。7、網(wǎng)絡操作系統(tǒng)的基本功能：文獻服務、打印服務、數(shù)據(jù)庫服務、通信服務、信息服務、分布式服務、網(wǎng)絡管理服務、Internet/Internet服務（分別用一句話總結(jié)其特點）8、WindowsNT（1）WindowsNTServer是服務器端軟件，WindowsNTWorkstation是客戶機端軟件（2）WindowsNT的版本不斷變化過程中有兩個概念始終沒有變那就是工作組模型與域模型（3）域的概念與分類：P94（4）特點（5個）：P94（5）WindowsNT的優(yōu)缺陷P95第二章數(shù)據(jù)結(jié)構(gòu)算法2.1基本概率考點1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)在計算機系統(tǒng)中，數(shù)據(jù)不僅包含了通常的數(shù)值概念，尚有更廣泛的含義我們把采用計算機對客觀事物進行辨認、存儲和加工所做的描述，統(tǒng)稱為數(shù)據(jù)。簡言之，數(shù)據(jù)就是計算機化的信息數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位，又稱為關鍵碼，其值可以唯一擬定一個數(shù)據(jù)元素的數(shù)據(jù)項。2.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)涉及3個方面的內(nèi)容：數(shù)據(jù)之間的邏輯關系、數(shù)據(jù)在計算機中的存儲方式，以及在這些數(shù)據(jù)上定義的運算的集合。(l)數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)在計算機中的存儲方式無關，它用來抽象地反映數(shù)據(jù)元素之間的邏輯關系。邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。最常見的線性結(jié)構(gòu)是線性表，最典型的非線性結(jié)構(gòu)是樹型結(jié)構(gòu)。(2)數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)實現(xiàn)了數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)的存儲問題，存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)。存儲結(jié)構(gòu)分為順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)。(3)數(shù)據(jù)的運算。數(shù)據(jù)的各種邏輯結(jié)構(gòu)都有相相應的運算，每一種邏輯結(jié)構(gòu)都有一個運算的集合。數(shù)據(jù)運算重要涉及查找(檢索)、排序、插人、更新及刪除等?？键c2重要的數(shù)據(jù)存儲方式實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計算機存儲器的映像有多種不同的方式。順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)是兩種最重要的存儲方式。1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，節(jié)點之間的關系由存儲單元的相鄰關系來決定，它重要用于存儲線性結(jié)構(gòu)的數(shù)據(jù)。順序存儲結(jié)構(gòu)的重要特點如下。(1)由于節(jié)點之間的關系由物理上的相鄰關系決定，所以節(jié)點中沒有鏈接信息域，只有自身的信息域，存儲密度大，空間運用率高。(2)數(shù)據(jù)結(jié)構(gòu)中第i個節(jié)點的存儲地址乙可由下述公式計算求得：L?i＝L?0＋(i－1)×KL?0為第一個節(jié)點存儲地址，左為每個節(jié)點所占的存儲單元數(shù)。(3)插人、刪除運算會引起相應節(jié)點的大量移動各節(jié)點的物理地址是相鄰的，每一次插人、刪除運算會引起相應節(jié)點物理地址的重新排列。2.鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)打破了計算機存儲單元的連續(xù)性，可以將邏輯上相鄰的兩個數(shù)據(jù)元素存放在物理上不相鄰的存儲單元中鏈式存儲結(jié)構(gòu)的每個節(jié)點中至少有一個節(jié)點域，來體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。鏈式存儲結(jié)構(gòu)的重要特點涉及以下幾個方面。(1)節(jié)點中除自身信自、外，尚有表達鏈接信息的指針域，因此比順序存儲結(jié)構(gòu)的存儲密度小，存儲空間運用率低。(2)：羅輯上相鄰的節(jié)點物理上不一定相鄰，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表達。(3)插人、刪除等操作靈活方便，不需要大量移動節(jié)點，只需將節(jié)點的指針值修改即可。考點3算法設計與分析在計算機領域，一個算法實質(zhì)上是針對所解決問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎上施加的一種運算，它是解決特定問題的方法。一個算法所占用的計算機資源涉及時間代價和空間代價兩個方面時間代價的含義是：當問題的規(guī)模以某種單位由1增至n時，解決該問題的算法運營時所花費的時間也以某種單位由f(1)增至f(n)，則稱該算法的時間代價為f(n)?？臻g代價的含義是：當問題的規(guī)模以某種單位由1增至n時，解決該問題的算法實現(xiàn)時所占用的空間也以某種單位由到g(1)增至g(n)，則稱該算法的空間代價為g(n)。2.2線性表線性表的邏輯結(jié)構(gòu)是由n個數(shù)據(jù)元素組成的一個有限序列。線性表中所包含元素的個數(shù)叫線性表的長度．它是可變的．可同線性表中增長或刪除元素。線性表涉及順序表、鏈表、散列表和串等。線性表的基本運算有：置表空、求表長、讀表元素、插人、刪除及檢索等操作。考點4順序表和一維數(shù)組線性表的順序存儲是線性表的一種最簡樸的存儲結(jié)構(gòu)。其存儲方法是：在內(nèi)存中為線性表開辟一塊連續(xù)的存儲空間，該存儲空間所包含的存儲單元數(shù)要大于或等于線性表的長度，讓線性表的第一個元素存儲在這個存儲空間的第一個單元中，第二個元素存儲在第二個單元中，其他元素依次類推。一般情況下，若長度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動的平均次數(shù)均為n/2。考點5鏈表鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈式存儲表達，非線性鏈表是非線性數(shù)據(jù)結(jié)構(gòu)樹和圖的鏈式存儲表達。1.線性鏈表線性鏈表也稱為單鏈表，其每個一節(jié)點中只包含一個指針域。對鏈表進行插人、刪除運算時只需改變節(jié)點中指針域的值。(1)在指針一P后插人指針q的關鍵運算環(huán)節(jié)：q↑.link：＝P↑．link：p↑.link：＝q；(2)刪除指針P后繼節(jié)點q的關鍵運算環(huán)節(jié)：q：＝p↑.link；p↑.link：＝q↑．link；(3)在第一個節(jié)點(或稱頭節(jié)點)前插人一個指針P的關鍵運算環(huán)節(jié)：p↑.link：＝head；head：二P；(4)刪除表中頭節(jié)點的關鍵運算環(huán)節(jié)：head：＝head↑.link：2.雙鏈表在雙鏈表中，每個節(jié)點中設立有兩個指針域，分別用以指向其前驅(qū)節(jié)點和后繼節(jié)點。rlink指向節(jié)點的后繼，llink指向節(jié)點的前驅(qū)，這樣的結(jié)構(gòu)方便向后和向前查找。(l)若要在雙鏈表中刪除指針P所指的節(jié)點時，只需修改其前驅(qū)的rlink字段和后繼的Mink字段，環(huán)節(jié)如下：p↑.llink↑.rlink：＝p↑.rlink；P↑T．rlink↑.llink：＝P↑．llink；(2)假如要在指針P后面插人指針q所指的新節(jié)點，只需修改P指針所指節(jié)點的rlink字段和本來后繼均Ilink字段，并重新設立q所指節(jié)點的Mink和rlink值，環(huán)節(jié)如下：q↑.Mink：＝P：q↑．rlink：＝P↑．rlink;P↑．rlinkr.Rink：＝q；p↑．rlink：＝q;3.可運用空間表可運用空間表的作用是管理可用于鏈表插人和刪除的節(jié)點，當鏈表插人需要一個新節(jié)點時，就從可運用空間表中刪除第一個節(jié)點，用這個節(jié)點去做鏈表插人；當從鏈表中刪除一個節(jié)點時，就把這個節(jié)點插人到可運用空間表的第一個節(jié)點前面?？键c6棧棧又稱為堆棧，它是一種運算受限的特殊的線性表，僅允許在表的一端進行插人和刪除運算，可進行運算的一端為棧頂(top)，另一端為棧底(bottom)。表中無任何元素的棧稱為空棧。由于棧的插人和刪除運算僅在棧頂進行，后進棧的元素必然先被刪除，所以又把棧稱為“后進先出”(LIFO)表。棧的基本操作有：(1)push(S,X)。往棧S中插人(或稱推人)一個新的棧頂元素x，即進棧。(2)pop(S)。從棧S中刪除(或稱彈出)棧頂元素，即出棧。(3)lop(S，X)：把棧S的棧頂元素讀到變量x中，棧保持不變。(4)empty(S)。判斷棧S是否為空棧，是則返回值為真。(5)makempty。(S)將棧S設立為空。棧既然是一種線性表，所以線性表的存儲結(jié)構(gòu)同樣也合用于棧。棧通常用順序存儲方式來存儲，分派一塊連續(xù)的存儲區(qū)域存放棧中元素，用一個變量來指向當前棧頂?？键c7隊列隊列簡稱為隊，它也是一種運算受限的線性表，隊列的限定是僅允許在表的一端進行插入，而在另一端進行刪除。進行刪除操作的一端稱做隊列的頭，進行插人操作的一端稱為隊列的尾.隊列的基本操作有：(1)enq(Q,X)。往隊列口中插人一個新的隊尾元素x，即人隊。(2)deq(口)從隊列Q中刪除隊頭元素，即出隊。(3)front口,x)將隊列口的隊頭元素值讀到變量x中，隊列保持不變。(4)empty(Q)．判斷隊歹，l口是否為空，是則返回值為真。(5)makempty(口)將隊列口置為空隊列。和線性表同樣、隊列的存儲方式也有順序存儲和鏈式存儲兩種。順序隊列在進行人隊操作時，會產(chǎn)生假溢出現(xiàn)象解決的辦法是讓隊列首尾相連，構(gòu)成一個循環(huán)隊列?？键c8串串(或字符串)是由零個或多個字符組成的有限序列。零個字符的串是空串。串中字符的個數(shù)就是串的長度串中的字符可以是字母、數(shù)字或其他字符。串的存儲同樣也有順序存儲和鏈式存儲兩種。順序存儲時，既可以采用非緊縮方式，也可以采用緊縮方式。串的基本運算有連接、賦值、求長度、全等比較、求子串、找子串位置及替換等，其中找子串位置(或稱模式匹配)比較重要。2.3多維數(shù)組、稀疏矩陣和廣義表考點9多維數(shù)組的順序存儲多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的所有元素并未排在一個線性序列里，要順序存儲多維數(shù)組就需要按一定順序把所有的元素排在一個線性序列里。常用的排列順序有行優(yōu)先順序和列優(yōu)先順序兩種?？键c10稀疏矩陣的存儲稀疏矩陣是指矩陣中具有大量的0元素。對稀疏矩陣可進行壓縮存儲，即只存儲其中的非0元素。若非0元素分布是有規(guī)律的，可用順序方法存儲非0元素。對于一般的稀疏矩陣，常見的存儲方法尚有不元組法和十字鏈表法，這里就不再介紹了?？键c11廣義表的定義和存儲廣義表(又稱列表)是線性表的另一種推廣，是由零個或多個單元素或子表所組成的有限序列。它與線性表的區(qū)別在于：線性表中的元素都是結(jié)構(gòu)上不可分的單元素，而廣義表中的元素既可以是單元素，又可以是有結(jié)構(gòu)的表廣義表與線性表相比，具有如下3個方面的特性。(1)廣義表的元素可以是子表，而子表的元素還可以是子表。(2)廣義表可被其他廣義表引用二(3)廣義表可以是遞歸的表，即廣義表也可以是自身的一個子表。2.4樹型結(jié)構(gòu)樹型結(jié)構(gòu)是節(jié)點之間有分支的、層次關系的結(jié)構(gòu)，它類似于自然界中的樹，是一類重要的非線性結(jié)構(gòu)常用的樹型結(jié)構(gòu)有樹和二叉樹?？键c12樹的定義樹是樹型結(jié)構(gòu)的一個重要類型。一棵樹或者是沒有任何節(jié)點的空樹，或者是由一個或多個節(jié)點組成的有限集合T，其中：(1)有且僅有一個稱為該樹根的節(jié)點。(2)除根節(jié)點外的其余節(jié)點可分為。M(m≥0)個互不相交的有限集71,，兀，…，T，其中每一個集合自身又是一棵樹，并且稱為根的子樹。這是一個遞歸的定義，即在樹的定義中又用到了樹的概念。這恰好顯示了樹的固有特性。考點13二叉樹定義1.二叉樹的定義二叉樹是一種最簡樸而巨重要的樹型結(jié)構(gòu)它或者是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的、分別稱為這個根的左子樹和右子樹的二叉樹組成。有兩種特殊形態(tài)的二＿叉樹，它們是滿二叉樹一和完全二叉樹。2.二叉樹與樹的區(qū)別盡管樹和二叉樹的概念之間有許多關系，但它們是兩個概念二叉樹不是樹的特殊情況，樹和二叉樹之間最重要的區(qū)別是：二叉樹的節(jié)點的子樹要區(qū)分左子樹和了。子樹，即使在節(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹?？键c14樹與二叉樹之間的轉(zhuǎn)換1.樹轉(zhuǎn)換成二叉樹將一棵樹轉(zhuǎn)換成相應的二叉樹應涉及以下幾個環(huán)節(jié)：(1)在兄弟竹點之間加條連線(2)對每一個節(jié)點，只保存它與第一個子節(jié)點的連線，與其他子節(jié)點連線所有抹掉(3)以樹根為軸心，順時針旋轉(zhuǎn)45。2.森林轉(zhuǎn)換成二叉樹假如F={T?1??，T?2,…Tm}是森林，則可按如下規(guī)則將其轉(zhuǎn)換乘一棵二叉樹B=(root,LB,RB,)：(1)若F為空，即m＝0，則B為樹。(2)若F非空，即m≠0,則B的跟root即為森林中的第一棵樹的跟ROOT(??T)；B的左子樹LB是從T、中根節(jié)點的子樹森林F1＝｛T11，T?，…，T?m｝轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林Fˊ＝{T?1,T2,…Tm}轉(zhuǎn)換而成的二叉樹。3.二叉樹轉(zhuǎn)換成森林假如B二(root，LB，RB)是、棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F＝{T?1,T2,…Tm}：(1)若B為空，則F為空。(2)若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root;T1中根節(jié)點的子樹森林Fl是由B的左子樹LB轉(zhuǎn)換而成的；F中除T1之外其余樹組成的森林Fˊ＝{T?1,T2,…Tm}是由B的右子樹RB轉(zhuǎn)換而成的。考點15二叉樹和樹的環(huán)游環(huán)游(或稱遍歷)是樹型結(jié)構(gòu)的一種重要運算，是其他運算的基礎。環(huán)游一棵樹就是按一定的順序訪問樹中聽有節(jié)點，并且每個節(jié)點僅被訪問一次的過程。1.環(huán)游二叉樹二又樹的環(huán)游重要有以下3種方式。(1)前序法(NLR)。訪問根，按前序環(huán)游左子樹，按前序環(huán)游右子樹。(2)后序法(LRN)。按后序環(huán)游左子樹，按后序環(huán)游右子樹，訪問根。(3)對稱序法(LNR)。按對稱序環(huán)游左子樹，訪問根，按對稱序環(huán)游右子樹。2.環(huán)游樹和樹林對樹和樹林的環(huán)游分為按深度優(yōu)先和按廣度優(yōu)先兩種方式進行。按深度優(yōu)先方式又可分為按先根順序和按后根順序環(huán)游兩種方式。(1)先根順序環(huán)游訪問第一棵樹的根，按先根順序環(huán)游第一棵樹的根子樹，按先根順序環(huán)游其他的樹。(2)后根順序環(huán)游按后根順序環(huán)游第一棵樹的子樹，訪問第一棵樹的根，按后根順序環(huán)游其他的樹。比較一下樹與一又樹之間的相應關系，可以看出，按先根順序環(huán)游樹正好與按前序法環(huán)游樹相應的二叉樹等同，后根順序環(huán)游樹正好與按對稱序法環(huán)游相應的二叉樹等同。按廣度優(yōu)先方式可以做層次順序環(huán)游，一方面依次訪問層數(shù)為0的節(jié)點，然后依次訪問下一層的節(jié)點，直至訪問完最后一層的節(jié)點。考點16二叉樹的存儲和線索l二叉樹的llink一rlink法存儲表達二叉樹的存儲通常采用鏈接方式，即每個節(jié)點除存儲節(jié)點自身的信息外再設立兩個指針域llink和rlink，分別指向節(jié)點的左子女和右子女。當節(jié)點的某個子女為空時，則相應的指針值為空。再加上一個指向樹根的指針t，就構(gòu)成了二叉樹的存儲表達。這種存儲表達法被稱為llink-rlink表達法。2.線索二叉樹在有n個節(jié)點的二叉樹的且ink-rlink法存儲表達中，必然有n+1個空指針域，將這些指針位置運用起來，存儲節(jié)點在指定環(huán)游順序F的前驅(qū)、后繼節(jié)點指針，則得到線索二叉樹?？键c17哈夫曼樹哈夫曼樹是樹型結(jié)構(gòu)的一種應用二哈夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權途徑長度最短的樹，這種樹在信息檢索中經(jīng)常用到。所謂途徑長度就是從一個節(jié)點到另一個節(jié)點所通過的分支總數(shù)。樹的途徑長度是從樹的根到每個節(jié)點的途徑長度之和。完全二叉樹就是這種途徑長度最短的二叉樹。節(jié)點的帶權途徑長度為從該節(jié)點到樹根之間的途徑長度與節(jié)點上權的乘積。樹的帶權途徑長度為樹中所有葉子節(jié)點的帶權途徑長度之和，WPL最小的不是完全二叉樹，而是權大的葉子離根最近的二叉樹。2.5“查找查找是數(shù)據(jù)結(jié)構(gòu)中一種很常用的基本運算。查找就是在數(shù)據(jù)結(jié)構(gòu)中找出滿足某種條件的節(jié)點。所給的條件可以是關鍵碼字段的值，也可以是非關鍵碼字段的值，本節(jié)只考慮基于關鍵碼值的查找考點18順序查找順序查找是線性表的最簡樸、最基本的查找方法順序查找的優(yōu)點是對線性表節(jié)點的邏輯順序無規(guī)定，對線性表存儲結(jié)構(gòu)也無規(guī)定順序查找的缺陷是速度較慢，平均檢索長度與表中節(jié)點個數(shù)和n成正比，查找成功最多需比較n次，平均查找長度為(n+1)/2次，約為表長的，半，查找失敗需比較n+l次順序查找算法的時間復雜度為O(n)?？键c19二分法查找二分法查找是一種效率比較高的查找方法，在進行二分法查找時，線性表節(jié)點必須按關鍵碼值排序，且線性表是以順序存儲方式存儲的。二分法查找的優(yōu)點是比較次數(shù)少，查找速度快，平均檢索長度小，通過｛＿logen次比較就可以完畢查找過程。缺陷是在查找之前要為建立有序表付出代價，同時對有序表的插人和刪除都需要平均比較和移動表中的一半元素。一般情況下，二分查找適應于數(shù)據(jù)相對固定的情況，且二分法查找只合用于線性表的順序存儲?？键c20分塊查找分塊查找又稱索引順序查找，是介于線性查找和二分法查找之間的一種查找方法。它規(guī)定把線性表分成若干塊，每一塊中的節(jié)點不必有序，但塊與塊之間必須排序，不妨設每一塊中各節(jié)點的關鍵碼都大于前一塊的最大關鍵碼值。此外，還規(guī)定將各塊中的最大關鍵碼值組成一個有序的索引表。滿足上述條件的線性表稱做分塊有序表。它的分塊檢索的過程分以下兩步進行。(I)先查索引表(可以用線性檢索或二分法檢索)，擬定要找的記錄在哪一塊。(2)在相應的塊中線性檢索待查記錄?？键c21散列表的存儲和查找散列存儲中使用的函數(shù)稱為散列(Hash)函數(shù)散列表(又稱哈希表)是線性表的一種重要的存儲方式和檢索方法。實現(xiàn)散列技術檢索必須解決兩個問題：一個是構(gòu)造一個好的散列函數(shù)，盡也許避免沖突現(xiàn)象的發(fā)生；另一個是設計有效的解決沖突的方法。1.散列函數(shù)常用的散列函數(shù)有以下幾種。(l)除余法。選擇一個適當?shù)恼麛?shù)川通常選p為不大于散列表存儲區(qū)域大刁、的最大素數(shù))，用p去除關鍵碼值，取其余數(shù)作為地址，即h(key)二keymodp。(2)數(shù)字分析法。當關鍵碼的位數(shù)比存儲區(qū)域地址碼位數(shù)多時，可以對關鍵碼的各位進行分析，去掉分布不均勻的位，留下分布均勻的位作為地址。(3)折疊法。將關鍵碼值從某些地方斷開，分為幾段，折疊相加，作為地址。(4)中平方法。對關鍵碼值求平方，取中間的幾位數(shù)作為地址。2.解決沖突的方法發(fā)生沖突是指由關鍵字求得的散列地址為i(O-i-m一l)的位置上已存有記錄，解決沖突就是為該關健字找到另一個“空”的散列地址。常用的解決沖突的方法有開地址法、拉鏈法等。3.負載因子(裝填因子)和平均檢索長度裝填因子表達散列表的裝滿限度，定義為散列表中節(jié)點的數(shù)目除以基本區(qū)域能容納的節(jié)點數(shù)所得的商，用a表達a越小，沖突的也許性越小，a越大，沖突的也許性越大，檢索時需要比較的次數(shù)就越多。平均檢索長度依賴于散列表的裝填因子。2.6排序排序是數(shù)據(jù)解決領域經(jīng)常要使用的一種運算，就是將一組元素按照關鍵碼的遞增或遞減的順序來排列為過程按照排序過程中的存儲器不同，可將排序方法分為內(nèi)部排序和外部排序兩類。一廠面將介紹插人排序、選擇排序、互換排序和歸并排序等幾種常用的內(nèi)部排序方法?？键c22插入排序插人排序的基本思想：每一步將一個待排序的記錄按其關鍵字值的大小插人到一個有序的文獻中，插人后該文獻仍然是有序文獻。l.直接插入排序直接插人排序是一種最簡樸的排序方法它的基木思想是將一個記錄插人到已排好序的有序表中，從而得到一個新的、記錄數(shù)增I的有序表整個排序過程為：先將第一個記錄當作是一個有序的子序列，然后從第2個記錄起依次逐個地插人到這個有序的子序列中去。直接插人排序的時間復雜度為0(n)。直接插人排序方法不僅合用于順序表，并且合用于單鏈表2.二分法插入排序在直接插人排序｝｝，，若采用二分法查找而不是順序查找待插入元素的插人位置，則稱為二分法插入排序這種插人排序可減少比較次數(shù)，使排序速度有所提高，但提高不會太多，由于移動記錄的總次數(shù)不受改變，其時間復雜度仍為0(n2)。直接插人和二分法插入排序方法都是穩(wěn)定的，由于它們不會改變原序列中具有相同關鍵字記錄的相對順序。3.希爾排序希爾排序又稱縮小增量排序，它是對直接插人排序的一種改善方法希爾排序的基本思緒：對相隔較大距離的記錄進行比較，就能使記錄在比較后移動較大的距離這樣能使較小的記錄盡快往前移，較大的記錄盡快往后移，從而提高排序的速度希爾排序是一種不穩(wěn)定的排序過程考點23選擇排序選擇排序的基木思想是每次從待排序的記錄中選出關鍵碼值最小或最大的記錄放在已排好序的記錄序列后面，直至排序完畢。1.直接選擇排序直接選擇排序也是一種簡樸的排序方法。選擇排序的基本方法是：每次從待排序的區(qū)間中選擇出具有最小排序碼的元素。把該元素與該區(qū)間的第一個元素互換位置。第一次待排序區(qū)間為A[1]～A[n]，通過選擇和互換后，A［1］為最小排序碼的元素。第二次待排序區(qū)間為A[2]~A[n]，通過選擇和互換后，A[2]為僅次于A［1］的具有最小排序碼的元素，依次類推，通過n-1次選擇和互換后，排序完畢。直接選擇排序方法的時間復雜度為O(n2)，此方法是不穩(wěn)定的。2.堆排序堆的定義如下：n個元素序列{k?1,k2，…，kn}，當且僅當滿足下列關系時，稱之為堆。Ki≤K2i,Ki≤K2i＋1，i＝1，2，…，n/2堆排序的基本思想：對一組待排序的關鍵碼，一方面把它們按堆的定義排列成一個序列，找到其中最小的關鍵碼．接著將最小的關鍵碼取出，然后將剩下的關鍵碼再建堆排序，依次進行，直到將所有關鍵碼排好為止。建堆的基本方法是將大的元素下沉，小的元素上浮，即所謂的篩選法。在最壞的情況下，堆排序時間復雜度為O(nlog2n)。堆排序僅需一個記錄大小的輔助存儲空間。堆排序是不穩(wěn)定的?？键c24互換排序互換排序的基本思想：兩兩比較待排序記錄的關鍵字值，并互換不滿足順序規(guī)定的那些記錄，直到所有記錄滿足關鍵字值排序規(guī)定為止。1.起泡排序起泡排序又稱為冒泡排序，其基本思想是通過相鄰記錄之間關鍵字的比較和互換，使關鍵字值較小的記錄逐漸從底部移向頂部，即從下標較大的單元移向下標較小的單元，關鍵字較大的記錄從頂部移向底部。從起泡排序算法可以看出，若初始序列為“正序”序列，則只需進行一趟排序；反之，若初始序列為“逆序”序列，則需進行。一I趟排序。因此，總的時間復雜度為。(礦)。起泡排序是一種穩(wěn)定的排序過程。2.快速排序快速排序是口前內(nèi)部排序中速度最快的一種排序算法，其實質(zhì)是對起泡排序的改善在快速排序中，記錄的比較和互換是從兩端向中間進行的，排序碼較大的記錄一次就可以從前面互換到后面單元，排序碼較小的記錄一次就可以從后面互換到前面單元，記錄每次移動的距離較遠，總比較和移動次數(shù)較少。快速排序是不穩(wěn)定的排序。排序速度最快時，其時間復雜度為0(nlog,n)；排序速度最慢時，其時間復雜度為。(n`)快速排序的平均時間復雜度為0(nlog2n)?？焖倥判虺诵枰粋€記錄的輔助空間來存放每次選取的基準記錄外，還需要一個?？臻g來實現(xiàn)遞歸?？键c25歸并排序歸并是將兩個或者多個有序表合并成一個有序表歸井排序規(guī)定待排序文獻已經(jīng)部分排序。歸并排序的基本思想是將這些已排過序的文獻進行合并，得到完全排序的文獻。假設初始序列具有n個記錄，則可當作是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或I的有序子序列，再兩兩歸并，如此反復，直到得到一個長度為n的有序序列為止。這種排序方法稱為二路歸并排序。歸并排序平均時間復雜度為0(n1092n)，輔助空間為0(n)。第3章操作系統(tǒng)3.1操作系統(tǒng)考點1操作系統(tǒng)概念1.操作系統(tǒng)基本概念操作系統(tǒng)是計算機系統(tǒng)中的一個系統(tǒng)軟件，是控制和管理計算機硬件和軟件資源，合理組織計算機工作流程及方便用戶的程序集合。操作系統(tǒng)有兩個重要的作用：一是管理系統(tǒng)中的各種資源；二是給用戶提供一個和諧的界面，方便用戶操作計算機。2.操作系統(tǒng)的基本特性操作系統(tǒng)涉及以下3個基本特性：(1)并發(fā)性。所謂并發(fā)性是指在計算機系統(tǒng)中同時存在多個程序，從宏觀上看，這些程序是同時向前推生的。(2)共享性。所謂資源共享性是指操作系統(tǒng)程序與多個用戶程序共享系統(tǒng)中的各種資源。這種共享是在操作系統(tǒng)控制下實現(xiàn)的。(3)隨機性。操作系統(tǒng)運營在一個隨機環(huán)境中。一個設備也許在任何時候向解決機發(fā)出中斷請求，系統(tǒng)無法知道運營著的程序會在什么時候做什么事情。考點2操作系統(tǒng)的功能操作系統(tǒng)的重要功能涉及以下幾個方面。(1)進程管理。重要是對解決機進行管理。(2)存儲管理。重要是對內(nèi)存的分派、保護和擴充。(3)設備管理。對所有輸人、輸出設備的管理。(4)文獻管理。重要涉及文獻的邏輯組織和物理組織，目錄的結(jié)構(gòu)和管理。(5)作業(yè)管理。為用戶提供一個和諧的環(huán)境，方便用戶組織自己的工作流程。考點3操作系統(tǒng)的類型隨著計算機硬件技術的不斷發(fā)展，出現(xiàn)了多種類型的操作系統(tǒng)：手工操作系統(tǒng)、批解決操作系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)及通用操作系統(tǒng)。隨著網(wǎng)絡技術的發(fā)展，相應地出現(xiàn)了網(wǎng)絡操作系統(tǒng)和分布式操作系統(tǒng)。下面將對重要的操作系統(tǒng)進行簡樸介紹。1.批解決操作系統(tǒng)批解決操作系統(tǒng)最大的特性就是用戶不直接操作計算機，而是將作業(yè)交給系統(tǒng)操作員，由操作人員將作業(yè)成批地輸人計算機，然后按某種調(diào)度策略，順序地執(zhí)行作業(yè)流中的每一個作業(yè)，以節(jié)省人工操作時間和提高機器的使用效率。批解決操作系統(tǒng)又可分為單道批解決系統(tǒng)和多道批解決系統(tǒng)。2.分時系統(tǒng)分時系統(tǒng)中的分時指多個用戶通過終端可同時使用一臺計算機。操作系統(tǒng)在接受用戶發(fā)出的請求后，按照時間片輪轉(zhuǎn)算法輪流分派給每個用戶一段CPU時間，進行各自的解決。但對于每個單獨的用戶都仿佛自己獨占了整個計算機系統(tǒng)分時系統(tǒng)重要有以下幾個方面的特點：(1)多路性若干個用戶同時使用一臺計算機，從微觀上看是各用戶輪流使用計算機；從宏觀上看是各用戶在并行工作。(2)交互性二用戶可根據(jù)系統(tǒng)對清求的響應結(jié)果，進一步向系統(tǒng)提出新的請求。(3)獨立性用戶之間可以互相獨立、互不十涉；系統(tǒng)保證各用戶程序運營的完整性，不會發(fā)生互相混淆或破壞等現(xiàn)象。(4)及時性系統(tǒng)對用戶的輸人及時做出啊應。分時系統(tǒng)性能的重要性能指標之一是響應時間，即從終端發(fā)出的命令到系統(tǒng)予以應答聽需的時間。3.實時系統(tǒng)實時系統(tǒng)是指可對外部事件做出及時洞應并在一定期間內(nèi)完畢對事件的解決的操作系統(tǒng)，其特點是及時響應和高可靠性實時系統(tǒng)可分為實時控制系統(tǒng)和實時信息解決系統(tǒng)兩大類。4.個人計算機操作系統(tǒng)個人計算機操作系統(tǒng)是指用于個人計算機上的操作系統(tǒng)，提供聯(lián)機交互功能：這規(guī)定系統(tǒng)有和諧的用戶接口和操作界面5.網(wǎng)絡操作系統(tǒng)網(wǎng)絡操作系統(tǒng)可通過通信設備將分散的具有獨立功能的多個計算機系統(tǒng)互聯(lián)起來，用于實現(xiàn)信息互換、資源共享、互操作和協(xié)作解決的系統(tǒng)各用戶間都要遵守一定的網(wǎng)絡協(xié)議來共享資源。6.分布式操作系統(tǒng)分布式操作系統(tǒng)可統(tǒng)?管理和調(diào)度整個系統(tǒng)上的資源以實現(xiàn)各計算機之間的資源共享和信息傳輸，對任務實行動態(tài)、合理的分派及并行的解決分布式系統(tǒng)各個計算機之間無主次之分，為用戶提供一個標準的接口和統(tǒng)一的界面，使用戶方便實現(xiàn)聽需要的操作?？键c4研究操作系統(tǒng)的方法研究操作系統(tǒng)可以從以下幾種不同的角度進行1.資源管理觀點從資源管理的觀點來看，操作系統(tǒng)的管理對象是計算機系統(tǒng)的資源，操作系統(tǒng)則是管理系統(tǒng)資源的程序集合通常，把操作系統(tǒng)分為解決機管理、存儲管理、設備管理、作業(yè)管理和文獻管理等5個重要部分，由這幾部分程序的協(xié)調(diào)、配合來完畢用戶的作業(yè)規(guī)定。2.進程觀點這種觀點把操作系統(tǒng)看作由若干個可以同時獨立進行的程序和一個對這些程序進行協(xié)調(diào)的核心所組成，這些同時運營的程序稱為進程，每個進程都可完畢某一特定的任務。3.虛機器觀點從服務用戶和機器功能擴充的觀點來看，操作系統(tǒng)為用戶使用計算機提供了許多服務功能和良好的工作環(huán)境?？键c5操作系統(tǒng)的硬件環(huán)境硬件是構(gòu)造操作系統(tǒng)的基礎，硬件對操作系統(tǒng)的構(gòu)造提供必要的支持。通常，操作系統(tǒng)所涉及的硬件環(huán)境重要涉及以下幾個方面。1.特權指今與解決機狀態(tài)(1)特權指令。只允許操作系統(tǒng)使用，而不允許一般用戶使用的指令。(2)非特權指令。特權指令之外的指令稱做非特權指令，非特權指令的執(zhí)行不影響其他用戶及系統(tǒng)。(3)CPU狀態(tài)。CPU交替執(zhí)行操作系統(tǒng)程序和用戶程序。在執(zhí)行不同程序時，根據(jù)運營程序為機器指是，的使用權限而將CPU置為不同的狀態(tài)CPU的狀態(tài)屬于程序狀態(tài)字PSW中的一位。2.中斷機制中斷機制是現(xiàn)代計算機系統(tǒng)中的基本設施之一，它在系統(tǒng)中起著通信聯(lián)絡的作用，以協(xié)調(diào)系統(tǒng)對各種外部事件的響應和解決。3.定期裝置為了實現(xiàn)系統(tǒng)管理和維護，硬件必須提供時鐘，即定期裝置硬件時鐘通常分為兩類：即絕對時鐘和相討時鐘。3.2進程管理考點6多道程序設計1.程序的順序執(zhí)行程序的順序執(zhí)行具有以下幾個特點：(1)順序性。程序所規(guī)定的動作在機器上嚴格地按順序執(zhí)行，每個動作的執(zhí)行都以前一個動作的結(jié)束為前提條件。(2)封閉性。程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響，即只有程序自身的動作才干改變程序的運營環(huán)境。(3)可再現(xiàn)性。順序執(zhí)行的最終結(jié)果與程序運營的速度無關。2.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化程序執(zhí)行環(huán)境具有以下3個特點：(1)獨立性。在多道環(huán)境下執(zhí)行的每道程序都是邏輯上獨立的，且執(zhí)行速度與其他程序無關，執(zhí)行的起止時間也是獨立的。(2)隨機性。在多道程序環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行的開始時間都是隨機的。(3)資源共享性。一般來說，多道環(huán)境下執(zhí)行程序的道數(shù)總是多于計算機系統(tǒng)中CPU的個數(shù)，單CPU也是如此。3.程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行是指為了充足運用系統(tǒng)資源，提高計算機的解決能力，在計算機系統(tǒng)中有兩個或兩個以上的程序同時執(zhí)行的狀態(tài)。參與并發(fā)執(zhí)行的程序稱為并發(fā)程序，并發(fā)程序執(zhí)行時的特點如下：(1)各并發(fā)程序在執(zhí)行期間互相制約。(2)程序與計算不是一一相應的關系。(3)不可再現(xiàn)性。4.多道程序系統(tǒng)一般情況下，計算機要同時解決多個具有獨立功能的程序來增強系統(tǒng)的解決能力和提高機器的解決效率。常采用并行操作技術來使系統(tǒng)的各種硬件資源做到并行工作，即在計算機中，所運營程序的道數(shù)(吞吐量)多。程序在運營時有如下3個特點：獨立性、隨機性和資源共享性?？键c7進程1.進程的概念進程是操作系統(tǒng)中最基本、最重要的概念。通常是指內(nèi)存區(qū)域中的一組指令序列的執(zhí)行過程，是程序中具有一定獨立功能的關于某個數(shù)據(jù)集合的一次運營活動，是系統(tǒng)進行資源分派和調(diào)度的一個獨立單位。2.進程的特性(1)并發(fā)性可以同其他進程一道向前推動，即一個進程的第一個動作可以在另一個進程的最后一個動作結(jié)束之前開始(2)動態(tài)性是指進程相應用程序的執(zhí)行過程，體現(xiàn)在兩方面：其一，進程動態(tài)產(chǎn)生，動態(tài)消亡；其二，在進程的生命周期內(nèi)，其狀態(tài)動態(tài)變化。(3)獨立性。一個進程是一個相對完整的調(diào)度單位，它可以獲得解決機并參與并發(fā)執(zhí)行。(4)交往性。一個進程在運營過程中也許與其他進程發(fā)生直接的或間接的互相作用。(5)異步性。每個進程按照各自獨立的、不可預知的速度向前推動。3.進程與程序的區(qū)別與聯(lián)系(1)進程是程序的執(zhí)行，是動態(tài)的；而程序是指令的集合，是靜態(tài)的。(2)進程的存在是有限的，從運營到結(jié)束，是暫時的；而程序則是永久存在的。(3)進程涉及程序、數(shù)據(jù)和進程控制塊(PCB)。(4)一個程序可以有多個進程，一個進程也可以包含多個程序。4.進程的狀態(tài)進程在其存在過程中，它們的狀態(tài)在不斷發(fā)生變化。系統(tǒng)中的不同事件均可以引起進程狀態(tài)的變化。一般情況下，一個進程可分為以下3種狀態(tài)：(1)就緒狀態(tài)。是指一個進程已經(jīng)具有運營條件，但由于沒有獲得CPU而不能運營所處的狀態(tài)。一旦把CPU分派給它，該進程就可運營二處在就緒狀態(tài)的進程可以是多個。(2)運營狀態(tài)。是指進程已獲得CP1,并且在CPU上執(zhí)行的狀態(tài)。(3)等待狀態(tài)。也稱阻塞狀態(tài)或封鎖狀態(tài)，是指進程由于等待某種事件發(fā)生而暫時不能運營的狀態(tài)。在一定的條件下，進程的狀態(tài)是可以互相轉(zhuǎn)換的。5.進程控制塊進程控制塊(ProcessContro1B1ock，簡稱PCB)是用來記錄進程狀態(tài)及其他相關信息的數(shù)據(jù)結(jié)構(gòu),PCB是進程存在的唯一標志，PCB存在則進程存在。系統(tǒng)創(chuàng)建進程時會產(chǎn)生一個PCB，撤消進程時，PCB也自動消失?？键c8進程控制進程控制也稱進程管理，對進程實行有效的管理，涉及進程的建立、撤消、進程阻塞及進程的喚醒等。進程控制是通過原語來實現(xiàn)的，用于進程控制的原語一般有：創(chuàng)建進程、撤消進程、掛起進程、激活進程、阻塞進程、喚醒進程及改變進程優(yōu)先級等。1.創(chuàng)建原語創(chuàng)建原語用于建立一個新的進程，其重要操作過程是先向系統(tǒng)申請一個空閑的PCB，然后根據(jù)父進程提供的參數(shù)，將相關信息填入，最后返回一個進程的內(nèi)部名。2.撤稍原語撤消原語是用于撤消一個已完畢任務的進程，以釋放它所占用的所有的內(nèi)部和外部資源。實質(zhì)上是撤消PCB，有兩種撤消策略，一種是只撤消1個具有特定標記符的進程，另一種是撤消該進程及其所有子孫進程。3.阻塞原語阻塞原語的作用是將進程由運營狀態(tài)變回阻塞狀態(tài)。具體過程是先中斷CPU，將CPU的當前狀態(tài)保存在PCB現(xiàn)場信息中，將進程的當前狀態(tài)置為等待，插人到等待隊列中去。4.喚酸原語喚醒原語的作用是將進程由阻塞狀態(tài)變?yōu)榫途w狀態(tài)，其操作過程是在等待隊列中找出某進程，將它的當前狀態(tài)置為就緒，然后將其從等待隊列中撤出并插人到就緒隊列中去。考點9進程的同步與互斥1.臨界資源和臨界區(qū)臨界資源是指一次只允許一個進程使用的資源：一個進程中訪問臨界資源的那段程序代碼稱為臨界區(qū)。它們不允許兩個及以上的進程同時訪問或修改。2.進程的同步進程的同步運營是指進程之間的一種直接的協(xié)同工作關系，這些進程通過互相合作來完畢一項任務。3.進程的互斤進程間一種間接的互相作用構(gòu)成進程互斥。進程互斥的目的就是使某一進程可以在某一時間內(nèi)獨占一些資源?考點10進程通信1.信號量和P,V操作解決進程的同步與互斥，既可用硬件實現(xiàn)，也可用軟件實現(xiàn)。(1)在系統(tǒng)中信號量(S)是一個整數(shù)。當S}--0時，表達可供并發(fā)進程使用的資源實體數(shù)；當S＜0時，代表等待使用臨界區(qū)的進程數(shù)。(2)只能通過P、V操作原語來改變P,V操作信號量的數(shù)值。P操作表達在當前進程申請的各種資源，V操作代表當前進程釋放所占用的資源。P操作和V操作都是低檔進程通信原語。(3)運用P、V操作可以解決并發(fā)進程間的互斥問題。(4)運用P、V操作也可以解決并發(fā)進程間的同步問題。2.高級通信機構(gòu)對進程間大量信息的互換常采用消息通信的方法，高級通信原語不僅可保證互相制約的進程的對的關系，同時還實現(xiàn)了進程之間的信息互換。該方法不僅能實現(xiàn)進程間的通信，并且能實現(xiàn)進程間數(shù)據(jù)的傳送。下面分別介紹3種高級進程通信。(1)消息緩沖通信。消息緩沖通信的基本思想：系統(tǒng)管理一組消息緩沖區(qū)，在每一個緩沖區(qū)可以存放一個信息。發(fā)送進程在發(fā)送消息前，在內(nèi)存中設立一個發(fā)送區(qū)，裝人欲發(fā)送的消息，在申請到一個消息緩沖區(qū)以后，將發(fā)送區(qū)里的消息發(fā)送到緩沖區(qū)中。(2)管道通信。管道通信實質(zhì)上是運用外存來進行數(shù)據(jù)通信，傳輸數(shù)據(jù)量大，但速度較慢。發(fā)送進程從管道的一端寫人數(shù)據(jù)，接受進程在需要的時候從管道的另一端讀出數(shù)據(jù)。(3)信箱通信。信箱通信指進程并不把消息直接發(fā)送給對方，而是將通信的消息以信件的方式放在信箱內(nèi)?？键c11進程調(diào)度進程調(diào)度即解決機調(diào)度在多道程序系統(tǒng)中，進程數(shù)目往往大于解決機數(shù)目，這會使進程互相爭奪解決機，必須按照一定的策略將C1't分派給這些進程中的某一進程1.進程調(diào)度的功能記錄系統(tǒng)中所有進程的狀態(tài)、優(yōu)先數(shù)及資源使用情況，CPU空閑時按一定算法擬定將CPU分派給哪個進程和分派多長時價。2.進程調(diào)度方式進程調(diào)度方式是指有優(yōu)先數(shù)更高的進程進人就緒隊列時，如何分派CPU，一般涉及剝奪方式和非剝奪方式兩種調(diào)度方式3.進程調(diào)度算法(1)先來先服務算法FCFS。該算法按照進程進入就緒隊列的先后順序來選擇二即每當進行進程調(diào)度時．總是把就緒隊列的隊首進程投人運營二(2)時間片輪轉(zhuǎn)算法。這重要是分時系統(tǒng)中使用的一種調(diào)度算法。其基本思想是：將CPU的解決時間劃提成一個個時間片，就緒隊列中的諸進程輪流運營一個時間片。當時間片結(jié)束時，就逼迫運營進程讓出CPU，該進程進人就緒隊列，等待下一次調(diào)度。同時，進程調(diào)度又去選擇就緒隊列中的另一個進程，分派給它一個時間片，以投人運營。影響時間片大小設立的重要因素有：系統(tǒng)響應時間、就緒進程數(shù)目(終端數(shù)目)和一計一算機解決能力。(3)最高優(yōu)先級算法進程調(diào)度每次將解決機分派給具有最高優(yōu)先級的就緒進程，進程的優(yōu)先級由進程優(yōu)先數(shù)決定進程優(yōu)先數(shù)的設立可以是靜態(tài)的，也可以是動態(tài)的。最高優(yōu)先數(shù)算法又可與不同的C1'U方式結(jié)合起來，形成可剝奪式最高優(yōu)先數(shù)算法和不可剝奪式最高優(yōu)先數(shù)算法?？键c12死鎖1.死鎖的概念死鎖是指在多道程序系統(tǒng)中，兩個或兩個以上的進程無限期地等待永遠不會發(fā)生的事件，得不到所需資源因而不能運營的狀態(tài)處在死鎖狀態(tài)的進程稱為死鎖進程。死鎖產(chǎn)生的因素：一是系統(tǒng)資源局限性；二是多道程序運營時，進程的推動順序不合理。2.產(chǎn)生死鎖的必要條件(1)互斥條件。進程互斥使用資源，任一時刻一個資源只為一個進程獨占，其他進程若請求一個已被占用的資源，只能等占用者釋放后才干使用(2)不可剝奪條件(不可搶rt1-)。進程所獲得的資源在未使用完畢之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放(3)部分分派(占有等待)。進程每次申請它所需要的一部分資源，在申請新的資源的同時，繼續(xù)占用已分派到的資源。(4)循環(huán)等待：存在一個進程環(huán)路，環(huán)路中每一個進程已獲得的資源同時被下一個進程所請求。3.資源分派圖死鎖問題可用一個有向圖來表達。資源分派圖就是描述進程、資源及它們之間關系的有向圖。當進程請求資源時，系統(tǒng)檢查并發(fā)進程組是否構(gòu)成資源的請求環(huán)路。存在環(huán)路，也許存在死鎖；不存在環(huán)路，一定沒有死鎖。4.死鎖防止只要破壞死鎖產(chǎn)生的4個必要條件之一，就可有效避免死鎖的產(chǎn)生，重要有以下幾種方法：(1)破壞互斥條件(2)破壞不可剝奪條件。(3)破壞部分分派條件二(4)破壞循環(huán)等待條件5.死鎖解除當發(fā)現(xiàn)死鎖后，可采用以下兩種方法來解除死鎖：(1)資源剝奪法。從一些進程那里強行剝奪足夠數(shù)量的資源分派給死鎖進程，以解除死鎖狀態(tài)(2)撤消進程法。按照某種策略逐個地撤消死鎖進程，直到獲得為解除死鎖所需要的足夠使用的資源為按照什么原則撤消進程，實用而又簡便的方法就是撤消那些代價最小的進程，或者撤消進程的數(shù)量最少。考點13線程1.線程的概念線程是進程中的一個實體，是CPU調(diào)度和分派的基本單位2.線程的屬性(1)每個線程有一個唯一的標記符和一張線程描述表。(2)不同的線程可以執(zhí)行相同的程序。(3)