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

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

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

1、若已知一個棧的入棧序列是1,2,3……n,其輸出序列為pl,p2,

p3....pn,若pl=n,則pi是（）。

A、i

B、n-i

C、n-i+1

D^不確定

標準答案：C

知識點。析：本題中所敘述的情況，棧的輸出序列一定是輸入序列的逆序。

2、將一個A[1……100,I……100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組

R[l.-29用中，A中元素A66.65（即該元素下標i=66,j=65）,在R數(shù)組中的位置k

為（）。

A、198

B、195

C、197

D、196

標準答案：B

知識點解析：根據(jù)三對角對陣壓縮方法，將A[l..n][l..n]壓縮至B[0..3n

一3]時，aij與bk的對應關系為:k=2i+j-3；將A[L.n][l..n]壓縮至

B[1..3n一2]時，叼與bk的對應關系為：k-2i+j—2；根據(jù)題目，A中元素

A66,65，在B數(shù)組中的位置k為：k=2i+j--2=2x66+65—2=195

3、查找效率最高的二叉排序樹是（）。

A、所有結(jié)點的左子樹都為空的二叉排序樹

B、所有結(jié)點的右子樹都為空的二叉排序樹

C、平衡二叉樹

D、沒有左子樹的二叉排序樹

標準答案：C

知識點解析：二叉排序樹的查找效率取決于二叉排序樹的深度，對于結(jié)點個數(shù)相同

的二叉排序樹，平衡二叉樹的深度最小。

4、一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0,則該樹的

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

A、2k-1-l

B、2kl

C、2k-,+l

D、2卜一1

標準答案：D

知識點解析：一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0,

也就是說每個非終端結(jié)點都有左子樹和右子樹且高度相等。因此，這樣的平衡二叉

樹即為滿二叉樹，而高度為k的滿二叉樹的結(jié)點數(shù)是2k—1。

5、以下敘述正確的是（LI.對有向圖G,如果以任一頂點出發(fā)講行一次深度優(yōu)先

或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖U.連通圖的廣度優(yōu)先

搜索中一般要采用隊列來暫存訪問過的頂點m.圖的深度優(yōu)先搜索中一般要采用

棧來暫存訪問過的頂點

A、I、n

B、口、m

c、I、m

D、I、n、m

標準答案：B

知識點解析：i敘述是錯誤的，因為如果有向圖構(gòu)成雙向有向環(huán)時，則從任一頂點

出發(fā)均能訪問到每個頂點，但該圖卻非完全圖?？?、ni敘述顯然是正確的。

6、一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中零元素的

個數(shù)是（）。

A、e

B、2e

C>n2—e

D、n2—2e-

標準答案：D

知識點解析：由鄰接矩陣的定義可知，無向圖的鄰接矩陣是對稱的，即圖中的一條

邊對應鄰接矩陣的兩個非零元素。因此一個含有n個頂點和e條邊的簡單無向圖的

鄰接矩陣中共有產(chǎn)一2e個零元素。

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

排列的是（）。

A、二叉排序樹

B、大頂堆

C、小頂堆

D、平衡二叉樹

標準答案：C

知識之解析：對于一個堆，若堆頂為最小元素，則稱為小頂堆；若堆頂為最大元

素，則稱為大頂堆。二叉排序樹和平衡二叉樹不符合。

8、順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索

引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在

等概率的情況下，分塊查找成功的平均查找長度為()。

A、21

B、23

C、41

D、62

標準答案：B

知識點解析：分塊查找成功的平均查找長度為ASL=(s2+s+n)/2s。在本題中，

n=123,s=123/3=41,故平均查找長度為23。

9、在下列存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關鍵字之間存在某種映射

關系的是()。

A、樹形存儲結(jié)構(gòu)

B、鏈式存儲結(jié)構(gòu)

C、索引存儲結(jié)構(gòu)

D、散列存儲結(jié)構(gòu)

標準答案：D

知識點解析：散列存儲結(jié)構(gòu)將結(jié)點按其關鍵字的散列地址存儲到散列表中。

10、若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)是()。

A、2

B、3

C、4

D、5

標準答案：B

知識點解析：歸并就是將兩個或兩個以上的有序表組合成一個新的有序表。設三趟

歸并中每次歸并x個有序表，則有27/X3=1,X=3C所以選取的歸并路數(shù)為3。

11、下列序列中，執(zhí)行第一趟快速排序的結(jié)果是()，

A、[da,ax,eb,de,bb]ff[ha,gc]

B、[cd,eb,ax,da]ff[ha,gc,bb]

C、[gc?ax,eb,cd,bb]ff[da?ha]

D、[ax,bb,cd,da]ff[eb,gc,ha]

標準答案：A

知識點解析：本題要按字典順序進行排序，前半?yún)^(qū)間中的所有元素都應小于ff,后

半?yún)^(qū)間中的所有元素都應大于ffo

12、某工作站采用時鐘頻率f為15MHz,處理速率為10MIPS的處理機來執(zhí)行一個

已知混合程序。假定每次存儲器存取為1周期延遲，試問此計算機的有效CPI是

()。

A、2.5

B、2

C、1.5

D、1

標準答案：C

知識點解析：CPI=15MHZ/(10X106)=1.5O

13、5位二進制定點小數(shù)，用補碼表示時，最小負數(shù)是()。

A>0.II11

B、1.0001

C、1.1111

D、1

標準答案：D

知識點解析：5位二進制定點小數(shù)，用補碼表示時，最小負數(shù)表示為I.0000。

14、浮點加減中的對階是()。

A、將較小的一個階碼調(diào)整到與較大的一個階碼相同

B、將較大的一個階碼調(diào)整到與較小的一個階碼相同

C、將被加數(shù)的階碼調(diào)整到與加數(shù)的階碼相同

D、將加數(shù)的階碼調(diào)整到與被加數(shù)的階碼相同

標準答案：A

知識點解析：對階的原則是小階向大階看齊。

15、若內(nèi)存按字節(jié)編址，用存儲容量為32Kx8比特的存儲器芯片構(gòu)成地址編號

A0000H至DFFFFH的內(nèi)存空間，則至少需要的片數(shù)是()。

A、4

B、6

C、8

D、10

標準答案：C

知識點解析：DFFFF—A0000+1=40000,即256KB,需用32Kx8的芯片數(shù)

=(256Kx8)/(32Kx8)=8o

16、某計算機的存儲系統(tǒng)由Cache一主存系統(tǒng)構(gòu)成，Cache的存取周期為10ns,主

存的存取周期為50ns。在CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為4800

次，主存完成的存取次數(shù)為200次，該Cache一主存系統(tǒng)的效率是()。

A、0.856

B、0.862

C、0.958

D、0.96

標準答案：B

知識點解析：命中率=4800/(4800+200)=0.96,平均訪問時間=0.96x10+(1—

0.96)x50=11.6ns,效率=10/II.6=0.862。

17、對于RISC機和CISC機，以下說法錯誤的是（）。

A、RISC機的指令條數(shù)比CISC機少

B、RISC機指令的平均字長比CISC機指令的平均字長短

C、對大多數(shù)計算任務來說，RISC機程序所用的指令條數(shù)比CISC機少

D、RISC機和CISC機都在發(fā)展

標準答案：C

知識點解析：對于大多數(shù)計算任務來說，RISC機編寫的程序會比CISC機編寫的

程序更長，這是因為RISC的指令都比較簡單，CSIC中的一條復雜指令所完成的

功能在RISC中可能要用幾條指令才能實現(xiàn)，對于同一個源程序，顯然RISC的指

令條數(shù)要比CISC的多。

18、微程序在計算機中存放的位置是（）。

A、主存儲器

B、控制存儲器

C、通用寄存器

D、指令寄存器

標準答案：B

知識點解析：微程序存放在只讀的控制存儲器中。

19、下列各敘述中正確的命題是（）。I.在取指周期中也可能從內(nèi)存取到操作數(shù)

n.CPU的訪存時間是由存儲器的容量決定的，存儲容量越大，訪存時間就越長

m.在主存與Cache之間的直接映射方式下，不采用替換策略也可以實現(xiàn)正確的塊

替換IV.動態(tài)存儲器的讀操作也具有刷新的功能

A、I、n、in

B、I、n、w

c、u、m、w

D、I、山、IV

標準答案：D

知識點解析：立即尋址方式就可以在取指周期從內(nèi)存取到操作數(shù)；在直接映射方式

下，一旦發(fā)生塊沖突是不需要替換策略的；動態(tài)存儲器的刷新是與讀寫操作沒有關

系的。

20、在菊花鏈方式中，靠近控制器的設備與遠處設備的（）。

A、優(yōu)先級高

B、優(yōu)先級相等

C、優(yōu)先級低

D、不一定

標準答案：A

知識點解析：常見的集中仲裁方式有鏈式查詢（菊花鏈）、計數(shù)器定時查詢和獨立請

求等3種。鏈式查詢方式的優(yōu)先次序是由串接部件的先后位置來確定的，在查詢鏈

中離總線控制器最近的設備具有最高優(yōu)先權(quán)。計數(shù)器定時查詢和獨立請求方式的優(yōu)

先級可以是固定的也可以是不固定的。鏈式查詢方式需要3條控制線、計數(shù)器定

時查詢方式需要［*］條控制線，而獨立請求方式需要2n+l條控制線。

21、RAID利用冗余技術實現(xiàn)高可靠性，其中RAID1的磁盤利用率是()。

A、25%

B、50%

C、75%

D、100%

標準答案：B

知識點解析：RA1D1稱為鏡象磁盤陣列，數(shù)據(jù)盤和檢測盤的數(shù)量是1:1的關系，所

以磁盤利用率為50%。

22、設存儲器容量為32字，字長64位，模塊數(shù)m=4,存儲周期T=200ns,數(shù)據(jù)總

線寬度為64位，總線傳送周期i=50ns。用交叉方式進行組織，交叉存儲器的帶寬

是()。

A、32x1(/位/秒

B、8xl()7位/秒

C、73xl()7位/秒

D、18xl()7位/秒

標準答案：C

知識點解析：順序存儲存儲器連續(xù)讀出4個字需要4個存儲周期，而交叉存儲存儲

器連續(xù)讀出4個字，由于采用分時啟動的方法，只需要一個存儲周期加上三個總線

傳輸周期的時間。現(xiàn)字長為64位，交叉存儲器連續(xù)讀出4個字的信息總量q=64位

x4=256位，交叉存儲器連續(xù)讀出4個字所需的時間t=T+(4—

l)T=200ns+3x50ns=350ns=3.5xl0-7s,所以交叉存儲器的帶寬W=q/

t=256-(3.5xl0-7)=73xl()7(位/秒)。

23、操作系統(tǒng)為用戶提供了多種接口，它們是()。I.計算機高級指令；11.終端

命令：m.圖標菜單；IV.匯編語言；V.C語言；VI.系統(tǒng)調(diào)用；

A、I；n；v

B、n；皿；vi

c、m；iv：v

D、口；w；w

標準答案：B

知識點解析：本題考查操作系統(tǒng)的接口，操作系統(tǒng)有二種接口，命令輸入和系統(tǒng)調(diào)

用，而命令輸入又可以分為命令行和圖形用戶界面。命令行是在終端或命令輸入窗

口中輸入操作和控制計算機的規(guī)定的命令，既可以一條一條輸入，也可以組織成一

批命令，逐條自動執(zhí)行，稱為批處理命令。圖形用戶接口是我們熟知的圖標和菜單

形式。系統(tǒng)調(diào)用是我們編寫程序過程中，需要計算機所做的操作，一般要按固定格

式來調(diào)用。

24、若一個信號量的初值為3,經(jīng)過多次PV操作以后當前值為一1,此表示等待

進入臨界區(qū)的進程數(shù)是()。

A、1

B、2

C、3

D、4

標準答案：A

知識點3析：本題考查信號量的意義。信號量是一個整型的特殊變量，只有初始化

和PV操作才能改變其值。通常，信號量分為互斥量和資源量，互斥量的初值一般

為1,表示臨界區(qū)只運許一個進程進入，從而實現(xiàn)互斥。互斥量可以為0,表示臨

界區(qū)己經(jīng)有1個進程進入，臨界區(qū)外尚無進程等待；當互斥量小于0時，表示臨界

區(qū)中有1個進程，互斥量的絕對值表示在臨界區(qū)外等待進入的進程數(shù)。同樣的道

理，資源信號量初值可以是任意整數(shù)，表示可用的資源數(shù)，當資源量為0時，表示

所有資源已經(jīng)用光，但是也沒有其它進程等待使用該資源。當資源量小于0時，表

示當前貨源已經(jīng)全部用完，而目.還有進程正在等待使用該資源，等待的進程數(shù)就是

資源量的絕對值。

25、利用銀行家算法進行安全序列檢查時，不需要的參數(shù)是()。

A、系統(tǒng)資源總數(shù)

B、滿足系統(tǒng)安全的最少資源數(shù)

C、用戶最大需求數(shù)

D、用戶已占有的資源數(shù)

標準答案：B

知識點露析：安全性檢查一般要用到進程所需的最大資源數(shù)，減去進程占用的資源

數(shù)，得到進程為滿足進程運行尚需要的可能最大資源數(shù)，而系統(tǒng)擁有的最大資源數(shù)

減去已經(jīng)分配掉的資源數(shù)得到剩余的資源數(shù)，比較剩余的資源數(shù)是否滿足進程運行

尚需要的可能最大資源數(shù)可以得到當前狀態(tài)是否安全的結(jié)論。而滿足系統(tǒng)安全的最

少資源數(shù)并沒有這么一個說法。

26、若有一進程擁有100個線程，這些線程都屬于用戶級線程，則在系統(tǒng)調(diào)度執(zhí)行

時間上占用的時間片是()。

A、1

B、100

C、1/100

D、0

標準答案：A

知識點解析：本題主要考查關于進程和線程之間資源共享的知識點。在引入線程的

操作系統(tǒng)中，線程是進程中的一個實體，是系統(tǒng)獨立調(diào)度和分派的基本單位。但是

線程自己基本上不擁有系統(tǒng)資源，所以它不是資源分配的基本單位，它只擁有一部

分在運行中必不可少的與處理機相關的資源，如線程狀態(tài)、寄存器上下文和棧等，

它同樣有就緒、阻塞和執(zhí)行三種基本狀態(tài)。它可與同屬一個進程的其他線程共享進

程所擁有的全部資源。一個線程可以創(chuàng)建和撤銷另一個線程；同一個進程中的多個

線程之間可以并發(fā)執(zhí)行。由于用戶線程不依賴于操作系統(tǒng)內(nèi)核，因此，操作系統(tǒng)內(nèi)

核是不知道用戶線程的存在的，用戶線程是由用戶來管理和調(diào)度的，用戶利用線程

庫提供的API來創(chuàng)建、司步、調(diào)度和管理線程。所以，用戶線程的調(diào)度在用戶程

序內(nèi)部進行，通常采用非搶先式和更簡單的規(guī)則，也無須用戶態(tài)和核心態(tài)切換，所

以速度很快。由于操作系統(tǒng)不知道用戶線程的存在，所以，操作系統(tǒng)把CPU的時

間片分配給用戶進程，再由用戶進程的管理器將時間分配給用戶線程。那么，用戶

進程能得到的時間片即為所有用戶線程共享。因此，正確答案應為A。

27、某計算機采用頁式存儲管理，內(nèi)存中現(xiàn)有1000個頁表項，CPU的cache中可

以存放N個頁表項，該系統(tǒng)中，CPU內(nèi)存訪問的時間為KJOns,對cache訪問的時

間是5ns,如果希望頁表映射的平均時間降到20ns以下，那么cache中的N必須高

于()。

A、850

B、858

C、923

D、842

標準答案：A

知識點露析：本題考查cache與頁式存儲管理結(jié)合下的時間計算。根據(jù)題意，頁式

尋址方式的過程是這樣的：當執(zhí)行到一個邏輯地址時，MMU首先將頁號分離，將

得到的頁號與cache中的多個頁表項比較(同時進行)，若頁表項命中，則取出頁表

項與頁內(nèi)地址相加，形成指令或數(shù)據(jù)的物理地址，花費5ns,據(jù)此地址，然后到內(nèi)

存中取得對應的指令或數(shù)據(jù)，送到CPU中執(zhí)行或計算。若不能在cache命中，那

么CPU會啟動cache更新程序，將新的頁表項從內(nèi)存復制到cache,花費100ns,

然后，重復上述地址轉(zhuǎn)段過程，又花去5ns,得到物理地址，再去內(nèi)存取指令或數(shù)

據(jù)。根據(jù)題意，要求得到頁框號，也就是物理地址的過程小于20ns,那么設，

cache的命中率為x,列關系式：5*x+(l—x)*(5+100)=20解得x為85%。因此，

裝入cache的頁表項應大于1000*85%=850項，這樣可以保證獲得頁框號的時間小

于20ns。本題若問，一個指令雙字的執(zhí)行時間是多少時，需要考慮的事情就比較

復雜。例如系統(tǒng)的字長是否是32位，32位的系統(tǒng)執(zhí)行一個雙字的時間是1次尋

址，16位系統(tǒng)就需要2次尋址。8位系統(tǒng)的就需要4次尋址。另外，采用什么內(nèi)存

管理機制，頁式和段式都是執(zhí)行1次指令尋址需要訪問內(nèi)存2次，段頁式需要3

次。還要看cache的容量多大，指令是否在cache中等，所以，內(nèi)存管理中尋址時

間的計算與CPU結(jié)構(gòu)和cache的運行模式息息相關，考生應結(jié)合計算機組成原

理，妥善解決此類問題。

28、分頁系統(tǒng)中的頁面是()。

A、用戶所能感知的

B、操作系統(tǒng)所能感知的

C、編譯程序所能感知的

D、鏈接裝配程序所能感知的

標準答案：B

知識點解析：分頁系統(tǒng)中由邏輯地址向物理地址的轉(zhuǎn)換是系統(tǒng)借助硬件系統(tǒng)自動實

現(xiàn)的，對用戶透明，對編譯程序和鏈接裝配程序透明(在相同的系統(tǒng)里)。只有操作

系統(tǒng)可以感知頁面的存在，在內(nèi)存管理過程中，操作系統(tǒng)要為用戶進程分配內(nèi)存，

回收內(nèi)存。所以操作系統(tǒng)是頁面最直接的接觸者，它將頁面從計算機系統(tǒng)中到用戶

進行了隔離。

29、某操作系統(tǒng)的文件管理采用直接索引和多級索引混合方式，文件索引表共有

10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接

索引項，假定物理塊的大小是1K,每個索引項占用4個字節(jié)，則該文件系統(tǒng)日最

大的文件可以達到()。

A、65800K

B、65792K

C、65536K

D、34000K

標準答案：A

知識點解析：多級索引的邏輯并不復雜，本題中一級間接索引表有256張，二級間

接索引表最多有256張，計算時加以仔細小心，一般不會有太多變化，但是對多級

索引的方法一定要掌握。直接索引為8xlK=8K,一級間接索引為(1K/4B)X1

K=256K；二級間接索引為(1K/4B)x(lK/4B)x1K=65536K。共計

65536K+25K+8K=65800K

30、設磁盤的IO請求隊列中所要訪問的磁道號為:96,184,25,120,12,

126,73,75,當前磁頭在96,前一次在90。當采用最短尋道時間優(yōu)先算法(SSTF)

和電梯算法所要移動的距離是()。

A、618,418

B、306,260

C、306,418

D、618,260

標準答案：B

知識點解析：本題考查考生對最短尋道時間優(yōu)先算法和電梯算法的理解。最短尋道

時間優(yōu)先算法(SSTF)：96—75—73—120—126—184—25—12共計306道。電梯算

法，前一次在90,當前在96,表示移動方向為磁道增大方向，故：

96-120—126T184—75—73-25T12共計260道。計算時注意磁頭的當前位置和

運行方向。

31、UNIX操作系統(tǒng)中，文件的索引結(jié)構(gòu)存放在()。

A、超級塊

B、索引節(jié)點

C、目錄項

D、空閑塊

標準答案：B

知識點解析：在UNIX的文件系統(tǒng)中文件系統(tǒng)是其核心，其功能強大，可擴展性

強。UNIX采用的是樹形目錄結(jié)構(gòu)，文件的信息存放在索引節(jié)點中，索引節(jié)點是一

個64字節(jié)長的表，含有一個文件的重要信息，包括文件大小，文件所有者，文件

存取許可方式，文件類型(普通文件、目錄文件、特殊文件)等信息，但是不包含文

件名，文件名存放在目錄中。除了上述信息以外，索引節(jié)點在表格的最后設計有

13項文件在外存存放的混合索引表，前10項存放的是直接指針，指向文件存放的

數(shù)據(jù)塊的直接地址，UNIX系統(tǒng)中文件塊的大小一般是1024字節(jié)。所以文件的大

小不能超過10*1024=10240字節(jié)，超過上述大小的文件將在第11項一級間接索引

表中指出，該表項指針指向的一個數(shù)據(jù)塊中，存放了256個索引指針(假設一個指

針為4字節(jié)，1024字節(jié)的一個存儲塊可以存放1024/4=256個指針)，可以最多容

納256*1024=262144字節(jié)。再大的文件在第12項的二級間接索引表中指明,二級

索引指針指向的數(shù)據(jù)塊中可以容納256個指針，這些指針指向的數(shù)據(jù)塊中還是索引

指針，故稱為二級間接索引，它可以容納的文件大小是256*256*1024=67108864

字節(jié)。第13項是三級間接索引，可以容納的文件大小更大，為

256*256*256*1024節(jié)。所以文件總的大小是上述各級索引文仁溶

量的總和。即文件最大可以達節(jié)的大小。當然，UNIX文件系統(tǒng)

對文件的大小是有限制的，不會讓其用完整個三級索引。文件的物理結(jié)構(gòu)中，主

要使用的是順序結(jié)構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)(Hash結(jié)構(gòu)實際上與索引結(jié)構(gòu)類似)。在

索引結(jié)構(gòu)的文件中，必須要用專門的存儲空問來存放索引指針，表示文件的內(nèi)容存

放的地址。所以，當訪問該文件時，必須首先去讀取該文件的索引表，才能知道相

應的邏輯文件塊在外存上的存放地址。邏輯文件塊與物理文件塊是一一對應關系，

不能在一個記錄中存放多個地址，而索引表中只存放地址指針，不存放文件內(nèi)容由

于有額外的索引表，所以它并不節(jié)省存儲空間。

32、在設備管理中，用來實現(xiàn)設備分配的四個數(shù)據(jù)結(jié)構(gòu)中，每個設備一張，描述設

備的特性和狀態(tài)，反映設備的特性、設備和控制器的連接情況的數(shù)據(jù)結(jié)構(gòu)是()。

A、設備控制表(DCT)

B、系統(tǒng)設備表(SDT)

C、控制器控制表(COCT)

D、通道控制表(CHCT)

標準答案：A

知識點解析：設備控制的數(shù)據(jù)結(jié)構(gòu)中，系統(tǒng)設備表(SDT)在整個操作系統(tǒng)中只有一

張，記錄了系統(tǒng)中所有的外部設備。經(jīng)系統(tǒng)設備表找到需使用的外部設備，則數(shù)據(jù)

結(jié)構(gòu)指針指向設備控制表(DCT),這個數(shù)據(jù)表每個設備一張，記錄了設備的特性和

狀態(tài)。每個設備有可能有不止一個控制器，所以從設備控制表會指向多張(至少一

張)控制器控制表(COCT),里面存放了控制器的控制參數(shù)，如果該設備是通道的

話，則會指向多張通道控制表(CHCT)。

33、在OSI參考模型中，第N層和其上的第N+1層的關系是()。

A、第N層為第N+1層提供服務

B、第N+1層將從第N層接收的信息增加了一個頭

C、第N層利用第N+1層提供的服務

D、第N層對N+l層沒有任何作用

標準答案：A

知識點解析：本題考查OSI模型的層次關系，在協(xié)嘆的控制下，兩個對等實體問的

通信使得本層能夠向上一層提供服務，同時要實現(xiàn)本層協(xié)議，還需要使用下層所提

供的服務。本層的服務用戶只能看見服務而無法看見下面的協(xié)議。下層的協(xié)議對上

層的服務用戶是透明的。也就是下一層要為上一層提供服務，并為上一層數(shù)據(jù)進行

封裝，因此答案為A,這里選項B和C的說法正好相反，應該是第N層將從第

N+1層接收的信息增加了一個頭，第N+1層利用第N層提供的服務。

34、設待傳送數(shù)據(jù)總長度為L位，分組長度為P位，其中頭部開銷長度為H位，

源節(jié)點到目的節(jié)點之間.的鏈路數(shù)為h,每個鏈路上的延遲時間為D秒，數(shù)據(jù)傳輸

率為Bbps,電路交換建立連接的時間為S秒，則傳送所有數(shù)據(jù)，電路交換需時間

是（）。

A、hD+L/B秒

B、S+hD+L/P秒

C、S+hD+L/B秒

D、S+L/B秒

標準答案：C

知識點解析：本題考查電路交換的原理，電路交換包括三個階段：建立電路。在傳

送數(shù)據(jù)之前，由發(fā)送方發(fā)出建立電路請求，交換機根據(jù)該請求，設法選擇一條空閑

的信道連接到接收方。諼收方收到該呼叫后，返回一應答信號確認本次電路連成，

則本次連接成功。傳送數(shù)據(jù)。建立電路連接后，發(fā)送方通過已建立的電路向接收方

發(fā)送數(shù)據(jù)。拆除電路。數(shù)據(jù)傳輸完畢，發(fā)送方或接收方任一方發(fā)出拆線信號，終止

電路連接，釋放所占用的信道資源。因此傳送所有數(shù)據(jù)所需的時間是連接建立時

間，鏈路延遲，發(fā)送時間的和，因此是S+hD+L/B,答案是C。

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

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

A、2幀

B、3幀

C、4幀

D、1幀

標準答案：B

知識點解析：本題考查滑動窗口的機制，發(fā)送方可連續(xù)發(fā)送K幀而無需對方應

答，但需要將已發(fā)出但尚未收到確認的幀保存在發(fā)送窗口中，以備由于出錯或丟失

而準備重發(fā)。接收方按正確的次序接受和遞交數(shù)據(jù)幀，并返回確認信息。接收方可

能因為一幀出錯，不能正確接受并遞交主機，對后面連續(xù)發(fā)送來的n幀均丟失，這

就是累積確認的概念。本題收到了2號幀的確認后，即0,1,2號幀已經(jīng)正確接

收，因此窗口向右移動3個幀，目前已經(jīng)發(fā)送了3號幀，因此可連續(xù)發(fā)送的幀數(shù)是

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

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

255.255.255.192,那么該主機所在的子網(wǎng)的網(wǎng)絡地址是（）。

A、130.25.0.0

B、130.25.3.0

C、130.25.3.128

D、130.25.3.255

標準答案：C

知識點解析：本題考查子網(wǎng)劃分的計算，從掩碼可以看出網(wǎng)絡地址僅和第四個字節(jié)

有關，因此130.25.3.135的二進制為130.25.3.10000111,子網(wǎng)掩碼的二

進制為255.255.255.11000000,兩者相與，因此網(wǎng)絡地址為

130.25.3.10000000,換算為十進制是130.25.3.128,因此答案為C。

37、為了限制路由信息傳播的范圍，OSPF、協(xié)議把網(wǎng)絡劃分成4種區(qū)域（Area）,其

中連接各個區(qū)域的傳輸網(wǎng)絡是（）。

A、不完全存根區(qū)域

B、標準區(qū)域

C、主干區(qū)域

D、存根區(qū)域

標準答案：C

知識點解析：本題考查層次路由與OSPF路由協(xié)議，如果將區(qū)域看成一個節(jié)點，則

OSPF是以主干區(qū)域（area。）為頂點，其他區(qū)域為終端的星形拓撲結(jié)構(gòu)。標準區(qū)域可

以接收鏈路更新信息和路由總結(jié)。存根區(qū)域是不接受自治系統(tǒng)以外的路由信息的區(qū)

域。如果需要自治系統(tǒng)以外的路由，它使用默認路由0.0.0.0。完全存根區(qū)域

不接受外部自治系統(tǒng)的路由以及自治系統(tǒng)內(nèi)其他區(qū)域的路由總結(jié)，需要發(fā)送到區(qū)域

外的報文則使用默認路由0.0.0.0o不完全存根區(qū)域類似于存根區(qū)域，但是允

許接收以LSAType7發(fā)送的外部路由信息，并且要把LSAType7轉(zhuǎn)換成

LSAType5o因此答案是C。

38、一臺主機的IP地址為11.I.1.100,子網(wǎng)掩碼為255.0.0.0?，F(xiàn)在用戶

需要配置該主機的默認路由。經(jīng)過觀察發(fā)現(xiàn)，與該主機直接相連的路由器具有如下

4個IP地址和子網(wǎng)掩碼：I.IP地址：11.1.1.1,子網(wǎng)掩碼：255.0.0.0

n.1P地址：II.1.2.1,子網(wǎng)掩碼：255.0.0.0山.IP地址：1

2.1.1.1,子網(wǎng)掩碼：255.0.0.0W.IP地址：13.1.2.1,子網(wǎng)掩碼：

255.0.0.。請問IP地址和子網(wǎng)屏蔽碼可能是該主機的默認路由的是（）。

A、I和口

B、I和m

C>CC和w

D、in和w

標準答案：A

知識點解析：本題考查默認路由的配置，路由器還可采用默認路由以減少路由表所

占用的空間和搜索路由表所用的時間。這種轉(zhuǎn)發(fā)方式在一個網(wǎng)絡只有很少的對外連

接時是很有用的。本題中主機地址是一個標準的A類地址，其網(wǎng)絡地址為

II.0.0.Oo選項I的網(wǎng)絡地址為11.0.0.0,選項II的網(wǎng)絡地址為

11.0.0.0,選項HI的網(wǎng)絡地址為12.0.0.0,選項IV的網(wǎng)絡地址為

13.0.0.0,因此和主機在同一個網(wǎng)絡是選項I和n,因此答案為A。

39、以太網(wǎng)交換機中的端口/MAC地址映射表是()。

A、是由交換機的生產(chǎn)廠商建立的

B、是交換機在數(shù)據(jù)轉(zhuǎn)發(fā)過程中通過學習動態(tài)建立的

C、是由網(wǎng)絡管理員建立的

D、是由網(wǎng)絡用戶利用特殊的命令建立的

標準答案：B

知識點解析：本題考查交換機中地址映射表的原理，主要與路由器的路由表進行區(qū)

分，路由表可以由人為配置靜態(tài)路由，也可以通過動態(tài)協(xié)議建立，而對于交換機，

映射表只能在數(shù)據(jù)轉(zhuǎn)發(fā)中進行動態(tài)學習建立，并且每個表項都有定時器，具體是收

到一幀后先進行自學習。查找轉(zhuǎn)發(fā)表中與收到幀的源地址有無相匹配的項目。如沒

有，就在轉(zhuǎn)發(fā)表中增加一個項目(源地址、進入的接口和時間)。如有，則把原有的

項目進行更新，因此答案為B。

40、下面關于電子郵件的說法中，不正確的是()。

A、電子郵件只能發(fā)送文本文件

B、電子郵件可以發(fā)送圖形文件

C、電子郵件可以發(fā)送二進制文件

D、電子郵件可以發(fā)送主頁形式的文件

標準答案：A

知識點解析：本題考查電子郵件的主要功能，電子郵件不僅僅發(fā)送文本文件，注意

郵件統(tǒng)中SMTP不能傳送可執(zhí)行文件或其他的二進制對象。SMTP限于傳送7位的

ASCII碼，也就是文本文件，因此引入MIME協(xié)議，在沒有改動SMTP或取代

SMTP的前提下，增加了郵件主體的結(jié)構(gòu)，并定義了傳送非ASCII碼的編碼規(guī)

則.因此答案為A.

二、綜合應用題(本題共7題，每題1.0分，共7分。)

41、己知二義樹采用二義鏈表方式存放，要求返回二義樹T的后序序列中的第一

個結(jié)點的指針，是否可不用遞歸且不用棧來完成?請簡述原因。

標準答案：可以。原因：后序遍歷的順序是“左子樹一右子樹一根結(jié)點”。因此，二

叉樹最左下的葉子結(jié)點是遍歷的第一個結(jié)點。下面的語句段說明了這一過程(設p

是二叉樹根結(jié)點的指針)。if(p!=NULL){while(p—>lchild!=NULL||p—>rchild!

-NULL){while(p>lchild!-NULL)p-p>lchild；if(p>ichild!-NULL)p-p

—>rchild：)(return(p)；//返回后序序列第一個結(jié)點的指針

知識點解析：本題主要考查后序遍歷過程及特點。

42、設有一個帶頭結(jié)點的循環(huán)單鏈表，其結(jié)點值均為正整數(shù)。試設計一個算法，反

復找出單鏈表中結(jié)點值最小的結(jié)點，并輸出之，然后將該結(jié)點從中刪除，直到單鏈

表空為止，最后再刪除表頭結(jié)點。

標準答案：voiddelall(LinkL5.st&L){LNode*p,*pre,*minp,*minpre；while(L

—*>next!=L){//循環(huán)單鏈表不空時循環(huán)p=Lnext：pre=L；minp=p；

minpre=pre；while(p!=L){//從頭開始查找最小值的結(jié)點if(p

—>datadata){minp=p；minpre=pre；)pre=p；//p>pre同步后移p=p

一〉next；}printf("％c"，minpdata)；//輸出最小值結(jié)點minpre

—>ncxt=minp—>ncxt；//刪除最小值結(jié)點frec(minp)；)free(L)；}

知識點解析：對于循環(huán)單鏈表L,在不空時循環(huán)：每循環(huán)一次查找一個最小結(jié)點

(由minp指向最小結(jié)點，minpre指向其前趨結(jié)點)并刪除它。最后釋放頭結(jié)點。

43、什么是單重分組和雙重分組跳躍進位鏈?一個按3,5,3,5分組的雙重分組跳

躍進位鏈(最低位為第0位)，試問大組中產(chǎn)生的是哪幾位進位?與4,4,4,4分組

的雙重分組跳躍進位鏈相比，試問產(chǎn)生全部進位的時間是否一致?為什么？

標準答案：單重分組即組內(nèi)并行、組間串行的進位方式；雙重分組即組內(nèi)并行，組

間也并行。雙重分組跳躍進位鏈中一個按3,5,3,5分組，大組中產(chǎn)生的進位輸

出是C4、C7、。2和C5而一個按4,4,4,4分組，大組中產(chǎn)生的進位輸出是

C3、C7、Cu和C|5雖然這兩種方式小組內(nèi)的位數(shù)不同，但產(chǎn)生全部進位的時間是

一致的。因為兩種方式都被分成4個小組，假定一級“與門”、“或門”的延遲時間定

為ly,則每一級進位的延遲時間為2ty。C]經(jīng)過2ty產(chǎn)生第1小組的進位及所有組

進位產(chǎn)生函數(shù)G「和組進位傳遞函數(shù)Pi*；再經(jīng)過2ty,由大組產(chǎn)生相應的進位；再

經(jīng)過2ty后，才能產(chǎn)生第2、3、4小組內(nèi)的其余的進位，所以最長的進位延遲時間

者B為6tyo

知識點解析?：假設最低位為第0位，16位并行加法器均分為4組，最低位的進位

輸入為C-],最高位的進位輸出為C]5。

44、某機的主要部件如下圖所示。

移位器1-1R.MDR

“L-￡^JR.

rm1凡Ld

DR,MAR

回函1--------1(1)請補充各部件間的主

要連接線，并注明數(shù)據(jù)流動方向。(2)擬出指令SUB(Ri),一(R2)的執(zhí)行流程(含取

指過程與確定后繼指令地址)。該指令的含義是進行減法操作，源操作數(shù)地址和日

的操作數(shù)地址分別在寄存器Ri和R2中，目的操作數(shù)尋址方式為自減型寄存器間接

尋址。其中：LA—A輸入選擇器，LB—B輸入選擇器，C、D一暫存器。

標準答案：(1)將各部件間的主要連接線補充完后，數(shù)據(jù)通路下圖所示。

CR~凡DR~旦

票機的敷據(jù)通路圖(2)指令

SUB(Ri),一(R2)的含義為(R2)-1-R2((RI))—(。2))一(R2)指令的執(zhí)行流程如

下：①(PC)—MAR；取指令②ReadG)M(MAR)-MDR-1R④(PC)+1-PC

⑤(RI)-MAR；取被減數(shù)⑥Read⑦M(MAR)TMDR-C⑧(R2)一1-R2:修改

R的地址@(R2)->MAR:取減數(shù)⑩Read?M(MAR)-MDR->D?(C)一

(D)一MDR；求差并保存結(jié)果？Write?MDR—MM

知識點解析：第44題的圖中只給出了計算機的主要部件，但各部件之間的連接線

沒有給出，由于LA和LB分別為輸入選擇器，所以特將數(shù)據(jù)通路設計為簡單的單

總線結(jié)構(gòu)形式。

45、實現(xiàn)一個經(jīng)典的“讀者一寫者”算法時，若當前臨界區(qū)中有讀者訪問，寫者再來

時必須在臨界區(qū)外面等候，如果其后讀者源源不斷地到達，按策略他們均可以進入

臨界區(qū)，始終保持臨界區(qū)中有讀者訪問，那么寫者可能長時間不能進入臨界區(qū)而形

成饑餓。為解決此類問題，我們修改訪問策略，要求當寫者到達時，寫者具有優(yōu)先

權(quán)。具體說，寫者到達后，已經(jīng)在臨界區(qū)內(nèi)的讀者繼續(xù)讀取直到結(jié)束，而后來的讀

者就不能進入臨界區(qū)。等所有的讀者離開臨界區(qū)以后讓寫者先進去訪問，然后等寫

者離開后再允許讀者進入臨界區(qū)。這所謂“寫者優(yōu)先讀者一寫者''問題。請用信號

量和PV操作來描述這一組進程的工作過程。

標準答案：第一部分：假設臨界區(qū)能容納的最大讀者數(shù)量為n。貝I：typedefint

semaphore；//定義信號量semaphoremutex=l；//讀寫的互斥量semaphore

rcadcrs=n；//讀者的資源量voidReaders(viod)//讀者進程{while(TRUE){/

/調(diào)度P(mutex)；//讀寫互斥P(readers)；//讀者資源量減一，為負時等待

V(mutex)；//釋放讀寫互斥read_data(void)；//讀者讀取數(shù)據(jù)V(readers)；}

//離開時釋放讀者數(shù)量，加I一}VoidWriters(void)//寫者進程

{while(TRUE){P(mutex)；//獲取讀寫互斥量for(inli=l；iv=n；

i++)P(readers)；//將許可讀者進入的資源量消耗光writedata(void)；//寫入

數(shù)據(jù)for(inti=l；iv=n；i++)V(readers)；//釋放讀者的資源量V(mutex)；}//

釋放讀寫互斥量}第二部分：若對讀者的數(shù)量不加以限制，那么應該如下書寫程

序。lypedefintsemaphore；//定義信號量semaphorerwmulex=l；//讀寫的

互斥量semaphorercmutex=l；//訪問讀者計數(shù)器的互斥量semaphore

nrmutex=1；//寫者等待讀者退出的互斥量intreaderscount=0；//讀者計數(shù)器

voidReaders(viod)//讀者進程{while(TRUE){//調(diào)度P(rwmutex)；//讀寫

互斥P(rcmutex)；//進入修改讀者計數(shù)器互斥readerscount++；//讀者數(shù)量加

-if(readerscount=1)P(nrmutex)；//若是第一個讀者，互斥寫者V(rcmutex)；/

/釋放讀者計數(shù)器互斥量V(rwmutex)；//及時移放讀寫互斥量，允許其它進程

申請readdata(void)；//讀者讀取數(shù)據(jù)P(rcmutex)；//離開臨界區(qū)時讀者計數(shù)

器互斥rcadcrscount--；//讀者數(shù)量減一if(rcaderscount==0)V(nnnutex)；//所

有讀者退出臨界區(qū)V(rcmutex)；)//離開時釋放讀者計數(shù)器互斥量}Void

writers(void)//寫者進程{while(TRUE){P(rwmutex)；//獲取讀寫互斥量

P(nrmutex)；//若臨界區(qū)有讀者，等待其退出writc_data(void)；//寫入數(shù)據(jù)

V(nrmutex)；//允許后續(xù)第一個讀者進入臨界區(qū)V(rwmulex)；}//允許新的讀

者和寫者排隊}上述程序不能保證在等待隊列中寫者更優(yōu)一點，因為上述約束條件

只能將讀者無限制地進入臨界區(qū)的情況給扉蔽了，而在臨界區(qū)外，讀者和寫者還是

按照先來先服務的方式排隊。第三部分給出的方法使得訪問隊列中只要有寫者出

現(xiàn)，它必然優(yōu)先進入臨界區(qū)。typedefintsemaphore；//定義信號量semaphore

rwmutcx=l；//讀寫的互斥量semaphorercmutcx=l；//訪問讀者計數(shù)器的互

斥量semaphorewcmutex=l；//訪問排隊寫者計數(shù)器的互斥量semaphore

nrmutex=1；//寫者等待讀者退出的互斥量intreaderscount=0；//讀者計數(shù)器

intwriterscount=0；//寫者計數(shù)器voidReaders(viod)//讀者進程

{while(TRUE){//調(diào)度P(rwmutex)；//讀寫互斥P(rcmutex)；//進入修改

讀者計數(shù)器互斥readerscount++；//讀者數(shù)量加一

if(readerscount==l)P(nrmutex)；//若是第一個讀者，互斥寫者V(rcmutex)；//

釋放讀者計數(shù)器互斥量V(rwmulex)；//及時釋放讀寫互斥量，允許其它進程申

請read_data(void)；//讀者讀取數(shù)據(jù)P(rcnnutex)://離開臨界區(qū)時讀者計數(shù)

器互斥readerscount-；//讀者數(shù)量減一if(readerscounl==0)V(nrmutex)；//所

有讀者退出臨界區(qū)V(rcmulex)；}//離開時釋放讀者計數(shù)器互斥量}Void

writers(void)//寫者進程{while(TRUE){P(wcmutex)；//獲取寫者隊列互斥量

writerscount++；//寫者隊列加一if(writerscount==l)P(ru/mutex)；//第一寫者

使用讀寫互斥量V(wcmurex)；//釋放寫者計數(shù)互斥量P(nrmutex)；//若臨界

區(qū)有讀者，等待其退出write_data(void)；//寫入數(shù)據(jù)V(nimutex)；//釋放后

續(xù)第一個讀者P(wcmutex)；//獲取寫者隊列互斥量writerscount-；//寫者隊

列減一if(writerscount==0)V(rwmutex)；//最后一個寫者退出，釋放臨界區(qū)

V(wcmutex)；)//釋放寫者計數(shù)互斥量}每個讀者進程最開始都要申請一下

rwmulex信號量，之后在真正做讀操作前即讓出(使得寫進程可以隨時申請到

rwmulex)o而只有第一個寫進程需要中請nnnulex,之后就一直占著不放了，直到

所有寫進程都完成后才讓出。等于只要有寫進程提出申請就禁止讀進程排隊，從而

提高了寫進程的優(yōu)先級。

知識點解析：“寫者優(yōu)先讀者一寫者''問題也是考試的熱點，解決此類問題也分兩方

面，一是讀者訪問臨界區(qū)的最大數(shù)量是有限的，例如說n,那么程序就比較簡單，

看解答中第一部分。若是不限的，則必須設定一個排隊的信號量，所有到達臨界區(qū)

的所有讀者一寫者均需在此排隊，按先來先服務使用臨界區(qū)，一旦進入臨界區(qū)以后

就釋放該信號量。見解答的第二部分。若需要徹底地讓后到的寫者跨越前面等待

的讀者，那么需要設定更多的限制，見解答的第三部分。

46、某32位計算機系統(tǒng)采用段頁式虛擬存儲管理，現(xiàn)有一個進程被分成5段，其

段號和段長見下表，段內(nèi)分頁，頁表見下，存放在內(nèi)存中，每頁的長度為4096B。

進程運行到某一個指令，其地址為（2,3,010）,當前CPU的寄存器和地址加法器

的狀態(tài)如圖所示，當上述指令執(zhí)行時，操作系統(tǒng)如何工作?CPU