一、1.單項選擇題

單項選擇題
1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。

0.若已知一個棧的入棧序列是1，2，3……．n，其輸出序列為p1，p2，p3……．pn，若p1=n，則pi是(     )。

A.i
B.n-i
C.n-i+1
D.不確定

1.將一個A[1……100，1……100]的三對角矩陣，按行優先存入一維數組B[1．．298]中，A中元素A_66,65(即該元素下標i=66，j=65)，在B數組中的位置k為(     )。

A.1 98
B.1 95
C.197
D.1 96

2.查找效率最高的二叉排序樹是(     )。

A.所有結點的左子樹都為空的二叉排序樹
B.所有結點的右子樹都為空的二叉排序樹
C.平衡二叉樹
D.沒有左子樹的二叉排序樹

3.一棵深度為k的平衡二叉樹，其每個非葉子結點的平衡因子均為0，則該樹的結點數是(     )。

A.2^k-1-1
B.2^k-1
C.2^k-1+1
D.2^k一1

4.以下敘述正確的是(     )。
  I．對有向圖G，如果以任一頂點出發進行一次深度優先或廣度優先搜索能訪問到每個頂點，則該圖一定是完全圖
  Ⅱ．連通圖的廣度優先搜索中一般要采用隊列來暫存訪問過的頂點
  Ⅲ．圖的深度優先搜索中一般要采用棧來暫存訪問過的頂點

A. I、Ⅱ
B.Ⅱ、Ⅲ
C. I、Ⅲ
D. I、Ⅱ、Ⅲ

5.一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結構中零元素的個數是(     )。

A.e
B.2e
C.n²-e
D.n²-2e

6.從二叉樹的任一結點出發到根的路徑上，所經過的結點序列必按其關鍵字降序排列的是 (     )。

A. 二叉排序樹
B.大頂堆
C.小頂堆
D.平衡二叉樹

7.順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均查找長度為(     )。

A.21
B.23
C.41
D.62

8.在下列存儲結構中，數據結構中元素的存儲地址與其關鍵字之間存在某種映射關系的是 (     )。

A.樹形存儲結構
B.鏈式存儲結構
C.索引存儲結構
D.散列存儲結構

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

A.2
B.3
C.4
D.5

10.下列序列中，執行第一趟快速排序的結果是(     )。

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]

11.某工作站采用時鐘頻率f為15MHz，處理速率為10MIPS的處理機來執行一個已知混合程序。假定每次存儲器存取為1周期延遲，試問此計算機的有效CPI是(     )。

A.2．5
B.2
C.1.5
D.1

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

A.0．11 11
B.1．0001
C.1．11 11
D.1

13.浮點加減中的對階是(     )。

A.將較小的一個階碼調整到與較大的一個階碼相同
B.將較大的一個階碼調整到與較小的一個階碼相同
C.將被加數的階碼調整到與加數的階碼相同
D.將加數的階碼調整到與被加數的階碼相同

14.若內存按字節編址，用存儲容量為32K×8比特的存儲器芯片構成地址編號A0000H至DFFFFH的內存空間，則至少需要的片數是(     )。

A.4
B.6
C.8
D.10

15.某計算機的存儲系統由Cache一主存系統構成，Cache的存取周期為10ns，主存的存取周期為50ns。在CPU執行一段程序時，Cache完成存取的次數為4800次，主存完成的存取次數為200次，該Cache一主存系統的效率是(     )。

A.0．856
B.0．862
C.0.958
D.0.96

16.對于RISC機和CISC機，以下說法錯誤的是(     )。

A.RISC機的指令條數比CISC機少
B.RISC機指令的平均字長比CISC機指令的平均字長短
C.對大多數計算任務來說，RISC機程序所用的指令條數比CISC機少
D.RISC機和CISC機都在發展

17.微程序在計算機中存放的位置是(     )。

A.主存儲器
B.控制存儲器
C.通用寄存器
D.指令寄存器

18.下列各敘述中正確的命題是(     )。
  I．在取指周期中也可能從內存取到操作數
  Ⅱ．CPU的訪存時間是由存儲器的容量決定的，存儲容量越大，訪存時間就越長
  Ⅲ．在主存與Cache之間的直接映射方式下，不采用替換策略也可以實現正確的塊替換
  Ⅳ．動態存儲器的讀操作也具有刷新的功能

A.I、Ⅱ、Ill
B.I、Ⅱ、Ⅳ
C.Ⅱ、Ⅲ、Ⅳ
D.I、Ⅲ、Ⅳ

19.在菊花鏈方式中，靠近控制器的設備與遠處設備的(     )。

A.優先級高
B.優先級相等
C.優先級低
D.不一定

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

A.25％
B.50％
C.75%
D.100%

21.設存儲器容量為32字，字長64位，模塊數m=4，存儲周期T=200ns，數據總線寬度為64位，總線傳送周期τ=50ns。用交叉方式進行組織，交叉存儲器的帶寬是(     )。

A.32×10⁷位／秒
B.8×10⁷位／秒
C.73×10⁷位／秒
D.18×10⁷位／秒

22.操作系統為用戶提供了多種接口，它們是(     )。
  I．計算機高級指令；Ⅱ．終端命令；Ⅲ．圖標菜單；Ⅳ．匯編語言；V．C語言；Ⅵ．系統調用；

A.I；Ⅱ；V
B.Ⅱ；Ⅲ；Ⅵ
C.Ⅲ；Ⅳ；V
D.Ⅱ；Ⅳ；Ⅵ

23.若一個信號量的初值為3，經過多次PV操作以后當前值為一1，此表示等待進入臨界區的進程數是(     )。

A.1
B.2
C.3
D.4

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

A.系統資源總數
B.滿足系統安全的最少資源數
C.用戶最大需求數
D.用戶已占有的資源數

25.若有一進程擁有100個線程，這些線程都屬于用戶級線程，則在系統調度執行時間上占用的時間片是(     )。

A.1
B.100
C.1／100
D.0

26.某計算機采用頁式存儲管理，內存中現有1000個頁表項，CPU的cache中可以存放N個頁表項，該系統中，CPU內存訪問的時間為lOOns，對cache訪問的時間是5ns，如果希望頁表映射的平均時間降到20ns以下，那么cache中的N必須高于(     )。

A.850
B.858
C.923
D.842

27.分頁系統中的頁面是(     )。

A.用戶所能感知的
B.操作系統所能感知的
C.編譯程序所能感知的
D.鏈接裝配程序所能感知的

28.某操作系統的文件管理采用直接索引和多級索引混合方式，文件索引表共有10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接索引項，假定物理塊的大小是1K，每個索引項占用4個字節，則該文件系統中最大的文件可以達到(     )。

A.65800K
B.65792K
C.65536K
D.34000K

29.設磁盤的IO請求隊列中所要訪問的磁道號為：96，184，25，120，1 2，126，73，75，當前磁頭在96，前一次在90。當采用最短尋道時間優先算法(SSTF)和電梯算法所要移動的距離是(     )。

A.618，418
B.306，260
C.306,418
D.618,260

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

A.超級塊
B.索引節點
C.目錄項
D.空閑塊

31.在設備管理中，用來實現設備分配的四個數據結構中，每個設備一張，描述設備的特性和狀態，反映設備的特性、設備和控制器的連接情況的數據結構是(     )。

A.設備控制表(DCT)
B.系統設備表(SDT)
C.控制器控制表(COCT)
D.通道控制表(CHCT)

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

A.第N層為第N+1層提供服務
B.第N+1層將從第N層接收的信息增加了一個頭
C.第N層利用第N+1層提供的服務
D.第N層對N+1層沒有任何作用

33.設待傳送數據總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源節點到目的節點之間．的鏈路數為h，每個鏈路上的延遲時間為D秒，數據傳輸率為B bps，電路交換建立連接的時間為S秒，則傳送所有數據，電路交換需時間是(     )。

A.hD+L／B秒
B.S+hD+L／P秒
C.S+hD+L／B秒
D.S+L／B秒

34.若數據鏈路的發送窗口尺寸WT=4，在發送3號幀、并接到2號幀的確認幀后，發送方還可連續發送的幀數是(     )。

A.2幀
B.3幀
C.4幀
D.1幀

35.TCP／IP網絡中，某主機的IP地址為130．25．3．1 35，子網掩碼為255．255．25 5．1 92，那么該主機所在的子網的網絡地址是(     )。

A.130．25．0．0
B.130．25．3．0
C.130．25．3．128
D.130．25．3．255

36.為了限制路由信息傳播的范圍，OSPF、協議把網絡劃分成4種區域(Area)，其中連接各個區域的傳輸網絡是(     )。

A.不完全存根區域
B.標準區域
C.主干區域
D.存根區域

37.一臺主機的IP地址為11．1．1．100，子網掩碼為255．0．0．0。現在用戶需要配置該主機的默認路由。經過觀察發現，與該主機直接相連的路由器具有如下4個IP地址和子網掩碼：
  I．IP地址：1 1．1．1．1，子網掩碼：255．0．0．0
  Ⅱ．IP地址：11．1．2．1，子網掩碼：255．0．0．0
  Ⅲ．IP地址：1 2．1．1．1，子網掩碼：255．0．0．0
  Ⅳ．IP地址：13．1．2．1，子網掩碼：255．0．0．0
  請問IP地址和子網屏蔽碼可能是該主機的默認路由的是(     )。

A.I和Ⅱ
B.I和Ⅲ
C.I、Ⅲ和Ⅳ
D.Ⅲ和Ⅳ

38.以太網交換機中的端口／MAC地址映射表是(     )。

A.是由交換機的生產廠商建立的
B.是交換機在數據轉發過程中通過學習動態建立的
C.是由網絡管理員建立的
D.是由網絡用戶利用特殊的命令建立的

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

A.電子郵件只能發送文本文件
B.電子郵件可以發送圖形文件
C.電子郵件可以發送二進制文件
D.電子郵件可以發送主頁形式的文件

二、2.綜合應用題

綜合應用題
41-47小題，共70分。

0. 已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一個結點的指針，是否可不用遞歸且不用棧來完成?請簡述原因。

1. 設有一個帶頭結點的循環單鏈表，其結點值均為正整數。試設計一個算法，反復找出單鏈表中結點值最小的結點，并輸出之，然后將該結點從中刪除，直到單鏈表空為止，最后再刪除表頭結點。

2. 什么是單重分組和雙重分組跳躍進位鏈?一個按3，5，3，5分組的雙重分組跳躍進位鏈(最低位為第O位)，試問大組中產生的是哪幾位進位?與4，4，4，4分組的雙重分組跳躍進位鏈相比，試問產生全部進位的時間是否一致?為什么?

3. 某機的主要部件如下圖所示。
  
  (1)請補充各部件間的主要連接線，并注明數據流動方向。
  (2)擬出指令SUB(R₁)，一(R₂)的執行流程(含取指過程與確定后繼指令地址)。該指令的含義是進行減法操作，源操作數地址和目的操作數地址分別在寄存器R₁和R₂中，目的操作數尋址方式為自減型寄存器間接尋址。
  其中：LA—A輸入選擇器，LB—B輸入選擇器，C、D一暫存器。

4. 實現一個經典的“讀者一寫者”算法時，若當前臨界區中有讀者訪問，寫者再來時必須在臨界區外面等候，如果其后讀者源源不斷地到達，按策略他們均可以進入臨界區，始終保持臨界區中有讀者訪問，那么寫者可能長時間不能進入臨界區而形成饑餓。為解決此類問題，我們修改訪問策略，要求當寫者到達時，寫者具有優先權。具體說，寫者到達后，已經在臨界區內的讀者繼續讀取直到結束，而后來的讀者就不能進入臨界區。等所有的讀者離開臨界區以后讓寫者先進去訪問，然后等寫者離開后再允許讀者進入臨界區。這所謂“寫者優先讀者一寫者’’問題。請用信號量和PV操作來描述這一組進程的工作過程。

5. 某32位計算機系統采用段頁式虛擬存儲管理，現有一個進程被分成5段，其段號和段長見下表，段內分頁，頁表見下，存放在內存中，每頁的長度為4096B。進程運行到某一個指令，其地址為(2，3，010)，當前CPU的寄存器和地址加法器的狀態如圖所示，當上述指令執行時，操作系統如何工作?CPU中各個寄存器和快表的值為多少?(均為十六進制)。
  
  當前CPU的寄存器和地址加法器的狀態：
  
  請填寫指令執行時的狀況：
  

6. 設需在兩臺計算機間經兩個中間節點傳送100M字節的文件，假定：
  (1)計算機與中間節點間的通信線路以及中間節點間通信線路的通信速率皆為8Kbps；
  (2)數據傳輸的差錯可以忽略不計；
  (3)中間節點存儲轉發時間可忽略不計；
  (4)每一段線路的傳播時延均為10ms
  試計算采用甲、乙兩種方案傳送此文件所需時間。其中：
  (1)方案甲：將整個文件逐級存儲轉發。
  (2)方案乙：將文件分為1000字節長的幀在進行逐級存儲轉發，假定幀頭和幀尾的開銷為10字節。