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

1、設n是描述問題規模的非負整數，下列程序段的時間復雜度是（  ）。

x=0;

while(n>=(x+1)*(x+1))

x=x+1;

A.O(logn)

B.O(n1/2)

C.O(n)

D.O(n2)

2、若將一棵樹T轉化為對應的二叉樹BT，則下列對BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是（  ）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

3、對n個互不相同的符號進行哈夫曼編碼。若生成的哈夫曼樹共有115個結點，則n的值是（  ）。

A.56

B.57

C.58

D.60

4、在任意一棵非空平衡二叉樹（AVL樹）T1中，刪除某結點v之后形成平衡二叉樹T2，再將v插入T2形成平衡二叉樹T3。下列關于T1與T3的敘述中，正確的是（  ）。

I.若v是T1的葉結點，則T1與T3可能不相同

II.若v不是T1的葉結點，則T1與T3一定不相同

III.若v不是T1的葉結點，則T1與T3一定相同

A.僅I

B.僅II

C.僅I、II

D.僅I、III

5、下圖所示的AOE網表示一項包含8個活動的工程。活動d的最早開始時間和最遲開始時間分別是（  ）。

A.3和7

B.12和12

C.12和14

D.15和15

6、用有向無環圖描述表達式(x+y)((x+y)/x)，需要的頂點個數至少是（  ）。

A.5

B.6

C.8

D.9

7、選擇一個排序算法時，除算法的時空效率，下列因素中，還需要考慮的是（  ）。

I.數據的規模

II.數據的存儲方式

III.算法的穩定性

IV.數據的初始狀態

A.僅III

B.僅I、II

C.僅II、III、IV

D.I、II、III、IV

8、現有長度為11且初始為空的散列表HT，散列函數是H(key)=key%7，采用線性探查(線性探測再散列)法解決沖突。將關鍵字序列87，40，30，6，11，22，98，20依次插入HT后，HT查找失敗的平均查找長度是（  ）。

A.4

B.5.25

C.6

D.6.29

9、設主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法進行模式匹配，到匹配成功時為止，在匹配過程中進行的單個字符間的比較次數是（  ）。

A.9

B.10

C.12

D.15

10、排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列序列中，不可能是快速排序第二趟結果的是（  ）。

A.5，2，16，12，28，60，32，72

B.2，16，5，28，12，60，32，72

C.2，12，16，5，28，32，72，60

D.5，2，12，28，16，32，72，60

11、設外存上有120個初始歸并段，進行12路歸并時，為實現最佳歸并，需要補充的虛段個數是（  ）。

A.1

B.2

C.3

D.4

12、下列關于馮·諾依曼結構計算機基本思想的敘述中，錯誤的是（  ）。

A.程序的功能都通過中央處理器執行指令實現

B.指令和數據都用二進制數表示，形式上無差別

C.指令按地址訪問，數據都在指令中直接給出

D.程序執行前，指令和數據需預先存放在存儲器中

13、考慮以下C語言代碼：

unsigned short usi = 65535;

short si = usi;

執行上述程序段后，si的值是（  ）。

A.-1

B.-32767

C.-32768

D.-65535

14、下列關于缺頁處理的敘述中，錯誤的是（  ）。

A.缺頁是在地址轉換時CPU檢測到的一種異常

B.缺頁處理由操作系統提供的缺頁處理程序來完成

C.缺頁處理程序根據頁故障地址從外存讀入所缺失的頁

D.缺頁處理完成后回到發生缺頁的指令的下一條指令執行

15、某計算機采用大端方式，按字節編址。某指令中操作數的機器數為1234 FF00H，該操作數采用基址尋址方式，形式地址（用補碼表示）為FF12H，基址寄存器的內容為F000 0000H，則該操作數的LSB（最低有效字節）所在的地址是（  ）。

A.F000 FF12H

B.F000 FF15H

C.EFFF FF12H

D.EFFF FF15H

16、下列有關處理器時鐘脈沖信號的敘述中，錯誤的是（  ）。

A.時鐘脈沖信號由機器脈沖源發出的脈沖信號經整形和分頻后形成

B.時鐘脈沖信號的寬度稱為時鐘周期，時鐘周期的倒數為機器主頻

C.時鐘周期以相鄰狀態單元間組合邏輯電路的最大延遲為基準確定

D.處理器總是在每來一個時鐘脈沖信號時就開始執行一條新的指令

17、某指令功能為R[r2]←R[r1]+M[R[r0]]，其兩個源操作數分別采用寄存器、寄存器間接尋址方式。對于下列給定部件，該指令在取數及執行過程中需要用到的是（  ）。

Ⅰ.通用寄存器組（GPRs）

Ⅱ.算術邏輯單元（ALU）

Ⅲ.存儲器（Memory）

Ⅳ.指令譯碼器（ID）

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅱ、Ⅲ

C.僅Ⅱ、Ⅲ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

18、在采用“取指、譯碼/取數、執行、訪存、寫回”5段流水線的處理器中，執行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器編號。

下列指令對中，不存在數據冒險的是（  ）。

A.I1和I3

B.I2和I3

C.I2和I4

D.I3和I4

19、假定一臺計算機采用3通道存儲器總線，配套的內存條型號為DDR3-1333，即內存條所接插的存儲器總線的工作頻率為1333MHz，總線寬度為64位，則存儲器總線的總帶寬大約是（  ）。

A.10.66GBps

B.32GBps

C.64GBps

D.96GBps

20、下列關于磁盤存儲器的敘述中，錯誤的是（  ）。

A.磁盤的格式化容量比非格式化容量小

B.扇區中包含數據、地址和校驗等信息

C.磁盤存儲器的最小讀寫單位為一字節

D.磁盤存儲器由磁盤控制器、磁盤驅動器和盤片組成

21、某設備以中斷方式與CPU進行數據交換，CPU主頻為1GHz，設備接口中的數據緩沖寄存器為32位，設備的數據傳輸率為50KBps。若每次中斷開銷（包括中斷響應和中斷處理）為1000個時鐘周期，則CPU用于該設備輸入/輸出的時間占整個CPU時間的百分比最多是（  ）。

A.1.25%

B.2.5%

C.5%

D.12.5%

22、下列關于DMA方式的敘述中，正確的是（  ）。

Ⅰ.DMA傳送前由設備驅動程序設置傳送參數

Ⅱ.數據傳送前由DMA控制器請求總統使用權

Ⅲ.數據傳送由DMA控制器直接控制總線完成

Ⅳ.DMA傳送結束后的處理由中斷服務程序完成

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ、Ⅳ

C.僅Ⅱ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ、Ⅳ

23、下列關于線程的描述中，錯誤的是（  ）。

A.內核級線程的調度由操作系統完成

B.操作系統為每個用戶級線程建立一個線程控制塊

C.用戶級線程間的切換比內核級線程間的切換效率高

D.用戶級線程可以在不支持內核級線程的操作系統上實現

24、下列選項中，可能會將進程喚醒的事件是（  ）。

Ⅰ.I/O結束

Ⅱ.某進程退出臨界區

Ⅲ.當前進程的時間片用完

A.僅Ⅰ

B.僅Ⅲ

C.僅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

25、下列關于系統調用的敘述中，正確的是（  ）。

Ⅰ.在執行系統調用服務程序的過程中，CPU處于內核態

Ⅱ.操作系統通過提供系統調用避免用戶程序直接訪問外設

Ⅲ.不同的操作系統為應用程序提供了統一的系統調用接口

Ⅳ.系統調用是操作系統內核為應用程序提供服務的接口

A.僅Ⅰ、Ⅳ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅱ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

26、下列選項中，可用于文件系統管理空閑磁盤塊的數據結構是（  ）。

Ⅰ.位圖

Ⅱ.索引結點

Ⅲ.空閑磁盤塊鏈

Ⅳ.文件分配表（FAT）

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ、Ⅳ

C.僅Ⅰ、Ⅲ

D.僅Ⅱ、Ⅲ、Ⅳ

27、系統采用二級反饋隊列調度算法進行進程調度。就緒隊列Q1采用時間片輪轉調度算法，時間片為10ms；就緒隊列Q2采用短進程優先調度算法；系統優先調度Q1隊列中的進程，當Q1為空時系統才會調度Q2中的進程；新創建的進程首先進入Q1；Q1中的進程執行一個時間片后，若未結束，則轉入Q2。若當前Q1、Q2為空，系統依次創建進程P1、P2后即開始進程調度，P1、P2需要的CPU時間分別為30ms和20ms，則進程P1、P2在系統中的平均等待時間為（  ）。

A.25ms

B.20ms

C.15ms

D.10ms

28、在分段存儲管理系統中，用共享段表描述所有被共享的段。若進程P1和P2共享段S，下列敘述中，錯誤的是（  ）。

A.在物理內存中僅保存一份段S的內容

B.段S在P1和P2中應該具有相同的段號

C.P1和P2共享段S在共享段表中的段表項

D.P1和P2都不再使用段S時才回收段S所占的內存空間

29、某系統采用LRU頁置換算法和局部置換策略，若系統為進程P預分配了4個頁框，進程P訪問頁號的序列為0,1,2,7,0,5,3,5,0,2,7,6，則進程訪問上述頁的過程中，產生頁置換的總次數是（  ）。

A.3

B.4

C.5

D.6

30、下列關于死鎖的敘述中，正確的是（  ）。

Ⅰ.可以通過剝奪進程資源解除死鎖

Ⅱ.死鎖的預防方法能確保系統不發生死鎖

Ⅲ.銀行家算法可以判斷系統是否處于死鎖狀態

Ⅳ.當系統出現死鎖時，必然有兩個或兩個以上的進程處于阻塞態

A.僅Ⅱ、Ⅲ

B.僅Ⅰ、Ⅱ、Ⅳ

C.僅Ⅰ、Ⅱ、Ⅲ

D.僅Ⅰ、Ⅲ、Ⅳ 

31、某計算機主存按字節編址，采用二級分頁存儲管理，地址結構如下所示：

虛擬地址20501225H對應的頁目錄號、頁號分別是（  ）。

A.081H、101H

B.081H、401H

C.201H、101H

D.201H、401H

32、在下列動態分區分配算法中，最容易產生內存碎片的是（  ）。

A.首次適應算法

B.最壞適應算法

C.最佳適應算法

D.循環首次適應算法

33、OSI參考模型的第5層（自下而上）完成的主要功能是（  ）。

A.差錯控制

B.路由選擇

C.會話管理

D.數據表示轉換

34、100BaseT快速以太網使用的導向傳輸介質是（  ）。

A.雙絞線

B.單模光纖

C.多模光纖

D.同軸電纜

35、對于滑動窗口協議，如果分組序號采用3比特編號，發送窗口大小為5，則接收窗口最大是（  ）。

A.2

B.3

C.4

D.5

36、假設一個采用CSMA/CD協議的10Mb/s局域網，最小幀長是128B，則在一個沖突域內兩個站點之間的單向傳播延時最多是（  ）。

A.2.56μs

B.5.12μs

C.10.24μs

D.20.48μs

37、若將101.200.16.0/20劃分為5個子網，則可能的最小子網的可分配IP地址數是（  ）。

A.126

B.254

C.510

D.1022

38、某客戶通過一個TCP連接向服務器發送數據的部分過程如題38圖所示。客戶在t0時刻第一次收到確認序列號ack_seq=100的段，并發送序列號seq=100的段，但發生丟失。若TCP支持快速重傳，則客戶重新發送seq=100段的時刻是（  ）。

A.t1

B.t2

C.t3

D.t4

39、若主機甲主動發起一個與主機乙的TCP連接，甲、乙選擇的初始序列號分別為2018和2046，則第三次握手TCP段的確認序列號是（  ）。

A.2018

B.2019

C.2046

D.2047

40、下列關于網絡應用模型的敘述中，錯誤的是（  ）。

A.在P2P模型中，結點之間具有對等關系

B.在客戶/服務器（C/S）模型中，客戶與客戶之間可以直接通信

C.在C/S模型中，主動發起通信的是客戶，被動通信的是服務器

D.在向多用戶分發一個文件時，P2P模型通常比C/S模型所需的時間短

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

41、（13分）設線性表L=(a1,a2,a3,…,an-2,an-1,an)采用帶頭結點的單鏈表保存，鏈表中的結點定義如下:

typedef struct node

{ int data ;

struct node*next;

} NODE;

請設計一個空間復雜度為O(1)且時間上盡可能高效的算法，重新排列L中的各結點，得到線性表L'=(a1,an,a2,an-1,a3,an-2,…)。要求：

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

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

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

42、（10分）請設計一個隊列，要求滿足：① 初始時隊列為空；② 入隊時，允許增加隊列占用空間；③ 出隊后，出隊元素所占用的空間可重復使用，即整個隊列所占用的空間只增不減；④ 入隊操作和出隊操作的時間復雜度始終保持為O(1)。請回答下列問題：

（1）該隊列是應選擇鏈式存儲結構，還是應選擇順序存儲結構?

（2）畫出隊列的初始狀態，并給出判斷隊空和隊滿的條件。

（3）畫出第一個元素入隊后的隊列狀態。

（4）給出入隊操作和出隊操作的基本過程。

43、（8分）有n(n≥3)位哲學家圍坐在一張圓桌邊，每位哲學家交替地就餐和思考。在圓桌中心有m(m≥1)個碗，每兩位哲學家之間有一根筷子。每位哲學家必須取到一個碗和兩側的筷子后，才能就餐，進餐完畢，將碗和筷子放回原位，并繼續思考。為使盡可能多的哲學家同時就餐，且防止出現死鎖現象，請使用信號量的P、V操作［wait()、signal()操作］描述上述過程中的互斥與同步，并說明所用信號量及初值的含義。

44、（7分）某計算機系統中的磁盤有300個柱面，每個柱面有10個磁道，每個磁道有200個扇區，扇區大小為512B。文件系統的每個簇包含2個扇區。請回答下列問題：

（1）磁盤的容量是多少？

（2）假設磁頭在85號柱面上，此時有4個磁盤訪問請求，簇號分別為100260、60005、101660和110560。若采用最短尋道時間優先（SSTF）調度算法，則系統訪問簇的先后次序是什么？

（3）第100530簇在磁盤上的物理地址是什么？將簇號轉換成磁盤物理地址的過程是由I/O系統的什么程序完成的？

45、（16分）已知f(n) = n! = n x (n - 1) x(n-2)x…x2x1，計算f(n)的C語言函數f1的源程序（陰影部分）及其在32位計算機M上的部分機器級代碼如下：

其中，機器級代碼行包括行號、虛擬地址、機器指令和匯編指令，計算機M按字節編址，int型數據占32位。請回答下列問題：

（1）計算f(10)需要調用函數f1多少次？執行哪條指令會遞歸調用f1？

（2）上述代碼中，哪條指令是條件轉移指令？哪幾條指令一定會使程序跳轉執行？

（3）根據第16行的call指令，第17行指令的虛擬地址應是多少？已知第16行的call指令采用相對尋址方式，該指令中的偏移量應是多少（給出計算過程）？已知第16行的call指令的后4字節為偏移量，M是采用大端方式還是采用小端方式？

（4）f(13)=6227020800，但f1(13)的返回值為1932053504，為什么兩者不相等？要使f1(13)能返回正確的結果，應如何修改f1的源程序？

（5）第19行的imul指令（帶符號整數乘）的功能是R[eax]←R[eax]×R[ecx]，當乘法器輸出的高、低32位乘積之間滿足什么條件時，溢出標志OF=1？要使CPU在發生溢出時轉異常處理，編譯器應在imul指令后應加一條什么指令？

46、（7分）對于題45，若計算機M的主存地址為32位，釆用分頁存儲管理方式，頁大小為4KB，則第1行的push指令和第30行的ret指令是否在同一頁中（說明理由）？若指令Cache有64行，采用4路組相聯映射方式，主存塊大小為64B，則32位主存地址中，哪幾位表示塊內地址？哪幾位表示Cache組號？哪幾位表示標記（tag）信息？讀取第16行的call指令時，只可能在指令Cache的哪一組中命中（說明理由）？

47、（9分）某網絡拓撲如題47圖所示，其中R為路由器，主機H1～H4的IP地址配置以及R的各接口IP地址配置如圖中所示。現有若干以太網交換機（無VLAN功能）和路由器兩類網絡互聯設備可供選擇。

請回答下列問題：

（1）設備1、設備2和設備3分別應選擇什么類型的網絡設備？

（2）設備1、設備2和設備3中，哪幾個設備的接口需要配置IP地址？為對應的接口配置正確的IP地址。

（3）為確保主機H1～H4能夠訪問Internet，R需要提供什么服務？

（4）若主機H3發送一個目的地址為192.168.1.127的IP數據報，網絡中哪幾個主機會接收該數據報？