一、1.單項選擇題

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

0.線性表的靜態鏈表存儲結構與順序存儲結構相比優點是(  )。

A.所有的操作算法實現簡單
B.便于隨機存取
C.便于插入與刪除
D.便于利用零散的存儲器空間

1.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是(  )。

A.棧
B.隊列
C.樹
D.圖

2.用P代表人棧，O代表出棧。棧的初始狀態和最終狀態都為空，則下列棧操作正確的是(  )。

A.POOPOOPP
B.POPOPOOP
C.PPPOOOPP
D.PPPOOPOO

3.按照二叉樹的定義，具有3個結點的二叉樹有( )種。

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

4.根據使用頻率為5個字符的哈夫曼編碼不可能的是(  )。

A.111，110，10，01，00
B.000，001．，010，011，1
C.100，11，10，1，0
D.001，000，01，11，10

5.某高度為k的完全二叉樹中，所含葉子結點的個數最少為(  )。

A.2k
B.k
C.2k-2
D.2k-1

6.下列敘述正確的個數是( )。
　 1)向二叉排序樹中插入一個結點，所需比較的次數可能大于此二叉排序樹的高度。
  2)對B-樹中任一非葉子結點中的某關鍵字K，比K小的最大關鍵字和比K大的最小關鍵字一定都在葉子結點中。
  3)所謂平衡二叉樹是指左、右子樹的高度差的絕對值不大于1的二叉樹。
　 4)刪除二叉排序樹中的一個結點，再重新插入，一定能得到原來的二叉排序樹。

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

7.求最短路徑常用的算法有( )。

A.Prim算法和Kruskal算法
B.深度優先遍歷算法和廣度優先遍歷算法
C.Dijkstra算法和Floyd算法。
D.拓撲排序算法

8.若一組記錄的排序碼序列F={50，80，30，40，70，60)，利用快速排序方法，以第一個記錄為基準，得到一趟快速排序的結果為(  )。

A.30，40，50，60，70，80
B.40，30，50，80，70，60
C.50，30，40，70，60，80
D.40，50，30，70，60，80

9.在下列排序方法中不需要對排序碼進行比較就能進行排序的是(  )。

A.基數排序
B.快速排序
C.直接插入排序
D.堆排序

10.計算機硬件系統中“主機”是指(  )。

A.主機箱及其內部硬件設備
B.運算器和控制器
C.CPU和主存儲器
D.CPU、主存和輸入輸出設備

11.[x]_補=1．x₁x₂x₄)，則當滿足(  )時，x＞-1．／2成立。

A.x₂必為0，x₂～x₄至少有一個為1
B.x₁必為0，x₂～x₄任意
C.x₁必為1，x₂～x₂至少有一個為1
D.x₁必為1，x₂～x₄任意

12.某浮點機字長16位，其中，階碼5位(含1位階符)，采用補碼表示，基數為4；尾數11位(含1位數符)，采用補碼表示，且為規格化形式，則其可以表示的最小正數是(  )。

A.2^-17
B.2^-26
C.2^-34
D.2^-42

13.下列有關存儲器的說法錯誤的是(  )。

A.訪問存儲器的請求是由CPU發出的
B.Cache與主存統一編址，即主存空間的某一部分屬于Cache
C.Cache的功能全由硬件實現
D.Cache—主存層次主要為了解決存儲系統的速度問題

14.一個四體并行的低位交叉編址存儲器，每個存儲體的存取周期為200 ns，總線傳輸周期為50 ns，則連續讀取10個存儲字需時( )。

A.2000 ns
B.600 ns
C.650 ns
D.300 ns

15.下列哪種尋址方式下，操作數在主存儲器(  )。

A.直接尋址
B.寄存器直接尋址
C.立即數尋址
D.以上都不對

16.下列關于RISC機的說法中錯誤的是(  )。

A.指令長度固定，指令格式種類少，尋址方式種類少
B.配備大量通用寄存器
C.強調采用流水線技術進行優化
D.較少使用硬布線邏輯實現

17.下列關于指令周期的說法中正確的是(  )。

A.指令周期即時鐘周期
B.指令周期是指CPU執行一條指令的時間
C.指令周期是指CPU取出一條指令并執行該指令的時間
D.以上說法都不對

18.在單發射、按序流動的普通流水線中，可能出現下列哪種數據相關問題?(  )。

A.寫后讀相關RAW
B.讀后寫相關WAR
C.寫后寫相關WAW
D.以上都有可能

19.某計算機系統中，各個主設備得到總線使用權的機會基本相等，則該系統采用的總線判優控制方式一定不是( )。

A.鏈式查詢方式
B.計數器定時查詢方式
C.獨立請求方式
D.以上選項都不正確

20.計算機的外圍設備是指(  )。

A.主存儲器
B.外存儲器
C.除主機外的其他設備
D.除CPU外的其他設備

21.某字節多路通道的最大數據傳輸率為1 000 B／s，它有5個子通道，則每個子通道的最大數據傳輸率為( )。

A.200 B／s
B.1 000 B／s
C.介于A、B之間
D.以都不對

22.下面關于進程的敘述中，正確的是(  )。

A.進程獲得CPU運行是通過調度得到的
B.優先級是進程調度的重要依據，一旦確定就不能改變
C.在單CPU的系統中，任意時刻都有一個進程處于運行狀態
D.進程申請CPU得不到滿足時，其狀態變為阻塞

23.在請求分頁存儲管理中，若采用FIFO的頁面淘汰算法，當分配的頁面數增加時，缺頁中斷的次數(  )。

A.減少
B.增加
C.無影響
D.可能增加也可能減少

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

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

25.在讀寫文件的操作中，通常使用“塊高速緩存”，以減少訪問磁盤的次數，但為了保證系統的( )，關鍵塊必須盡早寫盤。

A.一致性
B.安全性
C.性能
D.可擴性

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

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

27.設有3個作業，其運行時間分別為2小時、5小時、3小時，假定它們同時到達，并在同一臺處理機上以單道運行方式運行，則平均周轉時間最小的執行順序是(  )。

A.J1，J2，J3
B.J3，J2，J1
C.J2，J1，J3
D.J1，J3，J2

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

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

29.程序員利用系統調用打開I／O設備時，通常使用的設備標識是(  )。

A.邏輯設備名
B.物理設備名
C.主設備號
D.從設備號

30.中斷向量的地址是(  )。

A.子程序入口地址
B.中斷服務例行程序入口地址
C.中斷服務例行程序入口地址的地址
D.例行程序入口地址

31.操作系統采用頁式存儲管理方法，要求(  )。

A.每個進程擁有一張頁表，且進程的頁表駐留在內存中
B.每個進程擁有一張頁表，但只要執行進程的頁表駐留在內存中，其他進程的頁表不必駐留在內存中
C.所有進程共享一張頁表，以節約有限的內存空間，但頁表必須駐留在內存中
D.所有進程共享一張頁表，只有頁表當前使用的頁面必須駐留在內存中，以最大限度地節約有限的內存空間

32.在OSI的層次模型中，(  )是控制對等實體間進行通信的規則的集合。

A.協議
B.服務
C.接口
D.原語

33.在無噪聲情況下，若某通信鏈路的帶寬為3 kHz，采用4個相位，每個相位具有4種振幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是(  )。

A.12 kbps
B.24 kbps
C.48 kbps
D.96 kbps

34.數據鏈路層采用了后退N幀的(GBN)協議，如果發送窗口的大小是32，那么至少需要(  )位的序列號才能保證協議不出錯。

A.4位
B.5位
C.6位
D.7位

35.以太網地址是由(  )個字節組成的。

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

36.TCP使用三次握手協議來建立連接，假設甲乙雙方發送報文的初始序列號分別為X和Y，甲方發送SYN=1，序號=X的報文給乙方，乙方接收報文后發送(  )的報文給甲方，然后甲方發送一個確認報文給乙方便建立了連接。

A.SYN=0，序號=Y；ACK=1，確認序號=X+1
B.SYN=1，序號=Y；ACK=0，確認序號=X+1
C.SYN=1，序號=Y；ACK=1，確認序號=X+1
D.SYN一1，序號=Y；ACK=1，確認序號=X

37.假設一個應用每秒產生60 bytes的數據塊，每個數據塊被封裝在一個TCP報文中，然后再封裝到一個IP數據報中。那么最后每個數據報所含有的應用數據所占的百分比是(  )。

A.20％
B.40％
C.60％
D.80％

38.有一條TCP連接，它的最大報文段長度是2 kB，TCP擁塞窗口為24 kB，這時候發生了超時事件，那么該擁塞窗口變成了(  )。

A.1 kB
B.2 kB
C.5 kB
D.7 kB

39.在DNS的遞歸查詢中，由(  )給客戶端返回地址。

A.最開始連接的服務器
B.最后連接的服務器
C.目的地址所在的服務器
D.不確定

二、2.綜合應用題

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

0. 設一段正文由字符集{A，B，C，D，E，F)中的字母組成，這6個字母在正文中出現的次數分別為{12，18，26，6，4，34)。
 (1)為這6個編碼設計哈夫曼編碼。
 (2)設每個字節由8位二進制位組成，試計算按哈夫曼編碼壓縮存儲這段正文共需多少個字節。
 (3)若這段正文開始部分的二進制編碼序列為：0110001001011010100，請按1的哈夫曼編碼將其譯為正文。

1. 荷蘭國旗問題：設有一個僅紅、白、藍三種顏色的條塊組成的條塊序列，請編寫一個時間復雜度為O(n)的算法，使得這些條塊按紅、白、藍的順序排好，即排成荷蘭國旗圖案。

2. 一個由高速緩沖存儲器Cache與主存儲器組成的二級存儲系統。已知主存容量為1 MB，按字節編址，緩存容量為32 KB，采用組相聯方式進行地址映射與變換，主存與緩存的每一塊為64 B，緩存共分8組。
 (1)寫出主存與緩存的地址格式(標明各字段名稱與位數)。
 (2)假定Cache的存取周期為20μs，命中率為0．95，希望采用Cache后的加速比大于10。那么主存儲器的存取速度應大于多少(訪存時CPU同時訪問Cache和主存，如Cache命中則中斷主存訪問)?

3. 指令系統字長16位，每個地址碼為6位，采用擴展操作碼的方式，試設計14條二地址指令，100條一地址指令，100條零地址指令。
 (1)畫出操作碼的擴展形式。
 (2)下圖為指令譯碼邏輯圖，其中只給出了二地址指令的譯碼邏輯，試補全一地址指令和零地址指令的譯碼邏輯。

 (3)計算操作碼的平均長度。

4. 假定在一個處理機上執行的操作如下：
  作業  估計服務時間片  優先數
  A  10  3
  B  1  1
  C  2  3
  D  1  4
  E  5  2
 這些作業假定按A、B、C、D、E次序先后幾乎同時(時間差相對時間片大小忽略不計)到達。
 (1)給定相應的圖示來說明分別用FCFS、RR(時間片=1)、SJF和非搶占優先調度算法(最小優先數有最高優先權)調度這些作業的情況。
 (2)分別給出采用上述調度算法時每個作業的周轉時間和平均周轉時間。

5. 一個SPOOUNG系統由輸入進程I、用戶進程P、輸出進程O、輸入緩沖區、輸出緩沖區組成。進程I通過輸入緩沖區為進程P輸入數據，進程P的處理結果通過輸出緩沖區交給進程O輸出。進程間數據交換以等長度的數據塊為單位，這些數據塊均存儲在同一個磁盤上，因此，SPOOLING系統的數據塊通信原語保證始終滿足：I+O≤max其中，max為磁盤容量(以該數據塊為單位)，I為磁盤上輸入數據塊總數，O為磁盤上輸出數據總數。該SPOOLING系統運行時：
  (1)只要有輸入數據，進程I終究會將它放入輸入緩沖區；
  (2)只要輸入緩沖區有數據塊，進程P終究會輸入、處理并產生結果數據寫到輸出緩沖區；
  (3)只要輸出緩沖區有數據塊，進程O終究會輸出它。請說明該SPOOLING系統在什么情況下死鎖，請說明如何修正約束條件(1)避免死鎖，同時仍允許輸入數據塊和輸出數據塊存儲在同一個磁盤上。

6. 一個客戶機利用FTP協議從服務器上下載文件，如下圖所示為整個過程中協議交換的過程，請回答如下問題：
  (1)該協議層圖中第四層協議是什么?
  (2)如果FTP客戶端采用了LIST命令來獲得FTP服務器上的文件列表，該列表采用什么端口傳輸?
  (3)如果一個TCP數據包的數據部分長度為5 000字節，那么在IP層需要分片嗎?
  (4)如果需要分片請說明需要分成幾片，每片長度為多少?如果不需要分片，請說明原因。