一、1.單項選擇題

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

0.在一個長度為n(n>1)的帶頭結點的單鏈表h上，設有尾指針r(指向尾結點)，則執行(  )操作與鏈表的長度有關。

A.刪除單鏈表中的第一個元素
B.刪除單鏈表中的最后一個元素
C.在單鏈表第一個元素前插入一個新元素
D.在單鏈表最后一個元素后插入一個新元素

1.若用單鏈表來表示隊列，則應該選用(  )。

A.帶尾指針的非循環鏈表
B.帶尾指針的循環鏈表
C.帶頭指針的非循環鏈表
D.帶頭指針的循環鏈表

2.對于一個滿二叉樹，共有n個結點和m個葉子結點，深度為h，則(  )。

A.n=h+m
B.h+m=2n
C.m=h-1
D.n=2h-1

3.關于哈夫曼樹，下列說法正確的是(  )。

A.在哈夫曼樹中，權值相同的葉子結點都在同一層上
B.在哈夫曼樹中，權值較大的葉子結點一般離根結點較遠
C.哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近
D.在哈夫曼編碼中，當兩個字符出現頻率相同時，其編碼也相同，對于這種情況應作特殊處理

4.每棵樹都能唯一地轉換成相對應的二叉樹，由樹轉換成的二叉樹中，一個結點N的左孩子是它在原樹對應結點的( )。

A.最左孩子
B.最右孩子
C.右鄰兄弟
D.左鄰兄弟

5.已知8個數據元素為(34，76，45，18，26，54，92，65)，按照依次插入結點的方法生成一棵二叉排序樹，則該樹的深度為(  )。

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

6.下列敘述正確的個數是(  )。
(1)m=2的平衡m路查找樹是AVL樹
(2)m=3的平衡m路查找樹是2-3樹
(3)m=2的平衡m路查找樹的葉結點不一定在同一層
(4)m階B-樹的葉結點必須在同一層
(5)m階B-樹是平衡m路查找樹
(6)平衡m路查找樹不一定是B-樹

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

7.下列說法正確的是( )。

A.任何有向網絡(AOV-網)拓撲排序的結果是唯一的
B.有回路的圖不能進行拓撲排序
C.在AOE網中一定只有一條關鍵路徑
D.一個正常的AOE網中只能有一個源點、一小匯點和一條關鍵路徑

8.對任意7個關鍵字進行排序，至少要進行(  )次關鍵字之間的兩兩比較。

A.13
B.14
C.15
D.16

9.一組記錄的關鍵字為{25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序表，用歸并排序方法對該序列進行一趟歸并后的結果是(  )。

A.15，25，35，50，20，40，80，85，36，70
B.15，25，35，50，80，20，85，40，70，36
C.15，25，50，35，80，85，20，36，40，70
D.15，25，35，50，80，20，36，40，70，85

10.完整的計算機系統由(  )組成。

A.運算器和控制器
B.CPU和主存儲器
C.主機和外部設備
D.硬件系統和軟件系統

11.真值0在原碼、反碼和補碼機器數形式下(  )。

A.都有正0、負0兩種形式
B.僅在原碼中有兩種形式，而在反碼、補碼機器數形式下只有一種形式
C.僅在反碼中有兩種形式，而在原碼、補碼機器數形式下只有一種形式
D.僅在補碼中有一種形式，而在反碼、原碼機器數形式下均有兩種形式

12.某定點機字長8位(含1位符號位)，現該機中一個寄存器的內容為43H，則將其算術左移一位、算術右移一位的結果分別為(  )。

A.86H，21H
B.結果出錯，21H
C.結果出錯，A1H
D.未給出機器數形式，無法判斷

13.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判斷溢出等步驟。設浮點數的階碼和尾數均采用補碼表示，且位數分別為5位和7位(均含2位符號位)。若有兩個數X=2⁷×29／32，Y=⁵×5／8，則用浮點加法計算X+Y的最終結果是(  )。

A.00111 1100010
B.00111 0100010
C.01000 0010001
D.發生溢出

14.半導體隨機存儲器的訪問速度與(  )有關。

A.存儲芯片的存取周期
B.存儲芯片的容量大小
C.所訪問存儲單元的位置
D.以上都包括

15.Cache常用的寫回策略有寫直達法和寫回法。當采用寫回法時，一個Cache數據塊在(   )時寫回主存。

A.任何一次寫操作數時
B.第一次寫操作數時
C.數據塊被換出時
D.以上都有可能

16.主存地址寄存器MAR的位數與下列哪個寄存器相同?(  )。

A.主存數據寄存器MDR
B.程序計數器PC
C.指令寄存器IR
D.累加器AC

17.控制存儲器使用EPROM構成的控制器是(  )。

A.靜態微程序控制器
B.動態微程序控制器
C.毫微程序控制器
D.以上都不對

18.下列關于PCI總線的說法中錯誤的是(  )。

A.PCI總線采用集中式總線判優控制方式
B.PCI總線是一種16位的并行總線
C.PCI總線具有自動配置能力
D.PCI總線在PC機中得到了廣泛的使用

19.某計算機有8個主設備競爭總線使用權，使用鏈式請求方式進行總線判優控制，則該機為實現總線判優控制需要的控制線數為(  )。

A.3
B.5
C.16
D.無法確定

20.下列說法中錯誤的是(  )。

A.統一編址方式即把I／O端口當作主存儲器的單元來分配地址
B.統一編址方式下不需要專門的I／O指令
C.統一編址方式下指令系統的實現比單獨編址方式復雜
D.采用統一編址方式會減少主存的編址空間

21.活動頭磁盤的尋道時間是指(  )。

A.最大尋道時間
B.最小尋道時間
C.A、B之和
D.A、B的平均值

22.下列選擇中，(  )不是操作系統關心的主要問題。

A.管理計算機裸機
B.設計、提供用戶程序與計算機硬件資源的接口
C.管理計算機系統資源
D.高級程序設計語言的編譯器

23.采用(  )不會產生內部碎片。

A.分頁式存儲管理
B.分段式存儲管理
C.固定分區式存儲管理
D.段頁式存儲管理

24.在操作系統中，要對并發進程進行同步的原因是(  )。

A.進程必須在有限的時間內完成
B.進程具有動態性
C.并發進程訪問共享資源
D.進程具有結構性

25.(  )不是分段式虛擬存儲管理優于分頁式虛擬存儲管理的方面。

A.沒有內零頭
B.便于處理在進程執行過程中堆棧尺寸的增長問題
C.便于共享內存中數據
D.只需將進程的一部分調入內存，進程即可運行

26.在下面四段描述中(  )是錯誤的。

A.若進程A和進程B在臨界區上互斥，那么當進程A處于該臨界區時，它不能被進程B打斷
B.虛擬存儲管理中采用對換策略后，用戶進程可使用的存儲空間似乎增加了
C.虛擬存儲管理中的抖動現象是指頁面置換時用于換頁的時間遠多于執行程序的時間
D.進程可以由程序、數據和進程控制塊(PCB)描述

27.存放在磁盤上的文件( )。

A.既可隨機訪問，又可順序訪問
B.只能隨機訪問
C.只能順序訪問
D.必須通過操作系統訪問

28.文件系統中，文件訪問控制信息存儲的合理位置是(  )。

A.文件控制塊
B.文件分配表
C.用戶口令表
D.系統注冊表

29.在操作系統中，P，V操作是一種(  )。

A.機器指令
B.系統調用命令
C.作業控制命令
D.低級進程通信原語

30.(  )是操作系統必須提供的功能。

A.GUI(圖形用戶界面)
B.為進程提供系統調用命令
C.處理中斷
D.編譯源程序

31.磁盤和磁帶是兩種存儲介質，他們的特點是(  )。

A.二者都是順序執行的
B.二者都是隨機存取的
C.磁盤是順序存取的，磁帶是隨機存取的
D.磁帶是順序存取的，磁盤是隨機存取的

32.網橋是在以下(  )層上實現不同網絡互聯的設備。

A.物理層
B.數據鏈路層
C.網絡層
D.傳輸層

33.一種數據編碼的海明距是7，那么使用這種編碼最多可以糾正(  )個錯誤。

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

34.在一個HDLC幀的數據中，如果出現了0001 1111 1011這樣的流，請問發送到信道上它將會變成(  )。

A.0001 1111 1011 0
B.0001 1111 1101 1
C.0001 1111 0101 1
D.0000 1111 1101 1

35.以太網交換機進行轉發決策時使用的PDU地址是(  )。

A.目的物理地址
B.目的IP地址
C.源物理地址
D.源IP地址

36.
請問當目的地址為138．146．63．127的分組將會被發給(  )。

A.接口0
B.接口1
C.接口2
D.接口0和接口1

37.假設一個連接的最大數據段長度為2 KB，一個TCP的閥值為64 KB，如果這時候傳輸發生了超時，那么新的閥值為(  )。

A.32 KB
B.63 KB
C.128 KB
D.2 KB

38.如果在TCP連接中有一方發送了FIN分組，并且收到了回復，那么它將(  )。

A.不可以發送數據，也不可以接收數據
B.可以發送數據，不可以接收數據
C.不可以發送數據，可以接收數據
D.連接馬上斷開

39.下列的應用層協議中，(  )是采用UDP傳輸的。

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

二、2.綜合應用題

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

0. 試編寫一個非遞歸算法，實現求以二叉鏈表存儲的二叉樹中q結點的祖先。

1. 設計一個算法求圖的中心點。設v是有向圖G的一個頂點，把v的偏心度定義為：MAX{從w到v的最短距離｜w屬于V(G))如果v是有向圖G中具有的最小偏心度的頂點，則稱頂點v是G的中心點。

2. 在一個8級中斷的系統中，硬件中斷響應從高到低的優先順序是1→2→3→4→5→6→7→8，通過中斷屏蔽技術，將中斷處理優先順序設置為1→3→5→7→2→4→6→8，如果CPU在執行一個應用程序時有5、6、7、8級的四個中斷同時到達，CPU在按優先順序處理到第3個中斷請求的過程中又有一個3級中斷請求到達CPU，試畫出CPU響應這些中斷的順序示意圖。

3. 某計算機有8個主設備需要競爭總線的使用權，其設備號為0～7。現欲設計其判優控制方法，試回答下述問題。
  (1)集中式總線判優控制與分布式總線判優控制的區別是什么?
  (2)若采用集中式判優控制，則在鏈式查詢、計數器定時查詢和獨立請求三種方式下，該計算機為實現判優控制所需的控制線種類及數量分別為多少?

4. 三個進程P1、P2、P3互斥使用一個包含N(N＞O)個單元的緩沖區。P1每次用produce()生成一個正整數并用put()送入緩沖區某一空單元中；P2每次用getodd()從該緩沖區中取出一個奇數并用countodd()統計奇數個數；P3每次用geteven()從該緩沖區中取出一個偶數并用counteven()統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。

5. 在請求頁式系統中，一程序的頁面走向(訪問串或引用串)為2，3，4，5，2，3，6，2，3，4，5，6，設分配給該程序的存儲塊數為m。試分別計算m=3和m=4時，FIFO和LRU兩種替換算法的缺頁(頁故障)數，并給出：結果說明了什么?

6. 如下圖所示為一個網絡連接的示意圖，主機1到主機2采用了SLIP網絡連接，SLIP網絡可以傳輸的最大數據段是296字節，主機2和主機3使用了以太網連接。
請問：
(1)為了使IP不分片，主機1可以在TCP包中承載多少數據?
(2)主機3可以在TCP包中承載多少數據?
(3)先在主機1和主機3建立起了一條CP連接，請問這條TCP連接的mss值是多少?