一、1.單項選擇題

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

0.下面程序段中，執行S語句的次數為(  )。
  for(int i=1；i＜=n；i++)
  for(int j=1；j＜=i；j++)
  S；

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

1.單鏈表中有10個元素，head是表頭，以下代碼結束后，X存放表中第7個結點指針的概率是(  )。(rand()返回一個隨機整數，為0到機內最大整數之間的一個數)
  int m=0；link t，x；
  for(t=head；t!=NULL；t=t=＞next)
  if(rand()％++m=0)x=t；

A.1／3
B.1／10
C.1／7
D.1／2

2.若一個棧的輸入序列為1，2，3，…，n，輸出序列的第一個元素為i，則第j個輸出元素為(  )。

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

3.一個循環隊列Q最多可存儲m個元素，已知其頭尾指針分別是front和rear，則判定該循環隊列為滿的條件是( )。

A.Q．rear-Q．front==m
B.Q．rear!=Q．front
C.Q．front==(Q．rear+1)％m
D.Q．front==Q．rear％m+1

4.已知有一維數組A[0…m*n-1]，若要對應為m行n列的矩陣，則下面的對應關系(  )可將元素A[k](0＜=k<rn*n)表示成矩陣的第i行、第j列的元素(0＜=i＜m，0＜=j＜n)。

A.i=k／n，j=k％m
B.i=k／m，j=k％m
C.i=k／n，j=k％n
D.i=k／m，j=k％n

5.一棵哈夫曼樹共有215個結點，對其進行哈夫曼編碼，共能得到(  )個不同的碼字。

A.107
B.108
C.214
D.215

6.二叉樹的先序遍歷和中序遍歷的遍歷結果如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是(  )。

A.E
B.F
C.G
D.H

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

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

8.有一個長度為12的有序表，按二分查找法對該表進行查找，在表內各元素等概率查找情況下，查找成功所需的平均比較次數為(  )。

A.37／12
B.35／12
C.39／12
D.43／12

9.下列幾種排序方法中，要求內存量最大的是(  )。

A.插入排序
B.快速排序
C.歸并排序
D.選擇排序

10.計算機硬件能直接識別執行的語言是(  )。

A.機器語言
B.匯編語言
C.高級語言
D.第四代語言

11.計算機系統采用補碼運算是為了(  )。

A.與手工運算方式保持一致
B.提高運算速度
C.簡化計算機的設計
D.提高運算精度

12.若n+1位數的二進制整數為X=X，X₁，…，X_n，X移碼數值的取值范圍是(  )。

A.-2n≤X＜2ⁿ
B.-2ⁿ-1≤X＜2ⁿ
C.-2^n-1≤X＜2ⁿ
D.-2ⁿ≤X＜2ⁿ-1

13.下列幾項中，不符合RISC指令系統的特點的是(  )。

A.指令長度固定，指令種類少
B.尋址方式種類盡量減少，指令功能盡可能強
C.增加寄存器的數目，以盡量減少訪存次數
D.選取使用頻率最高的一些簡單指令，以及很有用但不復雜的指令

14.下面元件存取速度最快的是(  )。

A.Cache
B.寄存器
C.外存
D.內存

15.指令的尋址方式有順序和跳躍兩種方式，采用跳躍尋址方式，可以實現(  )。

A.堆棧尋址
B.程序的條件轉移
C.程序的無條件轉移
D.程序的條件或無條件轉移

16.指令系統中采用不同尋址方式的目的主要是(  )。

A.可以直接訪問外存
B.實現存儲程序和程序控制
C.縮短指令長度，擴大尋址空間，提高編程靈活性
D.提供擴展操作碼的可能并降低指令譯碼難度

17.計算機主頻的周期是指(  )。

A.指令周期
B.時鐘周期
C.CPU周期
D.存取周期

18.就微命令的編碼方式而言，若微操作命令的個數已確定，則(  )。

A.采用直接表示法的微指令字長通常比采用編碼表示法的微指令字長短
B.采用編碼表示法的微指令字長通常比采用直接表示法的微指令字長短
C.采用編碼表示法的微指令字長與采用直接表示法的的微指令字長相等
D.采用編碼表示法的微指令字長與采用直接表示法的的微指令字長大小關系不確定

19.下列說法中不正確的是(  )。

A.每個程序的虛地址空間可以遠大于實地址空間，也可以遠小于實地址空間
B.多級存儲體系由Cache、主存和虛擬存儲器構成
C.Cache和虛擬存儲器這兩種存儲器管理策略都利用了程序的局部性原理
D.當Cache未命中時，CPU可以直接訪問主存，而外存與CPU之間則沒有直接通路

20.為了便于實現多級中斷，保存現場信息最有效的方法是采用(  )。

A.通用寄存器
B.堆棧
C.存儲器
D.外存

21.交叉存儲器實質上是( )。

A.一種模塊式存儲器，能并行執行多個獨立的讀寫操作
B.一種模塊式存儲器，能串行執行多個獨立的讀寫操作
C.一種整體式存儲器，能并行執行多個獨立的讀寫操作
D.一種整體式存儲器，能串行執行多個獨立的讀寫操作

22.所謂(  )是指將一個以上的作業放入主存，并且同時處于運行狀態，這些作業共享處理機的時間和外圍設備等其他資源。

A.多重處理
B.多道程序設計
C.實時處理
D.共同執行

23.

A.P1 P2 P4 P5 P3
B.P2 P1 P4 P5 P3
C.P2 P4 P5 P1 P3
D.P4 P2 P5 P1 P3

24.若有4個進程共享同一程序段，每次允許3個進程進入該程序段，用P、V操作作為同步機制，則信號量S的取值范圍是(  )。

A.4，3，2，1，0
B.3，2，1，0，-1
C.2，1，0，-1，-2
D.1，0，-1，-2，-3

25.一個進程被喚醒意味著( )。

A.該進程馬上占有CPU
B.進程狀態變為就緒狀態
C.進程的優先級變為最高
D.其PCB移至就緒隊列的隊首

26.3個進程共享4個同類資源，這些資源的分配與釋放只能一次一個。已知每一個進程最多需要兩個該類資源，則該系統(  )。

A.有某進程可能永遠得不到該類資源
B.必然有死鎖
C.進程請求該類資源立刻能得到
D.必然無死鎖

27.在計算機系統中構成虛擬存儲器時(  )。

A.只需要一定的硬件資源便可實現
B.只需要一定的軟件即可實現
C.既需要軟件也需要硬件方可實現
D.既不需要軟件也不需要硬件

28.使Cache命中率最高的替換算法是( )。

A.先進先出算法FIFO
B.隨機算法RAND
C.先進后出算法FILO
D.最近最少使用算法LRU

29.某計算機系統，它的FCB占64B，一個磁盤塊的大小為1 KB，采用1級目錄，假定文件目錄中有3 200個目錄項，則查找一個文件平均啟動盤塊的次數是(  )。

A.50
B.100
C.54
D.200

30.操作系統中的SPOOLing技術，實質是將(  )轉化為共享設備的技術。

A.虛擬設備
B.獨占設備
C.脫機設備
D.塊設備

31.下面關于設備獨立性的論述中正確的是(  )。

A.設備獨立性是指I／O設備具有獨立執行I／O功能的一種特性
B.設備獨立性是指用戶程序獨立于具體使用的物理設備的一種特性
C.設備獨立性是指能獨立實現設備共享的一種特性
D.設備獨立性是指設備驅動程序獨立于具體使用的物理設備的一種特性

32.計算機網絡分為廣域網、城域網和局域網，其劃分的主要依據是(  )。

A.網絡的作用范圍
B.網絡的拓撲結構
C.網絡的通信方式
D.網絡的傳輸介質

33.下列關于集線器說法正確的是(  )。

A.集線器具有路徑選擇功能
B.集線器具有信息過濾功能
C.集線器可以對接收到的信號進行放大
D.集線器具有交換功能

34.ATM技術主要是解決( )。

A.帶寬傳輸問題
B.網絡成本問題
C.帶寬接入問題
D.帶寬交換問題

35.某部門申請到一個C類IP地址，若要分成8個子網，其掩碼應為(  )。

A.255．255．255．255
B.255．255．255．0
C.255．255．255．224
D.255．255．255．192

36.如果互聯的局域網高層分別采用TCP／IP協議與SPX／IPX協議，那么我們可以選擇的多個網絡互聯設備應該是( )。

A.中繼器
B.網橋
C.網卡
D.路由器

37.TCP是一個面向連接的協議，它提供連接的功能是(  )的。

A.全雙工
B.半雙工
C.單工
D.單方向

38.端到端通信作用于( )之間。

A.機器
B.網絡
C.進程
D.設備

39.關于FTP主要應用功能的敘述正確的是(  )。

A.FTP使用戶和遠程主機相連，從而對主機內的各種資源進行各種操作，如文件的讀、寫、執行、修改等
B.FTP的功能類似于Telnet
C.FTP的主要功能在于文件傳輸，但FTP客戶端在一定的范圍內也有執行修改等其他文件的功能
D.FTP使用戶同遠程主機相連，類似于遠程主機的仿真終端用戶，從而應用遠程主機的資源

二、2.綜合應用題

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

0. 設有m個連續單元供一個棧與隊列使用，且棧與隊列的實際占用單元數事先不知道，但是要求在任何時刻它們占用的單元數量不超過m，試寫出上述棧與隊列的插入算法。

1. 序列的“中值記錄”指的是：如果將此序列排序后，它是第n／2個記錄。試寫出一個求中值記錄的算法。

2. 某浮點機字長16位，其浮點數格式為：階碼5位(含1位階符)，采用補碼表示，尾數11位(含1位數符)，采用補碼表示，且尾數為規格化形式。已知X=0．1011000011×2^0.0101，Y=0．0001100000×2^0.1000，試求X+Y．要求寫出詳細的計算過程。假設浮點加減過程中階碼和尾數采用雙符號位，并使用“0舍1入法”進行舍入。

3. 某計算機的CPU主頻為500 MHz，CPI為5(即執行每條指令平均需5個時鐘周期)。假定某外設的數據傳輸率為0．5 MB／s，采用中斷方式與主機進行數據傳送，以32位為傳輸單位，對應的中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間。請回答下列問題，要求給出計算過程。
 (1)在中斷方式下，CPU用于該外設I／O的時間占整個CPU時間的百分比是多少?
 (2)當該外設的數據傳輸率達到5 MB／s時，改用DM@A@方式傳送數據。假設每次DMA傳送大小為5 000 B，且DMA預處理和后處理的總開銷為500個時鐘周期，則CPU用于該外設I／O的時間占整個CPU時間的百分比是多少?(假設DMA與CPU之間沒有訪存沖突)

4. 分時系統里，在條件相同的情況下，通常KLT(內核級線程)比ULT(用戶級線程)得到更多的CPU時間，請簡要解釋之。

5. 舉例說明P、V操作為什么要求設計成原語(即對同一信號量上的操作必須互斥)。P(S)操作：
  S．value--；
  If(S．value＜0)
  {
  Add this process to S．L；
  Block( )；
  }
  V(S)操作
  S．value++；
  If(S．value＜=0)
  {
  Remove a process P from S．L；
  Wakeup(P)；
  }

6. 如下圖所示為一個TCP主機中的擁塞窗口的變化過程，這里最大數據段長度為1 024字節，請回答如下問題：
(1)該TCP協議的初始閥值是多少?為什么?
(2)本次傳輸是否有發生超時?如果有是在哪一次傳輸超時?
(3)在14次傳輸的時候閥值為多少?
(4)在本例中，采用了什么擁塞控制算法?