計算機專業(yè)(基礎綜合)模擬試卷105(題后含答案及解析)

計算機專業(yè)（基礎綜合）模擬試卷105(題后含答案及解析)題型有：1.單項選擇題2.綜合應用題單項選擇題1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。1．關(guān)于線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的描述正確的是()。Ⅰ．線性表的順序存儲結(jié)構(gòu)優(yōu)于其鏈式存儲結(jié)構(gòu)Ⅱ．鏈式存儲結(jié)構(gòu)比順序存儲結(jié)構(gòu)可更方便地表示各種邏輯結(jié)構(gòu)Ⅲ．如頻繁使用插入和刪除結(jié)點操作，順序存儲結(jié)構(gòu)更優(yōu)于鏈式存儲結(jié)構(gòu)Ⅳ．順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都可以進行順序存儲A．僅Ⅰ、Ⅱ、ⅢB．僅Ⅱ、ⅣC．僅Ⅱ、ⅢD．僅Ⅲ、Ⅳ正確答案：B解析：Ⅰ：線性表的兩種存儲結(jié)構(gòu)各有優(yōu)缺點，順序存儲結(jié)構(gòu)支持隨機存儲，對于表內(nèi)任意元素的存取具有較高的效率，這一點優(yōu)于鏈式存儲結(jié)構(gòu)；鏈式存儲結(jié)構(gòu)不需要一次性分配所有空間給線性表，即支持動態(tài)存儲，這一點優(yōu)于順序存儲結(jié)構(gòu)，故Ⅱ錯誤。Ⅱ：比如樹和圖等邏輯結(jié)構(gòu)一般都是使用鏈式存儲結(jié)構(gòu)更為方便，故Ⅱ正確。Ⅲ：鏈式存儲應該更適合頻繁使用插入和刪除操作的線性表，因為不需要移動元素，僅需要修改指針即可；而線性存儲可能需要大量移動元素，故Ⅲ錯誤。Ⅳ：順序存儲結(jié)構(gòu)既可以隨機存儲也能順序存儲；鏈式存儲結(jié)構(gòu)只能順序存儲。綜上所述，Ⅱ、Ⅳ正確。2．相對于單向鏈表，使用雙向鏈表存儲線性表，其優(yōu)點是()。Ⅰ．提高查找速度Ⅱ．節(jié)約存儲空間Ⅲ．數(shù)據(jù)的插入和刪除更快速A．僅ⅠB．僅Ⅰ、ⅢC．僅ⅢD．僅Ⅱ、Ⅲ正確答案：C解析：在雙向鏈表中的查找仍然是順序查找，故查找速度并沒有提高；雙向鏈表中有兩個指針域，所以不但不能節(jié)約存儲空間，相比單鏈表，還增加了空間；既然增加了空間，那必須是以空間來換取時間，導致的結(jié)果就是數(shù)據(jù)的插入和刪除將會更快速。3．對于一個滿二叉樹，共有n個結(jié)點和m個葉子結(jié)點，且深度為h，則下列等式中正確的是()。Ⅰ．n=h+mⅡ．h+m=2nⅢ．m=2h-1Ⅳ．n=2h-1A．Ⅰ、Ⅱ、ⅢB．Ⅱ、ⅢC．Ⅱ、Ⅲ、ⅣD．Ⅲ、Ⅳ正確答案：D解析：對于深度為h的滿二叉樹，n=20+21+…+2h-1=2h-1；另外，根據(jù)滿二叉樹的性質(zhì)可知，m=2h-1，故Ⅲ、Ⅳ正確；而Ⅰ、Ⅱ舉反例很容易被排除。4．設一棵二叉樹是由森林轉(zhuǎn)換而來的，若森林中有n個非終端結(jié)點，則二叉樹中無右孩子的結(jié)點個數(shù)為()。A．n-1B．nC．n+1D．n+2正確答案：C解析：首先，對于一棵樹來講，每個非終端結(jié)點(除了樹的根結(jié)點)轉(zhuǎn)換成二叉樹后都對應一個無右孩子的結(jié)點，因為一個非終端結(jié)點至少有一個孩子結(jié)點，其最右邊的孩子結(jié)點轉(zhuǎn)換成二叉樹后一定沒有右孩子。為什么要除去根結(jié)點?因為根結(jié)點比較特殊，樹轉(zhuǎn)換成二叉樹之后，根結(jié)點本身也將會沒有右孩子。所以對于一棵具有n個非終端結(jié)點的樹來講，將其轉(zhuǎn)換成二叉樹之后，二叉樹中無右孩子的結(jié)點個數(shù)為n+1個。其實，此時已經(jīng)可以選出答案了，因為一棵樹也可以算是一個森林。如果一個森林有多棵樹(假設有x棵)，我們先把所有樹的根結(jié)點拿出來。除根結(jié)點之外的非終端結(jié)點(n-x個)轉(zhuǎn)換成二叉樹之后都是對應一個無右孩子的結(jié)點，可得到n-x個無右孩子的結(jié)點。但是，x個根結(jié)點是不足就對應2x個無右孩子的結(jié)點?顯然不是，因為下一棵數(shù)將會成為上一棵樹根結(jié)點的右孩子(見圖5-3)，所以只有森林的最后一棵樹的根結(jié)點才會變成無右孩子的結(jié)點，故x個根結(jié)點將會得到x+1個無右孩子的根結(jié)點，所以一共可以得到n-x+(x+1)=n+1個無右孩子的根結(jié)點。從圖5-3可以看出，三棵樹的根結(jié)點A、E、G轉(zhuǎn)換成二叉樹之后，只有最后一棵樹的根結(jié)點G是沒有右孩子的。綜上分析，二叉樹中無右孩子的結(jié)點個數(shù)為n+1個，故選C選項。5．若某完全二叉樹的結(jié)點個數(shù)為100，則第60個結(jié)點的度為()．A．0B．1C．2D．不確定正確答案：A解析：完全二叉樹的結(jié)點個數(shù)為偶數(shù)，說明有1個度為1的結(jié)點。設ni為度是i的結(jié)點的個數(shù)，那么就有：n0+n2+1=100，n0=n2-1，解得：n0=55，n2=54；又因為完全二叉樹的編號是先度為2的結(jié)點，然后度為1的結(jié)點，最后才是葉子結(jié)點，即1～54是度為2的結(jié)點，55是度為1的結(jié)點，56～100是度為0的結(jié)點。因此，第60個結(jié)點為度為0的結(jié)點。6．下列關(guān)于二叉樹的說法中，錯誤的是()。A．在二叉樹的后序序列中最后一個結(jié)點一定是二叉樹的根結(jié)點B．在二叉樹的中序序列中最后一個結(jié)點一定是二叉樹的一個葉結(jié)點C．在二叉樹的前序序列中最后一個結(jié)點一定是二叉樹的一個葉結(jié)點D．在二叉樹的層序序列中最后一個結(jié)點一定是二叉樹的一個葉結(jié)點正確答案：B解析：A：后序遍歷遵循LRT，所以最后的一個結(jié)點肯定是該二叉樹的根結(jié)點，故A選項正確。B：中序遍歷遵循LTR，所以如果該根結(jié)點是右子女為空指針的話，就有可能最后訪問的結(jié)點不是葉結(jié)點，例如：最后訪問的是根結(jié)點，而根結(jié)點此時不是葉結(jié)點，故B選項錯誤。C：前序遍歷遵循TLR，所以最后訪問的結(jié)點一定葉結(jié)點。因為如果當前的結(jié)點不是葉結(jié)點，遍歷算法會繼續(xù)遍歷它的子結(jié)點，直到該結(jié)點沒有子結(jié)點，也就是說，該結(jié)點是葉結(jié)點才會停止，故C選項正確。D：層序遍歷是按照二叉樹結(jié)點的序號來訪問的，所以最后一個結(jié)點一定是葉結(jié)點，故D選項正確。7．已知一棵5階B樹有53個關(guān)鍵字，并且每個結(jié)點的關(guān)鍵字都達到最少狀態(tài)，則它的深度是()。A．3B．4C．5D．6正確答案：C解析：根據(jù)B樹定義，m階B樹除根之外所有的非終端結(jié)點至少有[m／2]個結(jié)點，即3個，而根結(jié)點最少有兩個結(jié)點，在每個結(jié)點的關(guān)鍵字是最少狀態(tài)時，5層的滿樹結(jié)點的關(guān)鍵字為2+3×2+3×2×3+3×2×3×3＞53，而4層滿樹結(jié)點關(guān)鍵字為2+3×2+3×2×3＜53，故深度為5。8．設圖G=(V，E)，其中：V={V0，V1，V2，V3}E={(V0，V1)，(V0，V2)，(V0，V3)，(V1，V3)}則從頂點V0開始對圖G的深度優(yōu)先遍歷序列總共有()種。A．3B．4C．5D．2正確答案：B解析：此題的圖為：深度優(yōu)先諞歷的序列有4個：9．下列說法中正確的是()。Ⅰ．對有2500個記錄的索引順序表(分塊表)進行查找，最理想的塊長為50Ⅱ．順序查找法只適合于順序存儲結(jié)構(gòu)，不適合于鏈式存儲結(jié)構(gòu)Ⅲ．折半查找過程所對應判定樹是一棵完全二叉樹Ⅳ．理想情況下，散列表的平均比較次數(shù)可達到1次A．Ⅰ、ⅣB．Ⅱ、Ⅲ、ⅣC．Ⅲ、ⅣD．Ⅰ、Ⅱ、Ⅲ、Ⅳ正確答案：A解析：Ⅰ：分塊查找的平均查找長度不僅和表的總長度n有關(guān)，而且和所分的子表個數(shù)有關(guān)，對于n給定的情況下，s取時，平均查長度取得最小值，所以最理想塊長為50，故Ⅰ正確(注意：此題務必記住該結(jié)論)。Ⅱ：順序查找法就是從線性表的一端開始順序查找，并且逐個檢查關(guān)鍵字是否滿足給定的條件。所以順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)均適合(表可以無序)，故Ⅱ錯誤。Ⅲ：判定樹的結(jié)構(gòu)一定是先排滿一層，再排下一層，所以只有最低一層可能不滿。并且最低一層的葉子結(jié)點也不一定是從左到右按序排放，故不一定是完全二叉樹，故Ⅲ錯誤。Ⅳ：在理想情況下，散列表通過散列函數(shù)可直接計算得到元素的位置，所以平均比較次數(shù)可達到1，故Ⅳ正確。10．用某種排序方法對線性表{24，88，21，48，15，27，69，35，20}進行排序時，元素序列的變化情況如下：(1)24，88，21，48，15，27，69，35，20(2)20，15，21，24，48，27，69，35，88(3)15，20，21，24，35，27，48，69，88(4)15，20，21，24，27，35，48，69，88所采用的排序方法是：A．快速排序B．選擇排序C．希爾排序D．歸并排序正確答案：A解析：本題我們不容易一次就確定到底采用哪種排序方法，那么就可以采用排除法，按照四個選項當中的算法去模擬一遍。如果是選擇排序，則在4輪排序過程中無法得到最后的排序結(jié)構(gòu)，因為選擇排序每次只能確定一個元素的位置；如果是希爾排序不可能在第一步將20換到第一位。同理也不是歸并排序。這4次過程中是子序列同時進行的快速排序。11．假設在磁盤上存放有375000個記錄，做5路平衡歸并排序，內(nèi)存工作區(qū)能容納600個記錄，為把所有記錄都排好序，需要做()趟歸并排序。A．3B．4C．5D．6正確答案：B解析：假設做m路平衡歸并排序，且有n個初始歸并段，則歸并趟數(shù)為[logmn]。所以此題只需求出初始歸并段n即可，n=375000／600=625。故歸并趟數(shù)為[log5625]=4。12．假定有兩個帶符號整數(shù)x、y用8位補碼表示，x=63，y=-31，則x-y的機器數(shù)及其相應的溢出標志OF分別是()。A．5DH、0B．5EH、0C．5DH、1D．5EH、1正確答案：B解析：因為x=63，y=-31，則x-y=94，而帶符號的8位整數(shù)補碼所能表示的范圍是-128～127，所以94在其范圍之內(nèi)，沒有溢出，即OF標志為0，將結(jié)果轉(zhuǎn)化為機器數(shù)為5EH。此種題型在2009年，2014年的統(tǒng)考卷當中已經(jīng)出現(xiàn)，現(xiàn)在對于這種在選擇題當中出現(xiàn)補碼加減運算或者是涉及浮點數(shù)加減計算的情況，總結(jié)如下：(1)涉及浮點數(shù)計算或者是復雜的補碼的計算，不要立刻去按照補碼的規(guī)則和浮點數(shù)加減規(guī)則去運算，不要關(guān)注題干給你的一些無用信息(比如浮點數(shù)的各運算步驟之類的)。(2)觀察題干給你的兩個數(shù)，可以試著加加看，或者減減看，看結(jié)果到底為多少，然后看這個結(jié)果是否在寄存器所能表示的數(shù)(一般是補碼)的范圍之內(nèi)。如果不能表示，那一定是溢出了，如果能表示，再把這個結(jié)果化為二進制或者十六進制。13．十進制數(shù)-5基于單精度浮點數(shù)IEEE754標準的編碼是()。(注：單精度浮點數(shù)IEEE754格式為符號位1位、尾數(shù)23位、階碼8位，且階碼用移碼表示)A．(COA00000)16B．(81D00000)16C．(41500000)16D．(01D00000)16正確答案：A解析：-5用二進制表示為～0101，且符號位S為-1。0101=1．01×22，故e=2，則E=127+2=129，轉(zhuǎn)換成二進制為10000001，所以單精度浮點數(shù)IEEE754標準為11000000101000000000000000000000數(shù)符階碼尾數(shù)然后按照4位一組進行組合，11000000101000000000000000000000，轉(zhuǎn)換成十六進制為(C0A00000)16。14．設機器數(shù)字長16位，有一個C語言程序段如下：intn=0xA1B6;unsignedintm=n;m=m＞＞1;／／m右移一位則在執(zhí)行完該段程序后，m的值為()A．50DBHB．FFB6HC．A186HD．DODBH正確答案：A解析：無符號數(shù)的移位方式為邏輯移位，不管是左移還是右移，都是添0。A186H作為無符號數(shù)，使用邏輯右移。1010000110110110右移一位得0101000011011011，即50DBH，故選A。15．地址總線為A15(高位)～A0(低位)，若用1K×4位的存儲芯片組成4KB的存儲器，地址總線的高位做片選信號，則以下說法正確的是()。Ⅰ．加在各存儲芯片上的地址線是A11～A0Ⅱ．加在各存儲芯片上的地址線是A9～A0Ⅲ．一共需要使用8片1K×4位的存儲芯片Ⅳ．一共需要使用4片1K×4位的存儲芯片A．Ⅰ、ⅢB．Ⅱ、ⅣC．Ⅱ、ⅢD．Ⅰ、Ⅳ正確答案：C解析：首先要用1K×4位的存儲芯片組成4KB(即4K×8位)的存儲器，需要對字位一起擴展。由公式可知，共需要的芯片數(shù)為(4K×8位)／(1K×4位)=8，所以Ⅲ是正確的。另外，加在各存儲芯片上的地址線只與存儲芯片的存儲容量有關(guān)，本題芯片的存儲容量為1K，又因為210=1K，所以選取地址線的10位A9～A0作為各個存儲芯片上的地址線。16．假設某計算機采用小端方式存儲，按字節(jié)編址。一維數(shù)組a有100個元素，其類型為float，存放在地址C0001000H開始的連續(xù)區(qū)域中，則最后一個數(shù)組元素的最高有效位(MSB)所在的地址應為()。A．C0001396HB．C0001399HC．C000118CHD．C000118FH正確答案：D解析：這里考到了一個非常重要的概念——小端法，float類型的數(shù)據(jù)在計算機中占4個字節(jié)，100個float類型的數(shù)組元素應當占400字節(jié)，即最后一個字節(jié)在內(nèi)存中的相對地址應為399，加上初始數(shù)組起始地址C0001000H，得到最后一個字節(jié)的地址是C000118FH，又因為是小端法，則最后一個數(shù)組元素的低位字節(jié)在前，高位字節(jié)在后，所以最后一個字節(jié)就是最后一個數(shù)組元素的最高有效位地址，所以答案是D。17．某機器中有16個寄存器，假設機器字長為12位，下列()指令可以使用單字長指令來實現(xiàn)。Ⅰ．4條三寄存器指令Ⅱ．255條單寄存器指令Ⅲ．16條0寄存器指令A．僅Ⅰ、ⅡB．僅Ⅱ、ⅢC．僅Ⅰ、ⅢD．僅Ⅱ正確答案：B解析：由于該機器有16個寄存器，所以需要4位來表示這16個寄存器。Ⅰ：4條指令需要兩位來表示。4條三寄存器指令的操作碼部分需要兩位，而三寄存器需要使用4×3=12位來尋址，共需要14位，故字長12位不能表示4條三寄存器指令。Ⅱ：255條單寄存器指令可以用單字長指令來表示，8位操作碼+4位寄存器地址。Ⅲ：16條0寄存器指令可以用單字長指令來表示，只需4位操作碼。18．假設某條指令的一個操作數(shù)采用變址尋址方式，變址寄存器的內(nèi)容為8H，指令中給出的形式地址為1200H，地址為1200H的內(nèi)存單元中的內(nèi)容為12FCH，地址為12FCH的內(nèi)存單元的內(nèi)容為3888H，則該操作數(shù)的有效地址為()。A．1200HB．12FCHC．1208HD．3888H正確答案：C解析：該操作數(shù)的有效地址為變址寄存器的內(nèi)容加上形式地址，即8H+1200H=1208H。19．下列關(guān)于多核處理器說法中，正確的是()。Ⅰ．多核表明一個處理器擁有多個芯片Ⅱ．維持Cache一致性為其主要技術(shù)之一Ⅲ．多核之間共享一個統(tǒng)一地址空間A．僅Ⅰ、ⅡB．僅Ⅱ、ⅢC．僅Ⅰ、ⅢD．Ⅰ、Ⅱ和Ⅲ正確答案：B解析：Ⅰ：多核處理器是指單芯片處理器，即在一個芯片內(nèi)集成兩個或多個完整且并行工作的處理器核心而構(gòu)成的處理器。而“核心”通常包含指令部件、算術(shù)／邏輯部件、寄存器堆和一級或二級的緩存處理單元，這些核心通過某種方式互聯(lián)后，能夠相互交換數(shù)據(jù)，對外呈現(xiàn)為一個統(tǒng)一的多核處理器，故Ⅰ錯誤。Ⅱ：多核處理主要包含三大技術(shù)，即維持Cache一致性、核間通信技術(shù)、對軟件設計的挑戰(zhàn)，故Ⅱ正確。Ⅲ：如圖5-6所示，多個CPU共享統(tǒng)一的地址空間，且獨自又擁有屬于自己的L1Cache，故Ⅲ正確。20．假設計算機系統(tǒng)中軟盤以中斷方式與CPU進行數(shù)據(jù)交換，主頻為50MHz，傳輸單位為16位，軟盤的數(shù)據(jù)傳輸率為50kB／s。若每次數(shù)據(jù)傳輸?shù)拈_銷(包括中斷響應和中斷處理)為100個時鐘周期，則軟盤工作時CPU用于軟盤數(shù)據(jù)傳輸?shù)臅r間占整個CPU時間的百分比是()。A．0％B．5％C．1．5％D．15％正確答案：B解析：主頻為50MHz，則每秒會有50M個時鐘周期；軟盤的數(shù)據(jù)傳輸率為50kB／s，每次傳輸16位，則每秒要進行50kB*8／16=25k次傳輸，又因為每次傳輸，CPU的開銷為100個時鐘周期，所以每秒CU花在數(shù)據(jù)傳輸上的開銷為25k*100個時鐘周期，故CPU用于軟盤傳輸數(shù)據(jù)的時間占CPU時間的比率為25k*100／50M=5％；(提示：由頻率就可直接求出時鐘周期數(shù)，不要再去計算周期時間)21．某計算機有8個主設備競爭總線使用權(quán)，使用鏈式請求方式進行總線判優(yōu)控制，則該機為實現(xiàn)總線判優(yōu)控制需要的控制線數(shù)為()。A．3B．16C．5D．無法確定正確答案：A解析：鏈式請求方式下，為實現(xiàn)總線判優(yōu)控制，需要一根總線請求線、一根總線忙線、一根總線同意線，共三根控制線。而B和C選項分別對應獨立請求方式和計數(shù)器查詢方式所需要的線數(shù)。22．下列說法中，錯誤的是()。Ⅰ．程序中斷過程是由硬件和中斷服務程序共同完成的Ⅱ．每條指令的執(zhí)行過程中，每個總線周期要檢查一次有無中斷請求Ⅲ．檢測有無DMA請求，一般安排在一條指令執(zhí)行過程的末尾Ⅳ．中斷服務程序的最后指令是無條件轉(zhuǎn)移指令A．僅Ⅲ、ⅣB．僅Ⅱ、Ⅲ、ⅣC．僅Ⅱ、ⅣD．Ⅰ、Ⅱ、Ⅲ、Ⅳ正確答案：B解析：Ⅰ：程序中斷過程由硬件(如向量地址形成部件等)和中斷服務程序共同完成的，故Ⅰ正確。Ⅱ：每條指令執(zhí)行周期結(jié)束后，CPU會統(tǒng)一掃描各個中斷源，然后進行判優(yōu)來決定響應哪個中斷源，故Ⅱ錯誤。Ⅲ：CPU會在每個存儲周期結(jié)束后檢查是否有DMA請求，故Ⅲ錯誤。Ⅳ：中斷服務程序的最后指令通常是中斷返回指令(RETI)，該指令在中斷恢復之后，也就是此時CPU中的所有寄存器都已經(jīng)恢復到了中斷之前的狀態(tài)，因此該指令不需要進行無條件轉(zhuǎn)移，只需要通知CPU開始從PC中取指，進入取指周期即可，事實上，該指令可以理解為，它設置了一個標志，當CPU檢測到該標志的時候，就進入新的取指周期，故Ⅳ錯誤。23．下列說法中，正確的有()。Ⅰ．清除內(nèi)存、設置時鐘都是特權(quán)指令，只能在內(nèi)核態(tài)(系統(tǒng)態(tài)、管態(tài))下執(zhí)行Ⅱ．用零作除數(shù)將產(chǎn)生中斷Ⅲ．用戶態(tài)到內(nèi)核態(tài)的轉(zhuǎn)換是由硬件完成的Ⅳ．在中斷發(fā)生后，進入中斷處理的程序可能是操作系統(tǒng)程序，也可能是應用程序A．僅Ⅰ、ⅢB．僅Ⅰ、Ⅱ、ⅣC．僅Ⅱ、Ⅲ、ⅣD．Ⅰ、Ⅱ、Ⅲ、Ⅳ正確答案：A解析：Ⅰ正確，在雙重操作模式(即內(nèi)核態(tài)和用戶態(tài))中，用戶把能引起損害的機器指令作為特權(quán)指令，只允許在內(nèi)核態(tài)下執(zhí)行特權(quán)指令。判斷以下指令是特權(quán)指令嗎?(√)改變存儲器管理的寄存器。(√)寫程序指針。(×)讀取日期時鐘。(√)設置日期時鐘。(√)改變處理器的優(yōu)先級。(√)訪管指令。(√)系統(tǒng)重啟動。(√)讀取程序狀態(tài)字。(√)關(guān)閉中斷。(√)寫指令寄存器。Ⅱ錯誤，用零作除數(shù)將產(chǎn)生異常而不是中斷。這里考查中斷和異常的概念區(qū)分。中斷和異常是導致處理器轉(zhuǎn)向正?？刂屏髦獾拇a的兩種操作系統(tǒng)條件。中斷是異步事件，并且與處理器當前正在執(zhí)行的任務毫無關(guān)系。中斷主要由硬件如I／O設備、處理機、時鐘或定時器引起的，是隨機發(fā)生的事件，另外中斷可以被允許，也可以被禁止。異常是同步事件，是某些特定指令執(zhí)行的結(jié)果，在同樣的條件下用同樣的數(shù)據(jù)第二次運行一個程序可以重現(xiàn)異常。異常的例子有內(nèi)存訪問違例、特定的調(diào)試器指令(例如int3)，以及除零錯誤等。Ⅲ正確，計算機通過硬件中斷機制完成由用戶態(tài)到內(nèi)核態(tài)的轉(zhuǎn)換。Ⅳ錯誤，進入中斷處理的程序在內(nèi)核態(tài)執(zhí)行，是操作系統(tǒng)程序，不可能是應用程序。24．并發(fā)進程執(zhí)行的相對速度是()。A．由進程的程序結(jié)構(gòu)決定的B．由進程自己來控制的C．與進程調(diào)度策略有關(guān)的D．在進程被創(chuàng)建時確定的正確答案：C解析：并發(fā)進程執(zhí)行的相對速度受進程調(diào)度策略影響，因為采取不同調(diào)度策略(如FCFS,SJF)明顯會影響進程執(zhí)行時間長短，也就是會影響進程執(zhí)行的相對速度。25．下列()調(diào)度算法不適合交互式操作系統(tǒng)。A．高響應比優(yōu)先B．高優(yōu)先級優(yōu)先C．時間片輪轉(zhuǎn)D．先來先服務正確答案：A解析：高響應比優(yōu)先算法需要知道作業(yè)的預計運行時間，但是，一旦作業(yè)創(chuàng)建為進程，在交互式的情況下，預計運行時間是不確定的，因此也就不能計算響應比，故不適用。26．關(guān)于臨界問題的一個算法(假設只有進程P0和P1可能會進入該臨界區(qū))如下(i為0或1)：repeatretry：if(turn!=-1)turn=i；if(turn!=i)gotoretry；turn=-1；臨界區(qū)；turn=0；其他區(qū)域；unti1false；該算法()。A．不能保持進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”B．不能保持進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”C．保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”D．保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”正確答案：B解析：進程并發(fā)時容易產(chǎn)生爭奪資源現(xiàn)象，必須在入口碼處能夠阻止進程同時進入臨界區(qū)。要求根據(jù)給出的入口碼和出口碼判斷程序是否正確，此類出題方式較常見。此類題目要想得出正確答案，關(guān)鍵是找出程序的錯誤。根據(jù)條件可先寫出每個進程的執(zhí)行代碼，注意程序中i的取值應與進程Pi的取值相同：P0：repeatretry：if(turn!=-1)turn=0;①if(turn!=0)gotoretry；②turn=-1;⑤臨界區(qū)；turn=0；其他區(qū)域；unti1false；P1：repeatretry：if(turn!=-1)turn=1；③if(turn!=1)gotoretry；④turn=-1；⑥臨界區(qū)；turn=0；其他區(qū)域；unti1false；入口碼最容易出錯的地方就是在兩個進程同時申請進入臨界區(qū)的時候。若此時兩個進程同時申請資源，此時turn的值是0，按照①②③④⑤⑥的順序執(zhí)行，兩個進程同時進入臨界區(qū)。再討論“饑餓”問題。因為入口碼的判斷條件是turn!=-1，否則進程被阻塞，而只有在臨界區(qū)中存在進程訪問的情況下turn的值才會是-1，所以沒有進程會被餓死。27．設m為同類資源數(shù)，n為系統(tǒng)中并發(fā)進程數(shù)。當n個進程共享m個百斥資源時，每個進程最大需求為w，則下列情況會出現(xiàn)系統(tǒng)死鎖的是()。A．m=2，n=1，w=2B．m=2，n=2，w=1C．m=4，n=3，w=2D．m=4，n=2，w=3正確答案：D解析：當m≥n(w-1)+1時都不會發(fā)生死鎖，等號成立時就是最極端的資源分配情況：每個進程都已經(jīng)占有了w-1個資源，同時都需要再分配一個資源，這是如果要保證不發(fā)生死鎖，系統(tǒng)中至少還有一個可分配的資源，即滿足m≥n(w-1)+1。A、B、C選項都滿足，所以都不發(fā)生死鎖。D選項不滿足，會發(fā)生死鎖。舉例：當m=4，n=2，w=3時，若每個進程各占兩個資源，那么在它們申請第三個資源時，兩個進程都將阻塞，從而進入死鎖狀態(tài)。28．用外存加上內(nèi)存之和與虛擬內(nèi)存空間相比，其大小關(guān)系是()。A．前者比后者大B．前者比后者小C．二者相等D．不一定正確答案：D解析：當外存容量足夠大時，虛擬存儲空間只跟地址結(jié)構(gòu)的位數(shù)相關(guān)，即虛擬存儲空間小于等于內(nèi)存加上外存容量之和。當外存容量不足時，外存容量也成為一個限制條件，即虛擬存儲空間等于內(nèi)存加上外存容量之和。因此二者大小關(guān)系是不確定的。29．有一個矩陣為100×200，即a[100][200]。在一個虛擬系統(tǒng)中，采用LRU算法。系統(tǒng)分給該進程5個頁面來存儲數(shù)據(jù)(不包含程序)，設每頁可存放200個整數(shù)，該程序要對整個數(shù)組初始化，數(shù)組存儲時是按行存放的。試計算下列兩個程序各自的缺頁次數(shù)(假定所有頁都以請求方式調(diào)入)。程序—：for(i=0；i＜=99；i++)for(j=0；j＜=199；j++)A(i][j]：i*j；程序二：for(j=0；j＜=199；j++)for(i=0；i＜=99；i++)A[i][j]=i*j；A．100，200B．100，20000C．200，100D．20000，100正確答案：B解析：本題中，矩陣a有100×200=20000個整數(shù)，每頁存放200個整數(shù)，故一頁可以存放一行數(shù)組元素。系統(tǒng)分配給進程5個頁面存放數(shù)據(jù)，假設程序已調(diào)入內(nèi)存(因題目中沒有提供與程序相關(guān)的數(shù)據(jù)，可以不考慮程序的調(diào)入問題)，因此只需考慮矩陣訪問時產(chǎn)生的缺頁中斷次數(shù)。對于程序一，由于矩陣存放是按行存儲，本程序?qū)仃嘺的訪問也是按行進行的，因此本程序依次將矩陣a的內(nèi)容調(diào)入內(nèi)存，每一頁只調(diào)入一次，每一頁都會發(fā)生一次缺頁中斷，因此會產(chǎn)生20000／200=100次缺頁中斷。對于程序二，矩陣存放時按行存儲，而本程序?qū)仃嘺的訪問是按列進行的。當i=時，內(nèi)層循環(huán)的執(zhí)行將訪問矩陣a的所有元素，需要依次將矩陣a的100行調(diào)入內(nèi)存，將產(chǎn)生100次缺頁中斷。當j=1時，仍需要依次將矩陣a的100行調(diào)入內(nèi)存(因留在內(nèi)存中的是第95、96、97、98、99行)，仍將產(chǎn)生100次缺頁中斷。后續(xù)循環(huán)，可依此類推。由此可知，程序二將產(chǎn)生2000次缺頁中斷。30．當數(shù)據(jù)(1)很少修改并且以隨機順序頻繁地訪問時(變長記錄文件)(2)頻繁地修改并且相對頻繁地訪問文件整體時(變長記錄文件)(3)頻繁順序地訪問文件元素(定長記錄文件)依次從訪問速度、存儲空間的使用和易于更新(添加／刪除／修改)這幾個方面考慮(訪問速度最優(yōu)先考慮，其次是存儲開銷，再次是易于更新)，為了達到最大效率，你將分別選擇()文件組織。A．Ⅰ、Ⅱ、ⅢB．Ⅱ、Ⅰ、ⅢC．Ⅱ、Ⅲ、ⅠD．Ⅰ、Ⅲ、Ⅱ正確答案：C解析：順序文件的主要優(yōu)點是順序存取時速度最快。文件為定長記錄文件時，還可以根據(jù)文件的起始地址及記錄長度進行隨機訪問。其缺點是文件存儲需要連續(xù)的存儲空間，會產(chǎn)生碎片，同時也不利于文件的動態(tài)擴充。索引文件結(jié)構(gòu)的優(yōu)點是可以進行隨機訪問(邏輯塊可以是變長的，順序文件不可)，也易于進行文件的增刪。其缺點是索引表的使用增加了存儲空間的開銷。索引順序文件的優(yōu)點是大大提高了順序存取的速度(彌補了變長記錄順序文件不便于直接存取的缺點)，缺點是索引表的存儲開銷(開銷小于索引文件結(jié)構(gòu))，隨機訪問速度比索引文件慢。對于(1)的兩個特點：隨機順序訪問，變長記錄文件。順序文件不利于變長記錄文件的隨機訪問，索引順序文件的隨機訪問速度又不如索引文件，故最佳應該是選擇索引文件。對于(2)的兩個特點是：訪問文件整體，變長記錄文件。順序文件不利于變長記錄文件的隨機訪問，且索引順序的開銷小于索引文件，故最佳應該是選擇索引順序文件。對于(3)的兩個特點是：隨機順序訪問，定長記錄文件。順序存取速度最快的是順序文件，且無額外存儲開銷，所以最佳應該選擇順序文件。綜上所述，最佳答案依次是索引文件、索引順序文件和順序文件。31．某文件系統(tǒng)采用多級索引的方式組織文件的數(shù)據(jù)存放，假定在文件的i_node中設有13個地址項，其中直接索引10項，一次間接索引項1項，二次間接索引項1項，三次間接索引項1項。數(shù)據(jù)塊大小為4KB，磁盤地址用4B表示，請問這個文件系統(tǒng)允許的最大文件長度約為()。A．1TB．2TC．3TD．4T正確答案：D解析：數(shù)據(jù)塊大小為4KB，而一個地址需用4B表示，所以一個數(shù)據(jù)塊可以放4KB／4B=1K的地址項，則可得一個一次間接索引項可對應1K個物理塊。一個二次間接索引項可對于1M個物理塊。以此類推，最大文件的物理塊個數(shù)可達(10+1K+1M+1G)個。最大文件大小即為(10+1K+1M+1G)×4KB=40KB+4MB+4GB+4TB，即這個文件系統(tǒng)允許的最大文件長度約為4TB。32．下列有關(guān)通道技術(shù)的敘述中，不正確的是()。Ⅰ．通道可視為一種軟件，其作用是提高了CPU的利用率Ⅱ．編制好的通道程序是存放在主存儲器中的Ⅲ．通道又稱I／O處理機，它用于實現(xiàn)CPU與I／O設備之間的信息傳輸Ⅳ．通道程序是由一系列通道指令組成的A．僅Ⅰ、ⅢB．僅Ⅰ、Ⅲ、ⅣC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅱ、Ⅲ正確答案：B解析：Ⅰ錯誤，通道可以獨立完成系統(tǒng)交付的輸入／輸出任務，通過執(zhí)行自身的通道指令完成主存與外設間的數(shù)據(jù)傳輸，故通道應該是一種硬件，或者稱為是一種專用計算機。Ⅱ正確，為了快速地得到通道指令，故通道指令應存放在主存。Ⅲ錯誤，通道是用于完成內(nèi)存與I／O設備的信息交換。Ⅳ錯誤，通道程序是由通道執(zhí)行的程序，是由一系列通道指令組成的。通道獨立于CPU，有自己的指令系統(tǒng)。該指令系統(tǒng)比較簡單，一般只有數(shù)據(jù)傳送指令、設備控制指令等。綜上分析，本題選B選項。33．通過IEEE802．3局域網(wǎng)傳送ASCII碼信息“Goodmoming!”，若封裝成一個MAC幀，則該幀的數(shù)據(jù)字段的有效字節(jié)為()，需要填充()個字節(jié)。A．12、34B．13、34C．13、33D．12、33正確答案：C解析：可以看出ASCII碼信息中一共有13個字符(注意空格)，每個字符用1個字節(jié)表示，故有效字節(jié)為13，由MAC幀的封裝規(guī)則，數(shù)據(jù)字段最少需要46個字節(jié)，不足的以填充字節(jié)補充。故需要填充的字節(jié)數(shù)為46-13=33。34．在異步通信中，每個字符包含1位起始位、7位數(shù)據(jù)位、1位奇偶位和2位終止位，若每秒傳送100個字符，采用4相位調(diào)制，則碼元速率為()。A．50波特／sB．500波特／sC．550波特／sD．1100波特／s正確答案：C解析：采用四相位調(diào)制，表示有四種波形，為了標識這四種波形，至少需要2位，也就是用2位來表示一個碼元。每個字符共11位，每秒100個字符，則比特率為1100bit／s，2位表示一個碼元，則碼元的速率為1100／2=550波特／s。35．假設有一個12位的海明碼(采用偶校驗編碼，且最多只有1位發(fā)生錯誤)，其十六進制的值為ACFH，請問原來的值是()。A．EFHB．AFHC．4FHD．BFH正確答案：B解析：先將編碼后的數(shù)據(jù)換成二進制形式。十六進制ACFH轉(zhuǎn)換為二進制為101011001111。其次，列出數(shù)據(jù)與位置的對應表，如表5-3所示。其中，第1、2、4、8位為校驗位，其余位為數(shù)據(jù)位。不妨設出錯位為e1、e2、e3、e4，怎么確定e1、e2、e3、e4與數(shù)據(jù)位的關(guān)系呢?M1下標中的1可以表示成0001，這里的0001分別對應e4、e3、e2、e1(倒過來看)，由于e1的值為1，所以M1只和e1有關(guān)。M3下標中的3可以表示成0011，所以M3和e1、e2有關(guān)；M7下標中的7可以表示成0111，所以M7和e1、e2、e3有關(guān)。其他以此類推，只需要將這些有關(guān)的用異或符號⊕連接起來即可，最后可得如下公式：e1=M1⊕M3⊕M5⊕M7⊕M9⊕M11=1⊕1⊕1⊕1⊕1⊕1=1e2=M2⊕M3⊕M6⊕M7⊕M10⊕M11=0⊕1⊕1⊕0⊕1⊕1=0e3=M4⊕M5⊕M6⊕M7⊕M12=0⊕1⊕1⊕0⊕1=1e4=M8⊕M9⊕M10⊕M11⊕M12=0⊕1⊕1⊕1⊕1=0按照e4、e3、e2、e1的排列方式得到的二進制序列為0101，恰好是二進制5，只需要把第五位取反即可，最后的正確信息為101001001111，然后刪除校驗位，即第1、2、4、8位，最后得到原始的數(shù)據(jù)位為10101111，轉(zhuǎn)換成十六進制為AFH。36．下列說法中，錯誤的是()。Ⅰ．0．0．0．0不能作為目的IP地址Ⅱ．100．255．255．255不能作為源IP地址Ⅲ．255．255．255．255可作為目的IP地址Ⅳ．127．0．0．1既可以作為目的IP地址，也可以作為源IP電址A．僅ⅠB．僅Ⅰ、Ⅲ、ⅣC．僅Ⅰ、ⅡD．僅Ⅱ、Ⅲ正確答案：A解析：Ⅰ：這個在高分筆記中多次強調(diào)，0．0．0．0是不能作為目的地址，但是0．0．0．0是可以作為默認目的地址的。例如在2009年真題中考過，當路由器向互聯(lián)網(wǎng)轉(zhuǎn)發(fā)IP分組時，到互聯(lián)網(wǎng)的路由其實就相當于一個默認路由，默認路由一般寫作0／0，即默認目的地址為0．0．0．0，子網(wǎng)掩碼也是0．0．0．0，故I正確。Ⅱ：100．255．255．255是A類廣播地址，不能作為源地址，故Ⅱ正確。Ⅲ：目的IP地址為255．255．255．255，表示一個主機想把分組發(fā)送給互聯(lián)網(wǎng)所有其他的主機，但是路由器會把這種類型的地址阻攔，使得這樣的廣播僅僅局限于本地局域網(wǎng)，255．255．255．255屬于E類地址，故Ⅲ正確。Ⅳ：127．0．0．1既可以作為目的IP地址，也可以作為源IP地址，故Ⅳ正確。37．設有下面4條路由：172．18．129．0／24、172．18．130．0／24、172．18．132．0／24和172．18．133．0／24，如果進行路由聚合，能覆蓋這4條路由的地址是()。A．172．18．128．0／21B．172．18．128．0／22C．172．18．130．0／22D．172．18．132．0／23正確答案：A解析：前兩個字節(jié)和最后一個字節(jié)不做比較了，只比較第三個字節(jié)即可。129→10000001130→10000010132→10000100133→10000101顯然，這4個數(shù)字只有前5位是完全相同的，因此匯聚后的網(wǎng)絡的第3個字節(jié)應該是10000000→128。匯聚后的網(wǎng)絡的掩碼中1的數(shù)量應該有8+8+5=21，因此答案是172．18．128．0／21。38．在下列地址中，屬于子網(wǎng)86．32．0．0／12的地址是()。Ⅰ．86．33．224．123Ⅱ．86．79．65．126Ⅲ．86．68．65．216A．僅ⅠB．僅Ⅰ、ⅡC．僅Ⅱ、ⅢD．僅Ⅲ正確答案：A解析：CIDR地址塊86．32．0．0／12的網(wǎng)絡前綴為12位，說明第二個字節(jié)的前4位在前綴中。第2個字節(jié)為32，轉(zhuǎn)換成二進制為0010000。選項給出的3個地址的第2個字節(jié)的前4位分別是0010、0100、0100，所以只有Ⅰ滿足。39．下列說法中，錯誤的是()。Ⅰ．TCP不支持廣播服務Ⅱ．如果用戶程序使用UDP協(xié)議，則應用層必須承擔數(shù)據(jù)傳輸?shù)目煽啃寓螅甎DP數(shù)據(jù)報首部包含UDP源端口、UDP目的端口、UDP數(shù)據(jù)報首部長度和校驗和Ⅳ．TCP協(xié)議采用的滑動窗口協(xié)議能夠解決擁塞控制問題A．僅Ⅲ、ⅣB．僅Ⅱ、ⅢC．僅Ⅰ、ⅢD．僅Ⅰ、Ⅲ、Ⅳ正確答案：A解析：Ⅰ：TCP提供的是一對一全雙工可靠的字節(jié)流服務，所以TCP并不支持廣播，故Ⅰ正確。Ⅱ：傳輸層協(xié)議主要包括：創(chuàng)建進程到進程的通信，提供流量控制機制。UDP協(xié)議使用端口號完成進程到進程的通信，但在收到用戶數(shù)據(jù)報時沒有流量控制的機制，也沒有確認，而只是提供有限的差錯控制，因此UDP是一個無連接、不可靠的協(xié)議。如果用戶應用程序使用UDP協(xié)議進行數(shù)據(jù)傳輸，必須在傳輸層的上層，即應用層提供可靠性方面的全部工作，故Ⅱ正確。Ⅲ：UDP數(shù)據(jù)報的首部格式包括UDP源端口號、UDP目的端口號、UDP報文長度(2字節(jié))和校驗和，不包括UDP數(shù)據(jù)報首部長度。因為UDP首部為固定8B，所以UDP首部長度字段可以省略，故Ⅲ錯誤。Ⅳ：擁塞控制是一個全局性的過程，涉及所有的主機、路由器，以及與降低網(wǎng)絡傳輸性能有關(guān)的所有因素。而滑動窗口協(xié)議僅僅是對于點對點的通信進行控制，即TCP協(xié)議采用的滑動窗口協(xié)議只能夠解決流量控制，故Ⅳ錯誤。40．一個萬維網(wǎng)網(wǎng)點有1千萬個頁面，平均每個頁面有10個鏈接。讀取一個頁面平均要100ms。問要檢索整個網(wǎng)點需要的時間最少為()。A．103sB．104sC．105sD．106s正確答案：D解析：因為一個萬維網(wǎng)網(wǎng)點有1千萬個頁面，讀取一個頁面平均要100ms，所以檢索整個網(wǎng)點需要的最少時間是100ms×10000000=106s，與每個頁面的鏈接數(shù)目無關(guān)。綜合應用題41-47小題，共70分。有如圖3-4所示的帶權(quán)有向圖G，試回答以下問題。41．給出圖G的鄰接表。正確答案：圖G的鄰接表如下：42．給出從頂點1出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。正確答案：從頂點1出發(fā)的深度優(yōu)先遍歷序列：1→2→3→8→4→5→7→6。從頂點1出發(fā)的廣度優(yōu)先遍歷序列：1→2→4→6→3→5→7→8。43．給出G的一個拓撲序列。正確答案：G的一個拓撲序列是：1→2→6→4→5→3→7→8。44．判斷該圖是否為強連通圖。正確答案：強連通圖是指圖中任何一個點到圖中其他所有點都有路徑。因為頂點8到其他點無路徑，所以該圖不是強連通圖。45．若用三元組存儲鄰接矩陣的數(shù)據(jù)，每個三元組占3個字節(jié)，求共需多大空間?若用鄰接矩陣存儲時每個元素占1個字節(jié)，試比較哪種存儲更省空間。正確答案：稀疏矩陣的壓縮一般采用三元組的方式。設二叉排序樹用二叉鏈表表示，結(jié)點結(jié)構(gòu)為(1child，data，rchild)，其中，data為整形，指針1child和rchild分別指向左右孩子。46．試寫出二叉鏈表的結(jié)點類型和指針類型的定義。正確答案：structNode{intdata；Node*ichild；Node*rchild；};47．給定一棵遞增有序的二叉排序樹(前序遍歷得遞增有序序列)，根指針為root，試寫出算法：將該二叉排序樹轉(zhuǎn)變?yōu)檫f減有序的二叉排序樹(前序遍歷得遞減有序序列)，返回根指針。正確答案：對于如圖3-16a所示的子樹，假設根節(jié)點P的左子樹和右子樹都已經(jīng)經(jīng)過調(diào)整而達到題目的要求，rm結(jié)點為右子樹前序遍歷的最后一個結(jié)點，由于P的左子樹1tree的元素都小于右子樹nree的任意元素，所以圖3-16a右邊所示的樹是滿足題目要求的。類似地，在沒有左子樹(右子樹)的情況下，按方案圖3-16b(或圖3-16c)調(diào)整該樹得到的結(jié)果是滿足要求的。我們可以按遞歸的方式，對于不同的情況，用圖3-16a、b、c所示三種規(guī)則對樹進行調(diào)整。代碼如下：Node*reverseTree(Node*p，Node*m){Node*，*r，*1m，*rm；if(p-＞rchild!=NULL)r=reverseTree(p-＞rchild，rm)；／／遞歸處理右子樹if(p-＞ichild!=NULL)1=reverseTree(p-＞ichild，im);／／遞歸處理左子樹Node*q=(Node*)malloc(sizeof(Node))；／／申請并初始化新結(jié)點qq-＞data=p-＞data；q-＞ichild=q-＞xchild=NULL；m=q；if(r!=NULL)／／若遞歸返回之后右子樹不空{(diào)if(1!=NULL)rm-＞ichild=1；／／若遞歸返回之后左子樹不空rm-＞rchild=q；／／結(jié)點q作為右孩子returnr；／／返回調(diào)整后的樹}if(1!=NULL)／／若遞歸返回之后左子樹不空{(diào)1m-＞1child=q；／／結(jié)點q作為左孩子return1；／／返回調(diào)整后的樹}returnq；}48．分析你所設計算法的時間復雜度。正確答案：時間復雜度分析：由于樹中的每個結(jié)點只被訪問一次，所以時間復雜度為O(n)。有5個中斷源D1、D2、D3、D4和D5，它們的中斷優(yōu)先級從高到低分別是1級、2級、3級、4級和5級。這些中斷源的中斷優(yōu)先級，正常情況下的中斷屏蔽碼和改變后的中斷屏蔽碼如表3-4所示。每個中斷源有5位中斷屏蔽碼，“0”表示該中斷開放，“1”表示該中斷被屏蔽。49．當使用正常的中斷屏蔽碼時，處理機響應各中斷源的中斷服務請求的順序是什么?實際的中斷處理順序是什么?正確答案：中斷優(yōu)先級包含響應優(yōu)先級和處理優(yōu)先級，沒有特殊指明即為響應優(yōu)先級，即處理機響應各中斷源的中斷服務請求的順序。因此，處理機響應各中斷源的中斷服務請求的順序為D1、D2、D3、D4、D5。實際的中斷處理順序即為處理優(yōu)先級，在沒有采用屏蔽技術(shù)時，響應優(yōu)先級就是處理優(yōu)先級。根據(jù)正常的中斷屏蔽碼，由于響應中斷源D1的中斷屏蔽碼為全1，即屏蔽了其他所有的中斷源，處理完D1之后，響應D2。由于其中斷屏蔽碼可知它只能被中斷源D1打斷，所以其處理優(yōu)先級為2，后面的以此類推。最后可得，實際的中斷處理順序為D1、D2、D3、D4、D5。50．當使用改變后的中斷屏蔽碼時，處理機響應各中斷源的中斷服務請求的順序是什么?實際的中斷處理順序是什么?正確答案：因為中斷屏蔽碼不改變中斷的響應優(yōu)先級，所以使用改變后的中斷屏蔽碼時，處理機響應各中斷源的中斷服務請求的順序仍為D1、D2、D3、D4、D5；處理優(yōu)先級的分析如下：首先處理機響應D1，它可以被D2打斷，因而轉(zhuǎn)去響應D2，D2又被D3打斷，轉(zhuǎn)去響應D3，D3又被D4打斷，而D5不能打斷D4，所以D4中斷服務程序可以全部執(zhí)行完。然后響應D5，D5后面沒有中斷源，所以此時可以執(zhí)行完D5的中斷服務程序，之后返回到D3未執(zhí)行完的中斷服務程序處，執(zhí)行完D3的中斷服務程序，然后再返回到D2未執(zhí)行完的中斷服務程序處，執(zhí)行完D2的中斷服務程序，最后執(zhí)行完D1的中斷服務程序，返回主程序。實際的中斷處理順序為D4、D5、D3、D2、D1。51．當D1、D2、D3、D4、D5這5個中斷源同時發(fā)出中斷請求時(采用改變后的中斷屏蔽碼)，試畫出處理機響應中斷源的中斷服務請求和實際運行中斷服務過程的示意圖。正確答案：根據(jù)(2)的分析可畫出處理機響應中斷源的中斷服務請求和實際運行中斷服務過程的不意圖，如圖3-17所示。52．假設從處理機響應中斷源的中斷服務請求開始，到運行中斷服務程序中第一次開中斷所用的時間為1個單位時間，處理機運行中斷服務程序的其他部分所用的時間為4個單位時間。當處理機在執(zhí)行主程序時，中斷源D3、D4和D5同時發(fā)出中斷服務請求，經(jīng)過3個單位時間后，中斷源D1和D2同時發(fā)出中斷服務請求。采用改變后的中斷屏蔽碼，畫出處理機響應各中斷源的中斷服務請求和實際運行中斷服務程序過程的示意圖。正確答案：首先響應D3，D3被D4打斷，響應D4并執(zhí)行完D4的中斷服務程序，之后相當于D1，D2，D5同時發(fā)出中斷請求，因為D4處理完后立即返回D3，所以此時中斷屏蔽寄存器的內(nèi)容為D3的中斷屏蔽碼，由于D3可以被D2打斷，所以響應D2，D2被D1打斷，響應D1，D1又被D5打斷，執(zhí)行完D5的中斷服務程序。然后再依次返回D1、D2、D3，最后返回主程序。由上面的分析可畫出處理機響應各中斷源的中斷服務請求和實際運行中斷服務程序過程的示意圖如圖3-18所示。這題目容易弄錯的一點是：當處理完D4之后以為按響應優(yōu)先級去響應D1，要注意的是D4處理完后立即返回D3，此時中斷屏蔽寄存器的內(nèi)容為D3的中斷屏蔽碼，而D3只能被D2打斷，因此轉(zhuǎn)去響應D2。某16位機器所使用的指令格式和尋址方式如圖3-5所示，該機有兩個20位基址寄存器，4個16位變址寄存器，16個16位通用寄存器。指令匯編格式中的S(源)、D(目標)都是通用寄存器，M是主存的一個單元。3種指令的操作碼分別是MOV(OP)=(A)H，STA(OP)=(1B)H，LDA(OP)=(3C)H。MOV是傳送指令，STA為寫數(shù)指令，LDA為讀數(shù)指令。53．試分析3種指令的指令格式和尋址方式特點。正確答案：第一種指令是單字長二地址指令，屬于RR型。第二種指令是雙字長二地址指令，屬于RS型，其中S采用基址尋址或變址尋址，R由源寄存器決定。第三種也是雙字長二地址指令，屬于RS型，其中R由目標寄存器決定，S由20位地址(直接尋址)決定。54．處理機完成哪一種操作所花時間最短?哪一種操作所花時間最長?第二種指令的執(zhí)行時間有時會等于第三種指令的執(zhí)行時間嗎?正確答案：處理器完成第一種指令所花的時間最短，因為是RR型指令，不需要訪問存儲器。第二種指令所花的時間最長，因為是RS型指令，需要訪問存儲器，同時要進行尋址方式的變換運算(基址或變址)，這也要時間。第二種指令的執(zhí)行時間不會等于第三種指令，因為第三種指令雖也訪問存儲器，但節(jié)省了求有效地址運算的時間。55．下列情況中，每個十六進制指令字分別代表什么操作?并且描述此指令的作用。其中有些編碼不正確，如何改正才能成為合法指令?①FOF1H、3CD2H②2856H③6FD6H正確答案：根據(jù)已知條件：MOV(0P)=001010，STA(OP)=011011，LDA(OP)=111100，將指令的十六進制格式轉(zhuǎn)換成二進制代碼且比較后可知：1)(FOF1)H(3CD2)H前面6位為111100，所以該指令代表LDA指令。完整的二進制代碼為：11110000111100010011110011010010，前面111100代表操作碼，00代表橫線的內(nèi)容。1111代表目標寄存器，含義是把主存(13CD2)H地址單元的內(nèi)容取至115號寄存器。2)(2856)H前面6位為001010，所以該指令代表MOV指令。完整的二進制代碼為：0010100001010110，其中后面的0101和0110分表代表目標寄存器和源寄存器，含義是把6號源寄存器的內(nèi)容傳送至5號目標寄存器。3)首先因為(6FD6)H是單字長指令，所以肯定屬于MOV指令，但是編碼錯誤。6FD6的二進制為0110111111010110，可以將011011改為001010，11改為00，00代表橫線的內(nèi)容。所以最后可糾正為(28D6)H，含義是把6號源寄存器的內(nèi)容傳送至13號目標寄存器。假設有一個進程擁有兩個線程(編號為0和1)需要去訪問同一個共享資源，為了避免競爭狀態(tài)的問題，必須實現(xiàn)一種互斥機制，使得在任何時候只能有一個線程在訪問這個資源。假設有如下的一段代碼：intflag[2]；／*flag數(shù)組，初始化為FALSE*／Enter_Critica1_Section(intmy_thread_id)，intother_thread_id){while(flag[other_thread_id]==TRUE)；／*空循環(huán)語句*／flag[my_thread_id]=TRUE；}Exit_Critica1_Section(intmy_thread_id)，intother_thread_id){flag[my_thread_id]=FALSE；}當一個線程想要訪問臨界資源時，就調(diào)用上述的這兩個函數(shù)。比如，線程0的代碼可能是這樣的：Enter_Critica1_Section(0，1)；……使用這個資源……Exit_Critica1_Section(0，1)；……做其他的事情……試問：5