一、1.單項選擇題

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

0.下面說法錯誤的是( )。
 (1)算法原地工作的含義是指不需要任何額外的輔助空間
 (2)在相同的規模n下，復雜度O(n)的算法在時間上總是優于復雜度O(2n)的算法
 (3)所謂時間復雜度是指最壞情況下，估算算法執行時間的一個上界
 (4)同一個算法，實現語言的級別越高，執行效率就越低

A.-1
B.(1)，(2)
C.(1)，(4)
D. -3

1.若線性表最常用的運算是查找第i個元素及其前驅的值，則采用(  )存儲方式節省時間。

A.單鏈表
B.雙鏈表
C.單循環鏈表
D.順序表

2.設計一個判別表達式中左右括號是否配對出現的算法，采用(  )數據結構最佳。

A.順序表
B.隊列
C.鏈表
D.棧

3.設n階方陣是一個上三角矩陣，則需存儲的元素個數為(  )。

A.n
B.n×n
C.n×n／2
D.n(n+1)／2

4.在二叉樹的順序存儲中，每個結點的存儲位置與其父結點、左右子樹結點的位置都存在一個簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有n個結點，采用三叉鏈表存儲時，每個結點的數據域需要d個字節，每個指針域占用4個字節，若采用順序存儲，最后一個結點下標為k(起始下標為1)，那么(  )時采用順序存儲更節省空間。

A.d＜12n／(k-n)
B.d＞12n／(k-n)
C.d＜12n／(k+n)
D.d＞12n／(k+n)

5.中綴表達式A-(B+C／D)*E的后綴形式是(  )。

A.AB-C+D／E*
B.ABC+D／-E*
C.ABCD／E*+-
D.ABCD／+E*-

6.有m個葉子結點的哈夫曼樹所具有的結點數為(  )。

A.m
B.m+1
C.2m
D.2m-1

7.簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個結點，其鄰接矩陣為A[1…n，1…n]，且壓縮存儲在B[1…k]，則k的值至少為(  )。

A.n(n+1)／2
B.n²／2
C.(n-1)(n+1)／2
D.n(n-1)／2

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

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

9.快速排序最易發揮其長處的情況是(  )。

A.被排序的數據中含有多個相同排序碼
B.被排序的數據已基本有序
C.被排序的數據完全無序
D.被排序的數據中的最大值和最小值相差懸殊

10.在機器數中，正數的符號位用“1”表示的是(  )。

A.原碼
B.補碼
C.反碼
D.移碼

11.IEEE 754標準規定的64位浮點數格式中，符號位為1位，階碼為11位，尾數為52位。則它所能表示的最小規格化負數為(  )。

A.-(2-2⁵²)×2^-1023
B.-(2-2^-52)×2⁺¹⁰²³
C.-1×2-^-1024
D.-(1-2⁵²)×2⁺²⁰⁴⁷

12.按其數據流的傳遞過程和控制節拍來看，陣列乘法器可認為是(  )。

A.全串行運算的乘法器
B.全并行運算的乘法器
C.串一并行運算的乘法器
D.并啊一串行運算的乘法器

13.字長相同的兩種浮點數，第一種階碼位數較多，尾數位數少，第二種階碼位數少，尾數位數多，階的底數都是2，則(  )。

A.表示的數的范圍與精度相同
B.第一種數的范圍大，但精度低
C.第二種數的范圍大，精度高
D.第一種數的范圍大，精度高

14.4片74181ALU和1片74182CLA器件相配合，具有(  )進位傳遞功能。

A.串行進位
B.組內并行進位，組間并行進位
C.組內并行進位，組間串行進位
D.組內串行進位，組間并行進位

15.需要刷新的存儲器是( )。

A.SRAM
B.DRAM
C.ROM
D.上述三種

16.雙端口存儲器在(  )情況下會發生讀／寫沖突。

A.左端口與右端口的地址碼不同
B.左端口與右端口的地址碼相同
C.左端口與右端口的數據碼相同
D.左端口與右端口的數據碼不同

17.操作數地址存放在寄存器的尋址方式叫(  )。

A.相對尋址方式
B.變址寄存器尋址方式
C.寄存器尋址方式
D.寄存器間接尋址方式

18.在微程序控制中，機器指令和微指令的關系是(  )。

A.每一條機器指令由一條微指令解釋執行
B.每一條機器指令由一段微程序解釋執行
C.每一條微指令由一條機器指令解釋執行
D.每一段微程序由若干條機器指令解釋執行

19.直接映射Cache的主要優點是實現簡單。這種方式的主要缺點是(  )。

A.它比其他幾利Cache組織類型更貴
B.如果使用中的2個或多個block映射到Cache的同一行，命中率將下降
C.它的存取時間大于其他類型
D.Cache 中的Block數隨著主存的容量線性增加

20.由于CPU內部的操作速度較快，而CPU訪問一次主存所花的時間較長，因此機器周期通常用( )來規定。

A.主存中讀取一個指令字的最短時間
B.主存中讀取一個數據字的最長時間
C.主存中寫入一個數據字的平均時間
D.主存中取一個數據字的平均時間

21.DMA方式是在(  )之間建立直接的數據通路。

A.CPU與外部設備
B.外部設備與外部設備
C.主存與外部設備
D.主存與外部設備

22.在設計實時操作系統中，首先要考慮的是(  )。

A.靈活性和可靠性
B.實時性和可靠性
C.交互性和實時性
D.資源利用率

23.(  )進程調度算法綜合考慮到了CPU密集型進程和I／O密集型進程。

A.時間片輪轉
B.優先級
C.多重隊列
D.彩票

24.信號量S的初值定義為5，在S上調用了10次wait操作和8次signal操作后，S的值應為(  )。

A.2
B.3
C.7
D.13

25.臨界區是指并發進程中訪問共享變量的(  )段。

A.管理信息
B.信息存儲
C.數據
D.程序

26.死鎖的預防是通過破壞產生死鎖的四個必要條件來實現的。下列方法中，破壞了“循環等待”條件的是( )。

A.資源按序分配策略
B.銀行家算法
C.一次性分配資源策略
D.資源分配圖化簡法

27.系統“抖動”現象的發生是由(  )引起的。

A.置換算法選擇不當
B.交換的信息量過大
C.內存容量不足
D.請求頁式管理方案

28.兩個進程P、Q都需要三個資源1，2，3，系統中有資源1、2、3各一個，如果P請求資源的順序是1、2、3，Q請求資源的順序任意，共有3!=6種排列，其中共有(  )個排列可能導致死鎖。

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

29.對于三級文件目錄，若主目錄、用戶目錄及子目錄各級分別最多有3、4、5個目錄項，則為找到一指定文件的目錄項(絕對路徑名方式)，最多只需檢索的目錄項數是(  )。

A.12個
B.17個
C.23個
D.60個

30.在文件系統中，文件的不同物理結構有不同的優缺點。在下列文件的物理結構中，(  )具有直接讀寫文件任意一個記錄的能力，又提高了文件存儲空間的利用率。

A.順序結構
B.鏈接結構
C.Hash結構
D.索引結構

31.啟動磁盤執行一次輸入／輸出操作時，(  )是硬件設計時就固定的。

A.尋找時間
B.傳送時間
C.延遲時間
D.一次I／O操作的總時間

32.在網絡中計算機接收的信號是(  )。

A.數字信號
B.模擬信號
C.廣播信號
D.脈沖信號

33.通常通信信道的帶寬越大，在數據傳輸中失真將會(  )。

A.嚴重
B.不變
C.越大
D.越小

34.在共享介質的以太網中，采用的介質訪問控制方法是(  )。

A.并發連接
B.CSMA／CD
C.時間片
D.令牌

35.IP層的功能不包括( )。

A.差錯處理
B.數據報路由選擇
C.無連接的數據報傳輸
D.提供可靠連接

36.路由器在ISO／OSI開放系統參考模型中對應于(  )。

A.物理層
B.數據鏈路層
C.網絡層
D.表示層

37.TCP使用( )機制來進行流量控制。

A.三次握手
B.二次握手
C.Windows窗口
D.滑動窗口

38.下列應用層協議中，(  )協議是基于UDP傳輸的。

A.DNS
B.SMTP
C.HTTP
D.FTP

39.在OSI參考模型中，同一結點內相鄰層之間通過(  )來進行通信。

A.協議
B.接口
C.進程
D.應用程序

二、2.綜合應用題

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

0. 給定單鏈表的結點結構
  typedef struct node *link；
  struct node{int item，link next；)；
 將兩個升序單鏈表歸并為一個升序單鏈表。

1. 某中央處理器的數據通路如圖所示。MDR為內存數據寄存器，PC為程序計數器，IR為指令寄存器。所有的單線箭頭為控制微命令。
  (1)請說明圖中部件X的名稱和功能、寄存器Y的名稱和功能。
  (2)請解釋：為什么要設置T暫存器?
  (3)假定指令格式為RS型指令，其中“SUB R，A”指令的操作為：R←R-[A]，[A]為內存地址A所存儲的內容。請畫出SUB指令的指令周期流程圖，并給出每個微操作對應的微命令。

2. 設某系統有兩種磁盤配置：一種單磁盤結構，一種4磁盤組陣列結構。每個磁盤每磁道64個扇區，每扇區1 024．字節，轉速為10 000 rpm。找道時間為6 ms。兩種結構的磁盤控制器每次訪問的延遲時間均為1 ms。設I／O系統的性能只與磁盤和控制器有關，單磁盤中連續訪問的扇區在磁盤組中將盡量分布在不同磁盤中。設扇區可以按照任意順序讀寫。問：@A@若從單盤結構的順序排列的扇區中讀取4 KB，每次I／O操作用時多少?@B@若從陣列結構的順序排列的扇區中讀取4 KB，每次I／O操作用時多少?@C@設讀請求是隨機的，其中一半的請求從順序排列的扇區中讀取4KB，另一半的請求從順序排列的扇區中讀取16 KB。請比較兩種組織結構的I／O性能。

3. 某閱覽室晚間開放，第一個進入的讀者開燈，最后一個離開的讀者關燈。利用P、V原語操作實現讀者進程。

4. 給定頁面請求序列RS=cadbebabcd，頁框為4，起始為空，寫出LRU頁面置換過程。

5. 如圖所示一臺路由器連接3個以太網。請根據圖中給出的參數回答如下問題：
 (1)該TCP／IP網絡使用的是哪一類IP地址?
 (2)寫出該網絡劃分子網后所采用的子網掩碼。
 (3)系統管理員將計算機D和E按照圖中所示結構連入網絡并使用所分配的地址對TCP／IP軟件進行常規配置后，發現這兩臺機器上的網絡應用程序不能夠正常通信。這是為什么?
 (4)如果你在主機C上要發送一個IP分組，使得主機D和主機E都會接收它，而子網3和子網4上的主機都不會接收它，那么該IP分組應該填寫什么樣的目標IP地址?