一、1.單項選擇題

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

0. 下列有關數據存儲結構的敘述中，正確的是(  )。

A．順序存儲方式只能用于存儲線性結構
B．順序存儲方式的優點是占用存儲空間小，插入、刪除等操作效率高
C．鏈表的每個結點中都恰好含有一個指針
D．Hash存儲的基本思想是由關鍵詞的值決定數據的存儲地址

1. 若用一個大小為6的一維數組來實現循環隊列，且當前front和rear的值分別為3，0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為(  )。

A．5，1
B．4，2
C．2，4
D．1．5

2.

A．LRN
B．NRL
C．RLN
D．RNL

3. 完全二叉樹高度為h，則最左邊的葉子結點序號為(  )。

A．2h^h-1+1
B．2h^h-1
C．2^h+1-1
D．2^h+1

4. 下列的敘述不正確的個數是( )。
 (1)9階B-樹，除根以外的任一結點的關鍵字個數不少于4
 (2)理想情況下，在散列表中查找一個元素的時間復雜度為O(1)
 (3)在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰
 (4)在索引順序表的查找中，對索引表既可以采用順序查找方法，也可采用二分查找方法

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

5. 關于B-樹，下列說法不正確的是(  )。

A．B-樹是一種查找樹
B．所有的葉結點具有相同的高度
C．2-3樹中，所有非葉子結點有1或者3個孩子結點
D．通常情況下，B-樹不是二叉樹

6. 在AOE網絡中關鍵路徑敘述正確的是(  )。

A．從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間
B．從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間
C．從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間
D．從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間

7. 已知關鍵序列5，‘8，12，19，28，20，15，22是小根堆(最小堆)，插入關鍵字3，調整后得到的小根堆是( )。

A．3，5，12，8，28，20，15，22，19
B．3，5，12，19，20，15，22，8，28
C．3，8，12，5，20，15，22，28，19
D．3，12，5，8，28，20，15，22，19

8. 設用數組A[1，n]作為兩個棧S1、S2的共用存儲空間，對任一個棧，只有當數組A[1，n]全滿時才不作人棧操作，則分配這兩個?？臻g的最佳方案是(  )。

A．S1的棧底位置設為1，S2的棧底位置設為n
B．S1的棧底位置設為n／2，S2的棧底位置設為n／2+1
C．S1的棧底位置設為1，S2的棧底位置設為n／2
D．S1的棧底位置設為n／2，S2的棧底位置設為1

9. 在一棵高度為h的理想平衡二叉樹中，最少含有(  )個結點，最多含有(  )個結點。

A．2^h 2^h-1
B．2^h-1 2^h
C．2^h+1 2^h-1
D．2^h-1 2^h-1

10. 一個十進制數真值為-100，按補碼形式存放在一個16位寄存器中，該寄存器的內容用十六進制表示為( )。

A．FF9CH
B．009CH
C．9C00H
D．0064H

11. 某浮點機字長8位，尾數和階碼都采用補碼形式，且運算過程中數符和階符都采用雙符號位，基數為2。則浮點加減運算過程中，當出現下列哪種情況時，需要左規?(  )

A．尾數相加后，數符為“01”
B．尾數相加后，數符為“10”
C．尾數相加結果為“00．1xxxxxx”
D．尾數相加結果為“11．1xxxxxx”

12. 補碼除法中，根據( )上商0。

A．余數為負
B．余數的符號與被除數的符號相同
C．余數的符號與被除數的符號不同
D．余數的符號與除數的符號不同

13. 以下說法中錯誤的是(  )。

A．與DRAM相比，SRAM的集成度低，存取速度快
B．PC機的主存儲器常由DRAM構成
C．RAM需要刷新，且斷電后信息會丟失
D．ROM是一種非易失性存儲器，斷電后仍可保持記憶

14. 某DRAM芯片內部存儲元排列成1 024．×1 024的矩陣，且已知其存取周期為0．1μs，最大刷新間隔為2 ms。當采用異步刷新方式時，死時間(  )。

A．=2 ms
B．≈0．1 ms
C．=0．2μs
D．=0．1μs

15. 某計算機的指令系統中有“先基址后間址”的尋址方式，基址寄存器為BR，形式地址為A，則有效地址為( )。

A．(BR)+A
B．(BR+A)
C．((BR)+A)
D．((BR))+A

16. 在基址尋址方式中，若基址寄存器BR的內容為2D3C₁₆形式地址A的內容為53₁₆則有效地址EA為(  )。

A．53₁₆
B．2D3C₁₆
C．2D8F₁₆
D．803C₁₆

17. 某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間(忽略各功能段之間的緩存時間)分別是90 ns、80 ns、70 ns和60 ns，則該計算機的CPU時鐘周期至少是(  )。

A．90 ns
B．80 ns
C．70 ns
D．60 ns

18. 系統總線中地址線的功能是用于選擇(  )。

A．主存單元
B．I／O端口
C．磁盤數據塊
D．A或B

19. 假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10 MHz，則總線帶寬是(  )。

A．10 MB／s
B．20 MB／s
C．40 MB／s
D．80 MB／s

20. 微型計算機中，主機和高速磁盤交換數據適合采用(  )方式。

A．程序查詢控制
B．程序中斷控制
C．直接存儲器存取(DMA)
D．通道控制

21. 某圖像顯示器的分辨率為1 024×768，共可顯示256種灰度，則顯示存儲器的容量為(  )。

A．256 KB
B．768KB
C．1 MB
D．2 MB

22. 多道程序設計是指( )。

A．在實時系統中并發運行多個程序
B．在分布式系統中同一時刻運行多個程序
C．在一臺處理機上同一時刻運行多個程序
D．在一臺處理機上并發運行多個程序

23. 下列算法中用于磁盤移臂調度的是(  )。

A．時間片輪轉法
B．LRU算法
C．最短尋找時間優先法
D．優先級高者優先法

24. 當(  )時，進程從執行狀態轉變為就緒狀態。

A．進程被調度程序選中
B．時間片到
C．等待某一事件
D．等待的事件發生

25. 在下列文件中，不便于文件增、刪操作的是(  )。

A．索引文件
B．連續文件
C．Hash文件
D．串聯文件

26. 設有五個進程共享一個互斥段，如果最多允許兩個進程同時進入互斥段，則所采用的互斥信號量初值應該是( )。

A．5
B．2
C．1
D．0

27. 銀行家算法在解決死鎖問題中是用于(  )的。

A．預防死鎖
B．避免死鎖
C．檢測死鎖
D．解除死鎖

28. 通道又稱I／O處理機，它用于實現(  )之間的信息傳輸。

A．主存和外設
B．CPU與外設
C．主存與Cache
D．CPU與外存

29. 執行一次磁盤輸入輸出操作所花費的時間包括(  )。

A．尋道時間、延遲時間、傳送時間和等待時間
B．尋道時間、等待時間、傳送時間
C．等待時間、尋道時間、延遲時間、讀寫時間
D．尋道時間、延遲時間、傳送時間

30.

A．5F6AH
B．AF6AH
C．BF6AH
D．10F6AH

31. 從下面關于虛擬設備的論述中，選擇一條正確的論述(  )。

A．虛擬設備是指允許用戶使用比系統中具有的物理設備更多的設備
B．虛擬設備是指允許用戶以標準化方式來使用物理設備
C．虛擬設備是把一個物理設備變換成多個對應的邏輯設備
D．虛擬設備是指允許用戶程序不必全部裝入內存便可使用系統中的設備

32. 在OSI參考模型中，自下而上第一個提供端到端服務的層次是(  )。

A．數據鏈路層
B．傳輸層
C．會話層
D．應用層

33. 用PCM寸語音進行數字量化，如果將聲音分為128個量化級，采樣頻率為8 000次／秒，那么一路話音需要的數據傳輸率為(  )。

A．56 Kbps
B．64 Kbps
C．128 Kbps
D．1 024 Kbps

34. 假設有一個信道的帶寬是3 000 Hz，其信噪比為20 dB，那么這個信道可以獲得的理論最大傳輸速率是(  )。

A．1 Kbps
B．32 Kbps
C．20 Kbps
D．64 Kbps

35. 一個使用CSMA／CA的網絡上，計算機A的幀際間隔是2時槽，計算機B的幀際間隔是6時槽，如果計算機C使用(  )幀際間隔可以獲得最高優先級。

A．8時槽
B．5時槽
C．3時槽
D．1時槽

36. 長度為10 km、數據傳輸率為10 Mbps的CSMA／CS以太網，信號傳播速度為200 m／μs。那么該網絡的最小幀長為(  )。

A．20 bit
B．200 bit
C．100 bit
D．1 000 bit

37. 以下動態路由算法中，使用距離一矢量路由算法的是(  )。

A．RIP協議
B．OSPF協議
C．BGP協議
D．ICMP協議

38. 物理層、數據鏈路層和網絡層的PDU分別是(  )。

A．報文、幀、比特
B．報文、分組、比特
C．比特、分組、幀
D．比特、幀、分組

二、2.綜合應用題

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

0. 已知下列各種初始狀態(長度為n)元素，試問當利用直接插入法進行排序時，至少需要進行多少次比較(要求排序后的文件按關鍵字從小到大順序排列)?
 (1)關鍵字自小到大有序(key1＜key2＜…＜keyn)。
 (2)關鍵字自大到小逆序(key1＞key2＞…＞keyn)。
 (3)奇數關鍵字順序有序，偶數關鍵字順序有序(key1＜key3…，key2＜key4＜…)。
 (4)前半部分元素按關鍵字順序有序，后半部分元素按關鍵字順序逆序(key1＜key2＜…＜keym，keym+1＞keym+2＞…)keyn，m為中間位置)。

1. 請利用隊列的基本操作寫出判定一棵二叉樹是否為完全二叉樹的算法。要求以二叉鏈表作為二叉樹的存儲結構。函數原型為：int IsFull_Bitree(Bitree T)。

2. 計算機系統中存儲器為何采用分級結構?

3. 指令字長為12位，每個地址碼為3位，采用擴展操作碼的方式，設計4條三地址指令、16條二地址指令、64條一地址指令和16條零地址指令。
  (1)給出一種操作碼的擴展方案。
  (2)計算該方案操作碼的平均長度。

4. 在銀行家算法中，若出現下面的資源分配情況：
 
請問：
 (1)狀態是否安全?
 (2)若進程P2提出請求Request(1，2，2，2)后，系統能否將資源分配給它?

5. 三類線程search、insert、delete共享(訪問)單鏈表，利用P、V原語操作實現這三類線程。限定如下：
 (1)search可以與同類線程同時執行；
 (2)insert類線程之間互斥，但是可以與任意多search同時執行；
 (3)delete不但同類之間互斥，而且與其他類線程互斥。

6. 將要相互通信雙方怎樣進行建立TCP連接?在TCP報文段的首部中只有端口號而沒有IP地址，當TCP將其報文段交給IP層時，IP協議怎樣知道目的IP地址呢?為什么把IP地址又稱為“虛擬地址”，把TCP連接說成是“虛連接”?假設在建立連接時使用2次握手而非3次握手的方案，即：不再需要第3條報文，這時會發生什么情況?舉例說明。