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

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

概念問(wèn)題

C++/數(shù)據(jù)結(jié)構(gòu)

1、簡(jiǎn)述你對(duì)“面向?qū)ο蟆焙汀懊嫦蜻^(guò)程”編程思想的認(rèn)識(shí)與思考用就能夠了。

面向過(guò)程

例：考慮一個(gè)工資系統(tǒng)T

?這種功能明確的系統(tǒng)確實(shí)適合結(jié)構(gòu)化的開(kāi)發(fā)方法：自頂3

下，逐步求精。

?你完美地完成了任務(wù)。

?而后，極有可能，客戶會(huì)跑過(guò)來(lái)跟你說(shuō)：

?給我加個(gè)統(tǒng)計(jì)報(bào)我撤

?卜?個(gè)月我想一些人發(fā)記時(shí)工資，一些人發(fā)計(jì)件I:資啊行啊，有人

每月一發(fā)，有人林周一發(fā)哦

?加個(gè)個(gè)人所得稅系統(tǒng)接口

?加個(gè)圖像用戶界面，用交互查詢

就是分析出解決問(wèn)題所需要的步驟，然后用函數(shù)

把這些步驟一步一步實(shí)現(xiàn)，使用的時(shí)候一個(gè)一個(gè)

依次調(diào)

面向?qū)ο笫前褬?gòu)成問(wèn)題事務(wù)分解成各個(gè)對(duì)象，建

立對(duì)象的目的不是為了完成一個(gè)步驟，而是為了

描敘某個(gè)事物在整個(gè)解決問(wèn)題的步驟中的行為。

例如五子棋，面向過(guò)程的設(shè)計(jì)思路就是首先分析

問(wèn)題的步驟：1、開(kāi)始游戲，2、黑子先走，3、繪

制畫(huà)面，4、判斷輸贏，5、輪到白子，6、繪制

畫(huà)面，7、判斷輸贏，8、返回步驟2,9、輸出

最后結(jié)果。把上面每個(gè)步驟用分別的函數(shù)來(lái)實(shí)

現(xiàn)，問(wèn)題就解決了。

而面向?qū)ο蟮脑O(shè)計(jì)則是從另外的思路來(lái)解決問(wèn)

題。整個(gè)五子棋能夠分為1、黑白雙方，這兩方

的行為是一模一樣的，2、棋盤(pán)系統(tǒng)，負(fù)責(zé)繪制

畫(huà)面，3、規(guī)則系統(tǒng)，負(fù)責(zé)判定諸如犯規(guī)、輸贏

等。第一類對(duì)象（玩家對(duì)象）負(fù)責(zé)接受用戶輸入,

并告知第二類對(duì)象（棋盤(pán)對(duì)象）棋子布局的變化,

棋盤(pán)對(duì)象接收到了棋子的i變化就要負(fù)責(zé)在屏

幕上面顯示出這種變化，同時(shí)利用第三類對(duì)象

（規(guī)則系統(tǒng)）來(lái)對(duì)棋局進(jìn)行判定。

能夠明顯地看出，面向?qū)ο笫且怨δ軄?lái)劃分問(wèn)

題，而不是步驟。同樣是繪制棋局，這樣的行為

在面向過(guò)程的設(shè)計(jì)中分散在了總多步驟中，很可

能出現(xiàn)不同的繪制版本，因?yàn)橥ǔＴO(shè)計(jì)人員會(huì)考

慮到實(shí)際情況進(jìn)行各種各樣的簡(jiǎn)化。而面向?qū)ο?/p>

的設(shè)計(jì)中，繪圖只可能在棋盤(pán)對(duì)象中出現(xiàn)，從而

保證了繪圖的統(tǒng)一。

功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計(jì)的可擴(kuò)展性。

比如我要加入悔棋的功能，如果要改動(dòng)面向過(guò)程

的設(shè)計(jì)，那么從輸入到判斷到顯示這一連串的步

驟都要改動(dòng)，甚至步驟之間的循序都要進(jìn)行大規(guī)

模調(diào)整。如果是面向?qū)ο蟮脑?，只用改?dòng)棋盤(pán)對(duì)

象就行了，棋盤(pán)系統(tǒng)保存了黑白雙方的棋譜，簡(jiǎn)

單回溯就能夠了，而顯示和規(guī)則判斷則不用顧

及，同時(shí)整個(gè)對(duì)對(duì)象功能的調(diào)用順序都沒(méi)有變

化，改動(dòng)只是局部的。

再比如我要把這個(gè)五子棋游戲改為圍棋游戲，如

果你是面向過(guò)程設(shè)計(jì)，那么五子棋的規(guī)則就分布

在了你的程序的每一個(gè)角落，要改動(dòng)還不如重

寫(xiě)。但是如果你當(dāng)初就是面向?qū)ο蟮脑O(shè)計(jì)，那么

你只用改動(dòng)規(guī)則對(duì)象就能夠了，五子棋和圍棋的

區(qū)別不就是規(guī)則嗎？（當(dāng)然棋盤(pán)大小仿佛也不一

樣，但是你會(huì)覺(jué)得這是一個(gè)難題嗎?直接在棋盤(pán)

對(duì)象中進(jìn)行一番小改動(dòng)就能夠了。）而下棋的大

致步驟從面向?qū)ο蟮慕嵌葋?lái)看沒(méi)有任何變化。

當(dāng)然，要達(dá)到改動(dòng)只是局部的需要設(shè)計(jì)的人有足

夠的經(jīng)驗(yàn)，使用對(duì)象不能保證你的程序就是面向

對(duì)象，初學(xué)者或者很蹩腳的程序員很可能以面向

對(duì)象之虛而行面向過(guò)程之實(shí)，這樣設(shè)計(jì)出來(lái)的所

謂面向?qū)ο蟮某绦蚝茈y有良好的可移植性和可

擴(kuò)展性。

2、ADT是什么?簡(jiǎn)述你對(duì)“數(shù)據(jù)抽象”和“信息隱藏”的認(rèn)

識(shí)

抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)稱ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的

一組操作。抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型

(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。

抽象數(shù)據(jù)類型是與表示無(wú)關(guān)的數(shù)據(jù)類型，是一個(gè)

數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)

抽象數(shù)據(jù)類型進(jìn)行定義時(shí)，必須給出它的名字及

各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函

數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及

具體實(shí)現(xiàn)，程序設(shè)計(jì)中就能夠像使用基本數(shù)據(jù)類

型那樣，十分方便地使用抽象數(shù)據(jù)類型。

抽象數(shù)據(jù)類型通過(guò)類(class)實(shí)現(xiàn)

X程序設(shè)計(jì)語(yǔ)言對(duì)抽象數(shù)據(jù)類型的支持是指允

許用戶自定義具有如下特征的數(shù)據(jù)類型：

1.模塊封裝：Therepresentationof,and

operationson,objectsofthetypeare

definedinasingle

syntacticunit

2.信息隱蔽：Therepresentationofobjects

ofthetypeishiddenfromtheprogramunits

thatusethese

objects,sotheonlyoperationspossibleare

thoseprovidedinthetype'sdefinition

3、const和static有什么作用？

const是一個(gè)C和C++語(yǔ)言的關(guān)鍵字，它限定一

個(gè)變量不允許被改變，即只讀。使用const在一

定程度上能夠提高程序的安全性和可靠性，也便

于實(shí)現(xiàn)對(duì)此進(jìn)行優(yōu)化（如把只讀對(duì)象放入ROM

中）。const作為類型限定符，是類型的一部分。

靜態(tài)變量（StaticVariable）在計(jì)克機(jī)編程領(lǐng)域指在程序執(zhí)行前系統(tǒng)就為之（也即在運(yùn)行時(shí)中不

再改變分配情況）存儲(chǔ)空間的一類變量.與之相對(duì)應(yīng)的是在運(yùn)行時(shí)只暫時(shí)存在的自動(dòng)變量（即局部變量）

與以動(dòng)態(tài)分配方式獲取存儲(chǔ)空間的些對(duì)象，其中自動(dòng)變量的存儲(chǔ)空間在遇里戰(zhàn)上分配與釋放。

初始化為非零值的靜態(tài)分配數(shù)據(jù)和全局?jǐn)?shù)據(jù)存在數(shù)據(jù)段中，運(yùn)行相同程序的每個(gè)進(jìn)程都有H己的數(shù)據(jù)段.

初始化為零值的靜態(tài)分配數(shù)據(jù)和全局?jǐn)?shù)據(jù)存放在進(jìn)程的BSS區(qū)域內(nèi).

BSS段:BSS段（bsssegment）通常是指用來(lái)存放程序中未初始化的全局變盤(pán)的一塊內(nèi)存區(qū)域.BSS是英文

BlockStatedbySymbol的簡(jiǎn)稱.BSS段屬于靜態(tài)內(nèi)存分配.

足BlockStartedbySymbol"的縮寫(xiě),意為“以符號(hào)開(kāi)始的塊”.

BSS是Unix鞋接器產(chǎn)生的未初始化數(shù)據(jù)段.其他的段分別是包含程序代碼的“text”

段和包含已初始化數(shù)據(jù)的”data”段.BSS段的變室只有名稱和大小卻沒(méi)有值.此幺后來(lái)

被許多文件格式使用.包括吒?”以符號(hào)開(kāi)始的塊”指的是編譯器處現(xiàn)卡初始化數(shù)據(jù)的地

方?BSS”.不包含任何數(shù)據(jù)，只是簡(jiǎn)單的維護(hù)開(kāi)始和結(jié)束的地址，以便內(nèi)存區(qū)能在壇行

時(shí)被有效地清冬.BSS節(jié)任應(yīng)用程療的一進(jìn)制映象文件中并不存莊.

數(shù)據(jù)段:數(shù)據(jù)段(datasegment)通常是指用來(lái)存放程序中一初始化的全局變盤(pán)的一塊內(nèi)存區(qū)域.數(shù)據(jù)段屬「靜

態(tài)內(nèi)存分配。靜態(tài)變■存放在data段中

代碼段:代碼段(codesegment/textsegment)通常是指用來(lái)存放程序執(zhí)行代刊的?塊內(nèi)存區(qū)域.這部分區(qū)域的

大小在程序運(yùn)行前就已經(jīng)確定.并1L內(nèi)存區(qū)城通常屈于只讀，某些架構(gòu)也允i午代碼段為可寫(xiě).即允許修改程序-在

代碼段中?也仃可能包含一些只漆的常數(shù)變埴,例如字符小常量等。代碼段是存放了程序代碼的數(shù)據(jù)，假如機(jī)器

中有數(shù)個(gè)進(jìn)程運(yùn)行相同的一個(gè)程序，那么它們就可以使用同一個(gè)代碼段。

(heap)：堆是用于存放進(jìn)程運(yùn)行中被動(dòng)態(tài)分配的內(nèi)存段.它的K小并不固定，可動(dòng)態(tài)擴(kuò)張或縮減。與進(jìn)程調(diào)

用malloc等函數(shù)分配內(nèi)存時(shí).新分配的內(nèi)存就被動(dòng)態(tài)添加到堆上(堆被擴(kuò)張)；當(dāng)利用free等函數(shù)擇放內(nèi)存時(shí)，

被釋放的內(nèi)存從堆中被剔除(堆被縮減)

腳加㈤：棧;稱堆枝,是用戶「「「匕創(chuàng)建的局部變量.也中定義的變工(但

不包括static:聲明的變量，static意味著在數(shù)據(jù)段中存放變量).除此以外，任函數(shù)被調(diào)用時(shí)，其參數(shù)也會(huì)被出入

發(fā)起調(diào)用的進(jìn)程棧中,并且待到調(diào)用結(jié)束后，函數(shù)的返回值也會(huì)被存放回棧中.由廣棧的先進(jìn)先出特點(diǎn).所以棧

特別方便用來(lái)保存/恢復(fù)調(diào)用現(xiàn)場(chǎng).從這個(gè)意義上講,我們可以把堆棧看成?個(gè)寄存、交換臨時(shí)數(shù)據(jù)的內(nèi)存區(qū)。

4、友元關(guān)系的利與弊

如果將一個(gè)函數(shù)或一個(gè)類聲明為另一個(gè)類的友

元，那么它就能夠直接存取這個(gè)類對(duì)象中的各種

數(shù)據(jù)，而不必在意這些數(shù)據(jù)的封裝級(jí)別，即無(wú)論

是private的,protected的,還是public的,

有錢同使，有難同當(dāng)。

5、C++多態(tài)的實(shí)現(xiàn)

1.用virtual關(guān)鍵字申明的函數(shù)叫做虛函數(shù)，

虛函數(shù)肯定是類的成員函數(shù)。

2.存在虛函數(shù)的類都有一個(gè)一維的虛函數(shù)表叫

做虛表。類的對(duì)象有一個(gè)指向虛表開(kāi)始的虛指

針。虛表是和類對(duì)應(yīng)的，虛表指針是和對(duì)象對(duì)應(yīng)

的。

3.多態(tài)性是一個(gè)接口多種實(shí)現(xiàn)，是面向?qū)ο蟮?/p>

核心。分為類的多態(tài)性和函數(shù)的多態(tài)性。

4.多態(tài)用虛函數(shù)來(lái)實(shí)現(xiàn)，結(jié)合動(dòng)態(tài)綁定。

5.純虛函數(shù)是虛函數(shù)再加上二Oo

6.抽象類是指包括至少一個(gè)純虛函數(shù)的類。

構(gòu)造函數(shù)順序：

基類構(gòu)造函數(shù)。派生類構(gòu)造函數(shù)

前面輸出的結(jié)果是因?yàn)榫幾g器在編譯的時(shí)候，就

已經(jīng)確定了對(duì)象調(diào)用的函數(shù)的地址，要解決這個(gè)

問(wèn)題就要使用遲綁定(latebinding)技術(shù)。當(dāng)

編譯器使用遲綁定時(shí)，就會(huì)在運(yùn)行時(shí)再去確定對(duì)

象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采

用遲綁定，就要在基類中聲明函數(shù)時(shí)使用

virtual關(guān)鍵字(注意，這是必須的，很多學(xué)員

就是因?yàn)闆](méi)有使用虛函數(shù)而寫(xiě)出很多錯(cuò)誤的例

子)，這樣的函數(shù)我們稱為虛函數(shù)。一旦某個(gè)函

數(shù)在基類中聲明為virtual,那么在所有的派生

類中該函數(shù)都是virtual,而不需要再顯式地聲

明為virtualo

前面輸出的結(jié)果是因?yàn)榫幾g器在編譯的時(shí)候，就

已經(jīng)確定了對(duì)象調(diào)用的函數(shù)的地址，要解決這個(gè)

問(wèn)題就要使用遲綁定（latebinding）技術(shù)。當(dāng)

編譯器使用遲綁定時(shí)，就會(huì)在運(yùn)行時(shí)再去確定對(duì)

象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采

用遲綁定，就要在基類中聲明函數(shù)時(shí)使用

virtual關(guān)鍵字（注意，這是必須的，很多學(xué)員

就是因?yàn)闆](méi)有使用虛函數(shù)而寫(xiě)出很多錯(cuò)誤的例

子），這樣的函數(shù)我們稱為虛函數(shù)。一旦某個(gè)函

數(shù)在基類中聲明為virtual,那么在所有的派生

類中該函數(shù)都是virtual,而不需要再顯式地聲

明為virtualo

編譯器在編譯的時(shí)候，發(fā)現(xiàn)基類中有虛函數(shù)，此

時(shí)編譯器會(huì)為每個(gè)包含虛函數(shù)的類創(chuàng)建一個(gè)虛

表（即vtable）,該表是一個(gè)一維數(shù)組，在這個(gè)

數(shù)組中存放每個(gè)虛函數(shù)的地址。

那么如何定位虛表呢?編譯器另外還為每個(gè)類的

對(duì)象提供了一個(gè)虛表指針（即vptr）,這個(gè)指針

指向了對(duì)象所屬類的虛表。在程序運(yùn)行時(shí)，根據(jù)

對(duì)象的類型去初始化vptr

基類1的對(duì)

索所占內(nèi)存

派生類時(shí)象

哥占麻

派生類對(duì)象自身

增劉的學(xué)分

,從而讓

基類的viable

繼承類的"table基類和繼承類的虛

I■表

vptr正確的指向所屬類的虛表，從而在調(diào)用虛

函數(shù)時(shí)，就能夠找到正確的函數(shù)。對(duì)于例1-2的

程序，由于pAn實(shí)際指向的對(duì)象類型是fish,

因此vptr指向的fish類的vtable,當(dāng)調(diào)用

pAn->breathe()時(shí)，根據(jù)虛表中的函數(shù)地址找到

的就是fish類的breathe()函數(shù)。

那么虛表指針在什么時(shí)候，或者說(shuō)在什么地方初

始化呢？

答案是在構(gòu)造函數(shù)中進(jìn)行虛表的創(chuàng)建和虛表指

針的初始化。還記得構(gòu)造函數(shù)的調(diào)用順序嗎，在

構(gòu)造子類對(duì)象時(shí)，要先調(diào)用父類的構(gòu)造函數(shù)，此

時(shí)編譯器只“看到了”父類，并不知道后面是否

后還有繼承者，它初始化父類對(duì)象的虛表指針，

該虛表指針指向父類的虛表。當(dāng)執(zhí)行子類的構(gòu)造

函數(shù)時(shí)，子類對(duì)象的虛表指針被初始化，指向自

身的虛表。對(duì)于例2-2的程序來(lái)說(shuō)，當(dāng)fish類

的fh對(duì)象構(gòu)造完畢后，其內(nèi)部的虛表指針也就

被初始化為指向fish類的虛表。在類型轉(zhuǎn)換后,

調(diào)用pAn->breathe(),由于pAn實(shí)際指向的是

fish類的對(duì)象，該對(duì)象內(nèi)部的虛表指針指向的

是fish類的虛表，因此最終調(diào)用的是fish類的

breathe()函數(shù)。

要注意:對(duì)于虛函數(shù)調(diào)用來(lái)說(shuō)，每一個(gè)對(duì)象內(nèi)部

都有一個(gè)虛表指針，該虛表指針被初始化為本類

的虛表。所以在程序中，不論你的對(duì)象類型如何

轉(zhuǎn)換，但該對(duì)象內(nèi)部的虛表指針是固定的，所以

呢，才能實(shí)現(xiàn)動(dòng)態(tài)的對(duì)象函數(shù)調(diào)用，這就是C++

多態(tài)性實(shí)現(xiàn)的原理。

6、STL是什么?組成部分和核心作用

標(biāo)準(zhǔn)模板庫(kù)(蔓文：StandardTemplateLibrary.縮寫(xiě):STL),是一個(gè)C++軟件庫(kù),也是C++

標(biāo)準(zhǔn)程序庫(kù)的一部分。其中包含5個(gè)組件，分別為算法、容器、迭代器、函數(shù)、適配黑。容器即物之所

屬；算法是解決問(wèn)題的方式；迭代器是對(duì)容器的訪問(wèn)邏輯的抽象，是連接算法和容器的紐帶，通過(guò)添加

了一種間接層的方式實(shí)現(xiàn)了容器和算法之間的獨(dú)立。本文從應(yīng)用的角度對(duì)STL的方方面面進(jìn)行了簡(jiǎn)單的

介紹。

糜是C+十程序設(shè)計(jì)語(yǔ)言中的一個(gè)重要特征，而標(biāo)準(zhǔn)模板庫(kù)正是基于此特征。標(biāo)準(zhǔn)模板庫(kù)使得C++

編程語(yǔ)言在有了同Java一樣強(qiáng)大的類庫(kù)的同時(shí),保有了更大的可擴(kuò)展性。

標(biāo)準(zhǔn)模板庫(kù)于1994年2月年正式成為ANSI/ISO

C++的一部份，它的出現(xiàn)，促使C++程序員的思

維方式更朝向泛型編程(genericprogram)發(fā)

展。

7、闡述C++在什么情況下必須進(jìn)行運(yùn)算符重載。

9

8、為什么說(shuō)“繼承是C++面向?qū)ο蟮囊粋€(gè)主要

特征之一”，請(qǐng)做一下簡(jiǎn)要說(shuō)明。

9

9、請(qǐng)說(shuō)明函數(shù)模板(FunctionTemplate)和函

數(shù)模板實(shí)例化(function-1emplate

specification)的區(qū)別和聯(lián)系。

函數(shù)模板實(shí)例化

在函數(shù)模板為每個(gè)類型時(shí)首先調(diào)用中，編譯器創(chuàng)

建一個(gè)實(shí)例化。每個(gè)實(shí)例化是為該類型的該模

板化功能的版本。在中，此函數(shù)為類型時(shí)，使

用此實(shí)例化將調(diào)用。如果您有幾個(gè)相同的實(shí)例

化，即使在不同的模塊，因此，只有該實(shí)例化的

一個(gè)副本在可執(zhí)行文件將結(jié)果。

函數(shù)參數(shù)將所有參數(shù)的函數(shù)模板允許和參數(shù)，對(duì)

該參數(shù)不依賴于模板參數(shù)的位置。

函數(shù)模板能夠通過(guò)聲明與特定類型的模板顯式

實(shí)例化作為參數(shù)。

C++中提供了函數(shù)模板，實(shí)際上是建立一個(gè)通用

函數(shù)，其函數(shù)類型和形參類型不具體指定，用一

個(gè)虛擬的類型來(lái)代表，這個(gè)通用函數(shù)就成為函數(shù)

模板。使用模板的好處就是對(duì)于那些函數(shù)體相同

的函數(shù)都能夠用這個(gè)模板來(lái)代替，而不必去定義

每個(gè)具體的函數(shù)去實(shí)現(xiàn)。下面通過(guò)一個(gè)簡(jiǎn)單的具

體例子(比較兩個(gè)數(shù)的大小)來(lái)說(shuō)明：

#include<iostream>

usingnamespacestd;

template<classT>〃模板聲明，T為類型參數(shù)

TMax(Ta,Tb)〃定義一個(gè)通用函數(shù)，用T作

虛擬的類型名

if(a>b)

{

returna;

)

else

returnb;

}

模板(Template)指C++程廳改適宜中的正當(dāng)H卜；與二別出板,大:體對(duì)應(yīng)于iava和C#中的泛

型。目前，模板己經(jīng)成為C++的泛型編程中不可缺少的一部分。

模扳定義以關(guān)鍵字template開(kāi)始，后接模板形參表，模板形參表是用尖括號(hào)括住的一個(gè)或者多個(gè)模

板形參的列表，形參之間以逗號(hào)分隔。模板形參可以是表示類型的類型形參，也可以是表示常量表達(dá)式

的非類型影參。作類型影參跟作類型說(shuō)明符之后聲明.類型形參跟在關(guān)鉞字class或typename之后定

義.

模板是C++程序員絕佳的武器，特別是結(jié)合了多重繼承(multipleinheritance)與運(yùn)算符重載

(operatoroverloading)之后。C++的標(biāo)準(zhǔn)庫(kù)提供許多有用的函數(shù)大多結(jié)合了模板的觀念，如STL以

及IOStream.

模板實(shí)例化（templateinstantiation）是指

在編譯或鏈接時(shí)生成函數(shù)模板或類模板的具體

實(shí)例源代碼。ISOC++定義了兩種模板實(shí)例化方

法:隱式實(shí)例化（當(dāng)使用實(shí)例化的模板時(shí)自動(dòng)地

在當(dāng)前代碼單元之前插入模板的實(shí)例化代碼）、

顯式實(shí)例化（直接聲明模板實(shí)例化）。

10、編譯和鏈接的過(guò)程

源文件的編譯過(guò)程包含兩個(gè)主要階段，而它們之

間的轉(zhuǎn)換是自動(dòng)的。第一個(gè)階段是預(yù)處理階段，

在正式的編譯階段之前進(jìn)行。預(yù)處理階段將根據(jù)

已放置在文件中的預(yù)處理指令來(lái)修改源文件的

內(nèi)容。#include指令就是一個(gè)預(yù)處理指令，

這個(gè)在編譯之前修改源文件的方式提供了很大

的靈活性，以適應(yīng)不同的計(jì)算機(jī)和操作系統(tǒng)環(huán)境

的限制。一個(gè)環(huán)境需要的代碼跟另一個(gè)環(huán)境所需

的代碼可能有所不同，因?yàn)榭捎玫挠布虿僮飨?/p>

統(tǒng)是不同的。在許多情況下，能夠把用于不同環(huán)

境的代碼放在同一個(gè)文件中，再在預(yù)處理階段修

改代碼，使之適應(yīng)當(dāng)前的環(huán)境。

預(yù)處理器顯示為一個(gè)獨(dú)立的操作，但一般不能獨(dú)

立于編譯器來(lái)執(zhí)行這個(gè)操作。調(diào)用編譯器會(huì)自動(dòng)

執(zhí)行預(yù)處理過(guò)程，之后才編譯代碼。

編譯器為給定源文件輸出的是機(jī)器碼，執(zhí)行這個(gè)

過(guò)程需要較長(zhǎng)時(shí)間。在對(duì)象文件之間并沒(méi)有建立

任何連接。對(duì)應(yīng)于某個(gè)源文件的對(duì)象文件包含在

其它源文件中定義的函數(shù)引用或其它指定項(xiàng)的

引用，而這些函數(shù)或項(xiàng)仍沒(méi)有被解析。同樣，也

沒(méi)有建立同庫(kù)函數(shù)的鏈接。實(shí)際上，這些函數(shù)的

代碼并不是文件的一部分。這些工作是由鏈接程

序（有時(shí)稱為鏈接編輯器）完成的

鏈接程序把所有對(duì)象文件中的機(jī)器碼組合在一

起，并解析它們之間的交叉引用。它還集成了對(duì)

象模塊所使用的庫(kù)函數(shù)的代碼。這是鏈接程序的

一種簡(jiǎn)化表示，因?yàn)檫@里假定在可執(zhí)行模塊中，

模塊之間的所有鏈接都是靜態(tài)建立的。實(shí)際上有

些鏈接是動(dòng)態(tài)的，即這些鏈接是在程序執(zhí)行時(shí)建

立的。

鏈接程序靜態(tài)地建立函數(shù)之間的鏈接，即在程序

執(zhí)行之前建立組成程序的源文件中所包含的函

數(shù)鏈接。動(dòng)態(tài)建立的函數(shù)之間的鏈接（在程序執(zhí)

行過(guò)程中建立的鏈接）將函數(shù)編譯并鏈接起來(lái)，

創(chuàng)建另一種可執(zhí)行模塊一一動(dòng)態(tài)鏈接庫(kù)或共享

庫(kù)。動(dòng)態(tài)鏈接庫(kù)中的函數(shù)鏈接是在程序調(diào)用函數(shù)

時(shí)才建立的，在程序調(diào)用之前，該鏈接是不存在

的。

動(dòng)態(tài)鏈接庫(kù)有幾個(gè)重要的優(yōu)點(diǎn)。一個(gè)主要的優(yōu)點(diǎn)

是動(dòng)態(tài)鏈接庫(kù)中的函數(shù)能夠在幾個(gè)并行執(zhí)行的

程序之間共享，這將節(jié)省相同函數(shù)占用的內(nèi)存空

間。另一個(gè)優(yōu)點(diǎn)是動(dòng)態(tài)鏈接庫(kù)在調(diào)用其中的函數(shù)

之前是不會(huì)加載到內(nèi)存中的。也就是說(shuō)，如果不

使用給定動(dòng)態(tài)鏈接庫(kù)中的函數(shù)，該動(dòng)態(tài)鏈接庫(kù)就

不會(huì)占用內(nèi)存空間

11、解釋“優(yōu)先級(jí)隊(duì)列”這一抽象數(shù)據(jù)類型及實(shí)現(xiàn)方法

如果我們給每個(gè)元素都分配一個(gè)數(shù)字來(lái)標(biāo)記其

優(yōu)先級(jí)，不妨設(shè)較小的數(shù)字具有較高的優(yōu)先級(jí)，

這樣我們就能夠在一個(gè)集合中訪問(wèn)優(yōu)先級(jí)最高

的元素并對(duì)其進(jìn)行查找和刪除操作了。這樣，我

們就引入了優(yōu)先級(jí)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。

缺省情況下，優(yōu)先級(jí)隊(duì)列利用一個(gè)最大堆完成

函數(shù)列表：

empty()如果優(yōu)先隊(duì)列為空，則返回真

pop()刪除第一個(gè)元素

push()加入一個(gè)元素

sizeO返回優(yōu)先隊(duì)列中擁有的元素的個(gè)數(shù)

top()返回優(yōu)先隊(duì)列中有最高優(yōu)先級(jí)的元素

用途就不用多說(shuō)了吧，例如Huffman編碼、分支

限界、A*啟發(fā)式都需要用到優(yōu)先隊(duì)列存放信息。

12、逆波蘭式用什么數(shù)據(jù)結(jié)構(gòu)算法的效率比較高，為什么

卜面以（a+b）*c為例子進(jìn)行說(shuō)明:

（a+b）'c的逆波式為ab+c\假設(shè)計(jì)算機(jī)把a(bǔ)b+c*按從左到右的限序壓入棧13并且按照遇到星理液就把為頂

兩個(gè)元素里找,執(zhí)行運(yùn)算，得到的結(jié)果再入棧的原則來(lái)進(jìn)行處理，那么ab+c?的執(zhí)行結(jié)果如卜.：

1）a入棧（0位置）

2）b入棧（1位置）

3）泄到運(yùn)靠符將a和b也找，執(zhí)行a+b的操作，得到結(jié)果（1=2+4再將d入棧（。位置）

4）C入棧（1位置）

5）遇到左遜將d和c也找，執(zhí)行d*c的操作，得到結(jié)果e,再將e入棧（0位置）

經(jīng)過(guò)以上運(yùn)算，計(jì)算機(jī)就可以得到（a+b）*c的運(yùn)算結(jié)果e/.

逆界式除了可以實(shí)現(xiàn)上述類型的運(yùn)克，它還可以派生出許多新的算法.一據(jù)站內(nèi)，這就需要靈活運(yùn)用了.逆

汲工式只是一種序列體現(xiàn)形式.

13、C和C++,C++和Java的區(qū)別

C是一個(gè)結(jié)構(gòu)化語(yǔ)言，如譚老爺子所說(shuō):它的重

點(diǎn)在于算法和數(shù)據(jù)結(jié)構(gòu)。C程序的設(shè)計(jì)首要考慮

的是如何通過(guò)一個(gè)過(guò)程，對(duì)輸入（或環(huán)境條件）

進(jìn)行運(yùn)算處理得到輸出（或?qū)崿F(xiàn)過(guò)程（事務(wù)）控

制），而對(duì)于C++,首要考慮的是如何構(gòu)造一個(gè)

對(duì)象模型，讓這個(gè)模型能夠契合與之對(duì)應(yīng)的問(wèn)題

域，這樣就能夠通過(guò)獲取對(duì)象的狀態(tài)信息得到輸

出或?qū)崿F(xiàn)過(guò)程（事務(wù)）控制。

所以C與C++的最大區(qū)別在于它們的用于解決問(wèn)

題的思想方法不一樣。之所以說(shuō)C++比C更先進(jìn)，

是因?yàn)槊嫦驅(qū)?/p>

象設(shè)計(jì)這個(gè)概念已經(jīng)被融入到C++之中”，而就語(yǔ)言本身而言,在C中更多的是算法的概念.那么是不是C就

不重要了,錯(cuò)！算法是程序設(shè)計(jì)的基礎(chǔ),好的設(shè)計(jì)如果強(qiáng)有好的算法,?樣不行.而且，加上好的設(shè)計(jì).也能罵

出非常好的東西.

對(duì)語(yǔ)再本身而言，C是C++的廣集,那么是什么樣的?個(gè)上生？從上文可以看出，C實(shí)現(xiàn)「C++中過(guò)程化控制及

其它相關(guān)功能，而在C++中的C(我稱它為“C+”),相對(duì)于原來(lái)的C還有所加強(qiáng).引入了重教、內(nèi)聯(lián)函數(shù)、異常

處理等等玩仍兒,C++更是拓展/面向?qū)ο笤O(shè)計(jì)的內(nèi)容,如類、繼承、姓威等、模板和包容器類等等.

再提高一點(diǎn)，住C++中，數(shù)據(jù)封裝、類型這些東東己不是什么新鮮小兒需要考慮的是諸如：時(shí)象粒度的選擇、

對(duì)象接口的設(shè)ir和繼承、組合與繼承的使用等等問(wèn)題.

所以相對(duì)jc.C++包含了更豐富的?設(shè)計(jì)”的概念,但c是C++的?個(gè)自洽上生，也具有強(qiáng)大的功能,同樣值得

學(xué)習(xí).

C++Java

指針有JAVA喑占讓編程者無(wú)法找到指針來(lái)

直接訪問(wèn)內(nèi)存無(wú)指針.并且增添「門

M的內(nèi)存管理功能.從而有效地防止

\c/c++i3'中指針操作失誤,如

野指針?biāo)斐傻南到y(tǒng)崩涉

笠重繼承C++支持多重繼承?這是C++的一個(gè)Java八支持多重繼承,但允許一個(gè)類

特征?它允許多攵類一生一個(gè)類.盡繼承多個(gè)接口

管衫值繼承功能很怩.但.使川更雜.(extends+implement).9jr!>\c十十"

商且會(huì)弓I起許多麻煩,編譯程序?qū)崿F(xiàn)我繼承的功能.乂避免「C++中的8

它也很小容幼.垂維承實(shí)現(xiàn)方式帶來(lái)的諸一B小便.

多值繼承的問(wèn)題,二義性：兩個(gè)基類解決多重繼承的問(wèn)題：接11中沒(méi)有實(shí)

A部有同一個(gè)virtual方法,一個(gè)子類現(xiàn).所以也就沒(méi)仃1刎才的問(wèn)題了.

t了兩個(gè)基類，并同時(shí)overrideT

這個(gè)方法.那該聽(tīng)誰(shuí)的？

全局變量允許不允許

結(jié)構(gòu)體struct

白幼內(nèi)存菖理new%\要:顯式delete抻內(nèi)存垃圾回收

操作符照棧支持不支持

眺省閑數(shù)叁數(shù)(inta=1)支持不支持(不過(guò)可以通過(guò)override實(shí)現(xiàn))

goto語(yǔ)句支持《不提倡)不支持(但是保留關(guān)鍵字)

類型轉(zhuǎn)換支持降式轉(zhuǎn)換不支持降式轉(zhuǎn)換

14、什么是預(yù)處理

程序設(shè)計(jì)中的預(yù)處理(Preprocess),程序設(shè)計(jì)領(lǐng)

域，預(yù)處理是在程序源代碼被編譯之前，由預(yù)處

理器(Preprocessor)對(duì)程序源代碼進(jìn)行的處理。

這個(gè)過(guò)程并不對(duì)程序的源代碼進(jìn)行解析，但它把

源代碼分割或處理成為特定的符號(hào)用來(lái)支持宏

調(diào)用。

預(yù)處理器的主要作用就是把通過(guò)預(yù)處理的內(nèi)建

功能對(duì)一個(gè)資源進(jìn)行等價(jià)替換，最常見(jiàn)的預(yù)處

理有:文件包含，條件編譯、布局控制和宏替換

4種。

15、堆和棧的區(qū)別

棧區(qū)（stack）-由編譯器自動(dòng)分配釋放，存

放函數(shù)的參數(shù)值，局部變量的值等。其操作方

式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。

堆區(qū)（heap）—一般由程序員分配釋放,若程序員不釋放，程序結(jié)束時(shí)可能由OS回

收.注:直它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，分配方式倒是類似于鏈表，呵呵.

堆（英語(yǔ)：heap）亦被稱為：優(yōu)先隊(duì)列（英語(yǔ)：priorityqueue）,是計(jì)算.機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)

肉的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹(shù)的數(shù)組對(duì)象。在隊(duì)列中,調(diào)度程序反復(fù)提取隊(duì)列中第一個(gè)作業(yè)

算運(yùn)行，因而實(shí)際情況中某些時(shí)間較短的任務(wù)將等待很長(zhǎng)時(shí)間才能結(jié)束，或者某些不短小，但具有重要性

的作業(yè)，同樣應(yīng)當(dāng)具有優(yōu)先權(quán).唯即為解決此類問(wèn)題設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。

堆棧（英文:stack）,也可直接稱棧。臺(tái)灣作堆

疊，在計(jì)算機(jī)科學(xué)中，是一種特殊的串行形式的

數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串

行或陣列的一端（稱為堆棧頂端指標(biāo)，英文為

top）進(jìn)行加入資料（push）和輸出資料（pop）

的運(yùn)算。另外堆棧也能夠用一維陣列或連結(jié)串行

的形式來(lái)完成。堆棧的另外一個(gè)相對(duì)的操作方式

稱為佇列。

由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而

按照后進(jìn)先出(LIFO,LastInFirstOut)的

原理運(yùn)作。

堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作:推入（push）

和彈出（pop）:

在計(jì)算機(jī)科學(xué)中,內(nèi)聯(lián)函數(shù)（有時(shí)稱作在線函數(shù)或

宏（Macro）,是一種批量批量處理的稱

編譯時(shí)期展開(kāi)函數(shù)）是一種編程語(yǔ)言結(jié)構(gòu),用來(lái)建

謂。議編譯器對(duì)一些特殊函數(shù)進(jìn)行內(nèi)息投竹：（有時(shí)稱作

計(jì)算機(jī)科學(xué)里的宏是一種如邃（Abstraction）,在線擴(kuò)展）；也就是說(shuō)建議編譯器將指定的函數(shù)體

它根據(jù)一系列預(yù)定義的規(guī)則替換一定的文本模插入并取代每一處調(diào)用該函數(shù)的地方（上上義），從

而節(jié)省了每次調(diào)用函數(shù)帶來(lái)的額外時(shí)間開(kāi)支。但在

式。解釋器或編譯器在遇到宏時(shí)會(huì)自動(dòng)進(jìn)行這一

選擇使用內(nèi)聯(lián)函數(shù)時(shí)，必須在程序占用空間和程序

模式替換。對(duì)于編譯語(yǔ)言,宏展開(kāi)在編譯時(shí)發(fā)

也行X"之間進(jìn)行權(quán)衡,因?yàn)檫^(guò)多的比較復(fù)雜的函

生，進(jìn)行宏展開(kāi)的工具常被稱為宏展開(kāi)器。宏這數(shù)進(jìn)行內(nèi)聯(lián)擴(kuò)展將帶來(lái)很大的存儲(chǔ)資源開(kāi)支。另外

沐語(yǔ)也常常被用于許多類似的環(huán)境中，它們是還需要非常注意的是對(duì)遞歸困數(shù)的內(nèi)聯(lián)擴(kuò)展可能

源自宏展開(kāi)的概念，這包括進(jìn)匚的和宏語(yǔ)言。絕帶來(lái)部分編譯器的無(wú)窮編譯。

大多數(shù)情況下，“宏"這個(gè)詞的使用暗示著將小命令

或動(dòng)作轉(zhuǎn)化為一系列指令。

宏的用途在于自動(dòng)化頻繁使用的串行或者是

獲得一種更強(qiáng)大的抽象能力——但這常常是一回

事。

17、簡(jiǎn)述在面向?qū)ο蟪绦蛟O(shè)計(jì)中，引入繼承和封

裝的主要作用繼承:代碼重用封裝:代碼安全

18、簡(jiǎn)述C語(yǔ)言中指針及其作用

19、Java語(yǔ)言的多線程機(jī)制

20、簡(jiǎn)述四種常見(jiàn)的數(shù)據(jù)邏輯結(jié)構(gòu)

①集合集合中任何兩個(gè)數(shù)據(jù)元素之間都沒(méi)有

邏輯關(guān)系，組織形式松散。

②我件幺加線性結(jié)構(gòu)中的結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一個(gè)"鎖鏈

③樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)象自然界中的樹(shù).

④圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)中的結(jié)點(diǎn)按邏輯關(guān)系互

相纏繞，任何兩個(gè)結(jié)點(diǎn)都能夠鄰接

21、簡(jiǎn)述在一棵二叉排序樹(shù)中查找一特定元素x

的算法過(guò)程

二叉排序樹(shù)（BinarySortTree）又稱二叉查找

樹(shù)。它或者是一棵空樹(shù)；

或者是具有下列性質(zhì)的二叉樹(shù)：

（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值

均小于它的根結(jié)點(diǎn)的值；

（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值

均大于它的根結(jié)點(diǎn)的值；

:分治法1通過(guò)?趟排序?qū)⑺Ｅ判虻臄?shù)據(jù)分別成獨(dú)立的網(wǎng)部分,其中-部分的所有數(shù)據(jù)都比另外?部分的所行數(shù)據(jù)都

要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)再可以幽進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成仃

序序列.

（3）左、右子樹(shù)也分別為二叉排序樹(shù)；

在最壞的情況是，兩子數(shù)列擁有大各為1和

n-1,且調(diào)用樹(shù)（calltree）變成為一個(gè)n個(gè)

嵌套（nested）調(diào)用的線性連串（chain）。第i

次調(diào)用作了0(n-i)的工作量，且遞歸關(guān)系式為:

這與插入排序和選擇排序有相同的關(guān)系式，以及

它被解為T(n)=0(n2)o

它的最壞情況是很恐怖的，需要

空間，遠(yuǎn)比數(shù)列本身還多。

23、簡(jiǎn)述在一帶權(quán)有向圖中尋找關(guān)鍵路徑的基本

思想

關(guān)鍵路徑:關(guān)鍵路徑是指網(wǎng)絡(luò)終端元素的元素的

序列，該序列具有最長(zhǎng)的總工期并決定了整個(gè)項(xiàng)

目的最短完成時(shí)間。在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)

具有最大路徑長(zhǎng)度(該路徑上的各個(gè)活動(dòng)所持續(xù)

的時(shí)間之和)的路徑為關(guān)鍵路徑關(guān)鍵活動(dòng):關(guān)鍵

路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。

只有所有關(guān)鍵活動(dòng)提前完成，整個(gè)工程才能提前

完成。

最早可能開(kāi)始時(shí)間Ve[i]:從原點(diǎn)到頂點(diǎn)Vi最長(zhǎng)

路徑的長(zhǎng)度（之前所有事情做完了才可能開(kāi)始）;

最遲允許開(kāi)始時(shí)間保證匯點(diǎn)Vn-1在

Ve[n-1]時(shí)刻完成的前提下（整體工期不拖），事

件Vi最遲允許的開(kāi)始時(shí)間。

VI[i]=min{VI[k]-dur?Vi,Vk?}

關(guān)鍵活動(dòng)：松弛時(shí)間（slack

time）Al[j]-Ae[k]==0的節(jié)點(diǎn)。

24、類作用域和文件作用域的區(qū)別是什么

文件作用域也稱“全局作用域”。?

?定義在所有函數(shù)之外的標(biāo)識(shí)符，具有文件作用

域，作用域?yàn)閺亩x處到整個(gè)源文件結(jié)束。文

件中定義的全局變量和函數(shù)都具有文件作用域。

如果某個(gè)文件中說(shuō)明了具有文件作用域的標(biāo)識(shí)

符，該文件又被另一個(gè)文件包含，則該標(biāo)識(shí)符的

作用域延伸到新的文件中。，。

操作系統(tǒng)1.進(jìn)程和線程的區(qū)別及聯(lián)系，操作系

統(tǒng)的程序棧…

線程和進(jìn)程的區(qū)別：

1、線程是進(jìn)程的一部分，所以線程有的時(shí)候被

稱為是輕權(quán)進(jìn)程或者輕量級(jí)進(jìn)程。

2、一個(gè)沒(méi)有線程的進(jìn)程是能夠被看作單線程

的，如果一個(gè)進(jìn)程內(nèi)擁有多個(gè)進(jìn)程，進(jìn)程的執(zhí)行

過(guò)程不是一條線（線程）的，而是多條線（線程）

共同完成的。

3、系統(tǒng)在運(yùn)行的時(shí)候會(huì)為每個(gè)進(jìn)程分配不同的

內(nèi)存區(qū)域，但是不會(huì)為線程分配內(nèi)存（線程所使

用的資源是它所屬的進(jìn)程的資源），線程組只能

共享資源。那就是說(shuō)，出了CPU之外（線程在運(yùn)

行的時(shí)候要占用CPU資源），計(jì)算機(jī)內(nèi)部的軟硬

件資源的分配與線程無(wú)關(guān)，線程只能共享它所屬

進(jìn)程的資源。

4、與進(jìn)程的控制表PCB相似，線程也有自己的

控制表TCB,但是TCB中所保存的線程狀態(tài)比PCB

表中少多了（上下文保存一下就行）。

5、進(jìn)程是系統(tǒng)所有資源分配時(shí)候的一個(gè)基本單

位，擁有一個(gè)完整的虛擬空間地址，并不依賴線

程而獨(dú)立存在。

進(jìn)程與程序的區(qū)別：

程序是一組指令的集合，它是靜態(tài)的實(shí)體，沒(méi)有

執(zhí)行的含義。而進(jìn)程是一個(gè)動(dòng)態(tài)的實(shí)體，有自己

的生命周期。一般說(shuō)來(lái)，一個(gè)進(jìn)程肯定與一個(gè)程

序相對(duì)應(yīng)，并且只有一個(gè)，但是一個(gè)程序能夠有

多個(gè)進(jìn)程，或者一個(gè)進(jìn)程都沒(méi)有也能夠只有一個(gè)

進(jìn)程。除此之外，進(jìn)程還有并發(fā)性和交往性。簡(jiǎn)

單地說(shuō)，進(jìn)程是程序的一部分，程序運(yùn)行的時(shí)候

會(huì)產(chǎn)生進(jìn)程。總結(jié):線程是進(jìn)程的一部分，進(jìn)程

是程序的一部分。

前一句說(shuō)的不太準(zhǔn)確，線程也有自己的資源，比

如棧，私有數(shù)據(jù)等等。說(shuō)他使用而不擁有資源指

的是使用的是進(jìn)程的打開(kāi)文件句柄，進(jìn)程的全局

數(shù)據(jù)，進(jìn)程的地址空間等等，這些都屬于進(jìn)程，

而不屬于線程，進(jìn)程內(nèi)個(gè)線程共享。

進(jìn)程切換比線程切換開(kāi)銷大是因?yàn)檫M(jìn)程切換時(shí)

要切頁(yè)表，而且往往伴隨著頁(yè)調(diào)度，因?yàn)檫M(jìn)程的

數(shù)據(jù)段代碼段要換出去，以便把將要執(zhí)行的進(jìn)程

的內(nèi)容換進(jìn)來(lái)。本來(lái)進(jìn)程的內(nèi)容就是線程的超

集。而且線程只需要保存線程的上下文（相關(guān)寄

存器狀態(tài)和棧的信息）就好了，動(dòng)作很小。

2.OS里面進(jìn)程的“三態(tài)”“五態(tài)”“七態(tài)”是

什么

3.什么是操作系統(tǒng)

操作系統(tǒng)（英文:OperatingSystem,

縮寫(xiě):OS）是管理計(jì)竟機(jī)硬件與軟件資

源的計(jì)算機(jī)程序,同時(shí)也是計(jì)算機(jī)系統(tǒng)

的內(nèi)核與基石。操作系統(tǒng)需要處理如管

理與配置電理、決定系統(tǒng)資源供需的優(yōu)

先次序、控制輸入與輸出設(shè)備、操作網(wǎng)

絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系

統(tǒng)也提供一個(gè)讓用戶與系統(tǒng)交互的操作

界面。

4.死鎖的條件，檢測(cè)死鎖的可能方法及其基本

思想

Adeadlockisasituationinwhichtwoor

morecompetingactionsareeachwaitingfor

theothertofinish,andthusneitherever

does.

1.（互斥）:Atleasttworesourcesmustbe

non-shareable.[1]Onlyoneprocesscanuse

theresourceatanygiveninstantoftime.

2.HoldandWaitorResourceHolding:A

processiscurrentlyholdingatleastone

resourceandrequesting

additionalresourceswhicharebeingheldby

otherprocesses.

Hardware硬爆

3.No（禁止搶占）:Theoperatingsystemmust

notde-allocateresourcesoncetheyhave

been

allocated;theymustbereleasedbythe

holdingprocessvoluntarily.

4.Aprocessmustbewaitingforaresource

whichisbeingheldbyanotherprocess,

whichinturniswaitingforthefirst

processtoreleasetheresource.Ingeneral,

thereisaofwaiting

processes,P={Pl,P2,...,PN},suchthat

PliswaitingforaresourceheldbyP2,P2

iswaitingforaresourceheldbyP3andso

onuntilPNiswaitingforaresourceheld

byPl.

Thesefourconditionsareknownasthe

Coffmanconditionsfromtheirfirst

descriptionina1971article

by[7]Unfulfillmentofanyofthese

conditionsisenoughtoprecludeadeadlock

fromoccurring.

Ensurethatthesystemwillneverentera

deadlockstate.

Prevention:Ensureoneofthefour

conditionsfails.

Avoidance:TheOSneedsmoreinformationso

thatitcandetermineifthecurrentrequest

canbesatisfiedor

delayed.

死鎖檢測(cè)：

1.Resource-AllocationGraph

2.DetectionAlgorithm

5.用戶態(tài)和內(nèi)核態(tài)

當(dāng)程序運(yùn)行在3級(jí)特權(quán)級(jí)上時(shí)，就能夠稱之為運(yùn)

行在用戶態(tài)，因?yàn)檫@是最低特權(quán)級(jí)，是普通的用

戶進(jìn)程運(yùn)行的特權(quán)級(jí)，大部分用戶直接面對(duì)的程

序都是運(yùn)行在用戶態(tài)；反之，當(dāng)程序運(yùn)行在級(jí)特

權(quán)級(jí)上時(shí)，就能夠稱之為運(yùn)行在內(nèi)核態(tài)。用戶

態(tài)切換到內(nèi)核態(tài)的3種方式

a.系統(tǒng)調(diào)用

這是用戶態(tài)進(jìn)程主動(dòng)要求切換到內(nèi)核態(tài)的一種

方式，用戶態(tài)進(jìn)程通過(guò)系統(tǒng)調(diào)用申請(qǐng)使用操作系

統(tǒng)提供的服務(wù)程序完成工作，比如前例中forkO

實(shí)際上就是執(zhí)行了一個(gè)創(chuàng)建新進(jìn)程的系統(tǒng)調(diào)用。

而系統(tǒng)調(diào)用的機(jī)制其核心還是使用了操作系統(tǒng)

為用戶特別開(kāi)放的一個(gè)中斷來(lái)實(shí)現(xiàn)，例如Linux

的int80h中斷。

b.異常

當(dāng)CPU在執(zhí)行運(yùn)行在用戶態(tài)下的程序時(shí)，發(fā)生了

某些事先不可知的異常，這時(shí)會(huì)觸發(fā)由當(dāng)前運(yùn)行

進(jìn)程切換到處理此異常的內(nèi)核相關(guān)程序中，也就

轉(zhuǎn)到了內(nèi)核態(tài)，比如缺頁(yè)異常。

c.外圍設(shè)備的中斷

當(dāng)外圍設(shè)備完成用戶請(qǐng)求的操作后，會(huì)向CPU發(fā)

出相應(yīng)的中斷信號(hào)，這時(shí)CPU會(huì)暫停執(zhí)行下一條

即將要執(zhí)行的指令轉(zhuǎn)而去執(zhí)行與中斷信號(hào)對(duì)應(yīng)

的處理程序，如果先前執(zhí)行的指令是用戶態(tài)下的

程序，那么這個(gè)轉(zhuǎn)換的過(guò)程自然也就發(fā)生了由用

戶態(tài)到內(nèi)核態(tài)的切換。比如硬盤(pán)讀寫(xiě)操作完成，

系統(tǒng)會(huì)切換到硬盤(pán)讀寫(xiě)的中斷處理程序中執(zhí)行

后續(xù)操作等。

這3種方式是系統(tǒng)在運(yùn)行時(shí)由用戶態(tài)轉(zhuǎn)到內(nèi)核

態(tài)的最主要方式，其中系統(tǒng)調(diào)用能夠認(rèn)為是用戶

進(jìn)程主動(dòng)發(fā)起的，異常和外圍設(shè)備中斷則是被動(dòng)

的。

6.面包店算法

該算法的基本思想源于顧客在面包店中購(gòu)買面

包時(shí)的排隊(duì)原理.顧客在進(jìn)入面包店前，首先

抓一個(gè)號(hào)，然后按照號(hào)碼由小到大的次序依次

進(jìn)入面包店購(gòu)買面包.這里，面包店發(fā)放的號(hào)

碼是由小到大的，但是兩個(gè)或兩個(gè)以上的顧客

卻有可能得到相同的號(hào)碼（使所抓號(hào)碼不同需要

互斥），如果多個(gè)顧客抓到相同的號(hào)碼，則規(guī)定

按照顧客名字的字典次序進(jìn)行排序，這里假定

顧客是沒(méi)有重名的.在計(jì)算機(jī)系統(tǒng)中，顧客就

相當(dāng)于進(jìn)程，每個(gè)進(jìn)程有一個(gè)唯一的標(biāo)識(shí)，我

們用P的下面加一個(gè)下標(biāo)來(lái)表示.例如：對(duì)于

Pi和Pj,如果有i<j,則先為Pi服務(wù)，即Pi

先進(jìn)入臨界區(qū)

7.系統(tǒng)調(diào)用和庫(kù)函數(shù)的區(qū)別

⑴調(diào)用形式不同。過(guò)程（函數(shù)）使用一般調(diào)用

指令，其轉(zhuǎn)向地址是固定不變的，包含在跳轉(zhuǎn)語(yǔ)

句中；但系統(tǒng)調(diào)用中不包含處理程序入口，而僅

僅提供功能號(hào)，按功能號(hào)調(diào)用。

⑵被調(diào)用代碼的位置不同。過(guò)程（函數(shù)）調(diào)用

是一種靜態(tài)調(diào)用，調(diào)用者和被調(diào)用代碼在同一程

序內(nèi)，經(jīng)過(guò)連接編輯后作為目標(biāo)代碼的一部份。

當(dāng)過(guò)程（函數(shù)）升級(jí)或修改時(shí)，必須重新編譯連

結(jié)。而系統(tǒng)調(diào)用是一種動(dòng)態(tài)調(diào)用，系統(tǒng)調(diào)用的處

理代碼在調(diào)用程序之外（在操作系統(tǒng)中），這樣

一來(lái)，系統(tǒng)調(diào)用處理代碼升級(jí)或修改時(shí)，與調(diào)用

程序無(wú)關(guān)。而且，調(diào)用程序的長(zhǎng)度也大大縮短，

減少了調(diào)用程序占用的存儲(chǔ)空間。

⑶提供方式不同。過(guò)程（函數(shù)）往往由編譯系

統(tǒng)提供，不同編譯系統(tǒng)提供的過(guò)程（函數(shù)）能夠

不同；系統(tǒng)調(diào)用由操作系統(tǒng)提供，

一旦操作系統(tǒng)設(shè)計(jì)好，系統(tǒng)調(diào)用的功能、種類與

數(shù)量便固定不變了。

（4）調(diào)用的實(shí)現(xiàn)不同o程序使用一般機(jī)器指令（跳

轉(zhuǎn)指令）來(lái)調(diào)用過(guò)程（函數(shù)），是在用戶態(tài)運(yùn)行

的；程序執(zhí)行系統(tǒng)調(diào)用，是通過(guò)中斷機(jī)構(gòu)來(lái)實(shí)現(xiàn),

需要從用戶態(tài)轉(zhuǎn)變到核心態(tài)，在管理狀態(tài)執(zhí)行，

因此，安全性好。

8.經(jīng)典進(jìn)程同步問(wèn)題是什么，同步思想？

生產(chǎn)者-消費(fèi)者問(wèn)題是著名的進(jìn)程同步問(wèn)題，它

描述一組生產(chǎn)者進(jìn)程向一組消費(fèi)者進(jìn)程提供消

息。它們共享一個(gè)有界緩沖池，生產(chǎn)者向其中投

放消息，消費(fèi)者從中取得消息。生產(chǎn)者-消費(fèi)者

問(wèn)題是許多相互合作進(jìn)程的一種抽象。假定緩沖

池中有n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一個(gè)消息、。

由于緩沖池是臨界資源，它只允許一個(gè)生產(chǎn)者投

入消息，或者一個(gè)消費(fèi)者從中取出消息。生產(chǎn)者

之間、生產(chǎn)者與消費(fèi)者之間、消費(fèi)者之間都必須

互斥地使用緩沖池。所以必須設(shè)置互斥信號(hào)量

mutex,它代表緩沖池資源，它的數(shù)值為1。讀

者-寫(xiě)者問(wèn)題

問(wèn)題描述:一個(gè)數(shù)據(jù)集（如文件）被幾個(gè)并行進(jìn)

程所共享，有些進(jìn)程只要求讀數(shù)據(jù)集內(nèi)容，稱為

讀者，而另一些進(jìn)程則要求修改數(shù)據(jù)集內(nèi)容，稱

為寫(xiě)者，幾個(gè)讀者能夠同時(shí)讀數(shù)據(jù)集，而不需要

互斥，但一個(gè)寫(xiě)者不能和其它進(jìn)程（不論是寫(xiě)者

或讀者）同時(shí)訪問(wèn)這些數(shù)據(jù)集，它們之間必須互

斥。

哲學(xué)家進(jìn)餐問(wèn)題

該問(wèn)題描述如下:有五個(gè)哲學(xué)家，他們的生活方

式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們公用一張

圓桌，周圍放有五把椅子，每人坐一把。在圓桌

上有五個(gè)碗和五根筷子，當(dāng)一個(gè)哲學(xué)家思考時(shí)，

他不與其它人交談，饑餓時(shí)便試圖取用其左、右

最靠近他的筷子，但他可能一根都拿不到。只有

在他拿到兩根筷子時(shí)，方能進(jìn)餐，進(jìn)餐完后，放

下筷子又繼續(xù)思考。

9.文件管理及組織，F(xiàn)AT

FAT=FileAllocationTable

10.設(shè)備驅(qū)動(dòng)程序是否屬于OS,他的作用是什

么

不是，驅(qū)動(dòng)程序是另外安裝的軟件，是操作系統(tǒng)

控制并且和硬件之間通訊的橋梁（程序）

11.程序和任務(wù)的區(qū)別

任務(wù)是最抽象的，是一個(gè)一般性的術(shù)語(yǔ)，指由軟

件完成的一個(gè)活動(dòng)。一個(gè)任務(wù)既能夠是一個(gè)進(jìn)程,

也能夠是一個(gè)線程。簡(jiǎn)而言之,它指的是一系列

共同達(dá)到某一目的的操作。例如，讀取數(shù)據(jù)并將

數(shù)據(jù)放入內(nèi)存中。這個(gè)任務(wù)能夠作為一個(gè)進(jìn)程來(lái)

實(shí)現(xiàn),也能夠作為一個(gè)線程（或作為一個(gè)中斷任

務(wù)）來(lái)實(shí)現(xiàn)。進(jìn)程常常被定義為程序的執(zhí)行。

能夠把一個(gè)進(jìn)程看成是一個(gè)獨(dú)立的程序,在內(nèi)存

中有其完備的數(shù)據(jù)空間和代碼空間。一個(gè)進(jìn)程所

擁有的數(shù)據(jù)和變量只屬于它自己。線程則是某

一進(jìn)程中一路單獨(dú)運(yùn)行的程序。也就是說(shuō)，線程

存在于進(jìn)程之中。一個(gè)進(jìn)程由一個(gè)或多個(gè)線程構(gòu)

成，各線程共享相同的代碼和全局?jǐn)?shù)據(jù)，但各有

其自己的堆棧。由于堆棧是每個(gè)線程一個(gè)，所以

局部變量對(duì)每一線程來(lái)說(shuō)是私有的。由于所有線

程共享同樣的代碼和全局?jǐn)?shù)據(jù)，它們比進(jìn)程更緊

密，比單獨(dú)的進(jìn)程間更趨向于相互作用，線程間

的相互作用更容易些，因?yàn)樗鼈儽旧砭陀心承┕?/p>

通信用的共享內(nèi)存:進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局

數(shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)

進(jìn)程:資源分配、調(diào)度運(yùn)行的基本單位。

線程:進(jìn)程中執(zhí)行運(yùn)算的最小單位，執(zhí)行處理機(jī)

調(diào)度的基本單位。

12.數(shù)據(jù)庫(kù)安全性和操作系統(tǒng)安全性的關(guān)系

安全性問(wèn)題不是數(shù)據(jù)庫(kù)系統(tǒng)所獨(dú)有的,，而且為

許多最終用戶直接共享,，包括操作系統(tǒng),網(wǎng)絡(luò)系

統(tǒng)的安全性是緊密聯(lián)系,相互支持的.

13.中斷處理的過(guò)程

請(qǐng)求中斷一響應(yīng)中斷一關(guān)閉中斷一保留斷點(diǎn)一

中斷源識(shí)別一保護(hù)現(xiàn)場(chǎng)一中斷服務(wù)子程序一恢

復(fù)現(xiàn)場(chǎng)一中斷返回在實(shí)際運(yùn)行中，一旦設(shè)備通

過(guò)某引腳N向8259A發(fā)出中斷指令，后者便向

8086A的INTR引腳發(fā)送中斷信號(hào)。8086A通過(guò)

INTA引腳通知8259A中斷有效（這個(gè)過(guò)程實(shí)際

上還包括對(duì)此8259A的選址），后者即通過(guò)地址

總線將對(duì)應(yīng)引腳N的中斷類型碼（已預(yù)先存好，

見(jiàn)上節(jié)）發(fā)送給CPU。CPU得到中斷類型碼后，

先進(jìn)行現(xiàn)場(chǎng)保護(hù)，主要包括：

1.狀態(tài)寄存器FLAGS壓棧（同時(shí)堆棧寄存器

SP-2）；

2.關(guān)閉中斷（將FLAGS寄存器的IF位置零）；

3.將當(dāng)前代碼段寄存器CS和程序計(jì)數(shù)器IP壓

棧（同時(shí)堆棧寄存器SP-4）?，F(xiàn)場(chǎng)保護(hù)完成后,

CPU開(kāi)始按照前述的兩步驟翻譯中斷程序入口地

址。在得到中斷處理程序地址之后但調(diào)用中斷處

理程序之前，CPU會(huì)再檢查一下NMI引腳是否有

信號(hào)，以防在剛才的處理過(guò)程中忽略了可能的

NMI中斷。NMI的優(yōu)先級(jí)始終高于INTRo

中斷處理程序雖然是由程序員編寫(xiě)，但須循一定

規(guī)范。作為例程，中斷處理程序應(yīng)該先將各寄存

器信息（除了IP和CS,此二寄存器現(xiàn)已指向當(dāng)

前中斷程序）壓入堆棧予以保存，這樣才能在中

斷處理程序內(nèi)部使用這些寄存器。在程序結(jié)束

時(shí)，應(yīng)該按與壓棧保護(hù)時(shí)相反的順序彈出各寄存

器的值。中斷程序的最后一句始終是IRET指令,

這條指令將棧頂6個(gè)字節(jié)分別彈出并存入IP、

CS和FLAGS寄存器，完成了現(xiàn)場(chǎng)的還原。

當(dāng)然，如果是操作系統(tǒng)的中斷處理程序，則未必

——通常不會(huì)一一還原中斷前的狀態(tài)。這樣的中

斷處理程序通常會(huì)在調(diào)用完寄存器保存例程后，

調(diào)用進(jìn)程調(diào)度程序（多由高級(jí)語(yǔ)言編寫(xiě)），并決

定下一個(gè)運(yùn)行的進(jìn)程。隨后將此進(jìn)程的寄存器信

息（上次中斷時(shí)保存下來(lái)的）存入寄存器并返回o

在中斷程序結(jié)束之后，主程序也發(fā)生了改變。

14.計(jì)算機(jī)系統(tǒng)怎樣實(shí)現(xiàn)存儲(chǔ)保護(hù)

1.防止地址越界（對(duì)進(jìn)程所產(chǎn)生的地址必須加

以檢查，發(fā)生越界時(shí)產(chǎn)生中斷，由操作系統(tǒng)進(jìn)行

相應(yīng)處理）

2.防止操作越權(quán)（對(duì)屬于自己區(qū)域的信息，可

讀可寫(xiě):對(duì)公共區(qū)域中允許共享的信息或獲得授

權(quán)可使用的信息，可讀而不可修改；對(duì)未授權(quán)使

用的信息，不可讀，不可寫(xiě)）

15.調(diào)度的基本準(zhǔn)則（SchedulingCriteria）

Therearemanycriteriaforcomparing

differentschedulingalgorithms.Hereare

fivecommonones:CPUutilization（CPU不（J用

率）

Throughput（吞吐量）

Turnaroundtime（周轉(zhuǎn)時(shí)間）

Waitingtime（等待時(shí)間）

Responsetime（響應(yīng)時(shí)間）

16.多線程是否真正能提高效率

17.磁盤(pán)調(diào)度算法有哪幾種

FCFS

SSTF（ShortestSeekTimeFirst）

Scan/Look

C-Sacn/C-Look

18.RAID工作原理

RAID(RedundantArrayofIndependentDisks)

通過(guò)條帶化存儲(chǔ)和奇偶校驗(yàn)兩個(gè)措施來(lái)實(shí)現(xiàn)其

冗余和容錯(cuò)的目標(biāo)。條帶化存儲(chǔ)意味著能夠一次

寫(xiě)入一個(gè)數(shù)據(jù)塊的方式將文件寫(xiě)入多個(gè)磁盤(pán)。條

帶化存儲(chǔ)技術(shù)將數(shù)據(jù)分開(kāi)寫(xiě)入多個(gè)驅(qū)動(dòng)器，從而

提高數(shù)據(jù)傳輸速率并縮短磁盤(pán)處理總時(shí)間。這種

系統(tǒng)非常適用于交易處理、但可靠性卻很差，因

為系統(tǒng)的可靠性等于最差的單個(gè)驅(qū)動(dòng)器的可靠

性。

奇偶校驗(yàn)通過(guò)在傳輸后對(duì)所有數(shù)據(jù)進(jìn)行冗余校

驗(yàn)?zāi)軌虼_保數(shù)據(jù)的有效性。利用奇偶校驗(yàn)，當(dāng)

RAID系統(tǒng)的一個(gè)磁盤(pán)發(fā)生故障時(shí)，其它磁盤(pán)能

夠重建該故障磁盤(pán)。在這兩種情況中，這些功能

對(duì)于操作系統(tǒng)都是透明的。由磁盤(pán)陣列控制器

(DAC)進(jìn)行條帶化存儲(chǔ)和奇偶校驗(yàn)控制。

19.Windows中段最長(zhǎng)多少字節(jié)

20.同步、互斥

MethodShortDescriptionProvidedby(operatinqsystemsorotherenvironments)

Arecordstoredondiskthatcanbe

FileMostoperatingsystems

accessedbynamebyanyprocess

Asystemmessagesentfromone

Mostoperatingsystems;somesystems,suchasWindows,

processtoanother,notusually

SiqnalimplementsignalsinonlytheCrun-timelibraryandprovideno

usedtostoreinformationbut

supportfortheiruseasanIPCmethodls^^^^l

insteadgivecommands.

22.簡(jiǎn)述請(qǐng)求段頁(yè)式虛擬內(nèi)存管理基本思想

Bring