一、1.單項(xiàng)選擇題

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

0.如果對(duì)含有n(n＞1)個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素，刪除最后一個(gè)元素，在第一個(gè)元素前面插入新元素，在最后一個(gè)元素的后面插入新元素，則最好使用( )。

A.只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單鏈表
B.只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的非循環(huán)單鏈表
C.只有頭結(jié)點(diǎn)指針沒有尾結(jié)點(diǎn)指針的循環(huán)單鏈表
D.既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表

1.在一個(gè)順序循環(huán)隊(duì)列中刪除元素時(shí)，首先需要(  )。

A.前移隊(duì)首指針
B.后移隊(duì)首指針
C.取出隊(duì)首指針?biāo)肝恢蒙系脑?br/>D.取出隊(duì)尾指針?biāo)肝恢蒙系脑?/p>

2.如果二叉樹T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的(  )。

A.先序
B.中序
C.后序
D.層次序

3.前序遍歷和中序遍歷結(jié)果相同的二叉樹為(  )。

A.根結(jié)點(diǎn)無左孩子的二叉樹
B.根結(jié)點(diǎn)無右孩子的二叉樹
C.所有結(jié)點(diǎn)只有左子樹的二叉樹
D.所有結(jié)點(diǎn)只有右子樹的二叉樹

4.對(duì)包含n個(gè)關(guān)鍵碼的散列表進(jìn)行檢索，平均檢索長(zhǎng)度為(  )。

A.O(log n)
B.O(n)
C.O(nlog n)
D.不直接依賴于n

5.

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

6.

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

7.下面關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的敘述中正確的是(  )。

A.用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)有關(guān)，與邊數(shù)無關(guān)
B.用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)無關(guān)
C.用鄰接表存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)
D.用鄰接表存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)

8.下列排序算法中，(  )每一趟都能選出一個(gè)元素放在最終位置上，并且是不穩(wěn)定的。

A.冒泡排序
B.希爾排序
C.直接選擇排序
D.直接插入排序

9.下列排序算法中，時(shí)間復(fù)雜度為O(nlog n)且占用額外空間最少的是(  )。

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

10.條件轉(zhuǎn)移指令執(zhí)行時(shí)所依據(jù)的條件來自(  )。

A.指令寄存器IR
B.程序計(jì)數(shù)器PC
C.程序狀態(tài)字寄存器PSWR
D.主存地址寄存器MAR

11.某計(jì)算機(jī)字長(zhǎng)8位，采用補(bǔ)碼表示小數(shù)。若某數(shù)真值為-0．1001，則它在該計(jì)算機(jī)中的機(jī)器數(shù)形式為( )。

A.10111
B.10110111
C.10111000
D.10110000

12.定點(diǎn)數(shù)采用模4補(bǔ)碼，即變形補(bǔ)碼進(jìn)行加減運(yùn)算時(shí)，判斷溢出的方法是(  )。

A.符號(hào)位進(jìn)位與最高數(shù)值位進(jìn)位相異時(shí)表明溢出
B.實(shí)際參與運(yùn)算的兩數(shù)符號(hào)位相同，結(jié)果又與原操作數(shù)符號(hào)不同時(shí)表明溢出
C.雙符號(hào)位不同時(shí)表明溢出
D.以上都正確

13.浮點(diǎn)運(yùn)算結(jié)果滿足下列哪個(gè)條件時(shí)，需做中斷處理(  )。

A.尾數(shù)雙符號(hào)位為“01”
B.尾數(shù)雙符號(hào)位為“10”
C.階碼雙符號(hào)位為“01”
D.階碼雙符號(hào)位為“10”

14.下列各選項(xiàng)是采用奇偶校驗(yàn)碼編碼的ASCII碼，所有編碼都未發(fā)生錯(cuò)誤，采用偶校驗(yàn)的是(  )。

A.01001101
B.0011001
C.10101101
D.1101000

15.下列只讀存儲(chǔ)器中，可編程且可以實(shí)現(xiàn)字擦除的是(  )。

A.掩模ROM
B.PROM
C.EPROM
D.EEPROM

16.下列關(guān)于機(jī)器字長(zhǎng)與指令字長(zhǎng)的說法正確的是(  )。

A.指令字長(zhǎng)等于機(jī)器字長(zhǎng)
B.指令字長(zhǎng)一定是機(jī)器字長(zhǎng)的整數(shù)倍
C.兩者長(zhǎng)度沒有必然關(guān)系
D.以上說法都不對(duì)

17.某機(jī)器指令字長(zhǎng)12位，有零地址、一地址、二地址三種指令，地址碼長(zhǎng)4位，采用擴(kuò)展操作碼技術(shù)。若二地址指令和一地址指令條數(shù)都取最大值，則該機(jī)指令條數(shù)最多為(  )。

A.16
B.46
C.48
D.4 366

18.下列哪個(gè)選項(xiàng)不可能是微指令格式中的組成部分(  )。

A.操作碼字段
B.操作控制字段
C.外部條件字段
D.下地址字段

19.某機(jī)中，設(shè)備號(hào)小的主設(shè)備在總線判優(yōu)時(shí)具有較高的優(yōu)先級(jí)，其總線判優(yōu)方式可能是(  )。

A.鏈?zhǔn)讲樵兎绞?br/>B.計(jì)數(shù)器定時(shí)查詢方式
C.獨(dú)立請(qǐng)求方式
D.以上都有可能

20.中斷向量表中保存的是(  )。

A.被中斷程序的返回地
B.中斷服務(wù)程序入口地址
C.中斷服務(wù)程序入口地址的地址
D.中斷優(yōu)先級(jí)

21.下列說法中錯(cuò)誤的是(  )。

A.程序查詢方式下，CPU與I／O設(shè)備串行工作
B.程序中斷方式下，CPU與I／O設(shè)備并行工作
C.DMA方式下，主程序可與I／O數(shù)據(jù)傳送并行工作
D.實(shí)現(xiàn)了DMA方式的系統(tǒng)中，程序中斷方式?jīng)]有存在的必要

22.為了保證操作系統(tǒng)本身的安全，(  )是必須加以保護(hù)的。

A.從內(nèi)核模式轉(zhuǎn)換到用戶模式
B.從存儲(chǔ)操作系統(tǒng)內(nèi)核的空間讀取數(shù)據(jù)
C.從存儲(chǔ)操作系統(tǒng)內(nèi)核的空間讀取指令
D.打開定時(shí)器

23.以下關(guān)于UNIX操作系統(tǒng)的敘述中，(  )是錯(cuò)誤的。

A.UNIX 對(duì)實(shí)時(shí)系統(tǒng)是不合適的，因?yàn)檫M(jìn)程在核心態(tài)不可搶占
B.UNIX終究會(huì)在市場(chǎng)上消失的
C.UNIX是目前最流行的操作系統(tǒng)之一
D.UNIX 比較適用于高檔計(jì)算機(jī)系統(tǒng)和網(wǎng)絡(luò)環(huán)境，它不能用于普通的微機(jī)

24.關(guān)于臨界區(qū)問題(critical section problem)是一個(gè)算法(假設(shè)只有進(jìn)程P0和P1可能進(jìn)入該臨界區(qū))，算法如下(i為0或1)，該算法(  )。
 repeat
  retry：if(turn≠-1)turn：=i；
  if(turn≠i)go to retry；
  turn：=-1；
  critical Section(臨界區(qū))
  turn=0；
  remainder Section(其他區(qū)域)
until false；

A.不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，且會(huì)出現(xiàn)“饑餓”(Starvation)
B.不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，但不會(huì)出現(xiàn)“饑餓”
C.保證進(jìn)程能互斥進(jìn)入臨界區(qū)，但會(huì)出現(xiàn)“饑餓”
D.保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn)“饑餓”

25.系統(tǒng)功能調(diào)用是( )。

A.用戶編寫的一個(gè)子程序
B.高級(jí)語言中的庫(kù)程序
C.操作系統(tǒng)中的一條命令
D.操作系統(tǒng)向用戶提供的接口

26.在(  )的情況下，系統(tǒng)出現(xiàn)死鎖。

A.計(jì)算機(jī)系統(tǒng)發(fā)生重大故障
B.有多個(gè)封鎖的進(jìn)程同時(shí)存在
C.若干進(jìn)程因競(jìng)爭(zhēng)資源而無休止地相互等待對(duì)方釋放已占有的資源
D.資源數(shù)大大小于進(jìn)程數(shù)或進(jìn)程同時(shí)申請(qǐng)的資源數(shù)大大超過資源總數(shù)

27.通常對(duì)文件系統(tǒng)來說，文件名及其屬性可以集中在(  )。

A.目錄
B.索引
C.字典
D.作業(yè)控制塊

28.一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長(zhǎng)度為32位，其中段號(hào)占8位，則最大段長(zhǎng)是(  )。

A.2⁸字節(jié)
B.2¹⁶字節(jié)
C.2²⁴字節(jié)
D.2³²字節(jié)

29.如果I／O設(shè)備和存儲(chǔ)設(shè)備之間的數(shù)據(jù)交換不經(jīng)過CPU來完成，則這種交換方式是 (  )。

A.程序查詢方式
B.中斷方式
C.DMA方式
D.外部總線方式

30.假設(shè)系統(tǒng)的所有資源是同類型的，系統(tǒng)中的進(jìn)程每次申請(qǐng)資源數(shù)最多1個(gè)，那么，下面列出的4種情況中，(  )可能發(fā)生死鎖。情況序號(hào)系統(tǒng)中進(jìn)程數(shù)資源總量

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

31.

A.進(jìn)程A
B.進(jìn)程B
C.進(jìn)程A和進(jìn)程B同時(shí)
D.不一定

32.下列交換方式中，(  )一次連接沿著一條路由路徑發(fā)送所有的數(shù)據(jù)。

A.分組交換
B.報(bào)文交換
C.電路交換
D.以上都不是

33.某通訊線路每20 ms采樣一次，每一個(gè)信號(hào)共有64種不同的狀態(tài)，那么這個(gè)線路的傳輸速率是(  )。

A.100 bps
B.200 bps
C.300 bps
D.400 bps

34.RS-232-C的電氣特性規(guī)定邏輯“1”的電平范圍為(  )。

A.+5～+15 V
B.-5～-15 V
C.0～+5 V
D.0～-5 V

35.一個(gè)16端口的二層以太網(wǎng)交換機(jī)，沖突域和廣播域的個(gè)數(shù)分別是(  )。

A.1，1
B.16，16
C.1，16
D.16，1

36.假定一臺(tái)主機(jī)的IP地址是222．205．74．56，子網(wǎng)掩碼為255．255．240．0，該子網(wǎng)地址為 (  )。

A.222．205．0．0
B.222．205．64．0
C.222．205．72．0
D.222．205．74．0

37.以下(  )協(xié)議完成了從網(wǎng)卡到IP地址的映射。

A.ARP協(xié)議
B.RARP協(xié)議
C.IGMP協(xié)議
D.ICMP協(xié)議

38.一個(gè)TCP連接總是以1 KB的最大段發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16 KB時(shí)發(fā)生了超時(shí)，如果接下來的4個(gè)RTT(往返時(shí)間)時(shí)間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是(  )。

A.7 KB
B.8 KB
C.9 KB
D.16 KB

39.在HTTP協(xié)議中，一個(gè)以2開頭的響應(yīng)報(bào)文表示(  )。

A.暫時(shí)性失敗
B.永久性失敗
C.重定向
D.成功

二、2.綜合應(yīng)用題

綜合應(yīng)用題
41-47小題，共70分。

0. 在平衡二叉樹中的每個(gè)結(jié)點(diǎn)上增設(shè)一個(gè)Lsize域，其值為它的左子樹中的結(jié)點(diǎn)個(gè)數(shù)加1，試寫一個(gè)時(shí)間復(fù)雜度為O(log n)的算法，確定樹中第k個(gè)結(jié)點(diǎn)的位置。

1.

2. 某32位機(jī)(機(jī)器字長(zhǎng)32位)的一臺(tái)外設(shè)通過32位總線與系統(tǒng)內(nèi)存相連。CPU每秒執(zhí)行100條指令，平均每條指令需要5個(gè)機(jī)器周期，其中3個(gè)周期必須訪問內(nèi)存，內(nèi)存讀寫需一個(gè)機(jī)器周期，假定CPU在95％的時(shí)間內(nèi)持續(xù)執(zhí)行“背景程序”，且這段時(shí)間內(nèi)不執(zhí)行I／O指令?，F(xiàn)該外設(shè)需要把一個(gè)非常大的數(shù)據(jù)塊傳送到內(nèi)存。
  (1)如果采用程序I／O方式，每傳送一32位字寬的數(shù)據(jù)需要CPU執(zhí)行2條指令。請(qǐng)計(jì)算最大數(shù)據(jù)傳輸率(單位：字／秒)。
  (2)如果采用DMA方式，在DMA與CPU出現(xiàn)總線訪問沖突時(shí)，CPU優(yōu)先。請(qǐng)計(jì)算最大數(shù)據(jù)傳輸率(單位：字／秒)。

3. 下圖是某模型機(jī)CPU的組成框圖。設(shè)該CPU采用同步控制邏輯，分取指周期、取第一操作數(shù)周期，取第二操作數(shù)周期、執(zhí)行周期四個(gè)機(jī)器周期，每個(gè)機(jī)器周期有T₀、T₁、T₂三個(gè)節(jié)拍。試寫出如下雙操作數(shù)運(yùn)算指令的微操作命令及節(jié)拍安排。ADD R0，(R1)  完成功能(R0)+((R1))→R0

4. 設(shè)有一緩沖池P，P中含有10個(gè)可用緩沖區(qū)，一個(gè)輸入進(jìn)程將外部數(shù)據(jù)讀入P，另有一個(gè)輸出進(jìn)程將P中數(shù)據(jù)取出并輸出(如下圖所示)。若進(jìn)程每次操作均以一個(gè)緩沖區(qū)為單位，試用記錄型信號(hào)量寫出兩個(gè)進(jìn)程的同步算法，要求寫出信號(hào)量的設(shè)置。
  輸入進(jìn)程  輸出進(jìn)程
  L：讀入數(shù)據(jù)  L：從一滿緩沖區(qū)中取出數(shù)據(jù)
  將數(shù)據(jù)寫入一空緩沖區(qū)  將數(shù)據(jù)輸出
  GnTOL  GOTOL

5.
處理一次缺頁(yè)的平均時(shí)間為108 ns(已含更新TLB和頁(yè)表的時(shí)間)，進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)：①TLB初始為空；②地址轉(zhuǎn)換時(shí)先訪問TLB，若TLB未命中，再訪問頁(yè)表(忽略訪問頁(yè)表之后的TLB更新時(shí)間)；③有效位為0表示頁(yè)面不在內(nèi)存，產(chǎn)生缺頁(yè)中斷，缺頁(yè)中斷處理后，返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請(qǐng)問：
  (1)依次訪問上述三個(gè)虛地址，各需多少時(shí)間?給出計(jì)算過程。
  (2)基于上述訪問序列，虛地址1565H的物理地址是多少?請(qǐng)說明理由。

6.