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

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

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

1、設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時間復(fù)雜度是（）。inti=l：

while（i<=n）i=i*2：

A、O（log2n）

B、O（n）

C、O（nlog2n）

D、O（n2）

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：這是一個比較有趣的問題。如果不仔細(xì)分析的話，可能會得到O（n）

的結(jié)果。關(guān)鍵在于分析出while語句執(zhí)行的次數(shù)。由于循環(huán)體中，i=i*2,所以循環(huán)

執(zhí)行的次數(shù)是log2n,由此可見，算法的時間復(fù)雜度不是由問題規(guī)模n直接決定，

而是log2n。

2、排序趟數(shù)與序列的原始狀態(tài)無關(guān)的排序方法是（）。I.直接插入排序n.簡單

選擇排序in.冒泡排序IV.基數(shù)排序

A僅

、I、m

B僅

、I、口、w

c僅

、、口、皿

僅I

D

、I、IV

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：直接插入排序：每趟排序都是插入一個元索，所以排序趟數(shù)固定為n

一l（n為元素?cái)?shù)）。簡單選擇排序：每趟排序都是選出一個最?。ɑ蜃畲螅┑脑?，

所以排序趟數(shù)固定為n-l（n為元素?cái)?shù)）。交換類的排序：其趟數(shù)和原始序列狀態(tài)有

關(guān)，所以冒泡排序與初始序列有關(guān)?；鶖?shù)排序：每趟排序都要進(jìn)行“分配''和"收

集”，排序趟數(shù)固定為d（d為組成元素的關(guān)鍵字位數(shù)）。綜上所述，I、H、W都是

無關(guān)的，所以選B。

3、下列陳述中正確的是（）。

A、在DMA周期內(nèi)，CPU不能執(zhí)行程序。

B、中斷發(fā)生時，CPU首先執(zhí)行人棧指令將程序計(jì)數(shù)器的內(nèi)容保護(hù)起來。

C、DMA傳送方式中，DMAC每傳送一個數(shù)據(jù)就竊取一個指令周期。

D、輸入輸出操作的最終目的是要實(shí)現(xiàn)CPU與外設(shè)之間的數(shù)據(jù)傳輸。

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：A錯，DMA周期內(nèi)CPU仍然可以執(zhí)行程序。B錯，對于單重中斷發(fā)

生時首先執(zhí)行中斷周期，其順序?yàn)橹袛囗憫?yīng)、關(guān)中斷、程序斷點(diǎn)（PC）進(jìn)棧、向量地

址送PC。

4、［x］補(bǔ)=1.X|X2）X3X4，則當(dāng)滿足（）時,X>-1/2成乂。

A、X］必為0,X2~X4至少有一個為1

B、X|必為0,X2?X4任意

C、XI必為1,X2?X4至少有一個為1

D、X］必為I,X2~X4任意

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：可采用排除法，1.0001符合A、B選項(xiàng)的要求，其值一15/16<一

1/2,排除A、B：1.1000符合D選項(xiàng)的要求，其值二一1/2,排除D：故選

Co

5、下面有關(guān)指令周期的敘述中，錯誤的是（）。

A、指令周期的第一個機(jī)器周期一定是取指周期

B、所有指令的執(zhí)行周期一樣長

C、在有間接尋址方式的指令周期中，至少訪問兩次內(nèi)存

D、在一條指令執(zhí)行結(jié)束，取下條指令之前查詢是否有中斷發(fā)生

標(biāo)準(zhǔn)答案：B

知識點(diǎn)端析：取指令操作完成的任務(wù)是將當(dāng)前指令從內(nèi)存中取出來，并送至指令寄

存器中，所以指令周期的第一個機(jī)器周期一定是取指周期。在間接尋址方式的指令

周期中，至少訪問兩次內(nèi)存，第一次取指令，第二次取操作數(shù)地址。對中斷請求的

響應(yīng)時間只能發(fā)生在每條指令執(zhí)行完畢時，所以在一條指令執(zhí)行結(jié)束，取下條指令

之前需要查詢是否有中斷發(fā)生。

6、若數(shù)據(jù)鏈路的發(fā)送窗口尺寸WT=4,在發(fā)送3號幀、并接到2號幀的確認(rèn)幀

后，發(fā)送方還可連續(xù)發(fā)送的幀數(shù)是（）。

A2幀

、

B3幀

、

c4幀

、

D1幀

、

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查滑動窗口的機(jī)制。這里收到2號幀的確認(rèn)后，即，1,2號

幀己經(jīng)正確接收，因此窗口向有移動3個幀，目前己經(jīng)發(fā)送了3號幀，因此可連續(xù)

發(fā)送的幀數(shù)是窗口大小一已經(jīng)發(fā)送的幀數(shù)，即4—1=3,因此答案是B。

7、在DNS的遞歸查詢中，由（）給客戶端返回地址。

A、最開始連接的服務(wù)器

B、最后連接的服務(wù)器

C、目的地址所在的服務(wù)器

D、不確定

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：在遞歸查詢中，每臺不包含被請求信息的服務(wù)器都轉(zhuǎn)到別的地方去查

找，然后它再往回發(fā)送結(jié)果。所以客戶端最開始連接的服務(wù)器最終將返回給它正確

的信息。

8、設(shè)CPU與I/O設(shè)備以中斷方式進(jìn)行數(shù)據(jù)傳送。當(dāng)CPU響應(yīng)中斷時，該I/O設(shè)備

接口控制器送給CPU的中斷向量表（中斷向量表存放中斷向量）的指針是

0800H,0800H單元中的值為1200H,則該I/O設(shè)備的中斷服務(wù)程序在主存中的入

口地址為（）。

A、0800H

B、0801H

C、1200H

D、120IH

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：首先需要明白中斷向量就是中斷服務(wù)程序的入口地址，所以需要找到

指定的中斷向量。中斷向量是保存在中斷向量表中的，而0800H是中斷向量表的

地址，所以0800H的內(nèi)容即是中斷向量。

9、若一個棧的輸入序列為1,2,3,n,輸出序列的第一個元素是i,則第j

個輸出元素是（）。

A、i-j-1

B、i-j

C、j-i+1

D、不確定

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：一串?dāng)?shù)據(jù)依次通過一個棧，并不能保證出棧數(shù)據(jù)的次序總是倒置，可

以產(chǎn)生多種出棧序列「一串?dāng)?shù)據(jù)通過一個棧后的次序由每個數(shù)據(jù)之間的進(jìn)棧、出棧

操作序列決定，只有當(dāng)所有數(shù)據(jù)“全部進(jìn)棧后再全部出棧''才能使數(shù)據(jù)倒置。事實(shí)

上，存在一種操作序列——“進(jìn)棧、出棧、進(jìn)棧、出?！薄梢允箶?shù)據(jù)通過棧

后仍然保持次序不變。題目中輸出序列的第一個元素是i,則第j個輸出元素是不

確定的。

10、某調(diào)制解調(diào)器同時使用幅移鍵控和相移鍵控，采用0、兀/2、兀和3/2兀四種

相位，每種相位又都有2個不同的幅值，在波特率為1200的情況下數(shù)據(jù)速率是

（）。

A、7200bps

B、4800bps

C、2400bps

D、1200bps

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查奈奎斯特定理，注意根據(jù)題意有4種相位X2個幅值：8種信

號狀態(tài)，根據(jù)共識C=2Wxk）g2M=2xl2（X）xk）g28=2xl200x3=7200bps,因此答案

為A。［歸納總結(jié)］關(guān)于信道最大數(shù)據(jù)速率的計(jì)算：Nyquist已經(jīng)證明，若信號通過

帶寬為H的低通濾波器，則濾過的信號可以用每秒2H個采樣值完全恢復(fù)出來。如

果信號由V個離散等級組成，則Nyquist定理表明信道上的最大數(shù)據(jù)速率為

2Hlog2Vbpso對于無噪聲信道來說，V可以無窮大，但對于有噪聲信道來說，V

是有限的，與信道的信噪比有關(guān)。信噪比：信號功率s與噪聲功率N的比值，常

用分貝來表示：lOlogioS/N。根據(jù)Shannon定理，帶寬為H、信噪比為S/N的

信道的最大數(shù)據(jù)速率為Hlog2（l+S/N）bps。

11、局域網(wǎng)中訪問沖突的根源是（）。

A、獨(dú)占介質(zhì)

B、共享介質(zhì)

C、引入MAC子層

D、規(guī)則的拓?fù)浣Y(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查以太網(wǎng)CSMA/CD協(xié)議的原理，由于采用隨機(jī)訪問和競爭

技術(shù)，CS—MA/CD只用于總線拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)，因此答案為B。

12、指令流通常是（）。

A、從主存流向控制器

B、從控制器流向主存

C、從控制器流向控制港

D、從主存流向主存

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：指令是存放在主存中的，在主存中取出指令后送入控制器進(jìn)行分析并

發(fā)出相應(yīng)的各種操作序列，所以指令流是從主存流向控制器，且是單向流動；而數(shù)

據(jù)流是在CPU中的運(yùn)算器和主存之間流動，且是雙向流動。

13、下列關(guān)于文件控制決的錯誤說法的個數(shù)為（）。I.文件控制塊就是文件目錄

項(xiàng)口.文件控制塊是在執(zhí)行open（打開）系統(tǒng)調(diào)用時建立的ID.一個文件可以對應(yīng)

有多個文件控制塊W.文件控制塊通常含有3類信息：基本信息、存取控制信息

及使用信息

A、1

B、2

C、3

D、4

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：文件控制塊與文件一一對應(yīng)（HI錯誤），創(chuàng)建文件時（create）建立對應(yīng)的

FCB,而不是打開文件時創(chuàng)建的（II錯誤）。人們把文件控制塊的有序集合稱為文件

目錄，即一個文件控制塊就是一個文件目錄項(xiàng)（I正確）。在文件控制塊中，通常含

有3類信息：基本信息、存取控制信息及使用信息（W正確）。所以I、W正確，

U、IH錯誤。錯誤的個數(shù)為2,所以選Be

14、對于設(shè)計(jì)實(shí)時操作系統(tǒng)，不是其設(shè)計(jì)目標(biāo)的是（）。

A、安全可靠

B、處理機(jī)效率

C、及時響應(yīng)輸入

D、快速處理請求

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查實(shí)時操作系統(tǒng)的設(shè)計(jì)目標(biāo)。實(shí)時操作系統(tǒng)要求能對用戶的請

求在規(guī)定的時間內(nèi)完成，同時需要保證進(jìn)程運(yùn)行的安全性和高可靠性。而處理機(jī)的

效率不是實(shí)時操作系統(tǒng)沒計(jì)所關(guān)心的。

15、下列選擇中，（）不是操作系統(tǒng)關(guān)心的主要問題，

A、管理計(jì)算機(jī)裸機(jī)

B、設(shè)計(jì)、提供用戶程序與計(jì)算機(jī)硬件資源的接口

C、管理計(jì)算機(jī)系統(tǒng)資源

D、高級程序設(shè)計(jì)語言的編譯器

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：D不是操作系統(tǒng)的功能。

16、在一個HDLC幀的數(shù)據(jù)中，如果出現(xiàn)了000111111011這樣的流，請問發(fā)送到

信道上它將會變成（）。

A、0001111110110

B、0001111111011

C、0001111101011

D、0000111II1011

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：HDLC采用了比特填充法來實(shí)現(xiàn)鏈路層的透明傳輸，如果在數(shù)據(jù)流中

發(fā)現(xiàn)了連續(xù)的5個力”就在其后面加一個“0”，所以C是正確答案。

17、已知計(jì)算機(jī)存儲器按字節(jié)編址，指令字長32位，則一條指令結(jié)束后，PC值應(yīng)

自動加（）。

A、1

B、2

C、4

D、以上都不對

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：存儲器按字節(jié)編址，指令字長32位=4B,故PC值應(yīng)在每條指令執(zhí)

行結(jié)束后自動加4。

18、在系統(tǒng)總線中，地址總線的位數(shù)（）。

A、與機(jī)器字長有關(guān)

B、與存儲單元個數(shù)有關(guān)

C、與存儲字長有關(guān)

D、與存儲器帶寬有關(guān)

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：地址總線的位數(shù)與存儲單元個數(shù)有關(guān)，地址總線的位數(shù)越長，可訪問

的存儲單元個數(shù)就越多。

19、在一個雙鏈表中，在*P結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是（）。

A、p->pnor=q；q->next=p；p->pnor->next=q；q->prior=p->prior；

q->prior=p——>prior；P——>prior——>next=q；q->next=P；p——>prior=q->next；

C>q->next=P；p一>next=q；q->prior->next=q：q->next=P；

D、p->prior->next=q；q->next=P；q->prior=p->prior；p->prior=q；

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：（l）p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向的后繼結(jié)點(diǎn)指向q0（2）q的后繼結(jié)點(diǎn)指向

p。（3）q的前驅(qū)結(jié)點(diǎn)指向p的前驅(qū)結(jié)點(diǎn)。（4）p的前驅(qū)結(jié)點(diǎn)更新為cl。

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

的隊(duì)尾元素的實(shí)際位置，其移動按rear=（rear+1）MODm進(jìn)行，變量length表示

當(dāng)前循環(huán)隊(duì)列中的元素個數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是（）。

A^rear-length

B、（rear—lengh+m）MODm

C、（1+rear+m—length）MODm

D、m-length

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：按照循環(huán)隊(duì)列的定義，因?yàn)樵匾苿影凑誶car=（rcar+l）MODm進(jìn)

行，則當(dāng)數(shù)組Q[m=l]存放了元素之后，下一個入隊(duì)的元素將存放到Q[0]中，因

此隊(duì)列的首元素的實(shí)際位置是（rear—length+14-m）MODnic

21、下列關(guān)于配備32位微處理器的計(jì)算機(jī)說法正確的是（）。

A、該機(jī)器的通用寄存器一般為32位

B、該機(jī)器的地址總線寬度為32位

C、該機(jī)器能支持64位操作系統(tǒng)

D、以上說法均不正確

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查計(jì)算機(jī)的性能指標(biāo)。微處理器的位數(shù)是指該CPU一次能夠

處理的數(shù)據(jù)長度，稱為機(jī)器字長，機(jī)器字長通常等于通用寄存器的長度。64位操

作系統(tǒng)（通常向下兼容）需要64位CPU的支持，64位操作系統(tǒng)不僅是尋址范圍增加

到Z64,同時要求機(jī)器字長64位。而地址總線的寬度雖然一般情況下也會和處理器

的位數(shù)掛鉤，不過這也是不一定的，一些機(jī)器為了一些原因也可以把地址總線設(shè)為

小于32位，然后分幾個周期傳送一次地址。注：關(guān)于操作系統(tǒng)的位數(shù)和CPU的

位數(shù)的問題，32位操作系統(tǒng)指的是該操作系統(tǒng)最多可以訪問232個地址，即最多

4G的地址（因?yàn)橐恍┰颍热鏘/O的統(tǒng)一編址等，導(dǎo)致實(shí)際上不到4G,一般約

為3.7G左右），是一個軟件的概念；32位處理器指的是一次可以處理32位數(shù)

據(jù)，是CPU設(shè)計(jì)時就決定好的，是硬件的概念，而低位數(shù)的CPU不能運(yùn)行高位數(shù)

的操作系統(tǒng)，而高位數(shù)的CPU?？梢赃\(yùn)行低位數(shù)的操作系統(tǒng)（比如現(xiàn)在的CPU都是

64位的，但是大多數(shù)人用的仍是32位的操作系統(tǒng)）。

22、設(shè)圖G=（V,E）,其中：V={V（）,Vi，V2,V3}E={（V（）,Vi）,（V（）,V2）,

（Vo,V3）,（Vi，V3）}則從頂點(diǎn)Vo開始對圖G的深度優(yōu)先遍歷序列總共有（）種。

A、3

B、4

C、5

D、2

標(biāo)準(zhǔn)答案：B

Vi

知識點(diǎn)解析：此題的圖為V：深度優(yōu)先遍歷的序列有4個：

VoVjV^,V0V2V）V（VoVjV.V：

Viv,Viv,

23、對包含n個關(guān)鍵碼的散列表進(jìn)行檢索，平均檢索長度為（）。

A、O（logn）

B、0（n）

C>O（nlogn）

D、不直接依賴于n

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：對散列表進(jìn)行檢索，平均檢索長度僅與裝填因子a有關(guān)，而與關(guān)鍵字

個數(shù)n無關(guān)。

24、下列排序算法中，時間復(fù)雜度為O（nlogn）且占用額外空間最少的是（）。

A、堆排序

B、冒泡排序

C、快速排序

D、希爾排序

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：暫無解析

25、CPU響應(yīng)中斷時需要保護(hù)斷點(diǎn)，斷點(diǎn)指的是（）。

A、中斷服務(wù)程序的人口地址

B、程序計(jì)數(shù)器PC的內(nèi)容

C、CPU內(nèi)各寄存器的內(nèi)容

D、指令寄存器IR的內(nèi)容

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：CPU在一條指令執(zhí)行結(jié)束時響應(yīng)中斷，斷點(diǎn)指的是程序計(jì)數(shù)器PC的

內(nèi)容，也就是現(xiàn)行程序下一條將要執(zhí)行指令的地址。

26、已知定點(diǎn)小數(shù)x的補(bǔ)碼為1.x1X2X3，且xW-O.75,則必有()。

A、xi=l,X2=0,X3=l

B、xi=l

C、Xj=O?且X23

D、XI=O?X23

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：對于定點(diǎn)小數(shù)而言，當(dāng)爛-0.75,意味著-IVxW-O.75o

27、物理文件的組織方式是由()確定的。

A、應(yīng)用程序

B、存儲介質(zhì)

C、外存容量

D、存儲介質(zhì)和操作系統(tǒng)

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：本題考查文件的物理結(jié)構(gòu)。物理文件的組織是文件管理的內(nèi)容，而文

件管理是操作系統(tǒng)的主要功能之一；此外存儲介質(zhì)的特性也決定了文件的物理結(jié)

構(gòu)，如磁帶機(jī)只能采用順序存放方式。

28、設(shè)有一個n階三對角線矩陣A[n][n],現(xiàn)把它的三條對角線上的非零元素按行

存放到一個一維數(shù)組B口中，AUH1]存放到B|l]中(假定不用0下標(biāo))，那么

B[k]存放的元素的行號是()。

A、[(k+l)/3]

B、[(k+1)/3]

C>[(k+2)/3]

D、[(k+2)/3]

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：這種題目最好采用特殊值法，推導(dǎo)過程可能比較繁瑣，見表6-3。

?6-3特殊值推導(dǎo)過程

k1234S6789

A(i]U]A(1MUA[2](l]A[2J[2]A|2][3]A[3][2]A[3](3JA(3J[4]7*3]

「(k+1)/31ii2223334

29、假設(shè)某系統(tǒng)總線在一個總線周期中并行傳輸4字節(jié)信息，一個總線周期占用2

個時鐘周期，總線時鐘頻率為10MHz,則總線帶寬是()。

A、10MB/s

B、20MB/s

C、40MB/s

D、80MB/s

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：總線時鐘頻率為10MHz,一個總線周期占用2個時鐘周期，故1s

內(nèi)共有5M個總線周期；每個周期并行傳輸4字節(jié)信息，故總線帶寬為5M/sx4

B=20MB/so

30、以下動態(tài)路由算法中，使用距離一矢量路由算法的是（）。

A、RIP協(xié)議

B、OSPF協(xié)議

C、BGP協(xié)議

D、ICMP協(xié)議

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：RIP協(xié)議使用了距離一矢量路由算法c

31、下列關(guān)于棧的說法中，正確的是（）。I.若進(jìn)棧順序?yàn)閍、b、c,則通過出棧

操作可能得到5個a、b、c的不同出棧序列H.鏈?zhǔn)綏５臈ｍ斨羔樢欢ㄖ赶驐５?/p>

鏈尾n.兩個棧共享一個向量空間的好處是減少存取時間

A僅

、I

B僅

、I、n

c僅

、n

D僅

、n、w

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：I：該選項(xiàng)旨在讓考生知道一個公式。對于n個不同元素進(jìn)棧，出棧

—C；nJL>=_"約=5

序列的個數(shù)為"I加可以馬上得出，當(dāng)n=3時，出棧序列個數(shù)為44X3X2XI

故I正確。鏈?zhǔn)綏Ｒ话悴捎脝捂湵?，棧頂指針即為鏈頭指針。進(jìn)棧和出棧均

在鏈頭進(jìn)行，每次都要修改棧頂指針，鏈空即?？眨╰op=NULL）,故口錯誤。DI：

由于棧中數(shù)據(jù)的操作只有入棧和出棧，且時間復(fù)雜度均為0（1），因此并沒有減少

存取時間，故in錯誤。補(bǔ)充知識點(diǎn)：共享?xiàng)Ｌ崾荆簝蓚€棧共享一個數(shù)組

A|0.MaxSize—1］的空間，從而構(gòu)成共享?xiàng)?。?shù)組A的兩端是固定的，而棧底也

是固定的，為此將下標(biāo)為0的一端作為棧1的棧底，其棧項(xiàng)指針為topi;將下標(biāo)

為。MaxSize—1的一端作為棧2的棧底，其棧頂指針為top2,如圖7一所示。

MMSI/V-I

圖J共％找棧1的四要素如下：

6）棧空條件：topl==11。②棧滿條件：topl==top2—1。③元素x進(jìn)棧：

topl++；將元素x插入A［topl］處。④出棧元素：將出A［topl］元素；topi-。棧2

的四要素如卜：①?？諚l件：iop2二二MaxSize。②棧滿條件：top2==lopl+l。③

元素X進(jìn)棧：lop2一；將元素x插入A［【op2］處。?出棧元素：彈出A［lop2阮

素；top2++。注：以上都默認(rèn)指針指向當(dāng)前元素的下一個位置。

32、在一個請求分頁系統(tǒng)中，采用LRU頁面置換箕法時，假如一個作業(yè)的頁面走

向?yàn)?,3,2,1,1,3,5,I,3,2,1,5o當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3

和4時，則在訪問過程中所發(fā)生的缺頁率分別為()。

A、50%、33%

B、25%、100%

C、25%、33%

D、50%>75%

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查頁面置換的相關(guān)計(jì)算。當(dāng)物理塊數(shù)為3時，缺頁情況如下表

所示：

訪問事132113513215

1111111111\i

內(nèi)存33333333335

2222555222

477VV

缺頁次數(shù)為6,缺頁率為6/12=50%。當(dāng)物理塊數(shù)為4時，缺頁情況如下表所

小：

訪問

111111111111

33333333333

內(nèi)存

2222222222

555555

缺頁4V44

缺頁次數(shù)為4,缺頁率為4/12=33%。

33、有效容量為128KB的Cache,每塊16B,8路組相聯(lián)。字節(jié)地址為1234567H

的單元調(diào)入該Cache,其Tag應(yīng)為()。

A、1234H

B、2468H

C、048DH

D、12345H

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解信：因?yàn)閴K的大小為16B,所以塊內(nèi)地址字段為4位：又因?yàn)镃ache容量

為128KB,8路組相聯(lián)，所以可以分為1024組(128KB/(8xl6B)=l024),對應(yīng)的組

號字段10位；剩下為標(biāo)記字段。1234567H=0001001為0110100010101100111,標(biāo)

記字段為高14位，00010010001101=048DH,故選C選項(xiàng)。歸納總結(jié)：組相聯(lián)映

像對應(yīng)的主存地址應(yīng)包活3個部分，即標(biāo)記(Tag)、組號(Index)和塊內(nèi)地址

(Offset)o解題技巧：首先將主存地址由十六進(jìn)制變成二進(jìn)制，其中塊內(nèi)地址字段

為最后4位，組號字段為中間10位，剩下的就是標(biāo)記字段，將標(biāo)記字段二進(jìn)制轉(zhuǎn)

換為十六進(jìn)制，即可得出結(jié)果。

34、設(shè)n是描述問題規(guī)模的正整數(shù)，下列程序片段的時間復(fù)雜度是()。y=0；

while(n>=(y+1)*(y+1))y++；

A、0(log2n)

B、0(n)

C>0(nlog2n)

D、0(石)

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：考查時間復(fù)雜度。該程序片段的基本語句為“y+十；”，設(shè)其執(zhí)行次數(shù)

為k次，則(k—l+l)*(k—l+l)Sn<(k+l)*(k+l),有k2snVk2+2*k+l,可知k為?

的線性函數(shù)，故時間復(fù)雜度為0(6)。

35、下列幾種類型的系統(tǒng)中，適合采用忙等待I/O的有()。I.專門用來控制單

I/O設(shè)備的系統(tǒng)口.運(yùn)行一個多任務(wù)操作系統(tǒng)的個人計(jì)算機(jī)用.作為一個負(fù)載很

大的網(wǎng)絡(luò)服務(wù)器的工作站

A僅

、I

B僅

、I、n

c僅

、□、m

D僅

、i、n、m

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：采用忙等待I/O方式，當(dāng)CPU等待I/O操作完成時，進(jìn)程不能繼續(xù)執(zhí)

行。對于I和n這兩種系統(tǒng)而言，執(zhí)行i/o操作時，系統(tǒng)不需要處理其他的事務(wù)，

因此忙等待I/O是合適的。而對于網(wǎng)絡(luò)服務(wù)器而言，它需要處理網(wǎng)頁的并發(fā)請求，

需要CPU有并行處理的能力，忙等待I/O不適合這種系統(tǒng)。

36、一個TCP連接下面使用128kbit/s的鏈路，其端到端時延為32ms。經(jīng)測試，發(fā)

現(xiàn)吞吐率只有60kbit/s。則其發(fā)送窗口是()。

A、904B

B、906B

C、452B

D、454B

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：數(shù)據(jù)分組的往返時延為：32x2=64ms；設(shè)發(fā)送窗口為x字節(jié)，則數(shù)據(jù)

報(bào)網(wǎng)絡(luò)傳輸時延為8x/(128xl()3)bit/s,依題意有：8x/(8x/(128x!03)+64xl0

3)=60x10—3,得x=904B。

37、設(shè)有如下兩個優(yōu)先級相同的進(jìn)程Pl和P2。信號量S1和S2的初值均為0,試

進(jìn)程P1:進(jìn)程P2：

y=3；x?2s

z-2：P(S1);

V(S1):x?x+2；

z?y+l：V(S2)?

P(S2)；z=x+z：

y?z+y：

A、4、8、11

B、4、6

C、6、8

D、4、8

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：這類題目其實(shí)不難，但這種題卻很容易答錯，原因就是很容易漏掉某

種情況。首先，將上述進(jìn)程分解成以下6個程序段：

PSI：y=3；PS2：z=y+l：PS3：y=z+y；

z=2；

PS4：x=2；PS5：x=x+2；PS6：z=x+z；

假設(shè)沒有PV操作的情況下。進(jìn)程并發(fā)執(zhí)行關(guān)系用前驅(qū)圖表示如圖7—7所示。加

入了PV操作后用前驅(qū)圖表示如圖7—8所示。由于x的值只有PS4、PS5決定，

且兩者順序關(guān)系確定，則易得x的值始終為4。又P2和團(tuán)共享的變量只有z,則

PS6與PSI、PS2、PS3的關(guān)系決定了最終的y和z的值。又根據(jù)進(jìn)程前驅(qū)圖得，

PS6在PS1之后。所以可能的情況有（PS4、PS5爐處的順序有多種情況，但都不

對最后結(jié)果產(chǎn)生影響，為了方便，我們統(tǒng)一把PS4、PS5放在PS1后面執(zhí)行）：

PSI、PS4、PS5、PS6、PS2、PS3；PSI、PS4、PS5、PS2.PS6、PS3：PS1、

PS4、PS5、PS2、PS3、PS6；這3種情況，計(jì)算過程如表7—2所示。

圖7.8加入PV操作后的前驅(qū)圖

?7-2計(jì)算過程

XyZXyzXyz

PS132PS132PSI32

PS42PS42PS42

PS54PS54PS54

PS66PS24PS24

PS24PS68PS37

PS37PS3iiPS68

4744n8478

綜上所述，z的值可能是4、8。

38、在PC-DOS中，某磁盤文件A與B,它們所占用的磁盤空間如下所示。試問

A、B文件在磁盤上各占（）簇。

FDT（文件目錄表）FAT（文件配置表》

A、3,3

B、4,5

C、5,3

D、5,4

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：當(dāng)查找文件在磁盤上的存放地址時，首先從目錄中找到文件的起始簇

號，然后再到FAT表的相應(yīng)表目中找到文件存放的下一個簇號，依此類推，直至

遇到值為FFF的表項(xiàng)為止。文件A在磁盤上占用5簇，簇號依次為002、004、

009、005、007o文件B在磁盤上占用3簇，簇號依此為003、008、006。知識點(diǎn)

回顧：鏈接分配中每個文件對應(yīng)一個盤塊的鏈表，盤塊分布在磁盤的任何地方。

鏈接方式可分為隱式鏈接和顯示鏈接兩種。隱式鏈接：在文件目錄的每個目錄項(xiàng)

中，都必須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。例如，目錄表中

有一個目錄項(xiàng)為（jeep,9,25）,表示jeep文件的第一個盤塊號是9,最后一個盤塊

號是25,而在每個盤塊中都含有一個指向下一個盤塊的指針，如

9一16—1-10—25。如果指針占用4B,對于盤塊大小為512B的磁盤，則每個盤

塊中只有508B可供用戶使用。顯示鏈接：把用于鏈接文件各物理塊的指針，顯示

地存放在內(nèi)存的一張鏈接表中。該表在整個磁盤僅設(shè)置一張。表的序號是物理盤塊

號，從0開始，直到N—1,其中N為盤塊總數(shù)。在每個表項(xiàng)中存放鏈接指針，即

下一個盤塊號。

39、圖的鄰接表存儲表示，數(shù)據(jù)元素之間的關(guān)系是（）。

A、線性結(jié)構(gòu)

B、樹形結(jié)構(gòu)

C、網(wǎng)狀結(jié)構(gòu)

D、無結(jié)構(gòu)

標(biāo)準(zhǔn)答案：A

知識點(diǎn)露析：根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：（1）

集合結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合（2）線性結(jié)構(gòu)。該結(jié)

構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。（3）樹型垢構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存

在著一對多的關(guān)系。（4）圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，

也稱網(wǎng)狀結(jié)構(gòu)。鄰接表（adjaccncyrlist）是圖的一種錐式存儲結(jié)構(gòu)。這種存儲表示法

類似于樹的孩子鏈表表示法。對于圖G中每個頂點(diǎn)vi,把所有鄰接于vi的頂點(diǎn)vj

鏈成一個單鏈表，這個單鏈表稱為頂點(diǎn)vi的鄰接表。每個頂點(diǎn)對應(yīng)一個相應(yīng)的鄰

接表故圖的鄰接表存儲表示，數(shù)據(jù)元素之間的關(guān)系是線性關(guān)系。

:哲學(xué)家進(jìn)餐問題的偽代碼如下J1J2/3是三根筷子?則（

PhP3：

P2t

while<1)(while(1)(while(1)(

p（n）iP(f3)i

P(f3)?P(f2)tP(f2)i

eat()1Eat()jEatOi

V((3)iV((2)iV(f2)i

V(f!)iV(flhV(f3)i

1})

A、可能死鎖，pl或p2或p3都有可能饑餓

B、不可能死鎖，但pl或p2或p3都有可能饑餓

C、不可能死鎖，但只有pl或p2有可能饑餓

D、不可能死鎖，但只有p2或p3有可能饑餓

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：pl、p2和p3不滿足死鎖的四個必要條件中的循環(huán)等待條件，故不可

能發(fā)生死鎖，排除A。設(shè)p3先申請到f3,若此時p2先于pl申請到fl,則此時p2

好和p3任意一個申請到f2都可執(zhí)行完畢，假設(shè)是p2中請到了f2執(zhí)行完畢，釋放

f2,fl,則p3可獲得f2執(zhí)行完畢，倘若p2緊接著又申請到了fl,p3執(zhí)行完后緊

接著又申請到了13；如此循環(huán)則pl始終沒有機(jī)會獲得處理機(jī)執(zhí)行而發(fā)生饑餓現(xiàn)

象。以此類推p2和p3都有可能發(fā)生饑餓現(xiàn)象。故選B。

二、綜合應(yīng)用題（本題共9題，每題7.0分，共9分0）

下圖所示為雙總線結(jié)構(gòu)機(jī)器的數(shù)據(jù)通路，IR為指令寄存器，PC為程序計(jì)數(shù)器（具有

自增功能），M為主存（受R/W信號控制），AR為地址寄存器，DR為數(shù)據(jù)緩沖寄

存器，ALU由加、減控制信號次定完成何種操作，控制信號G控制的是一個門電

路。另外，線上標(biāo)注有小圈表示有控制信號，例中yi表示y寄存器的輸入控制信

號，R1。為寄存器R1的輸出控制信號，未標(biāo)字符的線為直通線，不受控制。

A顯線