一、1.單項選擇題

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

0.若某線性表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則下面最節省運算時間的存儲方式是(     )。

A.單鏈表
B.帶有頭指針的單循環鏈表
C.雙鏈表
D.帶有尾指針的單循環鏈表

1.循環隊列用數組A[0．．m～1]存放其元素值，已知其頭尾指針分別為front和rear，則當前元素個數為(     )。

A.(rear-front+m)MOD m
B.rear-front+1
C.rear-front+1
D.rear-front

2.二維數組A的每個元素是由6個字符組成的串，其行下標i=0，1……．，8，列下標j=1，2……，10。設每個字符占一個字節。若A按行先存儲，元素A[8，5]的起始地址與當A按列先存儲時起始地址相同的元素是(     )。

A.A[8，5]
B.A[3，1 0]
C.A[5，8]
D.A[0，9]

3.已知某二叉樹的中序、層序序列為DBAFCE、FDEBCA，則該二叉樹的后序序列為(     )。

A.BCDEAF
B.ABDCEF
C.DBACEF
D.DABECF

4.在平衡二叉樹中，下面敘述正確的是(     )。

A.任意結點的左、右子樹結點數目相同
B.任意結點的左、右子樹高度相同
C.任意結點的左、右子樹高度之差的絕對值不大于1
D.不存在度為1的結點

5.在二叉樹的順序存儲中，每個結點的存儲位置與其父結點、左右子樹結點的位置都存在一個簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有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)

6.二叉樹若用順序方法存儲，則下列4種算法中運算時間復雜度最小的是(     )。

A.先序遍歷二叉樹
B.判斷兩個指定位置的結點是否在同一層上
C.層次遍歷二叉樹
D.根據結點的值查找其存儲位置

7.判斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用的是(     )。

A.求關鍵路徑的方法
B.求最短路徑的迪杰斯特拉方法
C.深度優先遍歷算法
D.廣度優先遍歷算法

8.有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，99}，當折半查找值為82的結點時，查找成功的比較次數是(     )。

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

9.下面關于B-樹和B+樹的敘述中，不正確的是(     )。

A.B-樹和B+樹都是平衡的多分樹
B.B-樹和B+樹都可用于文件的索引結構
C.B-樹和B+樹都能有效地支持隨機檢索
D.B-樹和B+樹都能有效地支持順序檢索

10.最好情況下的算法時間復雜度為O(n)的是(     )。

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

11.對匯編語言程序員來說，以下部件中不透明的是(     )。
  I．指令緩沖器；  Ⅱ．移位器；  Ⅲ．通用寄存器；
  Ⅳ．中斷字寄存器； V．乘法器；  Ⅵ．先行進位鏈；

A.I、Ⅱ和Ⅲ
B.Ⅳ、V和Ⅵ
C.Ⅲ和Ⅳ
D.I、Ⅱ、V、Ⅵ

12.已知定點小數x的補碼為1．x₁x₂x₃，且x≤一0．75，則必有(     )。

A.x₁=1，x₂=0，x₃=1
B.x₁=1
C.x₁=0，且x₂，x₃不全為1
D.x₁=0，x₂=0，x₃=0

13.已知X=一0．875×2¹，Y=0．625×2²，設浮點數格式為階符1位，階碼2位，數符1位，尾數3位，通過補碼求出Z=X--Y的二進制浮點數規格化結果是(     )。

A.1011011
B.0111011
C.1001011
D.以上都不是

14.地址總線為A15(?葛位)-A0(低位)，若用1 K×4的存儲芯片組成4K字節存儲器，并且以地址總線的高位做片選，則加在各存儲芯片上的地址線是(     )。

A.A15-A0
B.A11-A0
C.A9～A0
D.A8-A0

15.設機器字長為32位，一個容量為16MB的存儲器，CPU按半字尋址，其可尋址的單元數是(     )。

A.2²⁴
B.2²³
C.2²²
D.2²¹

16.8086的堆棧采取向下生長的方式，在壓入時的操作是(     )。

A.SP先減，再壓入數據
B.先壓入數據，SP再減
C.SP先加，再壓入數據
D.先壓入數據，SP再加

17.若某條指令的操作數的地址就包含在指令中，則這條指令的尋址方式是(     )。

A.直接尋址
B.立即尋址
C.寄存器尋址
D.間接尋址

18.以下敘述中，不符合RISC指令系統特點的是(     )。

A.指令長度固定，指令種類少
B.尋址方式種類豐富，指令功能盡量增強
C.設置大量通用寄存器，訪問存儲器指令簡單
D.選取使用頻率較高的一些簡單指令

19.某數在計算機中用8421碼表示為011110001001，其真值是(     )。

A.789
B.789H
C.1929
D.11110001001B

20.傳輸一幅分辨率為640×480，6．5萬色的照片(圖像)，假設采用數據傳輸速度為56kb／s，大約需要的時間是(     )。

A.34．82s
B.42．86s
C.85．71 s
D.87．77s

21.對輸入輸出系統產生決定性影響的基本要求是(     )。
  I．異步性；Ⅱ．同步性；Ⅲ．分時性；
  Ⅳ．實時性；V．設備相關性；Ⅵ．設備無關性；

A.Ⅱ，Ⅲ，V
B. I，Ⅳ，Ⅵ
C.Ⅱ，Ⅳ，Ⅵ
D. I，Ⅲ，V

22.操作系統可以為用戶提供多種功能，而操作系統必須提供但是又不作為資源管理的是(     )。

A.編譯程序
B.內外存分配
C.處理中斷
D.使用處理機

23.進程處于下列哪個等待狀態時，它是處于非阻塞狀態(     )。

A.等待從鍵盤輸入數據
B.等待協作進程的一個信號
C.等待操作系統分配CPU時間
D.等待網絡數據進入內存

24.有兩個并發進程如下面所示，對于這段程序的運行，正確的說法是(     )。
  PARBEGIN
  var x：integer；
  process P1         process P2
  var y，z：integer；     var t，u：integer；
  BEGIN            BEGIN
    x：=1；          x：=0；
    y：=0；          t：=0；
    if x>=1 then y：=y+1；  if x<=1 then t：=t+2；
    z：=y；          u：=t；
   END            END
   PAREND

A.程序能正確運行，結果唯一
B.程序不能正確運行，可能有二種結果
C.程序不能正確運行，結果不確定
D.程序不能正確運行，可能會死鎖

25.段頁式存儲管理中，地址映射表是(     )。

A.每個進程有一張段表，兩張頁表
B.每個進程的每個段有一張段表，一張頁表
C.每個進程一張段表，每個段一張頁表
D.每個進程一張頁表，每個段一張段表

26.適合多道程序運行的存儲管理方法中，存儲保護主要是(     )。

A.防止一個進程占用一個分區
B.防止非法訪問磁盤文件
C.防止非法訪問臨界區
D.防止各道進程相互干擾

27.采用段式存儲管理時，一個程序分段的時機是(     )。

A.程序編譯時
B.用戶編程時
C.程序裝入時
D.程序執行時

28.在磁盤中讀取數據的下列時間中，影響最大的是(     )。

A.處理時間
B.延遲時間
C.傳送時間
D.尋道時間

29.若在磁盤格式化時把每個盤面分成大小相等的10個扇區，磁盤的轉速為20毫秒／圈，則讀取一個扇區所需要花費的時間是(     )。

A.2毫秒
B.1毫秒
C.20毫秒
D.10毫秒

30.某文件占100個磁盤塊，現要把該文件磁盤塊逐個讀入主存緩沖區，并送用戶區進行分析。假設一個緩沖區與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區的時間為200bμs將緩沖區的數據傳送到用戶區的時間是100μs，CPU對一塊數據進行分析的時間為100μs。在單緩沖區和雙緩沖區結構下，讀入并分析完該文件的時間分別是(     )。

A.30000μs、20000μs
B.30100μs、20200μs
C.30100μs、30100μs
D.20200μs、20200μs

31.有關虛擬設備的論述中，正確的是(     )。

A.虛擬設備是增加了比系統中現有設備更多的物理設備
B.虛擬設備是指將獨占設備轉變成了共享設備
C.虛擬設備是把一個物理設備變換成多個對應的邏輯設備
D.虛擬設備是指允許用戶程序不必全部裝入多個對應的邏輯設備

32.TCP／IP網絡協議主要在OSI模型中進行操作的層次是(     )。

A.數據鏈路層、傳輸層、物理層
B.物理層、傳輸層、會話層
C.網絡層、傳輸層、應用層
D.網絡層、傳輸層、會話層

33.設待傳送數據總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源節點到目的節點之間的鏈路數為h，每個鏈路上的延遲時間為D秒，數據傳輸率為B bps，虛電路建立連接的時間都為S秒，在分組交換方式下每個中間節點產生d位的延遲時間，則傳送所有數據，虛電路分組交換所需時間是([X]表示對X向上取整)(     )。

A.S+(hd／B+P／B)×[L／(P-H)]秒
B.S+(hD+P／B)×[L／(P-H)]秒
C.S+[(h-1)D+P／B]×[L／(P—H)]秒
D.s+[(h一1)d／B+hD+P／B]×[L／(P—H)]秒

34.在IP數據報報頭中有兩個有關長度的字段，一個為報頭長度(IHL)字段，一個為總長度 (total length)字段，下面說法正確的是(     )。

A.報頭長度字段和總長度字段都以8比特為計數單位
B.報頭長度字段以8比特為計數單位，總長度字段以32比特為計數單位
C.報頭長度字段以32比特為計數單位，總長度字段以8比特為計數單位
D.報頭長度字段和總長度字段都以32比特為計數單位

35.如果一臺主機的IP地址為192．168．0．10，子網掩碼為255．255．255．224，那么主機所在網絡的網絡號占IP地址的位數是(     )。

A.24
B.25
C.27
D.28

36.在IP分組的傳輸過程中(不包括NAT情況)，以下IP分組頭中的域保持不變的是 (     )。
  I．總長度Ⅱ．頭檢驗和Ⅲ．生存時間Ⅳ．源IP地址

A.I、Ⅱ、Ⅳ
B.只有Ⅳ
C.I、Ⅲ、Ⅳ
D.Ⅱ、Ⅳ

37.某PC不能接入Internet，此時采用抓包工具捕獲的以太網接口發出的信息如下：
  
   那么該PC不能接入Internet的原因可能是(     )。

A.DNS解析錯誤
B.TCP／IP協議安裝錯誤
C.不能正常連接到網關
D.DHCP服務器工作不正常

38.關于TCP和UDP端口，下列說法正確的是(     )。

A.TOP和UDP分別擁有自己的端口號，它們互不干擾，可以共存于同一臺主機
B.TCP和UDP分別擁有自己的端口號，但它們不能共享于同一臺主機
C.TCP和UDP的端口沒有本質區別，它們可以共存于同一臺主機
D.TCP和UDP的端口沒有本質區別，它們互不干擾，不能共存于同一臺主機

39.下列Internet應用中，基于C／S計算模式的是(     )。

A.FTP
B.BT
C.MSN
D.Skype

二、2.綜合應用題

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

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

1. 設計一個算法，求無向圖G(采用鄰接表存儲)的連通分量個數。

2. 問：下列IEEE單精度浮點數所表示的十進制數分別是多少?
  (1)1011 1101 0100 0000 0000 000 0000 0000
  (2)0101 0101 0110 0000 0000 0000 0000 0000
  (3)1100 0001 1111 0000 0000 0000 0000 0000
  (4)0011 1010 1000 0000 0000 0000 0000 0000
  (5)0000 0000 0000 0000 0000 0000 0000 0000

3. 某機主存容量為1MB，兩路組相連方式(每組僅有兩塊)的Cache容量為64KB，每個數據塊為256字節。CPU要順序訪問的地址為20124H、58100H、60140H和60138H等4個主存字節單元中的數。已知訪問開始前第2組(組號為1)的地址陣列內容如下圖所示，Cache采用LRU替換策略。
  
  說明Cache的結構(即分多少組、組內分多少塊)，給出主存及Cache的地址格式。上述4個數能否直接從Cache中讀取，若能，請給出實際訪問的Cache地址。第4個數訪問結束時，上圖的內容如何變化。

4. 假設在一臺單處理機上執行如下表所示的進程，且假定這些進程在時刻0以1，2，3，4，5的順序創建。時間單位為時間片，優先級以數值大者為優。
  
  (1)請說明分別使用FCFS、RR(時間片=1)、SPF以及非搶奪式優先級調度算法時，這些進程的執行情況。
  (2)爭對上述每種調度算法，給出平均周轉時間和平均帶權周轉時間。

5. 大部分文件系統以硬盤作為文件存儲器。某一個文件系統中，其磁盤物理塊的大小為512B，有一個文件，包含了590個邏輯記錄，每個記錄占255B；其中，為檢索方便，采用成組法存儲，在每個物理塊上只存放2個記錄。，文件A在該文件目錄中的位置如下圖所示。
  
  此樹形文件目錄結構由根目錄結點和作為文件中間的目錄結點以及作為信息文件的葉結點組成，每個目錄項占127B，每個物理塊存放4個目錄項。根目錄的內容常駐內存。
  (1)若文件采用隱式鏈接文件結構，設每塊的連接字占4B，存放在每個物理塊的尾部。如果要將文件A讀入內存，至少要讀取幾次硬盤?為什么?
  (2)若文件采用連續文件結構，如果要將文件A的邏輯記錄號為480的記錄讀入內存，至少要讀取幾次硬盤?為什么?

6. 設有A，B，C，D 4臺主機都處在同一個物理網絡中，A主機的IP地址是192．155．28．11 2，B主機的IP地址是1 92．1 55．28．120，C主機的IP地址是1 92．1 55．28．135，D主機的IP地址是192．155．28．202。共同的子網掩碼是255．255．2 55．224，請回答如下
  問題：
  (1)A，B，C，D 4臺主機之間哪些可以直接通信?哪些需要通過設置網關(或路由器)才能通信?請畫出網絡連接示意圖，并注明各個主機的子網地址和主機地址。
  (2)若要加入第5臺主機E，使它能與D直接通信，其IP地址的設定范圍應是多少?
  (3)不改變A主機的物理位置，將其IP改為1 92．155．28．168，試問它的直接廣播地址和本地廣播地址各是多少?若使用本地廣播地址發送信息，請問哪些主機能夠收到?
  (4)若要使主機A，B，C，D在這個網上都能夠直接通信，可采取什么辦法?