一、單項(xiàng)選擇題：1～40小題，每小題2分，共80分。在每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)比較符合試題要求。

1． 求整數(shù)n（n>=0）階乘的算法如下，其時(shí)間復(fù)雜度：

Int fact（int n）

{if （n<=1）

return 1；

return n*fact（n-1）；

}

A. O(log2n)

B. O(n）

C . (a log2n)

D. O(n2)

2．已知操作符包括‘+’，‘-’，‘*’，‘/’，‘（’和‘）’，將中綴表達(dá)式a+b-a*((c+d)/e-f)+g轉(zhuǎn)化為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來存放暫時(shí)還不能確定的運(yùn)算次序的操作符，若棧初始時(shí)為空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的比較大個(gè)數(shù)是：

A. 5

B. 7

C. 8

D. 11

3． 若一棵二叉樹的前序遍歷序列為a、e、b、d、c，后序遍歷序列為b、c、d、e、a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)：

A. 只有e

B. 有e、b

C. 有e、c

D. 無法確定

4．若平衡二叉樹的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為 ：

A. 10

B. 20

C. 32

D. 33

5．對(duì)有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是：

A. O(n)

B. O(e)

C. O(n+e)

D. O(n*e)

6． 若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是：

A. 存在，且唯一

B. 存在，且不唯一

C. 存在，可能不唯一

D. 無法確定是否存在

31．下列關(guān)于進(jìn)程和線程敘述中，正確的是：

A. 不管系統(tǒng)是否支持線程，進(jìn)程都是資源分配的基本單位。

B. 線程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位。

C. 系統(tǒng)級(jí)線程和用戶級(jí)線程的切換都需要內(nèi)核支持。

D. 同一進(jìn)程中的各個(gè)線程擁有各自不同的地址空間。

32．下列選項(xiàng)中，不能改善磁盤設(shè)備I/O性能的是：

A. 重排I/O請(qǐng)求次序

B. 在一個(gè)磁盤上設(shè)置多個(gè)分區(qū)

C. 預(yù)讀和滯后寫

D. 優(yōu)化文件物理的分布

33．在TCP/IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)協(xié)議的是：

A. PPP

B. IP

C. UDP

D. TCP

34．在物理層接口特性中用于描述完成每種功能的事件發(fā)生順序的是：

A. 機(jī)械特性

B. 功能特性

C. 過程特性

D. 電氣特性

38．ARP協(xié)議的功能是：

A. 根據(jù)IP地址查詢MAC地址

B. 根據(jù)MAC地址查詢IP地址

C. 根據(jù)域名查詢IP地址

D. 根據(jù)IP地址查詢域名

39．某主機(jī)的IP為180.80.77.55，子網(wǎng)掩碼為255.255.252.0，若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組，則目的地址為：

A. 180.80.76.0

B. 180.80.76.255

C. 180.80.77.255

D. 180.80.79.255

二、綜合應(yīng)用題：41~47小題，共70分。

41．設(shè)有6個(gè)有序表ABCDEF分別含有10、35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列，要求通過5次兩兩合并，將6個(gè)表比較終合并成1個(gè)升序表，并在比較壞情況下比較的總次數(shù)達(dá)到比較小，請(qǐng)回答：

（1）給出完整的合并過程，并求出比較壞情況下比較的總次數(shù)。

（2）根據(jù)你的合并過程，描述n（n≥2）個(gè)不等長升序表的合并策略，并說明理由。

46．某文件系統(tǒng)空間的比較大容量為4TB，（1T=240），以磁盤塊為基本分配單位，磁盤塊大小為1KB，文件控制塊（FCB）包含一個(gè)512B的索引表區(qū)。請(qǐng)回答：

（1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占多少字節(jié)？可支持的單個(gè)文件比較大長度是多少字節(jié)？

（2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：0——7字節(jié)采用<起始?jí)K號(hào)，塊數(shù)>格式表示文件創(chuàng)建時(shí)預(yù)分配的連續(xù)存儲(chǔ)空間，其中起始?jí)K號(hào)占6B，塊數(shù)2B，剩余504字節(jié)采用直接索引結(jié)構(gòu)，一個(gè)索引占6B，則可支持單個(gè)文件比較大長度是多少個(gè)字節(jié)？為了使單個(gè)文件的長度達(dá)到比較大，請(qǐng)指出起始?jí)K號(hào)和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。