考研計算機(jī)復(fù)試面試題總結(jié)

1、概念問題C+/數(shù)據(jù)結(jié)構(gòu)1、簡述你對“面向?qū)ο蟆焙汀懊嫦蜻^程”編程思想的認(rèn)識與思考用就可以了。面向過程就是分析出解決問題所需要的步驟，然后用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調(diào)面向?qū)ο笫前褬?gòu)成問題事務(wù)分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在整個解決問題的步驟中的行為。例如五子棋，面向過程的設(shè)計思路就是首先分析問題的步驟：1、開始游戲， 2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面， 7、判斷輸贏，8、返回步驟2，9、輸出最后結(jié)果。把上面每個步驟用分別的函數(shù)來實現(xiàn)，問題就解決了。而面向?qū)ο蟮脑O(shè)計則是從另外的思路來解決問題。整

2、個五子棋可以分為 1 、黑白雙方， 這兩方的行為是一模一樣的， 2、棋盤系統(tǒng)，負(fù)責(zé)繪制畫面，3、規(guī)則系統(tǒng)，負(fù)責(zé)判定諸如犯規(guī)、輸贏等。第一類對象（玩家對象）負(fù)責(zé)接受用戶輸入，并告知第二類對象（棋盤對象）棋子布局的變化， 棋盤對象接收到了棋子的 i變化就要負(fù)責(zé)在屏幕上面顯示出這種變化，同時利用第三類對象（規(guī)則系統(tǒng)）來對棋局進(jìn)行判定?？梢悦黠@地看出，面向?qū)ο笫且怨δ軄韯澐謫栴}，而不是步驟。同樣是繪制棋局，這樣的行為在面向過程的設(shè)計中分散在了總多步驟中，很可能出現(xiàn)不同的繪制版本， 因為通常設(shè)計人員會考慮到實際情況進(jìn)行各種各樣的簡化。而面向?qū)ο蟮脑O(shè)計中， 繪圖只可能在棋盤對象中出現(xiàn)，從而保證了繪圖的統(tǒng)一

3、。功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴(kuò)展性。比如我要加入悔棋的功能，如果要改動面向過程的設(shè)計， 那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的循序都要進(jìn)行大規(guī)模調(diào)整。如果是面向?qū)ο蟮脑挘挥酶膭悠灞P對象就行了，棋盤系統(tǒng)保存了黑白雙方的棋譜， 簡單回溯就可以了，而顯示和規(guī)則判斷則不用顧及，同時整個對對象功能的調(diào)用順序都沒有變化，改動只是局部的。再比如我要把這個五子棋游戲改為圍棋游戲， 如果你是面向過程設(shè)計， 那么五子棋的規(guī)則就分布在了你的程序的每一個角落， 要改動還不如重寫。 但是如果你當(dāng)初就是面向?qū)ο蟮脑O(shè)計，那么你只用改動規(guī)則對象就可以了， 五子棋和圍棋的區(qū)別不就是規(guī)則嗎 （當(dāng)然

4、棋盤大小好像也不一樣，但是你會覺得這是一個難題嗎直接在棋盤對象中進(jìn)行一番小改動就可以了。 ）而下棋的大致步驟從面向?qū)ο蟮慕嵌葋砜礇]有任何變化。當(dāng)然，要達(dá)到改動只是局部的需要設(shè)計的人有足夠的經(jīng)驗， 使用對象不能保證你的程序就是面向?qū)ο螅?初學(xué)者或者很蹩腳的程序員很可能以面向?qū)ο笾摱忻嫦蜻^程之實， 這樣設(shè)計出來的所謂面向?qū)ο蟮某绦蚝茈y有良好的可移植性和可擴(kuò)展性。2、 ADT 是什么簡述你對“數(shù)據(jù)抽象”和“信息隱藏”的認(rèn)識抽象數(shù)據(jù)類型 (Abstract Data Type簡稱ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型（高級編程語言中已實現(xiàn)的數(shù)據(jù)

5、類型）來實現(xiàn)。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。對一個抽象數(shù)據(jù)類型進(jìn)行定義時，必須給出它的名字及各運算的運算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型通過類(class)實現(xiàn)程序設(shè)計語言對抽象數(shù)據(jù)類型的支持是指允許用戶自定義具有如下特征的數(shù)據(jù)類型：1. 模塊封裝： The representation of, and operations on, objects of the type are defined in a single

6、syntactic unit2. 信息隱蔽： The representation of objects of the type is hidden from the program units that use theseobjects,so the only operationspossibleare thoseprovidedin the typesdefinition3、 const 和 static有什么作用const 是一個 C 和 C+語言的關(guān)鍵字，它限定一個變量不允許被改變，即只讀。使用 const 在一定程度上可以提高程序的安全性和可靠性， 也便于實現(xiàn)對此進(jìn)行優(yōu)化 （如把只讀

7、對象放入 ROM中）。 const 作為類型限定符，是類型的一部分。4、友元關(guān)系的利與弊如果將一個函數(shù)或一個類聲明為另一個類的友元，那么它就可以直接存取這個類對象中的各種數(shù)據(jù)，而不必在意這些數(shù)據(jù)的封裝級別，即無論是private的，protected的，還是 public的，有錢同使，有難同當(dāng)。5、C+多態(tài)的實現(xiàn)1. 用 virtual 關(guān)鍵字申明的函數(shù)叫做虛函數(shù)，虛函數(shù)肯定是類的成員函數(shù)。2. 存在虛函數(shù)的類都有一個一維的虛函數(shù)表叫做虛表。類的對象有一個指向虛表開始的虛指針。虛表是和類對應(yīng)的，虛表指針是和對象對應(yīng)的。3. 多態(tài)性是一個接口多種實現(xiàn)，是面向?qū)ο蟮暮诵摹７譃轭惖亩鄳B(tài)性和函數(shù)的多態(tài)

8、性。4. 多態(tài)用虛函數(shù)來實現(xiàn)，結(jié)合動態(tài)綁定。5.純虛函數(shù)是虛函數(shù)再加上= 0 。6. 抽象類是指包括至少一個純虛函數(shù)的類。構(gòu)造函數(shù)順序：基類構(gòu)造函數(shù)派生類構(gòu)造函數(shù)前面輸出的結(jié)果是因為編譯器在編譯的時候，就已經(jīng)確定了對象調(diào)用的函數(shù)的地址，要解決這個問題就要使用遲綁定（latebinding ）技術(shù)。當(dāng)編譯器使用遲綁定時，就會在運行時再去確定對象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采用遲綁定，就要在基類中聲明函數(shù)時使用 virtual關(guān)鍵字 （注意， 這是必須的， 很多學(xué)員就是因為沒有使用虛函數(shù)而寫出很多錯誤的例子），這樣的函數(shù)我們稱為虛函數(shù)。一旦某個函數(shù)在基類中聲明為virtual，那么在所有

9、的派生類中該函數(shù)都是virtual，而不需要再顯式地聲明為virtual。前面輸出的結(jié)果是因為編譯器在編譯的時候，就已經(jīng)確定了對象調(diào)用的函數(shù)的地址，要解決這個問題就要使用遲綁定（latebinding ）技術(shù)。當(dāng)編譯器使用遲綁定時，就會在運行時再去確定對象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采用遲綁定，就要在基類中聲明函數(shù)時使用 virtual關(guān)鍵字 （注意， 這是必須的， 很多學(xué)員就是因為沒有使用虛函數(shù)而寫出很多錯誤的例子），這樣的函數(shù)我們稱為虛函數(shù)。一旦某個函數(shù)在基類中聲明為virtual，那么在所有的派生類中該函數(shù)都是virtual，而不需要再顯式地聲明為virtual。編譯器在編譯的

10、時候，發(fā)現(xiàn)基類中有虛函數(shù)，此時編譯器會為每個包含虛函數(shù)的類創(chuàng)建一個虛表（即vtable ），該表是一個一維數(shù)組，在這個數(shù)組中存放每個虛函數(shù)的地址。那么如何定位虛表呢編譯器另外還為每個類的對象提供了一個虛表指針（即vptr），這個指針指向了對象所屬類的虛表。在程序運行時，根據(jù)對象的類型去初始化vptr，從而讓vptr正確的指向所屬類的虛表，從而在調(diào)用虛函數(shù)時，就能夠找到正確的函數(shù)。對于例 1-2的程序，由于pAn 實際指向的對象類型是fish ，因此 vptr指向的 fish類的 vtable ，當(dāng)調(diào)用 pAn-breathe()時，根據(jù)虛表中的函數(shù)地址找到的就是fish類的 breathe()

11、函數(shù)。那么虛表指針在什么時候，或者說在什么地方初始化呢答案是在構(gòu)造函數(shù)中進(jìn)行虛表的創(chuàng)建和虛表指針的初始化。還記得構(gòu)造函數(shù)的調(diào)用順序嗎，在構(gòu)造子類對象時， 要先調(diào)用父類的構(gòu)造函數(shù)， 此時編譯器只“看到了”父類，并不知道后面是否后還有繼承者，它初始化父類對象的虛表指針，該虛表指針指向父類的虛表。當(dāng)執(zhí)行子類的構(gòu)造函數(shù)時， 子類對象的虛表指針被初始化，指向自身的虛表。 對于例 2-2 的程序來說，當(dāng) fish 類的 fh 對象構(gòu)造完畢后，其內(nèi)部的虛表指針也就被初始化為指向fish類的虛表。在類型轉(zhuǎn)換后，調(diào)用pAn-breathe() ，由于 pAn 實際指向的是fish 類的對象，該對象內(nèi)部的虛表指針

12、指向的是fish 類的虛表，因此最終調(diào)用的是fish類的 breathe()函數(shù)。要注意： 對于虛函數(shù)調(diào)用來說，每一個對象內(nèi)部都有一個虛表指針，該虛表指針被初始化為本類的虛表。 所以在程序中， 不管你的對象類型如何轉(zhuǎn)換，但該對象內(nèi)部的虛表指針是固定的，所以呢，才能實現(xiàn)動態(tài)的對象函數(shù)調(diào)用，這就是C+多態(tài)性實現(xiàn)的原理。6、STL是什么組成部分和核心作用標(biāo)準(zhǔn)模板庫于1994 年 2 月年正式成為ANSI/ISO C+ 的一部份，它的出現(xiàn)，促使的思維方式更朝向泛型編程（generic program）發(fā)展。C+程序員7、闡述 C+在什么情況下必須進(jìn)行運算符重載。8、 為什么說“繼承是C+面向?qū)ο蟮囊粋€

13、主要特征之一”，請做一下簡要說明。9 、請 說 明 函 數(shù) 模 板 (Functionspecification)的區(qū)別和聯(lián)系。Template)和 函 數(shù) 模 板 實 例 化 (function-template函數(shù)模板實例化在函數(shù)模板為每個類型時首先調(diào)用中，編譯器創(chuàng)建一個實例化。 每個實例化是為該類型的該模板化功能的版本。 在中，此函數(shù)為類型時，使用此實例化將調(diào)用。 如果您有幾個相同的實例化，即使在不同的模塊，因此，只有該實例化的一個副本在可執(zhí)行文件將結(jié)果。函數(shù)參數(shù)將所有參數(shù)的函數(shù)模板允許和參數(shù)，對該參數(shù)不依賴于模板參數(shù)的位置。函數(shù)模板可以通過聲明與特定類型的模板顯式實例化作為參數(shù)。C+中

14、提供了函數(shù)模板，實際上是建立一個通用函數(shù)，其函數(shù)類型和形參類型不具體指定，用一個虛擬的類型來代表，這個通用函數(shù)就成為函數(shù)模板。使用模板的好處就是對于那些函數(shù)體相同的函數(shù)都可以用這個模板來代替，而不必去定義每個具體的函數(shù)去實現(xiàn)。下面通過一個簡單的具體例子（比較兩個數(shù)的大?。﹣碚f明：#include using namespace std;templatepp 文件中還有其他許多預(yù)處理指令這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應(yīng)不同的計算機(jī)和操作系統(tǒng)環(huán)境的限制。 一個環(huán)境需要的代碼跟另一個環(huán)境所需的代碼可能有所不同，因為可用的硬件或操作系統(tǒng)是不同的。在許多情況下， 可以把用于不同環(huán)

15、境的代碼放在同一個文件中，再在預(yù)處理階段修改代碼，使之適應(yīng)當(dāng)前的環(huán)境。預(yù)處理器顯示為一個獨立的操作，但一般不能獨立于編譯器來執(zhí)行這個操作。調(diào)用編譯器會自動執(zhí)行預(yù)處理過程，之后才編譯代碼。編譯器為給定源文件輸出的是機(jī)器碼，執(zhí)行這個過程需要較長時間。在對象文件之間并沒有建立任何連接。 對應(yīng)于某個源文件的對象文件包含在其他源文件中定義的函數(shù)引用或其他指定項的引用，而這些函數(shù)或項仍沒有被解析。同樣，也沒有建立同庫函數(shù)的鏈接。實際上，這些函數(shù)的代碼并不是文件的一部分。這些工作是由鏈接程序( 有時稱為鏈接編輯器) 完成的鏈接程序把所有對象文件中的機(jī)器碼組合在一起，并解析它們之間的交叉引用。它還集成了對象模

16、塊所使用的庫函數(shù)的代碼。這是鏈接程序的一種簡化表示，因為這里假定在可執(zhí)行模塊中， 模塊之間的所有鏈接都是靜態(tài)建立的。實際上有些鏈接是動態(tài)的，即這些鏈接是在程序執(zhí)行時建立的。鏈接程序靜態(tài)地建立函數(shù)之間的鏈接，即在程序執(zhí)行之前建立組成程序的源文件中所包含的函數(shù)鏈接。動態(tài)建立的函數(shù)之間的鏈接( 在程序執(zhí)行過程中建立的鏈接) 將函數(shù)編譯并鏈接起來，創(chuàng)建另一種可執(zhí)行模塊動態(tài)鏈接庫或共享庫。動態(tài)鏈接庫中的函數(shù)鏈接是在程序調(diào)用函數(shù)時才建立的，在程序調(diào)用之前，該鏈接是不存在的。動態(tài)鏈接庫有幾個重要的優(yōu)點。一個主要的優(yōu)點是動態(tài)鏈接庫中的函數(shù)可以在幾個并行執(zhí)行的程序之間共享， 這將節(jié)省相同函數(shù)占用的內(nèi)存空間。另一

17、個優(yōu)點是動態(tài)鏈接庫在調(diào)用其中的函數(shù)之前是不會加載到內(nèi)存中的。也就是說， 如果不使用給定動態(tài)鏈接庫中的函數(shù)，該動態(tài)鏈接庫就不會占用內(nèi)存空間11、解釋“優(yōu)先級隊列”這一抽象數(shù)據(jù)類型及實現(xiàn)方法如果我們給每個元素都分配一個數(shù)字來標(biāo)記其優(yōu)先級，不妨設(shè)較小的數(shù)字具有較高的優(yōu)先級，這樣我們就可以在一個集合中訪問優(yōu)先級最高的元素并對其進(jìn)行查找和刪除操作了。這樣，我們就引入了優(yōu)先級隊列這種數(shù)據(jù)結(jié)構(gòu)。缺省情況下，優(yōu)先級隊列利用一個最大堆完成函數(shù)列表：empty()如果優(yōu)先隊列為空，則返回真pop()刪除第一個元素push()加入一個元素size()返回優(yōu)先隊列中擁有的元素的個數(shù)top()返回優(yōu)先隊列中有最高優(yōu)先級

18、的元素用途就不用多說了吧，例如 Huffman 編碼、 分支限界、 A* 啟發(fā)式都需要用到優(yōu)先隊列存放信息。12、逆波蘭式用什么數(shù)據(jù)結(jié)構(gòu)算法的效率比較高，為什么13、C 和 C+，C+和 Java 的區(qū)別C 是一個結(jié)構(gòu)化語言，如譚老爺子所說：它的重點在于算法和數(shù)據(jù)結(jié)構(gòu)。C 程序的設(shè)計首要考慮的是如何通過一個過程，對輸入（或環(huán)境條件） 進(jìn)行運算處理得到輸出（或?qū)崿F(xiàn)過程 （事務(wù)）控制），而對于C+，首要考慮的是如何構(gòu)造一個對象模型，讓這個模型能夠契合與之對應(yīng)的問題域，這樣就可以通過獲取對象的狀態(tài)信息得到輸出或?qū)崿F(xiàn)過程（事務(wù)）控制。所以 C 與 C+的最大區(qū)別在于它們的用于解決問題的思想方法不一樣。

19、之所以說C+比 C 更先進(jìn)，是因為面向?qū)?4、什么是預(yù)處理程序設(shè)計中的預(yù)處理(Preprocess)，程序設(shè)計領(lǐng)域， 預(yù)處理是在程序源代碼被編譯之前，由預(yù)處理器 （ Preprocessor）對程序源代碼進(jìn)行的處理。這個過程并不對程序的源代碼進(jìn)行解析，但它把源代碼分割或處理成為特定的符號用來支持宏調(diào)用。預(yù)處理器的主要作用就是把通過預(yù)處理的內(nèi)建功能對一個資源進(jìn)行等價替換，最常見的預(yù)處理有：文件包含，條件編譯、布局控制和宏替換4 種。15、堆和棧的區(qū)別棧區(qū)（ stack ） 由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。堆棧（英文： stack ），也可直

20、接稱棧。臺灣作堆疊，在計算機(jī)科學(xué)中，是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指標(biāo)，英文為top ）進(jìn)行加入資料（push）和輸出資料（pop）的運算。另外堆棧也可以用一維陣列或連結(jié)串行的形式來完成。堆棧的另外一個相對的操作方式稱為佇列。由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, LastIn First Out）的原理運作。堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作：推入（push）和彈出（ pop）：17、簡述在面向?qū)ο蟪绦蛟O(shè)計中，引入繼承和封裝的主要作用繼承：代碼重用封裝：代碼安全18、簡述 C語言中指針及其作用19、 Java

21、 語言的多線程機(jī)制20、簡述四種常見的數(shù)據(jù)邏輯結(jié)構(gòu) 集合集合中任何兩個數(shù)據(jù)元素之間都沒有邏輯關(guān)系，組織形式松散。 圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)中的結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接21、簡述在一棵二叉排序樹中查找一特定元素x 的算法過程二叉排序樹（ Binary Sort Tree）又稱二叉查找樹。它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（ 1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（ 2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；在最壞的情況是，兩子數(shù)列擁有大各為1和 n-1 ，且調(diào)用樹 （ calltree ）變

22、成為一個n個嵌套（ nested ）調(diào)用的線性連串（chain ）。第 i次調(diào)用作了O(n-i)的工作量，且遞歸關(guān)系式為：這與插入排序和選擇排序有相同的關(guān)系式，以及它被解為T(n) = O(n2)。它的最壞情況是很恐怖的，需要空間，遠(yuǎn)比數(shù)列本身還多。23、簡述在一帶權(quán)有向圖中尋找關(guān)鍵路徑的基本思想關(guān)鍵路徑： 關(guān)鍵路徑是指網(wǎng)絡(luò)終端元素的元素的序列， 該序列具有最長的總工期并決定了整個項目的最短完成時間。 在 AOE網(wǎng)中，從始點到終點具有最大路徑長度 （該路徑上的各個活動所持續(xù)的時間之和）的路徑為關(guān)鍵路徑 關(guān)鍵活動：關(guān)鍵路徑上的活動稱為關(guān)鍵活動。只有所有關(guān)鍵活動提前完成，整個工程才能提前完成。最早

23、可能開始時間Vei：從原點到頂點Vi 最長路徑的長度（之前所有事情做完了才可能開始）； 最遲允許開始時間Vli：保證匯點Vn-1 在 Ven-1 時刻完成的前提下（整體工期不拖），事件 Vi 最遲允許的開始時間。Vli=minVlk-dur()關(guān)鍵活動：松弛時間(slack time)Alj-Aek=0的節(jié)點。24、類作用域和文件作用域的區(qū)別是什么文件作用域也稱“全局作用域”。定義在所有函數(shù)之外的標(biāo)識符，具有文件作用域，作用域為從定義處到整個源文件結(jié)束。文件中定義的全局變量和函數(shù)都具有文件作用域。如果某個文件中說明了具有文件作用域的標(biāo)識符，該文件又被另一個文件包含，則該標(biāo)識符的作用域延伸到新的

24、文件中。如cin和 cout 是在頭文件中說明的具有文件作用域的標(biāo)識符，它們的作用域也延伸到嵌入的文件中。操作系 1. 程和 程的區(qū) 及 系，操作系 的程序 程和 程的區(qū) ：1、 程是 程的一部分，所以 程有的 候被稱 是 程或者 量 程。2、 一個沒有 程的 程是可以被看作 程的，如果一個 程內(nèi) 有多個 程， 程的 行 程不是一條 （ 程）的，而是多條 （ 程）共同完成的。3、 系 在運行的 候會 每個 程分配不同的內(nèi)存區(qū)域， 但是不會 程分配內(nèi)存 （ 程所使用的 源是它所屬的 程的 源） ， 程 只能共享 源。 那就是 ， 出了 CPU之外（ 程在運行的 候要占用 CPU 源）， 算機(jī)內(nèi)部

25、的 硬件 源的分配與 程無關(guān)， 程只能共享它所屬 程的 源。4、 與 程的控制表PCB相似， 程也有自己的控制表TCB，但是 TCB中所保存的 程狀 比 PCB表中少多了（上下文保存一下就行）。5、 程是系 所有 源分配 候的一個基本 位， 有一個完整的虛 空 地址，并不依 程而獨立存在。 程與程序的區(qū) ：程序是一 指令的集合，它是靜 的 體，沒有 行的含 。而 程是一個 的 體，有自己的生命周期。一般 來，一個 程肯定與一個程序相 ，并且只有一個，但是一個程序可以有多個 程，或者一個 程都沒有也可以只有一個 程。除此之外， 程 有并 性和交往性。 地 ， 程是程序的一部分，程序運行的 候會

26、生 程。 ： 程是 程的一部分， 程是程序的一部分。前一句 的不太準(zhǔn)確， 程也有自己的 源， 比如 ，私有數(shù)據(jù)等等。 他使用而不 有 源指的是使用的是 程的打開文件句柄， 程的全局?jǐn)?shù)據(jù)， 程的地址空 等等 , 些都屬于 程，而不屬于 程， 程內(nèi)個 程共享。進(jìn)程切換比線程切換開銷大是因為進(jìn)程切換時要切頁表，而且往往伴隨著頁調(diào)度，因為進(jìn)程的數(shù)據(jù)段代碼段要換出去，以便把將要執(zhí)行的進(jìn)程的內(nèi)容換進(jìn)來。本來進(jìn)程的內(nèi)容就是線程的超集。而且線程只需要保存線程的上下文（相關(guān)寄存器狀態(tài)和棧的信息）就好了，動作很小。2. OS 里面進(jìn)程的“三態(tài)”“五態(tài)”“七態(tài)”是什么3. 什么是操作系統(tǒng)4. 死鎖的條件，檢測死鎖的

27、可能方法及其基本思想A deadlock is a situation in which two or more competing actions are each waitingfor the other to finish, and thus neither ever does.1.（互斥） : At leasttwo resourcesmust be non-shareable.1Only one processcanuse the resource at any given instant of time.2. Hold and Wait or Resource Holding: A

28、 process is currently holding at least one resource and requestingadditional resources which are being held by other processes.3. No（禁止搶占）: The operating system must not de-allocate resources once theyhave beenallocated; they must be released by the holding process voluntarily.4. A processmust be wa

29、itingfora resourcewhich isbeing heldby anotherprocess,which in turniswaitingforthefirstprocesstoreleasetheresource.Ingeneral,there is a of waitingprocesses, P = P1, P2, ., PN, such that P1 is waiting for a resource held byP2, P2 is waitingfora resourceheld by P3 and so on untilPN is waitingfora reso

30、urceheld by P1.17ThesefourconditionsareknownastheCoffmanconditionsfromtheirfirstdescription in a 1971 articleby 7 Unfulfillment of any of these conditions is enough to preclude a deadlockfrom occurring.Ensure that the system will never enter a deadlock state.Prevention: Ensure one of the four condit

31、ions fails.Avoidance: The OS needs more information so that it can determine if the currentrequest can be satisfied ordelayed.死鎖檢測：1. Resource-Allocation Graph2. Detection Algorithm5. 用戶態(tài)和內(nèi)核態(tài)當(dāng)程序運行在3 級特權(quán)級上時， 就可以稱之為運行在用戶態(tài)，因為這是最低特權(quán)級，是普通的用戶進(jìn)程運行的特權(quán)級，大部分用戶直接面對的程序都是運行在用戶態(tài)；反之，當(dāng)程序運行在級特權(quán)級上時，就可以稱之為運行在內(nèi)核態(tài)。用戶態(tài)切換

32、到內(nèi)核態(tài)的3 種方式a. 系統(tǒng)調(diào)用這是用戶態(tài)進(jìn)程主動要求切換到內(nèi)核態(tài)的一種方式，用戶態(tài)進(jìn)程通過系統(tǒng)調(diào)用申請使用操作系統(tǒng)提供的服務(wù)程序完成工作，比如前例中fork()實際上就是執(zhí)行了一個創(chuàng)建新進(jìn)程的系統(tǒng)調(diào)用。而系統(tǒng)調(diào)用的機(jī)制其核心還是使用了操作系統(tǒng)為用戶特別開放的一個中斷來實現(xiàn)，例如 Linux 的 int 80h中斷。b. 異常當(dāng) CPU在執(zhí)行運行在用戶態(tài)下的程序時，發(fā)生了某些事先不可知的異常，這時會觸發(fā)由當(dāng)前運行進(jìn)程切換到處理此異常的內(nèi)核相關(guān)程序中，也就轉(zhuǎn)到了內(nèi)核態(tài)，比如缺頁異常。c. 外圍設(shè)備的中斷當(dāng)外圍設(shè)備完成用戶請求的操作后，會向 CPU發(fā)出相應(yīng)的中斷信號，這時 CPU會暫停執(zhí)行下一條

33、即將要執(zhí)行的指令轉(zhuǎn)而去執(zhí)行與中斷信號對應(yīng)的處理程序，如果先前執(zhí)行的指令是用戶態(tài)下的程序， 那么這個轉(zhuǎn)換的過程自然也就發(fā)生了由用戶態(tài)到內(nèi)核態(tài)的切換。比如硬盤讀寫操作完成，系統(tǒng)會切換到硬盤讀寫的中斷處理程序中執(zhí)行后續(xù)操作等。這 3 種方式是系統(tǒng)在運行時由用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)的最主要方式，其中系統(tǒng)調(diào)用可以認(rèn)為是用戶進(jìn)程主動發(fā)起的，異常和外圍設(shè)備中斷則是被動的。6. 面包店算法該算法的基本思想源于顧客在面包店中購買面包時的排隊原理. 顧客在進(jìn)入面包店前 ,首先抓一個號 , 然后按照號碼由小到大的次序依次進(jìn)入面包店購買面包. 這里 , 面包店發(fā)放的號碼是由小到大的 , 但是兩個或兩個以上的顧客卻有可能得到相

34、同的號碼( 使所抓號碼不同需要互斥 ), 如果多個顧客抓到相同的號碼,則規(guī)定按照顧客名字的字典次序進(jìn)行排序,這里假定顧客是沒有重名的. 在計算機(jī)系統(tǒng)中,顧客就相當(dāng)于進(jìn)程,每個進(jìn)程有一個唯一的標(biāo)識 , 我們用 P的下面加一個下標(biāo)來表示 .例如 : 對于 Pi和 Pj,如果有 ij, 則先為 Pi服務(wù) , 即 Pi 先進(jìn)入臨界區(qū)7. 系統(tǒng)調(diào)用和庫函數(shù)的區(qū)別(1) 調(diào)用形式不同。過程（函數(shù)）使用一般調(diào)用指令，其轉(zhuǎn)向地址是固定不變的，包含在跳轉(zhuǎn)語句中；但系統(tǒng)調(diào)用中不包含處理程序入口，而僅僅提供功能號，按功能號調(diào)用。(2) 被調(diào)用代碼的位置不同。過程（函數(shù)）調(diào)用是一種靜態(tài)調(diào)用，調(diào)用者和被調(diào)用代碼在同一程

35、序內(nèi)，經(jīng)過連接編輯后作為目標(biāo)代碼的一部份。當(dāng)過程（函數(shù)）升級或修改時，必須重新編譯連結(jié)。 而系統(tǒng)調(diào)用是一種動態(tài)調(diào)用，系統(tǒng)調(diào)用的處理代碼在調(diào)用程序之外（在操作系統(tǒng)中），這樣一來，系統(tǒng)調(diào)用處理代碼升級或修改時，與調(diào)用程序無關(guān)。而且，調(diào)用程序的長度也大大縮短，減少了調(diào)用程序占用的存儲空間。(3) 提供方式不同。過程（函數(shù)）往往由編譯系統(tǒng)提供，不同編譯系統(tǒng)提供的過程（函數(shù)）可以不同；系統(tǒng)調(diào)用由操作系統(tǒng)提供，一旦操作系統(tǒng)設(shè)計好，系統(tǒng)調(diào)用的功能、種類與數(shù)量便固定不變了。(4) 調(diào)用的實現(xiàn)不同。程序使用一般機(jī)器指令（跳轉(zhuǎn)指令）來調(diào)用過程（函數(shù)），是在用戶態(tài)運行的；程序執(zhí)行系統(tǒng)調(diào)用，是通過中斷機(jī)構(gòu)來實現(xiàn)，需要

36、從用戶態(tài)轉(zhuǎn)變到核心態(tài)，在管理狀態(tài)執(zhí)行，因此，安全性好。8. 經(jīng)典進(jìn)程同步問題是什么，同步思想生產(chǎn)者 - 消費者問題是著名的進(jìn)程同步問題，它描述一組生產(chǎn)者進(jìn)程向一組消費者進(jìn)程提供消息。它們共享一個有界緩沖池，生產(chǎn)者向其中投放消息，消費者從中取得消息。生產(chǎn)者-消費者問題是許多相互合作進(jìn)程的一種抽象。假定緩沖池中有n 個緩沖區(qū)， 每個緩沖區(qū)存放一個消息。 由于緩沖池是臨界資源，它只允許一個生產(chǎn)者投入消息，或者一個消費者從中取出消息。生產(chǎn)者之間、生產(chǎn)者與消費者之間、消費者之間都必須互斥地使用緩沖池。所以必須設(shè)置互斥信號量mutex，它代表緩沖池資源，它的數(shù)值為1。 讀者 - 寫者問題問題描述：一個數(shù)據(jù)

37、集（如文件）被幾個并行進(jìn)程所共享，有些進(jìn)程只要求讀數(shù)據(jù)集內(nèi)容，稱為讀者，而另一些進(jìn)程則要求修改數(shù)據(jù)集內(nèi)容，稱為寫者，幾個讀者可以同時讀數(shù)據(jù)集，而不需要互斥， 但一個寫者不能和其他進(jìn)程（不管是寫者或讀者）同時訪問這些數(shù)據(jù)集，它們之間必須互斥。哲學(xué)家進(jìn)餐問題該問題描述如下：有五個哲學(xué)家， 他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們公用一張圓桌， 周圍放有五把椅子，每人坐一把。 在圓桌上有五個碗和五根筷子，當(dāng)一個哲學(xué)家思考時，他不與其他人交談，饑餓時便試圖取用其左、右最靠近他的筷子，但他可能一根都拿不到。只有在他拿到兩根筷子時，方能進(jìn)餐，進(jìn)餐完后，放下筷子又繼續(xù)思考。9. 文件管理及組織， FA

38、T FAT = File Allocation Table10. 設(shè)備驅(qū)動程序是否屬于 OS，他的作用是什么不是，驅(qū)動程序是另外安裝的軟件，是操作系統(tǒng)控制并且和硬件之間通訊的橋梁（程序）11. 程序和任務(wù)的區(qū)別任務(wù)是最抽象的， 是一個一般性的術(shù)語， 指由軟件完成的一個活動。一個任務(wù)既可以是一個進(jìn)程 , 也可以是一個線程。 簡而言之 , 它指的是一系列共同達(dá)到某一目的的操作。例如 , 讀取數(shù)據(jù)并將數(shù)據(jù)放入內(nèi)存中。這個任務(wù)可以作為一個進(jìn)程來實現(xiàn), 也可以作為一個線程（或作為一個中斷任務(wù)）來實現(xiàn)。進(jìn)程常常被定義為程序的執(zhí)行。可以把一個進(jìn)程看成是一個獨立的程序 , 在內(nèi)存中有其完備的數(shù)據(jù)空間和代碼空間

39、。一個進(jìn)程所擁有的數(shù)據(jù)和變量只屬于它自己。 線程則是某一進(jìn)程中一路單獨運行的程序。也就是說，線程存在于進(jìn)程之中。一個進(jìn)程由一個或多個線程構(gòu)成，各線程共享相同的代碼和全局?jǐn)?shù)據(jù)，但各有其自己的堆棧。由于堆棧是每個線程一個，所以局部變量對每一線程來說是私有的。由于所有線程共享同樣的代碼和全局?jǐn)?shù)據(jù)，它們比進(jìn)程更緊密，比單獨的進(jìn)程間更趨向于相互作用, 線程間的相互作用更容易些 , 因為它們本身就有某些供通信用的共享內(nèi)存：進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程：資源分配、調(diào)度運行的基本單位。線程：進(jìn)程中執(zhí)行運算的最小單位，執(zhí)行處理機(jī)調(diào)度的基本單位。12. 數(shù)據(jù)庫安全性和操作系統(tǒng)安全性

40、的關(guān)系安全性問題不是數(shù)據(jù)庫系統(tǒng)所獨有的, 所有計算機(jī)系統(tǒng)都有這個問題. 只是在數(shù)據(jù)庫系統(tǒng)中大量數(shù)據(jù)集中存放, 而且為許多最終用戶直接共享, 從而使安全性問題更為突出. 系統(tǒng)安全保護(hù)措施是否有效是數(shù)據(jù)庫系統(tǒng)的主要指標(biāo)之一. 數(shù)據(jù)庫的安全性和計算機(jī)系統(tǒng)的安全性, 包括操作系統(tǒng) , 網(wǎng)絡(luò)系統(tǒng)的安全性是緊密聯(lián)系, 相互支持的 .13. 中斷處理的過程請求中斷響應(yīng)中斷關(guān)閉中斷保留斷點中斷源識別保護(hù)現(xiàn)場中斷服務(wù)子程序恢復(fù)現(xiàn)場中斷返回在實際運行中，一旦設(shè)備通過某引腳N 向 8259A 發(fā)出中斷指令，后者便向 8086A 的 INTR 引腳發(fā)送中斷信號。 8086A 通過 INTA 引腳通知8259A 中斷有

41、效（這個過程實際上還包括對此8259A 的選址），后者即通過地址總線將對應(yīng)引腳N 的中斷類型碼（已預(yù)先存好，見上節(jié)）發(fā)送給CPU。 CPU得到中斷類型碼后，先進(jìn)行現(xiàn)場保護(hù)，主要包括：1. 狀態(tài)寄存器 FLAGS壓棧（同時堆棧寄存器 SP-2）；2. 關(guān)閉中斷（將 FLAGS寄存器的 IF 位置零）；3.將當(dāng)前代碼段寄存器CS和程序計數(shù)器IP 壓棧（同時堆棧寄存器SP-4）。 現(xiàn)場保護(hù)完成后， CPU開始按照前述的兩步驟翻譯中斷程序入口地址。在得到中斷處理程序地址之后但調(diào)用中斷處理程序之前，CPU會再檢查一下NMI引腳是否有信號，以防在剛才的處理過程中忽略了可能的NMI 中斷。 NMI 的優(yōu)先級

42、始終高于INTR。中斷處理程序雖然是由程序員編寫，但須循一定規(guī)范。作為例程， 中斷處理程序應(yīng)該先將各寄存器信息（除了IP 和 CS，此二寄存器現(xiàn)已指向當(dāng)前中斷程序）壓入堆棧予以保存，這樣才能在中斷處理程序內(nèi)部使用這些寄存器。在程序結(jié)束時， 應(yīng)該按與壓棧保護(hù)時相反的順序彈出各寄存器的值。中斷程序的最后一句始終是IRET 指令，這條指令將棧頂6 個字節(jié)分別彈出并存入IP 、 CS和 FLAGS寄存器，完成了現(xiàn)場的還原。當(dāng)然， 如果是操作系統(tǒng)的中斷處理程序，則未必通常不會還原中斷前的狀態(tài)。這樣的中斷處理程序通常會在調(diào)用完寄存器保存例程后，調(diào)用進(jìn)程調(diào)度程序（多由高級語言編寫），并決定下一個運行的進(jìn)程。

43、隨后將此進(jìn)程的寄存器信息（上次中斷時保存下來的）存入寄存器并返回。在中斷程序結(jié)束之后，主程序也發(fā)生了改變。14. 計算機(jī)系統(tǒng)怎樣實現(xiàn)存儲保護(hù)1. 防止地址越界（對進(jìn)程所產(chǎn)生的地址必須加以檢查，發(fā)生越界時產(chǎn)生中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理）2. 防止操作越權(quán)（對屬于自己區(qū)域的信息，可讀可寫：對公共區(qū)域中允許共享的信息或獲得授權(quán)可使用的信息，可讀而不可修改；對未授權(quán)使用的信息，不可讀，不可寫）15.調(diào)度的基本準(zhǔn)則(Scheduling Criteria)There are many criteriaforcomparing differentschedulingalgorithms.Here are fivecommon ones: CPU utilization(CPU利用率 )Throughput （吞吐量）Turnaround time（周轉(zhuǎn)時間）Waiting time（等待時間）Response time （響應(yīng)時間）16. 多線程是否真正能提高效率17. 磁盤調(diào)度算法有哪幾種FCF