一、1.單項選擇題

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

0.在一個雙向鏈表中，在*p結點之后插入結點*q的操作是(     )。

A.q->prior=p；p->next=q；p->next一>prior=q；q->next=p->next；
B.q->next=p->next；p->next->prior=q；p->next=q；q->prior=p；
C.p->next=q；q->prior=p；q->next=p->next；p->next->prior=q；
D.p->next->prior=q；q->next=p->next；q->prior=p；p->next=q；

1.設線性表中有2n個元素，以下操作中，在單鏈表上實現要比在順序表上實現效率更高的是 (     )。

A.刪除指定元素
B.在最后一個元素的后面插入一個新元素
C.順序輸出前k個元素
D.交換第i個元素和2n—i一1個元素的值(i=0，1…．，n一1)

2.設數組S[n]作為兩個棧S₁和S₂的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是(     )。

A．S₁的棧底位置為O，S₂的棧底位置為n一1
B．S₁的棧底位置為O，S₂的棧底位置為n／2
C．S₁的棧底位置為O，S₂的棧底位置為n
D．S₁的棧底位置為0，S₂的棧底位置為1

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

A.1和5
B.2和4
C.4和2
D.5和1

4.利用逐點插入建立序列(50，72，43，85，75，20，35，45，65，30)對應的二叉排序樹以后，要查找元素30要進行元素間的比較次數是(     )。

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

5.將有關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度是(     )。

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

6.在一個具有n(n>0)個頂點的連通無向圖中，至少需要的邊數是(     )。

A.n
B.n+1
C.n一1
D.n／2

7.已知一個線性表(38，25，74，63，52，48)，假定采用散列函數h(key)=key％7計算散列地址，并散列存儲在散列表A[0．．6]中，若采用線性探測方法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為(     )。

A.1．5
B.1．7
C.2
D.2.3

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

A.37／12
B.62／13
C.39／12
D.49／13

9.下列排序算法中不能保證每趟排序至少能將一個元素放到其最終的位置上的是(     )。

A.快速排序
B.希爾排序
C.堆排序
D.起泡排序

10.若要求盡可能快地對序列進行穩定的排序，則應選的是(     )。

A.快速排序
B.歸并排序
C.起泡排序
D.堆排序

11.計算機系統的層次結構，下列五個級別機器由下到上的順序是(     )。
  I．機器語言機器； Ⅱ．匯編語言機器；  Ⅲ．高級語言機器；
  Ⅳ．微程序控制機器 V．操作系統機器；

A.I→Ⅱ→Ⅲ→Ⅳ→V
B.Ⅳ→I→V→Ⅱ→Ⅲ
C.Ⅲ→Ⅱ→V→I→Ⅳ
D.V→Ⅳ→Ⅲ→Ⅱ→I

12.已知定點整數x的補碼為1 x₃x₂x₁x₀，且x>-8，則必是(     )。

A.x₃=1，x₂～x₀至少有一個1
B.x₃=0，x₂~x₀至少有一個1
C.x₃=1，x₂～x₀任意
D.x₃=0，x₂～x₀任意

13.在規格化浮點運算中，若某浮點數為2⁵×1．10101，其中尾數為補碼表示，則該數是(     )。

A.不需規格化
B.需右移規格化
C.需將尾數左移一位規格化
D.需將尾數左移兩位規格化

14.漢字“啊”的十進制區位碼為“16-01”，它的十六進制機內碼是(     )。

A.1601H
B.9081H
C.BOA1H
D.B081H

15.在一個按字節編址的計算機中，若數據在存儲器中以小端方案存放。假定int型變量i的地址為08000000H，i的機器數為01234567 H，地址：08000000H單元的內容是(     )。

A.01 H
B.23 H
C.45 H
D.67 H

16.在CPU的狀態寄存器中，若符號標志為“1”，表示運算結果是(     )。

A.正
B.負
C.零
D.不一定

17.在微程序控制器設計中，假設微命令采用最短編碼法，需產生N種微操作。則微命令控制字段要設置的位數是(     )。
  

A.A
B.B
C.C
D.D

18.下列是有關馮.諾依曼結構計算機中指令和數據存放位置的敘述，其中正確的是(     )。

A.指令存放在內存中，數據存放在外存中
B.指令和數據任何時候都存放在內存中
C.指令和數據任何時候都存放在外存中
D.程序被啟動前指令和數據都存放在外存中，而啟動后指令和數據被裝入內存

19.在讀寫硬盤的一個物理記錄塊時，不需要的參數是(     )。

A.柱面(磁道)號
B.盤片(磁頭)
C.簇號
D.扇區號

20.有效容量為128KB的Cache，每塊1 6字節，8路組相聯。字節地址為1 2345 67 H的單元調入該Cache，其Tag應是(     )。

A.1234H
B.2468H
C.048DH
D.12345 H：

21.中斷的概念是(     )。

A.暫停正在運行的程序
B.暫停對內存的訪問
C.暫停CPU運行
D.I／O設備的輸入或輸出

22.在操作系統的以下功能中，不需要硬件支持的是(     )。

A.中斷系統
B.時鐘管
C.地址映射
D.頁面調度

23.在單處理機的多進程系統中，進程什么時候占用處理機以及決定占用時間的長短是 (     )。

A.進程相應的代碼長度
B.進程總共需要運行的時間
C.進程特點和進程調度策略
D.進程完成什么功能

24.系統產生死鎖的可能原因是(     )。

A.共享資源分配不當
B.系統資源不足
C.進程運行太快
D.CPU內核太多

25.下列選項中，降低進程優先級的合理時機是(     )。

A.進程時間片用完
B.進程剛完成I／O，進入就緒隊列
C.進程長期處于就緒隊列
D.進程從就緒狀態轉換為運行狀態

26.在某計算機中采用了多級存儲體系，設計有cache，主存和磁盤，假設訪問cache一個字需要花費10ns，若該字不在cache p但是存在在主存中，那么需要100ns載2k cache，然后重新開始定位。若該字既不在cache中，也不在主存中，那么需要10ms的時間裝入主存，再化100ns復制到cache，再開始定位。設cache的命中率為0．90，主存的命中率為0．75，那么，該系統訪問一個字的平均時間是(     )。

A.25000ns
B.250023ns
C.250017ns
D.250020ns

27.在一個采用請求式調頁的虛擬存儲系統中，存放在外存上的程序代碼調入內存的時機是(     )。

A.在進程創建填寫進程表時
B.在進程創建分配內存時
C.在進程被調度占用處理機執行時
D.在每次產生缺頁中斷時

28.為了防止各種意外可能破壞文件，文件系統保護文件的方法可以是(     )。

A.為文件加密
B.對每個文件規定使用權限
C.建立副本和定時轉儲
D.為文件設置口令

29.已知某磁盤的平均轉速為r秒／轉，平均尋道時間為T秒，每個磁道可以存儲的字節數為N，現向該磁盤讀寫b字節的數據，采用隨機尋道的方法，每道的所有扇區組成一個簇，請問：平均訪問時間是(     )。

A.b／N*(r+T)
B.b／N*T
C.(b／Nq+T)*r
D.b*T／N+r

30.文件系統中，當調用open()去打開一個文件時，其主要目的是(     )。

A.把文件內容從外存調入內存
B.把文件的控制信息從外存調入內存
C.把文件系統的文件分配表調入內存
D.把文件系統的目錄調入內存

31.在下列事件中，哪個不是設備分配中應該考慮的問題(     )。

A.及時性
B.設備的固有屬性
C.設備的無關性
D.安全性

32.OSI模型中完成路徑選擇功能的層次是(     )。

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

33.現采用調相與調幅相結合的調制方式，載波有四種相位變化和兩種振幅變化，調制速率是600波特，那么數據速率是(     )。

A.1 200bps
B.1 800bps
C.2400bps
D.3 600bps

34.在CSMA／CD協議中，下列指標與沖突時間沒有關系的是(     )。

A.檢測一次沖突所需的最長時間
B.最小幀長度
C.最大幀長度
D.最大幀碎片長度

35.CSMA／CD以太網中，發生沖突后，重發前的退避時間最大是(     )。

A.65536個時間片
B.65535個時間片
C.1024個時間片
D.1023個時間片

36.IEEE 802．11采用了CSMA／CA協議，下面關于這個協議的描述中錯誤的是(     )。

A.各個發送站在兩次幀間隔(IFS)之間進行競爭發送
B.每一個發送站維持一個后退計數器并監聽網絡上的通信
C.各個發送站按業務的優先級獲得不同的發送機會
D.CSMA／CA協議適用于突發性業務

37.局域網交換機首先完整地接收數據幀，并進行差錯檢測。如果正確，則根據幀目的，則根據目的地址確定輸出端口號再轉發出去。這種交換方式是(     )。

A.直接交換
B.改進直接交換
C.存儲轉發交換
D.查詢交換

38.在TCP協議中，建立連接時被置為1的標志位和所處的字段是(     )。

A.保留，ACK
B.保留，SYN
C.偏移，ACK
D.控制，SYN

39.下列協議中，用于解決電子郵件中傳輸多語言文字和附件問題的協議是(     )。

A.MIME
B.SMTP
C.SNMP
D.POP3

二、2.綜合應用題

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

0. 對于下圖G，按下列條件試分別寫出從頂點0出發按深度優先搜索遍歷得到的頂點序列和按廣度優先搜索遍歷得到的頂點序列。
  (1)假定它們均采用鄰接矩陣表示；
  (2)假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。
  

1. 一棵二叉樹的繁茂度定義為R層結點數的最大值與樹的高度的乘積。編寫一個算法求二叉樹的繁茂度。

2. (11分)某圖形顯示器的分辨率為640×480，刷新頻率為50Hz，且假定水平回掃期和垂直回掃期各占水平掃描周期和垂直掃描周期的20％，試計算圖形顯示器的行頻、水平掃描周期、每個像素的讀出時間和視頻帶寬。若分辨率提高到1024×768，刷新頻率提高到60Hz，再次計算圖形顯示器的行頻、水平掃描周期、每個像素的讀出時間和視頻帶寬。

3. 一臺模型機共有7條指令，主頻25MHz，各指令的使用頻率與CPI如下表所示，該機有8位和16位兩種指令字長，采用2—4擴展操作碼。8位字長指令為寄存器一寄存器(R—R)二地址類型，1 6位字長指令為寄存器～存儲器(R—M)二地址變址類型(地址碼范圍在一128～127之間)。
  (1)計算該機的MIPS速率。
  (2)計算操作碼的平均碼長。
  (3)設計該機的兩種指令格式，標出各字段位數并給出操作碼編碼。
  (4)該機允許使用多少個可編址的通用寄存器，多少個變址寄存器?
  (5)如何計算存儲器有效地址?
  

4. 假設有8個記錄A、B，C、D、E、F、G、H存放在磁盤里，每個磁道有8個扇區，正好可以存放8個記錄。假設磁盤旋轉速度為20ms／r，處理程序每讀出一個記錄后，用2ms的 時間進行處理，請問：
  (1)當記錄A、B、C、D、E、F、G、H按順序放在磁道上時，順序處理這5個記錄花費的總時間是多少?假設啟動時的位置正好在A扇區的起點。
  (2)如何采取優化方法，使處理這些記錄所花費的總時間最短?求出該最短時間。

5. 在某個操作系統中，通過大量的實驗，人們觀察到在兩次缺頁中斷之間執行的指令數與分配給程序的頁框數成正比，即可用內存加倍，缺頁中斷的平均間隔也加倍。整體缺頁次數減少約一半。假設一條普通指令需要100ns，但若發生了缺頁中斷就需要1ms。一個程序運行了60s，期間發生了1 500次缺頁中斷，如果該程序的可用內存增加到原來的2倍，那么，請計算，此時這個程序運行需要多少時間?

6. 下面是給出的一段IP數據包頭所包含的數據，00 00 30 52 52 40 00 80 06 2C 23 C0 A8 01 01 D8 03 E2 15，請根據IPv4頭部格式回答如下問題：
  (1)該IP包的發送主機和接收主機的地址分別是什么?
  (2)該IP包的總長度是多少?頭部長度是多少?
  (3)該IP分組有分片嗎?如果有分片它的分片偏移量是多少?
  (4)該IP包是由什么傳輸層協議發出的?