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