銀行科技信息部招聘筆試題

1、一、選擇題 1、計(jì)算機(jī)系統(tǒng)中采用補(bǔ)碼運(yùn)算的目的是為了（B）。  A、與手工運(yùn)算方法保持一致      B、提高運(yùn)算速度    C、簡(jiǎn)化計(jì)算機(jī)的設(shè)計(jì)            D、提高運(yùn)算的精度   2、長(zhǎng)度相同但格式不同的兩種浮點(diǎn)數(shù)，假設(shè)前者階碼長(zhǎng)、尾數(shù)短，后者階碼短、尾數(shù)長(zhǎng)，其他規(guī)定均相同，則它們可表示的數(shù)的范圍和精度為

2、（2）。  A、兩者可表示的數(shù)的范圍和精度相同      B、前者可表示的數(shù)的范圍大但精度低 C、后者可表示的數(shù)的范圍大但精度高      D、前者可表示的數(shù)的范圍大但精度高   3、數(shù)值x*的近似值x0.1215×10-2，若滿足|x-x*|（3），則稱x有4位有效數(shù)字。 A、0.5×10-3      B、0.5×

3、10-4   C、0.5×10-5     D、0.5×10-6   4、 一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉子結(jié)點(diǎn)個(gè)數(shù)為（4）。 A、383      B、384   C、385     D、386   5、對(duì)于一個(gè)線性表既要求能夠進(jìn)行較快的插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反應(yīng)數(shù)據(jù)之間

4、的邏輯關(guān)系，則應(yīng)該用（5）。  A、順序方式存儲(chǔ)      B、鏈接方式存儲(chǔ)  C、散列方式存儲(chǔ)  D、以上方式均可   6、地址碼長(zhǎng)度為二進(jìn)制24位時(shí)，其尋址范圍是（C）。  A、512kB     B、1MB  C、16MB    D、24MB   解析： 2的10次方是10

5、24b,也就是1KB,16M=16*1024*1024也就是2的24次方,所以24位時(shí)就是16MB. 7、有m個(gè)進(jìn)程共享同一臨界資源，若使用信號(hào)量機(jī)制實(shí)現(xiàn)對(duì)一臨界資源的互斥訪問(wèn)，則信號(hào)量的變化范圍是（A）。 A.1至(m-1)   B.1至m-1   C.1至m  D.1至m 程序的執(zhí)行結(jié)果是（19）。  8、選擇下面程序的運(yùn)行結(jié)果是（20）。  #include<iostream.h> struct stu

6、60;int num;  char name10; int age;   void fun(stu *p)  cout<<(*p).name<<end1; main()  stu students3=9801,”Zhang”,20,   9802,”Long”,21,   9803,”Xue”,19;   fun(

7、students+2);   A、 Zhang    B、Xue  C、Long   D、18   9、隨著塊的增大，Cache的不命中率（）。 A、下降   B、上升  C、不變   D、不定   10、 按網(wǎng)絡(luò)采用的控制方式，可把計(jì)算機(jī)網(wǎng)絡(luò)分為（）。  A、集中式與廣播式   

8、; B、主控制式與從控制式   C、集中式與分布式   D、都不是   11、設(shè)rear是指向非空帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，則刪除鏈表第一個(gè)結(jié)點(diǎn)的操作可表示為（）。  A、p=rear;rear=rearnext;free(p);       B、rear=rearnext;free(p); C、rear=rearnextnext;free(p);    

9、;   D、p=rearnextnext; rearnext=pnext free(p);   12、數(shù)組A56的每個(gè)元素占4個(gè)單元，下標(biāo)從0計(jì)起，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A45的地址為（）。  A、1116   B、11029  C、1096   D、1088   13、設(shè)二叉排序樹(shù)中關(guān)鍵字由1到1000內(nèi)的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)

10、點(diǎn)，下述關(guān)鍵字序列（）不可能是在二叉排序樹(shù)上查找到的序列？  A、2，252，401，398，330，344，397，363    B、924，220，911，244，898，258，362，363  C、925，202，911，240，912，245，363    D、2，399，387，219，266，382，381，278，363   14、進(jìn)程控制塊中的現(xiàn)場(chǎng)信息是在（26）保存的。  A、創(chuàng)建進(jìn)程時(shí) 

11、0; B、處理器執(zhí)行指令時(shí)  C、中斷源申請(qǐng)中斷時(shí)   D、中斷處理程序處理中斷前   15、下面關(guān)于面向?qū)ο蠓椒ㄖ邢⒌臄⑹?，不?zhǔn)確的是（）。  A、鍵盤、鼠標(biāo)、通信端口、網(wǎng)絡(luò)等設(shè)備一有變化，就會(huì)產(chǎn)生消息    B、操作系統(tǒng)不斷向應(yīng)用程序發(fā)送消息，但應(yīng)用程序不能向操作系統(tǒng)發(fā)送消息   C、應(yīng)用程序之間可以相互發(fā)送消息    D、發(fā)送與接收消息的通信機(jī)制與傳統(tǒng)的子程序調(diào)用機(jī)制不

12、同   16、消息傳遞是對(duì)象間通信的手段，一個(gè)對(duì)象通過(guò)向另一個(gè)對(duì)象發(fā)送消息來(lái)請(qǐng)求其服務(wù)。一個(gè)消息通常包括（）。  A、發(fā)送消息的對(duì)象的標(biāo)識(shí)、調(diào)用的發(fā)送方的操作名和必要的參數(shù)  B、發(fā)送消息的類名和接收消息的類名  C、接收消息的對(duì)象的標(biāo)識(shí)、調(diào)用的接收方的操作名和必要的參數(shù)  D、接收消息的類名   17、軟件項(xiàng)目管理一般包含幾個(gè)方面的內(nèi)容：任務(wù)劃分、計(jì)劃安排、經(jīng)費(fèi)管理、審計(jì)控制、（）和項(xiàng)目保證等 A、市場(chǎng)管理  B、用戶管理&

13、#160;                                                 &

14、#160; C、風(fēng)險(xiǎn)管理  D、設(shè)備管理   18、在使用UML建模時(shí)，若需要描述跨越多個(gè)用例的單個(gè)對(duì)象的行為，使用（）是最為合適的。  A、協(xié)作圖（Collaboration Diagram）  B、序列圖（Sequence Diagram）                   

15、0;  C、活動(dòng)圖（Activity Diagram）  D、狀態(tài)圖(Statechart Diagram)   19、某公司使用包過(guò)濾防火墻控制進(jìn)出公司局域網(wǎng)的數(shù)據(jù)，在不考慮使用代理服務(wù)器的情況下，下面描述錯(cuò)誤的是“該防火墻能夠（）”。  A、使公司員工只能訪問(wèn)Internet上與其有業(yè)務(wù)聯(lián)系的公司的IP地址  B、僅允許HTTP協(xié)議通過(guò)  C、使員工不能直接訪問(wèn)FTP服務(wù)端口號(hào)為21的FTP服務(wù)  D、僅允許公司中具有某些

16、特定IP地址的計(jì)算機(jī)可以訪問(wèn)外部網(wǎng)絡(luò)20、下列敘述中，與提高軟件可移植性相關(guān)的是（）。   A、選擇時(shí)間效率高的算法    B、盡可能減少注釋 C、選擇空間效率高的算法  D、盡量用高級(jí)語(yǔ)言編寫系統(tǒng)中對(duì)效率要求不高的部分   21、采用瀑布模型進(jìn)行系統(tǒng)開(kāi)發(fā)的過(guò)程中，每個(gè)階段都會(huì)產(chǎn)生不同的文檔。以下關(guān)于產(chǎn)生這些文檔的描述中，正確的是（）。  A、外部設(shè)計(jì)評(píng)審報(bào)告在概要設(shè)計(jì)階段產(chǎn)生  B、集成測(cè)試計(jì)劃在程序設(shè)計(jì)階段產(chǎn)生 

17、 C、系統(tǒng)計(jì)劃和需求說(shuō)明在詳細(xì)設(shè)計(jì)階段產(chǎn)生  D、在進(jìn)行編碼的同時(shí)，獨(dú)立的設(shè)計(jì)單元測(cè)試計(jì)劃   22、 一個(gè)具有n（n0）個(gè)頂點(diǎn)的連同無(wú)向圖至少有（）條邊。  A、n1    B、n     C、n/2      D、n1   23、一個(gè)局域網(wǎng)中某臺(tái)主機(jī)的IP地址為2，使用22位作為網(wǎng)絡(luò)地址，那么該局域網(wǎng)的子網(wǎng)掩碼

18、為（），  A、       B、C、       D、  24、（接上題）最多可以連接的主機(jī)數(shù)為（）。  A、254    B、512    C、1022    D、1024&#

19、160;  25、 以下選項(xiàng)中，可以用于Internet信息服務(wù)器遠(yuǎn)程管理的是（）。  A、 Telnet    B、RAS    C、FTP    D、SMTP   26、兩個(gè)公司希望通過(guò)Internet進(jìn)行安全通信，保證從信息源到目的地之間的數(shù)據(jù)傳輸以秘文形式出現(xiàn)，而且公司不希望由于在傳輸節(jié)點(diǎn)使用特殊的安全單元而增加開(kāi)支，最合適的加密方式是（），  A、鏈路加密 B、節(jié)點(diǎn)加

20、密 C、端端加密 D、混合加密  27、 （接上題）使用的會(huì)話密鑰算法應(yīng)該是（）。 A、RSA    B、RC-5    C、MD5    D、ECC  28、關(guān)于軟件測(cè)試對(duì)軟件質(zhì)量的意義，有以下觀點(diǎn)：度量與評(píng)估軟件的質(zhì)量；保證軟件質(zhì)量；改進(jìn)軟件開(kāi)發(fā)過(guò)程；發(fā)現(xiàn)軟件錯(cuò)誤。其中正確的是（40）。  A、 B、C、 D、    二、簡(jiǎn)

21、單題 2.1. 死鎖產(chǎn)生的必要條件，如何檢測(cè)和解除死鎖 ? 2.1.1. 要點(diǎn)提示 （1） 掌握死鎖的概念和產(chǎn)生死鎖的根本原因。 （2） 理解產(chǎn)生死鎖的必要條件-以下四個(gè)條件同時(shí)具備：互斥條件、不可搶占條件、占有且申請(qǐng)條件、循環(huán)等待條件。 （3） 記住解決死鎖的一般方法，掌握死鎖的預(yù)防和死鎖的避免二者的基本思想。 （4） 掌握死鎖的預(yù)防策略中資源有序分配策略。 （5） 理解進(jìn)程安全序列的概念，理解死鎖與安全序列的關(guān)系。（6） 了解銀行家

22、算法。 （7） 了解資源分配圖。 （8） 了解死鎖的檢測(cè)及恢復(fù)的思想。   2.2. 內(nèi)容簡(jiǎn)介   在計(jì)算機(jī)系統(tǒng)中有很多一次只能由一個(gè)進(jìn)程使用的資源，如打印機(jī)，磁帶機(jī)，一個(gè)文件的I節(jié)點(diǎn)等。在多道程序設(shè)計(jì)環(huán)境中，若干進(jìn)程往往要共享這類資源，而且一個(gè)進(jìn)程所需要的資源不止一個(gè)。這樣，就會(huì)出現(xiàn)若干進(jìn)程競(jìng)爭(zhēng)有限資源，又推進(jìn)順序不當(dāng)，從而構(gòu)成無(wú)限期循環(huán)等待的局面。這種狀態(tài)就是死鎖。系統(tǒng)發(fā)生死鎖現(xiàn)象不僅浪費(fèi)大量的系統(tǒng)資源，甚至導(dǎo)致整個(gè)系統(tǒng)崩潰，帶來(lái)災(zāi)難性后果。所以，對(duì)于死鎖問(wèn)題在理論上和技術(shù)上都必須

23、給予高度重視。 2.3. 死鎖的概念     死鎖是進(jìn)程死鎖的簡(jiǎn)稱，是由Dijkstra于1965年研究銀行家算法時(shí)首先提出來(lái)的。它是計(jì)算機(jī)操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最難處理的問(wèn)題之一。實(shí)際上，死鎖問(wèn)題不僅在計(jì)算機(jī)系統(tǒng)中存在，在我們?nèi)粘Ｉ钪兴矎V泛存在。 2.4. 什么是死鎖   我們先看看這樣一個(gè)生活中的例子：在一條河上有一座橋，橋面較窄，只能容納一輛汽車通過(guò)，無(wú)法讓兩輛汽車并行。如果有兩輛汽車A和B分別由橋的兩端駛上該橋，則對(duì)于A車來(lái)說(shuō)，它走過(guò)橋面左面的一段路（即占有了

24、橋的一部分資源），要想過(guò)橋還須等待B車讓出右邊的橋面，此時(shí)A車不能前進(jìn)；對(duì)于B車來(lái)說(shuō)，它走過(guò)橋面右邊的一段路（即占有了橋的一部分資源），要想過(guò)橋還須等待A車讓出左邊的橋面，此時(shí)B車也不能前進(jìn)。兩邊的車都不倒車，結(jié)果造成互相等待對(duì)方讓出橋面，但是誰(shuí)也不讓路，就會(huì)無(wú)休止地等下去。這種現(xiàn)象就是死鎖。如果把汽車比做進(jìn)程，橋面作為資源，那麼上述問(wèn)題就描述為：進(jìn)程A占有資源R1，等待進(jìn)程B占有的資源Rr；進(jìn)程B占有資源Rr，等待進(jìn)程A占有的資源R1。而且資源R1和Rr只允許一個(gè)進(jìn)程占用，即：不允許兩個(gè)進(jìn)程同時(shí)占用。結(jié)果，兩個(gè)進(jìn)程都不能繼續(xù)執(zhí)行，若不采取其它措施，這種循環(huán)等待狀況會(huì)無(wú)限期持續(xù)下去，就發(fā)生了進(jìn)

25、程死鎖。     在計(jì)算機(jī)系統(tǒng)中，涉及軟件，硬件資源都可能發(fā)生死鎖。例如：系統(tǒng)中只有一臺(tái)CD-ROM驅(qū)動(dòng)器和一臺(tái)打印機(jī)，某一個(gè)進(jìn)程占有了CD-ROM驅(qū)動(dòng)器，又申請(qǐng)打印機(jī)；另一進(jìn)程占有了打印機(jī)，還申請(qǐng)CD-ROM。結(jié)果，兩個(gè)進(jìn)程都被阻塞，永遠(yuǎn)也不能自行解除。   所謂死鎖，是指多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無(wú)限期地僵持下去的局面。很顯然，如果沒(méi)有外力的作用，那麼死鎖涉及到的各個(gè)進(jìn)程都將永遠(yuǎn)處于封鎖狀態(tài)。從上面的例子可以看出，計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng)。即：一種原因是系統(tǒng)提供的資源太少了，遠(yuǎn)不

26、能滿足并發(fā)進(jìn)程對(duì)資源的需求。這種競(jìng)爭(zhēng)資源引起的死鎖是我們要討論的核心。例如：消息是一種臨時(shí)性資源。某一時(shí)刻，進(jìn)程A等待進(jìn)程B發(fā)來(lái)的消息，進(jìn)程B等待進(jìn)程C發(fā)來(lái)的消息，而進(jìn)程C又等待進(jìn)程A發(fā)來(lái)的消息。消息未到，A，B，C三個(gè)進(jìn)程均無(wú)法向前推進(jìn)，也會(huì)發(fā)生進(jìn)程通信上的死鎖。另一種原因是由于進(jìn)程推進(jìn)順序不合適引發(fā)的死鎖。資源少也未必一定產(chǎn)生死鎖。就如同兩個(gè)人過(guò)獨(dú)木橋，如果兩個(gè)人都要先過(guò)，在獨(dú)木橋上僵持不肯后退，必然會(huì)應(yīng)競(jìng)爭(zhēng)資源產(chǎn)生死鎖；但是，如果兩個(gè)人上橋前先看一看有無(wú)對(duì)方的人在橋上，當(dāng)無(wú)對(duì)方的人在橋上時(shí)自己才上橋，那麼問(wèn)題就解決了。所以，如果程序設(shè)計(jì)得不合理，造成進(jìn)程推進(jìn)的順序不當(dāng)，也會(huì)出現(xiàn)死鎖。&#

27、160;2.5. 產(chǎn)生死鎖的必要條件   從以上分析可見(jiàn)，如果在計(jì)算機(jī)系統(tǒng)中同時(shí)具備下面四個(gè)必要條件時(shí)，那麼會(huì)發(fā)生死鎖。換句話說(shuō)，只要下面四個(gè)條件有一個(gè)不具備，系統(tǒng)就不會(huì)出現(xiàn)死鎖。     1互斥條件。即某個(gè)資源在一段時(shí)間內(nèi)只能由一個(gè)進(jìn)程占有，不能同時(shí)被兩個(gè)或兩個(gè)以上的進(jìn)程占有。這種獨(dú)占資源如CD-ROM驅(qū)動(dòng)器，打印機(jī)等等，必須在占有該資源的進(jìn)程主動(dòng)釋放它之后，其它進(jìn)程才能占有該資源。這是由資源本身的屬性所決定的。如獨(dú)木橋就是一種獨(dú)占資源，兩方的人不能同時(shí)過(guò)橋。   

28、0; 2不可搶占條件。進(jìn)程所獲得的資源在未使用完畢之前，資源申請(qǐng)者不能強(qiáng)行地從資源占有者手中奪取資源，而只能由該資源的占有者進(jìn)程自行釋放。如過(guò)獨(dú)木橋的人不能強(qiáng)迫對(duì)方后退，也不能非法地將對(duì)方推下橋，必須是橋上的人自己過(guò)橋后空出橋面（即主動(dòng)釋放占有資源），對(duì)方的人才能過(guò)橋。     3占有且申請(qǐng)條件。進(jìn)程至少已經(jīng)占有一個(gè)資源，但又申請(qǐng)新的資源；由于該資源已被另外進(jìn)程占有，此時(shí)該進(jìn)程阻塞；但是，它在等待新資源之時(shí)，仍繼續(xù)占用已占有的資源。還以過(guò)獨(dú)木橋?yàn)槔?，甲乙兩人在橋上相遇。甲走過(guò)一段橋面（即占有了一些資源），還需要走其余的橋面（申請(qǐng)新的資

29、源），但那部分橋面被乙占有（乙走過(guò)一段橋面）。甲過(guò)不去，前進(jìn)不能，又不后退；乙也處于同樣的狀況。     4循環(huán)等待條件。存在一個(gè)進(jìn)程等待序列P1，P2，.，Pn，其中P1等待P2所占有的某一資源，P2等待P3所占有的某一源，.，而Pn等待P1所占有的的某一資源，形成一個(gè)進(jìn)程循環(huán)等待環(huán)。就像前面的過(guò)獨(dú)木橋問(wèn)題，甲等待乙占有的橋面，而乙又等待甲占有的橋面，從而彼此循環(huán)等待。   上面我們提到的這四個(gè)條件在死鎖時(shí)會(huì)同時(shí)發(fā)生。也就是說(shuō)，只要有一個(gè)必要條件不滿足，則死鎖就可以排除。 2.6. 解決死鎖的

30、方法 2.6.1. 死鎖的預(yù)防     前面介紹了死鎖發(fā)生時(shí)的四個(gè)必要條件，只要破壞這四個(gè)必要條件中的任意一個(gè)條件，死鎖就不會(huì)發(fā)生。這就為我們解決死鎖問(wèn)題提供了可能。一般地，解決死鎖的方法分為死鎖的預(yù)防，避免，檢測(cè)與恢復(fù)三種（注意：死鎖的檢測(cè)與恢復(fù)是一個(gè)方法）。我們將在下面分別加以介紹。   死鎖的預(yù)防是保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的一種策略。它的基本思想是要求進(jìn)程申請(qǐng)資源時(shí)遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，保證系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。   

31、60;1打破互斥條件。即允許進(jìn)程同時(shí)訪問(wèn)某些資源。但是，有的資源是不允許被同時(shí)訪問(wèn)的，像打印機(jī)等等，這是由資源本身的屬性所決定的。所以，這種辦法并無(wú)實(shí)用價(jià)值。    2打破不可搶占條件。即允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。就是說(shuō)，當(dāng)一個(gè)進(jìn)程已占有了某些資源，它又申請(qǐng)新的資源，但不能立即被滿足時(shí)，它必須釋放所占有的全部資源，以后再重新申請(qǐng)。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強(qiáng)占了。這種預(yù)防死鎖的方法實(shí)現(xiàn)起來(lái)困難，會(huì)降低系統(tǒng)性能。       

32、0; 3打破占有且申請(qǐng)條件?？梢詫?shí)行資源預(yù)先分配策略。即進(jìn)程在運(yùn)行前一次性地向系統(tǒng)申請(qǐng)它所需要的全部資源。如果某個(gè)進(jìn)程所需的全部資源得不到滿足，則不分配任何資源，此進(jìn)程暫不運(yùn)行。只有當(dāng)系統(tǒng)能夠滿足當(dāng)前進(jìn)程的全部資源需求時(shí)，才一次性地將所申請(qǐng)的資源全部分配給該進(jìn)程。由于運(yùn)行的進(jìn)程已占有了它所需的全部資源，所以不會(huì)發(fā)生占有資源又申請(qǐng)資源的現(xiàn)象，因此不會(huì)發(fā)生死鎖。但是，這種策略也有如下缺點(diǎn)： （1）在許多情況下，一個(gè)進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時(shí)是動(dòng)態(tài)的，不可預(yù)測(cè)的；（2）資源利用率低。無(wú)論所分資源何時(shí)用到，一個(gè)進(jìn)程只有在占有所需的全部資源后才能

33、執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長(zhǎng)期占著不用的狀況。這顯然是一種極大的資源浪費(fèi)； （3）降低了進(jìn)程的并發(fā)性。因?yàn)橘Y源有限，又加上存在浪費(fèi)，能分配到所需全部資源的進(jìn)程個(gè)數(shù)就必然少了。       （4）打破循環(huán)等待條件，實(shí)行資源有序分配策略。采用這種策略，即把資源事先分類編號(hào)，按號(hào)分配，使進(jìn)程在申請(qǐng)，占用資源時(shí)不會(huì)形成環(huán)路。所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按資源序號(hào)遞增的順序提出。進(jìn)程占用了小號(hào)資源，才能申請(qǐng)大號(hào)資源，就不會(huì)產(chǎn)生環(huán)路，從而預(yù)防了死鎖。這種策略與前面的策略相比

34、，資源的利用率和系統(tǒng)吞吐量都有很大提高，但是也存在以下缺點(diǎn)： （1）限制了進(jìn)程對(duì)資源的請(qǐng)求，同時(shí)給系統(tǒng)中所有資源合理編號(hào)也是件困難事，并增加了系統(tǒng)開(kāi)銷； （2）為了遵循按編號(hào)申請(qǐng)的次序，暫不使用的資源也需要提前申請(qǐng)，從而增加了進(jìn)程對(duì)資源的占用時(shí)間。 2.6.2. 死鎖的避免      上面我們講到的死鎖預(yù)防是排除死鎖的靜態(tài)策略，它使產(chǎn)生死鎖的四個(gè)必要條件不能同時(shí)具備，從而對(duì)進(jìn)程申請(qǐng)資源的活動(dòng)加以限制，以保證死鎖不會(huì)發(fā)生。下面我們介紹排除死鎖的動(dòng)態(tài)策略-死鎖的避免，它不限制進(jìn)程有關(guān)申請(qǐng)資源的命令，

35、而是對(duì)進(jìn)程所發(fā)出的每一個(gè)申請(qǐng)資源命令加以動(dòng)態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進(jìn)行資源分配。就是說(shuō)，在資源分配過(guò)程中若預(yù)測(cè)有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。   . 安全序列   我們首先引入安全序列的定義：所謂系統(tǒng)是安全的，是指系統(tǒng)中的所有進(jìn)程能夠按照某一種次序分配資源，并且依次地運(yùn)行完畢，這種進(jìn)程序列P1，P2，.，Pn就是安全序列。如果存在這樣一個(gè)安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這樣一個(gè)安全序列，則系統(tǒng)是不安全的。   安全序列P1，P

36、2，.，Pn是這樣組成的：若對(duì)于每一個(gè)進(jìn)程Pi，它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足，則P1，P2，.，Pn為一個(gè)安全序列，這時(shí)系統(tǒng)處于安全狀態(tài)，不會(huì)進(jìn)入死鎖狀態(tài)。     雖然存在安全序列時(shí)一定不會(huì)有死鎖發(fā)生，但是系統(tǒng)進(jìn)入不安全狀態(tài)（四個(gè)死鎖的必要條件同時(shí)發(fā)生）也未必會(huì)產(chǎn)生死鎖。當(dāng)然，產(chǎn)生死鎖后，系統(tǒng)一定處于不安全狀態(tài)。  . 銀行家算法   這是一個(gè)著名的避免死鎖的算法，是由Dijstra首先提出來(lái)并加以解決的。 &

37、#160;  背景知識(shí)    一個(gè)銀行家如何將一定數(shù)目的資金安全地借給若干個(gè)客戶，使這些客戶既能借到錢完成要干的事，同時(shí)銀行家又能收回全部資金而不至于破產(chǎn)，這就是銀行家問(wèn)題。這個(gè)問(wèn)題同操作系統(tǒng)中資源分配問(wèn)題十分相似：銀行家就像一個(gè)操作系統(tǒng)，客戶就像運(yùn)行的進(jìn)程，銀行家的資金就是系統(tǒng)的資源。   問(wèn)題的描述   一個(gè)銀行家擁有一定數(shù)量的資金，有若干個(gè)客戶要貸款。每個(gè)客戶須在一開(kāi)始就聲明他所需貸款的總額。若該客戶貸款總額不超過(guò)銀行家的資金總數(shù)，銀行家可以接收客戶的要求。客戶貸款是以

38、每次一個(gè)資金單位（如1萬(wàn)RMB等）的方式進(jìn)行的，客戶在借滿所需的全部單位款額之前可能會(huì)等待，但銀行家須保證這種等待是有限的，可完成的。   例如：有三個(gè)客戶C1，C2，C3，向銀行家借款，該銀行家的資金總額為10個(gè)資金單位，其中C1客戶要借9各資金單位，C2客戶要借3個(gè)資金單位，C3客戶要借8個(gè)資金單位，總計(jì)20個(gè)資金單位。某一時(shí)刻的狀態(tài)如圖所示。銀行家算法示意   對(duì)于a圖的狀態(tài)，按照安全序列的要求，我們選的第一個(gè)客戶應(yīng)滿足該客戶所需的貸款小于等于銀行家當(dāng)前所剩余的錢款，可以看出只有C2客戶能被滿足：C2客戶需1個(gè)資金單位，小銀行家

39、手中的2個(gè)資金單位，于是銀行家把1個(gè)資金單位借給C2客戶，使之完成工作并歸還所借的3個(gè)資金單位的錢，進(jìn)入b圖。同理，銀行家把4個(gè)資金單位借給C3客戶，使其完成工作，在c圖中，只剩一個(gè)客戶C1，它需7個(gè)資金單位，這時(shí)銀行家有8個(gè)資金單位，所以C1也能順利借到錢并完成工作。最后（見(jiàn)圖d）銀行家收回全部10個(gè)資金單位，保證不賠本。那麼客戶序列C1，C2，C3就是個(gè)安全序列，按照這個(gè)序列貸款，銀行家才是安全的。否則的話，若在圖b狀態(tài)時(shí)，銀行家把手中的4個(gè)資金單位借給了C1，則出現(xiàn)不安全狀態(tài)：這時(shí)C1，C3均不能完成工作，而銀行家手中又沒(méi)有錢了，系統(tǒng)陷入僵持局面，銀行家也不能收回投資。 

40、60; 綜上所述，銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個(gè)按安全序列檢查各客戶誰(shuí)能完成其工作，然后假定其完成工作且歸還全部貸款，再進(jìn)而檢查下一個(gè)能完成工作的客戶，.。如果所有客戶都能完成工作，則找到一個(gè)安全序列，銀行家才是安全的。   從上面分析看出，銀行家算法允許死鎖必要條件中的互斥條件，占有且申請(qǐng)條件，不可搶占條件的存在，這樣，它與預(yù)防死鎖的幾種方法相比較，限制條件少了，資源利用程度提高了。 這是該算法的優(yōu)點(diǎn)。其缺點(diǎn)是：    1這個(gè)算法要求客戶數(shù)保持固定不變，這在多道程序系統(tǒng)中是難以做到的。 &#

41、160;     2這個(gè)算法保證所有客戶在有限的時(shí)間內(nèi)得到滿足，但實(shí)時(shí)客戶要求快速響應(yīng)，所以要考慮這個(gè)因素。       3由于要尋找一個(gè)安全序列，實(shí)際上增加了系統(tǒng)的開(kāi)銷。  2.6.3. 死鎖的檢測(cè)與恢復(fù)    一般來(lái)說(shuō)，由于操作系統(tǒng)有并發(fā)，共享以及隨機(jī)性等特點(diǎn)，通過(guò)預(yù)防和避免的手段達(dá)到排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開(kāi)銷，而且不能充分利用資源。為此，一種簡(jiǎn)便的方法是系統(tǒng)為進(jìn)程分配資源時(shí)，不采取

42、任何限制性措施，但是提供了檢測(cè)和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來(lái)。因此，在實(shí)際的操作系統(tǒng)中往往采用死鎖的檢測(cè)與恢復(fù)方法來(lái)排除死鎖。   死鎖檢測(cè)與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時(shí)，該機(jī)構(gòu)能夠檢測(cè)到死鎖發(fā)生的位置和原因，并能通過(guò)外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來(lái)。 1.放大觀看>>)   圖中所示為一個(gè)小的死鎖的例子。這時(shí)進(jìn)程P1占有資源R1而申請(qǐng)資源R2，進(jìn)程P2占有資源R2而申請(qǐng)資源R1，按循環(huán)等待條件，進(jìn)程和資源形成了環(huán)路，所以系統(tǒng)是死鎖狀態(tài)。進(jìn)程P1，P

43、2是參與死鎖的進(jìn)程。   下面我們?cè)賮?lái)看一看死鎖檢測(cè)算法。算法使用的數(shù)據(jù)結(jié)構(gòu)是如下這些：             占有矩陣A：n*m階，其中n表示并發(fā)進(jìn)程的個(gè)數(shù)，m表示系統(tǒng)的各類資源的個(gè)數(shù)，這個(gè)矩陣記錄了每一個(gè)進(jìn)程當(dāng)前占有各個(gè)資源類中資源的個(gè)數(shù)。        申請(qǐng)矩陣R：n*m階，其中n表示并發(fā)進(jìn)程的個(gè)數(shù)，m表示系統(tǒng)的各類資源的個(gè)數(shù)，這個(gè)矩陣記錄了每一個(gè)進(jìn)

44、程當(dāng)前要完成工作需要申請(qǐng)的各個(gè)資源類中資源的個(gè)數(shù)。        空閑向量T：記錄當(dāng)前m個(gè)資源類中空閑資源的個(gè)數(shù)。        完成向量F：布爾型向量值為真（true）或假（false），記錄當(dāng)前n個(gè)并發(fā)進(jìn)程能否進(jìn)行完。為真即能進(jìn)行完，為假則不能進(jìn)行完。        臨時(shí)向量W：開(kāi)始時(shí)W：=T。 算法步驟：   &

45、#160;  （1）W：=T，      對(duì)于所有的i=1，2，.，n，      如果Ai=0，則Fi：=true；否則，F(xiàn)i：=false      （2）找滿足下面條件的下標(biāo)i：      Fi：=false并且Ri=W      如果不存在滿足上面的條件i，則轉(zhuǎn)到步驟（4

46、）。      （3）W：=W+Ai      Fi：=true      轉(zhuǎn)到步驟（2）      （4）如果存在i，F(xiàn)i：=false，則系統(tǒng)處于死鎖狀態(tài)，且Pi進(jìn)程參與了死鎖。什麼時(shí)候進(jìn)行死鎖的檢測(cè)取決于死鎖發(fā)生的頻率。如果死鎖發(fā)生的頻率高，那麼死鎖檢測(cè)的頻率也要相應(yīng)提高，這樣一方面可以提高系統(tǒng)資源的利用率，一方面可以避免更多的進(jìn)程卷入死鎖。如果進(jìn)程申

47、請(qǐng)資源不能滿足就立刻進(jìn)行檢測(cè)，那麼每當(dāng)死鎖形成時(shí)即能被發(fā)現(xiàn)，這和死鎖避免的算法相近，只是系統(tǒng)的開(kāi)銷較大。為了減小死鎖檢測(cè)帶來(lái)的系統(tǒng)開(kāi)銷，一般采取每隔一段時(shí)間進(jìn)行一次死鎖檢測(cè)，或者在CPU的利用率降低到某一數(shù)值時(shí)，進(jìn)行死鎖的檢測(cè)。  2.死鎖的恢復(fù)一旦在死鎖檢測(cè)時(shí)發(fā)現(xiàn)了死鎖，就要消除死鎖，使系統(tǒng)從死鎖狀態(tài)中恢復(fù)過(guò)來(lái)。       （1）最簡(jiǎn)單，最常用的方法就是進(jìn)行系統(tǒng)的重新啟動(dòng)，不過(guò)這種方法代價(jià)很大，它意味著在這之前所有的進(jìn)程已經(jīng)完成的計(jì)算工作都將付之東流，包括參與死鎖的那些進(jìn)程，以及未參與死鎖的進(jìn)程。&#

48、160;    （2）撤消進(jìn)程，剝奪資源。終止參與死鎖的進(jìn)程，收回它們占有的資源，從而解除死鎖。這時(shí)又分兩種情況：一次性撤消參與死鎖的全部進(jìn)程，剝奪全部資源；或者逐步撤消參與死鎖的進(jìn)程，逐步收回死鎖進(jìn)程占有的資源。一般來(lái)說(shuō)，選擇逐步撤消的進(jìn)程時(shí)要按照一定的原則進(jìn)行，目的是撤消那些代價(jià)最小的進(jìn)程，比如按進(jìn)程的優(yōu)先級(jí)確定進(jìn)程的代價(jià)；考慮進(jìn)程運(yùn)行時(shí)的代價(jià)和與此進(jìn)程相關(guān)的外部作業(yè)的代價(jià)等因素。    此外，還有進(jìn)程回退策略，即讓參與死鎖的進(jìn)程回退到?jīng)]有發(fā)生死鎖前某一點(diǎn)處，并由此點(diǎn)處繼續(xù)執(zhí)行，以求再次執(zhí)行時(shí)不再發(fā)生死鎖。雖然

49、這是個(gè)較理想的辦法，但是操作起來(lái)系統(tǒng)開(kāi)銷極大，要有堆棧這樣的機(jī)構(gòu)記錄進(jìn)程的每一步變化，以便今后的回退，有時(shí)這是無(wú)法做到的。  2.2. 畫出網(wǎng)絡(luò)中的星型結(jié)構(gòu)、總線結(jié)構(gòu)、環(huán)型結(jié)構(gòu)和樹(shù)型拓?fù)浣Y(jié)構(gòu)，并說(shuō)明星型和總線型拓?fù)浣Y(jié)構(gòu)。    2.3. 把中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式         2.4. A-H  8個(gè)字符出現(xiàn)的頻率依次為  0.16 0.10 0.01

50、 0.29 0.10  0.05 0.09  0.26  （注明：這幾個(gè)數(shù)我記不清，反正就是這么幾個(gè)數(shù)）構(gòu)造最優(yōu)二叉樹(shù)，并將 A-H  8個(gè)字符用二進(jìn)制碼表示及計(jì)算平均碼長(zhǎng)。    2.5. 操作系統(tǒng)中的快表相關(guān)的問(wèn)題  2.6. java的異常處理機(jī)制有什么優(yōu)點(diǎn)  2.7. 輸出字符串中第一個(gè)只出現(xiàn)一次的字符，用兩種方案。 2.8. 某進(jìn)程被喚醒

51、并立即運(yùn)行,該系統(tǒng)采用的是剝奪調(diào)度方法嗎?為什么?   某進(jìn)程被喚醒并立即運(yùn)行并不能說(shuō)明該系統(tǒng)是剝奪調(diào)度算法。 進(jìn)程調(diào)度有以下兩種基本方式： (1)、非剝奪方式：一旦把處理器分配給某進(jìn)程后便讓它一直運(yùn)行下去，知道進(jìn)程完成或發(fā)生某事件阻塞時(shí)，才把處理器分配給另一個(gè)進(jìn)程。 (2)、剝奪方式：當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理器，將之分配給其他進(jìn)程。 2.9. A,B,C,D四個(gè)元素依次進(jìn)棧,進(jìn)棧過(guò)程中允許出棧,寫出所有可能的出棧序列。 解題思路： 1、先進(jìn)先出 

52、;2、先進(jìn)后出 3、還沒(méi)進(jìn)完就出 4、進(jìn)完了才出 進(jìn)一個(gè)出一個(gè)，ABCD 先進(jìn)兩個(gè)，AB進(jìn)，進(jìn)C出C,進(jìn)D出D，出B出A，CDBA 進(jìn)A進(jìn)B，進(jìn)C進(jìn)D，出D出C出B出A，DCBA 下面的不解釋了，不明白你再問(wèn) BCDA,BDCA,BCAD,BADC,BACD, 前三個(gè)一起進(jìn) CBAD,CBDA,CDBA 第一個(gè)進(jìn)去就出來(lái) ADCB,ACDB,ACBD 一共14種 2.10. UML中四類動(dòng)態(tài)建模圖(狀態(tài)圖，協(xié)作圖，活動(dòng)圖，序列圖)的區(qū)別與用途 U

53、ML提供圖來(lái)描述系統(tǒng)的結(jié)構(gòu)和行為。在其中，類圖用于描述系統(tǒng)的靜態(tài)結(jié)構(gòu)，狀態(tài)圖，協(xié)作圖，活動(dòng)圖，序列圖則用于描述系統(tǒng)的動(dòng)態(tài)行為，描述系統(tǒng)在執(zhí)行期間不同時(shí)間點(diǎn)是如何動(dòng)態(tài)交互的。       在這四種圖中可以大體分為兩類:以描述系統(tǒng)狀態(tài)轉(zhuǎn)移為主的狀態(tài)圖和活動(dòng)圖，以描述系統(tǒng)系統(tǒng)對(duì)象通訊和交互為主的協(xié)作圖和序列圖。   1，以描述系統(tǒng)狀態(tài)轉(zhuǎn)移為主的狀態(tài)圖和活動(dòng)圖   狀態(tài)圖：用來(lái)描述對(duì)象，子系統(tǒng)，系統(tǒng)的生命周期。通過(guò)狀態(tài)圖可以了解一個(gè)對(duì)象所能達(dá)到的所有狀態(tài)，以及對(duì)象收到的事件

54、對(duì)對(duì)象狀態(tài)的影響。   活動(dòng)圖：顯示動(dòng)作及其結(jié)果。著重描述操作（方法）實(shí)現(xiàn)中所完成的工作以及實(shí)例或?qū)ο笾械幕顒?dòng)，它是狀態(tài)圖的一個(gè)變種。   狀態(tài)圖與活動(dòng)圖的區(qū)別：活動(dòng)圖主要描述動(dòng)作及對(duì)象狀態(tài)改變的結(jié)果。狀態(tài)圖主要描述的是事件對(duì)對(duì)象狀態(tài)的影響。   2，以描述系統(tǒng)對(duì)象通訊和交互為主的協(xié)作圖和序列圖   序列圖：描述對(duì)象是如何交互的。重點(diǎn)放在消息序列上，描述消息在對(duì)象間是如何收發(fā)的。   協(xié)作圖：描述協(xié)作對(duì)象的交互與鏈接。  &#

55、160;協(xié)作圖和序列圖的區(qū)別：協(xié)作圖和序列圖都是描述對(duì)象交互的，但是序列圖強(qiáng)調(diào)的是時(shí)間，協(xié)作圖強(qiáng)調(diào)的空間。2.11. 用圖描述出進(jìn)程的三元狀態(tài)，并簡(jiǎn)單說(shuō)明狀態(tài)之間的轉(zhuǎn)換條件。 進(jìn)程有三個(gè)狀態(tài)：就緒狀態(tài)、運(yùn)行狀態(tài)、阻塞狀態(tài)2.12. 簡(jiǎn)述網(wǎng)上銀行的基本支付模式。 卡號(hào)支付、專業(yè)版支付、動(dòng)態(tài)密碼支付、令牌支付、密碼卡支付。常見(jiàn)的就這些了。 2.13. 給出一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列，畫出二叉樹(shù)并寫出后序遍歷序列。 先來(lái)了解二叉樹(shù)的相關(guān)知識(shí)。 2.13.1. 二叉樹(shù)概念  

56、60;  二叉樹(shù)(binary tree)是一種數(shù)據(jù)結(jié)構(gòu)，是一種樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù) (即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn) )，并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒 。 2.13.2. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)  . 順序存儲(chǔ)結(jié)構(gòu)     連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)的數(shù)據(jù)元素。例如圖 6.4(b)的完全二叉樹(shù) , 可以向量 (一維數(shù)組 ) 

57、bt(1:6)作它的存儲(chǔ)結(jié)構(gòu)，將二叉樹(shù)中編號(hào)為 i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量 bti中 ,如圖 6.6(a) 所示。但這種順序存儲(chǔ)結(jié)構(gòu)僅適合于完全二叉樹(shù) ,而一般二叉樹(shù)也按這種形式來(lái)存儲(chǔ) ,這將造成存 貯浪費(fèi)。如和圖 6.4(c)的二叉樹(shù)相應(yīng)的存儲(chǔ)結(jié)構(gòu)圖 6.6(b)所示，圖中以 “0”表示不存在此結(jié)點(diǎn) 。  . 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 就緒狀態(tài) 阻塞狀態(tài) 運(yùn)行狀態(tài) 當(dāng)進(jìn)程分配了處理機(jī)之后 

58、正在執(zhí)行的進(jìn)程因時(shí)間片段用完而被暫停執(zhí)行；或者在可搶占調(diào)度方式中，一個(gè)優(yōu)先級(jí)高的進(jìn)程到來(lái)，正在執(zhí)行的低優(yōu)先級(jí)進(jìn)程被強(qiáng)制撤下處理機(jī)，轉(zhuǎn)換為就緒狀態(tài)。 正在執(zhí)行的進(jìn)程因等待某事件而無(wú)法正常執(zhí)行。 進(jìn)程所等待的某事件發(fā)生了     由二叉樹(shù)的定義得知二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向左右子樹(shù)的兩個(gè)分支構(gòu)成 ,則表示二叉樹(shù)的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域 :數(shù)據(jù)域和左右指針域 ,如圖 (b)所示。有時(shí) ,為了便于找 到結(jié)點(diǎn)的雙親 ,則還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙

59、親受的指針域，如圖 6.7(c)所示。   2.13.3. 遍歷二叉樹(shù)      遍歷二叉樹(shù) (traversing binary tree)的問(wèn)題， 即如何按某條搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。 其中常見(jiàn)的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和后 (根 )序遍歷。 這三種分類都是以根所在的位置進(jìn)行分類的。

60、 . 前序遍歷      前序遍歷運(yùn)算：即先訪問(wèn)根結(jié)點(diǎn)，再前序遍歷左子樹(shù)，最后再前序遍歷右子樹(shù)。前序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以根、左、右的順序進(jìn)行訪問(wèn)的。 . 中序遍歷      中序遍歷運(yùn)算：即先中前序遍歷左子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)，最后再中序遍歷右子樹(shù)。中序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、根、右的順序進(jìn)行訪問(wèn)的。 . 后序遍歷      后序遍歷運(yùn)算：即先后序遍歷左子樹(shù)，然后再后序遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。后序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、右、根的順序進(jìn)行訪問(wèn)的。  例子：