計算機作業系統學習指導的方法

　　作業系統在大綱中的考查目標是瞭解作業系統在計算機系統中的作用、地位、發展和特點;能夠運用所學的作業系統原理、方法與技術分析問題和解決問題。下面是小編分享給大家的的資料，希望大家喜歡!

　　▶作業系統概述

　　這一章出現大題的可能性微乎其微。選擇題中常出現的點主要是這些：作業系統的定義，引入單道批處理系統、多道批處理、分時系統、實時系統的原因，這些不同階段的作業系統共的特徵如何，相互之間的差別在什麼地方;作業系統的基本特徵和功能;作業系統的執行環境。

　　▶程序管理

　　程序管理是重點和難點之所在。考點既可以出現在選擇題中，又可以出在綜合應用題中。按照大綱考點的順序，諸如程序的概念、基本特徵、組成結構，程序與程式的區別與聯絡，程序的狀態及其相互轉換的條件及過程，程序間的通訊方式，執行緒的定義以及和程序的區別與聯絡，排程的基本概念、時機、切換過程和各種排程演算法，程序同步相關的概念，實現同步與互斥的機制，訊號量和PV操作，管程的基本組成結構和執行過程，死鎖的基本概念，死鎖產生的四個必要條件，預防、避免、檢測和解除死鎖的原理與方法，這些點都可以出現在選擇題中進行考查。對於綜合應用題，重點應該放在PV操作，排程演算法和銀行家演算法。其中，用PV操作實現經典同步問題及其變形是整個作業系統考試的最難點，也是最大的熱點。要注意收集往年各校考過的PV操作應用題，把常見的經典題型做會做熟，力求看到題目就能想到相關的解題套路。排程演算法的難點在於計算不同調度演算法下排程的效率，建議使用時間軸的方法解決相關的排程時間計算問題。銀行家演算法是系統做資源分配的時候防止發生死鎖的一種方法，該演算法的難點在於搞清楚各種不同表格的含義，能夠看懂並且會做出相關的表格，由表格推出結果。

　　▶記憶體管理

　　記憶體管理可考的點也很多，同樣也可以有靈活的考查方法。但是相比程序管理來說，這一部分理解起來要相對簡單，各種儲存管理的演算法的思想都是比較直接的，難點在於要記住解決某一個問題的演算法有那幾個，每一個演算法的執行過程是怎麼樣的。這一章典型的綜合應用題出現在：記憶體的連續分配演算法，比如給出記憶體的申請和釋放序列，要求解空閒塊列表;非連續分配管理方式下虛擬地址和實體地址的轉換，這一點可以和組成原理中的虛擬儲存器結合來看;各種頁面置換演算法產生的缺頁數的統計，經典的解法是表格法。至於選擇題的點，這一章有比較多，除了上述綜合題點都可以簡化後出現在選擇題中外，還需要注意記憶體管理的基本概念，如裝入、連結、邏輯地址、實體地址、交換、覆蓋等等，各種主存分配方式的工作過程以及優缺點對比，虛存的基本概念，抖動、工作集、程式區域性性原理以及請求分段請求分頁的基本原理。

　　▶檔案管理

　　檔案管理的重點在於檔案的順序和索引結構。這一部分最重要的應用題點在於索引檔案的目錄結構，要熟練掌握計算給定目錄樹結構下單檔案的最大檔案大小;其次是Unix系統的檔案系統空閒塊的組織方法——成組連結法，要能說清楚空閒塊是怎麼分配給申請空閒塊的檔案的，以及釋放的空閒塊如何加入到空閒塊組裡;最後是磁碟的排程演算法，要熟練掌握不同調度演算法尋道數的計算。檔案系統其它需要了解的知識點包括：檔案的相關概念，檔案的邏輯結構和物理結構，目錄結構以及目錄管理，檔案共享與保護機制，隱式連結和顯式連結，空閒塊的三種不同組織方法，磁碟的相關概念和引數，磁碟的結構以及排程演算法的特點和優缺點對比等。

　　▶輸入輸出管理

　　這一章是非重點。需要注意的地方是五種I/O控制方式和它們之間的對比，SPOOLING技術以及緩衝策略。可能的選擇題點包括I/O裝置的分類，I/O管理的目標與功能，應用結構，控制方式，I/O排程的相關概念，裝置獨立性相關的概念和原理，容錯技術等。

　　計算機是一門很博大精深的科目，包含的內容千變萬化，能學的東西也數不勝數。作業系統是重要的科目，知識點還是很多的，考生應該牢牢掌握。

　　計算機資料結構核心考點之排序演算法

　　各類排序演算法的特點及比較

　　幾種主要的排序演算法：氣泡排序、選擇排序、插入排序、快速排序、歸併排序、Shell排序、堆排序等。

　　氣泡排序演算法思想：

　　將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在氣泡排序演算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。

　　選擇排序演算法思想：

　　選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。

　　插入排序演算法思想：

　　經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。

　　快速排序演算法思想：

　　快速排序的基本思想是基於分治策略的。對於輸入的子序列L[p..r]，如果規模足夠小則直接進行排序，否則分三步處理：1. 分解***Divide***：將輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大於L[q+1..r]中任一元素的值。2. 遞迴求解***Conquer***：通過遞迴呼叫快速排序演算法分別對L[p..q]和L[q+1..r]進行排序。3. 合併***Merge***：由於對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序。

　　歸併排序演算法思想：

　　分而治之***divide -conquer***。每個遞迴過程涉及三個步驟：1.分解，把待排序的n個元素的序列分解成兩個子序列，每個子序列包括 n/2 個元素。2. 治理，對每個子序列分別呼叫歸併排序MergeSort，進行遞迴操作。3. 合併，合併兩個排好序的子序列,生成排序結果。

　　Shell排序演算法思想：

　　演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。

　　堆排序演算法思想：

　　用大根堆排序的基本思想：1.先將初始檔案R[1..n]建成一個大根堆，此堆為初始的無序區。2.再將關鍵字最大的記錄R[1]***即堆頂***和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key。3. 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。

　　計算機資料結構核心考點之二叉樹

　　▶二叉樹的遍歷

　　遍歷的過程就是把非線性結構的二叉樹中的結點排成一個線性序列的過程。

　　二叉樹遍歷方法可分為兩大類，一類是“寬度優先”法，即從根結點開始，由上到下，從左往右一層一層的遍歷;另一類是“深度優先法”，即一棵子樹一棵子樹的遍歷。

　　從二叉樹結構的整體看，二叉樹可以分為根結點，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設D表示根結點，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左後右，則只有DLR，LDR，LRD三種，分別稱為先***前***序法***先根次序法***，中序法***中根次序法，對稱法***，後序法***後根次序法***。三種遍歷的遞迴演算法如下：

　　1.先序法***DLR***

　　若二叉樹為空，則空操作，否則：訪問根結點，先序遍歷左子樹，先序遍歷右子樹。

　　2.中序法***LDR***

　　若二叉樹為空，則空操作，否則：中序遍歷左子樹，訪問根結點，中序遍歷右子樹.

　　3.後序法***LRD***

　　若二叉樹為空，則空操作，否則：後序遍歷左子樹，後序遍歷右子樹，訪問根結點。

　　▶完全二叉樹中有關結點個數計算

　　完全二叉樹的定義：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹。

　　完全二叉樹的葉子數為***n + 1*** / 2取下整。

　　▶森林與二叉樹之間的轉換以及轉換過程中結點之間的關係

　　將一棵樹轉換為二叉樹的方法是：

　　1.樹中所有相鄰兄弟之間加一條連線。

　　2.對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。

　　3.以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

　　森林轉換為二叉樹的方法如下：

　　1.將森林中的每棵樹轉換成相應的二叉樹。

　　2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把後一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起後，所得到的二叉樹就是由森林轉換得到的二叉樹。

　　樹和森林都可以轉換為二叉樹，二者的不同是:樹轉換成的二叉樹,其根結點必然無右孩子，而森林轉換後的二叉樹，其根結點有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下：

　　1.若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、……都與該結點的雙親結點用線連起來。

　　2.刪掉原二叉樹中所有雙親結點與右孩子結點的連線。

　　3.整理由1、2兩步所得到的樹或森林，使之結構層次分明。

　　計算機是一門很博大精深的科目，包含的內容千變萬化，能學的東西也數不勝數。二叉樹是重要的考點，考生應該牢牢掌握。