一、1.單項選擇題

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

0.將5個字母“ooops”按此順序入棧，則有(  )種不同的出棧順序可以仍然得到“ooops”。

A.1
B.3
C.5
D.6

1.設有10階矩陣A，其對角線以上的元素a_ij(1≤j≤10，1＜i＜j)均取值為-3，其他矩陣元素為正整數，現將矩陣A壓縮存儲放在一維數組F[m]中，則m為(  )。

A.45
B.46
C.55
D.56

2.—棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DFBAC，則先序遍歷序列為( )。

A.ACBED
B.DECAB
C.DEABC
D.CEDBA

3.以下敘述不正確的是(  )。

A.后序線索二叉樹是不完善的，要對它進行遍歷，不需使用棧
B.任何一棵二叉樹的后序線索樹進行后序遍歷時都必須使用棧
C.任何一棵二叉樹都可以不用棧實現先序線索樹的先序遍歷
D.任何一棵二叉樹都可以不用棧實現中序線索樹的中序遍歷

4.如果一棵完全二叉樹共有26個結點，則必定有(  )個結點的度為1。

A.0
B.1
C.3
D.13

5.在散列表中，當裝填因子非常接近1時，線性探測類似于(  )查找。

A.二分
B.隨機
C.順序
D.分塊

6.高度為7的AVL樹最少有(  )個結點。

A.31
B.32
C.33
D.34

7.

A.a b c f d e g
B.a b c g f d e
C.a b c d e f g
D.a b c f g d e

8.設有關鍵字序列F={Q，G，M，Z，A，N，P，X，H)，下面(  )序列是從上述序列出發建堆的結果。

A.A，G，H，M，N，P，Q，X，Z
B.A，G，M，H，Q，N，P，X，Z
C.G，M，Q，A，N，P，X，H，Z
D.H，G，M，P，A，N，Q，X，Z

9.若數據元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法只能是(  )。

A.起泡排序
B.插入排序
C.選擇排序
D.二路歸并排序

10.使用海明碼來檢出并糾正一位錯，當有效代碼長度為8位時，至少需要(  )位校驗位。

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

11.下列關于加法器的說法錯誤的是(  )。

A.實現n位的串行加法器只需1位全加器
B.實現n位的并行加法器需要n位全加器
C.影響并行加法器速度的關鍵因素是加法器的位數的多少
D.加法器是一種組合邏輯電路

12.某256×1位的存儲芯片內部結構為16×16的存儲元矩陣，且采用“重合法”的譯碼驅動方式來選擇存儲元，則該芯片引腳中地址線的數目為(  )。

A.256
B.32
C.16
D.8

13.下列四種存儲器中，存取速度最快的是(  )。

A.DRAM
B.SRAM
C.掩模式ROM
D.EPROM

14.下列關于一地址指令的說法正確的是(  )。

A.可能是數據傳送指令
B.可能是實現單目運算的運算指令
C.可能是實現雙目運算的運算指令
D.以上都有可能

15.堆棧(軟堆棧)尋址的尋址方式可看作是(  )n

A.寄存器尋址
B.寄存器間接尋址
C.基址尋址
D.直接尋址

16.關于基址尋址和變址尋址，下列說法中錯誤的是(  )。

A.兩者都可擴大指令的尋址范圍
B.兩者在取操作數之前都需要對有效地址進行計算
C.在程序執行過程中，基址寄存器的內容不可變，變址寄存器中的內容可變
D.基址寄存器和變址寄存器的內容都由用戶確定

17.指令流水線中出現數據相關時流水線將受阻，(  )可解決數據相關問題。

A.增加硬件資源
B.采用旁路技術
C.采用分支預測技術
D.以上都可以

18.設CPU與I／O設備以中斷方式進行數據傳送，CPU響應中斷時，該I／O設備接口控制器送給CPU的中斷向量表(中斷向量表存放中斷向量)指針是0800H，0800H單元中的值為1200H。則該I／O設備的中斷服務程序在主存中的入口地址為(  )。

A.0800H
B.0801H
C.1200H
D.1201H

19.CPU的工作周期為20 ns，主存存取周期為10 ns，此時DMA接口適合采用(  )方式與CPU共享主存。

A.停止CPU訪問主存
B.周期挪用
C.DMA與CPU交替訪存
D.以上無正確選項

20.假設某計算機的存儲系統由Cache和主存組成j某程序執行過程中訪存1 000次，其中訪問Cache缺失(未命中)50次，則Cache的命中率是(  )。

A.5％
B.9．5％
C.50％
D.95％

21.關于DMA方式和通道方式，下列說法中錯誤的是(  )。

A.DMA的數據傳送全部由硬件控制，而通道方式通過執行通道程序來傳送數據
B.一個DMA控制器連接多臺外設時，這些外設只能串行工作
C.一個通道可連接多臺外設，且可使這些外設并行工作
D.DMA控制器和通道都可以連接各種高低速設備

22.分時系統中，為使多個用戶能夠同時與系統交互，最關鍵的問題是(  )。

A.計算機具有足夠的運行速度
B.內存容量應足夠大
C.系統能及時地接收多個用戶輸入
D.能在一短的時間內，使所有用戶程序都能運行

23.計算機操作系統中，若WAlT、SIGNAL操作的信號量S初值為3，當前值為-2，則表示當前有(  )個等待信號量S的進程。

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

24.假定系統擁有某類資源10個。在該系統上運行的所有作業，其對該類資源的需求量不會超過2個。為了提高資源利用率，我們打算對這種資源采用動態分配，但用限制系統中并發執行的作業數來防止發生死鎖。你認為作業調度允許并發執行的最大作業數應是(  )。

A.1
B.8
C.9
D.10

25.設某進程的訪問串為1、3、1、2、4，駐留集為3塊，當訪問4號頁面時，按LRU頁面替換算法，應淘汰( )號頁面。

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

26.文件系統的主要目的是(  )。

A.實現對文件的按名存取
B.實現虛擬存儲器
C.提高外圍設備的輸入輸出速度
D.用于存儲系統文檔

27.虛擬存儲管理系統的基于程序的局部性理論，(  )是指最近被訪問的存儲單元可能馬上被訪問。

A.數據局部性
B.空間局部性
C.時間局部性
D.空間全局性

28.我們把一段時間內，只允許一個進程訪問的資源，稱為臨界資源，因此，我們可以得出以下論述，請選擇一條正確的論述( )。

A.對臨界資源是不能實現資源共享的
B.對臨界資源，應采取互斥訪問方式，來實現共享
C.為臨界資源配上相應的設備控制塊后，便能被共享
D.對臨界資源應采取同時訪問方式，來實現共享

29.有關設備管理概念的下列敘述中，(  )是不正確的。

A.通道是處理輸入、輸出的軟件
B.所有外圍設備的啟動工作都由系統統一來做
C.來自通道的I／O中斷時間由設備管理負責處理
D.編制好的通道程序是存放在主存儲器中的

30.驅動調度算法中，(  )算法可能會隨時改變移動臂的運動方向。

A.電梯調度
B.最短尋找時間優先
C.掃描
D.單向掃描

31.對于一個文件的訪問，常由(  )共同限制。

A.用戶訪問權限和文件屬性
B.用戶訪問權限和用戶優先級
C.優先級和文件屬性
D.文件屬性和口令

32.為了使數據在網絡中的傳輸延遲最小，首選的交換方式是(  )。

A.電路交換
B.報文交換
C.分組交換
D.信元交換

33.假定有一條通帶為100 kHz的信道，每路信號的帶寬為3．2 kHz，各路信號間的防護帶寬為0．8 kHz。若采用頻分多路復用，那么最多可以同時傳輸(  )路信號。

A.10路
B.20路
C.25路
D.40路

34.一個ATM網絡的源端點和目的端點之間有三個ATM交換機，現在要建立一條虛電路，一共需要發送( )個報文。

A.12
B.15
C.18
D.21

35.下列設備中，可以分割廣播域的是(  )。

A.集線器
B.網橋
C.以太網交換機
D.路由器

36.路由器采用( )方式來發送IP分組。

A.存儲轉發機制
B.直通交換機制
C.分組交換機制
D.分組檢測機制

37.TCP是采用(  )來控制流量的。

A.設定擁塞窗口
B.TCP首部中的接收窗口
C.設定擁塞閥值
D.通過標志位來通知

38.一個UDP用戶的數據報的數據部分長為8 192字節。那么通過以太網來傳播該UDP數據報時，最后一個IP分片的數據長度是(  )。

A.1 500
B.1 480
C.800
D.600

39.在使用瀏覽器打開某個網頁時，用戶輸入網址后，瀏覽器首先要進行(  )。

A.域名到IP地址的解析
B.和服務器建立TCP連接
C.發送UDP分組到服務器
D.發出GET的HTTP命令來獲得網頁內容

二、2.綜合應用題

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

0. 某汽車輪渡口，過江渡船每次能載10輛車過江。過江車輛分為客車類和汽車類，上渡船有如下規定：同類車先到先上船，客車先于貨車上船，且每上4輛客車，才允許上一輛貨車，若等待客不足4輛，則以貨車代替，若無貨車等待允許客車都上船。寫一算法模擬渡口管理。

1. 某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通(但不一定有直接的道路相連，只要互相間接通過道路即可)，并要求增設的道路條數為最少，要解決這個問題，問：
 (1)可用什么數據結構來表示城鎮和道路；
 (2)請用偽代碼描述效率最高的解法。

2. 已知某CPU有16根地址線、8根數據線，并用MREQ作為訪存控制信號(低電平有效)。現有下列存儲芯片：1 K×4位ROM、2 K×4位ROM、4 K×8位ROM、4 K×8位RAM、8 K×4位RAM、8 K×8位RAM和非門、與非門、或非門若干，如下圖所示。試對該機存儲系統進行設計，要求：0～2 047為系統程序區，4 096～16 383為用戶程序區，在不浪費存儲容量的基礎上使用最少數量的存儲芯片。
  (1)畫出主存地址空間分配示意圖；
  (2)說明使用存儲芯片的種類及數量；
  (3)使用所給門電路畫出存儲芯片片選邏輯圖(片選信號低電平有效)。

3.

4. 設某計算機系統有一塊CPU、一臺輸入設備、一臺打印機。現有兩個進程同時進入就緒狀態，且進程A先得到CPU運行，進程B后運行。進程A的運行軌跡為：計算50 ms，打印信息100 ms，再計算50 ms，打印信息100 ms，結束。進程B的運行軌跡為：計算50 ms，輸入數據80 ms，再計算100 ms，結束。試畫出它們的時序關系圖(可以用甘特圖)，并說明：
 (1)開始運行后，CPU有無空閑等待?若有，在哪段時間等待?計算CPU的利用率。
 (2)進程A運行時有無等待現象?若有，在什么時候發生等待現象?
 (3)進程B運行時有無等待現象?若有，在什么時候發生等待現象?

5. 關于死鎖的銀行家算法是圍繞“安全狀態”的概念工作的。當系統預測到不安全狀態時，就拒絕分配資源，但是，銀行家算法要求的條件并不是必要的。例如，某系統有12個資源供進程P0、P1、P2使用。目前的分配情況如下：

 (1)請說明系統處于不安全狀態；
 (2)請說明系統并不一定死鎖。

6. 如下圖所示有一個移動主機，原來的IP地址是160．80．40．20／16，為了移動到其他網絡，它將160．80．40．26設置為了本地代理。之后它移動到了179．56．0．0／16的網絡中，設置了179．56．0．1為外部代理，并且獲得了新的IP地址179．56．78．69。請問：
 (1)如果這時候該主機和其他主機通信，對端需要把數據發給什么地址?
 (2)當一個160．80．40．20到達160．80．0．0／16網絡后，會有主機響應該ARP請求嗎?
 (3)本地代理需要將發送給移動主機的分組發送到哪個地址?