【正文】 在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有明顯的層次關(guān)系，每一層中的數(shù)據(jù)元素只和上一層中的一個元素(即雙親結(jié)點)相關(guān)?！　、坌D(zhuǎn):將虛線及有關(guān)實線逆時鐘旋轉(zhuǎn)約45度，并將幾個結(jié)點按層次排列?！　?3)層次遍歷　?、偃魳浞强眨L問根結(jié)點。數(shù)據(jù)域用于存儲樹上一個結(jié)點中的數(shù)據(jù)元素。嚴(yán)格地說，無論選擇上述哪種定義，得到的都是鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為在這兩種定義之下，各存儲結(jié)點之間的聯(lián)結(jié)是通過“指針”完成的，而且這些指針反映了結(jié)點之間的邏輯關(guān)系。因此，通過指向雙親的指針而將樹中所有結(jié)點組織在一起形成一種存儲結(jié)構(gòu)是十分簡法的。兄弟域———用于存放指向本結(jié)點下一個兄弟的指針。一個孩子鏈表是一個帶頭結(jié)點的單鏈表，單鏈表的頭結(jié)點含兩個域:數(shù)據(jù)域和指針域。最先(最后、在中間)執(zhí)行此子任務(wù)，則為先根(后根、中根)遍歷。　?、巯雀闅v右子樹。③遍歷右子樹(即依次訪問右子樹上的全部結(jié)點)?！　　　∮捎诙鏄涞幕具\算在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)比較簡單，無需詳加討論?！　《鏄涞逆?zhǔn)酱鎯Y(jié)構(gòu)操作方便，表達(dá)簡明(二叉樹的邏輯關(guān)系———結(jié)點間的父子關(guān)系———在二叉鏈表和三叉鏈表中被直接表達(dá)成對應(yīng)存儲結(jié)點之間的指針)，因而成為二叉樹最常用的存儲結(jié)構(gòu)。類似地，rchild域稱為右孩子指針域，用于存放指向本結(jié)點右孩子的指針(簡稱右指針)。另外，二叉樹上任一結(jié)點的度定義為該結(jié)點的孩子數(shù)(即非空子樹數(shù))。　?、芙銫REATE(X，T 1 ，…，T k )k≥1，加工型運算，其作用是建立一棵以X為根，以T 1 ，…，T k 為第1，…k棵子樹的樹。所謂“層次”是指樹上所有結(jié)點可以按它們的層數(shù)劃分不同的“層次”。一棵樹中所有結(jié)點的度的最大值稱為該樹的度。　　　　樹是一類重要的樹形結(jié)構(gòu)，其定義如下:樹是n(n0)個結(jié)點的有窮集合，滿足:　　(1)有且僅有一個稱為根的結(jié)點。　　對于數(shù)組的運算，主要有檢索或存取數(shù)組中某個元素?！　、趀mpty(Q)測試隊列是否為空隊列。　?、辮op(s) 刪除棧頂元素。允許插入和刪除的一端稱為棧頂，另一端稱為棧底?！　“言瓉淼趎1個結(jié)點至第i個結(jié)點依次往后移一個數(shù)組元素位置。每個鏈表還要有一個指向鏈表的第一個表元，鏈表的最末一個表元的后繼指針值為空。用數(shù)組存儲線性表的最大優(yōu)點是能直接訪問線性表中的任一結(jié)點?！　【€性表分析?！　≡诰€性表中查找具有給定鍵值的表元?！　《?、線性表　　(1)線性表及其基本操作　　線性表是n≥0個元素的一個有限序列:(a 1 ，a 2 ，a 3 ，…，a n 1 ，a n ，)表中元素的個數(shù)n稱為表的長度，長度n=0的表稱為空表。一個程序不一定滿足有窮性，操作系統(tǒng)就是如此，只要整個系統(tǒng)不被破壞，操作系統(tǒng)就永遠(yuǎn)不會停止，所以操作系統(tǒng)程序不是一個算法。常用的運算有:查找、插入、刪除、更新、排序等。它們是:　?、夙樞虼鎯Ψ椒?該方法是把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元內(nèi)，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。數(shù)據(jù)對象中數(shù)據(jù)元素之間的聯(lián)系需要在對數(shù)據(jù)進(jìn)行存儲和加工中反映出來，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機(jī)中的存儲方式、以及在這些數(shù)據(jù)上定義的運算的集合。樹和二叉樹的定義，互相轉(zhuǎn)換，二叉樹的存儲，二叉樹的周游。如從鍵盤(輸入設(shè)備)向磁盤中輸入一個信息，此信息必須通過總線先輸入到主存中的特定區(qū)域中，通過程序控制將信息存放到主存中對應(yīng)于磁盤輸入/輸出的一個特定區(qū)域內(nèi)，然后將此信息轉(zhuǎn)存到磁盤上?！　楸ＷC寫入時兩者內(nèi)容一致的方法有:①將內(nèi)容同時寫入主存和Cache。指令地址的分布又是連續(xù)的，加上循環(huán)程序和子程序段的重復(fù)執(zhí)行，對這些地址的訪問自然具有時間上集中分布的傾向。因此，可以認(rèn)為組相聯(lián)映象是全相聯(lián)映象和直接映象方法的結(jié)合?！　、偃嗦?lián)映象　　任一邏輯頁能映象到實際主存的任意頁面位置稱為全相聯(lián)映象，通常利用頁表法進(jìn)行地址間的變換。　　(2)虛擬存儲的工作原理　　虛擬存儲技術(shù)，實際上是將編寫程序時所用的虛擬地址(邏輯地址)轉(zhuǎn)換成較小的物理地址。如果不在主存中，通過輔助的軟、硬件將虛擬地址對應(yīng)的內(nèi)容調(diào)入主存中，然后再進(jìn)行訪問。光盤信息的保存時間也比磁盤的長。激光器發(fā)出激光經(jīng)光學(xué)線路至聚焦透鏡射向光盤表面，表面的凹凸不平造成反射光的變化，利用數(shù)據(jù)光檢測器將這些變化轉(zhuǎn)換為數(shù)據(jù)“0”和“1”的電信號傳輸?shù)綌?shù)據(jù)輸出端，整個讀取工作完成。計算一個磁盤容量的公式是:　　磁盤存儲容量=盤面數(shù)每盤面磁道數(shù)每磁道扇區(qū)數(shù)每扇區(qū)存儲容量　　(2)光盤存儲器　　所謂光盤(CD)是利用光學(xué)原理讀寫信息的存儲器。根據(jù)盤片的基本組成材料將磁盤分為硬盤和軟盤兩種?！　　　⊥獯鎯ζ魇侵改切┎荒鼙籆PU直接訪問的，讀取速度較內(nèi)存慢，容量比內(nèi)存大，通常用來存放不常用的程序和數(shù)據(jù)的存儲器。其特點是可以根據(jù)用戶的要求用工具擦去RAM中原有的存儲內(nèi)容，重新寫入新的編碼。因制造工藝和功能不同，一般分為普通ROM、可編程ROM(PROM)、可擦寫可編程ROM(EPROM)和電可擦寫可編程ROM(EEPROM)等?！　∪绻O(shè)計的存儲器容量有x字，字長為y，而采用的芯片為NM位。但無論雙極型或MOS型存儲器，其保持的信息將隨電源的撤消而消失?！　〔煌愋偷拇鎯ζ鞲鶕?jù)其特點有不同的讀寫操作控制電路、控制機(jī)構(gòu)、讀寫電路及地址譯碼器，但它們的基本操作原理大同小異。將后5位輸入到Y(jié)地址譯碼器中譯出Y0 到Y(jié)31 譯碼線，分別選擇0～31列。由于存儲體中存儲單元的每個二進(jìn)制位必須并行工作，因此將存儲單元按其地址的順序組成存儲陣列?！　、芸刂齐娐?接收CPU傳來的控制命令，經(jīng)過控制電路一系列的處理，產(chǎn)生一組時序信號控制存儲器的操作?！　“恕⒋鎯ζ鳌　　　?1)存儲器的基本組成部分　　主存儲器由存儲體、地址譯碼電路、驅(qū)動電路、讀寫電路和控制電路等組成?！　?7)操作控制器　　操作控制器的功能，就是根據(jù)指令操作碼和時序信號，產(chǎn)生各種操作控制信號，以便正確地建立數(shù)據(jù)通路，從而完成取指令和執(zhí)行指令的控制。由于在內(nèi)存和CPU之間存在著操作速度上的差別，所以必須使用地址寄存器來保持地址信息，直到內(nèi)存讀/寫操作完成為止。　　(2)指令寄存器(IR)指令寄存器用來保存當(dāng)前正在執(zhí)行的一條指令。①單總線結(jié)構(gòu)的運算器②雙總線結(jié)構(gòu)的運算器③三總線結(jié)構(gòu)的運算器　　七、控制器　　　　中央處理器(CPU)由兩個主要部分———控制器及運算器組成。內(nèi)部總線是指CPU內(nèi)各部件的連線，而外部總線是指系統(tǒng)總線，即CPU與存儲器、I/O系統(tǒng)之間的連線。標(biāo)識符是“1”，則是漢字內(nèi)部碼。漢字:　　(1)漢字字音編碼　　(2)漢字字形編碼　　(3)漢字音形編碼　　(4)電報碼　　(5)整字編碼為了能在不同的漢字系統(tǒng)之間交換信息、高效率高質(zhì)量共享漢字信息，近年來國家推出了一系列有關(guān)中文信息處理的標(biāo)準(zhǔn)。ASCII碼選擇了四類共128種常用的字符:①數(shù)字0～9。它拼接在有效信息后面組成CRC碼。CRC碼到達(dá)接收方時，接收方的設(shè)備一方面接收CRC碼，一方面用同樣的生成多項式相除，如果正好除盡，表示無信息差錯，接收方去掉CRC碼后面r位校驗，收下k位有效信息。0～9的8421碼與通常的二進(jìn)制一樣進(jìn)位，十分簡單，當(dāng)計數(shù)超過9時，需要采取辦法自動向十進(jìn)制高位進(jìn)一，即要進(jìn)行“十進(jìn)制調(diào)整”才能得到正確結(jié)果?！　《c數(shù)表示方法簡單直觀，不過定點數(shù)表示數(shù)的范圍小，不易選擇合適的比例因子，運算過程容易產(chǎn)生溢出。應(yīng)該注意，不存在128的8位原碼和反碼形式。　　(3)補(bǔ)碼表示法(plement)　　設(shè)計補(bǔ)碼表示法的目的是:①使符號位能和有效數(shù)值部分一起參加數(shù)值運算從而簡化運算規(guī)則，節(jié)省運算時間。實用的數(shù)據(jù)有正數(shù)和負(fù)數(shù)，因為計算機(jī)只能表示0、1兩種狀態(tài)，數(shù)據(jù)的正號“+”或負(fù)號“”，在機(jī)器里就用一位二進(jìn)制的0或1來區(qū)別。需要指出的是并不是所有十進(jìn)制小數(shù)都能轉(zhuǎn)換成有限位的二進(jìn)制小數(shù)并出現(xiàn)乘積的小數(shù)部分0的情況，有時整個換算過程無限進(jìn)行下去?！　?3)計算機(jī)中二進(jìn)制數(shù)的0、1數(shù)碼與邏輯代數(shù)變量值0與1吻合，所以二進(jìn)制同時可以使計算機(jī)方便地進(jìn)行邏輯運算。從硬件來說，除計算機(jī)作為網(wǎng)絡(luò)的結(jié)點以外，還有如服務(wù)器(也可用一臺計算機(jī))，網(wǎng)絡(luò)適配器，終端控制器以及網(wǎng)絡(luò)連接器等硬件設(shè)備?！　?3)實時系統(tǒng)?！　?3)中斷處理。軟件分為系統(tǒng)軟件和應(yīng)用軟件。隨機(jī)存儲器是按地址存取數(shù)據(jù)的，若地址總線共有20條地址線(A 0 ～A 19 )，即有20個二進(jìn)制位，可形成2 20 =1048576個地址(1兆地址)。計算機(jī)的應(yīng)用如下:　　(1)在科學(xué)計算中的應(yīng)用　　(2)在實時控制中的應(yīng)用　　(3)在數(shù)據(jù)處理中的應(yīng)用　　(4)計算機(jī)在輔助設(shè)計和輔助制造(CAD/CAM)中的應(yīng)用　　(5)辦公自動化系統(tǒng)中的應(yīng)用　　三、計算機(jī)硬件結(jié)構(gòu)　　實際應(yīng)用的計算機(jī)系統(tǒng)是由計算機(jī)硬件系統(tǒng)、軟件系統(tǒng)以及通信網(wǎng)絡(luò)系統(tǒng)組成的一個整體系統(tǒng)?！　〉诙卫顺睘榭蛻魴C(jī)/服務(wù)器(Client/Server)的時期，這時期出現(xiàn)了小型機(jī)、微型機(jī)和局域網(wǎng)。最早的應(yīng)用是軍事上的需要，如炮彈彈道計算，核武器的設(shè)計等?！　?0世紀(jì)70年代初期到70年代后期(1972～1978)為大規(guī)模集成電路(LSI)計算機(jī)時代。1969年CDC公司研制的DCD7600平均速度達(dá)到每秒千萬次浮點運算。除了ENIAC以外，1945年左右，馮?諾依曼等人在研制EDVAC(electronic discrete variable puter)時，提出了存儲程序(storedprogram)概念，奠定了以后計算機(jī)發(fā)展的基石。全國計算機(jī)等級考試四級復(fù)習(xí)綱要　　第一章考試要點　　一、計算機(jī)的發(fā)展　　自從1946年2月現(xiàn)代電子計算機(jī)的鼻祖ENIAC(electronic numerical integrator and puter)在美國賓夕法尼亞大學(xué)問世以后，短短50年里，計算機(jī)技術(shù)經(jīng)歷了巨大的變革。IBM公司1954年12月推出的IBM650是第一代計算機(jī)的代表?！　?0世紀(jì)60年代中期到70年代初期(1965～1972)為集成電路計算機(jī)時代。20世紀(jì)70年代初半導(dǎo)體存儲器的出現(xiàn)，迅速取代了磁芯存儲器，計算機(jī)的存儲器向大容量、高速度的方向飛速發(fā)展。其次是廣泛地用于科學(xué)計算，工程設(shè)計計算。其特點是多用戶分時處理。計算機(jī)硬件系統(tǒng)是指構(gòu)成計算機(jī)的所有實體部件的集合，通常這些部件由電路(電子元件)、機(jī)械等物理部件組成，它們都是看得見摸得著的，故通常稱為“硬件”?！　　　】刂破饔扇蟛考M成，它們是指令部件、時序部件和操作控制部件?！　∠到y(tǒng)軟件包括計算機(jī)操作系統(tǒng)(Operation System)、計算機(jī)的各種管理程序、監(jiān)控程序、調(diào)試程序、編輯程序以及各種語言的編譯或解釋程序等?！　?4)I/O處理?！　〔僮飨到y(tǒng)的管理功能主要內(nèi)容:　　(1)處理機(jī)管理。從軟件來說，有網(wǎng)絡(luò)操作系統(tǒng)，網(wǎng)絡(luò)通信及協(xié)議軟件，網(wǎng)絡(luò)數(shù)據(jù)庫管理系統(tǒng)等?！　?4)二進(jìn)制數(shù)和十進(jìn)制數(shù)之間的關(guān)系亦不復(fù)雜。此時可以根據(jù)要求并考慮計算機(jī)字長，取定長度的位數(shù)后四舍五入，這時得到的二進(jìn)制數(shù)是原十進(jìn)制數(shù)的近似值。通常這個符號放在二進(jìn)制數(shù)的最高位，稱符號位，以0代表符號“+”，以1代表符號“”，這樣正負(fù)符號就被數(shù)值化了。②使減法運算轉(zhuǎn)化成加法運算，從而進(jìn)一步簡化計算機(jī)中運算器的線路設(shè)計?！　「鶕?jù)互補(bǔ)的概念，一個補(bǔ)碼機(jī)器數(shù)再求一次補(bǔ)就得到機(jī)器數(shù)的原碼了?！　?2)浮點數(shù)(floatingpoint number)　　計算機(jī)采用浮點數(shù)來表示數(shù)值，它與科學(xué)計算法相似，把任意一個二進(jìn)制數(shù)通過移動小數(shù)點位置表示成階碼和尾數(shù)兩部分:N=2 E S　　其中:E———N的階碼(exponent)，是有符號的整數(shù)?！　　　∮捎谄骷|(zhì)量不可靠、線路工藝不過關(guān)、遠(yuǎn)距離傳送帶來的干擾或受來自電源、空間磁場影響等因素，使得信息在存取、傳送和計算過程中難免會發(fā)生諸如“1”誤變?yōu)椤?”的錯誤，計算機(jī)一旦出錯，要能及時檢測并糾正錯誤，其中一種方法是對數(shù)據(jù)信息擴(kuò)充，加入新的代碼，它與原數(shù)據(jù)信息一起按某種規(guī)律編碼后具有發(fā)現(xiàn)錯誤的能力，有的甚至能指出錯誤所在的準(zhǔn)確位置使機(jī)器自動糾正，能起這種作用的編碼叫“校驗碼”(check code)。當(dāng)不能除盡時，說明有信息的狀態(tài)位發(fā)生了轉(zhuǎn)變，即出錯了。因為校驗位擴(kuò)充了傳送部分的代碼，所以這是一種基于“冗余校驗”的思想的校驗辦法。②字母。比如1981年我國制定推行的GB231280國家標(biāo)準(zhǔn)信息交換用流字編碼字符集(基本集)———簡稱國標(biāo)碼，以及若干輔助集?！　　　≌Z音產(chǎn)生機(jī)理的研究表明，每一種語言的語音都有自己特定的音素特征，語音是不同頻率振動的結(jié)果。　　按總線的邏輯結(jié)構(gòu)來說，總線可分為單向傳送總線和雙向傳送總線。其中程序計數(shù)器、指令寄存器、指令譯碼器、時序產(chǎn)生器和操作控制器等組成了控制器。指令劃分為操作碼和地址碼字段，它們由二進(jìn)制數(shù)字組成?！　?5)累加寄存器(AC)　　累加寄存器AC通常簡稱為累加器。　　根據(jù)設(shè)計方法不同，操作控制器可分為組合邏輯型、存儲邏輯型、組合邏輯與存儲邏輯結(jié)合型三種。主存儲器的主要功能是:①存儲體:是信息存儲的集合體，由某種存儲介質(zhì)按一定結(jié)構(gòu)組成的存儲單元的集合?！　≡诖鎯ζ鞯慕M成中，存儲體是核心，其余部分是存儲的外圍線路。　　(3)存儲器的地址譯碼系統(tǒng)　　CPU要訪問存儲單元的地址由地址總線輸入到地址寄存器中。X向譯碼器和Y向譯碼器引出的地址線都是2 5 =32條?！　　⒔M織及其應(yīng)用　　半導(dǎo)體存儲器有體積小、存取速度快、生產(chǎn)制造易于自動化等特點，其性能價格比遠(yuǎn)遠(yuǎn)高于磁芯存儲器，因而得到廣泛的應(yīng)用?！　?1)RAM的組織　　半導(dǎo)體RAM芯片是在半導(dǎo)體技術(shù)和集成電路工藝支持下的產(chǎn)物。要組成滿足字長要求的存儲器所需芯片數(shù)為:y/M。　　(1)ROM的工作原理　　一般的ROM使用掩模式ROM。擦除和寫入可以根據(jù)用戶的要求用工具擦去RAM中原有的存儲內(nèi)容，重新寫入新的編碼。磁帶、磁盤存儲器是現(xiàn)今最常用的外存，因其利用磁表面介質(zhì)存儲數(shù)據(jù)，通常也稱為磁表面存儲器。所謂硬盤是指由金屬材料制成一定厚度的盤片基體，這些盤片一般