計算機專業（基礎綜合）模擬試卷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]的三對角矩陣，按行優先存入一維數組

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

為（）。

A、198

B、195

C、197

D、196

標準答案：B

知識點解析：根據三對角對陣壓縮方法，將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；根據題目，A中元素

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

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

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

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

C、平衡二叉樹

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

標準答案：C

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

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

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

結點數是（）。

A、2k-1-l

B、2kl

C、2k-,+l

D、2卜一1

標準答案：D

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

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

樹即為滿二叉樹，而高度為k的滿二叉樹的結點數是2k—1。

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

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

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

棧來暫存訪問過的頂點

A、I、n

B、口、m

c、I、m

D、I、n、m

標準答案：B

知識點解析：i敘述是錯誤的，因為如果有向圖構成雙向有向環時，則從任一頂點

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

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

個數是（）。

A、e

B、2e

C>n2—e

D、n2—2e-

標準答案：D

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

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

鄰接矩陣中共有產一2e個零元素。

7、從二叉樹的任一結點出發到根的路徑上，所經過的結點序列必按其關鍵字降序

排列的是（）。

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、在下列存儲結構中，數據結構中元素的存儲地址與其關鍵字之間存在某種映射

關系的是()。

A、樹形存儲結構

B、鏈式存儲結構

C、索引存儲結構

D、散列存儲結構

標準答案：D

知識點解析：散列存儲結構將結點按其關鍵字的散列地址存儲到散列表中。

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

A、2

B、3

C、4

D、5

標準答案：B

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

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

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

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

知識點解析：本題要按字典順序進行排序，前半區間中的所有元素都應小于ff,后

半區間中的所有元素都應大于ffo

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

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

()。

A、2.5

B、2

C、1.5

D、1

標準答案：C

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

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

A>0.II11

B、1.0001

C、1.1111

D、1

標準答案：D

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

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

A、將較小的一個階碼調整到與較大的一個階碼相同

B、將較大的一個階碼調整到與較小的一個階碼相同

C、將被加數的階碼調整到與加數的階碼相同

D、將加數的階碼調整到與被加數的階碼相同

標準答案：A

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

15、若內存按字節編址，用存儲容量為32Kx8比特的存儲器芯片構成地址編號

A0000H至DFFFFH的內存空間，則至少需要的片數是()。

A、4

B、6

C、8

D、10

標準答案：C

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

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

16、某計算機的存儲系統由Cache一主存系統構成，Cache的存取周期為10ns,主

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

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

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機的指令條數比CISC機少

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

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

D、RISC機和CISC機都在發展

標準答案：C

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

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

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

令條數要比CISC的多。

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

A、主存儲器

B、控制存儲器

C、通用寄存器

D、指令寄存器

標準答案：B

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

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

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

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

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

A、I、n、in

B、I、n、w

c、u、m、w

D、I、山、IV

標準答案：D

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

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

系的。

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

A、優先級高

B、優先級相等

C、優先級低

D、不一定

標準答案：A

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

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

中離總線控制器最近的設備具有最高優先權。計數器定時查詢和獨立請求方式的優

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

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

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

A、25%

B、50%

C、75%

D、100%

標準答案：B

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

以磁盤利用率為50%。

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

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

是()。

A、32x1(/位/秒

B、8xl()7位/秒

C、73xl()7位/秒

D、18xl()7位/秒

標準答案：C

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

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

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

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

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

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

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

命令：m.圖標菜單；IV.匯編語言；V.C語言；VI.系統調用；

A、I；n；v

B、n；皿；vi

c、m；iv：v

D、口；w；w

標準答案：B

知識點解析：本題考查操作系統的接口，操作系統有二種接口，命令輸入和系統調

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

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

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

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

式來調用。

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

進入臨界區的進程數是()。

A、1

B、2

C、3

D、4

標準答案：A

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

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

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

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

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

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

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

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

資源量的絕對值。

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

A、系統資源總數

B、滿足系統安全的最少資源數

C、用戶最大需求數

D、用戶已占有的資源數

標準答案：B

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

數，得到進程為滿足進程運行尚需要的可能最大資源數，而系統擁有的最大資源數

減去已經分配掉的資源數得到剩余的資源數，比較剩余的資源數是否滿足進程運行

尚需要的可能最大資源數可以得到當前狀態是否安全的結論。而滿足系統安全的最

少資源數并沒有這么一個說法。

26、若有一進程擁有100個線程，這些線程都屬于用戶級線程，則在系統調度執行

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

A、1

B、100

C、1/100

D、0

標準答案：A

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

操作系統中，線程是進程中的一個實體，是系統獨立調度和分派的基本單位。但是

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

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

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

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

線程之間可以并發執行。由于用戶線程不依賴于操作系統內核，因此，操作系統內

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

庫提供的API來創建、司步、調度和管理線程。所以，用戶線程的調度在用戶程

序內部進行，通常采用非搶先式和更簡單的規則，也無須用戶態和核心態切換，所

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

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

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

27、某計算機采用頁式存儲管理，內存中現有1000個頁表項，CPU的cache中可

以存放N個頁表項，該系統中，CPU內存訪問的時間為KJOns,對cache訪問的時

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

于()。

A、850

B、858

C、923

D、842

標準答案：A

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

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

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

項與頁內地址相加，形成指令或數據的物理地址，花費5ns,據此地址，然后到內

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

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

然后，重復上述地址轉段過程，又花去5ns,得到物理地址，再去內存取指令或數

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

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

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

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

復雜。例如系統的字長是否是32位，32位的系統執行一個雙字的時間是1次尋

址，16位系統就需要2次尋址。8位系統的就需要4次尋址。另外，采用什么內存

管理機制，頁式和段式都是執行1次指令尋址需要訪問內存2次，段頁式需要3

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

間的計算與CPU結構和cache的運行模式息息相關，考生應結合計算機組成原

理，妥善解決此類問題。

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

A、用戶所能感知的

B、操作系統所能感知的

C、編譯程序所能感知的

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

標準答案：B

知識點解析：分頁系統中由邏輯地址向物理地址的轉換是系統借助硬件系統自動實

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

系統可以感知頁面的存在，在內存管理過程中，操作系統要為用戶進程分配內存，

回收內存。所以操作系統是頁面最直接的接觸者，它將頁面從計算機系統中到用戶

進行了隔離。

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

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

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

大的文件可以達到()。

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。當采用最短尋道時間優先算法(SSTF)

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

A、618,418

B、306,260

C、306,418

D、618,260

標準答案：B

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

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

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

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

運行方向。

31、UNIX操作系統中，文件的索引結構存放在()。

A、超級塊

B、索引節點

C、目錄項

D、空閑塊

標準答案：B

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

強。UNIX采用的是樹形目錄結構，文件的信息存放在索引節點中，索引節點是一

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

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

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

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

數據塊的直接地址，UNIX系統中文件塊的大小一般是1024字節。所以文件的大

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

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

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

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

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

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

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

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

量的總和。即文件最大可以達節的大小。當然，UNIX文件系統

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

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

索引結構的文件中，必須要用專門的存儲空問來存放索引指針，表示文件的內容存

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

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

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

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

32、在設備管理中，用來實現設備分配的四個數據結構中，每個設備一張，描述設

備的特性和狀態，反映設備的特性、設備和控制器的連接情況的數據結構是()。

A、設備控制表(DCT)

B、系統設備表(SDT)

C、控制器控制表(COCT)

D、通道控制表(CHCT)

標準答案：A

知識點解析：設備控制的數據結構中，系統設備表(SDT)在整個操作系統中只有一

張，記錄了系統中所有的外部設備。經系統設備表找到需使用的外部設備，則數據

結構指針指向設備控制表(DCT),這個數據表每個設備一張，記錄了設備的特性和

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

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

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

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

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

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

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

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

標準答案：A

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

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

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

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

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

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

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

源節點到目的節點之間.的鏈路數為h,每個鏈路上的延遲時間為D秒，數據傳輸

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

是（）。

A、hD+L/B秒

B、S+hD+L/P秒

C、S+hD+L/B秒

D、S+L/B秒

標準答案：C

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

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

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

則本次連接成功。傳送數據。建立電路連接后，發送方通過已建立的電路向接收方

發送數據。拆除電路。數據傳輸完畢，發送方或接收方任一方發出拆線信號，終止

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

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

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

后,發送方還可連續發送的幀數是（）“

A、2幀

B、3幀

C、4幀

D、1幀

標準答案：B

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

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

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

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

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

收，因此窗口向右移動3個幀，目前已經發送了3號幀，因此可連續發送的幀數是

窗口大小一已經發送的項數，即4—1=3,答案是B。

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

255.255.255.192,那么該主機所在的子網的網絡地址是（）。

A、130.25.0.0

B、130.25.3.0

C、130.25.3.128

D、130.25.3.255

標準答案：C

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

有關，因此130.25.3.135的二進制為130.25.3.10000111,子網掩碼的二

進制為255.255.255.11000000,兩者相與，因此網絡地址為

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

37、為了限制路由信息傳播的范圍，OSPF、協議把網絡劃分成4種區域（Area）,其

中連接各個區域的傳輸網絡是（）。

A、不完全存根區域

B、標準區域

C、主干區域

D、存根區域

標準答案：C

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

OSPF是以主干區域（area。）為頂點，其他區域為終端的星形拓撲結構。標準區域可

以接收鏈路更新信息和路由總結。存根區域是不接受自治系統以外的路由信息的區

域。如果需要自治系統以外的路由，它使用默認路由0.0.0.0。完全存根區域

不接受外部自治系統的路由以及自治系統內其他區域的路由總結，需要發送到區域

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

許接收以LSAType7發送的外部路由信息，并且要把LSAType7轉換成

LSAType5o因此答案是C。

38、一臺主機的IP地址為11.I.1.100,子網掩碼為255.0.0.0。現在用戶

需要配置該主機的默認路由。經過觀察發現，與該主機直接相連的路由器具有如下

4個IP地址和子網掩碼：I.IP地址：11.1.1.1,子網掩碼：255.0.0.0

n.1P地址：II.1.2.1,子網掩碼：255.0.0.0山.IP地址：1

2.1.1.1,子網掩碼：255.0.0.0W.IP地址：13.1.2.1,子網掩碼：

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

A、I和口

B、I和m

C>CC和w

D、in和w

標準答案：A

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

占用的空間和搜索路由表所用的時間。這種轉發方式在一個網絡只有很少的對外連

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

II.0.0.Oo選項I的網絡地址為11.0.0.0,選項II的網絡地址為

11.0.0.0,選項HI的網絡地址為12.0.0.0,選項IV的網絡地址為

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

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

A、是由交換機的生產廠商建立的

B、是交換機在數據轉發過程中通過學習動態建立的

C、是由網絡管理員建立的

D、是由網絡用戶利用特殊的命令建立的

標準答案：B

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

分，路由表可以由人為配置靜態路由，也可以通過動態協議建立，而對于交換機，

映射表只能在數據轉發中進行動態學習建立，并且每個表項都有定時器，具體是收

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

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

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

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

A、電子郵件只能發送文本文件

B、電子郵件可以發送圖形文件

C、電子郵件可以發送二進制文件

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

標準答案：A

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

郵件統中SMTP不能傳送可執行文件或其他的二進制對象。SMTP限于傳送7位的

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

SMTP的前提下，增加了郵件主體的結構，并定義了傳送非ASCII碼的編碼規

則.因此答案為A.

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

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

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

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

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

是二叉樹根結點的指針)。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)；//返回后序序列第一個結點的指針

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

42、設有一個帶頭結點的循環單鏈表，其結點值均為正整數。試設計一個算法，反

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

表空為止，最后再刪除表頭結點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C3、C7、Cu和C|5雖然這兩種方式小組內的位數不同，但產生全部進位的時間是

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

為ly,則每一級進位的延遲時間為2ty。C]經過2ty產生第1小組的進位及所有組

進位產生函數G「和組進位傳遞函數Pi*；再經過2ty,由大組產生相應的進位；再

經過2ty后，才能產生第2、3、4小組內的其余的進位，所以最長的進位延遲時間

者B為6tyo

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

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

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

移位器1-1R.MDR

“L-￡^JR.

rm1凡Ld

DR,MAR

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

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

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

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

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

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

CR~凡DR~旦

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

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

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

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

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

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

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

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

總線結構形式。

45、實現一個經典的“讀者一寫者”算法時，若當前臨界區中有讀者訪問，寫者再來

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

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

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

權。具體說，寫者到達后，已經在臨界區內的讀者繼續讀取直到結束，而后來的讀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

現，它必然優先進入臨界區。typedefintsemaphore；//定義信號量semaphore

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

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

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

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

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

讀者計數器互斥readerscount++；//讀者數量加一

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

提高了寫進程的優先級。

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

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

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

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

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

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

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

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

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

的狀態如圖所示，當上述指令執行時，操作系統如何工作?CPU