【正文】 元插在線性表的第 i(0≤ i≤ n)個位置上；線性表合并；用數(shù)組存儲線性表的缺點主要有兩個：一是 程序中的數(shù)組通常大小是固定的，可能會與線性表的結點可以任意增加和減少的要求相矛盾；二是執(zhí)行線性表的結點插、刪操作時要移動存于數(shù)組中的其他元素，使插和刪操作不夠簡便 ②線性表的鏈接存儲線性表鏈接存儲是用鏈表存儲線性表，最簡單的用單鏈表。 (3)線性表上的查找線性表上的查找運算是指在線性表中查找某個鏈值的結點。 (5)棧棧的工作原理是采用后進先出 (LIFO)技術，棧頂由中央處理器中的棧指示器(SP)指出。棧的基本操作有： ① create(s)建立一個空棧 s ② empty(s)測試棧是否為空棧。隊列的最后一個元素一定是最新入隊的元素。 【考點三】 數(shù)組線性表 (包括棧和隊列 )都是線性結構，結構中的每個元素只是無結構的數(shù)據(jù)元素。然而，在計算機科學和計算機應用的各個領域中，存在著大量需要用更復雜的邏輯結構加以表示的問題。度為 0的結點稱為葉子或終端結點，度大于 0的結點稱為非終端結點或分支點。樹 (及一切樹形結構 )是一種 “分支層次 ”結構。 ⑤剪枝 DELETE(T， X， i)，加工型運算，其作用是刪除樹 T上結點 X的第 i棵子樹；若 T無第 i棵子樹，則為空操作。二叉樹的基本運算包括：ⅰ初始化 INITLATE(BT)，加工型運算，其作用是設置一棵空二叉樹 BT= ROOT(BT)，引用型運算，其結果是二叉樹 BT的根結點；若 BT為空二叉樹，運算結果為一特殊標志。性質 2深度為 k(k≥ 1)的二叉樹至多有 2k1個結點。完全二叉樹另一個重要性質是對其結點的 “按層編號 ”將得到很好的結果。二叉鏈表中的所有存儲結點通過它們的左、右指針的鏈接而形成一個整體。然而在某些情況下，二叉樹的順序存儲結構也很有用 。下面研究二叉樹的一種較為復雜的重要運算 ——遍歷及其在二叉鏈表上的實現(xiàn)。若以 D、 L、 R分別表示這三項子任務，則人有六種可能的次序： DLR、 LDR、 LRD、 DRL、 RDL和 RLD。下面介紹樹的三種常用存儲結構 (1)孩子鏈表表示法孩子鏈表表示法是樹的一種鏈式存儲結構。 (2)孩子兄弟鏈表表示法孩子兄弟鏈表中所有存儲結點的形式相同，均含三個域：數(shù)據(jù)域 ——用于存儲樹上的結點中的數(shù)據(jù)元素；孩子域 ——用于存儲指向本結點第一個孩子的指針；兄弟域 ——用于存放指向本結點下一個兄弟的指針。在雙親表示法下，每個存儲結點由兩個域組成：數(shù)據(jù)域 ——用于存儲樹上結點中的數(shù)據(jù)元素； “指針 ”域 ——用于指示本結點之雙親所在的存儲結點。相反，靜態(tài)鏈有的容量必須事先說明，因而其大小是固定的。 (2)后根遍歷若樹非空，則 ①依次先根遍歷根的各個子樹 T1，…， Tm。在插入時，元素的移動次數(shù)最多為1+2+3+… +(n1)=n(n1)/2。第一趟掃描的比較次數(shù)是 n1，第二趟掃描的比較次數(shù)是 n2……，總的比較次數(shù)是 (n1)+(n2)+……+1=n(n1)/2。如果表已排好序，則移動次數(shù)為 0。 。由于分塊而縮小了查找范圍，從而加快檢索速度。雙重散列技術是對線性探測法的改進。 (1)用戶觀點操作系統(tǒng)是用戶與計算機之間的接口，有了操作系統(tǒng)，用戶可以方便地使用計算機；在功能上，操作系統(tǒng)提供功能很強的系統(tǒng)調用，用戶軟件使用這些系統(tǒng)調用 (也稱管態(tài) )運行 (2)資源管理觀點操作系統(tǒng)是控制和管理計算機系統(tǒng)資源的程序，它的工作是當用戶程序和其他程序爭用這些資源時，提供有序的和可控的分配。而網絡操作系統(tǒng)用戶則需指明欲使用哪一臺計算機上的哪個資源。 (2)存儲管理計算機系統(tǒng)中，存儲器 (一般稱為主存或內存 )是運行程序、存放工作數(shù)據(jù)的，存儲管理的工作主要是對主存儲器進行分配、擴充和保護。一種接口是作業(yè)一級的接口，即提供一組操作命令，如 UNIX和 Linux的 shell命令語言或作業(yè)控制語言 (JCL)讓用戶組織和控制自己作 業(yè)的運行。程序的并發(fā)執(zhí)行，發(fā)揮了處理器與輸入輸出設備并發(fā)工作的能力，使系統(tǒng)的效率提高。內部中斷也稱為軟件中斷。所有的中斷向量構成一個中斷向量表，它們通常存放在一個專門的存儲區(qū)域中，這個區(qū)域的地址可以是固定的；相應的處理程序的入口地址通常是在系統(tǒng)引導過程中，通過對系統(tǒng)配置的檢測，得到系統(tǒng)中設備配置的情況，在操作系統(tǒng)裝入過程中，填寫中斷向量表中的內容。封閉性是指程序運行時獨占系統(tǒng)資源，只有程序本身能改變系統(tǒng)的狀態(tài)；可再現(xiàn)性是指程序運行不受外部因素影響，只要初始條件相同 ，運行結果就相同。因此，進程之間需要某種形式的通信。為了成功地協(xié)同工作，有關進程在某些確定的點上應當同步它們的活動：一個進程到達了這些點后，除非另一進程已完成了某個活動，否則就停下來，以等待該活動結束。 (1)互斥為了保護共享資源 (如公共變量等 )，使它們不被多個進程同時訪問，就要阻止這些進程同時執(zhí)行訪問這些資源的代碼段，這些代碼段稱為臨界區(qū)，這些資源稱為臨界資源。對此，可以令信號量 proceed初值為 0，實現(xiàn)這種同步的程序形式是： 進程 A… L1： P(proceed)；…進程 B… L2： V(proceed)；…更復雜一點的同步問題是單緩沖的生產者、消費者問題。 (2)特權指令為使各并發(fā)進程不相互干擾，系統(tǒng)的部分指令集應保留僅供操作系統(tǒng)使用，這些指令稱為特權指令，如允許與禁止中斷，執(zhí)行輸入輸出操作等。相對于程序，進程是一個動態(tài)的概念，而程序是靜態(tài)的概念，是指令的集合。進程控制塊隨著進程的建立而產生，隨著進程的完成而撤消。他們都涉及現(xiàn)場隊列管理等。該進程的運行也會因等待某個事件(如 I/O完成 )的發(fā)生而處于阻塞狀態(tài)，轉入相應的阻塞隊列。在有些進程 (如高優(yōu)先級進程 )需 要快速服務的系統(tǒng)中，剝奪調度是非常有用的。 (2)進程調度進程調度 即處理器調度，它的主要功能是確定在什么時候分派處理器，并確定分給哪一個進程。一般阻塞隊列的個數(shù)取決于等待事件 (原因 )的個數(shù)。進程管理涉及到進程控制、隊列管理、進程調度等。從靜態(tài)的觀點看，進程由程序、數(shù)據(jù)和進程控制塊組成；從動態(tài)的觀點看，是計算機狀態(tài)的一個有序集合。保護機制應包含在主存尋址硬件中。 (1)有緩沖區(qū)的通信方式中，有原語： Write(Buffer_Name,Variable)等緩沖區(qū)空再存入 Read(Buffer_Name,Variable)等緩沖區(qū)滿再取出 2)無緩沖區(qū)的通信，又稱為消息傳遞，有原語： Send(Who,Message)發(fā)送消息給指定進程或一組進程 Receive(Who,Message)從約定進程接收消息有的系統(tǒng)還提供帶標記的發(fā)送，有 Send(Who,Message,Tag)用 Tag可指定發(fā)送進程是否要等待接收進程取到內容以后再繼續(xù)運行。 P(mutex)。信號量是一種特殊的變量，它的表現(xiàn)形式是一個整型變量及相應的隊列，除了設置初值外，對信號量只能施加特殊的操作。 (1)互斥多道系統(tǒng)中，各進程 可以共享各類資源，但有些資源卻一次只能供一個進程使用。由于中斷是以不可預測的次序發(fā)生，即程序的指令序列也以不可預測的次序前進，這樣就會產生操作系統(tǒng)的另一特性：不確定性。如果是不可剝奪的，它重新得到處理器，否則，可能被別的進程 (如優(yōu)先級更高 )奪得處理器。不可屏蔽的中斷是一些最緊急最重要的中斷，如掉電等。 異常迅速，導致了控制技術的發(fā)展，設備控制的基本技術是中斷。并發(fā)的意思是存在許多同時的活動 (或并行的活動 )；輸入輸出操作和處理器運行并行活動；在主存中同時駐留幾道用戶程序等都是并發(fā)的例子。為了發(fā)揮設備和處理機的并行工作能力，常常采用緩沖技術和虛擬技術。許多操作系統(tǒng)是以作業(yè)和進程的方式進行管理，實現(xiàn)作業(yè)和進程的調度，分配處理器，控制作業(yè)和進程的執(zhí)行。分布式操作系統(tǒng)負責全系統(tǒng)的資源分配和調度，為用戶提供統(tǒng)一的界面。它從系統(tǒng)各部分可以并行工作為出發(fā)點，考慮管理任務的分割和相互之間的關系，通過進程之間的通信解決共享資源時帶來的競爭問題。操作系統(tǒng)控制和管理所有的系統(tǒng)硬件 (如處理器、存儲器、各種設備 )，也控制和管理系統(tǒng)中所有的軟件，操作系統(tǒng)為計算機使用者提供了一種良好的操作環(huán)境，也為各種應用系統(tǒng)提供了基本的支持環(huán)境。一般說來，關鍵碼值的集合比散列表存儲位的數(shù)目大得多，這正是體現(xiàn)散列表的優(yōu)勢所在，但同時帶來了沖突問題，即不同的關鍵值經散列函數(shù)計算，可能得到相同的存儲位置。為加快查找，還要建立一個索引表，表中給出每一塊的最大關鍵值和指向塊內第一個結點的指針。 【考點六】 檢索 。所需要的比較次數(shù)為 nlog2n，移動次數(shù)為 n。所需移動次數(shù)最多也為 n(n1)/2。 二叉樹還原為一般樹的步驟是： ①加線：若某結點是一父結點的左孩子，則將該結點的右孩子以及沿著右鏈搜索到的所有右孩子結點都用線與那個父結點連接起來； ②抹線：抹去原二叉樹中所有結點與其右孩子的連線； ③旋轉：將虛線及有關實線逆時針旋轉約 45度，并將幾個結點按層次排列 ： ①將森林中的每棵樹轉換為二叉樹； ②森林中第一棵樹的根結點就是轉換后二叉樹的根結點，依次將后一棵樹作為前一棵樹根結點的右子樹。數(shù)據(jù)域用于存儲樹上一個結點中的數(shù)據(jù)元素；雙親域用于存放本結點的雙親結點在數(shù)組中的序號 (下標值 )。第二種選擇是將 “指針 ”域定義為整型、子界型等型。同時，在這種存儲結構上容易實現(xiàn)樹形數(shù)據(jù)結構的大多數(shù)運算。其中，數(shù)據(jù)域用于存儲結點 X中的數(shù)據(jù)元素；指針域用于存儲指向該單鏈表中第一個表結點 (首結點 )的指針。后根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操 作； ①后根遍歷左子樹 ②后根遍歷右子樹 ③訪問根結點。由定義可知，一棵二叉樹由三部分組成：根、左子樹和右子樹。因此，對于任何完全二叉樹來說，可以采用 “以編號為地址 ”的策略將結點存入作為順序存儲結構的一維數(shù)組。若二叉樹為空，則 root=NULL。 (3)若 2i+1n，則結點 X無右孩子，否則， X的右孩子 RCHILD(X)的編號為 2i+1 ，順序存儲結構和鏈式存儲結構。由性質 2知，滿二叉樹上各層的結點數(shù)已達到了二叉樹可以容納的最大值。ⅵ剪枝 DELLEFT(BT， X)和 DELRIGHT(BT， X)，加工型運算，其作用分別為刪除二叉樹BT上結點 X的左、右子樹；若 X無左或右子樹，運算為空操作。相應地，二叉樹上任一結點左、右子樹的根分別稱為該結點的左孩子和右孩子。 ： ①求根 ROOT(T)，引用型運算，其結果是結點 X在樹 T的根結點。一棵樹上的任何結點 (不包括根本身 )稱為根的子孫。在樹上，根結點沒有直接前趨。 (2)數(shù)組的順序存儲結構由于對數(shù)組一般不作插入和刪除運算，因此，一旦數(shù)組被建立，則結構中的元素個數(shù)和元素之間的關系就不再發(fā)生變動。 ③ full(Q) 測試隊列是否為滿。 ⑥ pop(s)刪除棧頂元素。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作。檢查插入要求的有關參數(shù)的合理性；單鏈表就是通過鏈接指針來體現(xiàn)線性表中結點的先后次序關系。 ①線性表的順序存儲線性表的順序存儲是最簡單的存儲方式。統(tǒng)計線性表中表元的個數(shù)；下面所列的是其中一些常用的運算。 (2)算法的分析求解同一個問題可以有多種不同的算法，評價一個算法的優(yōu)劣除了正確性和簡明性外，主要考慮兩點：一是執(zhí)行算法所耗費的時間，二是執(zhí)行算法所耗費的存儲空間，特別是輔助存儲空間的耗費。 ③可行性算法中的所有待實現(xiàn)的運算必須在原則上能夠由人使用筆和紙在做有窮次運算后完成。關鍵字是能唯一標識一個結點的那些數(shù)據(jù)項。線性表就是一個典型的線性結構。當計算機運行時，源病毒能把自身精確拷貝或者有修改地拷貝到其他程序體內，影響和破壞正常程序的執(zhí)行和數(shù)據(jù)的正確性。 重要方面。而從更全面的意義來理解，就是要保證信息的保密性 (confidentiality)、完整性 (integrity)、可用性 (availability)和可控性 (controllability)。 (4)城域網城域網 (MAN,Metropolitan Area Network)是介于廣域網與局域網之間的一種高速網絡。適應大容量與突發(fā)性通信的要求； 【考點五】 計算機網絡基礎 (1)計算機網絡的形成與發(fā)展 (2)計算機網絡的主要特征資源共享觀點將計算機網絡定義為 “以能夠相互共享資源的方式互聯(lián)起來的自治計算機系統(tǒng)的集合 ”。 用的應用軟件。 (7)保護和保密處理。應用軟件是為解決各種實際問題而設計的程序。 ，它們是指令部件、時序部件和操作控制部件。計算機硬件結構也可以稱為馮其特點是多用戶分時處理。同時系統(tǒng)結構的特點對計算機的性能也有巨大的影響 (中斷系統(tǒng)、 Cache存儲器、流水線技術等等 )。集成電路 (integrated circuit)的出現(xiàn)，宣告了第三代計算機的來臨。從 20世紀 50年代后期到 60年代中期 (1958～ 1964)為晶體管計算機時期。從 1946年到 50年代后期 (1946～ 1957)為電子管計算機時期。 (五 )數(shù)據(jù)庫設計和數(shù)據(jù)庫應用 、內容和方法。 。 ，具有數(shù)據(jù)庫設計能力，了解數(shù)據(jù)庫技術發(fā)展。 C語言編程、開發(fā)數(shù)據(jù)庫應用 (含上機調試 )的能力。 (三 )操作系統(tǒng) 、主要功能和分類。 。計算機的元器件主要由電子管 (vacuum tube)組成。自從 1947年晶體管 (transistor)在貝爾實驗室誕生后