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

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

一、單選題(本題共40題，每題1.0分，共40分。)

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

j?intm){inti?temp；if(j<m){for(i=j?i<=n；i++)if(a[i]<a[j]){temp=a[i]；

a[j]=tcmp；}j++；order。，m)；//遞歸調(diào)用}}

A、0(n)

O(nlog2n)

C、O(n2)

D、0(i?)

標準答案：C

知識點解析：order。函數(shù)是一個遞歸排序過程，設(shè)T(n)是排序n個元素所需要的時

間。在排序n個元素時，算法的計算時間主要花費在遞歸調(diào)用。rder()上。第一次調(diào)

用時，處埋的元素序列個數(shù)為n―1,也就是對余下的n―1個元素進行排序，所

需要的計算時間應(yīng)為T(n—1)。又因為在其中的循環(huán)中，需要n—l次比較，所以

排序n個元素所需要的時間為T(n)=T(n—l)+n-1,n>l這樣得到如下方程：

T(l)=0T(n)=T(n—l)+n—1n>l求解過程為T(n)=|T(n-2)+(n-2)]+(n—1)=[T(n

-3)+(n-3)]+(n-2)+(n—1)=[T(l)+l]+2+...+n—1=0+l+2+...+n-1=n(n—1)/2

=0(n2)

2、在順序表的動態(tài)存儲定義中需要包含的數(shù)據(jù)成員是()。I.數(shù)組指針*data

II.表中元素個數(shù)n川.表的大小maxSizeW.數(shù)組基址base

A、I、口

B、I>n、w

c、i、口、m

D、全都需要

標準答案：C

知識點解析：首先，表的大小和表的元素個數(shù)是肯定需要的。其次，在順序表的動

態(tài)存儲定義中，它的存儲空間是通過執(zhí)行malloc或new動態(tài)分配的，所以不包括

數(shù)組基址。最后，數(shù)組的首地址需要數(shù)組指針data來存儲?？赡芤蓡桙c：數(shù)組首

址和數(shù)組基址貌似?樣，有什么區(qū)別？提示：數(shù)組基址指數(shù)組首地址在內(nèi)存中的真

實地址，即物理地址”既然是動態(tài)分配，自然就無法確定，所以就沒有必要納入其

數(shù)據(jù)成員。數(shù)組首址就是數(shù)組第一個元素的下標，通常情況下都是0。換句話說：

數(shù)組基址是一個全局的概念，首址是一個局部的概念。

3、向一個棧頂指針為head的帶頭結(jié)點的鏈棧中插入指針L所指的結(jié)點時，應(yīng)該執(zhí)

行()。

A、head一next=L

B、L—>next=head

C^L—*next=head;hcad—>next=L

D、L—next=head一next：head—next=L

標準答案：D

知識點解析?：此題表面上考查的是鏈棧的插入，其實與單鏈表的插入沒有什么兩

樣。既然是棧的插入，那么就是在棧頂進行操作，即考查的就是在單鏈表的頭結(jié)點

（指針head所指結(jié)點）后播入一個新的結(jié)點。該知識點在《數(shù)據(jù)結(jié)構(gòu)高分筆記》中

IInot

②heM-EI

己經(jīng)詳細地講解過了，操作如圖2-5所示。圖2.5fit枝的瓶入注

意：①和②的順序千萬不可顛倒，否則將斷鏈，導(dǎo)致操作失敗。

4、棧S和隊列Q的初始狀態(tài)皆為空，元素al、a2、a3、a4、a5和a6依次通過S

棧，一個元素出棧后即進入隊列Q,若6個元素出隊列的順序是a3、a4、a2、al、

a5、a6,則棧S至少應(yīng)該容納（）個元素。

A、6

B、4

C、3

D、2

標準答案：C

知識點解析：模擬一下入棧、出棧過程，如表2-5所示。選取模擬過程中棧內(nèi)元素

個數(shù)最大的值，便為該題答案，因此本題選C。

5、某平衡二叉樹的樹高為3,其根結(jié)點A左孩子的平衡因子為一1,右孩子的度

為0。在該平衡二叉樹口插入一個結(jié)點后造成了不平衡，則應(yīng)該進行（）型旋轉(zhuǎn)以使

其平衡。

A、LL或者RL

B、LR或者LL

C、RL或者RR

D、RR或者LL

標準答案：C

知識點解析：由題意可知，樹的結(jié)構(gòu)如圖2-6所示。由圖2—6可知，插入一個結(jié)

點造成根結(jié)點A的左孩子結(jié)點不平衡，說明這個結(jié)點一定是插在根結(jié)點A的左孩

子的右孩子上，如圖2-7所示。所以需要進行RL型或者RR型旋轉(zhuǎn)。

re2-7捅入一個針，點后的義利

6、在由4棵樹組成的森林中，第一、第二、第三和第四棵樹中的結(jié)點個數(shù)分別為

30、10、20、5,當把森林轉(zhuǎn)換成二叉樹后，對應(yīng)的二叉樹中根結(jié)點的左子樹中結(jié)

點個數(shù)為（）。

A、64

B、29

C、30

D、4

標準答案：B

知識點解析：當森林轉(zhuǎn)於成二叉樹后，根結(jié)點的左子樹其實就是原來第一棵樹除了

根結(jié)點的所有結(jié)點，所以二叉樹中根結(jié)點的左子樹中結(jié)點個數(shù)為29,故選B。

7、若一棵深度為6的完全二叉樹的第6層有3個葉子結(jié)點，則該二義樹共有（）個

葉子結(jié)點。

A、16

B、17

C、18

D、19

標準答案：B

知識點解析：首先根據(jù)每一層最多葉子結(jié)點的計算公式可知，完全二叉樹的第五層

有16（2、個葉子結(jié)點，題目說第6層有3個葉子結(jié)點，那么這3個葉子結(jié)點肯定要

占據(jù)第五層的2個葉子結(jié)點，第五層就只有14個葉子結(jié)點，然后再加上第六層的

3個葉子結(jié)點，所以一共有14+3=17個葉子結(jié)點。

8、用有向無環(huán)圖描述表達式(A+B)*((A+B)/A),至少需要頂點的數(shù)目為()。

A、5

B、6

C、8

D、9

標準答案：A

知識點解析：用圖2—8可以表示表達式，圖2-8中頂點表示參與運算的一種操作

數(shù)和運算符(注意是一種而不是一個)，用邊來確定各種運算以及運算優(yōu)先順序。

(A+B)*((A+B)/A)表達式中的運算符有3種,即操作數(shù)有兩種,

即“A”、“B”，因此圖2-8中頂點數(shù)至少為5o圖2-8中A與B結(jié)合運算符“+”做運

算，將所得結(jié)果與結(jié)合運算符做運算，上兩步的結(jié)果再結(jié)合運算符“”做運

算得到最終結(jié)果。本題比較靈活，屬于在掌握基礎(chǔ)后的能力擴展。

9、下列關(guān)于AOE網(wǎng)的敘述中，錯誤的是()。

A、關(guān)鍵活動延期完成必定影響整個工程的完成時間

B、關(guān)鍵路徑是AOE網(wǎng)中從起點到終點的最短路徑

C、所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成

D、一個AOE網(wǎng)的關(guān)鍵路徑可以有多條

標準答案：B

知識點解析：關(guān)鍵活動組成了關(guān)鍵路徑。關(guān)鍵路徑是從起點到終點的最長路徑，關(guān)

鍵路徑的長度代表整個工期的最短完成時間。關(guān)鍵活動延期完成，必將導(dǎo)致關(guān)鍵路

徑長度增加，即整個工期的最短完成時間增加，所以A正確。關(guān)鍵路徑實際上是

從源點到終點的最長路經(jīng)，而非最短路徑。這點很容易理解.，因為整個工程的工期

就是按照最長路徑長度計算出來的，即等于該路徑上所有活動的持續(xù)時間之和，所

以B錯誤。只有加快那些包括在所有關(guān)鍵路徑上的關(guān)鍵活動才能達到縮短工期的

目的，所以C正確。關(guān)健路徑并不唯一，可以有多條，所以D正確。注意：關(guān)鍵

路徑算法是以拓撲排序為基礎(chǔ)的。

10、為提高查找效率，對有65025個元素的有序順序表建立索引順序結(jié)構(gòu)，在最好

情況下查找到表中已有元素，需要執(zhí)行()次關(guān)鍵字比較。

A、10

B、14

C、20

D、21

標準答案：B

知識點解析：首先需要知道折半查找成功的平均查找長度為k)g2(n+l)?l。為使查

找效率最高，可對有65025個元素的有序順序表分塊，每塊有兩礪=255個元

素。為每一塊建立一個索引項，索引表共255個索引項。若對索引表和每一塊都采

用折半查找，則查找效率最高，計算可得

ASLindexSeqSearch=ASLindex+ASLBlock=log2(255+1)1l+log2(255+l)―-1=14下面補充

一些關(guān)于折半查找的概念。補充(1)：折半查找的時間復(fù)雜度為O(log2n)。補充

(2)：折半查找是基于隨機存儲方式的算法，必須用順序表而不能用鏈表。補充

(3)：對于折半查找，假設(shè)h表示判定樹的高度，如果有n個元素，則判定樹的高

度為h=[log2(n+1)]或者h=[log2(n+l)]+l

11、對于序列(32,47,12,8,2,19,30),其堆頂元素最小的初始堆是()。

A、(2,8,12,32,47.19,30)

B、(2,8,12,19,30：32,47)

C、(2,12,8,32,19,47,30)

D、(2,12,8,30,19.32,47)

標準答案：A

所示。圖2-9序列對龍的景小雄畫U過目因

此，最后結(jié)果為(2,8,12,32,47,19,30)。補充：堆調(diào)整過程從無序序列所

確定的完全二叉樹的第一個非葉子結(jié)點開始，從右至左、從下至上，對每個結(jié)點進

行調(diào)整，最終將得到一個小頂堆。

12、CPU的CPI與下列哪個因素有關(guān)？()I.時鐘頻率H.系統(tǒng)結(jié)構(gòu)m.指令集

A、僅I、n

B、僅I、in

c、僅u、m

D、I、II和in

標準答案：c

知識點解析：CPI是執(zhí)行一條指令所需要的時鐘周期數(shù)，系統(tǒng)結(jié)構(gòu)、指令集、計算

機組織等都會影響CPI,而時鐘頻率并不會影響到CPI,但可以加快指令的執(zhí)行速

度.如執(zhí)行一條指令需要5個時鐘周期，則主頻大的CPU執(zhí)行這條指令要比主頻

小的CPU快。

13、n+I位的定點小數(shù)，其補碼表示范圍是()。

A、-l<x<l-2'n

B、一1<X<1—2-n

C、一1<X<1—2'n

D、一1<X<1—2'n

標準答案：A

知識點解析：各種編碼下的數(shù)值范圍總結(jié)如表2-6所示。

囊29各科螭碼依值范81總結(jié)

崎蚪”式?小但■科?小便Al大伏垢利?大值

Ml0上符號定點?⑹000...0000Ill-Ill2-'-|

n*l位JL符號堂點小數(shù)0.00..0000on...in1-2-0?Sx?l-2"

。1位定點祭故傣研iuio.ni-2,41OIII...Ill2,1

ml位定且小散發(fā)叫i.in-inOlli...IllI-2-*?IHWxW卜2f

*1W定6尊數(shù)乃科1000000-r0III...III2,12"<?e￡r-l

印|付定6小數(shù)韓研1000.000-1Olli--tili-r*ICM?I-I',

Ml健證**數(shù)辰科1000.000-2**l0111-III2,11

?*1位定點小數(shù)反碼1000ooo?1*2**OIII...Ill1-2--l*2-Cx<|-2a

**1位企力，戶數(shù)杼料0000.000ini^in2,1

。八位定點小數(shù)移碼小散沒有將科定義

14、有一主存-Cache層次的存儲器，其主存容量為1MB（按字節(jié)編址），Cache容量

為16KB,每字塊有8個字，每字為32位，采用直接地址映像方式。若主存地址

為35301H,且CPU訪問Cache命中,則在Cache的第（）號字塊（Cache字塊號從0

開始）。

A、152

B、153

C、154

D、151

標準答案：A

知識點解析：首先將主存地址35301H寫成二進制，即00110101001100000001,

然后主要分析該主存地址哪些位才是Cache字塊地址。低位是塊內(nèi)地址，高位是主

存字塊標記位，所以中間的部分就是Cache字塊地址；題目中給出每字塊有8個

字，每字為32位，所以每字塊的大小為32B,故塊內(nèi)地址需要低5位來表示。另

外，要求主存字塊標記位，只需求主存包含了多少個Cache即可，1MB/

16KB=64,所以需要6位來表示主存字塊標記位，二進制地址就劃分為如下格式：

00110101001100000001（主存字塊標記位）（Cache字塊地址）（塊內(nèi)地址）010011000

的十進制數(shù)為152,所以選A。

15、下列的說法正確的是（）。I.高位多體交叉存儲器能很好地滿足程序的局部

性原理n.高位四體交叉存儲器可能在一個存儲底期內(nèi)連續(xù)訪問4個模塊HI.雙

端口存儲器可以同時對同一區(qū)間、同一單元進行寫操作

A、僅I、m

B、僅口、出

C、僅皿

D、僅口

標準答案：D

知識點解析：I：高位多體交叉存儲器由于是在單個存儲器中將字連續(xù)存放的，所

以不能保證程序的局部性原理；而低位多體交叉存儲器由于是交叉存放的，所以能

很好地滿足程序的局部性原理，故I錯誤。n：高位四體交叉存儲器雖然不能滿

足程序的連續(xù)讀取，但是仍然有可能一次連續(xù)讀出彼此地址相差一個存儲體容量的

4個字。雖然概率比較小，但是也非不可能，所以II正確。n：雙端口存儲器雖然

具有兩套獨立讀/寫端口，且具有各自的地址寄存器和譯碼電路，但是仍然不能同

時對同一區(qū)間、同一單元進行寫操作。因為當有一方進行寫時，忙標志位將會阻止

BUSY^-BUSY”

另一方訪問（見圖2/0）,所以HI錯誤。圖雙浦u存儲港擴

展：雙端口存儲器可以同時對同一區(qū)間、同一單元進行讀操作。另外，一方讀一方

寫也不能同時對同一區(qū)間、同一單元進行操作，否則將會發(fā)生沖突?？傊?，只要有

寫操作，就不能同時進行。

16、地址總線為A15（高位）?A0（低位），若用1KX4位的存儲芯片組成4KB的存儲

器，地址總線的高位做片選信號，則以下說法正確的是（）。I.加在各存儲芯片

上的地址線是All?AO口.加在各存儲芯片上的地址線是A9?AODI.一共需要

使用8片1KX4位的存儲芯片W.一共需要使用4片1KX4位的存儲芯片

A、I、田

B、口、W

c>n>m

D、I、W

標準答案：c

知識點解析：首先要用1KX4位的存儲芯片組成4KB（即4K.x8位）的存儲器，需

要進行字位一起擴展由公式可知，共需要的芯片數(shù)為（4Kx8位）/（1KX4位）=8,所

以m是正確的。另外，加在各存儲芯片上的地址線只與存儲芯片的存儲容量有關(guān)，

本題芯片的存儲容量為1K,又因為21°=1K,所以選取地址線的10位A9?A。作

為各個存儲芯片上的地址線。

17、下列說法正確的是（）。I.某加法指令，在指令的地址碼中給出了存儲器地

址，則此指令在執(zhí)行周期一定訪問存儲器U.零地址雙操作數(shù)指令不需要指出操

作數(shù)地址HI.在一地址格式的指令中，只有一個操作數(shù)

A、僅n、m

B、僅i、n

c、僅i、m

D、i、n和in

標準答案：B

知識點解析：I：既然指令碼給出了存儲器地址，無論此地址是源操作數(shù)地址，還

是目的操作數(shù)地址，執(zhí)行周期都需要根據(jù)此地址訪問存儲器，所以I正確。D：

零地址雙操作數(shù)指令不需要指出操作數(shù)地址，因為操作數(shù)的地址隱含在堆棧指針

中，所以n正確。n：一地址指令應(yīng)該分為兩種情況來討論：（1）進行單目運算（只

需要一個操作數(shù)的運算，如白增、求反等操作）的一些操作，也就是說只有目的操

作數(shù)的單操作數(shù)指令，按指令地址字段給出的地址讀取操作數(shù)，最后將執(zhí)行結(jié)果存

回源地址。（2）將目的地址隱含的雙操作數(shù)指令，先按指令地址碼給出的地址讀取

源操作數(shù)，而另一個操作數(shù)由AC提供，運算結(jié)果也將存放在AC中。綜上所述，

在一地址格式的指令中，可能有一個操作數(shù)，也可能有兩個操作數(shù)，所以m錯誤。

18、為了縮短指令中某個地址段的位數(shù)，有效的方法是采?。ǎ?/p>

A、立即尋址

B、變址尋址

C、間接尋址

D、寄存器尋址

標準答案：D

知識點露析：題目要求縮短某個地址段的位數(shù)，因此首先想到的就是寄存器尋址。

由于計算機中寄存器的數(shù)量一般很少，采用寄存器尋址時可用少量的代碼來指定寄

存器，這樣可以減少對應(yīng)地址段的代碼位數(shù)，也可減少整個指令的代碼長度。其余

的立即尋址中地址字段需要存儲一個操作數(shù)，有可能會增長位數(shù)：變址尋址

EA=A+（IX）,其中的A仍然和主存有一定關(guān)系；間接尋址中存放的仍然是一個主

存地址。知識點擴展：常見指令尋址方式特點總結(jié)。（1）立即尋址：操作數(shù)獲取便

捷。通常用于給寄存器賦初值。（2）直接尋址：相對于立即尋址，縮短了指令長

度。（3）間接尋址；擴大尋址范圍，便于編制程序，易于完成子程序返回。（4）寄存

器尋址：指令字較短，指令執(zhí)行速度較快。（5）寄存器間接尋址：擴大尋址范圍。

（6）基址尋址：擴大操作數(shù)尋址范圍，適用于多道程序設(shè)計，常用于為程序或數(shù)據(jù)

分配存儲空間。（7）變址尋址：主要用于處理數(shù)組問題，適合編制循環(huán)程序。（8）相

對尋址：控制程序的執(zhí)行順序、轉(zhuǎn)移等。（9）基址尋址和變址尋址的區(qū)別：兩種方

式有效地址的形成都是寄存器內(nèi)容+偏移地址，但在基址尋址中，程序員操作的是

偏移地址，基址寄存器的內(nèi)容由操作系統(tǒng)控制，在執(zhí)行過程中是動態(tài)調(diào)整的；而在

變址尋址中，程序員操作的是變址寄存器，偏移地址是固定不變的。

19、下列說法正確的是（）。I.微程序控制方式和硬布線方式相比較，前者可以

使指令的執(zhí)行速度更快U.若采用微程序控制方式，則可用"C取代PCHI.控

制存儲器可以用ROM實現(xiàn)W.指令周期也稱為CPU周期

A、I、m

B、II、in

c、只有川

D、i、m、w

標準答案：c

知識點解析?：i：可以這樣來理解，微程序控制方式是用軟件方式來實現(xiàn)指令執(zhí)

行，而硬布線方式則是采用硬件方式來實現(xiàn)指令執(zhí)行。當一個命令信號到來時，硬

布線控制器方式下，命令信號只需要通過一些門電路，就可以快速產(chǎn)生有效的控制

信號來控制部件完成操作，因此速度較快，所以I錯誤。n："c必然無法取代

PC,"C只是在微程序中指向下一條微指令地址的寄存器，只要熟悉微程序的執(zhí)

行過程，便可以很容易得知：當一條指令執(zhí)行時，分派給微程序部件來進行具體操

作，而這個操作僅僅是限于這條指令的內(nèi)部，它無法得知整個程序是什么樣，因此

它也必然不可能知道這段微程序執(zhí)行完畢后，下一條是什么指令，所以口錯誤。

m：由于每一條微指令執(zhí)行時所發(fā)出的控制信號是事先設(shè)計好的，不需要改變，所

以存放所有控制信號的存儲器應(yīng)為只讀存儲器，并將其集成到CPU內(nèi)，稱其為控

制存儲器(簡稱控存)，故in正確。iv：指令周期是從一條指令的啟動到下一條指令

啟動的間隔時間，CPU周期是機器周期(通常使用內(nèi)存中讀取一個指令字的最短時

間來規(guī)定CPU周期)，是指令執(zhí)行中每一步操作所需的時間，所以w錯誤。

20、下列部件中屬于控制部件的是()。I.指令寄存器n.操作控制器nr.程序

計數(shù)器w.狀態(tài)條件寄存器

A、僅I、m、w

B、僅I、u、m

c、僅I、n、w

D、I、u、in和w

標準答案：B

知識點解析：CPU控制器主要由3個部件組成：指令寄存器、程序計數(shù)器和操作

控制器。狀態(tài)條件寄存器通常屬于運算器的部件，保存由算術(shù)指令和邏輯指令運行

或測試的結(jié)果建立的各種條件碼內(nèi)容，如運算結(jié)果進位標志(C)、運算結(jié)果溢出標

志(V)、運算結(jié)果為零標志(Z)、運算結(jié)果為負標志(N)、中斷標志⑴、方向標志(D)

和單步標識等。注意；存儲器、運算器、外部設(shè)備等都屬于執(zhí)行部件。知識點擴

展：操作控制器總結(jié)。操作控制器(OC)的功能就是根據(jù)指令操作碼和時序信號，

產(chǎn)生各種操作控制信號：以便正確地建立數(shù)據(jù)通路，從而完成取指令和執(zhí)行指令的

控制。CPU內(nèi)的每個功能部件都完成一定的特定功能。然而信息怎樣才能在各部

件之間傳送呢?也就是說，數(shù)據(jù)的流動是由什么部件控制的呢?通常把許多數(shù)字部件

之間傳送信息的通路稱為“數(shù)據(jù)通路信息從什么地方開始，中間經(jīng)過哪個寄存器

或多路開關(guān)，最后傳到哪個寄存器，都要加以控制。在各寄存器之間建立數(shù)據(jù)通路

的任務(wù)是由稱為“操作控制器”的部件來完成的。操作控制器中主要有節(jié)拍脈沖發(fā)

生器、控制矩陣、時鐘脈沖發(fā)生器、復(fù)位電路和啟停電路等控制邏輯。這幾個部件

對微處理器設(shè)計人員來說很關(guān)鍵，但微處理器用戶卻可以不必過多關(guān)心。

21、下列關(guān)于總線仲裁方式的說法中，正確的是()，I.計數(shù)器定時查詢方式

下，有一根總線請求(BR)線和一根設(shè)備地址線，如果每次計數(shù)器從。開始計，則設(shè)

備號大的優(yōu)先級高口.計數(shù)器定時查詢方式下，有一根總線請求(BR)線和一根設(shè)

備地址線，如果每次計數(shù)器從當前設(shè)備開始計，則設(shè)備號小的優(yōu)先級高m.分布

式仲裁控制邏輯分散在總線各部件中，不需要中央仲裁器

僅In

A、、

僅n

B、m

僅I

、、

C僅n

D、IIn

標準答案：B

知識點解析：I和HI：計數(shù)器定時模式下，有n個I/O接口，就需要有l(wèi)og2n根

設(shè)備地址線，工作原理是：假設(shè)有8個I/O設(shè)備，此時就需要3根設(shè)備地址線，

并且3根設(shè)備地址線與這8個設(shè)備都相連；當有設(shè)備請求總線時（不管有多少個設(shè)

備請求），BR線中產(chǎn)生信號，觸動計時器，此時計時器從0開始，通過設(shè)備地址線

發(fā)送一一進制信號，3根線中信號逐步變化：000、001、010、…當設(shè)備檢測到設(shè)備

線中信號與該設(shè)備編號相同時，該設(shè)備獲得總線控制權(quán)，進行總線操作；當該設(shè)備

操作結(jié)束后，若仍有其，’也設(shè)備在請求，則計數(shù)器要么從。開始重新計數(shù)，要么從當

前設(shè)備開始計數(shù)……依次進行。如果每次計數(shù)器從0開始，肯定導(dǎo)致設(shè)備號小的

優(yōu)先級最高。如果每次計數(shù)器從當前設(shè)備開始計數(shù)，則每個設(shè)備的優(yōu)先級是一樣

的。所以I、II都錯誤。m：分布式仲裁控制邏輯分散在總線各部件中，不需要

中央仲裁器，所以HI正確。

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

設(shè)備接口控制器送給CPU的中斷向量表（中斷向量表存放中斷向量）的指針是

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

入口地址為（）。

A、0800H

B、0801H

C、1200H

D、1201H

標準答案：C

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

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

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

23、在下列操作系統(tǒng)的各個功能組成部分中，一定需要專門硬件配合支持的是（）。

I.地址映射n.進程調(diào)度W.中斷系統(tǒng)W.系統(tǒng)調(diào)用

A、I

B、I、川

C、I、皿、IV

D、口、m

標準答案：B

知識點解析：有人可能會這樣理解，任何功能都是在硬件的基礎(chǔ)上實現(xiàn)的，所以都

是需要硬件支持的。但這里肯定不是這個意思，這里需要專門硬件支持的意思是，

除了處理機和內(nèi)存以外，為了實現(xiàn)該功能，需要另外添加的專門用于實現(xiàn)該功能的

硬件。I是，地址映射是需要硬件機構(gòu)來實現(xiàn)的。例如，在分頁儲存系統(tǒng)中，需

要一個頁表寄存器，在其中存放頁表在內(nèi)存的始址和頁表的長度。除此之外，當

進程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址變換機構(gòu)（它是硬件）會自動將有效

地址（相對地址）分為頁號和頁內(nèi)地址兩部分，再以頁號為索引去檢索頁表。查找操

作是由硬件執(zhí)行的。n不是，進程調(diào)度是通過使用一些調(diào)度算法來編程實現(xiàn)的，

所以不需要專門硬件支待。HI是，CPU硬件有一條中斷請求線（IRL）。CPU在執(zhí)行

完每條指令后，都將判斷IRL。當CPU檢測到已經(jīng)有中斷控制器（即中斷源）通過中

斷請求線發(fā)送了信號時，CPU將保留少量狀態(tài)（如當前指令位置），并且跳轉(zhuǎn)到內(nèi)存

特定位置的中斷處理程序。這里的中斷控制器是硬件。中斷系統(tǒng)離開中斷控制器是

不可能工作的。w不是，對于系統(tǒng)調(diào)用是否一定需要專門的硬件這個問題，需要

清楚系統(tǒng)調(diào)用的過程。在C程序中調(diào)用系統(tǒng)調(diào)用好像是一般的函數(shù)調(diào)用，實際上

調(diào)用系統(tǒng)調(diào)用會引起用戶態(tài)到核心態(tài)的狀態(tài)變化，這是怎么做到的呢？原來C編譯

程序采用一個預(yù)定義的函數(shù)庫（C的程序庫），其中的函數(shù)具有系統(tǒng)調(diào)用的名字，從

而解決了在用戶程序中請求系統(tǒng)調(diào)用的問題。這些庫函數(shù)一般都執(zhí)行一條指令，該

指令將進程的運行方式變?yōu)楹诵膽B(tài)，然后使內(nèi)核開始為系統(tǒng)調(diào)用執(zhí)行代碼，稱這個

指令為操作系統(tǒng)陷入（OperatingSystemTrap）。系統(tǒng)調(diào)用的接口是一個中斷處理程

序的特例。在處理操作系統(tǒng)陷入時：（1）內(nèi)核根據(jù)系統(tǒng)調(diào)用號查系統(tǒng)調(diào)用入口表，

找到相應(yīng)的內(nèi)核子程序的地址。（2）內(nèi)核還要確定該系統(tǒng)調(diào)用所要求的參數(shù)個數(shù)。

⑶從用戶地址空間復(fù)制參數(shù)到U區(qū)（UNIXV）。（4）保存當前卜下文，執(zhí)行系統(tǒng)調(diào)用

代碼。（51恢復(fù)處理機現(xiàn)場并返回。上述（I）?（3）過程和（5）過程都不需要專門的硬

件（除了CPU和內(nèi)存），只有第（4）過程可能需要專門硬件，如顯示器輸出字符。但

也可以不需要專門硬件，如打開一個已經(jīng)在緩存中的文件。綜上所述，本題選

Bo

24、下列說法中，正確的說法有（）個。I.當進程申請CPU得不到滿足時，它將

處于阻塞狀態(tài)。n.當進程由執(zhí)行變?yōu)榫途w狀態(tài)時，CPU現(xiàn)場信息必須被保存在

PCB中。n.一一個進程的狀態(tài)發(fā)生變化總會引起其他一些進程的狀態(tài)發(fā)生變

化。

A、0

B、1

C、2

D、3

標準答案：B

知識點解析：當進程申請CPU得不到滿足時，它處于就緒狀態(tài)；當因I/O等待

時，處于阻塞狀態(tài)，因此I錯誤。當進程由執(zhí)行變?yōu)榫途w狀態(tài)時，為了使下次進

程調(diào)度時進程可以繼續(xù)從暫停的地方開始運行，CPU現(xiàn)場信息必須被保存在PCB

中，因此n正確。一個進程的狀態(tài)發(fā)生變化并非總會引起其他一些進程的狀態(tài)發(fā)

生變化。例如，一個進程等待的I/O數(shù)據(jù)到來后，它將從阻塞態(tài)變?yōu)榫途w態(tài)，但

這時其他進程的狀態(tài)可能并不會發(fā)生變化，因此111錯誤。綜上，正確的說法有1

個，所以本題選B。

25、將“I/O為主”的進程定義為：當此類進程單獨運行時，用于I/O處理的時間

遠遠多于處理機的處理時間。將“計算為主''的進程定義為：當此類進程單獨運行

時，處理機的處理時間遠遠多于處理的時間。若系統(tǒng)中運行的主要是這兩類進程，

采用（）調(diào)度算法更有利于資源的利用率。

A、先來先服務(wù)

B、短作業(yè)（進程）優(yōu)先

C、時間片輪轉(zhuǎn)

D、多級反饋隊列

標準答案：D

知識點解析：以I/O為主的進程，如果采片］時間片調(diào)度算法，勢必導(dǎo)致CPU利

用率的下降。對于計算為主的進程，如果采用純優(yōu)先調(diào)度算法，可能會導(dǎo)致進程平

均周轉(zhuǎn)時間變長。因此正確答案是采用多級反饋隊列輪轉(zhuǎn)法進程調(diào)度算法。所謂

多級反饋隊列輪轉(zhuǎn)法就是把就緒進程按優(yōu)先級排成多個隊列，并賦給每個隊列不同

的時間片，高優(yōu)先級進程的時問片比低優(yōu)先級進程的時間片小。調(diào)度時先選擇高優(yōu)

先級隊列的第一個進程，使其投入運行，當該進程時間片用完后，若高優(yōu)先級隊列

中還有其他進程，則按照輪轉(zhuǎn)法依次調(diào)度執(zhí)行，否則轉(zhuǎn)入低一級的就緒隊列。只有

高優(yōu)先級就緒隊列為空時，才從低一級的就緒隊列中調(diào)度進程執(zhí)行。此種方法既照

顧了時間緊迫的進程，又兼顧了短進程，同時考慮了長進程，是一種比較理想的進

程調(diào)度方法。因此本題選D。

26、在某個十字路口，卷個車道只允許一輛汽車通過，且只允許直行、左拐和右

拐，如圖2—1所示。如果把各個方向的車看成進程，則需要對這些進程進行同

步，那么這里臨界資源個數(shù)應(yīng)該為（）。

A、1

B、2

C、4

D、不確定

標準答案：C

知識點解析：如圖2—11所示，直行的車輛需要獲得該方向上的兩個鄰近的臨界

資源。例如，北方開來的車輛需要獲得1、2兩個臨界資源，南方開來的車的需要

獲得3、4兩個臨界資源。圖2小十字路口乍退，意圖「）北方來車右轉(zhuǎn)的情況需要獲得

1這個臨界資源，左轉(zhuǎn)的情況需要獲得1、2、3臨界資源。所以每個方向來車有3

種不同的進程，4個方向有12種不同的進程。也可以用排除法來做該題，該路口

可以有南北方向的車同時直行，所以臨界資源個數(shù)大于或等于2,排除A。該路口

可以4個方向的車都左轉(zhuǎn)，所以臨界資源個數(shù)大于或等于4,排除B。D選項一般

不會選，所以選C。

27、考慮一個由4個進程和一個單獨資源組成的系統(tǒng)，當前的最大需求矩陣和分配

1

矩陣如下：SI【2J對于安全狀態(tài)，需要的最小資源數(shù)目是（）。

A、1

B、2

C、3

D、5

標準答案：C

知識點解析：依次用P1?P4來表示4個進程。從矢巨陣可以看出，4個進程還需

要的資源數(shù)目為（2,1,6,5）,按所需資源數(shù)目從小到大排列，即P2、Pl、P4、

P3。這就是所需最小資源數(shù)目的執(zhí)行順序。設(shè)有x個可用資源。當XN1時，P2可

以執(zhí)行完成，并釋放占用資源，此時資源數(shù)為x+l0當乂+自2時,，P1可以執(zhí)行完

成，并釋放占用資源，此時資源數(shù)為x+2。當x+2及時，P4可以執(zhí)行完成，并釋

放占用資源，此時資源數(shù)為x+4。當x+4次時，P3可以執(zhí)行完成，并釋放占月資

源，此時費源數(shù)為（忽略）。剩下的，就是解這個簡單的方程組，得出xN3。按這種

方法做題，可以比較有把握不算錯，也利于檢杳。

28、已知系統(tǒng)為32位實地址，采用48位虛擬地址，頁面大小4KB,頁表項大小

為8B；每段最大為4GB。假設(shè)系統(tǒng)使用純頁式存儲，則要采用（），頁內(nèi)偏移為（）

位。

A、3級頁表，12

B、3級頁表，14

C、4級頁表，12

D、4級頁表，14

標準答案：C

知識點解析：頁面大小為4KB,故頁內(nèi)偏移為12位。系統(tǒng)采用48位虛擬地址，

故虛頁號為48-12=36位。當采用多級頁表時，最高級頁表項不能超出一頁大?。?/p>

每頁能容納頁表項數(shù)為4KB/8B=51.2=27,36/9=4故應(yīng)采用4級頁表，最高級

頁表項正好占據(jù)一頁空間，所以本題選C。

29、某系統(tǒng)有4個頁框，某個進程頁面使用情況如表2-1所示。

?2-1某個迸程頁面使用情況

卜.次川用時間R<4)M(ett)

012627900

12302M10

212027211

31602W11

請問采用

FIFO置換算法將會替換的頁的頁號為（）。采用LRU置換算法將會替換的頁的頁號

為（）。采用簡單CLOCK置換算法將會替換的頁的頁號為（）。采用改進型CLOCK

置換算法將會替換的頁的頁號為（）。

A、1、3、2、0

B、3、2、0、1

C、2、1、0、0

D、3、1、0、

標準答案：C

知識點解析?：FIFO置換算法選擇最先進入內(nèi)存的頁面進行替換。由表中裝入時間

可知，第2頁最先進入內(nèi)存，所以FIFO置換算法選擇第2頁替換。LRU國換算法

選擇最近最長時間未使用的頁面進行替換。由表中上次引用時間可知，第1頁是最

長時間未使用的頁面，所以LRU置換算法將選擇第1頁替換。簡單CLOCK置換

算法從上一次位置開始掃描，選擇第一個訪問位為0的頁面進行替換。由表中

R（讀）標志位可知，依次掃描1、2、3、0,頁面。未被訪問，掃描結(jié)束，所以簡單

CLOCK置換算法將選搭第。頁替換。改進型CLOCK置換算法從上一次位置開始

掃描，首選的置換頁面是既未使用過的，又未修改的頁面。由表中R（讀）標志位和

M（修改）標志位可知，只有頁面。滿足R=0和M=0,所以改進型CLOCK置換算法

將選擇第0頁置換。

30、有某個操作系統(tǒng)對外存分配采用混合索引分配方式。在索引節(jié)點中包含了文件

的物理結(jié)構(gòu)數(shù)組iaddr[12],其中前10項iaddr[O]?iaddr⑼為直接地址，iaddr[IO]

為一次間接地址，iaddrlll]為二次間接地址。如果系統(tǒng)的塊的大小是4KB,磁盤的

每個扇區(qū)也為4KB。描述磁盤塊的數(shù)據(jù)項需要4B,其中1B標識磁盤分區(qū)，3B標

識物理塊號。該文件系統(tǒng)支持的最大文件是（）。

A、4GB

B、8GB

C、40KB+4MB+4GB

D、40KB+4MB+8GB

標準答案：C

知識點解析：磁盤塊大小為4KB,每個磁盤塊要4B,則一一個磁盤塊可以存放

1K個磁盤塊號。直接地址的文件長度為10x4KB=40KB；一級間址時的文件長度

1KX4KB=4MB；二級問址時的文件長度為1KX1KX4KB=4GB；所以，該文件系統(tǒng)

支持的最大文件是40KB+4MB+4GB。

31、某個磁盤系統(tǒng)采用最短尋道時間優(yōu)先(SSTF)磁盤調(diào)度算法，假設(shè)有一個請求柱

面讀寫磁盤請求隊列如下：7、136、58、100、72,當前磁頭位置是80柱面。請

問，磁盤總移動距離是()。

A、80

B、136

C、229

D、244

標準答案：C

知識點解析：表2—7所示是磁盤移動距離。

*2-7磁窗移動距離

。前?道仲農(nóng)72100IM杵的

?20

7214q14

5t-51y?42-42

100qV?36

1)6?y

l*y129.根據(jù)

SSTF磁盤調(diào)度算法,相應(yīng)請求順序為72、58、100、136、7。因此，總的移動距

離是8+14+42+36+129=229。此類問題的做法是：按照請求磁道的大小順序排列，

然后算出兩個方向上最近磁道的距離，決定磁頭移動方向即可。

32、下面關(guān)于設(shè)備屬性的敘述中，正確的是()。

A、字符設(shè)備的基本特征是可尋址到字節(jié)，即能指定輸入的源地址或輸出的目標地

址

B、共享設(shè)備必須是可尋址的和可隨機訪問的設(shè)備

C、共享設(shè)備是指同一時間內(nèi)允許多個進程同時訪問的設(shè)備

D、在分配共享設(shè)備和獨占設(shè)備時都可能引起進程死鎖

標準答案：B

知識點解析：字符設(shè)備的特征是不可尋址，即輸入/輸出時不能指定數(shù)據(jù)的輸入源

地址及輸出的目標地址。因此A錯誤。B敘述正確。共享設(shè)備是指在一段時間內(nèi)

允許多個進程同時訪問的設(shè)備，但不是同一時間同時訪問，因此C錯誤。分配共

享設(shè)備和獨占設(shè)備不會引起進程死鎖，因此D錯誤。

33、關(guān)于OSI參考模型和TCP/IP模型在網(wǎng)絡(luò)層和傳輸層提供的服務(wù)，正確的是

()°

A、OSI參考模型在網(wǎng)絡(luò)層提供無連接和面向連接服務(wù)，在傳輸層僅提供面向連接

服務(wù)

B、TCP/IP模型在網(wǎng)絡(luò)層僅提供無連接服務(wù)，在傳輸層僅提供面向連接服務(wù)

C、OSI參考模型在網(wǎng)絡(luò)層和傳輸層均可提供無連接和面向連接服務(wù)

D、TCP/IP模型在網(wǎng)絡(luò)層提供無連接和面向連接服務(wù)，在傳輸層僅提供面向連接

服務(wù)

標準答案：A

知識點解析：OSI參考模型和TCP/IP模型的特性對比，如表2-8所示。

?24OSI參考模里相TCP/IP模型的特性對比

OSI,號幔年

①，個％咎*急：接口、的或

①&衣明第1“分”務(wù).楂林試

②產(chǎn)生。町收發(fā)明2前

③產(chǎn)生在靜試發(fā)明之何

③（不J6S肥）

④共有?依

同Q層,

同絡(luò)笈?AR和（屋樓

傳?炭，而同遑檢和包植

的?叢：儀有向自殘找

34、一個傳輸數(shù)字信號的模擬信道的信號功率是0.62W,噪聲功率是0.02W,

頻率范圍為3.5?3.9MHz,該信道的最高數(shù)據(jù)傳輸速率是（）。

A、1Mbit/s

B、2Mbit/s

C、4Mbit/s

D、8Mbit/s

標準答案：B

知識點解析：首先計算信噪比S/N=0.62/0.02=31；帶寬W=3.9MHz一

3.5MHz=0.4MHz,由香農(nóng)公式可知最高數(shù)據(jù)傳輸率V=Wx]og2（l+S/

N）=0.4xlog2（l+31）Mbit/s=2Mbit/s?提示：這道題目題干說得很清楚,是有噪

聲的信道，所以第一個想到的應(yīng)該是香農(nóng)公式；如果題干說是無噪聲信道，則應(yīng)該

想到奈奎斯特定理。補充知識點：關(guān)于香農(nóng)公式和奈奎斯特定理的總結(jié)。提示：

具體的信道所能通過的頻率范圍總是有限的（因為具體的信道帶寬是確定的），所以

信號中的大部分高頻分量就過不去了，這樣在傳輸?shù)倪^程中會衰減，導(dǎo)致在接收端

收到的信號的波形就失去了碼元之間的清晰界限，這種現(xiàn)象叫做碼間串擾.所以需

要找到在不出現(xiàn)碼問串況的前提下，碼元傳輸速率的最大值是多少（因為找到了最

大值既滿足了最大傳輸率，也滿足了不出現(xiàn)碼問串擾），奈奎斯特就在采樣定理和

無噪聲的基礎(chǔ)上，提出了奈式準則。而奈奎斯特定理的公式為Cmax=f采樣

xlog2N=2fxlog2N（其中f表示帶寬）介紹香農(nóng)定理之前先介紹信噪比，首先要清楚

噪聲的影響是相對的，也就是說信號較強，那么噪聲的影響就相對較?。▋烧呤峭?/p>

時變化的，僅考慮兩者之一是沒有任何意義的），所以求信號的平均功率和噪聲的

平均功率之比（記為S/N）才有意義,故引入信噪比=1Oxlogio（S/N）（dB）。引入信

噪比之后就得出香農(nóng)公式：Cmax二Wxlog2（"S/N）（bil/s）式中，W為信道的帶

寬，所以說耍想提高信息的傳輸速率，應(yīng)設(shè)法提高傳輸線路的帶寬或者設(shè)法提高所

傳信號的信噪比。

35、CSMA協(xié)議可以利用多種監(jiān)聽算法來減小發(fā)送沖突的概率，下面關(guān)于各種監(jiān)

聽算法的描述中，錯誤的是（）。I.非堅持型監(jiān)聽算法有利于減少網(wǎng)絡(luò)空閑時間

口.1一堅持型監(jiān)聽算法有利于減少沖突的概率ni.P—堅持型監(jiān)聽算法無法減少

網(wǎng)絡(luò)的空閑時間IV.1一堅持型監(jiān)聽算法能夠及時搶占信道

A、I>n、w

B、n5m

C、I、U、IV

D、n、w

標準答案：A

知識點解析：按總線爭用協(xié)議來分類，CSMA有以下3種類型。（1）非堅持

CSMA：一個站點在發(fā)送數(shù)據(jù)幀之前，先要對信道進行檢測。如果沒有其他站點在

發(fā)送數(shù)據(jù)，則該站點開始發(fā)送數(shù)據(jù)。如果信道被占用，則該站點不會持續(xù)監(jiān)聽信

道，而等待一個隨機的延遲時間之后再監(jiān)聽。采用隨機的監(jiān)聽延遲時間可以減少沖

突的可能性，但其缺點也是很明顯的：即使有多個站點有數(shù)據(jù)要發(fā)送，因為此時所

有站點可能都在等待各芻的隨機延遲時間，而信道仍然可能處于空閑狀態(tài)，這樣就

使得信道的利用率較為低下，所以I錯誤。（2）1-堅持CSMA：當一個站點要發(fā)送

數(shù)據(jù)幀時，它就監(jiān)聽信道，判斷當前時刻是否有其他站點正在傳輸數(shù)據(jù)。如果信道

忙，該站點將一直等待，直至信道空閑。一旦該站點檢測到信道空閑，它就立即發(fā)

送數(shù)據(jù)幀，所以W正確。如果產(chǎn)生沖突，則等待一個隨機時間再監(jiān)聽。之所以叫

“1-堅持”，是因為當一個站點發(fā)現(xiàn)信道空閑的時候，它傳輸數(shù)據(jù)幀的概率是1。1-

堅持CSMA的優(yōu)點是：只要信道空閑，站點就立即發(fā)送；它的缺點是：假如有兩

個或兩個以上的站點有數(shù)據(jù)要發(fā)送，沖突就不可避免，所以口錯誤。（3）P-堅持

CSMA：P-堅持CSMA是非堅持CSMA和1-堅持CSMA的折中。P-堅持CSMA應(yīng)

用于劃分時槽的信道，其工作過程是：當一個站點要發(fā)送數(shù)據(jù)幀的時候，它先檢測

信道。若信道空閑，則該站點按照概率P的可能性發(fā)送數(shù)據(jù)，而有1-P的概率會把

要發(fā)送數(shù)據(jù)幀的任務(wù)延遲到下一個時槽。按照這樣的規(guī)則，若下一個時槽也是空閑

的，則站點同樣按照概率P的可能性發(fā)送數(shù)據(jù)，所以說如果處理得當P堅持型監(jiān)

聽算法還是可以減少網(wǎng)絡(luò)的空閑時間的，所以HI錯誤。

36、下面的地址中，屬于單播地址的是（）。

A、10.3.2.255/24

B、172.31.129.255/18

C、192.168.24.59/30

D、224,100.57.211

標準答案：B

知識點解析：A選項：10.3.2.255/24所表示的子網(wǎng)掩碼是11111111

111111111111111100000000,即后8位為主機號,很明顯主機號全為1,所以

10.3.2.255/24是子網(wǎng)10.3.2.0的一個廣播地址。B選項：與A選項類

似，可以得到主機號為00000111111111.由此可知，172.31.129.255/18是一

個單播IP地址。C選項：與產(chǎn)選項類似，可以得到主機號為11。由此可知，

192.168.24.59/30屬于子網(wǎng)192.168.24.56的一個廣播地址。D選項：

224.100.57.211為D類IP地址，即組播地址。

37、以下IP地址中，路由器不進行轉(zhuǎn)發(fā)的有（）。I.10.1.32.7

H.192.168.32.2EI.172.30.1.3IV.172.35.32.244

A、僅I、n、in

B、僅口、皿

c、僅I、皿、w

D、僅w

標準答案：A

知識點器析：路由器對于專用網(wǎng)地址（私有地址）是不進行轉(zhuǎn)發(fā)的。私有地址總結(jié)如

下：A類10.0.0.0-10.255.255.255（記住10開頭即可）B類

172.16.0.0-172.31.255.255（這個死記）C類192.168.0.0?

192.168.255.255（記住192.168開頭即可）

38、假如一臺連接到網(wǎng)絡(luò)上的計算機的網(wǎng)絡(luò)配置為：IP地址為136.62.2.55,

子網(wǎng)掩碼為255.255.192.0,網(wǎng)關(guān)地址為136.62.89.I。這臺計算機在網(wǎng)絡(luò)

中不能與其他主機進行通信，可能是由（）造成的。

A、子網(wǎng)掩碼

B、網(wǎng)關(guān)地址

C、IP地址

D、其他配置

標準答案：c

知識點露析：首先采用反證法，即假設(shè)如果能通信，應(yīng)該滿足什么條件?先要判斷

網(wǎng)關(guān)地址和IP地址是否在一個網(wǎng)絡(luò)中。主要看IP地址的第三個字節(jié)。2的二進制

是00000010,89的二進制是01011001,因此要使得這兩個IP地址屬于同一個網(wǎng)

絡(luò)（只有取第三字節(jié)的第一位為子網(wǎng)號，到了第二位已經(jīng)不同了），子網(wǎng)掩碼必須為

255.255.128.0。問題是如果子網(wǎng)掩碼為255.255.128.0,說明從主機號只

拿出了1位作為子網(wǎng)號，這樣所允許的有效子網(wǎng)數(shù)為21-2=0,所以網(wǎng)關(guān)地址和IP

地址必須有一個是錯的。對于子網(wǎng)掩碼為255.255.192.0,其第三個字節(jié)192

的二進制表示為11000000,表示的含義是所劃分的網(wǎng)絡(luò)包括2?—2=2個子網(wǎng)，子

網(wǎng)號分別為01和10。因此，兩個子網(wǎng)的主機地址范圍分別為：

（1）136.62.01000000.1-136.62.01111111.254,即136.62.64.1?

136.62.127.254o（2）136.62.10000000.1—136.62.10111111.254,即

136.62.128.1-136.62.191.254。注意：加了下畫線的01和10表示子網(wǎng)

號，加粗的0和1表示主機號，主機號不能全。和全1,所以從開始到254。綜上

所述?？梢钥闯觯W(wǎng)關(guān)地址包含在里面的，而IP地址不在。

39、RI、R2是一個自治系統(tǒng)中采用RIP路由協(xié)議的兩個相鄰路由器，R1的路由表

如表2-2所示，當R1收到R2發(fā)送的（V,D）報文（見表2.3）后，R1更新的3個路

由表項中距離值從上到下依次為（）。

?2-2R1的路由衰*2-3R2發(fā)送的報文

日的村絡(luò)加?用圖H的網(wǎng)絹我離

0直稱3

200007R220.00.04

500004R230.00.03

A、0、4、3

B、0、4、4

C、0、5、3

D、0、5、4

標準答案：D

知識點解析：當R1收到R2發(fā)送的報文后，按照以下規(guī)律更新路由表的信息、。（1）

如果R1的路由表沒有某項路由記錄，則R1在路由表中增加該項，由于要經(jīng)過R2

轉(zhuǎn)發(fā)，所以距離值要在R2提供的距離值基礎(chǔ)上加I。（2）如果R1的路由表中的表

項路由記錄比R2發(fā)送的對應(yīng)項的距離值加1還要大，則R1在路由表中修改該

項，距離值根據(jù)R2提供的值加1?？梢?，對于路由器距離值為O的直連網(wǎng)絡(luò)，則

無需進行更新操作，其路由距離保持為0。對比表2-2和表2-3發(fā)現(xiàn)，R1到達目的

網(wǎng)絡(luò)20.0.0.0的距離為7,而表2-3中R2到達目的網(wǎng)絡(luò)20.0.0.0的距離

為4。由于7>4+1,此時R1經(jīng)過R2到達目的網(wǎng)絡(luò)20.0.0.0的路由距離變短

了，所以R1要根據(jù)R2提供的數(shù)據(jù)修改相應(yīng)路由項的距離值為5。R1到達目的網(wǎng)

絡(luò)30.0.0.0的距離為4,而表2-3中R2到達目的網(wǎng)絡(luò)30.0.0.0的距離為

3o由于4=3+1,顯然R1經(jīng)過R2到達目的網(wǎng)絡(luò)30.0.0.0,并不能得到更短的

路由距離，所以R1無需進行更新操作，將保持該路由條目原來的參數(shù)。因此，經(jīng)

過RIP路由重新計算后的R1路由表3個路由表項距離值從上到下依次為0、5、

4o

40、以下應(yīng)用層協(xié)議采用無連接的是（）。I.SMTPn.FTPm.SNMP

IV.HTTP

A僅

、

B僅

、i、n

c僅

、

僅I>IV

D

、i、m、w

標準答案：A

知識點解析：SMTP、FTP、HTTP等協(xié)議使用的都是TCP,所以采用有連接。而

SNMP采用的是UDP,所以采用無連接。表2-9列出了常用的應(yīng)用層協(xié)議與傳輸

表29常用的應(yīng)用層僑議與傳愉層的議

咫川M梅似傳?層的議

DNSUDPmT

nn>UDP

網(wǎng)絡(luò)看照SNMPVW

斛中通界總議RIPUDP

DI1CPUDP

?HrtrnWKITPTCP

AHIMWWWHTTPTCP

FTFTCP

層協(xié)議對應(yīng)的關(guān)系。*2空」TELNETKT

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

分。)

有一結(jié)點的關(guān)鍵字序列F={129,72,180,105,147,96,45,69},散列函數(shù)為

H(k)=kmodll,其中k為關(guān)鍵字，散列地址空間為D?10。要求：

41、畫出相應(yīng)的散列表。當發(fā)生沖突時，以線性探測法解決。該散列表的裝填因子

是多少?計算在等概率情況下，查找成功和查找不成功時的平均查找長度ASLc

標準答案：采用線性探測法處理沖突建立的散列表如下：H(129)=129modll=8

H(72)=72modll=6H(180)=180mod11=4H(105)=105mod11=6沖突

Hi(105)=(l05+l)mod11=7H(147)=147modH=4沖突Hi(l47)=(147+l)mod11=5

H(96)=96modll=8沖突Hi(96)=(96+l)modl1=9H(45)=45modl1=1

H(69)=69modl1=3綜上所述，散列表如表4—7所示。

表4.7雄性除試法處"油窯罐方的數(shù)科褰

卜k0I23454k78910

*4569IMM772105129%

愣例內(nèi)數(shù)

1t121212

裝填因子

a=8/11oASLSUCC=(5X1+2x3)/8=11/8

ASLUNSUCC=(1+2+1+8+7+64-5+4+3+2+1)/11=40/11

知識點解析：暫無解析

42、畫出相應(yīng)的散列表。當發(fā)生沖突時，以鏈地址法解決。計算在等概率情況下,

查找成功和查找不成功時的平均查找長度ASL(只將與關(guān)鍵字的比較次數(shù)計算在內(nèi)

即可)。

標準答案：采用鏈地址法處理沖突建立的散列表如卜.: