一、單項選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求）

1、若棧S1中保存整數，棧S2中保存運算符，函數F()依次執行下述各步操作：

（1）從S1中依次彈出兩個操作數a和b；

（2）從S2中彈出一個運算符op；

（3）執行相應的運算bopa；

（4）將運算結果壓入S1中。

假定S1中的操作數依次是5，8，3，2（2在棧頂），S2中的運算符依次是*，-，+（+在棧頂）。調用3次F（）后，S1棧頂保存的值是（  ）。

A.-15

B.15

C.-20

D.20

2、現有隊列Q與棧S，初始時Q中的元素依次是1，2，3，4，5，6(1在隊頭)，S為空。若僅允許下列3種操作：① 出隊并輸出出隊元素；② 出隊并將出隊元素入棧；③ 出棧并輸出出棧元素，則不能得到的輸出序列是（  ）。

A.1，2，5，6，4，3

B.2，3，4，5，6，1

C.3，4，5，6，1，2

D.6，5，4，3，2，1

3、設有一個12×12的對稱矩陣M，將其上三角部分的元素mi,j(1<=i<=j<=12)按行優先存入C語言的一維數組N中，元素m6,6在N中的下標是（  ）。

A.50

B.51

C.55

D.66

4、設一棵非空完全二叉樹T的所有葉結點均位于同一層，且每個非葉結點都有2個子結點。若T有k個葉結點，則T的結點總數是（  ）。

A.2k-1

B.2k

C.k2

D.2k-1

5、已知字符集{a，b，c，d，e，f}，若各字符出現的次數分別為6，3，8，2，10，4，則對應字符集中各字符的哈夫曼編碼可能是（  ）。

A.00，1011，01，1010，11，100

B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010

D.0011，10，11，0010，01，000

6、已知二叉排序樹如下圖所示，元素之間應滿足的大小關系是（  ）。

A.x1<x2<x5

B.x1<x4<x5

C.x3<x5<x4

D.x4<x3<x5

7、下列選項中，不是如下有向圖的拓撲序列的是（  ）。

A.1，5，2，3，6，4

B.5，1，2，6，3，4

C.5，1，2，3，6，4

D.5，2，1，6，3，4

8、高度為5的3階B樹含有的關鍵字個數至少是（  ）。

A.15

B.31

C.62

D.242

9、現有長度為7、初始為空的散列表HT，散列函數H(k)=k%7，用線性探測再散列法解決沖突。將關鍵字22，43，15依次插入到HT后，查找成功的平均查找長度是（  ）。

A.1、5

B.1、6

C.2

D.3

10、對初始數據序列（8，3，9，11，2，1，4，7，5，10，6）進行希爾排序。若第一趟排序結果為（1，3，7，5，2，6，4，9，11，10，8），第二趟排序結果為（1，2，6，4，3，7，5，8，11，10，9），則兩趟排序采用的增量（間隔）依次是（  ）。

A.3，1

B.3，2

C.5，2

D.5，3

11、在將數據序列（6，1，5，9，8，4，7）建成大根堆時，正確的序列變化過程是（  ）。

A.6，1，7，9，8，4，5→6，9，7，1，8，4，5→9，6，7，1，8，4，5→9，8，7，1，6，4，5

B.6，9，5，1，8，4，7→6，9，7，1，8，4，5→9，6，7，1，8，4，5→9，8，7，1，6，4，5

C.6，9，5，1，8，4，7→9，6，5，1，8，4，7→9，6，7，1，8，4，5→9，8，7，1，6，4，5

D.6，1，7，9，8，4，5→7，1，6，9，8，4，5→7，9，6，1，8，4，5→9，7，6，1，8，4，5→9，8，6，1，7，4，5

12、馮·諾依曼結構計算機中數據采用二進制編碼表示，其主要原因是（  ）。

Ⅰ.二進制的運算規則簡單

Ⅱ.制造兩個穩態的物理器件較容易

Ⅲ.便于用邏輯門電路實現算術運算

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅲ

D.Ⅰ、Ⅱ和Ⅲ

13、假定帶符號整數采用補碼表示，若int型變量x和y的機器數分別是FFFF FFDFH和0000 0041H，則x、y的值以及x-y的機器數分別是（  ）。

A.x=-65，y=41，x-y的機器數溢出

B.x=-33，y=65，x-y的機器數為FFFFFF9DH

C.x=-33，y=65，x-y的機器數為FFFFFF9EH

D.x=-65，y=41，x-y的機器數為FFFFFF96H

14、IEEE754單精度浮點格式表示的數中，最小的規格化正數是（  ）。

A.1.0X2-126

B.1.0X2-127

C.1.0X2-128

D.1.0X2-149

15、某32位計算機按字節編址，采用小端（Little Endian）方式。若語令“int i=0”對應指令的機器代碼為“C745FC00000000”，則語句“int i=-64”對應指令的機器代碼是（  ）。

A.C7 45 FC C0 FF FF FF

B.C7 45 FC 0C FF FF FF

C.C7 45 FC FF FF FF C0

D.C7 45 FC FF FF FF 0C

16、整數x的機器數為11011000，分別對x進行邏輯右移1位和算術右移1位操作，得到的機器數各是（  ）。

A.1110 1100、1110 1100

B.0110 1100、1110 1100

C.1110 1100、0110 1100

D.0110 1100、0110 1100

17、假定DRAM芯片中存儲陣列的行數為r、列數為c，對于一個2K×1位的DRAM芯片，為保證其地址引腳數最少，并盡量減少刷新開銷，則r、c的取值分別是（  ）。

A.2048、1

B.64、32

C.32、64

D.1、2048

18、按字節編址的計算機中，某double型數組A的首地址為2000H，使用變址尋址和循環結構訪問數組A，保存數組下標的變址寄存器初值為0，每次循環取一個數組元素，其偏移地址為變址值乘以sizeof(double)，取完后變址寄存器內容自動加1。若某次循環所取元素的地址為2100H，則進入該次循環時變址寄存器的內容是（  ）。

A.25

B.32

C.64

D.100

19、減法指令“sub R1,R2,R3”的功能為“(R1)-(R2)→R3"，該指令執行后將生成進位/借位標志CF和溢出標志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，則該減法指令執行后，CF與OF分別為（  ）。

A.CF=0，OF=0

B.CF=1，OF=0

C.CF=0，0F=1

D.CF=1，OF=1

20、若某計算機最復雜指令的執行需要完成5個子功能，分別由功能部件A~E實現，各功能部件所需時間分別為80ps、50ps、50ps、70ps和50ps，采用流水線方式執行指令，流水段寄存器延時為20ps，則CPU時鐘周期至少為（  ）。

A.60ps

B.70ps

C.80ps

D.100ps

21、下列選項中，可提高同步總線數據傳輸率的是（  ）。

Ⅰ.增加總線寬度

Ⅱ.提高總線工作頻率

Ⅲ.支持突發傳輸

Ⅳ.采用地址/數據線復用

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅱ、Ⅲ

C.僅Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

22、下列關于外部I/O中斷的敘述中，正確的是（  ）。

A.中斷控制器按所接收中斷請求的先后次序進行中斷優先級排隊

B.CPU響應中斷時，通過執行中斷隱指令完成通用寄存器的保護

C.CPU只有在處于中斷允許狀態時，才能響應外部設備的中斷請求

D.有中斷請求時，CPU立即暫停當前指令執行，轉去執行中斷服務程序

23、下列關于多任務操作系統的敘述中，正確的是（  ）。

Ⅰ、具有并發和并行的特點

Ⅱ、需要實現對共享資源的保護

Ⅲ、需要運行在多CPU的硬件平臺上

A.僅Ⅰ

B.僅Ⅱ

C.僅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

24、某系統采用基于優先權的非搶占式進程調度策略，完成一次進程調度和進程切換的系統時間開銷為1μs。在T時刻就緒隊列中有3個進程P1、P2和P3，其在就緒隊列中的等待時間、需要的CPU時間和優先權如下表所示。

若優先權值大的進程優先獲得CPU，從T時刻起系統開始進程調度，則系統的平均周轉時間為（  ）。

A.54μs

B.73μs

C.74μs

D.75μs

25、屬于同一進程的兩個線程thread1和thread2并發執行，共享初值為0的全局變量x。thread1和thread2實現對全局變量x加1的機器級代碼描述如下。

在所有可能的指令執行序列中，使x的值為2的序列個數是（  ）。

A.1

B.2

C.3

D.4

26、假設系統中有4個同類資源，進程P1、P2和P3需要的資源數分別為4、3和1，P1、P2和P3已申請到的資源數分別為2、1和0，則執行安全性檢測算法的結果是（  ）。

A.不存在安全序列，系統處于不安全狀態

B.存在多個安全序列，系統處于安全狀態

C.存在唯一安全序列P3、P1、P2，系統處于安全狀態

D.存在唯一安全序列P3、P2、P1，系統處于安全狀態

27、下列選項中，可能導致當前進程P阻塞的事件是（  ）。

Ⅰ、進程P申請臨界資源

Ⅱ、進程P從磁盤讀取數據

Ⅲ、系統將CPU分配給高優先權的進程

A.僅Ⅰ

B.僅Ⅱ

C.僅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

28、若x是管程內的條件變量，則當進程執行x、wait()時所做的工作是（  ）。

A.實現對變量x的互斥訪問

B.喚醒一個在x上阻塞的進程

C.根據x的值判斷該進程是否進入阻塞狀態

D.阻塞該進程，并將之插入x的阻塞隊列中

29、當定時器產生時鐘中斷后，由時鐘中斷服務程序更新的部分內容是（  ）。

Ⅰ、內核中時鐘變量的值

Ⅱ、當前進程占用CPU的值

Ⅲ、當前進程在時間片內剩余執行時間

A.僅Ⅰ、Ⅱ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ 

30、系統總是訪問磁盤的某個磁道而不響應對其他磁道的訪問請求，這種現象稱為磁臂黏著。下列磁盤調度算法中，不會導致磁臂粘著的是（  ）。

A.先來先服務（FCFS）

B.最短尋道時間優先（SSTF）

C.掃描算法（SCAN）

D.循環掃描算法（CSCAN）

31、下列優化方法中，可以提高文件訪問速度的是（  ）。

Ⅰ、提前讀

Ⅱ、為文件分配連續的簇

Ⅲ、延遲寫

Ⅳ、采用磁盤高速緩存

A.僅Ⅰ、Ⅱ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ、Ⅳ

32、在下列同步機制中，可以實現讓權等待的是（  ）。

A.Peterson方法

B.swap指令

C.信號量方法

D.TestAndSet指令

33、下列TCP/IP應用層協議中，可以使用傳輸層無連接服務的是（  ）。

A.FTP

B.DNS

C.SMTP

D.HTTP

34、下列選項中，不屬于物理層接口規范定義范疇的是（  ）。

A.接口形狀

B.引腳功能

C.物理地址

D.信號電平

35、IEEE802、11無線局域網的MAC協議CSMA/CA進行信道預約的方法是（  ）。

A.發送確認幀

B.采用二進制指數退避

C.使用多個MAC地址

D.交換RTS與CTS幀

36、主機甲采用停-等協議向主機乙發送數據，數據傳輸速率是3kbps，單向傳播延時是200ms，忽略確認幀的傳輸延時。當信道利用率等于40%時，數據幀的長度為（  ）。

A.240比特

B.400比特

C.480比特

D.800比特

37、路由器R通過以太網交換機S1和S2連接兩個網絡，R的接口、主機H1和H2的IP地址與MAC地址如下圖所示。若H1向H2發送1個IP分組P，則H1發出的封裝P的以太網幀的目的MAC地址、H2收到的封裝P的以太網幀的源MAC地址分別是（  ）。

A.00-a1-b2-c3-d4-62，00-1a-2b-3c-4d-52

B.00-a1-b2-c3-d4-62，00-a1-b2-c3-d4-61

C.00-1a-2b-3c-4d-51，00-1a-2b-3c-4d-52

D.00-1a-2b-3c-4d-51，00-a1-b2-c3-d4-61

38、某路由表中有轉發接口相同的4條路由表項，其目的網絡地址分別為35.230.32.0/21，35.230.40.0/21，35.230.48.0/21和35.230.56.0/21，將該4條路由聚合后的目的網絡地址為（  ）。

A.35.230.0.0/19

B.35.230.0.0/20

C.35.230.32.0/19

D.35.230.32.0/20

39、UDP協議實現分用（demultiplexing）時所依據的頭部字段是（  ）。

A.源端口號

B.目的端口號

C.長度

D.校驗和

40、無需轉換即可由SMTP協議直接傳輸的內容是（  ）。

A.JPEG圖像

B.MPEG視頻

C.EXE文件

D.ASCII文本

二、綜合應用題（第41~47小題，共70分）

41、（13分）給定一個含n（n>=1）個整數的數組，請設計一個在時間上盡可能高效的算法，找出數組中未出現的最小正整數。例如，數組{-5，3，2，3}中未出現的最小正整數是1；數組{1，2，3}中未出現的最小正整數是4。要求：

（1）給出算法的基本設計思想。

（2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

（3）說明你所設計算法的時間復雜度和空間復雜度。 

42、（12分）擬建設一個光通信骨干網絡連通BJ、CS、XA、QD、JN、NJ、TL和WH等8個城市，題42圖中無向邊上的權值表示兩個城市間備選光纜的鋪設費用。

請回答下列問題。

（1）僅從鋪設費用角度出發，給出所有可能的最經濟的光纜鋪設方案（用帶權圖表示），并計算相應方案的總費用。

（2）題42圖可采用圖的哪一種存儲結構？給出求解問題（1）所使用的算法名稱。

（3）假設每個城市采用一個路由器按（1）中得到的最經濟方案組網，主機H1直接連接在TL的路由器上，主機H2直接連接在BJ的路由器上。若H1向H2發送一個TTL=5的IP分組，則H2是否可以收到該IP分組？

43、（8分）假定計算機的主頻為500MHz，CPI為4。現有設備A和B，其數據傳輸率分別為2MBps和40MBps，對應I/O接口中各有一個32位數據緩沖寄存器。請回答下列問題，要求給出計算過程。

（1）若設備A采用定時查詢I/O方式，每次輸入/輸出都至少執行10條指令。設備A最多間隔多長時間查詢一次才能不丟失數據？CPU用于設備A輸入輸出的時間占CPU總時間的百分比至少是多少？

（2）在中斷I/O方式下，若每次中斷響應和中斷處理的總時鐘周期數至少為400，則設備B能否采用中斷I/O方式？為什么？

（3）若設備B采用DMA方式，每次DMA傳送的數據塊大小1000B，CPU用于DMA預處理和后處理的總時鐘周期數為500，則CPU用于設備B輸入/輸出的時間占CPU總時間的百分比最大是多少？

44、（15分）某計算機采用頁式虛擬存儲管理方式，按字節編址。CPU進行存儲訪問的過程如題44圖所示。

題44圖

根據題44圖回答下列問題。

（1）主存物理地址占多少位？

（2）TLB采用什么映射方式？TLB用SRAM還是DRAM實現？

（3）Cache采用什么映射方式？若Cache采用LRU替換算法和回寫（Write Back）策略，則Cache每行中除數據（Data）、Tag和有效位外，還應有哪些附加位？Cache總容量是多少？Cache中有效位的作用是什么？

（4）若CPU給出的虛擬地址為0008C040H，則對應的物理地址是多少？是否在Cache中命中？說明理由，若CPU給出的虛擬地址為0007C260H，則該地址所在主存塊映射到的Cache組號是多少？

45、（8分）請根據題44圖給出的虛擬存儲管理方式，回答下列問題。

（1）某虛擬地址對應的頁目錄號為6，在相應的頁表中對應的頁號為6，頁內偏移量為8，該虛擬地址的十六進制表示是什么？

（2）寄存器PDBR用于保存當前進程的頁目錄起始地址，該地址是物理地址還是虛擬地址？進程切換時，PDBR的內容是否會變化？說明理由。同一進程的線程切換時，PDBR的內容是否會變化？說明理由。

（3）為了支持改進型CLOCK置換算法，需要在頁表項中設置哪些字段？

46、（7分）某文件系統采用索引節點存放文件的屬性和地址信息，簇大小為4KB。每個文件索引節點占64B，有11個地址項，其中直接地址項8個，一級、二級和三級間接地址項各1個，每個地址項長度為4B。請回答下列問題。

（1）該文件系統能支持的最大文件長度是多少？（給出計算表達式即可）

（2）文件系統用1M（1M=220）個簇存放文件索引節點，用512M個簇存放文件數據。若一個圖像文件的大小為5600B，則該文件系統最多能存放多少個這樣的圖像文件？

（3）若文件F1的大小為6KB，文件F2的大小為40KB，則該文件系統獲取F1和F2最后一個簇的簇號需要的時間是否相同？為什么？

47、（7分）某公司網絡如題47圖所示。IP地址空間192.168.1.0/24被均分給銷售部和技術部兩個子網，并已分別為部分主機和路由器接口分配了IP地址，銷售部子網的MTU=1500B，技術部子網的MTU=800B。

請回答下列問題。

（1）銷售部子網的廣播地址是什么？技術部子網的子網地址是什么？若每個主機僅分配一個IP地址，則技術部子網還可以連接多少臺主機？

（2）假設主機192.168.1.1向主機192.168.1.208發送一個總長度為1500B的IP分組，IP分組的頭部長度為20B，路由器在通過接口F1轉發該IP分組時進行了分片。若分片時盡可能分為最大片，則一個最大IP分片封裝數據的字節數是多少？至少需要分為幾個分片？每個分片的片偏移量是多少？