一、數(shù)據(jù)庫部分

數(shù)據(jù)庫緒論
1、簡述三層模式、兩級映射，分別有什么作用？
模式（邏輯模式）：是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述，是數(shù)據(jù)庫系統(tǒng)模式結(jié)構(gòu)的中間層，即不涉及數(shù)據(jù)的物理存儲細節(jié)，也與具體應用程序開發(fā)工具語言無關(guān)。
外模式（用戶模式）：是用戶能看見和使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征描述，是與某一應用有關(guān)的數(shù)據(jù)的邏輯表示，是模式的子集，一個數(shù)據(jù)庫可以有多個外模式。
內(nèi)模式（存儲模式）：數(shù)據(jù)物理結(jié)構(gòu)和存儲方式的描述，是數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式，如存儲方式是按照某個屬性升序存儲，什么索引等。
外模式模式映像：當模式發(fā)生改變，數(shù)據(jù)庫管理員對外模式模式映像作相應改變，可使外模式不變，從而應用程序不用修改。保證數(shù)據(jù)與程序的邏輯獨立性。
模式內(nèi)模式映像：當數(shù)據(jù)庫的存儲結(jié)構(gòu)改變了，由數(shù)據(jù)庫管理員對模式內(nèi)模式映像作相應改變，可以保持模式不變，從而應用程序也不必改變，保證了數(shù)據(jù)與程序的物理獨立性。
三級模式使用戶能邏輯地抽象地處理數(shù)據(jù)而不關(guān)心數(shù)據(jù)在計算機內(nèi)具體表示方式與存儲方式，兩級映像保證了數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)有較高的邏輯獨立性和物理獨立性。

2、說出至少三種數(shù)據(jù)庫類型（層次，網(wǎng)狀，關(guān)系）并簡要解釋了一下
層次模型：用樹形結(jié)構(gòu)來表示各類實體以及實體間的聯(lián)系，有且只有一個節(jié)點沒有雙親節(jié)點（根節(jié)點），其他的都有且只有一個雙親節(jié)點。只能直接表示的是一對多聯(lián)系。
優(yōu)點：效率高結(jié)構(gòu)清晰，性能優(yōu)于關(guān)系數(shù)據(jù)庫，不低于網(wǎng)狀。
缺點：現(xiàn)實世界很多聯(lián)系都不是層次的，如節(jié)點間多對多聯(lián)系，還有一個節(jié)點具有多個雙親的情況都不好表示。

網(wǎng)狀模型：對于非層次關(guān)系的聯(lián)系，用層次表示非樹形結(jié)構(gòu)是很不直接的，網(wǎng)狀模型可以很好的表示，它允許有一個以上的節(jié)點沒有雙親，一個節(jié)點也可以有多個雙親，可以更直接地描述現(xiàn)實世界。
優(yōu)點：更直接描述現(xiàn)實世界，性能也較好，存取效率也較高。
缺點：結(jié)構(gòu)比較復雜不利于掌握，用戶編程還得了解系統(tǒng)結(jié)構(gòu)細節(jié)，加重了編程的負擔。

關(guān)系模型：通常來看關(guān)系就是一張規(guī)范二維表，實體還是實體間的聯(lián)系都用關(guān)系來表示，對數(shù)據(jù)的檢索和更新結(jié)果也是關(guān)系。
優(yōu)點：概念單一，用戶易懂易用，而且存取路徑是對用戶透明的，從而有更高的數(shù)據(jù)獨立性和安全性，也簡化程序員的工作。
缺點：查詢效率往往不如格式化數(shù)據(jù)模型，為了提高性能，增加開發(fā)DBMS難度。

關(guān)系數(shù)據(jù)庫
3、簡述關(guān)系與關(guān)系模式的區(qū)別。
關(guān)系實質(zhì)是一張二維表，關(guān)系模式是對關(guān)系的描述，關(guān)系是關(guān)系模式在某一時刻的狀態(tài)或內(nèi)容。
關(guān)系模式是靜態(tài)的、穩(wěn)定的，而關(guān)系是動態(tài)的，隨時間不斷變化的，因為關(guān)系操作不斷更新數(shù)據(jù)庫中的數(shù)據(jù)。
通俗的說：關(guān)系是一張二維表，關(guān)系模式是表格的描述（表頭），關(guān)系名是表名，元組是一行，屬性是列，分量是一條記錄中的一個列值。

4、什么是關(guān)系數(shù)據(jù)庫？關(guān)系和二維表有什么區(qū)別？
關(guān)系數(shù)據(jù)庫，是建立在關(guān)系數(shù)據(jù)庫模型基礎(chǔ)上的數(shù)據(jù)庫，借助于集合代數(shù)等概念和方法來處理數(shù)據(jù)庫中的數(shù)據(jù)。
在關(guān)系模型中，數(shù)據(jù)結(jié)構(gòu)表示為一個二維表，一個關(guān)系就是一個二維表（但不是任意一個二維表都能表示一個關(guān)系。表中的第一行通常稱為屬性名，表中的每一個元組和屬性都是不可再分的，且元組的次序是無關(guān)緊要的。

5、關(guān)系的完整性（實體完整性、參照完整性、用戶自定義）和數(shù)據(jù)庫主鍵的約束性
實體完整性：關(guān)系的主碼不能取空值，如果主碼由若干屬性組成都不能為空。實體以主碼作為唯一性標識。
參照完整性：一個關(guān)系中的外碼，或者取空值（若屬性組全為空），或者等于它參照的那個關(guān)系的主碼值。
用戶自定義完整性：針對具體關(guān)系數(shù)據(jù)庫的約束。

數(shù)據(jù)庫語言SQL
6、什么是DDL、DML、DCL？（數(shù)據(jù)庫語言有哪幾種？）
數(shù)據(jù)定義語言（DDL）：Create、Drop、Alter
數(shù)據(jù)操縱語言（DML）：Insert、Update、Delete
數(shù)據(jù)控制語言（DCL）：Grant、Revoke
數(shù)據(jù)查詢語言：Select

7、什么是視圖，有什么作用？在數(shù)據(jù)庫哪層？
視圖：是從一個或幾個基本表導出的表，是一個虛表，數(shù)據(jù)庫只存放視圖的定義，不存放視圖對應的數(shù)據(jù)，數(shù)據(jù)仍放在原來的基本表，基本表數(shù)據(jù)改變，通過視圖查詢也改變了，

數(shù)據(jù)庫設(shè)計
8、簡述數(shù)據(jù)庫設(shè)計的幾個階段
需求分析：詳細調(diào)查現(xiàn)實世界要處理的對象，充分了解各種需求，在此基礎(chǔ)確定新系統(tǒng)的功能。
概念結(jié)構(gòu)設(shè)計：經(jīng)常采用自頂向下需求分析，自底向上概念結(jié)構(gòu)設(shè)計。對需求分析收集到的數(shù)據(jù)進行分類組織形成實體、實體的屬性，確定實體之間聯(lián)系，設(shè)計分E-R圖。逐一設(shè)計分E-R圖，最后將所有分E-R圖綜合成一個系統(tǒng)的E-R圖。
邏輯結(jié)構(gòu)設(shè)計：一般來講把E-R圖向關(guān)系模型轉(zhuǎn)換，一個實體型轉(zhuǎn)換為一個關(guān)系模式。一個一對一聯(lián)系可以獨立也可以和任意一端合并，一個一對多聯(lián)系可以獨立也可以和N端對應的關(guān)系模式合并，一個多對多聯(lián)系獨立轉(zhuǎn)換為一個關(guān)系模式。對數(shù)據(jù)模型規(guī)范化，還根據(jù)具體需求設(shè)計相應的視圖。
數(shù)據(jù)庫物理設(shè)計：關(guān)系模式存取方法的選擇，比如索引、聚簇、哈希等存儲方式。還應該確定數(shù)據(jù)庫的存取結(jié)構(gòu)，目前許多計算機有多個磁盤或磁盤陣列，因此可以將表和索引放在不同的磁盤上，在查詢時磁盤驅(qū)動器并行工作，可以提高物理IO讀寫效率，也可以將比較大的表放在兩個磁盤上，以加快存取速度。
數(shù)據(jù)庫的實施與維護：比如備份與恢復等待。

9、什么是E-R圖
E-R圖：實體-聯(lián)系圖，在概念結(jié)構(gòu)設(shè)計中，對需求分析收集到的數(shù)據(jù)進行分類組織,形成實體的屬性，確定實體之間聯(lián)系，設(shè)計E-R圖。

10、分別解釋1NF、2NF、3NF、BCNF、4NF
范式：關(guān)系數(shù)據(jù)庫中的關(guān)系是要滿足一定要求的，滿足不同程度的要求的為不同范式。
規(guī)范化：一個低一級范式關(guān)系模式通過模式分解可以轉(zhuǎn)化為若干個高一級范式的關(guān)系模式的集合。
1NF：滿足最低要求的叫第一范式，每一個分量必須是一個不可分的數(shù)據(jù)項。
2NF：消除關(guān)系中的部分函數(shù)依賴就稱為第二范式，部分函數(shù)依賴就是非主屬性不完全依賴于碼。
3NF：每一個非主屬性既不部分依賴于碼，也不傳遞依賴于碼。
BCND：所有非主屬性對每一個碼都是完全函數(shù)依賴，沒有任何屬性完全依賴于非碼的任何屬性，就是除了碼外一定不能有決定因素。

數(shù)據(jù)庫并發(fā)控制
11、什么是事物，并發(fā)控制是保證事物的？
事物：是一系列的數(shù)據(jù)操作，這些操作要么全不做，要么全做，不可分割。運行過程中發(fā)生某種故障不能繼續(xù)執(zhí)行，全部回滾到開始狀態(tài)。
并發(fā)控制中多個用戶存取數(shù)據(jù)庫時候可能會產(chǎn)生多個事物同時存取同一個數(shù)據(jù)的情況，不加控制就會破壞事物的一致性，為了保證事物的一致性所以進行并發(fā)控制。

12、ACID（事物的四個性質(zhì)）
A原子性：要么都做，要么都不做。
C一致性：如果運行中發(fā)生故障，必須回滾。不能讓數(shù)據(jù)不一致。比如兩人轉(zhuǎn)錢，一半壞了，不一致倆人都沒有錢。
I隔離性：一個事物不能被其他事物干擾。
D持續(xù)性：事物一旦提交，他對數(shù)據(jù)庫的改變就應該是永久的。接下來的操作和故障不應該對剛才結(jié)果有任何影響。

13、數(shù)據(jù)庫中鎖有什么作用？什么是只讀鎖、什么是只寫鎖？
一個事物對數(shù)據(jù)加鎖可以保證事物的四個特性，加鎖后其他事物不能更新此數(shù)據(jù)對象，不會產(chǎn)生數(shù)據(jù)不一致性。
寫鎖（排他鎖/ X鎖）：加寫鎖其他事物不能在對這個數(shù)據(jù)加任何類型鎖，釋放之前不能讀取和修改。
讀鎖（共享鎖/ S鎖）：事物對數(shù)據(jù)加讀鎖，其他事物可以讀但不可以修改，可以加讀鎖不能加寫鎖。

14、什么是觸發(fā)器，有什么作用？
用戶定義在關(guān)系表上的一類由事件驅(qū)動的特殊過程，一旦定義了，用戶對表的增、刪、改操作均有數(shù)據(jù)庫系統(tǒng)自動激活相應觸發(fā)器
觸發(fā)器可以分為語句觸發(fā)器和行級觸發(fā)器，觸發(fā)器動作體是一個匿名PL/SQL過程塊，語句級觸發(fā)器可以在語句執(zhí)行前或后執(zhí)行，而行級觸發(fā)在觸發(fā)器所影響的每一行觸發(fā)一次。行觸發(fā)器用戶可以用new和old引用數(shù)據(jù)，語句級不能。
15、什么是臟讀？幻讀？不可重復讀？
1、臟讀：事務 A 讀取了事務 B 更新的數(shù)據(jù)，然后 B 回滾操作，那么 A 讀取到的數(shù)據(jù)是臟數(shù)據(jù)
2、不可重復讀：事務 A 多次讀取同一數(shù)據(jù)，事務 B 在事務 A 多次讀取的過程中，對數(shù)據(jù)作了更新并提交，導致事務 A 多次讀取同一數(shù)據(jù)時，結(jié)果 不一致。
3、幻讀：系統(tǒng)管理員 A 將數(shù)據(jù)庫中所有學生的成績從具體分數(shù)改為 ABCDE 等級，但是系統(tǒng)管理員 B 就在這個時候插入了一條具體分數(shù)的記錄，當系統(tǒng)管理員 A 改結(jié)束后發(fā)現(xiàn)還有一條記錄沒有改過來，就好像發(fā)生了幻覺一樣，這就叫幻讀。
不可重復讀側(cè)重于修改，幻讀側(cè)重于新增或刪除（多了或少量行），臟讀是一個事務回滾影響另外一個事務。
補：什么是活鎖和死鎖？解決辦法是什么？
1、 活鎖：由于系統(tǒng)調(diào)度原因，某些事務的加鎖請求得不到響應而永遠等待下去，稱為
活鎖。
解決辦法：采用合理的調(diào)度方法，如先來先服務策略。
2、死鎖：兩個或多個事務都已封鎖了一些數(shù)據(jù)對象，然后又都請求對方被封鎖的數(shù)據(jù)對象，兩個事務永遠不能結(jié)束，形成死鎖。
預防：一次封鎖法：要求每個事務必須一次將所有要使用的事務加鎖，否則不能繼續(xù)執(zhí)行。
順序封鎖法：預先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務都按這個順序?qū)嵭蟹怄i。
診斷與解除：超時法：如果一個事務的等待時間超過了規(guī)定的時限，就認為發(fā)生了死鎖。
等待圖法：等待圖是一個有向圖，正運行的事務表示節(jié)點，事務等待的情況表示邊，如果圖中存在回路，則表示系統(tǒng)中存在回路。

二、數(shù)據(jù)結(jié)構(gòu)部分

線性表
15、單鏈表的就地逆置
將頭結(jié)點摘下，然后從第一節(jié)點開始，頭插法建立單鏈表，直到最后一個節(jié)點為止。

16、單鏈表可以用什么實現(xiàn)？
指向結(jié)構(gòu)體的指針實現(xiàn)，結(jié)構(gòu)體中有兩個成員，每個節(jié)點分為數(shù)據(jù)域和指針域，除了最后一個節(jié)點，每個節(jié)點指針域都指向下一個節(jié)點的地址，最后一個節(jié)點指針域指向NULL。
也可以用結(jié)構(gòu)體數(shù)組模擬這種操作，數(shù)組中每個下標都對應一個數(shù)據(jù)元素和游標，游標是下一個元素在數(shù)組中的下標，把未被使用的數(shù)組元素作為備用鏈表，下標為0的元素游標存放備用鏈表第一個節(jié)點的下標。數(shù)組最后一個元素游標存放第一個有效數(shù)值元素的下標，相當于頭結(jié)點作用，游標為0表示指向為空。

棧和隊列
17、實現(xiàn)一個隊列的方法？為什么隊列的順序存儲需要留一個空位？循環(huán)有什么好處？
鏈式存儲：把鏈表改裝一下，加尾指針作為隊列的尾部可以插入節(jié)點，頭指針可以刪除節(jié)點，相當于出隊。
順序存儲：正常的順序存儲想要利用空出的空間就必須移動元素，不移動還會浪費空間，循環(huán)隊列可以解決這個問題，把這段連續(xù)的地址空間，想象成邏輯上的環(huán)，所以只要有空閑空間就能使用。
但是當front和rear指針相等的時候有兩種情況，一種是滿，一種是空，為了區(qū)分這種情況，保留一個元素空間，我們假定當rear+1與front相等隊列就滿了。而空的時候是rear等于front。又因為是環(huán)也可能存在rear>front的情況，所以取模操作。
另外計算隊列長度的時候，rear>front隊長為rear-front，但當rear<front隊長為兩段相加，所以通用公式為（rear-front+隊列的總長度）%隊列總長度

樹與二叉樹
18、什么是完全二叉樹？
完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有N個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應時稱之為完全二叉樹。

19、什么是二叉排序樹，簡述它的查找過程，二叉排序樹的時間復雜度，遍歷后得到什么樣的序列？
二叉排序樹是一種二叉樹，具有了一些獨特性質(zhì)，若左子樹不為空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值，右子樹不為空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值，而且它的左右子樹也是二叉排序樹。構(gòu)造一個二叉排序樹是為了提高動態(tài)查找中插入和刪除的速度。
查找過程：遞歸查找二叉排序樹中是否存在要查關(guān)鍵字，若成功則指針指向該數(shù)據(jù)元素的節(jié)點，返回成功，如果關(guān)鍵字小于樹中這個節(jié)點，則去它左子樹中繼續(xù)查找，大于則去右子樹中查找。如果樹中沒有要查的關(guān)鍵字，則指針指向訪問的上一個節(jié)點，以便于插入。
插入過程：如果當查找失敗且指針p為空，則新建根節(jié)點，如果要插入的關(guān)鍵字小于p指向節(jié)點的數(shù)據(jù)，則插入到左孩子，否則右孩子。
刪除過程：1葉節(jié)點直接刪除2只有左或右子樹刪了接下面3左右子樹都有的，找到要刪除的節(jié)點的直接前驅(qū)或后繼，用這個節(jié)點替換要刪除的節(jié)點，然后在刪除這個節(jié)點。
二叉排序樹，以鏈接的方式存儲，有在執(zhí)行插入或刪除操作時候不用移動元素的優(yōu)點，插入刪除性能較好，而查找的時間復雜度取決與二叉排序樹的形狀。中序遍歷后得到升序系列，所以也稱為二叉排序樹。

20、什么是平衡二叉樹？
為了解決二叉查找樹，查找時間依賴于形狀的問題，平衡二叉樹就是在建立二叉排序樹的時候，對它做了一定的限制，使它保持平衡，使每一個節(jié)點的左子樹和右子樹的高度差至多為1。
具體做法：找出距離插入節(jié)點最近且平衡因子絕對值大于一的節(jié)點，把它當為根的子樹叫做最小不平衡子樹，進行相應旋轉(zhuǎn)，使之平衡。
插入節(jié)點：LL型，向右旋轉(zhuǎn)。RR型，向左旋轉(zhuǎn)。RL型，先右轉(zhuǎn)，再左轉(zhuǎn)。LR型，先左轉(zhuǎn)，再右轉(zhuǎn)。

21、什么是哈夫曼樹？哈夫曼樹的作用是什么？
哈夫曼樹：帶權(quán)路徑長度為從該節(jié)點到樹根之間的路徑長度與節(jié)點上權(quán)的乘積，帶權(quán)路徑長度WPL最小的二叉樹稱作哈夫曼樹。
構(gòu)造過程：把帶有權(quán)值的葉子節(jié)點按照從小到大的順序排列成一個有序序列，取出前兩個最小權(quán)值的節(jié)點作為一個新節(jié)點的兩個子節(jié)點，左孩子一般比右孩子小，新節(jié)點權(quán)值為兩個葉子的和，將新節(jié)點插入剛才有序序列適當位置，重新選出頭兩個最小的，重復上面過程。
哈夫曼編碼：為了解決當年遠距離電報的數(shù)據(jù)傳輸?shù)淖顑?yōu)化問題，發(fā)明了哈夫曼編碼，比如多英文文章傳輸，假設(shè)每個字母固定用一個二進制串表示，文章很長那傳送的串會非常長。但英文字母每個字母出現(xiàn)的頻率是不一樣的，所以可以根據(jù)字母頻率設(shè)定權(quán)值，用哈夫曼樹來規(guī)劃它們，構(gòu)造哈夫曼樹以后，把左分支用0表示，右分支用1表示，然后從根到葉子所經(jīng)過的路徑的數(shù)字用來編碼，當雙方約定好同樣的哈夫曼樹后，發(fā)送信息的時候能明顯減少串長度。

圖的應用
22、什么是有環(huán)圖，連通圖，強連通圖？
連通圖：無向圖任意兩點都是連通的，圖中極大連通子圖（極大子圖還是連通的）成為連通分量。
強連通圖：有向圖從vi到vj和從vj到vi都存在路徑稱為強連通圖，有向圖中極大連通子圖稱作強連通分量。
連通圖的生成樹：是一個極小連通子圖，含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊，少于是非連通圖，多余必定構(gòu)成環(huán)。
有向樹：有向圖中一頂點入度為0，其余入度為1
第一個頂點到最后一個頂點相同的路徑稱為環(huán)或回路。序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑，除了第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路，稱為簡單環(huán)。

23、圖的存儲方式有哪些簡要敘述（鄰接矩陣和鄰接表）？
鄰接矩陣：將頂點和邊分別存儲，頂點用一維數(shù)組存儲，邊用二維數(shù)組?？梢愿鶕?jù)這個二維數(shù)組獲取圖中的信息。比如判定兩頂點是否有邊，只需讀取二維數(shù)組值。想知道某個頂點的度就是將這一行的值相加。求他的臨界點也只需遍歷一行，值為1的就是。無向圖的邊數(shù)組是對稱的，有向圖入度看列，出度看行。
鄰接表：對于邊數(shù)較少，頂點較多的圖，如果還用鄰接矩陣那是對空間的極大浪費，所以用鄰接表，頂點還是一維數(shù)組存儲，此外數(shù)組每一個數(shù)據(jù)元素還存儲指向第一個鄰接點的指針，以便于查找邊的信息，圖中每個頂點的所有鄰接點構(gòu)成一個鏈表。邊表每個節(jié)點存儲這個頂點在頂點表中的下標，和一個指向下一個節(jié)點的指針。想知道某頂點的度，就查找這個頂點的邊中節(jié)點的個數(shù)，要判斷是否存在邊也只需遍歷相應邊表。但是對于有向圖能得到每個頂點出度，為了便于確定入度可以再建立一個逆鄰接表。

24、什么是DFS，遍歷后形成什么？時間和空間復雜度多少？遍歷節(jié)點順序是否唯一？
DFS：圖的深度優(yōu)先遍歷，是一種遞歸過程，是對樹的先序遍歷的推廣，從某個頂點開始訪問，然后對尚未訪問的鄰接點出發(fā)，繼續(xù)深度優(yōu)先遍歷，直到所有和初始頂點路徑相通的頂點都被訪問到。對于非連通圖，只需對它的連通分量分別進行DFS。
BFS：圖的廣度優(yōu)先遍歷，類似于樹的層序遍歷，先初始化一輔助隊列，從某個頂點開始訪問，訪問節(jié)點后入隊，隊列不為空則隊列元素出隊列，然后判斷當前出隊列頂點鄰接點是否訪問過，沒有則訪問入隊，重復這一過程。

25、什么是迪杰斯特拉算法？
用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。并不是一下子就求出最短路徑，而是一步步求他們之間頂點的最短路徑，在這個過程中都基于已經(jīng)求出的最短路徑的基礎(chǔ)上。

26、什么是拓撲排序？什么圖可以拓撲排序？
這種用頂點表示活動，用弧來表示活動間的優(yōu)先關(guān)系的有向圖叫做頂點表示活動的網(wǎng)絡(luò)簡稱為AOV網(wǎng)。通常，在AOV網(wǎng)中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序，而且每個頂點出現(xiàn)且只出現(xiàn)一次，若頂點a在序列中排在頂點b前面，則在圖中不存在從頂點b到頂點a的路徑。
(1)從有向圖中選擇一個沒有前驅(qū)(即入度為0)的頂點并且輸出它.
(2)從網(wǎng)中刪去該頂點,并且刪去從該頂點發(fā)出的全部有向邊.
(3)重復上述兩步,直到剩余的網(wǎng)中不再存在沒有前趨的頂點為止.
判定網(wǎng)中是否存在環(huán)的方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都出現(xiàn)在它的拓撲有序序列中，則該AOV網(wǎng)中一定不存在環(huán)。

27、什么是普里姆算法？什么是克魯斯卡爾算法？
最小生成樹：權(quán)值之和最小的那顆生成樹稱為最小生成樹。
普里姆算法：在所有“其一個頂點已經(jīng)落在生成樹上，而另一個頂點尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止
克魯斯卡爾：新建一個圖G，G中擁有原圖中相同的節(jié)點，但沒有邊，將原圖中所有的邊按權(quán)值從小到大排序，從權(quán)值最小的邊開始，如果這條邊連接的兩個節(jié)點于圖G中不在同一個連通分量中，則添加這條邊到圖G中，重復，直至圖G中所有的節(jié)點都在同一個連通分量中。

28、什么是關(guān)鍵路徑？
用頂點表示事件，弧表示活動，弧上的權(quán)值表示活動持續(xù)的時間的有向圖叫AOE網(wǎng)。
在項目管理中，關(guān)鍵路徑最長的那個路徑，決定了整個項目的最短完成時間。把關(guān)鍵路徑上的活動成為關(guān)鍵活動，關(guān)鍵活動影響了整個工程的時間，即如果關(guān)鍵活動不能按時完成的話，整個工程完成時間就會受到影響。
事件最早發(fā)生時間：從開始頂點到下一個頂點最長路徑長度。它決定了它后面的活動的最早發(fā)生時間。
事件最遲發(fā)生時間：工程不推遲的前提，該事件最遲必須發(fā)生的時間，從后往前計算，邊值最小的。
活動的最遲發(fā)生時間：活動終點所表示事件最遲發(fā)生時間與該活動所需時間之差。
補：請簡述一下迪杰斯特拉算法的過程？
1.數(shù)組d中存放源點到其他點的最短距離，每次從數(shù)組d中選一個值最小且沒有被訪問過的點；
2.如果經(jīng)過此點到其他點距離更短，則更新數(shù)組d；
3.標記此點已訪問過，遍歷其他點，直到所有點被訪問完。

查找與排序
29、什么是折半查找？時間復雜度多少？前提條件是什么？過程如何？
1.必須采用順序存儲結(jié)構(gòu) 2.必須按關(guān)鍵字大小有序排列。
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
時間復雜度：其算法復雜度為O（log n）
30、什么是哈希表?什么是沖突？
普通的查找方法，查找關(guān)鍵字都需要比較，時間較長，而哈希表的方法是欲查找關(guān)鍵字的存儲位置是由某個函數(shù)計算出來的，它把記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應關(guān)系，使得每個關(guān)鍵字對應一個存儲位置。這種關(guān)系稱為散列函數(shù)。
查找步驟：存儲數(shù)據(jù)時候存儲在通過散列函數(shù)計算的地址，當查找記錄時通過同樣的散列函數(shù)計算地址。
適用情況：一個關(guān)鍵字對應很多不適合，范圍查找不適合，排序也不可能。
沖突：兩個不同的關(guān)鍵字用散列函數(shù)計算出了相同的存儲地址稱為沖突。
處理沖突的方法：
開放定址法：空閑地址，同義詞表項可以存，非同義詞也可以。
1.線性探測法：有沖突就順序查看下一個單元，可能造成堆積。
平方探測法：1方，-1方，2方，-2方。。。這個不堆積但是只能探測一半。
再散列：用別的函數(shù)再試試。
偽隨機數(shù)法：
拉鏈法：把所有同義詞存在一個線性鏈表中。
31、什么是折半插入排序？時間空間復雜度多少？
正常插入排序插入時候，從后往前查找待插入位置，而折半插入是用折半的方法找到插入的位置，然后插入。僅僅是減少了比較元素的次數(shù)，時間復雜度仍為O（N方）

32、什么是快速排序？時間空間復雜度多少？簡述基本過程
一般用第一個元素用作基準數(shù)，但如果是有序花費時間將是二次。一般可以使用三數(shù)取中值分割法?？焖倥判蚴菍γ芭菖判虻母倪M，屬于交換排序，基本思想基于分治法，在待排序表中取一個元素作為基準，通過一趟排序?qū)⒋判虮韯澐譃楠毩⒌膬刹糠帧Ｗ筮叢糠中∮诨鶞?，右邊大于，這個過程稱為一趟排序，而后分別遞歸地對兩個子表重復上述過程，直到每部分內(nèi)只有一個元素或為空，即所有元素放在最終位置上。
當i<j 時且 j對應的值大于基準跳過，碰到小于基準停下來，i小于j且i從前向后跳過小于基準的值。如果i小于j，交換然后縮小區(qū)間（i++，j- -) 繼續(xù) 回到開始但前提i小于j

33、什么是堆？有什么用？什么是堆排序？
堆可以看成是一棵完全二叉樹，如果任意一節(jié)點都小于它的子孫，稱為小項堆，任意節(jié)點大于它子孫稱為大頂堆。
作用：可以對一組數(shù)據(jù)進行排序。大數(shù)據(jù)中找出最大的幾個值，用堆比較快。
堆排序：構(gòu)造堆先自下往上調(diào)整，如果建立大根堆，從下往上，從右往左，每個有孩子的節(jié)點（如果從數(shù)組角度是n/2處向前到1）的關(guān)鍵字小于左右子樹中關(guān)鍵字大者，則交換。反復利用上述調(diào)整堆的方法建堆，直到根節(jié)點。這樣將R[1…n]構(gòu)造為初始堆，將當前初始堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆（亦稱重建堆）。
與直接選擇區(qū)別：直接選擇排序中，為了從R[1…n]中選出關(guān)鍵字最小的記錄，必須進行n-1次比較，然后在R[2…n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復執(zhí)行了這些比較操作。
堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。

34、你認為哪種排序算法最優(yōu)？
沒有最好，只有最適合，若n較小，用簡單的排序算法較好比如簡單選擇，直接插入，如果數(shù)據(jù)初始狀態(tài)已經(jīng)按關(guān)鍵字基本有序，則選用直接插入或冒泡較好。如果n較大應該考慮用那幾個時間復雜度較好的算法，快速排序是被認為是目前基于比較的內(nèi)部排序算法中最好的方法，當待排序關(guān)鍵字是隨機分布時，快速排序的平均時間最短。如果對負輔助空間有限制則可以考慮堆排序，另外求大數(shù)據(jù)的最大的幾個數(shù)，堆排序最適合。如果要求排序穩(wěn)定可以考慮歸并排序。如果n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解，采用基數(shù)排序較好。當記錄本身信息量很大，為了避免移動，可以考慮鏈表。

三、操作系統(tǒng)部分

操作系統(tǒng)概述
35、操作系統(tǒng)用到了那些數(shù)據(jù)結(jié)構(gòu)？舉例說明
進程調(diào)度后備隊列，先進先出算法
短進程優(yōu)先算法用了堆
動態(tài)分區(qū)分配，首次適應算法。在此算法中，空閑區(qū)鏈按起始地址遞增順序排列，在進行內(nèi)存分配時，從鏈首開始順序查找，直到找到一個能滿足其大小要求的空閑區(qū)為止。循環(huán)首次適應算，循環(huán)鏈表。
目前廣泛流行公用緩沖池，池中的緩沖區(qū)可供多個進程共享。它把相同類型的緩沖區(qū)鏈成一個隊列
索引順序文件：記錄分組，索引表中為每組中的第一個記錄建立一個索引項，組與組之間關(guān)鍵字必須有序，組中關(guān)鍵字可以無序。通過索引表找到所在組。
散列文件：沒有 順序特征。
文件分配磁盤塊方式：鏈接分配，索引分配。
系統(tǒng)調(diào)用的過程？操作系統(tǒng)的組成？
內(nèi)核提供一系列具備預定功能的多內(nèi)核函數(shù)，通過一組稱為系統(tǒng)調(diào)用（system call)的接口呈現(xiàn)給用戶。系統(tǒng)調(diào)用把應用程序的請求傳給內(nèi)核，調(diào)用相應的的內(nèi)核函數(shù)完成所需的處理，將處理結(jié)果返回給應用程序。
系統(tǒng)調(diào)用通常包括：進程控制、文件系統(tǒng)控制、內(nèi)存管理、網(wǎng)絡(luò)管理，進程通信等。
基本功能：處理機管理，處理器的分配和運行實施有效的管理，如進程控制，同步，通信，調(diào)度。存儲器管理，對內(nèi)存分配、保護、擴充。設(shè)備管理，對計算機系統(tǒng)內(nèi)的所有設(shè)備實施有效管理，比如設(shè)備分配，緩沖和虛擬，設(shè)備傳輸控制，設(shè)備獨立性。文件管理，有效的支持文件的存儲、檢索和修改等操作，解決文件的共享、保護問題，比如文件存儲空間管理、目錄管理、文件操作管理。用戶接口，方便用戶使用操作系統(tǒng)，通常有命令接口，程序接口，圖形接口。

36、什么是微內(nèi)核？ 什么是shell？
操作系統(tǒng)：操作系統(tǒng)是控制和管理整個計算機系統(tǒng)硬件和軟件資源，并合理組織調(diào)度計算機的工作和資源分配。進程管理 存儲管理 設(shè)備管理 文件管理
微內(nèi)核：操作系統(tǒng)的一種體系結(jié)構(gòu)，將最基本的功能保留在內(nèi)核，基于客戶服務器模式的微內(nèi)核結(jié)構(gòu)，將操作系統(tǒng)劃分兩大部分，微內(nèi)核和服務器，把操作系統(tǒng)絕大部分功能都放在服務器中實現(xiàn)，交互借助于微內(nèi)核通信。優(yōu)點：每個服務進程允許在獨立用戶進程中，即每個服務器失敗不會引起系統(tǒng)其他服務器崩潰，可靠性好。還具有良好的靈活性，可以方便增刪服務功能，便于維護修改服務器代碼不會影響其他部分，適合分布式處理的計算環(huán)境。缺點：效率不高，所有用戶進程都要通過微內(nèi)核相互通信。
Shell：編程人員通過系統(tǒng)調(diào)用，api接口來使用操作系統(tǒng)提供的功能，普通用戶不編程，所以操作系統(tǒng)給普通用戶提供一個shell與用戶交互，shell就是覆蓋在操作系統(tǒng)上的一個用戶界面，可以是圖形的比如window，也可以是文本，比如linux，用戶可以輸入命令操作系統(tǒng)，不是進行直接系統(tǒng)調(diào)用。

進程管理
37、作業(yè)與進程的區(qū)別
一個進程是一個程序?qū)δ硞€數(shù)據(jù)集的執(zhí)行過程，是分配資源的基本單位。作業(yè)是用戶需要計算機完成的某項任務，是要求計算機所做工作的集合。

38、進程和程序有什么區(qū)別？
進程是程序及其數(shù)據(jù)在計算機上的一次運行活動，是一個動態(tài)概念，而程序是一組有序的指令集合，是一種靜態(tài)的概念
進程是程序的一次執(zhí)行過程它是動態(tài)地創(chuàng)建和消亡的具有一定的生命周期是暫時存在的，程序則是一組代碼集合，是永久存在可長期保存的。
進程可以創(chuàng)建進程，程序不能創(chuàng)建新程序。

39、進程和線程有什么區(qū)別？什么是進程樹？
進程是資源擁有的基本單位，線程是獨立調(diào)度的基本單位，而不用有系統(tǒng)資源，當可訪問其隸屬進程的系統(tǒng)資源，不僅進程之間可以并發(fā)，同一進程內(nèi)的多個線程也能，進一步提高了并發(fā)度，由于創(chuàng)建和撤銷進程系統(tǒng)都要為之分配或回收資源，保存當前環(huán)境等開銷遠大于創(chuàng)建或撤銷線程。
進程樹是一個形象化的比喻，比如一個進程啟動了一個程序，而啟動的這個進程就是原來那個進程的子進程，形成的一種樹形的結(jié)構(gòu)。

40、簡述進程的狀態(tài)與轉(zhuǎn)換
新建完進程分配了必要資源，進入就緒狀態(tài)，這時只需要得到處理就進程就能運行，進入運行狀態(tài)后，需要等待某個資源進入阻塞狀態(tài)，資源到位了進入就緒隊列等待處理機。運行完事進入終止狀態(tài)，資源回收。

41、進程間的通信有幾種方式？
共享存儲：在通信進程之間存在一塊可直接訪問的共享空間，通過對這段空間的讀寫實現(xiàn)進程之間的信息交換，在對共享空間進行寫/讀操作時，需要使用同步互斥工具。
消息傳遞：數(shù)據(jù)交換是以格式化的消息為但單位，操作系統(tǒng)提供的消息傳遞方式，有直接通信方式和間接通信方式。
管道通信：管道就是連接一個讀進程和一個寫進程以實現(xiàn)他們之間通信的一個共享文件，向管道提供輸入的發(fā)送進程以字符流形式將大量數(shù)據(jù)送入管道，接受管道輸出的進程，則從管道中接受數(shù)據(jù)，為了協(xié)調(diào)雙方通信，管道機制需提供互斥、同步和確定對方的存在。

42、什么叫饑餓？
短作業(yè)優(yōu)先算法時候，長作業(yè)一直得不到處理機

43、進程的調(diào)度算法有哪些?分別簡述
先來先服務，缺點短作業(yè)可能等待很長時間，平均響應時間很慢。
短任務優(yōu)先算法：平均響應時間最優(yōu)，分為搶占和非搶占，容易餓死長任務。
高響應比：優(yōu)先權(quán)=等待時間+要求服務時間/要求服務時間既照顧了短作業(yè)，又不會使長作業(yè)得不到服務。
分時（時間片）：選擇適當時間片，過大退化成FCFS過小切換所用時間多。
優(yōu)先級：靜態(tài)優(yōu)先級不變，動態(tài)優(yōu)先級，執(zhí)行了降低優(yōu)先級。
多級反饋隊列調(diào)度算法：設(shè)置多個就緒隊列，并為各個隊列賦予不同優(yōu)先級，第一個隊列優(yōu)先級最高，依次降低，各隊列中進程內(nèi)時間片的大小也不相同，最高優(yōu)先級的時間片最小，依次升高。當一個進程進入內(nèi)存后，先進入優(yōu)先級最高隊尾，等待調(diào)度，當運行時候如果在該時間片結(jié)束，便可撤離了，沒完成就進入第二個隊列末尾等待，依次進行，如果在最后一個隊列執(zhí)行一次還沒完成，就在這隊列繼續(xù)排隊。僅當?shù)谝魂犃锌臻e時候，調(diào)度程序才會調(diào)度第二隊中進程運行，優(yōu)先級高的隊列空閑，優(yōu)先級低才會被調(diào)度，如果優(yōu)先級低的隊列正在執(zhí)行，優(yōu)先級高隊列有進程進入，則調(diào)度程序把正在執(zhí)行的進程放在這隊的末尾，優(yōu)先級高的先執(zhí)行。
實時最早截止時間優(yōu)先（EDF）：開始截止時間確定優(yōu)先級。
最低松弛度優(yōu)先（LLF）：根據(jù)任務緊急程度來確定優(yōu)先級。
44、什么是軟實時，什么是硬實時？
硬實時系統(tǒng)有一個剛性的、不可改變的時間限制，它不允許任何超出時限的錯誤。超時錯誤會帶來損害甚至導致系統(tǒng)失敗、或者導致系統(tǒng)不能實現(xiàn)它的預期目標。
軟實時系統(tǒng)的時限是一個柔性靈活的，它可以容忍偶然的超時錯誤。失敗造成的后果并不嚴重，僅僅是輕微的降低了系統(tǒng)的吞吐量。

45、什么是PV操作？簡述PV操作要點及注意事項。
信號量是最早出現(xiàn)的用來解決進程同步與互斥問題的機制，包括一個稱為信號量的變量及對它進行的兩個原語操作p操作和v操作，這兩個操作是不可中斷的程序段，稱為原語。
P原語操作的動作是：信號量減1；若減1后仍大于或等于零，則進程繼續(xù)執(zhí)行；若減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中V原語操作的動作是：信號量加1；若相加結(jié)果大于零，則進程繼續(xù)執(zhí)行；若相加結(jié)果小于或等于零，則從該信號的等待隊列中喚醒一等待進程。
信號量必須成對使用。且在P,V愿語執(zhí)行期間不允許有中斷的發(fā)生。P,V原語不但可以解決進程管理當中的互斥問題，而且我們還可以利用此方法解決進程同步與進程通信的問題。同步時候信號量初始為0，互斥時候為1。

46、什么是死鎖？有什么解決辦法？
死鎖：多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將無法向前推進。原因：是資源的爭奪，或進程推進順序非法。
必要條件：資源為臨界資源、進程所獲得資源在用完之前不可強行奪走，只能主動釋放，進程已經(jīng)保持了至少一個資源，但有提出了新的資源請求，但該資源以被占用了，循環(huán)等待條件，存在一種進程資源的循環(huán)等待鏈。
預防死鎖：這是一種較簡單和直觀的事先預防的方法。方法是通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或者幾個，來預防發(fā)生死鎖。但是由于所施加的限制條件往往太嚴格，可能會導致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。
避免死鎖：該方法同樣是屬于事先預防的策略，但它并不須事先采取各種限制措施去破壞產(chǎn)生死鎖的的四個必要條件，而是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖。
檢測死鎖：這種方法并不須事先采取任何限制性措施，也不必檢查系統(tǒng)是否已經(jīng)進入不安全區(qū)，此方法允許系統(tǒng)在運行過程中發(fā)生死鎖。但可通過系統(tǒng)所設(shè)置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源，然后采取適當措施，從系統(tǒng)中將已發(fā)生的死鎖清除掉。
解除死鎖：這是與檢測死鎖相配套的一種措施。當檢測到系統(tǒng)中已發(fā)生死鎖時，須將進程從死鎖狀態(tài)中解脫出來。常用的實施方法是撤銷或掛起一些進程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運行。

內(nèi)存管理
47、簡述內(nèi)存的連續(xù)分配管理方式
固定分區(qū)分配，劃分若干個固定大小區(qū)域，建立分區(qū)說明表，容易產(chǎn)生內(nèi)部碎片。
動態(tài)分區(qū)分配，又稱可變分區(qū)分配，是一種動態(tài)劃分內(nèi)存的分區(qū)方法。不預先劃分，而是在進程裝入內(nèi)存時候，根據(jù)進程大小動態(tài)的建立分區(qū)。并使分區(qū)大小正好適合進程的需要。因此系統(tǒng)中分區(qū)的大小數(shù)目是可變的。會產(chǎn)生外部碎片?？捎镁o湊技術(shù)解決，不時的動態(tài)整理。
首次適應，空閑分區(qū)以地址遞增次序鏈接，找到一個能滿足要求的分區(qū)。
最佳適應：分區(qū)按容量遞增形成分區(qū)鏈。
最壞適應：分區(qū)按容量遞減形式分區(qū)鏈。
臨近適應：循環(huán)首次適應，從上次查找結(jié)束位置開始繼續(xù)查找。
48、程序裝入和鏈接。
編譯：將源代碼編譯成若干個目標模塊
鏈接：鏈接程序?qū)⒕幾g后形成的目標模塊，以及所需庫函數(shù)鏈接在一起，形成一個完整的裝入模塊。鏈接分為靜態(tài)，裝入時動態(tài)，運行時動態(tài)
裝入：由裝入程序裝入模塊裝入內(nèi)存中運行。分為絕對裝入，可重定位，靜態(tài)重定位一次性完成，動態(tài)重定位。
49、常用內(nèi)存保護方法有哪些？
頁表機制里，頁表寄存器中有頁表起始地址，和頁表長度，比較頁號和頁表長度如果大于頁表長度則產(chǎn)生越界中斷。

50、什么是交換技術(shù)？什么是覆蓋技術(shù)？及其區(qū)別
覆蓋：把一個用戶空間分成一個固定分區(qū)和若干個覆蓋區(qū)，活躍部分放入固定區(qū)，其余部分先放即將訪問的進覆蓋區(qū)，其他需要時候在調(diào)入覆蓋原有的段。
交換：把處于等待狀態(tài)的程序從內(nèi)存移到外存，騰出空間這叫換出，然后把準備好競爭CPU運行的程序從外存調(diào)入內(nèi)存，這叫換入。

51、什么是拼接技術(shù)？
就是緊湊技術(shù)：動態(tài)分區(qū)分配回收時候，將其余空閑分區(qū)合并為一個大的空閑分區(qū)。

52、簡述內(nèi)存的非連續(xù)非配管理方式（段、頁）
非連續(xù)分配根據(jù)分區(qū)大小是否固定分為，分頁存儲管理和分段存儲管理。分頁存儲管理方式又根據(jù)是否要把作業(yè)的所有頁面都裝入內(nèi)存分為基本分頁存儲方式，和請求分頁存儲方式
基本分頁存儲管理方式：把主存空間分為大小相等且固定的塊，相對較小，作為主存的基本單位，每個進程也以塊為單位進行劃分，進程在執(zhí)行時，以塊為單位逐個申請主存中的塊空間。與固定分區(qū)技術(shù)的區(qū)別是塊的大小相對于分區(qū)較多，而且進程也按照塊進行劃分，進程運行時按塊申請主存可用空間并執(zhí)行，只會在最后一個不完整塊產(chǎn)生內(nèi)部碎片。
進程在執(zhí)行過程中需要申請主存空間，就是要為每個頁面分配主存中的可用葉框，這就產(chǎn)生了頁和葉匡的一一對應。頁面大小要適中，太小頁表長，頁內(nèi)碎片增大，降低內(nèi)存的利用率。一般每頁大小4KB，所以頁內(nèi)偏移量12位，頁號20位，地址最多2的20此方頁。
頁表：為了便于在內(nèi)存中找到進程的每個頁面所對應的物理塊，系統(tǒng)為每個進程創(chuàng)建一張頁表，記錄頁面在內(nèi)存中對應的物理塊號，頁表一般在內(nèi)存中。頁表作用是實現(xiàn)從頁號到物理塊號的映射。頁表寄存器PTR存放頁表在內(nèi)存地址，和頁表長度。進程未執(zhí)行放在進程控制塊中，執(zhí)行存入。
TLB快表：若頁表全部放在內(nèi)存中，則存取一個數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存，一次是訪問頁表，確定物理地址，一次是取數(shù)據(jù)和指令。這顯然比通常執(zhí)行指令慢一倍，所以增加一個具有并行查找能力的高速緩存存儲器–快表。又稱聯(lián)想寄存器，用來存放當前訪問的若干表項，比較的時候是將頁與塊表中的所有頁號同時進行比較，找到取出，如果沒有則訪問主存中頁表，讀出后同時放入快表中，以便后面可能再次訪問，但若塊表以滿則按著一定算法對舊頁表進行替換。
頁表占空間太大可以用兩級頁表，進程執(zhí)行只需調(diào)入最高級頁表就可以，進程的頁表和進程本身的頁面，可以再后面的執(zhí)行中再調(diào)入。
分段管理：分頁是從計算機角度考慮設(shè)計，提高內(nèi)存利用率，而且通過硬件機制，對用戶完全透明，分段管理方式的提出考慮了用戶程序員以滿足編程方便，信息保護和共享等多方面需求。段內(nèi)要求連續(xù)，段間不要求連續(xù)，作業(yè)地址空間是二維的。最大段長64KB，段號為16位，段內(nèi)偏移量為16位。段式系統(tǒng)中段號和段內(nèi)偏移量必須由用戶顯示提供。段表映射了邏輯空間和內(nèi)存空間。段表項記錄了起址和段長。分段系統(tǒng)共享是通過兩個作業(yè)的段表中相應表指向被共享的段的同一個物理副本實現(xiàn)的。不能修改的代碼稱為純代碼和可重入代碼這樣代碼不能修改數(shù)據(jù)是可以共享的。
段頁式：將兩種存儲管理方法結(jié)合起來，形成了段頁式存儲管理方式。作業(yè)地址空間首先分成若干邏輯段，每段都有自己段號，然后每一段分成若干大小固定的頁。對內(nèi)存空間管理仍然和分頁一樣。邏輯地址三部分，段號，頁號，偏移量。段表項報考段號，頁表長度，頁表起始地址。頁表項包括頁號和塊號。
53、簡述虛擬存儲器的原理
傳統(tǒng)存儲管理方式一次性，駐留性不換出。局部性原理，空間局部性，一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元頁將被訪問，指令通常說順序存放，順序執(zhí)行的，數(shù)據(jù)也一般以數(shù)組等方式簇聚存儲的。時間局部性，某一指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行，數(shù)據(jù)被訪問過，不久以后數(shù)據(jù)有可能再次被訪問。原因是程序有循環(huán)?；诰植啃栽恚诔绦蜓b入時候，可以將程序的一部分裝入內(nèi)存，其余部分留在外存，就可以啟動程序執(zhí)行，在程序執(zhí)行過程中，訪問的信息不存在內(nèi)存，由系統(tǒng)將所需的部分調(diào)入內(nèi)存然后繼續(xù)執(zhí)行程序，另一方面將暫時不使用的內(nèi)存換出道外存。從而騰出空間存放將要掉入內(nèi)存的信息，這樣系統(tǒng)好像為用戶提供了一個比實際內(nèi)存大的多的存儲器，稱為虛擬存儲器。
實現(xiàn)：請求分頁，請求分段，請求段頁式存儲管理
硬件支持：內(nèi)存外存，也表機制，中斷機構(gòu)，地址變換機構(gòu)。
請求分頁管理方式：建立在基本分頁管理方式，為了支持虛擬存儲器功能，增加了請求調(diào)頁和頁面置換功能。每當要訪問的頁面不在內(nèi)存時候，便產(chǎn)生了一個缺頁中斷，請求操作系統(tǒng)將所缺的頁面調(diào)入內(nèi)存，此時將缺頁進程阻塞，調(diào)完喚醒，內(nèi)存有空閑塊則分配，將要掉入的頁裝入該塊，并修改頁表中相應表項，若此時沒有空閑塊，則按著一定算法置換。修改過還寫回，與一般中斷比可以再指令執(zhí)行期間產(chǎn)生和處理中斷信號。
54、簡述各種頁面置換算法（LRU、CLOCK）LRU是如何實現(xiàn)的？
最佳，以后不會使用的淘汰。不可能實現(xiàn)。
先進先出：優(yōu)先淘汰最早進入內(nèi)存的頁面。
最近最久未使用LRU置換算法：淘汰最近最長時間未訪問過的頁面，該算法未每個頁面設(shè)置一個訪問字段，來記錄頁面自上次被訪問以來所經(jīng)歷的時間，淘汰頁面時候選擇現(xiàn)有頁面中值最大的。需要棧支持?？衫靡粋€特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號民，而棧底則是最近最久未使用的頁面的頁面號。
Clock算法：LRU接近最佳置換算法，性能好但是開銷大，F(xiàn)IFO簡單但是性能差，CLOCK算法比較小的開銷接近LRU的性能，最近未用（NRU），給每一幀關(guān)聯(lián)一個附加位，稱為使用位，當某一頁首次裝入主存，該幀使用位設(shè)置1，隨后再被訪問頁被置1，替換算法把候選幀集合看成一個循環(huán)緩沖區(qū)，并且有一個指針與之關(guān)聯(lián)， 當某一頁被替換時該指針被設(shè)置成指向緩沖區(qū)的下一幀。當需要替換一頁時候，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位為0的一幀，每當遇到為1的改0，如果所有都為0則替換第一個，所有都為1則全改0一圈回來后替換第一個，由于循環(huán)檢查各頁情況，所以CLOCK。
優(yōu)化：加一個修改位，改了的為1， 系統(tǒng)先找沒訪問過頁沒修改過的，不對使用位修改，找不到的找沒訪問，改了的，這次過去使用位改0，找不到，回原點從新來，這回一定能找到了。由于修改的頁面需要寫回。這樣節(jié)省時間。

55、什么是TLB（快表）？有什么用？原理？
TLB塊表：若頁表全部放在內(nèi)存中，則存取一個數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存，一次是訪問頁表，確定物理地址，一次是取數(shù)據(jù)和指令。這顯然比通常執(zhí)行指令慢一倍，所以增加一個具有并行查找能力的高速緩存存儲器–快表。又稱聯(lián)想寄存器，用來存放當前訪問的若干表項，比較的時候是將頁與塊表中的所有頁號同時進行比較，找到取出，如果沒有則訪問主存中頁表，讀出后同時放入快表中，以便后面可能再次訪問，但若塊表以滿則按著一定算法對舊頁表進行替換。

IO管理和文件
56、什么是設(shè)備無關(guān)性？
應用程序獨立于具體使用的物理設(shè)備。為了實現(xiàn)設(shè)備獨立性，在程序中使用邏輯設(shè)備名來請求，使用某類設(shè)備，在系統(tǒng)中設(shè)置邏輯設(shè)備表。用于將邏輯設(shè)備名映射為物理設(shè)備名。這樣多個進程可以分時使用同一個設(shè)備了。

57、磁盤調(diào)度算法有哪些？
先來先服務：僅適用于請求磁盤IO的進程數(shù)目較少的場合最簡單的一種磁盤調(diào)度算法，根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。優(yōu)點：簡單，公平，每一個請求的進程都能夠得到處理，不會出現(xiàn)長期得不到處理的進程。缺點：未對尋道進行優(yōu)化，致使平均尋道時間可能較長。
最短尋道時間優(yōu)先：該算法選擇這樣的進程，其要求訪問的磁道，與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種算法不能保證平均尋道時間最短優(yōu)點：較FCFS有更好的尋道性能缺點：可能導致老進程饑餓，可能會出現(xiàn)磁臂黏著
掃描算法：也叫電梯調(diào)度算法在SSTF算法基礎(chǔ)上優(yōu)化而得到，可以防止老進程饑餓。該算法不僅考慮到被訪問磁道和當前磁頭之間的距離，更優(yōu)先考慮的是磁頭當前的移動方向。(應該選取同方向且距離最近的磁道訪問。)優(yōu)點：磁頭雙向移動，不會產(chǎn)生饑餓，平均尋道時間短。缺點：可能會出現(xiàn)磁臂黏著
循環(huán)掃描算法：為了減少延遲，CSCAN規(guī)定磁頭單向移動，當從里到最外后，磁頭立即返回到最里的欲訪問磁道，然后繼續(xù)向外。優(yōu)點：磁頭單向移動，不會產(chǎn)生饑餓，平均尋道時間短。
58、文件共享的方式又哪些？
硬連接：基于索引節(jié)點的共享方式，諸如文件的物理地址以及其他的文件屬性等信息，不再是放在目錄項中，而是放在索引節(jié)點中。文件目錄只設(shè)置文件名以及指向相應索引節(jié)點的指針，索引節(jié)點還應有一個鏈接計數(shù)。
軟連接：符號鏈為讓B共享用戶A的一個共享文件F，可以由系統(tǒng)創(chuàng)建一個LINK類型的新文件也取名為F，并將文件F寫入用戶B的目錄中，指向這個鏈接文件，其實就是快捷方式。
59、文件分配方式有哪些？
連續(xù)分配：每個文件在磁盤上占一組連續(xù)塊，支持順序訪問和直接訪問，優(yōu)點是簡單，存取速度快。缺點是文件長度不宜動態(tài)增加。增加需大量移動。
鏈接分配：采取離散分配，消除外部碎片，提高了磁盤利用率，根據(jù)當前需要分配必需的盤塊，當文件動態(tài)增長時，可以動態(tài)再為它分配盤塊。隱式鏈接：每個文件對應一個磁盤塊的鏈表，磁盤塊分布在磁盤的任何地方，除最后一個盤塊外，每個盤塊都由指向下一個盤塊的指針。顯示連鏈接：把指針顯式存放在內(nèi)存中一張連接表中，該表在整個磁盤設(shè)置一張，每個表項中存放鏈接指針，即下一個盤塊號。顯著提高了檢索速度，大大減少了訪問磁盤的次數(shù)，由于分配給文件的所有盤塊號都放在該表中，故稱該表為文件分配表（FAT）
索引分配：把每個文件的所有盤塊號都集中放在一起構(gòu)成索引塊表。為了處理大文件，可以鏈接多個索引塊，也可以多層索引。
混合索引：把多種索引分配方式相結(jié)合的分配方式。
60、文件存儲空間管理
空閑表法：與內(nèi)存動態(tài)分配相似
空閑鏈表法：將所有空閑盤區(qū)拉成一條空閑鏈。
位示圖：磁盤上每個盤塊都有一個二進制位與之對應

61、簡述緩沖池原理
緩沖池：由多個系統(tǒng)公用的緩沖區(qū)組成，緩沖區(qū)按其使用情況可以形成三個隊列，空緩沖隊列、裝滿輸入數(shù)據(jù)的緩沖隊列（輸入隊列）和裝滿輸出數(shù)據(jù)的隊列（輸出隊列），還有四個緩沖區(qū)：用于收容輸入數(shù)據(jù)緩沖區(qū)、用于提取輸入數(shù)據(jù)的工作緩沖區(qū)、用于收容輸出數(shù)據(jù)的工作緩沖區(qū)以及用于提取輸出數(shù)據(jù)的工作緩沖區(qū)。
當輸入進程需要輸入數(shù)據(jù)時，從空緩沖隊列隊首摘下一個空緩沖區(qū)，把它作為收容輸入工作緩沖區(qū)，然后把輸入數(shù)據(jù)輸入其中，裝滿后再掛到輸入隊列末尾。當計算機進程要輸入數(shù)據(jù)時，便從輸入隊列取得一個空緩沖區(qū)作為提取輸入工作緩沖區(qū)，計算進程從中提取數(shù)據(jù)，數(shù)據(jù)用完后再將它掛到空緩沖隊列尾。當計算機進程需要輸入數(shù)據(jù)時，便從空緩沖隊列的隊首取得空緩沖區(qū)，作為收容輸出工作緩沖區(qū)，當其中裝滿輸出數(shù)據(jù)后，再將它掛到輸出隊列隊尾。當要輸出時，有輸出進程從輸出隊列中取得一個裝滿輸出數(shù)據(jù)的緩沖區(qū)，作為提取輸出工作緩沖區(qū)，提取完掛到空緩沖隊列隊尾。

四、計算機網(wǎng)絡(luò)部分

計算機網(wǎng)絡(luò)概述
62、三網(wǎng)融合，指哪三網(wǎng)？
電信網(wǎng)絡(luò)：主要業(yè)務是電話，傳真等。
有線電視網(wǎng)絡(luò)：單向電視節(jié)目傳輸網(wǎng)絡(luò)。
計算機網(wǎng)絡(luò)：我們現(xiàn)在用的很多的局域網(wǎng)和Internet等。

63、組成網(wǎng)絡(luò)協(xié)議的三個要素
語法：用戶數(shù)據(jù)與控制信息的結(jié)構(gòu)和格式
語義：需要發(fā)出何種控制信息，完成何種動作以，解釋比特流每一部分的意義
時序：對事件實現(xiàn)順序的詳細說明

64、OSI參考模型和TCP/IP模型有幾層，簡述各層原理及作用，TCP/IP有哪些協(xié)議？
OSI物理層，透明的傳輸比特流。
數(shù)據(jù)鏈路層，兩個相鄰節(jié)點間的鏈路上，透明地傳送幀中的數(shù)據(jù)，數(shù)據(jù)傳送時，數(shù)據(jù)鏈路層將網(wǎng)絡(luò)層交下來的IP數(shù)據(jù)包組成幀，每個幀包括數(shù)據(jù)和必要控制信息，以使得接收端能夠知道從哪開始和結(jié)束，進行硬件地址尋址進行硬件地址尋址，還使接收端能檢測到所收到的幀中有無差錯，有就丟失。
網(wǎng)絡(luò)層，為分組交換網(wǎng)上的不同主機提供通信服務，把運輸層產(chǎn)生的報文段或用戶數(shù)據(jù)報封裝成分組，關(guān)鍵問題是邏輯地址尋址，實現(xiàn)不同網(wǎng)絡(luò)之間的路徑選擇。
運輸層，運輸層負責端到端的通信，對一個主機同時運行的多個進程提供服務，這是復用，運輸層把收到的信息分別交付給上面應用層相應進程，為高層提供可靠透明有效的數(shù)據(jù)傳輸服務，實現(xiàn)進程到進程的傳輸管理，差錯控制，流量控制等。
會話層（Session Layer）：建立、管理、終止會話。（在五層模型里面已經(jīng)合并到了應用層）
表示層（Presentation Layer）：數(shù)據(jù)的表示、安全、壓縮。（在五層模型里面已經(jīng)合并到了應用層）
應用層 (Application)： 網(wǎng)絡(luò)服務與最終用戶的一個接口。協(xié)議有：HTTP FTP TFTP SMTP SNMP DNS
TCP/IP協(xié)議不是TCP和IP這兩個協(xié)議的合稱，而是指因特網(wǎng)整個TCP/IP協(xié)議族。TFTP，HTTP，SNMP，F(xiàn)TP，SMTP，DNS，Telnet ，TCP，UDPIP，ICMP，OSPF，EIGRP，IGMP,RIP，PPP，MTU，ARP，RARP

65、計算機網(wǎng)絡(luò)通信過程，什么是同步通信和異步通信？
同步通信：同步通信是一種比特同步通信技術(shù)，要求發(fā)收雙方具有同頻同相的同步時鐘信號，只需在傳送報文的最前面附加特定的同步字符，使發(fā)收雙方建立同步，此后便在同步時鐘的控制下逐位發(fā)送/接收。
異步通信：相對于同步通信，異步通信在發(fā)送字符時，所發(fā)送的字符之間的時隙可以是任意的。但是接收端必須時刻做好接收的準備，發(fā)送端可以在任意時刻開始發(fā)送字符，因此必須在每一個字符的開始和結(jié)束的地方加上標志，即加上開始位和停止位，以便使接收端能夠正確地將每一個字符接收下來。

66、各設(shè)備（集線器、交換機、路由器）在那層工作，分別是什么？
中繼器：中繼器從一個網(wǎng)絡(luò)電纜里接收信號， 放大它們，將其送入下一個電纜。
集線器：相當于多接口中繼器，可將各節(jié)點連接成一個局域網(wǎng)，但任何時刻都只能有一個節(jié)點通過公共信道發(fā)送數(shù)據(jù)。邏輯上仍然是一個總線網(wǎng)，使用CSMA/CD協(xié)議。不能隔離碰撞域。不能連接不同技術(shù)和速率的網(wǎng)絡(luò)。
網(wǎng)橋：相比較而言，網(wǎng)橋?qū)年P(guān)卡上傳下來的信息更敏銳一些。網(wǎng)橋是一種對幀進行轉(zhuǎn)發(fā)的技術(shù)，根據(jù)MAC分區(qū)塊，可隔離碰撞。網(wǎng)橋?qū)⒕W(wǎng)絡(luò)的多個網(wǎng)段在數(shù)據(jù)鏈路層連接起來。
交換機：工作在數(shù)據(jù)鏈路層相當于多端口的網(wǎng)橋，允許端口之間建立多個并發(fā)連接，實現(xiàn)多個節(jié)點之間并發(fā)傳輸，每個端口所占帶寬不會因為端口數(shù)量增加而減少
路由器：使用物理層或數(shù)據(jù)鏈路層的中繼系統(tǒng)時只是把一個網(wǎng)絡(luò)擴大了，而從網(wǎng)絡(luò)層的角度看，它仍然是通一個網(wǎng)絡(luò)，一般并不稱之為網(wǎng)絡(luò)互連，網(wǎng)絡(luò)互聯(lián)通常是指用路由器進行網(wǎng)絡(luò)互聯(lián)和路由選擇。

67、網(wǎng)絡(luò)按地理位置劃分為幾種？分別介紹
廣域網(wǎng)WAN，城域網(wǎng)MAN，局域網(wǎng)LAN，個人區(qū)域網(wǎng)WPAN

物理層
68、什么是基帶信號？什么是寬帶信號？什么是模擬信號？什么是數(shù)字信號？
基帶信號：將數(shù)字信號1或0直接用不同的電壓來表示，然后送到電路上去傳輸。
寬帶信號：將基帶信號調(diào)制后形成的頻分復用模擬信號。由于基帶信號經(jīng)過調(diào)制，其頻譜移動到較高的頻率處。由于每一路基帶信號的頻譜都被移動到不同的頻段上，因此合在一起后并不會互相干擾，這樣可以在一條電纜中傳送多路的數(shù)字信號，因而提高了線路的利用率。
模擬信號：連續(xù)信號，例如：話音信號和廣播信號
數(shù)字信號：離散信號，二進制代碼0、1組成的信號

69、簡述電路交換、報文交換、分組交換，比較優(yōu)缺點
電路交換：源節(jié)點和目的節(jié)點之間建立一專用通路，用于傳送數(shù)據(jù)，包括建立連接，傳輸數(shù)據(jù)，斷開連接，優(yōu)點：延遲小。缺點：利用率低
報文交換：將數(shù)據(jù)加上源地址，目的地址等信息，封裝成報文，存儲轉(zhuǎn)發(fā)每個報文可以單獨選擇到達目的節(jié)點的路徑，優(yōu)點利用率較好，缺點是增加了資源開銷，和緩沖延遲，緩沖難以管理，因為報文大小不確定。
分組轉(zhuǎn)發(fā)：將數(shù)據(jù)分成較短的固定長度的數(shù)據(jù)塊，每個塊上加上目的地址，源地址等輔助信息組成分組，以存儲轉(zhuǎn)發(fā)的方式傳輸，除具備報文的優(yōu)點，還有緩沖易于管理，平均延遲更小。
70、分組交換的方式有哪些？
數(shù)據(jù)報方式：不需要建立連接，發(fā)送方可以隨時發(fā)，接收方也可以隨時接受，網(wǎng)絡(luò)盡最大努力交付傳輸，不保證可靠性，分組中有發(fā)送端和接受端完整地址，以便獨立傳輸。
虛電路方式：將數(shù)據(jù)報方式與電路交換給結(jié)合起來，建立邏輯上的虛電路。與物理電路不同，節(jié)點可以共用，不時真實建立物理連接了。
71、什么是信宿和信源？
信源：在通信中，向另一部件(信宿)發(fā)出信息的部件。
信宿：從另一部件(信源)接收信息的部件
72、簡述單工，半雙工，全雙工
單工：信息在兩點之間只能單方向發(fā)送的工作方式。
半雙工：信息在兩點之間能夠在兩個方向上進行發(fā)送，但不能同時發(fā)送的工作方式。
全雙工：通信允許數(shù)據(jù)在兩個方向上同時傳輸
73、異步通信的信源和信宿沒有時鐘同步信號，怎么解決這個問題？
采用曼徹斯特或者差分曼徹斯特。簡述這兩個的原理

數(shù)據(jù)鏈路層
74、比較一下BSC協(xié)議和HDLC協(xié)議
BSC是面向字符的同步控制協(xié)議而HDLC是面向比特的同步控制協(xié)議，BSC使用字符填充的首尾定界符法。該法用一些特定的字符來定界一幀的起始與終止.協(xié)議依賴特定字符集，HDLC使用比特填充的首尾定界符法。該法以一組特定的比特模式(如01111110)來標志一幀的起始與終止。協(xié)議不依賴特定字符集。
由于BSC是一個半雙工協(xié)議，它的鏈路傳輸效率很低。HDLC支持全雙工通信，傳輸效率高。

75、數(shù)據(jù)鏈路層的作用
鏈路管理：鏈路的建立、維持、釋放。
幀定界：又稱幀同步，指接收方能從接收到的比特流中準確提取數(shù)據(jù)幀。
流量控制：發(fā)送與接收數(shù)據(jù)同步
差錯控制：采用編碼技術(shù)(如CRC)來檢測或糾正傳輸中的錯誤。其中前向糾錯具有檢測與糾錯的功能、開銷大。差錯檢測只檢錯，不糾錯，并通知發(fā)送方重傳出錯幀。
進行硬件地址尋址 進行硬件地址尋址

76、列舉數(shù)據(jù)鏈路層的協(xié)議，至少兩個
HDLC：是一個在同步網(wǎng)上傳輸數(shù)據(jù)、面向比特的數(shù)據(jù)鏈路層協(xié)議，該協(xié)議不依賴于任何一種字符編碼集，數(shù)據(jù)報文可透明傳輸，用于實現(xiàn)透明傳輸?shù)?比特填充法易于硬件實現(xiàn)，全雙工通信，較高的數(shù)據(jù)鏈路傳輸效率。
PPP：是使用串行線路通信的面向字節(jié)的協(xié)議，協(xié)議應用在直接連接的兩個節(jié)點的鏈路上，主要用來通過撥號或?qū)＞€方式建立點對點連接發(fā)送數(shù)據(jù)，因特網(wǎng)用戶連接到ISP就是使用PPP協(xié)議。PPP協(xié)議功能幀定界，以便接受端能找到幀的開始和結(jié)束位置，在同一條物理鏈路上支持多種網(wǎng)絡(luò)層的協(xié)議，差錯檢測。Ppp協(xié)議將一個IP數(shù)據(jù)報封裝成幀，既支持異步也支持同步面向比特流，還有一個用來建立、配置和測試數(shù)據(jù)鏈路連接的鏈路控制協(xié)議LCP，和一套網(wǎng)絡(luò)控制協(xié)議NCP，其中的每一個協(xié)議支持不用的網(wǎng)絡(luò)層協(xié)議。

77、什么是流量控制？在那幾層有流量控制？
數(shù)據(jù)鏈路層：流量控制設(shè)計對鏈路上的幀的發(fā)送速率的控制，以使接收方有足夠的緩沖空間來接受每一個幀。由接收方控制發(fā)送方的速率，常見方式有停止等待協(xié)議，發(fā)送方每發(fā)送一幀，都要等待接受對方應答，之后才能發(fā)送下一幀，接收方每接受一幀都要反饋一個應答信號，如果沒有應答一直等待，效率很低。
滑動窗口，在任意時刻發(fā)送方都維持一組連續(xù)連續(xù)的允許發(fā)送的幀的序號，稱為發(fā)送窗口，同時接收方頁維持一組連續(xù)允許接受的幀序號，稱為接受窗口，發(fā)送窗口用來對發(fā)送方進行流量控制，發(fā)送窗口大小代表還沒有收到對方確認情況下，發(fā)送方最多還可以發(fā)送多少數(shù)據(jù)幀，接受窗口為了控制可以接收哪些數(shù)據(jù)幀而不可以接收哪些幀。當接收方收到的數(shù)據(jù)幀是接受窗口內(nèi)的序號才收。不是丟棄。發(fā)送端每收到一個確認幀，發(fā)送窗口就向前滑動一個幀的位置，當發(fā)送窗口都沒確認就停止發(fā)送，直到接收方發(fā)送來的確認幀使窗口移動才可以發(fā)送。數(shù)據(jù)鏈路層滑動窗口大小是固定的。
自動重傳請求ARQ有三種：
單幀滑動窗口（停止等待協(xié)議），可保證有序。后兩種后退N幀ARQ和選擇重傳ARQ是滑動窗口與請求重發(fā)的結(jié)合。由于窗口尺寸足夠大，幀可以再線路上連續(xù)流動，又稱連續(xù)ARQ。
后退N幀ARQ：接收窗口等于1。允許發(fā)送方可以連續(xù)發(fā)送信息幀，但是，一旦某幀發(fā)生錯誤，必須重新發(fā)送該幀及其后的n幀。這種方式提高了信道的利用率，但允許已發(fā)送有待于確認的幀越多，可能要退回來重發(fā)的幀也越多。
選擇重傳ARQ：當發(fā)送方接收到接收方的狀態(tài)報告指示報文出錯，發(fā)送方只發(fā)送傳送發(fā)生錯誤的報文。
數(shù)據(jù)鏈路層可靠傳輸只有超時重傳。傳輸層TCP連接中傳送的數(shù)據(jù)流中每一個字節(jié)都編上一個序號，確認號是期望收到對方的下一個報文段的數(shù)據(jù)的第一個字節(jié)的序號。超時重傳和冗余確認（ACK），可以縮短時間發(fā)送方收到同一個報文段的三個冗余確認，就重傳，也成為快重傳。
傳輸層TCP流量控制：接收方根據(jù)自己接受緩存的大小，動態(tài)調(diào)整發(fā)送方的發(fā)送窗口大小，這就是接受窗口rwnd，來限制發(fā)送方向網(wǎng)絡(luò)注入報文的速率，同時發(fā)送方根據(jù)其對當前網(wǎng)絡(luò)擁塞程序的估計而確定的窗口值，成為擁塞窗口cwnd。rwnd是接收方允許連續(xù)接收的最大能力，單位字節(jié)，發(fā)送法根據(jù)最新收到的rwnd限制自己發(fā)送窗口大小。實際取rwnd和cwnd最小值。
傳輸層與數(shù)據(jù)鏈路層的流量控制區(qū)別在于，傳輸層定義了端到端用戶之間的流量控制，數(shù)據(jù)鏈路層定義了兩個中間的相鄰節(jié)點的流量控制。

78、簡述CSMA/CD的原理，如果有兩端同時發(fā)信息會出現(xiàn)什么情況？什么叫沖突？解決沖突的辦法都有哪些
載波監(jiān)聽多路訪問/碰撞檢測：載波監(jiān)聽就是發(fā)送前先偵聽，每一個站在發(fā)送數(shù)據(jù)之前要先檢測一下總線上是否有其他站點在發(fā)送數(shù)據(jù)，如果有，則暫時不發(fā)送數(shù)據(jù)，要等待信道變?yōu)榭臻e時再發(fā)送。只支持半雙工。
碰撞檢測：邊發(fā)送數(shù)據(jù)邊檢測信道上信號電壓的變化情況，以便判斷自己在發(fā)送數(shù)據(jù)時其他站點是否也發(fā)送數(shù)據(jù)。
如果傳輸了整個幀沒有檢測到來自其他適配器的信號能量，這個適配器完成該幀的傳輸，否則適配器就必須停止傳輸它的幀，傳輸一個擁塞信號。在停發(fā)后適配器采用截斷二進制指數(shù)退避算法來等待一段隨機時間后重新先聽后發(fā)。
爭用期：由于總線有傳播時延，你檢測到空閑，其實可能有數(shù)據(jù)沒到你這呢，單程端到端傳播時延為t，適配器發(fā)送幀后至多經(jīng)過2t時間就可以知道所發(fā)送數(shù)據(jù)是否遭到碰撞，之所以是2t是因為最多在最那邊，在返回來超不過2t。每一個站在發(fā)數(shù)據(jù)之后一小段時間內(nèi)，都存在遭遇沖突的可能，只有經(jīng)過爭用期這段時間還沒檢測到?jīng)_突才能確定不會發(fā)生沖突，
截斷二進制指數(shù)退避：從集合0到2的k此方減一中隨機取出一個數(shù)，k是重傳次數(shù)，最大等于10超過也是10。選出一個乘以爭用期2t得出的時間。
前64沒發(fā)生沖突就不會，規(guī)定最短有效幀長64，小于的就是異常終止的無效幀
79、簡述IEEE 802.3協(xié)議
是一種基于總線型的局域網(wǎng)標準描述物理層和數(shù)據(jù)鏈路層的MAC子層的實現(xiàn)方法。采用CSMA/CD方式對總線訪問控制。
以太網(wǎng)MAC幀，每一塊網(wǎng)絡(luò)適配器有一個地址，物理地址，MAC地址長6字節(jié)，高24位廠商代碼，低24位廠商自行分配。

80、計算機網(wǎng)絡(luò)使用的通道共享技術(shù)有哪些？簡述頻分復用、時分復用、波分復用、碼分復用。時分復用的時隙怎么確定？頻分復用如何避免各路信號間干擾?
介質(zhì)訪問控制：將使用介質(zhì)的每個設(shè)備與來自同一信道上的其他設(shè)備通信隔離開，使資源合理分配給網(wǎng)絡(luò)上的設(shè)備，采用多路復用技術(shù)可以把多個輸入通道的信息整合到一個復用通道，在接受端把收到的信息分離出來傳送到對應的輸出通道。
頻分復用FDM：就是將用于傳輸信道的總帶寬劃分成若干個子頻帶(或稱子信道)，每一個子信道傳輸1路信號。頻分復用要求總頻率寬度大于各個子信道頻率之和，同時為了保證各子信道中所傳輸?shù)男盘柣ゲ桓蓴_，應在各子信道之間設(shè)立隔離帶，這樣就保證了各路信號互不干擾(條件之一)。頻分復用技術(shù)的特點是所有子信道傳輸?shù)男盘栆圆⑿械姆绞焦ぷ?，每一路信號傳輸時可不考慮傳輸時延，因而頻分復用技術(shù)取得了非常廣泛的應用。
時分復用TDM：是采用同一物理連接的不同時段來傳輸不同的信號，也能達到多路傳輸?shù)哪康?。同?Synchronous)時分多路復用TDM,它的時間片是預先分配好的,而且是固定不變的,因此各種信號源的傳輸定時是同步的。但是計算機數(shù)據(jù)傳輸?shù)耐话l(fā)性，利用率不高。STDM又稱統(tǒng)計時分復用，異步時分多路復用，當終端數(shù)據(jù)要傳送時才會分配時間片，因此可以提高線路的利用率。
波分復用WDM：就是光的頻分復用，在一根光纖中傳輸多種不同波長的光信號，由于波長不同，所以各路光信號互不干擾，最后在用波長分解復用器將各路波長分解出來。
碼分復用CDM：是靠不用的編碼來區(qū)分各路原始信號的一種復用方式，是用一組包含互相正交的碼字的碼組攜帶多路信號。每個發(fā)送者有自己不同的密碼，接受者在接到不同信號，通過密碼過濾掉自己無法解碼的信號，留下和自己密碼對應的信號。碼分多址，每個用戶在同一時間使用同樣的頻帶進行通信。

網(wǎng)絡(luò)層
81、二層交換機是哪一層的設(shè)備，與三層交換機之間的區(qū)別？
二層交換技術(shù)是發(fā)展比較成熟，二層交換機屬數(shù)據(jù)鏈路層設(shè)備，可以識別數(shù)據(jù)包中的MAC地址信息，根據(jù)MAC地址進行轉(zhuǎn)發(fā)，并將這些MAC地址與對應的端口記錄在自己內(nèi)部的一個地址表中。
三層交換機就是具有部分路由器功能的交換機，三層交換技術(shù)就是二層交換技術(shù)＋三層轉(zhuǎn)發(fā)技術(shù)。傳統(tǒng)交換技術(shù)是在OSI網(wǎng)絡(luò)標準模型第二層——數(shù)據(jù)鏈路層進行操作的，而三層交換技術(shù)是在網(wǎng)絡(luò)模型中的第三層實現(xiàn)了數(shù)據(jù)包的高速轉(zhuǎn)發(fā)，既可實現(xiàn)網(wǎng)絡(luò)路由功能，又可根據(jù)不同網(wǎng)絡(luò)狀況做到最優(yōu)網(wǎng)絡(luò)性能。

82、連接兩個局域網(wǎng)需要用什么設(shè)備，在哪層？
網(wǎng)絡(luò)層。

83、路由器與交換機有什么區(qū)別？
（1）工作層次不同
　　最初的的交換機是工作在數(shù)據(jù)鏈路層，也就是第二層，路由器工作在的網(wǎng)絡(luò)層。
　?。?）數(shù)據(jù)轉(zhuǎn)發(fā)所依據(jù)的對象不同
　　交換機是利用物理地址或者說MAC地址來確定轉(zhuǎn)發(fā)數(shù)據(jù)的目的地址。而路由器則是利用不同網(wǎng)絡(luò)的IP地址來確定數(shù)據(jù)轉(zhuǎn)發(fā)的地址。IP地址是在軟件中實現(xiàn)的，描述的是設(shè)備所在的網(wǎng)絡(luò)，有時這些第三層的地址也稱為協(xié)議地址或者網(wǎng)絡(luò)地址。MAC地址通常是硬件自帶的，由網(wǎng)卡生產(chǎn)商來分配的，而且已經(jīng)固化到了網(wǎng)卡中去，一般來說是不可更改的。而IP地址則通常由網(wǎng)絡(luò)管理員或系統(tǒng)自動分配。
　　（3）傳統(tǒng)的交換機只能分割沖突域，不能分割廣播域；而路由器可以分割廣播域。由交換機連接的網(wǎng)段仍屬于同一個廣播域，廣播數(shù)據(jù)包會在交換機連接的所有網(wǎng)段上傳播，在某些情況下會導致通信擁擠和安全漏洞。連接到路由器上的網(wǎng)段會被分配成不同的廣播域，廣播數(shù)據(jù)不會穿過路由器。交換機是連接同一網(wǎng)段的設(shè)備?；ヂ?lián)網(wǎng)是由無數(shù)個路由器組成的，幾個交換機組成的是同一個局域網(wǎng)。

84、路由的原理
RIP路由協(xié)議：基于路徑向量，經(jīng)過一個路由器跳數(shù)加1，認為好的路由就是它通過的路由器樹最少，超過15認為不可到達，網(wǎng)絡(luò)規(guī)模不能大，只能適合小型互聯(lián)網(wǎng)，任意兩個使用RIP協(xié)議的路由之間每30秒廣播一次更新信息，特點僅和相鄰的路由交換信息，交換信息是當前本路由器所知道的全部信息，固定時間30秒一交換。優(yōu)點是簡單開銷小。缺點是規(guī)模不能大，出現(xiàn)故障收斂慢啊。使用UDP傳送數(shù)據(jù)。不一定時間最短但是跳數(shù)最少。
距離向量算法：每一個相鄰路由器發(fā)送過來的RIP報文，把所有下一跳都修改成那個路由器，距離加一，然后更新自己，沒有到目的網(wǎng)絡(luò)的之間加，有的且下一跳是那個路由的直接改不是那個路由的看短就改。
OSPF協(xié)議：鏈路狀態(tài)路由算法，它使用洪泛法向本自治系統(tǒng)中所有路由器發(fā)送信息，RIP只是向相鄰的。發(fā)送的信息是與本路由器相鄰的所有路由器的鏈路狀態(tài)，但這是部分信息，包括鏈路的代價，RIP是本路由器知道全部信息就是真?zhèn)€路由表，只有當鏈路發(fā)生變化時候才用洪泛法向所有路由發(fā)送信息，收斂快不會壞消息傳的慢。RIP是固定30秒。它使用IP數(shù)據(jù)報之間傳送。特點是根據(jù)IP分組不同服務類型設(shè)置不同代價。時分靈活。所有路由器最終都直接得到一個全網(wǎng)拓撲結(jié)構(gòu)，每個路由可以用迪杰斯特拉算法計算自己到目的最優(yōu)路徑，以此構(gòu)造自己路由表。為了能夠用于更大網(wǎng)絡(luò)，還可將一個自治系統(tǒng)劃分為若干個區(qū)域，好處是交換信息只在區(qū)域內(nèi)。減少網(wǎng)絡(luò)通信量。
85、路由的協(xié)議有哪些？分別簡述（RIP、OSPF、BGP）
BGP協(xié)議：是不同自治系統(tǒng)的路由器之間交換路由信息的協(xié)議，它是一種外部網(wǎng)關(guān)協(xié)議，邊界網(wǎng)關(guān)協(xié)議常常應用于互聯(lián)網(wǎng)的網(wǎng)關(guān)之間，它力求尋找一種到達目的網(wǎng)絡(luò)比較好的路由不能兜圈子，而不是最佳。采用路徑向量路由選擇協(xié)議，基于TCP的。原理：每一個自治系統(tǒng)的管理員選擇至少一個路由器作為該自治系統(tǒng)的BGP發(fā)言人，與其他BGP發(fā)言人交換信息建立TCP連接，建立BGP會話交換信息。當所有BGP發(fā)言人都相互交換網(wǎng)絡(luò)可達性的信息后，各BGP發(fā)言人就可找到達各自治系統(tǒng)的比較好的路由。
86、IPV4有什么替代方案？與IPV6有什么區(qū)別？IPv4和IPv6怎么互相通信？
采用無分類編址CIDR可以使IP地址分配更合理，使用網(wǎng)絡(luò)前綴概念代替子網(wǎng)概念。使用斜線記法，IP地址/網(wǎng)絡(luò)前綴占幾位。
網(wǎng)絡(luò)地址轉(zhuǎn)換：局域網(wǎng)內(nèi)部使用專用本地IP地址，對外可以只有一個全球IP就可以，大大提高了IP的重用性，必須利用NAT把私有IP地址轉(zhuǎn)換為全球IP。大大節(jié)省全球IP。
采用具有更大地址空間的新版本的IPV6，前兩種只是延遲了地址分配結(jié)束時間，IPV6從根本上解決了IP地址耗盡的問題。主要特點是：地址空間大，從32位增加到了128位，更靈活的首部格式，包含8個段（IPv4包含12個段），這一改變使得路由器可以盡快地處理
分組，從而可以改善吞吐率，更好的選項支持，以前必要現(xiàn)在可選了，所以加快了分組處理速度。
從IPv4向IPv6過渡可以采用雙協(xié)議棧和隧道技術(shù)。雙協(xié)議棧：在完全過渡到IPv6之前，使一部分主機（或路由器）裝有兩個協(xié)議棧。即一個IPv4和一個IPv6，通過雙協(xié)議棧進行轉(zhuǎn)換。隧道技術(shù)：是將整個IPv6數(shù)據(jù)報封裝到IPv4數(shù)據(jù)報的數(shù)據(jù)部分，這樣，使得IPv6數(shù)據(jù)報可以在IPv4網(wǎng)絡(luò)的隧道中傳輸。

87、簡述網(wǎng)際控制報文協(xié)議ICMP
為了提高數(shù)據(jù)報交付成功的機會，在網(wǎng)絡(luò)層使用了網(wǎng)際控制報文協(xié)議來允許主機或路由報告差錯和異常情況，ICMP作為IP數(shù)據(jù)報的數(shù)據(jù)部分加上首部，組成IP分組發(fā)送出去。有兩種一種是差錯報告報文，一種是詢問報文。
詢問報文常用的有：回送請求和回答報文、時間戳請求和回答報文。
PING命令用來探測兩主機之間連通性，使用了回送請求與回答報文，tracert使用了ICMP時間超過報文，用于確定 IP 數(shù)據(jù)包訪問目標所采取的路徑。

傳輸層
88、什么是擁塞控制？有哪些算法？與流量控制什么區(qū)別？
網(wǎng)絡(luò)擁塞：擁塞現(xiàn)象是指到達通信子網(wǎng)中某一部分的分組數(shù)量過多，使得該部分網(wǎng)絡(luò)來不及處理，以致引起這部分乃到整個網(wǎng)絡(luò)性能下降的現(xiàn)象，嚴重時甚至會導致網(wǎng)絡(luò)通信業(yè)務陷入停頓即出現(xiàn)死鎖現(xiàn)象。
TCP擁塞控制：就是防止過多的數(shù)據(jù)注入到網(wǎng)絡(luò)中，這樣可以使網(wǎng)絡(luò)中的路由器或鏈路不至于過載，當出現(xiàn)擁塞時候，端點并不能了解到擁塞發(fā)生的細節(jié)，對通信連接的端口來說擁塞往往表現(xiàn)為通信時延的增加。擁塞控制室讓網(wǎng)絡(luò)能承受現(xiàn)有負荷，是一個全局過程，涉及所有主機和路由器。流量控制只是點對點的通信量控制。
發(fā)送方維持一個擁塞窗口cwnd的狀態(tài)變量，大小取決于擁塞程度，并且動態(tài)變化。慢開始算法，先令擁塞窗口cwnd=1，最大報文長度為1，每收到一個確認增大一倍。呈指數(shù)增長，當增大到規(guī)定好的閥值就改用擁塞避免算法，每次加一不時加倍了。當網(wǎng)絡(luò)出現(xiàn)擁塞時，就是超時事件發(fā)生后把閥值減半，擁塞窗口cwnd重新設(shè)置為1，執(zhí)行慢開始算法。迅速減少發(fā)送到網(wǎng)絡(luò)中的分組數(shù)，使發(fā)生擁塞的路由器有足夠時間處理完積壓的分組。當發(fā)送方連續(xù)收到三個重復確認報文，就直接重傳對方尚未收到報文段，不必等待計時器?？旎謴途褪前验y值減半，把窗口cwnd設(shè)置為減半后的數(shù)值直接加法增大。

89、TCP連接和UDP連接有什么區(qū)別？分別適用什么情況？
TCP在不可靠的IP層之上實現(xiàn)的可靠數(shù)據(jù)傳輸協(xié)議，主要解決可靠的、有序、無丟失和不重復的問題。是面向字節(jié)流的把應用程序交付下來的數(shù)據(jù)看成一連串無結(jié)構(gòu)的字節(jié)流。傳送的數(shù)據(jù)單元稱為報文段。TCP是面向連接的服務，在傳送數(shù)據(jù)之前必須建立連接，數(shù)據(jù)傳送結(jié)束后要釋放鏈接，TCP不提供廣播或組播服務，開銷較大如確認，流量控制，計時器等。不僅使數(shù)據(jù)單元頭部增大很多，還占用許多處理機資源。TCP提供的是可靠傳輸，連接采用客戶服務器方式，連接建立需要三次握手。主要用于可靠傳輸如FTP，HTTP。
UDP無需建立連接，首部開銷小，沒有擁塞控制，某些應用要求以穩(wěn)定的速度發(fā)送，能夠容忍一些數(shù)據(jù)丟失，但不允許有較大時延，正好UDP滿足。提供最大努力支付，不保證可靠交付，UDP是面向報文的，直接把應用層報文增加首部就交IP層不經(jīng)過合并和拆分，接受IP層交來的UDP數(shù)據(jù)報直接去除首部給應用層進程一次交付完整報文。

應用層
90、簡述應用層的協(xié)議（HTTP、DNS、FTP、DHCP、SMTP、POP3）
DNS：用來把便于人們記憶的含有特定含義的主機名轉(zhuǎn)換為便于機器處理的IP地址，DNS使用了大量域名服務器，他們以層次方式組織，沒有一臺域名服務器具有因特網(wǎng)上所有主機的映射，采用分布式設(shè)計，分為根域名服務器，知道所有頂級域名服務器的IP地址，不管哪個本地域名服務器，只要自己無法解析，就求助于它，它會告訴你應該找哪個頂級域名服務器。頂級域名服務器負責管理在該頂級域名服務器注冊的多有二級域名，當收到DNS查詢請求，就給出相應回答，可能是結(jié)果，也可能是下一個應該找的域名服務器地址。每一個主機都必須在權(quán)限域名服務器處登記，它總能將管轄的主機名轉(zhuǎn)換為該主機IP地址。每一個ISP服務提供商都有一個本地服務器，查詢先送給本地域名服務器。主機向本地域名服務器采用遞歸查詢，或者返回結(jié)果或者報錯。本地域名服務器向根域名服務器查詢采用迭代查詢。要么給出地址，要么告訴你去哪找。
FTP：文件傳輸協(xié)議，提供交互式的訪問，允許客戶指明文件類型與格式，它屏蔽了各計算機系統(tǒng)的細節(jié)，因而適合于在異構(gòu)網(wǎng)絡(luò)中任意計算機之間傳送文件，采用客戶服務器工作方式，使用TCP可靠的傳輸服務。一個FTP服務器進程可同時為多個客戶進程提供服務。在工作時使用兩個并行連接，一個是控制連接用來傳輸控制信息，如連接請求。一個是數(shù)據(jù)連接，完成實際文件傳送。
SMTP：郵件發(fā)送協(xié)議，用于用戶代理向郵件服務器發(fā)送郵件或在郵件服務器之間發(fā)送郵件。采用TCP連接，它連接時候不使用中間服服務器，不管多遠就與目的服務器建立連接， 然后傳輸郵件，然后釋放。
POP3：郵件接收協(xié)議，當用戶讀取郵件時，用戶代理向郵件服務器發(fā)出請求，使用POP3協(xié)議將自己的郵件從接收方郵件服務器的用戶郵箱中取回。也采用TCP。
MIME：多用途網(wǎng)絡(luò)郵件擴充，沒改動SMTP只是定義傳送編碼。
HTTP：超文本傳輸協(xié)議，定義了瀏覽器怎樣向服務器請求網(wǎng)頁文檔，以及服務器怎么樣把文檔傳送給瀏覽器，是面向事務的應用層協(xié)議，規(guī)定了在瀏覽器和服務器之間的請求和響應的格式和規(guī)則，是萬維網(wǎng)上能夠可靠交換文件的重要基礎(chǔ)。域名解析后瀏覽器通過TCP向服務器發(fā)送建立連接請求，然后瀏覽器向服務器發(fā)送請求，服務器通過HTTP響應把請求的文件發(fā)送給瀏覽器，連接釋放
DHCP：動態(tài)主機配置協(xié)議，用于給主機動態(tài)分配IP地址，是應用層協(xié)議，基于UDP的，需要IP的主機在啟動的時候就廣播發(fā)送發(fā)現(xiàn)報文，這時該主機就成為DHCP客戶，所有主機都收到這個報文，但只有DHCP服務器才回答此廣播報文，在其數(shù)據(jù)庫中查找該計算機的信息，如果找到，就返回。沒有就從服務器IP地址池中取一個地址分配給該計算機?；卮饒笪慕刑峁﹫笪?，地址是臨時的，這段時間成為租用期，數(shù)值由服務器自己決定。
91、簡述P2P協(xié)議
P2P思想是整個網(wǎng)絡(luò)中的傳輸內(nèi)容不再保存在中心服務器上，每個節(jié)點都同時具有上傳下載功能，每個節(jié)點即作為客戶訪問其他節(jié)點資源，也作為服務器提供資源給其他節(jié)點訪問，當前比較流行的P2P應用如PPLive。
優(yōu)點：減輕了服務器壓力，消除對某個服務器的完全依賴，可以將任務分配到各個節(jié)點上?？蓴U展性好，傳統(tǒng)服務器有響應和帶寬限制，只能接受一定數(shù)量請求，網(wǎng)絡(luò)健壯性強，單個節(jié)點失效也不會影響其他部分的節(jié)點。
缺點：占用用戶過多內(nèi)存資源，影響整機速度，也使網(wǎng)絡(luò)變得非常擁堵。

92、網(wǎng)絡(luò)安全性有哪些方面，網(wǎng)絡(luò)服務質(zhì)量包括哪些方面？什么是QoS？
QoS：（QualityofService）服務質(zhì)量是一種安全控制機制，它提供了針對不同用戶或者不同數(shù)據(jù)流采用相應不同的優(yōu)先級，或者是根據(jù)應用程序的要求，保證數(shù)據(jù)流的性能達到一定的水準。在正常情況下，如果網(wǎng)絡(luò)只用于特定的無時間限制的應用系統(tǒng)，并不需要QoS，比如Web應用，但是對關(guān)鍵應用和多媒體應用就十分必要。當網(wǎng)絡(luò)過載或擁塞時，QoS能確保重要業(yè)務量不受延遲或丟棄，同時保證網(wǎng)絡(luò)的高效運行。
網(wǎng)絡(luò)安全：是指網(wǎng)絡(luò)系統(tǒng)的硬件、軟件及其系統(tǒng)中的數(shù)據(jù)受到保護，不因偶然的或者惡意的原因而遭受到破壞、更改、泄露，系統(tǒng)連續(xù)可靠正常地運行，網(wǎng)絡(luò)服務不中斷。網(wǎng)絡(luò)安全從其本質(zhì)上來講就是網(wǎng)絡(luò)上的信息安全。從廣義來說，凡是涉及到網(wǎng)絡(luò)上信息的保密性、完整性、可用性、真實性和可控性的相關(guān)技術(shù)和理論都是網(wǎng)絡(luò)安全的研究領(lǐng)域。網(wǎng)絡(luò)安全是一門涉及計算機科學、網(wǎng)絡(luò)技術(shù)、通信技術(shù)、密碼技術(shù)、信息安全技術(shù)、應用數(shù)學、數(shù)論、信息論等多種學科的綜合性學科。

五、計算機硬件部分

計算機硬件概述
93、什么是馮諾依曼體系結(jié)構(gòu)？有什么特點？
之前存儲器只存放數(shù)據(jù)，不存程序，后來馮諾依曼提出了存儲程序的概念，此概念為基礎(chǔ)的各類計算機統(tǒng)稱為馮諾依曼機。特點是計算機由運算器，存儲器，控制器，輸入輸出設(shè)備5大部件組成，指令和數(shù)據(jù)以同等地位保存于存儲器內(nèi)，并可按地址訪存。指令和數(shù)據(jù)均用二進制代碼表示。指令在存儲器內(nèi)按順序存放。機器以運算器為中心，輸入輸出設(shè)備與存儲器之間的數(shù)據(jù)傳送通過運算器完成。

94、什么是三態(tài)門？
三態(tài)門：邏輯門的輸出端除有高低電平兩種狀態(tài)以外，還有第三種高阻態(tài)，相當于隔斷狀態(tài)。比如內(nèi)存中一個存儲單元，寫低電平，讀高電平，但不讀不寫就要用高阻態(tài)，就像把存儲單元隔離開來一樣。

95、什么是386保護模式？
80386有的一種工作模式，在這種模式下80386處理器才能充分發(fā)揮它的高性能特點。保護模式的特點：在保護模式下80386采用了全新的分段和分頁內(nèi)存管理技術(shù)，不僅允許直接尋址4GB內(nèi)存空間，而且允許使用虛擬存儲器。支持多任務工作方式?？梢允褂?-3級優(yōu)先級保護功能，實現(xiàn)程序與程序之間，用戶與操作系統(tǒng)之間的保護與隔離，為多任務操作系統(tǒng)提供優(yōu)化支持。而8086只支持單任務。還引入優(yōu)先級概念。每個存放程序和數(shù)據(jù)的存儲段都被賦予不用的優(yōu)先級。0為最高3為最低，實際上是某一任務使用處理器資源的權(quán)利，0級可以使用整個處理器資源，操作系統(tǒng)核心為0級，1級賦予外設(shè)驅(qū)動，系統(tǒng)服務等，2級用來保護一下子系統(tǒng)，如數(shù)據(jù)庫系統(tǒng)。一般用戶只能擁有3級權(quán)利，也稱用戶級。

96、PC機端口是同步還是異步？什么是異步？異步通信有沒有時鐘信號？
同步傳輸方式：該方式的數(shù)據(jù)傳輸在一個共同的時鐘信號控制下進行，時鐘通常由時鐘發(fā)生器發(fā)出，經(jīng)分頻電路送到總線上的所有模塊，總線操作有固定時序，所有信號與時鐘的關(guān)系在時序上是固定的，主控模塊和受控模塊之間沒有其他應答、控制信號。
同步傳輸：系統(tǒng)采用一個統(tǒng)一的時鐘信號來協(xié)調(diào)發(fā)送和接受雙方的傳送定時關(guān)系，優(yōu)點是傳輸速率快，缺點是必須按最慢的模塊設(shè)計公共時鐘，當差別大時，損失總線效率。
異步通信：不要求所有部件嚴格的統(tǒng)一操作時間，而是采用應答的方式，不互鎖：沒有相互制約關(guān)系，不必等待回答等一段時間默認從模塊收到請求信號，撤銷請求信號。半互鎖必須等回答才撤銷。全互鎖：主模塊發(fā)出請求信號后，等待從模塊回答才撤銷，從模塊發(fā)出回答后也必須等接受到主模塊的應答信號才撤銷回答信號。

97、什么是指令周期、時鐘周期、總線周期？之間有什么關(guān)系？一條指令有幾個機器周期？
時鐘周期：處理操作的最基本單位。(CPU的主頻)
指令周期：取出并執(zhí)行一條指令的時間。
機器周期：計算機中，為了便于管理，常把一條指令的執(zhí)行過程劃分為若干個階段，每一階段完成一項工作。例如，取指令、存儲器讀、存儲器寫等，這每一項工作稱為一個基本操作。完成一個基本操作所需要的時間稱為機器周期。時鐘周期：處理操作的最基本單位。(CPU的主頻)
指令周期、機器周期和時鐘周期之間的關(guān)系：指令周期通常用若干個機器周期表示，而機器周期時間又包含有若干個時鐘周期。
總線周期：通常把CPU通過總線對微處理器外部（存貯器或I/O接口）進行一次訪問所需時間稱為一個總線周期。一個總線周期一般包含4個時鐘周期，這4個時鐘周期分別稱4個狀態(tài)即T1狀態(tài)、T2狀態(tài)、T3狀態(tài)和T4狀態(tài)，必要時，可在T3、T4間插入一個至數(shù)個Tw。

指令和匯編
98、8086微處理器的組成和尋址方式，有哪些段寄存器？什么作用
總線接口部件BIU：指令隊列緩沖器、地址加法器、4個段寄存器、16位的指令指針寄存器和輸入輸出控制電路。BIU是8086與外部設(shè)備的借口負責處理所有總線操作。包括提供20位地址總線、16位數(shù)據(jù)總線和所有的控制總線信號，并且生成2位物理地址，負責從內(nèi)存指定地址處取出指令，送到指令隊列緩沖器中排隊，當需要操作數(shù)時，也由BIU從內(nèi)存的指定地址中取出、傳送給EU進行運算。
執(zhí)行部件EU：包括4個通用寄存器、四個專用寄存器、標識寄存器、算數(shù)邏輯單元和EU控制電路。EU負責指令的譯碼執(zhí)行，指令規(guī)定的運算器都由EU完成。指令執(zhí)行過程中取指令和譯碼執(zhí)行階段是分別由不同部件完成的。當EU執(zhí)行一條指令時，BIU就可以取出下一條指令，送往指令流隊列中排隊。在一條指令執(zhí)行完以后，即可以立即執(zhí)行嚇一跳指令，減少CPU為取指令而等待的時間，提高了CPU利用率和整個微處理器的運行速度。
尋址方式：立即尋址、直接尋址、寄存器尋址、寄存器間接尋址、寄存器相對尋址、基址変址尋址、相對基址変址尋址。
CS代碼段寄存器，存放當前程序所在段的首地址。DS數(shù)據(jù)段寄存器，存放當前程序所用數(shù)據(jù)段的首地址。SS堆棧段，存放當前程序所用堆棧段的首地址。ES附加段寄存器，存放附加數(shù)據(jù)所在段的首地址。
99、call和return具體做了哪些工作
call：參數(shù)壓棧、返回地址壓棧、保護現(xiàn)場
return：返回地址、恢復現(xiàn)場

100、什么是RISC和CISC，比較一下兩者區(qū)別和優(yōu)缺點
CISC：指令系統(tǒng)復雜龐大，80%的程序使用其20%的指令，使用頻率差距太大，難以優(yōu)化編譯生成高效目標代碼程序。由于指令豐富有專門指令完成特定功能，因此，處理特殊任務效率高。
RISC：設(shè)計者主要把精力放在那些經(jīng)常使用的指令上，盡量使用它們具有簡單、高效的特性。對不常用的功能，常通過組合簡單指令來完成。因此RISC機器上實現(xiàn)也屬功能時，效率可能較低，但可以利用流水線技術(shù)和超標量技術(shù)加以改進和彌補。

101、算術(shù)右移，邏輯右移，循環(huán)右移區(qū)別
算數(shù)右移最高位不變，其他和邏輯右移一樣。循環(huán)右移右邊移出的到左邊來。

存儲器系統(tǒng)
102、高速緩存（Cache）的工作原理以及替換算法更新策略
根據(jù)局部性原理，可以在主存和CPU之間設(shè)置一個高速的容量相對較小的Cache，如果當前正在執(zhí)行的程序和數(shù)據(jù)存放在Cache中，程序運行不必從主存儲器取指令和數(shù)據(jù)，而是訪問這個Cache即可。Cache中保存的內(nèi)容是CPU對主存儲器當前訪問頻度較高區(qū)域中內(nèi)容的映像。操作時將所訪問存儲器的物理地址同時送主存儲器和Cache，Cache控制器對CPU輸出的地址進行檢測比較，若Cache標記區(qū)中所對應的地址碼則稱為命中，否則稱為失效。命中了CPU就從Cache中讀取需要的指令或數(shù)據(jù)，失效CPU從主存儲器中讀取指令代碼或數(shù)據(jù)的同時將當前被訪問主存儲器相鄰單元中的內(nèi)容復制到Cache中，保證CPU所執(zhí)行的訪問操作主要集中在CPU和Cache之間。
工作原理：把Cache和主存分成若干塊，塊大小要保持相同，Cache與主存之間是以塊為單位進行數(shù)據(jù)交換的。塊的大小通常以在主存的一個讀、寫周期中能訪問的數(shù)據(jù)長度為限。Cache容量遠小于主存容量，所以Cache中字塊遠少于主存中的塊數(shù)，只有一小部分的內(nèi)容可以放到Cache中，保存主存中最活躍的若干塊的副本，在Cache中的每一塊都有一個標記，用于指明它是主存哪一塊副本的映像，所以該標記的內(nèi)容相當于主存中快的編號。當CPU發(fā)出請求時候，將主存地址或一部分與Cache塊的標記字段比較，相等就命中了。不相等訪問失效，根據(jù)替換算法，將該數(shù)據(jù)所在的整個字塊從主存一次掉進Cache中。
直接映像：一般是主存地址對Cache塊數(shù)取模得到Cache中的塊地址，相當于主存的空間按Cache尺寸分區(qū)，每區(qū)內(nèi)將相同塊號映像到Cache中相同位置。訪問時候根據(jù)主存中塊號讀出塊表中的組號，并與當前地址的區(qū)號進行比較，結(jié)果相同表示Cache命中。成本低易實現(xiàn)地址變換速度快，但是不夠靈活有空地方也去不了。
全相聯(lián)映像：就是主存中任何一個字塊均可以映像裝入到Cache中任何一個塊的位置上，也允許從被占滿的Cache存儲器中替換任何一個。但它地址變換需要與Cache的全部標記進行比較才能判斷出所訪主存地址的內(nèi)容是否已在Cache中。這種比較速度慢，成本高。
組相連映像：對直接和全相連映像的折中，該方式是將主存空間按Cache大小等分成區(qū)后，再將主存空間的每一區(qū)和Cache空間都分成大小相等的組，每組再等分成大小相等的塊。讓主存各區(qū)中某組中的任何一塊，均可以之間映像裝入Cache中對應的任何一塊位置上。
替換算法：先進先出、最近最少使用LRU算法、隨機。
寫策略：直寫法，CPU對Cache和主存同時寫操作?；貙懛ǎ簱Q出時候?qū)懟亍?br> 103、比較SRAM、DRAM、ROM、EPROM、EEPROM、閃存
RAM：隨機存儲器，內(nèi)容可讀可寫，主要用來存放程序、輸入的數(shù)據(jù)以及結(jié)果。當斷電會全部丟失。
SRAM：靜態(tài)隨機存取存儲器：速度非常快，基本存儲電路為6個MOS管組成一位，依靠雙穩(wěn)態(tài)電路內(nèi)部交叉反饋的機制存儲信息，集成度低，結(jié)構(gòu)復雜，功耗大，成本高一般用于高速緩存Cache。
DRAM：依靠電容存儲電荷的原理存儲信息，如單管存儲電路由一個MOS管以及一個電容組成，因此必須周期性地對其刷新，集成度高，成本低，功耗低，但必須外加刷新電路，一般PC機上內(nèi)存。
MROM：掩膜ROM是由半導體廠家用掩膜技術(shù)寫入程序，其內(nèi)容只能讀出，不能改變。
PROM：是由使用特殊方法對它進行編程，但只能寫一次，一次編程就不能修改。
EPROM：光可擦除可編程存儲器，固化的程序可以用紫外線光照射存儲器芯片上的透明窗口，使芯片內(nèi)容被刪除，擦出后又可以重新固化新的程序和數(shù)據(jù)。只能整個芯片擦除。
EEPROM：電可擦除可編程存儲器：在不同引腳加不同電壓就可以實現(xiàn)全片或字節(jié)擦寫。
FLASH存儲器：閃存，雖然屬于內(nèi)存的一種，但是斷電不丟失。U盤里就是。Flash存儲器都是按塊來讀取數(shù)據(jù)的，不是字節(jié)。

104、簡述RAM和ROM的原理和區(qū)別
RAM是隨機存儲器，可讀可寫斷電數(shù)據(jù)消失，內(nèi)存就是。
ROM是只讀存儲器：內(nèi)容只能讀不能寫的存儲器，制造時候?qū)懭搿Ｍǔ４娣殴潭ú蛔兊某绦?，斷電信息不會丟失。

105、什么是RAID（磁盤陣列），簡述一下
RAID：（廉價冗余磁盤陣列）是指由多個小容量磁盤代替一個大容量的磁盤，可以將數(shù)據(jù)交錯存放在多個磁盤上，使之可以并行存取，RAID0是最簡單的陣列架構(gòu)，寫入資料分成數(shù)個小塊，在同時送到不同的磁盤內(nèi)存儲，讀取資料時也需要從不同的磁盤內(nèi)讀取，然后再重新組合。存取速度大大加快，缺點就是如果有一個磁盤數(shù)據(jù)損壞了，整個資料不完整無法讀取了。
RAID1:鏡像備份，把所有資料保持一份完全相同的備份，使得資料完全一樣。寫入時，相同的資料會同時寫入到磁盤陣列中的每一個磁盤，讀取僅從其中一個讀取即可。

輸入輸出系統(tǒng)
106、簡述IO接口
設(shè)置接口原因：1、IO設(shè)備速度較慢，與CPU速度嚴重不匹配，通過接口可以實現(xiàn)數(shù)據(jù)緩沖。2、一臺機器通常配有多臺IO設(shè)備，他們各自有其設(shè)備編號，通過接口可以實現(xiàn)IO設(shè)備選擇3、某些設(shè)備是串行傳輸、而CPU是并行傳送，通過接口可以實現(xiàn)數(shù)據(jù)串一并格式的轉(zhuǎn)換。
IO接口功能：1、設(shè)備選擇功能，通過設(shè)備選擇線上的設(shè)備碼來確定，該設(shè)備碼送至所有設(shè)備接口，與本設(shè)備碼相符合，發(fā)出設(shè)備選擇中信號。那么這個信號便可以控制這個設(shè)備通過命令線、狀態(tài)線、和數(shù)據(jù)線與主機交換信息。2、傳送命令功能，IO接口中設(shè)有存放命令的命令寄存器以及命令譯碼器，當選擇電路輸出SEL信號，命令寄存器才接收命令碼。3、傳送數(shù)據(jù)功能，還應該具有數(shù)據(jù)緩沖的能力。4、反映IO設(shè)備工作狀態(tài)，比如沒準備好。
IO編址有兩只方式：統(tǒng)一編址和不統(tǒng)一編址。統(tǒng)一編址是將IO的地址碼和主存的地址碼統(tǒng)一起來，指令和訪問內(nèi)存的一樣。統(tǒng)一編址占用了存儲空間，減少主存容量。不統(tǒng)一編址就是IO設(shè)備的訪問有專用IO指令，不影響主存容量，但需要專用指令。

107、簡述程序查詢方式
查詢方式又稱為程序控制IO方式，查詢環(huán)節(jié)主要通過讀取狀態(tài)寄存器的標識位來檢查外設(shè)是否就緒。若沒有就緒則程序不斷循環(huán)，直到就緒后才繼續(xù)進行下一步工作。如果多個端口狀態(tài)需查詢，可定義多個標識位采用輪流查詢控制程序容易編寫，且工作可靠，適應面寬，但由于需要不斷測試狀態(tài)信息，CPU浪費。

108、簡述程序中斷查詢方式和流程，中斷可不可以被打斷？哪些情況？斷點問題
中斷方式：CPU啟動IO后，不必停止現(xiàn)行程序的運行，而IO接到啟動命令后，進入自身的準備階段。當準備就緒，就向CPU提出請求，此時CPU立即中斷現(xiàn)行程序，并保存斷電，轉(zhuǎn)至執(zhí)行中斷服務程序，為IO服務。中斷服務程序結(jié)束后，CPU又返回到程序的斷電處，繼續(xù)執(zhí)行源程序。這種方式CPU效率得到了提高。
保護現(xiàn)場：保存程序斷點，保存通用寄存器和狀態(tài)寄存器的內(nèi)容。將個寄存器內(nèi)容推入堆棧中保存。
中斷的流程：1中斷請求和響應階段，CPU在每條指令執(zhí)行的最后一個機器周期采樣中斷請求信號，在執(zhí)行完當前指令后，進入是否響應中斷的判斷流程，如果是內(nèi)部中斷或NMI非屏蔽中斷，CPU自動形成中斷類型號，如果是INTR可屏蔽中斷，進入中斷響應周期從數(shù)據(jù)線總線獲取中斷類型號。INTR還要看IF是否允許中斷。2、中斷自動處理階段：標識寄存器入棧，令TEMP=TF，暫存TF狀態(tài)，然后IF和TF清零，CS和IF入棧，根據(jù)中斷類型號查中斷向量表，這些都是硬件自動完成。3、中斷服務階段：主要執(zhí)行相應中斷服務子程序，所做的處理視應用場合而定。4、中斷返回：當執(zhí)行IRET時，自動彈出IP和CS以及標識寄存器，返回中斷前程序位置，執(zhí)行下一條指令。

109、什么是DMA，DMA控制器的組成和工作原理
程序中斷方式雖然減少CPU等待時間，使設(shè)備和主機在一定程度上并行工作，但在這種方式下，每傳送一個字或字節(jié)都要發(fā)送一次中斷，去執(zhí)行一次中斷服務程序，并且保護現(xiàn)場也要花費一定時間。
DMA方式是一種完全由硬件進行成組信息傳送的控制方式，具有程序中斷方式的優(yōu)點，即在數(shù)據(jù)準備階段，CPU與外設(shè)并行。它還降低了CPU傳送數(shù)據(jù)時的開銷，這是因為信息傳送不再經(jīng)過CPU，而在外設(shè)和內(nèi)存之間直接進行，因此成為直接存儲器存取方式，由于數(shù)據(jù)傳送不經(jīng)過CPU，也不需要保護現(xiàn)場。數(shù)據(jù)塊傳送結(jié)束給CPU結(jié)束信號。

110、簡述通道方式
IO通道是指專門負責輸入輸出的處理機。IO通道方式是DMA方式的發(fā)展，可以進一步減少CPU的干預，即把對一個數(shù)據(jù)塊的讀為單位的干預，減少為對一組數(shù)據(jù)塊的讀寫及有關(guān)的控制和管理為單位的干預，同時又可以實現(xiàn)CPU、通道和IO設(shè)備三者的并行操作，從而更有效地提高整個系統(tǒng)的資源利用率。
例如當CPU要完成一組相關(guān)的讀寫操作及有關(guān)控制時，只需向IO通道發(fā)送一條IO指令，已給出其所要執(zhí)行的通道程序的首地址和要訪問的IO設(shè)備，通道接到該指令后，通過執(zhí)行通道程序便可以完成CPU指定的IO任務，數(shù)據(jù)傳送結(jié)束時向CPU發(fā)中斷請求。
通道與一般處理機的區(qū)別是通道指令單一，沒有自己內(nèi)存，通道所執(zhí)行的通道程序是放在主機的內(nèi)存中的，也就是說通道與CPU共享內(nèi)存，與DMA區(qū)別是DMA方式需要CPU控制傳輸?shù)臄?shù)據(jù)塊大小、傳輸?shù)膬?nèi)存位置、而通道方式中這些信息是由通道控制的。
111、簡述顯卡作用，原理。
顯卡：又叫顯示適配器，是個人電腦最基本組成部分之一，是將計算機系統(tǒng)所需要的顯示信息進行轉(zhuǎn)換驅(qū)動，并向顯示器提供行掃描信號，控制顯示器正確顯示，是連接顯示器和個人電腦主板的重要元件，是“人機對話”的重要設(shè)備之一。
工作原理：1、將CPU送來的數(shù)據(jù)送到北橋（主橋）再送到GPU（圖形處理器）里面進行處理。2、將芯片處理完的數(shù)據(jù)送到顯存。3、從顯存讀取出數(shù)據(jù)再送到RAMDAC進行數(shù)據(jù)轉(zhuǎn)換的工作（數(shù)字信號轉(zhuǎn)模擬信號）。4、將轉(zhuǎn)換完的模擬信號送到顯示屏。
112、中斷的一些概念，軟件中斷，硬件中斷
中斷：計算機在執(zhí)行程序的過程中，由于某種特殊原因，向CPU輸入一定特定信號，使之執(zhí)行完現(xiàn)行一條指令后，終止現(xiàn)程序轉(zhuǎn)去執(zhí)行相應中斷服務子程序，當中斷服務子程序執(zhí)行完畢在回來執(zhí)行被中止的程序。
中斷源：可引起中毒的原因稱為中斷源。中斷的作用：實現(xiàn)CPU與IO設(shè)備并行工作，具有處理器應急事件能力，可實現(xiàn)實時處理，實現(xiàn)人機對話等。
軟件中斷：不是隨機產(chǎn)生的中斷是程序以指令形式產(chǎn)生的中斷，由它可以引出一段具有特定功能的程序，通常有三種情況引起。1、由中斷指令I(lǐng)NT引起的中斷2、由CPU的某些運算錯誤引起的中斷3、由調(diào)試程序debug設(shè)置的中斷。都是不可屏蔽。IF也無效。
硬件中斷：是隨機產(chǎn)生的不是程序事先安排好的，當這種中斷發(fā)生后，由中斷系統(tǒng)強迫CPU終止現(xiàn)行程序并轉(zhuǎn)入中斷服務子程序。中斷源可能來源：硬件故障或外設(shè)引起的中斷。只有可屏蔽中斷看IF標準。
向量中斷：事先將系統(tǒng)所有中斷服務子程序的首地址集中組織存放在一個內(nèi)存空間，叫中斷向量表，每四個字節(jié)存放一個中斷服務子程序的入口地址，一共可存放256個中斷向量，較高地址的兩個單元存放中斷服務子程序的入口地址，較低地址兩個單元存放段內(nèi)偏移量，其值就是中斷類型嗎乘以4。
響應中斷后，先將標識寄存器內(nèi)容壓棧，然后執(zhí)行一個段間間接調(diào)用指令CALL相當?shù)倪^程來啟動一個中斷過程，該過程中CPU將CS和IP壓棧，以保存斷點地址，然后將重點向量表中相應4個字節(jié)放入IP和CS轉(zhuǎn)入中斷過程。
非向量中斷：中斷服務子程序入口地址不能直接提供，由CPU查詢之后得到。
可屏蔽中斷：微處理器內(nèi)部能夠禁止的中斷，是CPU響應各種外部設(shè)備中斷的最常用的方法，是通過INTR引腳產(chǎn)生的。它受CPU內(nèi)部中斷允許標識IF控制。
不可屏蔽中斷：處理器內(nèi)不能禁止的中斷，是一種為外部緊急請求提供服務的中斷，它通過CPU的NMI引腳產(chǎn)生的，不受IF屏蔽，優(yōu)先權(quán)比可屏蔽中斷高。
中斷嵌套：CPU在處理某個中斷服務程序的過程中CPU又響應級別更高的中斷請求。
多級嵌套中斷過程：CPU響應中斷后，首先關(guān)中斷以保護程序的斷點和現(xiàn)場，就是把斷點處有關(guān)寄存器內(nèi)容以及標識寄存器狀態(tài)，壓入堆棧中保存，判斷中斷源，并轉(zhuǎn)入相應中斷服務子程序，并開中斷，可以響應更高優(yōu)先級，實現(xiàn)嵌套。執(zhí)行服務子程序完成中斷服務，然后關(guān)中斷恢復斷點處有關(guān)寄存器數(shù)據(jù)，關(guān)中斷為了保證恢復現(xiàn)場完整。然后恢復現(xiàn)場，與前面入棧過程對應。然后開中斷，中斷返回。
中斷請求觸發(fā)器：當觸發(fā)器為1，該中斷源向CPU發(fā)出中斷請求信號。

控制單元
113、什么是組合邏輯設(shè)計和微程序設(shè)計？比較兩者區(qū)別和優(yōu)缺點
組合邏輯控制：基本的門電路組合實現(xiàn)，這種方式實現(xiàn)的控制器的處理速度快，當電路龐雜，制造周期長，不靈活，可維護性差。
微程序控制：仿照程序設(shè)計的方法編寫每個機器指令對應的微程序，每個微程序由若干條微指令構(gòu)成，各微指令包含若干條微命令。所有指令對應的微程序放在只讀存儲器中，當執(zhí)行到某某指令時，取出對應微程序中的各條微指令，譯碼產(chǎn)生對應微命令，送到機器響應地方，控制其動作，微程序控制方式控制單元設(shè)計簡單、指令添加靈活，可維護性好，但速度慢。

114、什么是芯片組？有什么用？
芯片組（Chipset）是構(gòu)成主板電路的核心。一定意義上講，它決定了主板的級別和檔次。它就是"南橋"和"北橋"的統(tǒng)稱，就是把以前復雜的電路和元件最大限度地集成在幾顆芯片內(nèi)的芯片組。芯片組是整個身體的神經(jīng)，芯片組幾乎決定了這塊主板的功能，進而影響到整個電腦系統(tǒng)性能的發(fā)揮，芯片組是主板的靈魂。芯片組性能的優(yōu)劣，決定了主板性能的好壞與級別的高低。這是因為目前CPU的型號與種類繁多、功能特點不一，如果芯片組不能與CPU良好地協(xié)同工作，將嚴重地影響計算機的整體性能甚至不能正常工作。主板芯片組幾乎決定著主板的全部功能。
北橋芯片：是主板芯片組中起主導作用的最重要的組成部分，也稱為主橋。北橋芯片就是主板上離CPU最近的芯片，這主要是考慮到北橋芯片與處理器之間的通信最密切，為了提高通信性能而縮短傳輸距離。因為北橋芯片的數(shù)據(jù)處理量非常大，發(fā)熱量也越來越大，所以現(xiàn)在的北橋芯片都覆蓋著散熱片或風扇用來加強北橋芯片的散熱。
提供對CPU類型和主頻的支持、系統(tǒng)高速緩存的支持、主板的系統(tǒng)總線頻率、內(nèi)存管理（內(nèi)存類型、容量和性能）、顯卡插槽規(guī)格，ISA/PCI/AGP插槽、ECC糾錯等支持；
南橋芯片：一般位于主板上離CPU插槽較遠的下方，PCI插槽的附近，這種布局是考慮到它所連接的I/O總線較多，離處理器遠一點有利于布線。相對于北橋芯片來說，其數(shù)據(jù)處理量并不算大，所以南橋芯片一般都沒有覆蓋散熱片。它提供了對I/O的支持，提供對KBC（鍵盤控制器）、RTC（實時時鐘控制器）、USB（通用串行總線）、Ultra DMA/33(66)EIDE數(shù)據(jù)傳輸方式和ACPI（高級能源管理）等的支持，以及決定擴展槽的種類與數(shù)量、擴展接口的類型和數(shù)量（如USB2.0/1.1，IEEE1394，串口，并口，筆記本的VGA輸出接口）等。

六、程序語言、軟件工程、編譯原理

程序語言

115、C語言里面指針問題，指針有哪幾種？（比如指針的指針）
指向指針的指針**p，指向函數(shù)的指針(*p)(int, int)、指針數(shù)組（用于玩字符串）int *p[3];
指向數(shù)組的指針int (*p) [3]

116、C語言中結(jié)構(gòu)體和共同體區(qū)別
結(jié)構(gòu)體變量所占內(nèi)存長度是各成員占的內(nèi)存長度之和，每個成員分別占用自己內(nèi)存單元。而共用體變量所占用的內(nèi)存長度等于最長的成員的長度，幾個變量共享一個段內(nèi)存。不能一起初始化三個成員。

117、面向?qū)ο蟮亩x和特征
面向?qū)ο笫且环N編程思想，把復雜的問題簡單化，把我們編程時候的角色從執(zhí)行者，變成指揮者，以后開發(fā)就是找對象使用，沒有對象就創(chuàng)建一個用。并維護對象之間的關(guān)系。最大限度的重用代碼，適合開發(fā)大型軟件，把編程人員的精力主要放在現(xiàn)實世界的業(yè)務邏輯上。

118、C++和C有什么區(qū)別，什么是面向?qū)ο?，面向過程？
是兩種編程語言，C是面向過程，C++是面向?qū)ο?。C與C++的最大區(qū)別在于它們的用于解決問題的思想方法不一樣。
面向過程：就是分析出解決問題所需要的步驟，然后用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調(diào)用就可以了。
面向?qū)ο螅好嫦驅(qū)ο笫前褬?gòu)成問題事務分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在整個解決問題的步驟中的行為。

119、Java與C++有什么區(qū)別？
Java中對內(nèi)存的分配是動態(tài)的,它采用面向?qū)ο蟮臋C制,采用運算符new為每個對象分配內(nèi)存空間,而且,實際內(nèi)存還會隨程序運行情況而改變.程序運行中,每個, Java系統(tǒng)自動對內(nèi)存進行掃描,對長期不用的空間作為”垃圾”進行收集,使得系統(tǒng)資源得到更充分地利用.按照這種機制,程序員不必關(guān)注內(nèi)存管理問題,這使Java程序的編寫變得簡單明了,并且避免了了由于內(nèi)存管理方面的差錯而導致系統(tǒng)出問題.而C語言通過malloc()和free()這兩個庫函數(shù)來分別實現(xiàn)分配內(nèi)在和釋放內(nèi)存空間的,C++語言中則通過運算符new和delete來分配和釋放內(nèi)存.在C和C++這仲機制中,程序員必須非常仔細地處理內(nèi)存的使用問題.一方面,如果對己釋放的內(nèi)存再作釋放或者對未曾分配的內(nèi)存作釋放,都會造成死機;而另一方面,如果對長期不用的或不再使用的內(nèi)存不釋放,則會浪費系統(tǒng)資源,甚至因此造成資源枯竭.
Java不再使用指針.指針是C和C++中最靈活,也最容易產(chǎn)生錯誤的數(shù)據(jù)類型.由指針所進行的內(nèi)存地址操作常會造成不可預知的錯誤,同時通過指針對某個內(nèi)存地址進行顯式類型轉(zhuǎn)換后,可以訪問一個C++中的私有成員,從而破壞安全性.而Java對指針進行完全地控制,程序員不能直接進行任何指針操作.
多重繼承：雖然多重繼承是C或C++語言從多個父類中派生一個類的有效方法,但是由于這種派生很復雜,因而也很容易產(chǎn)生問題。正是由于這種原因,Java的開發(fā)者沒有采用多重繼承,Java的類似Objective C協(xié)議的接口能夠完成C++中多重繼承能夠完成的所有任務。

120、從抽象的角度說說什么是類的繼承和泛化、組合、聚合
繼承指的是一個類（稱為子類、子接口）繼承另外的一個類（稱為父類、父接口）的功能，并可以增加它自己的新功能的能力
泛化表示類與類之間的繼承關(guān)系，接口與接口之間的繼承關(guān)系，或類對接口的實現(xiàn)關(guān)系。一般化的關(guān)系是從子類指向父類的，與繼承或?qū)崿F(xiàn)的方法相反。
關(guān)聯(lián)關(guān)系的一種，是強的關(guān)聯(lián)關(guān)系。聚合是整體和個體的關(guān)系。聚合關(guān)系也是通過實例變量實現(xiàn)的。例如汽車、發(fā)動機、輪胎，一個汽車對象由一個發(fā)動機對象，四個輪胎對象組成。
組合關(guān)系也是關(guān)聯(lián)關(guān)系的一種，是比聚合關(guān)系更強的關(guān)系。合成關(guān)系是不能共享的。例如人有四肢、頭等。表示類之間整體和部分的關(guān)系，組合關(guān)系中部分和整體具有統(tǒng)一的生存期。一旦整體對象不存在，部分對象也將不存在。部分對象與整體對象之間具有共生死的關(guān)系。
實現(xiàn)是說明和實體之間關(guān)系

121、C語言中怎樣定義字符串
Char string[] = “Hello”;
Char *string = “Hello”;

122、MVC模型
MVC是一個框架模式，它強制性的使應用程序的輸入、處理和輸出分開。使用MVC應用程序被分成三個核心部件：模型、視圖、控制器。它們各自處理自己的任務。視圖是用戶看到并與之交互的界面。模型表示企業(yè)數(shù)據(jù)和業(yè)務規(guī)則?？刂破鹘邮苡脩舻妮斎氩⒄{(diào)用模型和視圖去完成用戶的需求，

編譯原理

123、編譯過程有哪些步驟，編譯過程生成什么文件？
詞法分析：是編譯過程的第一個階段，這個階段任務就是從左到右，一個字符一個字符地讀入源程序，對字符流進行掃描和分解，從而辨別出一個個單詞，包括標識符，保留關(guān)鍵字以及一些符號。
語法分析：語法分析是編譯過程的第二個階段，語法分析的任務是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如語句，表達式等。一般這種語法短語也稱語法單位，可以表示成語法樹。中序遍歷還原。依據(jù)語言的語法規(guī)則，通過分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。
語義分析：是審查源程序有無語義錯誤，為代碼生成階段手收集類型信息，比如一個工作是類型檢查，審查每個運算符是否具有語言規(guī)范允許的運算對象，不符合報錯，比如數(shù)組下標你寫負數(shù)報錯。
中間代碼生成：進行語法分析和語義分析階段的工作后，有的編譯程序?qū)⒃闯绦?，編程一種內(nèi)部表示形式，叫做中間代碼，設(shè)計要點是容易生成，容易翻譯成目標代碼。
代碼優(yōu)化：對中間代碼進行變換或進行改造，使其變得更加高效，省時間和空間。
目標代碼生成：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼，編譯最后階段與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。

軟件工程

124、軟件開發(fā)步驟，模塊設(shè)計規(guī)則，詳細設(shè)計如何實現(xiàn)？
需求分析：借助當前系統(tǒng)邏輯模型導出目標系統(tǒng)邏輯模型，準確回答系統(tǒng)必須做什么的問題，比如功能要求，性能要求。得到數(shù)據(jù)流圖。
概要設(shè)計（總體設(shè)計）：就是概要的說系統(tǒng)如何實現(xiàn)，選擇一個最優(yōu)方案，設(shè)計軟件的結(jié)構(gòu)，確定系統(tǒng)中每個程序時有哪些模塊組成的，以及這些模塊相互之間關(guān)系。設(shè)計數(shù)據(jù)庫。
模塊設(shè)計規(guī)則有：信息隱藏，把實現(xiàn)細節(jié)隱藏，彼此之間為了完成系統(tǒng)功能而必須交換的信息。模塊獨立：兩個標準高內(nèi)聚低耦合。很重要有效模塊化，的軟件開發(fā)容易，尤其是多人分工合作，測試維護也很方便。內(nèi)聚：一個模塊內(nèi)部各元素彼此結(jié)合的緊密程度。耦合：衡量不同模塊彼此之間相互依賴的緊密程度。
詳細設(shè)計：不時具體編程，而是設(shè)計出程序的藍圖，以后程序員將根據(jù)這個藍圖寫出實際的程序代碼。就是對概要設(shè)計的一個細化，就是詳細設(shè)計每個模塊實現(xiàn)算法，所需的局部結(jié)構(gòu)。對數(shù)據(jù)庫進行設(shè)計，即確定數(shù)據(jù)庫的物理結(jié)構(gòu)。傳統(tǒng)軟件開發(fā)方法的詳細設(shè)計主要是用結(jié)構(gòu)化程序設(shè)計法。詳細設(shè)計的表示工具有圖形工具和語言工具。圖形工具有業(yè)務流圖、程序流程圖、NS圖。語言工具有偽碼等。還有人機界面的設(shè)計。

125、什么是軟件測試？測試和調(diào)試有啥區(qū)別？
調(diào)試是程序完工前的工作，調(diào)試前的程序一般都不是正確的，調(diào)試后才是正確的。就是通過種種手段，將程序中的bug給定位出來，然后解決。
測試是程序基本完成以后的步驟，一般是作為正確性驗證的，測試可能會發(fā)現(xiàn)問題文章來源地址http://www.zghlxwxcb.cn/news/detail-407359.html

到了這里，關(guān)于計算機復試面試基礎(chǔ)知識（八股文）（數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計網(wǎng)、機組等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！