計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)的方法

計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)的方法

　　操作系統(tǒng)在大綱中的考查目標(biāo)是了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位、發(fā)展和特點(diǎn);能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題。下面是學(xué)習(xí)啦小編分享給大家的計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)的方法的資料，希望大家喜歡!

　　計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)的方法

　　▶操作系統(tǒng)概述

　　這一章出現(xiàn)大題的可能性微乎其微。選擇題中常出現(xiàn)的點(diǎn)主要是這些：操作系統(tǒng)的定義，引入單道批處理系統(tǒng)、多道批處理、分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)的原因，這些不同階段的操作系統(tǒng)共的特征如何，相互之間的差別在什么地方;操作系統(tǒng)的基本特征和功能;操作系統(tǒng)的運(yùn)行環(huán)境。

　　▶進(jìn)程管理

　　進(jìn)程管理是重點(diǎn)和難點(diǎn)之所在?？键c(diǎn)既可以出現(xiàn)在選擇題中，又可以出在綜合應(yīng)用題中。按照大綱考點(diǎn)的順序，諸如進(jìn)程的概念、基本特征、組成結(jié)構(gòu)，進(jìn)程與程序的區(qū)別與聯(lián)系，進(jìn)程的狀態(tài)及其相互轉(zhuǎn)換的條件及過程，進(jìn)程間的通信方式，線程的定義以及和進(jìn)程的區(qū)別與聯(lián)系，調(diào)度的基本概念、時(shí)機(jī)、切換過程和各種調(diào)度算法，進(jìn)程同步相關(guān)的概念，實(shí)現(xiàn)同步與互斥的機(jī)制，信號量和PV操作，管程的基本組成結(jié)構(gòu)和運(yùn)行過程，死鎖的基本概念，死鎖產(chǎn)生的四個(gè)必要條件，預(yù)防、避免、檢測和解除死鎖的原理與方法，這些點(diǎn)都可以出現(xiàn)在選擇題中進(jìn)行考查。對于綜合應(yīng)用題，重點(diǎn)應(yīng)該放在PV操作，調(diào)度算法和銀行家算法。其中，用PV操作實(shí)現(xiàn)經(jīng)典同步問題及其變形是整個(gè)操作系統(tǒng)考試的最難點(diǎn)，也是最大的熱點(diǎn)。要注意收集往年各?？歼^的PV操作應(yīng)用題，把常見的經(jīng)典題型做會(huì)做熟，力求看到題目就能想到相關(guān)的解題套路。調(diào)度算法的難點(diǎn)在于計(jì)算不同調(diào)度算法下調(diào)度的效率，建議使用時(shí)間軸的方法解決相關(guān)的調(diào)度時(shí)間計(jì)算問題。銀行家算法是系統(tǒng)做資源分配的時(shí)候防止發(fā)生死鎖的一種方法，該算法的難點(diǎn)在于搞清楚各種不同表格的含義，能夠看懂并且會(huì)做出相關(guān)的表格，由表格推出結(jié)果。

　　▶內(nèi)存管理

　　內(nèi)存管理可考的點(diǎn)也很多，同樣也可以有靈活的考查方法。但是相比進(jìn)程管理來說，這一部分理解起來要相對簡單，各種存儲(chǔ)管理的算法的思想都是比較直接的，難點(diǎn)在于要記住解決某一個(gè)問題的算法有那幾個(gè)，每一個(gè)算法的運(yùn)行過程是怎么樣的。這一章典型的綜合應(yīng)用題出現(xiàn)在：內(nèi)存的連續(xù)分配算法，比如給出內(nèi)存的申請和釋放序列，要求解空閑塊列表;非連續(xù)分配管理方式下虛擬地址和物理地址的轉(zhuǎn)換，這一點(diǎn)可以和組成原理中的虛擬存儲(chǔ)器結(jié)合來看;各種頁面置換算法產(chǎn)生的缺頁數(shù)的統(tǒng)計(jì)，經(jīng)典的解法是表格法。至于選擇題的點(diǎn)，這一章有比較多，除了上述綜合題點(diǎn)都可以簡化后出現(xiàn)在選擇題中外，還需要注意內(nèi)存管理的基本概念，如裝入、鏈接、邏輯地址、物理地址、交換、覆蓋等等，各種主存分配方式的工作過程以及優(yōu)缺點(diǎn)對比，虛存的基本概念，抖動(dòng)、工作集、程序局部性原理以及請求分段請求分頁的基本原理。

　　▶文件管理

　　文件管理的重點(diǎn)在于文件的順序和索引結(jié)構(gòu)。這一部分最重要的應(yīng)用題點(diǎn)在于索引文件的目錄結(jié)構(gòu)，要熟練掌握計(jì)算給定目錄樹結(jié)構(gòu)下單文件的最大文件大小;其次是Unix系統(tǒng)的文件系統(tǒng)空閑塊的組織方法——成組鏈接法，要能說清楚空閑塊是怎么分配給申請空閑塊的文件的，以及釋放的空閑塊如何加入到空閑塊組里;最后是磁盤的調(diào)度算法，要熟練掌握不同調(diào)度算法尋道數(shù)的計(jì)算。文件系統(tǒng)其它需要了解的知識(shí)點(diǎn)包括：文件的相關(guān)概念，文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，目錄結(jié)構(gòu)以及目錄管理，文件共享與保護(hù)機(jī)制，隱式鏈接和顯式鏈接，空閑塊的三種不同組織方法，磁盤的相關(guān)概念和參數(shù)，磁盤的結(jié)構(gòu)以及調(diào)度算法的特點(diǎn)和優(yōu)缺點(diǎn)對比等。

　　▶輸入輸出管理

　　這一章是非重點(diǎn)。需要注意的地方是五種I/O控制方式和它們之間的對比，SPOOLING技術(shù)以及緩沖策略。可能的選擇題點(diǎn)包括I/O設(shè)備的分類，I/O管理的目標(biāo)與功能，應(yīng)用結(jié)構(gòu)，控制方式，I/O調(diào)度的相關(guān)概念，設(shè)備獨(dú)立性相關(guān)的概念和原理，容錯(cuò)技術(shù)等。

　　計(jì)算機(jī)是一門很博大精深的科目，包含的內(nèi)容千變?nèi)f化，能學(xué)的東西也數(shù)不勝數(shù)。操作系統(tǒng)是重要的科目，知識(shí)點(diǎn)還是很多的，考生應(yīng)該牢牢掌握。

　　計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)核心考點(diǎn)之排序算法

　　各類排序算法的特點(diǎn)及比較

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

　　冒泡排序算法思想：

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

　　選擇排序算法思想：

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

　　插入排序算法思想：

　　經(jīng)過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。

　　快速排序算法思想：

　　快速排序的基本思想是基于分治策略的。對于輸入的子序列L[p..r]，如果規(guī)模足夠小則直接進(jìn)行排序，否則分三步處理：1. 分解(Divide)：將輸入的序列L[p..r]劃分成兩個(gè)非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。2. 遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法分別對L[p..q]和L[q+1..r]進(jìn)行排序。3. 合并(Merge)：由于對分解出的兩個(gè)子序列的排序是就地進(jìn)行的，所以在L[p..q]和L[q+1..r]都排好序后不需要執(zhí)行任何計(jì)算L[p..r]就已排好序。

　　歸并排序算法思想：

　　分而治之(divide -conquer)。每個(gè)遞歸過程涉及三個(gè)步驟：1.分解，把待排序的n個(gè)元素的序列分解成兩個(gè)子序列，每個(gè)子序列包括 n/2 個(gè)元素。2. 治理，對每個(gè)子序列分別調(diào)用歸并排序MergeSort，進(jìn)行遞歸操作。3. 合并，合并兩個(gè)排好序的子序列,生成排序結(jié)果。

　　Shell排序算法思想：

　　算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。

　　堆排序算法思想：

　　用大根堆排序的基本思想：1.先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無序區(qū)。2.再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key。3. 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。

　　計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)核心考點(diǎn)之二叉樹

　　▶二叉樹的遍歷

　　遍歷的過程就是把非線性結(jié)構(gòu)的二叉樹中的結(jié)點(diǎn)排成一個(gè)線性序列的過程。

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

　　從二叉樹結(jié)構(gòu)的整體看，二叉樹可以分為根結(jié)點(diǎn)，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設(shè)D表示根結(jié)點(diǎn)，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先(前)序法(先根次序法)，中序法(中根次序法，對稱法)，后序法(后根次序法)。三種遍歷的遞歸算法如下：

　　1.先序法(DLR)

　　若二叉樹為空，則空操作，否則：訪問根結(jié)點(diǎn)，先序遍歷左子樹，先序遍歷右子樹。

　　2.中序法(LDR)

　　若二叉樹為空，則空操作，否則：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹.

　　3.后序法(LRD)

　　若二叉樹為空，則空操作，否則：后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點(diǎn)。

　　▶完全二叉樹中有關(guān)結(jié)點(diǎn)個(gè)數(shù)計(jì)算

　　完全二叉樹的定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹。

　　完全二叉樹的葉子數(shù)為(n + 1) / 2取下整。

　　▶森林與二叉樹之間的轉(zhuǎn)換以及轉(zhuǎn)換過程中結(jié)點(diǎn)之間的關(guān)系

　　將一棵樹轉(zhuǎn)換為二叉樹的方法是：

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

　　2.對樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。

　　3.以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

　　森林轉(zhuǎn)換為二叉樹的方法如下：

　　1.將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。

　　2.第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

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

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

　　2.刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。

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

　　計(jì)算機(jī)是一門很博大精深的科目，包含的內(nèi)容千變?nèi)f化，能學(xué)的東西也數(shù)不勝數(shù)。二叉樹是重要的考點(diǎn)，考生應(yīng)該牢牢掌握。