計算機專業(yè)（基礎(chǔ)綜合）模擬試卷112

一、單選題（本題共40題，每題1.0分，共40分。）

1、若循環(huán)隊列以數(shù)組Q|0..m?1]作為其存儲結(jié)構(gòu)，變量rear表示循環(huán)隊列中的隊

尾元素的實際位置，其移動按rear=（rear+1）MODm進行，變量length表示當(dāng)前循

環(huán)隊列中的元素個數(shù)，則循環(huán)隊列的隊首元素的實際位置是（）。

A、rear-length

B、（rear—Iength+m）MODm

C、（1+rcar+m—lcngth）MODm

D、（rear+length-1）MODm

標(biāo)準答案：C

知識點解析：考查循環(huán)隊列的性質(zhì)。區(qū)分循環(huán)隊列隊空還是隊滿有3種方法：①

犧牲一個存儲單元；②增設(shè)表示元素個數(shù)的變量；③設(shè)標(biāo)記法。這里用的是第二

種方法.因為元素移動按rear=（rear+l）MODm進行?，即若隊列沒有循環(huán)時（即隊列

沒有越過數(shù)組的頭尾），隊頭應(yīng)該在隊尾的左側(cè)，即數(shù)組下標(biāo)小的位置，詳細來算

應(yīng)當(dāng)是數(shù)組下標(biāo)為rear—（length—1）的位置（因為Q[rear]本身占用一個位置，所以減

去的長度不是length,而是length—1）,然而光是這樣若隊列越過了數(shù)組頭尾，那

么會導(dǎo)致算出來的隊頭為負數(shù)，所以這里可以給這個式子加上一個數(shù)組長度再取

模，即（rear—le呷h.l+m）MODm,這樣當(dāng)隊列沒有越過數(shù)組邊界時，由于取模的

存在，能保證結(jié)果的正確，而當(dāng)隊列越過了數(shù)組邊界時，由于加了m所以結(jié)果正

確。

2、若一個棧以向量V|存儲，初始棧頂指針lop為n+1,則x進棧的正確操作

是（）。

A、top=top+1；V[top]=x

B、V[top]=x；top=top+1

C^top=top-1；V[top]=x

D、V[top]=x；top=top-1

標(biāo)準答套C

知識點露析：考查棧的操作。初始時棧頂指針top=n+l,所以該棧應(yīng)該是從高地址

向低地址生長。.且n+1不在向量的地址范圍，因此應(yīng)該先將top減I,再存儲。即

選C。注意：對于順序存儲的棧（對于隊列也類似），如果存儲的定義不同，則出入

棧的操作也不相同（并不是固定的），這要看棧頂指針指向的是棧頂元素，還是戌頂

元素的下一位置。

3、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和from的值分別為。和

3,其移動按數(shù)組下標(biāo)增大的方向進行（當(dāng)下標(biāo)不等于m—l時）。當(dāng)從隊列中刪除

一個元素，再加入兩個元素后，rear和front的值分別為（）。

A、1和5

B、2和4

C、4和2

D、5和1

標(biāo)準答案：B

知識點解析：考查循環(huán)隊列的插入和刪除，頭、尾指針的變化。隊列的特點是先進

先出，隊頭刪除元素，隊尾插入元素。刪除一個元素，隊頭指針

front=（front+1）mod6=4,隊尾指針不變。插入兩個元素,隊尾指針

reai-（rear+2）mod6=2,隊頭指針不變。所以rear和front分別為2和4,選B。

4、若一棵二叉樹中有24個葉結(jié)點，有28個僅有一個孩子的結(jié)點，則該二叉樹的

總結(jié)點數(shù)為（）。

A、70

B、73

C、75

D、77

標(biāo)準答案：C

知識點解析：考察二義樹結(jié)點數(shù)量之間關(guān)系的性質(zhì)。按照二義樹結(jié)點數(shù)的關(guān)系有

NO=N2+1,而題中有24個葉子節(jié)點即為有24個度為。的結(jié)點，有28個僅有一個

孩子的結(jié)點即為有28個度為1的結(jié)點，按照公式N（）=N2+1,即N2=No—1=24—

1=23,所以樹的結(jié)點的總數(shù)為NO+NI+N2=24+28+23=75,答案選C。

5、某二叉樹結(jié)點的中序序列為BDAECF,后序序列為DBEFCA,則該二叉樹對應(yīng)

的森林包括（）棵樹。

A、1

B、2

C、3

D、4

標(biāo)準答案：C

知識點解析：考查由遍歷序列確定二叉樹、森林與二叉樹的轉(zhuǎn)換。根據(jù)后序序列，

A是二義樹的根結(jié)點。根據(jù)中序遍歷序列，則二叉樹的形態(tài)一定如下圖左所示。對

于A的左子樹，由后序序列可知，因為B比D后被訪問，因此，B必為D的父結(jié)

點，又由中序序列可知，D是B的右兒子。對于A的右子樹，同理可確定結(jié)點

E、C、F的關(guān)系。此二叉樹的形態(tài)如下圖右所示。

AA

B、D

再根據(jù)二叉樹與森林的對

應(yīng)關(guān)系。森林中樹的棵數(shù)即為其對應(yīng)二叉樹（向右上旋轉(zhuǎn)45。后）中根結(jié)點A及其“右

兄弟”數(shù)?？芍松种杏?棵樹，根結(jié)點分別為A、C和F。

6、在具有刀個頂點的圖G中，若最小生成樹不唯一，貝以）。

A、G的邊數(shù)一定大于n-I

B、G的權(quán)值最小的邊一定有多條

C、G的最小生成樹代價不一定相等

D、上述選項都不對

標(biāo)準答案：A

知識點解析：G的最小生成樹的邊數(shù)為n-l,若最小生成樹不唯一，則G的邊數(shù)

一定大于，n—1,A正確。在G中找到與最小生成樹T中某條邊el權(quán)值相等的邊

e2,加入最小生成樹中，則會產(chǎn)生一個環(huán)，就可以用e2來代替el,形成一個新的

最小生成樹ET=T—el+e2,這就使最小生成樹不唯一，而邊的權(quán)值在這里是任意

的，并不是最小的，B錯誤。最小生成樹的樹形可能不唯一，但代價肯定是相等且

是最小的，C錯誤。

7、給定結(jié)點個數(shù)n,在下面二叉樹中，葉結(jié)點個數(shù)不能確定的是（）。

A、滿二叉樹

B、完全二叉樹

C、哈夫曼樹

D、二叉排序樹

標(biāo)準答案：D

知識點解析：考查幾種特殊二叉樹的性質(zhì)。對于A,滿二叉樹，設(shè)層數(shù)為h,則

2h—l=n,求出h,葉結(jié)點都在最后一層上，即葉結(jié)點數(shù)為2卜一I對于B,在完全

二義樹中，度為1的結(jié)點數(shù)為?；?,N=2No+N|+l,則No=r（n+l）/2jo對于

c,哈夫蛇樹只有度數(shù)為2和0的結(jié)點,NO=N2+1,No+N2=n,即No=（n+1）/2可得

葉結(jié)點個數(shù)。對于D,則無法求出葉結(jié)點個數(shù)。

8、在關(guān)鍵字隨機分布的情況下，用二分查找樹的方法進行查找，其平均查找長度

與（）量級相當(dāng)。

A、順序查找

B、折半查找

C、分塊查找

D、散列查找

標(biāo)準答案：B

知識點解析：考查各種查找方法的特點。順序查找平均查找長度的數(shù)量級是

O(n)；折半查找平均查找長度的數(shù)量級是O(lOgzn)。分塊查找平均查找長度的數(shù)量

級是O(log|K+n/K)o散列查找的平均查找長度跟裝填因子和采用的沖突解決方法

有關(guān)。二分查找樹在最壞情況下的平均查找長度為O(n),但在關(guān)鍵字隨機分布的

情況下，用二分查找樹的方法進行查找的平均查找長度的數(shù)量級為O(login)o

9、下列可用于表示有向圖的存儲結(jié)構(gòu)有()。I.鄰接矩陣H.鄰接表HI.十字

鏈表W.鄰接多重表

A、I和U

B、II和W

C、I、II和m

D、I、II和IV

標(biāo)準答案：C

知識點解析：考查圖的存儲結(jié)構(gòu)。鄰接矩陣和鄰接表既能存儲有向圖，也能存儲無

向圖，鄰接多重表只能存儲有向圖，十字鏈表只能存儲無向圖，I、II和ni符合題

意，選Co

10、從二叉樹的任一結(jié)點出發(fā)到根的路徑上，所經(jīng)過的結(jié)點序列必按其關(guān)鍵字降序

排列的是()。

A、二叉排序樹

B、大頂堆

C、小頂堆

D、平衡二叉樹

標(biāo)準答案：C

知識點解析：考查二叉徘序樹、大頂堆、小頂堆、平衡二叉樹的性質(zhì)。二叉排序樹

中的任一結(jié)點x大于其左孩子，小于其右孩子，從二叉排序樹的任一結(jié)點出發(fā)到根

結(jié)點，只要路徑中存在左子樹關(guān)系則必不滿足題中降序的條件。同理，平衡二叉樹

也不滿足。小頂堆中的任一結(jié)點x均小于左右孩子，因此從任一結(jié)點到根的路徑上

的結(jié)點序列必然是降序的。大頂堆剛好相反。注意：堆存儲在一個連續(xù)的數(shù)組單

元中，它是一棵完全二叉樹。二叉排序樹和小頂堆的共同部分。當(dāng)且僅有一個左

孩子時。

11、設(shè)待排序元素序列所有元素的關(guān)鍵字都相等，則下列排序方法中排序速度最慢

的是()。

A、直接插入排序

B、冒泡排序

C、簡單選擇排序

D、基數(shù)排序

標(biāo)準答案：C

知識點解析：當(dāng)所有待排序元素的關(guān)鍵字都相等時，直接插入排序的關(guān)鍵字比較次

數(shù)為n—1,元素移動次數(shù)為0；冒泡排序的關(guān)鍵字比較次數(shù)為n—1,元素移動次

數(shù)為0;簡單選擇排序的關(guān)鍵字比較次數(shù)為n(n—1)/2(進行n趟，第i趟比較n-

i+1個元素），元素移動次數(shù)為0；基數(shù)排序的關(guān)鍵字比較次數(shù)為n*d（d為關(guān)鍵字位

數(shù)），元素移動次數(shù)為0,故排序速度最慢的是簡單選擇排序。

12、以下有關(guān)計算機運算速度衡量指標(biāo)的描述中，正確的是（）。

A、MIPS大的機器一定MIPS小的機器快

B、CPU的主頻越高速度越快

C、執(zhí)行不同的程序，測得的同一臺計算機的CPI可能不同

D、CPU執(zhí)行程序的時間就是觀測到用戶程序的執(zhí)行時間

標(biāo)準答案：C

知識點解析：本題考查計算機的性能指標(biāo)。整機的速度是由多個指標(biāo)綜合衡量的，

比如整個CPU的架構(gòu)、指令集、高速緩沖等，某個指標(biāo)的高低并不能完全決定機

器的速度，故A、B錯誤。在多道程序的操作系統(tǒng)下，一個用戶程序執(zhí)行過程中，

可能會插入運行其他程序，所以觀測到用戶程序的執(zhí)行時間要大于其真正的CPU

執(zhí)行時間，故D錯誤。在不同的程序中，各類指令所占的比例有可能不同，而不

同類型的指令執(zhí)行時間也是不一樣的，比如訪存指令執(zhí)行時間一般會比運算指令花

費更多的時間，而就算是運算指令本身，乘法指令也會比加法指令花費更多的時

間，因此測得的CPI有可能不同，C正確。

13、已知小寫英文字母“a”的ASCH碼值為61H,現(xiàn)字母“g”被存放在某個存儲單元

中，若采用偶校驗（假設(shè)最高位作為校驗位），則該存儲單元中存放的十六進制數(shù)是

（）o

A、66H

B、E6H

C、67H

D、E7H

標(biāo)準答案：D

知識點解析：本題考查ASCII碼和奇偶校驗碼。英文字母的ASCII碼是順序相連

的C偶校驗就是增加一個校驗位，便得整個碼串中;T'的個數(shù)為偶數(shù)C因為“屋的

ASCII碼為61H,而“g”是第7個字母，所以“g”的ASCH碼應(yīng)為

6IH+6H=67H=1100111Bo標(biāo)準ASCH碼為7位，在7位數(shù)前增加1位校驗位?，F(xiàn)

“g”的ASCII碼中1的個數(shù)為5,根據(jù)偶校驗的原理，整個碼串為

111001HB=E7Ho

14、設(shè)浮點數(shù)的基數(shù)為4,尾數(shù)用原碼表示，則以下（）是規(guī)格化的數(shù)。

A、1.001101

B、0.001101

C、1.011011

D、0.000010

標(biāo)準答案：C

知識點解析：考查規(guī)格叱形式。規(guī)格化規(guī)定尾數(shù)的絕對值應(yīng)大于或等于1/R（R為

基數(shù)），并小于或等于1，當(dāng)基數(shù)為4時，尾數(shù)絕對值應(yīng)大于等于1/4,尾數(shù)用原

碼表示，則小數(shù)點后面兩位不全為0即為規(guī)格化數(shù)。注意：對于基數(shù)為4的原碼

尾數(shù)，每右（或左）移2位，階碼加（或減）1。

15、設(shè)某按字節(jié)編址的計算機已配有00000H”?07FFFH的ROM區(qū)，MAR.為20

位，現(xiàn)再用16Kx8位的RAM芯片構(gòu)成剩下的RAM區(qū)08000H?FFFFFH,則需要

這樣的RAM芯片（）片。

A、61

B、62

C、63

D、64

標(biāo)準答案：B

知識點解析：本題考查存儲芯片的擴展。RAM區(qū)的地址范圍為：000010000C00

00000000—11111111111111111111,由此可知RAM區(qū)的大小為31X32KB,

（31x32KB）/16KB=62o

16、在Cache和主存構(gòu)成的兩級存儲體系中，Cache的存取時間是100ns,主存的

存取時間是1000ns,如果希望有效（平均）存取時間不超過Cache存取時間15%,

則Cache的命中率至少應(yīng)為（）。（設(shè)Cache和主存不能同時訪問）。

A,90%

B、98%

C、95%

D、99%

標(biāo)準答案：D

知識點解析：本題考查Cache命中率的相關(guān)計算。設(shè)Cache命中率為a,則

（1000+100）（1—a）+100a<l15,解得Q0.985,故至少為99%。注意：雖然也可以

采用同時訪問Cache和主存的方式，此時不命中的訪問時間為1000ns,但若題設(shè)

中沒有說明，默認Cache不命中的時間為訪問Cache和主存的時間之和。

17、為了縮短指令中某個地址段的位數(shù)，有效的方法是采取（）。

A、立即尋址

B、變址尋址

C、間接尋址

D、寄存器尋址

標(biāo)準答案：D

知識點解析?：考查各種尋址方式的特點。一般CPL-中的寄存器的數(shù)量都不會太

多，可以用很短的編碼就可以指定寄存器，寄存器尋址需要的地址段位數(shù)為

log2（通用寄存器個數(shù)），采用寄存器尋址可以減少指令的地址段的位數(shù)。立即尋

址，操作數(shù)直接保存在指令中，可能會增長地址段的位數(shù)，若地址段個數(shù)太小，則

操作數(shù)表示的范圍會很??；變址尋址，EA二變址寄存器IX的內(nèi)容+形式地址A,A

與主存尋址空間有關(guān)；間接尋址中存放的仍然是一個主存地址。

18、下面關(guān)于RISC技術(shù)的描述中，正確的是（）。

A、采用RISC技術(shù)后，計算機的體系結(jié)構(gòu)又恢復(fù)到早期的比較簡單的情況

B、為了實現(xiàn)兼容，新設(shè)計的RISC是從原來的CISC系統(tǒng)的指令系統(tǒng)中挑選一部

分實現(xiàn)的

C、RISC的主要目標(biāo)是減少指令數(shù)

D、RISC設(shè)有乘、除法指令和浮點運算指令，只是很少使用

標(biāo)準答案：C

知識點解析：考查RISC的特點。選項A明顯錯誤，RISC只是CPIJ的結(jié)構(gòu)發(fā)生變

化，基本不會影響整個計算機的結(jié)構(gòu)，并且即使是采用了RISC技術(shù)的CPU,其架

構(gòu)也不可能像早期一樣簡單。RISC選擇那些常用的、寄存器型的指令，并不是為

了兼容CISC,RISC也不可能與CISC兼容，B錯誤。RISC中復(fù)雜指令是通過簡單

指令的組合來實現(xiàn)的，D錯誤。

19、流水CPU是由一系列叫做“段”的處理部件組成的。當(dāng)流水穩(wěn)定后的，和具備

m個并行部件的CPU相比，一個m段流水CPU（）。

A、具備同等水平的吞吐能力

B、不具備同等能力的吞吐能力

C、吞吐能力小于前者的吞吐能力

D、吞吐能力大于后者的吞吐能力

標(biāo)準答案：A

知識點解析：考查流水線的性能分析。當(dāng)m段流水穩(wěn)定后，每個時鐘周期流出一

條指令，平均每個指令周期流出m條指令，與具備m個并行部件的CPU的吞吐能

力相等。

20、在做手術(shù)過程中，醫(yī)生將手伸出，等護士將手術(shù)刀遞上，待醫(yī)生握緊后，護士

才松手。如果把醫(yī)生和于士看作兩個通信模塊，上述一系列動作相當(dāng)于（）。

A、同步通信

B、異步通信的全互鎖方式

「、異步通信的半互鎖方式

D、異步通信的不互鎖方式

標(biāo)準答案：B

知識點解析：本題考查總線的定時方式。由題意可知，醫(yī)生是主模塊，護士是從模

塊。醫(yī)生伸出手后（即主模塊發(fā)出請求信號），等待護士將手術(shù)刀遞上（主模塊等待從

模塊的回答信號），護士也必須等待醫(yī)生握緊后才松開收（從模塊等待主模塊的回答

信號），以上整個流程就是異步通信的全互鎖方式。

21、當(dāng)有中斷源發(fā)出請求時，CPU可執(zhí)行相應(yīng)的中斷服務(wù)程序，以下可以提出中

斷的是（）。I.外部事件口.CacheDI.虛擬存儲器失效W.浮點運算下溢

V.浮點運算上溢

A、I、in和w

B、I和V

c、I、II和m

D、I、HI和v

標(biāo)準答案：D

知識點解析：本題考查中斷請求。外部事件如按鍵以退出運行的程序等，屬于外中

斷，I正確。Cache完全是由硬件實現(xiàn)的，不會涉及到中斷層面，II錯誤。虛擬存

儲器失效如缺頁等，會發(fā)出缺頁中斷，屬于內(nèi)中斷，DI正確。浮點運算下溢，直接

當(dāng)做機器零處理，而不會引發(fā)中斷，W錯誤。浮點數(shù)上溢，表示超過了浮點數(shù)的表

示范圍，屬于內(nèi)中斷，V正確。注意：中斷請求是指中斷源向CPU發(fā)送中斷請求

信號，分為外中斷和內(nèi)中斷。外中斷指來自處理器和內(nèi)存外部的中斷，如I/O設(shè)

備發(fā)出的、外部事件等；內(nèi)中斷指在處理器和內(nèi)存內(nèi)部產(chǎn)生的中斷。

22、在DMA方式下，數(shù)據(jù)從內(nèi)存?zhèn)魉偷酵庠O(shè)經(jīng)過的路徑是（）。

A、內(nèi)存一數(shù)據(jù)總線一外設(shè)

B、內(nèi)存一數(shù)據(jù)總線—DMA—外設(shè)

C、內(nèi)存-CPU-數(shù)據(jù)總線—外設(shè)

D、外設(shè)一內(nèi)存

標(biāo)準答案：B

知識點解析：本題考查DMA的數(shù)據(jù)傳送方式。在DMA方式下，數(shù)據(jù)傳送不需要

經(jīng)過CPU,但需要經(jīng)過DMA控制器中的數(shù)據(jù)緩沖寄存器。DMA控制器中的數(shù)據(jù)

緩沖寄存器用來暫存每次傳送的數(shù)據(jù)。輸入時，數(shù)據(jù)由外設(shè)（如磁盤）先送往數(shù)據(jù)緩

沖需存器，再通過數(shù)據(jù)總線送到主存。反之，輸出時.，數(shù)據(jù)由主存通過數(shù)據(jù)總線送

到數(shù)據(jù)緩沖寄存器，然后再送到外設(shè)。

23、當(dāng)中斷發(fā)生后，進入中斷處理的程序?qū)儆冢ǎ?/p>

A、用戶程序

B、可能是用戶程序，也可能是OS程序

C、OS程序

D、單獨的程序，即不是用戶程序也不是OS程序

標(biāo)準答案：C

知識點解析，本題考查中斷的處理過程和作用.當(dāng)中斷或異常發(fā)生時.通過硬件實

現(xiàn)將運行在用戶態(tài)的CPU立即轉(zhuǎn)入到核心態(tài)。中斷發(fā)生時，若被中斷的是用戶程

序，系統(tǒng)將從目態(tài)轉(zhuǎn)入管態(tài)，在管態(tài)下進行中斷的處理；若被中斷的是低級中斷，

則仍保留在管態(tài)，而用戶程序只能在目態(tài)下運行，因此進入中斷處理的程序只能是

OS程序。這里需要注意的是，中斷程序本身有可能是用戶程序，但是進入中斷的

處理程序一定是OS程序。

24、支持多道程序設(shè)計的操作系統(tǒng)在運行過程中，會不斷選擇新進程來運行，共享

CPU資源，但是下面哪個不是操作系統(tǒng)選擇新進程的直接原因，（）。

A、運行進程的時間片用完

B、運行進程出錯

C、運行進程等待某個事件的發(fā)生

D、有新的進程被創(chuàng)建進入就緒隊列

標(biāo)準答案：D

知識點解析：本題考查進程調(diào)度的時機。讀者應(yīng)掌握不能進行進程調(diào)度與切換的情

況(處理中斷的過程、訪問臨界區(qū)、原子操作)及應(yīng)該進行進程調(diào)度與切換的情況。

運行著的進程由于時間片用完、運行結(jié)束、需要等待事件的發(fā)生(如等待鍵盤響

應(yīng))、出錯、自我阻塞等均可以激活調(diào)度程序進行重新調(diào)度，選擇一個新的就緒進

程投入運行。新進程加入到就緒隊列不是引起調(diào)度的直接原因，當(dāng)CPU正在運行

其他進程時，該進程仍需等待。即使在采用高優(yōu)先級優(yōu)先調(diào)度算法的系統(tǒng)中，一個

最高優(yōu)先級的進程進入就緒隊列，仍需要考慮是否允許搶占，當(dāng)不允許搶占時仍需

等待。

25、為實現(xiàn)人機交互作用應(yīng)采用的調(diào)度算法是()。

A、短作業(yè)優(yōu)先調(diào)度

B、時間片輪轉(zhuǎn)法

C、基于優(yōu)先權(quán)的剝奪調(diào)度算法

D、高響應(yīng)比優(yōu)先調(diào)度

標(biāo)準答案：B

知識點解析：本題考查調(diào)度算法的性質(zhì)。實現(xiàn)人機交互作用的系統(tǒng)中最主要的要求

是各用戶作業(yè)的響應(yīng)時間短。采用時間片輪轉(zhuǎn)法調(diào)度能夠使多個終端能夠得到系統(tǒng)

的及時響應(yīng)。

26、下面是一個并發(fā)進程的程序代碼，正確的說法是()。semaphorex1=x2=y=l；

intci=c2=0；Pl(){P2()(P(xl)；P(x2)；if(++cl==l)P(y),if(++c2==l)P(y)；

V(xl)；V(x2)；computedA),computer(B)；P(xl)；P(x2)；if(------cl==0)V(y)

A、進程不會死鎖，也不會饑餓

B、進程不會死鎖，但是會饑餓

C、進程會死鎖，但是不會饑餓

D、進程會死鎖，也會饑餓

標(biāo)準答案：B

知識點解析：本題考查PV操作與死鎖以及饑餓的關(guān)系°仔細考察程序代碼,我們

似曾相識，可以看出是一個擴展的單行線問題。也就是說，某單行線只允許單方向

的車輛通過，在單行線的入口設(shè)置信號量v,在告示牌上顯示某一時刻各方向來車

的數(shù)量cl和c2,要修改告示牌上的車輛數(shù)量必須互斥進行，為此設(shè)置信號量xl

和x2。若某方向的車輛需要通過時，首先要將該方向來車數(shù)量cl或c2增加1,并

查看自己是否是第一個進入單行線的車輛，若是，則獲取單行線的信號量v,并進

入單行線。通過此路段以后出單行線時，將該方向的車輛數(shù)cl或c2減1(當(dāng)然是利

用xl或x2來互斥修改)，并查看自己是否是最后一輛車，若是釋放單行線的互斥

量y,否則保留信號量y,讓后繼車輛繼續(xù)通過。雙方的操作如出一轍。考慮出現(xiàn)

一個極端情況，即當(dāng)某方向的車輛首先占據(jù)單行線并后來者絡(luò)繹不絕時，另一個方

向的車輛就再沒有機會通過該單行線了。而這種現(xiàn)象是由于算法本身的缺陷造成

的，不屬于因為特殊序列造成的饑餓，所以它是真正的饑餓現(xiàn)象。由于有信號量的

控制，死鎖的可能性沒有了(即雙方同時進入單行線，在中間相遇，造成雙方均無

法通過的情景)。

27、若存儲單元長度為刀，存放在該存儲單元的程序長度為m,則剩下長度為n-

m的空間稱為該單元的內(nèi)部碎片。下面存儲分配方法中，哪種存在內(nèi)部碎片（）。

I.固定式分區(qū)n.動態(tài)分區(qū)HI.頁式管理W.段式管理V.段頁式管理

VI.請求段式管理

A、I和口

B、I、B和V

C、W、V和VI

D、D和V

標(biāo)準答案：B

知識點解析：本題考查各存儲分配方法的特點。固定分區(qū)存在內(nèi)部碎片，當(dāng)程序小

于固定分區(qū)大小時，也占用了一個完整的內(nèi)存分區(qū)空間，導(dǎo)致分區(qū)內(nèi)部有空間浪

費，這種現(xiàn)象稱內(nèi)部碎片。凡涉及到頁的存儲分配管理，每個頁的長度都一樣（對

應(yīng)固定），所以會產(chǎn)生內(nèi)部碎片，雖然頁的碎片比較小，每個進程平均產(chǎn)生半個塊

大小的內(nèi)部碎片。段式管理中每個段的長度都不一樣（對應(yīng)不固定），所以只會產(chǎn)生

外部碎片。段頁式管理先被分為若干個邏輯段，然后再將每個段分為若干個固定的

頁，所以其仍然是固定分配，會產(chǎn)生內(nèi)部碎片。

28、下列關(guān)于頁式存儲的說法中，正確的是（）。I.在頁式存儲管理中，若無

TLB和Cache,則每訪問一條數(shù)據(jù)都至少需要訪問2次內(nèi)存口.頁式存儲管理不

會產(chǎn)生內(nèi)部碎片m.頁式存儲管理當(dāng)中的頁面是莊戶可以感知的W.頁式存儲方

式可以采用靜態(tài)重定位

A、I、II和IV

B、I和W

C、I

D、I和m

標(biāo)準答案：c

知識點露析：本題考查頁式存儲的相關(guān)知識。關(guān)閉了TLB之后，每訪問一條數(shù)據(jù)

都要先訪問頁表（內(nèi)存中），得到物理地址后，再訪問一次內(nèi)存進行相應(yīng)操作（若是多

級頁表會產(chǎn)生更多次訪存），I正確。凡是分區(qū)固定的都會產(chǎn)生內(nèi)部碎片，而無外

部碎片，II錯誤。頁式存儲管理不僅對于用戶是透明的，對于程序員都是透明的，

in錯誤。靜態(tài)重定位是在程序運行之前由裝配程序完成的，頁式存儲不是連續(xù)的，

而且頁式存儲管理方案在運行過程中可能改變程序位置，分配的時候會把相鄰邏輯

地址映射到不同的物理地址，這需要動態(tài)重定位的支持，w錯誤。注意：頁式存

儲是內(nèi)存管理部分最重要的知識點之一，對于頁式存儲，無論選擇、分析還是計算

題，都比較常見。不僅要知道簡單的原理和優(yōu)缺點，更要深入理解頁式存儲的各方

面特點和具體操作處理過程。

29、下列關(guān)于文件系統(tǒng)的說法中，錯誤的是（）。I.一個文件在同一系統(tǒng)中、不

同的存儲介質(zhì)上的拷貝，應(yīng)采用同一種物理結(jié)構(gòu)口.對一個文件的訪問，常由用

戶訪問權(quán)限和用戶優(yōu)先級共同限制W.文件系統(tǒng)采用樹型目錄結(jié)構(gòu)后，對于不同

用戶的文件，其文件名應(yīng)該不同W.為防止系統(tǒng)故障造成系統(tǒng)內(nèi)文件受損，常采

用存取控制矩陣方法保十文件

A、i、ii和m

B、i、m

c、i、m、w

D、i、n、in和w

標(biāo)準答案：D

知識點解析：本題考查文件系統(tǒng)的多個知識點。建議采用排除法求解。文件在磁盤

上的存放通常采用連續(xù)方式，但在內(nèi)存上通常不會采用連續(xù)方式，I錯誤。對文件

的訪問控制，通常由用戶訪問權(quán)限和文件屬性共同限制，II錯誤。在樹型目錄結(jié)構(gòu)

中，對于不同用戶的文件，文件名可以相同也可以不同，m錯誤。存取控制矩陣方

法通常用于多個用戶之間的存取權(quán)限保護，w錯誤。

30、下列哪些存儲分配方案可能使系統(tǒng)抖動，（）。I.動態(tài)分區(qū)分配n.簡虺頁

式m.虛擬頁式w.簡單段頁式v.簡單段式VI.虛擬段式

A、I、口和v

B、in和w

c、只有迎

D、in和VI

標(biāo)準答案：D

知識點解析：本題考查系統(tǒng)抖動。要通過對存儲分配的理解來推斷系統(tǒng)是否會發(fā)生

抖動，所以本題同時也需要了解不同的存儲分配方案的內(nèi)容。抖動現(xiàn)象是指剛剛被

換出的頁很快又要被訪問，為此，又要換出其他頁，而該頁又很快被訪問，如此頻

繁地置換頁面，以致大部分時間都花在頁面置換上。對換的信息量過大，內(nèi)存容量

不足不是引起系統(tǒng)抖動現(xiàn)象的原因，而選擇的置換算法不當(dāng)才是引起抖動的根本原

因，例如，先進先出算法就可能會產(chǎn)生抖動現(xiàn)象。本題中只有虛擬頁式和虛擬段式

才存在換人換出的操作，簡單頁式和簡單段式因已經(jīng)全部將程序調(diào)入內(nèi)存，因此不

需要置換，也就沒有了抖動現(xiàn)象。這里需要注意簡單式和虛擬式的區(qū)別。

31、若用8個字（字長32位，且字號和位號都從。開始計數(shù)）組成的位示圖管理內(nèi)

存，假定用戶歸還一個塊號為100的內(nèi)存塊時，它對應(yīng)位示圖的位置為（）。

A、字號為3,位號為5

B、字號為4,位號為4

C、字號為3,位號為4

D、字號為4,位號為5

標(biāo)準答案：C

知識點解析：本題考查位示圖。先求出塊號為100所在的字號，。?31在字號0,

32?63在字號1,64?95在字號2,96?127在字號3,所以塊號100在字號3。

接下來求出第100塊在字號3的哪一位，字號3的第0位是第96塊，以此類推第

100塊在字號3的第4位?；蛘?，字號二100/32=3,位號=100%32=4。對于此類

題，為了避免出錯，建議畫出草圖求解。

32、I/O中斷是CPU與通道協(xié)調(diào)工作的一種手段，所以在（）時，便要產(chǎn)生中斷。

A、CPU執(zhí)行“啟動I/0”指令而被通道拒絕接收

B、通道接收了CPU的啟動請求

C、通道完成了通道程序的執(zhí)行

D、通道在執(zhí)行通道程序的過程中

標(biāo)準答案：c

知識點。析：本題考查通道控制方式。CPU啟動通道時不管啟動成功與否，通道

都要回答CPU,通過執(zhí)行通道程序來實現(xiàn)數(shù)據(jù)的傳送。通道在執(zhí)行通道程序時，

CPU與通道并行，當(dāng)通道完成通道程序的執(zhí)行（即數(shù)據(jù)傳送結(jié)束），便產(chǎn)生1/0中

斷向CPU報告。

33、對于可靠服務(wù)和不可靠服務(wù)，正確的理解是（），

A、可靠服務(wù)是通過高質(zhì)量的連接線路來保證數(shù)據(jù)可靠傳輸

B、如果網(wǎng)絡(luò)本身是不可靠的，那么用戶只能嘗試使用而無更好的辦法

C、可靠性是相對的，不可能完全保證數(shù)據(jù)準確傳輸?shù)侥康牡?/p>

D、對于不可靠的網(wǎng)絡(luò)，可以通過應(yīng)用或用戶來保障數(shù)據(jù)傳輸?shù)恼_性

標(biāo)準答案：D

知識點解析：本題考查可靠服務(wù)和不可靠服務(wù)。在網(wǎng)絡(luò)的傳輸過程中，數(shù)據(jù)出錯是

很難避免的，只有通過檢錯、糾錯、應(yīng)答機制才能保證數(shù)據(jù)正確地傳輸，這種數(shù)據(jù)

傳輸是可以準確地到目的地的，這種可靠服務(wù)是由網(wǎng)絡(luò)本身（或鏈路）負責(zé)，即可靠

服務(wù)是通過一系列的機制來保證傳輸?shù)目煽啃?，并不是通過高質(zhì)量的連接線路，A

錯誤；不可靠服務(wù)是出于速度、成本等原因的考慮，而忽略了網(wǎng)絡(luò)本身的數(shù)據(jù)傳輸

的保證機制，但可以通過應(yīng)用或用戶判斷數(shù)據(jù)的準確性，再通知發(fā)送方采取措施，

從而把不可靠的服務(wù)變?yōu)榭煽糠?wù)，B錯誤，D正確；而當(dāng)網(wǎng)絡(luò)是可靠的時候，因

為檢錯、糾錯、應(yīng)答機制的存在，一定能保證數(shù)據(jù)最后準確的傳輸?shù)侥康牡兀珻錯

誤。這題可以注意到B和D選項是相對的，基本可以確定兩者中必有一個是答

案。

34、采用GBN幀協(xié)議，接收窗口內(nèi)的序號為4時，接收到正確的5號幀應(yīng)該（）。

A、丟棄5號幀

B、將窗口滑動到5號

C、將5號幀緩存下來

D、將5號幀交給上層處理

標(biāo)準答案：A

知識點解析：本題考查了有關(guān)GBN協(xié)議的相關(guān)機制問題。在GBN協(xié)議中，接收

窗口尺寸被定為1,從而保證了按序接收數(shù)據(jù)幀。如果接收窗口內(nèi)的序號為4時，

此時接收方需要接收到的幀即為4號幀，即便此時接收到正確的5號幀，接收端也

會自動丟棄該幀從而保證按序接收數(shù)據(jù)幀。注意：GBN協(xié)議中接收端是沒有緩存

的，所以也不存在將5號幀緩存下來的說法。

35、信道速率為4kbps,采用停止一等待協(xié)議。設(shè)傳播時延t=20ms,確認幀長度和

處理時間均可忽略。若信道的利用率達到至少50%,則幀長至少為（）。

A、40bit

B、80bit

C、160bit

D、320bit

標(biāo)準答案：C

知識點解析：本題考查最小幀長與信道利用率。在確認幀長度和處理時間均可忽略

不計的情況下，信道的利用率發(fā)送時間/（t發(fā)送時間+2xt傳播時間）。根據(jù)信道利用率的計

算公式，當(dāng)發(fā)送一幀的時間等于信道的傳播時延的2倍時，信道利用率是50%,

或者說當(dāng)發(fā)送一幀的時間等于來回路程的傳播時延時，效率將是50%,即

20msx2=40mso現(xiàn)在發(fā)送速率是4000bps,即發(fā)送一位需要0.25ms,則幀長40

/0.25=160bito

36、TCP/IP網(wǎng)絡(luò)中，某主機的IP地址為130.25.3.135,子網(wǎng)掩碼為

255.255.255.192,那么該主機所在的子網(wǎng)的網(wǎng)絡(luò)地址是（），該子網(wǎng)最大可分配

地址個數(shù)是（）。

A、130.25.0.0,30

B、130.25.3.0,30

C、130.25.3.128,62

D、130.25.3.255,126

標(biāo)準答案：C

知識"解析：本題考查子網(wǎng)地址的計算。子網(wǎng)掩碼與IP地址逐位相“與”可得網(wǎng)絡(luò)

地址。主機號為全0表示本網(wǎng)絡(luò)，全1表示本網(wǎng)絡(luò)的廣播地址。從子網(wǎng)掩碼可以看

出網(wǎng)絡(luò)地址與第四個字節(jié)有關(guān)。因此，130.25.3.135的二進制為

130.25.3.10000111,子網(wǎng)掩碼的二進制為255.255.255.11000000,兩者

相與,因此網(wǎng)絡(luò)地址為130.25.3.10000000,換算成十進制為

130.25.3.128。最后6位為主機號，主機號不能為全O或全1,最大可分配地

址個數(shù)為26—2=62。

37、當(dāng)路由器接收到一個15個字節(jié)的IP數(shù)據(jù)報時,需要將其轉(zhuǎn)發(fā)到MTU為980

的子網(wǎng),分片后產(chǎn)生兩個IP數(shù)據(jù)報，長度分別是（）。（首部長度為2OB）

A、750,750

B、980,520

C、980,540

D、976,544

標(biāo)準答案：C

知識點解析：MTU為980B,則數(shù)據(jù)部分長度應(yīng)該為MTtJ長度減去IP數(shù)據(jù)報首部

長度，即為960B,接收到的IP數(shù)據(jù)報長度為1500B,數(shù)據(jù)部分長度為1480B,則

第一個數(shù)據(jù)報長度即為一個MTU長度980B,第二個數(shù)據(jù)報長度為1480-

960+20=5409。

38、下圖中，主機A發(fā)送一個IP數(shù)據(jù)報給主機B,通信過程中以太網(wǎng)1上出現(xiàn)的

以太網(wǎng)幀中7…一頭中的目的地址

分別是（）。

A、B的MAC地址，B的IP地址

B、B的MAC地址，R1的IP地址

C、R1的MAC地址，B的IP地址

D、R1的MAC地址，RI的IP地址

標(biāo)準答案：C

知識點解析：因為主機B與主機A不在一個局域網(wǎng)，所以主機A在鏈路層封裝IP

數(shù)據(jù)報時，MAC幀中日的MAC地址填寫的是網(wǎng)關(guān)MAC地址，就是R1的MAC

地址。在該以太網(wǎng)IP報頭中，目的IP地址是B的IP地址，而且在傳輸過程中源

IP地址和目的IP地址都不會發(fā)生改變。

39、下列網(wǎng)絡(luò)設(shè)備中，能隔離ARP廣播幀是（）。

A、路由器

B、網(wǎng)橋

C、以太網(wǎng)交換機

D、集線器

標(biāo)準答案：A

知識點解析：路由器可以隔離廣播域和沖突域，要扉蔽數(shù)據(jù)鏈路層的廣播幀，當(dāng)然

應(yīng)該是網(wǎng)絡(luò)層設(shè)備，因此只能選路由器。而以太網(wǎng)交換機和網(wǎng)橋是數(shù)據(jù)鏈路層的設(shè)

備，只能隔離沖突域，不能隔離廣播域。此外，集線器作為物理層設(shè)備，既不能隔

離廣播域，又不能隔離沖突域。當(dāng)然此題選項中，路由器為其中最高層的網(wǎng)絡(luò)設(shè)

備，其他設(shè)備能隔離的，路由舂一定能隔離，又因為是單選題，所以就算不記得具

體知識點，也肯定能推斷出選A。

40、下列關(guān)于客戶/服務(wù)器模型的描述中，錯誤的是（）。I.客戶端和服務(wù)器必

須都事先知道對方的地址，以提供請求和服務(wù)口.HTTP基于客戶/服務(wù)器模型，

客戶端和服務(wù)器端的默認端口號都是80III.瀏覽器顯示的內(nèi)容來自服務(wù)器W.客

戶端是請求方，即使連接建立后，服務(wù)器也不能主動發(fā)送數(shù)據(jù)

A、I和IV

B、II和W

C、I、n和IV

D、只有W

標(biāo)準答案：C

知識點解析：本題考查客戶/服務(wù)器模式的概念?？蛻舳耸欠?wù)請求方，服務(wù)器是

服務(wù)提供方，二者的交互由客戶端發(fā)起。客戶端是連接的請求方，在連接未建立之

前，服務(wù)器在端口80上監(jiān)聽，當(dāng)確立連接以后會轉(zhuǎn)到其他端口號，而客戶端的端

口號不固定。這時客戶端必須要知道服務(wù)器的地址才能發(fā)出請求，很明顯服務(wù)器事

先不需要知道客戶端的地址。一旦連接建立后，服務(wù)器就能主動發(fā)送數(shù)據(jù)給客戶端

(即瀏覽器顯示的內(nèi)容來自服務(wù)器)，用于一些消息的通知(如一些錯誤的通知)。在

客戶/服務(wù)器模型中，默認端口號通常都是指服務(wù)器端，而客戶端的端口號通常都

是動態(tài)分配。

二、綜合應(yīng)用題(本題共79題，每題7.0分，共”

分。)

41、設(shè)記錄的關(guān)鍵字(key)集合:k=｛24,15,39,26,18,31,05,22),請回

答：依次取K中各值，構(gòu)造一棵二叉排序樹(不耍求平衡)，并寫出該樹的前序、

中序和后序遍歷序列。設(shè)Hash表表長m=16,Hash函數(shù)H(key)=(key)%13,處理

沖突方法為“二次探測法”，請依次取K中各值，構(gòu)造出滿足所給條件的Hash表；

并求出等概率條件下查找成功時的平均查找長度。將給定的K調(diào)整成一個堆頂元

素取最大值的堆(即大根堆)。

標(biāo)準答案：(1)將關(guān)鍵字｛24,15,39,26,18,31,05,22｝依次插入構(gòu)成的二叉

排序樹如下：24,15,05,18,22,39,26,

31中序遍歷序列:05,15,18,22,24,26,31,39后序遍歷序列：05,22,

18,15,31,26,39,24(2)各關(guān)鍵字通過Hash函數(shù)得到的散列地址如下表。

關(guān)健字2415392618310322

散列地址112005559

Key=24.15、39均沒有沖突，H0(26)=0,沖突,HI(26)=0+1=1,沒有沖突；

Key=18沒有沖突,HO(31)=5,沖突，Hl(31)=5+1=6,沒有沖突;H0(05)=5,沖

突，HI(05)=5+1=6,沖突，H2(05)=5—1=4,沒有沖突,Key=22沒有沖突故各個

關(guān)鍵字的存儲地址如下表所示。

地址0123456789101112131415

關(guān)鍵字3926150518312224

沒有發(fā)生沖突的關(guān)鍵字，查找的比較次數(shù)為1,發(fā)生沖突的關(guān)鍵字，查找的比較次

數(shù)為沖突次數(shù)+1,因此，等概率下的平均查找長度為：ASL=(1+1+1+2+1+24-3+1)

/2=1.5次⑶首先對以26為根的子樹進行調(diào)整，調(diào)整后的結(jié)果如圖b所示；對

以39為根的子樹進行調(diào)整，調(diào)整后的結(jié)果如圖c所示；再對以15為根的子樹進行

藝整，調(diào)整后的結(jié)果如圖d所示；最后對根結(jié)點進行調(diào)整，調(diào)整后的結(jié)果如圖e所

示。

⑹調(diào)整39的子樹后

(d)調(diào)整15的子科后(e)01整根結(jié)點后

知識點解析：暫無解析

假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)，設(shè)計一個算法求其指定的某一層k(k>1)的葉

子結(jié)點個數(shù)，要求：

42、給出算法的基本設(shè)計思想。

標(biāo)準答案：算法的基本沒計思想：可以使用層次遍歷模型，只需在層次遍歷上加

上記錄當(dāng)前層次的功能。當(dāng)沒有達到目標(biāo)層時，把該結(jié)點的孩子結(jié)點入隊列；當(dāng)

達到目標(biāo)層時，不再讓各個結(jié)點的孩子結(jié)點入隊，而是統(tǒng)計這一層葉子結(jié)點的數(shù)目

即可。

知識點解析：暫無解析

43、寫出二叉樹采用的存儲結(jié)構(gòu)代碼。

標(biāo)準答案：二叉樹存儲結(jié)構(gòu)如下：typcdefstructBiTNode{ElemTypedata；//數(shù)

據(jù)域structBiTNode*lchild,*rchild；//左、右孩子指針}BTNode,*BiTree

知識點解析：暫無解析

44、根據(jù)設(shè)計思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

標(biāo)準答案：算法的設(shè)計如卜：intn；intLealKLevel(BiTreeroot,inik){n=0；

PreOrder(root,0,k)；return0；)intPreOrderfBiTreeroot,intdeep,intk){if(deep

<k){if(root—>lchild!=NULL)//若左子樹不空，對左子樹遞歸遍歷

PreOrder(root->lchild,deep+1)；if(root->rchiid!=NULL)//若右子樹不空，對

右子樹遞歸遍歷PreOrder(root—>rchild,deep+1),}else

if{deep==k&&root—>lchild==NULL&&root—>rchild==NULL)++n,}

知識點解析：暫無解析

己知32位寄存器中存放的變量x的機器碼為C0000004H,請問:

45、當(dāng)x是無符號整數(shù)時，x的真值是多少?x/2的真值是多少?x/2存放在R1中

的機器碼是什么?2x的真值是多少?2x存放在R1中的機器碼是什么？

標(biāo)準答案：x是無符號整數(shù)，所有的二進制位均為數(shù)值位，COOOO004H的真值為

231+230+22Ox/2是由邏輯右移一位得到的，即Q31+230+22)/2,其真值為

23。+229+2,存放在R1中的機器碼是60000002H。2x是由x邏輯左移一位得到的，

真值發(fā)生溢出，存放在R1中的機器碼是80000008H。

知識點解析：暫無解析

46、當(dāng)x是帶符號整數(shù)(補碼)時，x的真值是多少?x/2的真值是多少?x/2存放在

R1中的機器碼是什么?2x的真值是多少?2x存放在R1中的機器碼是什么？

標(biāo)準答案：機器碼COOO0004H=11000000000000000000000000000100B,表示

這是一個負數(shù)，數(shù)值位取反末位加1,得到的二進制原碼為1011111111111111

1111111111111100,即二進制真值為一0011111111111111111111111111

1100,對應(yīng)的十進制真值為—Q30—22)。x/2是由X算術(shù)右移一位得到的，其真

值為—Q29—2),存放在R1中的機器碼是E0000002Ho2x是由x算術(shù)左移一位得

到的，其真值為=Q31—23),存放在R1中的機器碼是80000008H。

知識點解析：暫無解析

47、當(dāng)x是float型浮點數(shù)時，x的真值是多少?x/2的真值是多少?x/2存放在R1

中的機器碼是什么?2x的真值是多少?2x存放在R1中的機器碼是什么？

標(biāo)準答案：)在舊￡754單精度浮點數(shù)中，最高位為數(shù)符位；其后是8位階碼，以2

為底，用移碼表示，階碼的偏置值為127；其后23位是尾數(shù)數(shù)值位，隱藏數(shù)值的

最高位力”。轉(zhuǎn)換為二進制110000000000000000000(X)000000100,可知，x為

負數(shù),階碼為1,尾數(shù)為1+2—21,故真值為一(1+2-21)X2。x/2的真值是一(1+2—

2|),存放在R1中的機器碼為10111111100000000000000000000100,即BF80

0004Ho2x的真值是一(1+2—21)x22,存放在R1中的機器碼為110000001000

00000000000000000100,即C0800004H。

知識點解析：暫無解析

某16位機器所使用的指令格式和尋址方式如下所示，該機有四個20位基址寄存

器，十六個16位通用寄存器(可用做變址寄存器)。指令匯編格式中的S(源)，D(目

標(biāo))都是通用寄存器，M是主存的一個單元。三種指令的操作碼分別是

48、分析三種指令的指令格式和尋址方式特點。

標(biāo)準答案：本題考查指令的格式與編碼。第一種指令是單字長二地址指令，RR

型；第二種指令是雙字長二地址指令，RS型，其中S采用基址尋址或變址尋玨，

R由源寄存器決定；第三種也是雙字長二地址指令，RS型，其中R由目標(biāo)寄存器

決定，S由20位地址(直接尋址)決定。

知識點解析：暫無解析

49、處理機完成哪一種操作所花時間最短?哪一種最長?第二種指令的執(zhí)行時間有時

會等于第三種指令的執(zhí)行時間嗎？

標(biāo)準答案：處理機完成第一種指令所花的時間最短，因為是RR型指令，不需要訪

問存儲器。第二種指令所花的時間最長，因為RS型指令，需要訪問存儲器，同時

要進行尋址方式的變換迄算(基址或變址)，這也要時間。第二種指令的執(zhí)行時間不

會等于第三種指令，因為第三種指令雖然也訪問存儲器，但節(jié)省了求有效地址運算

的時間開銷。

知識點解析：暫無解析

50、下列情況中，每個十六進制指令字分別代表什么操作?若有指令編碼不正確，

如何改正i才能成為合法指令？①(FOF1)H(3CD2)H②(2856)H③(6DC6)H④(1C2)H

標(biāo)準答案：根據(jù)已知條;牛：MOV(OP)=001010,STA(OP)=011011,

LDA(OP)=1I1IOO,將指令的十六進制格式轉(zhuǎn)換為二進制代碼且比較后可知：

?(FOF1)H(3CD2)H=111100I00I111100010011110011010002,指令代表LDA

指令，編碼正確，其含義是把主存(13CD2)H地址單元的內(nèi)容取至15號寄存器。

②(2856)H=00101。I00I。1。1I0110指令代表MOV指令，編碼正確，含義是把

6號源寄存器的內(nèi)容傳送至5號目標(biāo)寄存器。③(6DC6)H=0110“I01IH00I

0110是單字長指令，一定是MOV指令，但編碼錯誤，可改正為(29C6)H。

④(1C2)H=000000I01I1100I0010是單字長指令，代表MOV指令，但編碼錯

誤，可改正為(29C2)H。

知識點解析：暫無解析

某系統(tǒng)由RI、R2和R3共3種資源，在TO時刻Pl、P2、P3和P4這4個進程對

資源的占用和需求情況如下表所示，此時系統(tǒng)的可用資源向量為(2，1,2)o試

最大資源需求量已分配資源數(shù)量

進程

R1R2R3R1R2R3

PI322!00

P2613411

P3314211

P4422002

51、系統(tǒng)是否處于安全狀態(tài)?如安全，請給出一個安全序列。

標(biāo)準答案：本題考查采用銀行家算法避免死鎖。利用安全性算法對時刻的資源分

配情況進行分析，可得到如下表所示的安全性檢測情況。可以看出，此時存在一

個安全序列{P2,P3,P4,P1},故該系統(tǒng)是完全的。

WorkNeedAllocationWork+Allocation

進程Fiftish

R1R2R3RIR2R3RIR2R3RIR2R3

P2212202411623True

P3623103211834.True

P4834420002836True

P1836222100936True

此處要注意，一般大多數(shù)題目中的安全序列并不唯一。

知識點解析：暫無解析

52、如果此時P1和P2均發(fā)出資源請求向量Request。，0,1),為了保證系統(tǒng)的安

全性，應(yīng)該如何分配資源給這兩個進程?說明你所采用策略的原因。

標(biāo)準答案：若此時P1發(fā)出資源請求Requestl(l,0,1),按銀行家算法進行檢查：

Requestl(1,0,l)<Needl(2,2,2)Request1(1?0,l)<Available(2,1,2)試分配并

修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，由此形成的資源分配情況如下表所示：

AllocationMaxAvailable

進程

RIR2R3RIR2R3RiR2R3

Pi201121

P241!202

111

P321I103

P4002420

再利用安

仝性算法檢查系統(tǒng)是否安全，可用資源Available。，1,1)已不能滿足任何進程，

系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不能將資源分配給P1。若此時P2發(fā)出資源請求

Request2(l,0,1),按銀行家算法進行檢查：Request2(l,0,l)<Need2(2,0,2)

Request2(l,0,l)<Available(2,1,2)試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，由此形成的

資源分配情況如下表所示：

AllocationMaxAvailable

進程

RIR2R3RIR2R3RIR2R3

PI100222

P2512101

111

P3211103

P4002420

再利用安全性算法檢查系統(tǒng)是否安全，安全性檢查情況如下表所示。可以看出，此

時存在一個安全序列{P2,P3,P4,P1},故該狀態(tài)是完全的，可立即給P2申請的資源

分配給它。

WorkNeedAllocationWork+Allocation

進程Finish

RIR2R3RIR2R3RIR2R3RIR2R3

P2111101512623True

P3623103211834True

P4834420002836True

PI836222100936True

知識點解機?：哲尢解析

53、如果(2)中兩個請求立即得到滿足后，系統(tǒng)此刻是否處于死鎖狀態(tài)。

標(biāo)準答案：如果上一小題中兩個請求立即得到滿足，此刻系統(tǒng)并沒有立即進程死鎖

狀態(tài)，因為這時所有進程沒有提出新的資源申請，全部進程均沒有因資源請求沒得

到滿足而進入阻塞狀態(tài)。只有當(dāng)進程提出資源請求，且全部進程都進入阻塞狀態(tài)

時，系統(tǒng)才處于死鎖狀態(tài)。

知識點解析：暫無解析

在實現(xiàn)文件系統(tǒng)時，為加快文件目錄的檢索速度,可利用“文件捽制塊分解法喝假

設(shè)目錄文件存放在磁盤上，每個盤塊有512字節(jié)。文件控制塊占64字節(jié)，其中文

件名占8個字節(jié)。通常將文件控制塊分解成兩部分，第一部分占16字節(jié)(包括文件

名和文件內(nèi)部號)，第二部分占48字節(jié)(包括文件內(nèi)部號和文件其他描述信息)。

54、假設(shè)某一目錄文件共有254個文件控制塊，試分別給出采用分解法前和分解法

后，查找該目錄文件的某一個文件控制塊的平均訪問磁盤次數(shù)。(訪問每個文件的

概率相同)

標(biāo)準答案：本題考查文件系統(tǒng)的目錄檢索。目錄是存放在磁盤上的，檢索目錄時

需要訪問磁盤，速度很慢。利用“文件控制塊分解法”加快目錄檢索速度的原理是：

將文件控制塊的一部分分解出去，存放在另一個數(shù)據(jù)結(jié)構(gòu)中，而在目錄中僅留下文

件的基本信息和指向該數(shù)據(jù)結(jié)構(gòu)的指針，這樣一來能有效地縮減目錄的體積，減少

了目錄在磁盤中的塊數(shù)，于是檢索目錄時讀取磁盤的次數(shù)也減少，于是也就加快了

檢索目錄的速度。分解法前，目錄的磁盤塊數(shù)為64x254/512=31.75,即32

塊。前31塊中，每塊放了512/64=8個，而最后一塊放了254—31x8=6個。所以

查找該目錄文件的某一個文件控制塊的平均訪問磁盤次數(shù)=(8x(l+2+3+…+3

1)+6*32)/254=16.38次。分解法后，目錄的磁盤塊數(shù)為16x254/512