【正文】 基本特征。 (8)記帳。 (1)指令部件指令部件包括程序計(jì)數(shù)器 PC，指令寄存器 IR和指令譯碼器 ID。第三個(gè)浪潮是 70～ 80年代的微型計(jì)算機(jī) PC(Personal Computer)的出現(xiàn)。由于采用了集成電路，使得計(jì)算機(jī)的制造成本迅速下降；同時(shí)因?yàn)檫壿嫼痛鎯?chǔ)器件集成化的封裝，大大提高了運(yùn)行速度，功耗也隨之下降；集成電路的使用，使得計(jì)算機(jī)內(nèi)各部分的互聯(lián)更加簡單和可靠，計(jì)算機(jī)的體積也進(jìn)一步縮小。計(jì)算機(jī)的元器件主要由電子管 (vacuum tube)組成。 (三 )操作系統(tǒng) 、主要功能和分類。 ，具有數(shù)據(jù)庫設(shè)計(jì)能力，了解數(shù)據(jù)庫技術(shù)發(fā)展。 (五 )數(shù)據(jù)庫設(shè)計(jì)和數(shù)據(jù)庫應(yīng)用 、內(nèi)容和方法。從 20世紀(jì) 50年代后期到 60年代中期 (1958～ 1964)為晶體管計(jì)算機(jī)時(shí)期。同時(shí)系統(tǒng)結(jié)構(gòu)的特點(diǎn)對計(jì)算機(jī)的性能也有巨大的影響 (中斷系統(tǒng)、 Cache存儲(chǔ)器、流水線技術(shù)等等 )。計(jì)算機(jī)硬件結(jié)構(gòu)也可以稱為馮應(yīng)用軟件是為解決各種實(shí)際問題而設(shè)計(jì)的程序。 用的應(yīng)用軟件。適應(yīng)大容量與突發(fā)性通信的要求； 重要方面。線性表就是一個(gè)典型的線性結(jié)構(gòu)。 ③可行性算法中的所有待實(shí)現(xiàn)的運(yùn)算必須在原則上能夠由人使用筆和紙?jiān)谧鲇懈F次運(yùn)算后完成。下面所列的是其中一些常用的運(yùn)算。 ①線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)是最簡單的存儲(chǔ)方式。檢查插入要求的有關(guān)參數(shù)的合理性； ⑥ pop(s)刪除棧頂元素。 (2)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)由于對數(shù)組一般不作插入和刪除運(yùn)算，因此，一旦數(shù)組被建立，則結(jié)構(gòu)中的元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。一棵樹上的任何結(jié)點(diǎn) (不包括根本身 )稱為根的子孫。相應(yīng)地，二叉樹上任一結(jié)點(diǎn)左、右子樹的根分別稱為該結(jié)點(diǎn)的左孩子和右孩子。由性質(zhì) 2知，滿二叉樹上各層的結(jié)點(diǎn)數(shù)已達(dá)到了二叉樹可以容納的最大值。若二叉樹為空，則 root=NULL。由定義可知，一棵二叉樹由三部分組成：根、左子樹和右子樹。其中，數(shù)據(jù)域用于存儲(chǔ)結(jié)點(diǎn) X中的數(shù)據(jù)元素；指針域用于存儲(chǔ)指向該單鏈表中第一個(gè)表結(jié)點(diǎn) (首結(jié)點(diǎn) )的指針。第二種選擇是將 “指針 ”域定義為整型、子界型等型。 二叉樹還原為一般樹的步驟是： ①加線：若某結(jié)點(diǎn)是一父結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)的右孩子以及沿著右鏈搜索到的所有右孩子結(jié)點(diǎn)都用線與那個(gè)父結(jié)點(diǎn)連接起來； ②抹線：抹去原二叉樹中所有結(jié)點(diǎn)與其右孩子的連線； ③旋轉(zhuǎn)：將虛線及有關(guān)實(shí)線逆時(shí)針旋轉(zhuǎn)約 45度，并將幾個(gè)結(jié)點(diǎn)按層次排列 ： ①將森林中的每棵樹轉(zhuǎn)換為二叉樹； ②森林中第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換后二叉樹的根結(jié)點(diǎn)，依次將后一棵樹作為前一棵樹根結(jié)點(diǎn)的右子樹。所需要的比較次數(shù)為 nlog2n，移動(dòng)次數(shù)為 n。為加快查找，還要建立一個(gè)索引表，表中給出每一塊的最大關(guān)鍵值和指向塊內(nèi)第一個(gè)結(jié)點(diǎn)的指針。操作系統(tǒng)控制和管理所有的系統(tǒng)硬件 (如處理器、存儲(chǔ)器、各種設(shè)備 )，也控制和管理系統(tǒng)中所有的軟件，操作系統(tǒng)為計(jì)算機(jī)使用者提供了一種良好的操作環(huán)境，也為各種應(yīng)用系統(tǒng)提供了基本的支持環(huán)境。分布式操作系統(tǒng)負(fù)責(zé)全系統(tǒng)的資源分配和調(diào)度，為用戶提供統(tǒng)一的界面。為了發(fā)揮設(shè)備和處理機(jī)的并行工作能力，常常采用緩沖技術(shù)和虛擬技術(shù)。 異常迅速，導(dǎo)致了控制技術(shù)的發(fā)展，設(shè)備控制的基本技術(shù)是中斷。如果是不可剝奪的，它重新得到處理器，否則，可能被別的進(jìn)程 (如優(yōu)先級(jí)更高 )奪得處理器。 (1)互斥多道系統(tǒng)中，各進(jìn)程 可以共享各類資源，但有些資源卻一次只能供一個(gè)進(jìn)程使用。 P(mutex)。保護(hù)機(jī)制應(yīng)包含在主存尋址硬件中。從靜態(tài)的觀點(diǎn)看，進(jìn)程由程序、數(shù)據(jù)和進(jìn)程控制塊組成；從動(dòng)態(tài)的觀點(diǎn)看，是計(jì)算機(jī)狀態(tài)的一個(gè)有序集合。一般阻塞隊(duì)列的個(gè)數(shù)取決于等待事件 (原因 )的個(gè)數(shù)。在有些進(jìn)程 (如高優(yōu)先級(jí)進(jìn)程 )需 要快速服務(wù)的系統(tǒng)中，剝奪調(diào)度是非常有用的。他們都涉及現(xiàn)場隊(duì)列管理等。 (2)特權(quán)指令為使各并發(fā)進(jìn)程不相互干擾，系統(tǒng)的部分指令集應(yīng)保留僅供操作系統(tǒng)使用，這些指令稱為特權(quán)指令，如允許與禁止中斷，執(zhí)行輸入輸出操作等。 (1)互斥為了保護(hù)共享資源 (如公共變量等 )，使它們不被多個(gè)進(jìn)程同時(shí)訪問，就要阻止這些進(jìn)程同時(shí)執(zhí)行訪問這些資源的代碼段，這些代碼段稱為臨界區(qū)，這些資源稱為臨界資源。因此，進(jìn)程之間需要某種形式的通信。所有的中斷向量構(gòu)成一個(gè)中斷向量表，它們通常存放在一個(gè)專門的存儲(chǔ)區(qū)域中，這個(gè)區(qū)域的地址可以是固定的；相應(yīng)的處理程序的入口地址通常是在系統(tǒng)引導(dǎo)過程中，通過對系統(tǒng)配置的檢測，得到系統(tǒng)中設(shè)備配置的情況，在操作系統(tǒng)裝入過程中，填寫中斷向量表中的內(nèi)容。程序的并發(fā)執(zhí)行，發(fā)揮了處理器與輸入輸出設(shè)備并發(fā)工作的能力，使系統(tǒng)的效率提高。 (2)存儲(chǔ)管理計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器 (一般稱為主存或內(nèi)存 )是運(yùn)行程序、存放工作數(shù)據(jù)的，存儲(chǔ)管理的工作主要是對主存儲(chǔ)器進(jìn)行分配、擴(kuò)充和保護(hù)。雙重散列技術(shù)是對線性探測法的改進(jìn)。 。第一趟掃描的比較次數(shù)是 n1，第二趟掃描的比較次數(shù)是 n2……，總的比較次數(shù)是 (n1)+(n2)+……+1=n(n1)/2。 (2)后根遍歷若樹非空，則 ①依次先根遍歷根的各個(gè)子樹 T1，…， Tm。在雙親表示法下，每個(gè)存儲(chǔ)結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域 ——用于存儲(chǔ)樹上結(jié)點(diǎn)中的數(shù)據(jù)元素； “指針 ”域 ——用于指示本結(jié)點(diǎn)之雙親所在的存儲(chǔ)結(jié)點(diǎn)。下面介紹樹的三種常用存儲(chǔ)結(jié)構(gòu) (1)孩子鏈表表示法孩子鏈表表示法是樹的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。下面研究二叉樹的一種較為復(fù)雜的重要運(yùn)算 ——遍歷及其在二叉鏈表上的實(shí)現(xiàn)。二叉鏈表中的所有存儲(chǔ)結(jié)點(diǎn)通過它們的左、右指針的鏈接而形成一個(gè)整體。性質(zhì) 2深度為 k(k≥ 1)的二叉樹至多有 2k1個(gè)結(jié)點(diǎn)。 ⑤剪枝 DELETE(T， X， i)，加工型運(yùn)算，其作用是刪除樹 T上結(jié)點(diǎn) X的第 i棵子樹；若 T無第 i棵子樹，則為空操作。度為 0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)，度大于 0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支點(diǎn)。 【考點(diǎn)三】 數(shù)組線性表 (包括棧和隊(duì)列 )都是線性結(jié)構(gòu)，結(jié)構(gòu)中的每個(gè)元素只是無結(jié)構(gòu)的數(shù)據(jù)元素。棧的基本操作有： ① create(s)建立一個(gè)空棧 s ② empty(s)測試棧是否為空棧。 (3)線性表上的查找線性表上的查找運(yùn)算是指在線性表中查找某個(gè)鏈值的結(jié)點(diǎn)。線性表合并；表元素又稱為結(jié)點(diǎn)，線性表的一個(gè)重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。常用的運(yùn)算有：查找、插入、刪除、更新、排序等。數(shù)據(jù)對象中數(shù)據(jù)元素之間的聯(lián)系需要在對數(shù)據(jù)進(jìn)行存儲(chǔ)和加工中反映出來，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式、以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。一般人們將加密前的信息稱為明文，而將加密后的稱為密文，因此加密的目的就是將明文變?yōu)槊芪摹? 操作系統(tǒng)的管理功能主要內(nèi)容 (1)處理機(jī)管理。磁性設(shè)備閱讀機(jī)、光學(xué)閱讀機(jī)等也可作為輸入設(shè)備。 【考點(diǎn)二】 計(jì)算機(jī)的分類及其應(yīng)用計(jì)算機(jī)分類的方法大致可分如下幾種： 、模擬計(jì)算機(jī)以及數(shù)字混合計(jì)算機(jī) 。 20世紀(jì) 70年代初半導(dǎo)體存儲(chǔ)器的出現(xiàn)，迅速取代了磁芯存儲(chǔ)器，計(jì)算機(jī)的存儲(chǔ)器向大容量、高速度的方向飛速發(fā)展。這一階段，計(jì)算機(jī)主要用于軍事、國防等尖端技術(shù)領(lǐng)域。 (四 )數(shù)據(jù)庫系統(tǒng)基本原理 ，數(shù)據(jù)庫系統(tǒng)的構(gòu)成。三級(jí)數(shù)據(jù)庫技術(shù)等級(jí)考試大綱 基本要求 、計(jì)算機(jī)網(wǎng)絡(luò)的基本知識(shí)和應(yīng)用知識(shí)、信息安全的基本概念 。 。除了 ENIAC以外， 1945年左右，馮存儲(chǔ)器芯片從 1kbit， 4kbit， 16kbit， 64kbit， 256kbit， 1Mbit， 4Mbit發(fā)展到16Mbit(1992年 )。 、大型機(jī)、中型機(jī)、小型機(jī)、微型機(jī)等。 【考點(diǎn)四】 計(jì)算機(jī)軟件的功能及分類所謂軟件是指為運(yùn)行、維護(hù)、管理、應(yīng)用計(jì)算機(jī)所編制的所有程序的總和。 (2)存儲(chǔ)管理。根據(jù)網(wǎng)絡(luò)的覆蓋范圍與規(guī)模 (scale)分類。開放的協(xié)議標(biāo)準(zhǔn)，獨(dú)立于特定的計(jì)算機(jī)硬件與操作系統(tǒng)。而反過來將密文變?yōu)槊魑牡倪^程則稱為解密。 (1)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。顯然，對數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)方法只有在確定了存儲(chǔ)結(jié)構(gòu)之后才能加以考慮。若 n≥ 1，則 a1，為第一個(gè)元素， an為最后一個(gè)元素。線性表排序；根據(jù)線性表的存儲(chǔ)形式和線性 表本身的性質(zhì)差異，有多種查找算法，如：順序查找、二分法查找、分塊查找、散列查找等。 ③ full(s)測試棧是否滿。我們對線性表作進(jìn)一步的推廣，使結(jié)構(gòu)中的元素本身也可以是具有某種結(jié)構(gòu) (如向量 )的數(shù)據(jù)，從而引出了數(shù)組這一種新的數(shù)據(jù)結(jié)構(gòu)。一棵樹中所有結(jié)點(diǎn)的度的最大值稱為該樹的度。 (1)二叉樹的基本概念二叉樹是結(jié)點(diǎn)的有窮集合，它或者是空集，或者同時(shí)滿足下述兩個(gè)條件： ①有且僅有一個(gè)稱為根的結(jié)點(diǎn)： ②其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合 T T2， T1與 T2都是二叉樹，并且 T1與 T2有順序關(guān)系 (T1在 T2之前 )，它們分別稱為根的左子樹和右子樹。性質(zhì) 3對任何二叉樹，若度數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2，則葉子數(shù) n0=n2+1。此外，每個(gè)二叉鏈表還必須有一個(gè)指向根結(jié)點(diǎn)的指針，該指針稱為根指針。遍歷一棵二叉樹就是按某種次序系統(tǒng)地 “訪問 ”二叉樹上的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被 “訪問 ”一次。與二叉樹的二叉鏈表存儲(chǔ)方法類似，孩子鏈表表示法的基本思想是：樹上的一個(gè) 結(jié)點(diǎn)的內(nèi)容 (數(shù)據(jù)元素 )以及指向該結(jié)點(diǎn)所有孩子的指針存儲(chǔ)在一起以便于運(yùn)算的實(shí)現(xiàn)。值得注意的是， “指針 ”域的類型定義可以有兩種選擇。 ②訪問根結(jié)點(diǎn)； (3)層次遍歷 ①若樹非空，訪問根結(jié)點(diǎn)； ②若第 1，…， i(i≥ 1)層結(jié)點(diǎn)已被訪問，且第 i+1層結(jié)點(diǎn)未訪問，則從左到右依次訪問第 i+1層結(jié)點(diǎn)。如果恰好表中元素按反序排列，則需要移動(dòng)的次數(shù)為 3 n(n1)/2。在查找時(shí)，首先與表的中間位置上結(jié)點(diǎn)的關(guān)鍵值比較，若相等則檢索成功；否則根據(jù)比較結(jié)果確定下一步在表的前半部或后半部中繼續(xù)進(jìn)行。它使用兩個(gè)散列函數(shù) H1和 H2。分時(shí)操作系統(tǒng)(time sharing system)；系統(tǒng)中有多個(gè)程序 (操作系統(tǒng)，實(shí)用程序和用戶程序 )共享存儲(chǔ)器，它們彼此之間不能相互干擾和破壞，這就是存儲(chǔ)保護(hù)問題。多個(gè)計(jì)算程序同時(shí)駐留在主存儲(chǔ)器中并行執(zhí)行的程序設(shè)計(jì)方法稱為多道程序設(shè)計(jì)，這種系統(tǒng)稱為多道程序系統(tǒng)。中斷處理程序?qū)χ袛嗍录奶幚矸謨刹竭M(jìn)行。進(jìn)程之間直接發(fā)生聯(lián)系的稱為相交進(jìn)程 (又稱相關(guān)進(jìn)程 )，否則為不相交進(jìn)程。對臨界資源訪問的互斥要求可視作執(zhí)行臨界區(qū)的互斥要求。為了區(qū)分什么時(shí)候可以使用特權(quán)指令，什么時(shí)候不可以使用，系統(tǒng)至少具有兩種工作狀態(tài)，它們分別稱為系統(tǒng)態(tài)和用戶態(tài)，又稱為管態(tài)和目態(tài)。阻塞(blocked):正等待某個(gè)事件 (I/O完成 )的發(fā)生。當(dāng)一個(gè)進(jìn)程創(chuàng)建一個(gè)新的進(jìn)程時(shí)，創(chuàng)建者稱為父進(jìn)程，被創(chuàng)建者稱為子進(jìn)程。例如，在實(shí)時(shí)系統(tǒng)中丟失一個(gè)。在單處理器系統(tǒng)中運(yùn)行隊(duì)列只有一個(gè)成員。 PCB是進(jìn)程存在的惟一標(biāo)志， PCB描述了進(jìn)程的基本情況。 (3)主存保護(hù)多道程序系統(tǒng)中，必須對各進(jìn)程使用的主存加以保護(hù)，以防止其他進(jìn)程進(jìn)行未經(jīng)許可的操作。例如，令信號(hào)量 mutex的初值為 1，于是臨界區(qū)就改寫成下列形式的代碼段。不相交進(jìn)程之間的聯(lián)系將表現(xiàn)在資源使用上的間接制約關(guān)系。中斷處理完成后，處理器分配給發(fā)生中斷時(shí)正在運(yùn)行的進(jìn)程，還 是分配給另一進(jìn)程，這取決于被中斷的進(jìn)程是可剝奪的還是不可剝奪的。既然他們同處在一個(gè)系統(tǒng)中，一個(gè)任務(wù) (或子任務(wù) )的執(zhí)行會(huì)受到其他任務(wù) (或子任務(wù) )的影響 (又稱為制約 )。 (3)設(shè)備管理現(xiàn)代計(jì)算機(jī)系統(tǒng)常常配置很多種類的輸入輸出設(shè)備，它們的輸入輸出速度差別很大，計(jì)算機(jī)系統(tǒng)常常采用通道、控制器、設(shè)備三級(jí)控制方法管理這些設(shè)備，設(shè)備管理的任務(wù)就是監(jiān)視這些資源的使用情況，根據(jù)一定的分配策略，把通道、控制器和設(shè)備分配給請求輸入輸出操作的程序，并啟動(dòng)設(shè)備完成所需的操作。網(wǎng)絡(luò)環(huán)境下的操作系統(tǒng)又分成網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)，網(wǎng)絡(luò)操作系統(tǒng)是在各單機(jī)操作系統(tǒng)的基礎(chǔ)上，按照網(wǎng)絡(luò)體系結(jié)構(gòu)的各個(gè)協(xié)議、標(biāo)準(zhǔn)進(jìn)行開發(fā)，形成網(wǎng)絡(luò)軟件，包括網(wǎng)絡(luò)管理、通信、資源共享、系統(tǒng)安全和多種網(wǎng)絡(luò)應(yīng)用等；分布式操作系統(tǒng)要求一個(gè)統(tǒng)一的操作系統(tǒng)，即廢棄 (或改造 )各單機(jī)的操作系統(tǒng)，整個(gè)網(wǎng)絡(luò)設(shè)有單一的操作系統(tǒng)。硬件指的是構(gòu)成計(jì)算機(jī)系統(tǒng)的物理設(shè)備。 ，塊內(nèi)結(jié)點(diǎn)不必有序，但塊與塊之間必須有序，即每一塊中各結(jié)點(diǎn)的關(guān)鍵值必須大于 (或小于，依此類推 )前一塊最大關(guān)鍵值。 ，使表中的 n個(gè)元素變成n/2個(gè)已排序的 組，再兩兩組比較，而變成 n/4個(gè)已排序的組……，直到表中只含有一個(gè)已排序的組，即完成排序。 ：將樹中每個(gè)結(jié)點(diǎn)用兩個(gè)鏈接表示就可以了，一個(gè)指向它最左邊的孩子，另一個(gè)指向它右邊的一個(gè)兄弟，從圖形上看，具體步驟是： ①加線：在兄弟結(jié)點(diǎn)間直接加一虛線； ②抹線：對每個(gè)結(jié)點(diǎn)，除了其最左的一個(gè)孩子外，抹去該結(jié)點(diǎn)原來與其余孩子之間的邊線； ③旋轉(zhuǎn)：將新加上的虛線改為實(shí)線，并將虛線以及有關(guān)的實(shí)線順時(shí)針旋轉(zhuǎn) 45度。通過將存儲(chǔ)結(jié)點(diǎn)中的指針域定義為高級(jí)語言中的指針類型，就得到各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，如單鏈表、二叉鏈表、孩子鏈表等等。一個(gè)孩子鏈表是一個(gè)帶頭結(jié)點(diǎn)的單鏈表，單鏈表的頭結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域和指針域。遍歷運(yùn)算的關(guān)鍵在于訪問結(jié)點(diǎn)的 “次序 ”，這種次序應(yīng)保 證二叉樹上的每個(gè)結(jié)點(diǎn)均被訪問一次且僅一次。值得注意的是，二叉鏈表中每 個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是指向該結(jié)點(diǎn)的一個(gè)孩子的指針，或者是空指針 NULL。深度為 k(k≥