2012年計算機科學專業基礎綜合試題

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

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

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

A. 5

B. 7

C. 8

D. 11

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

A. 只有e

B. 有e、b

C. 有e、c

D. 無法確定

4．若平衡二叉樹的高度為6，且所有非葉結點的平衡因子均為1，則該平衡二叉樹的結點總數為 ：

A. 10

B. 20

C. 32

D. 33

5．對有n個結點、e條邊且使用鄰接表存儲的有向圖進行廣度優先遍歷，其算法時間復雜度是：

A. O(n)

B. O(e)

C. O(n+e)

D. O(n*e)

6． 若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結構是：

A. 存在，且唯一

B. 存在，且不唯一

C. 存在，可能不唯一

D. 無法確定是否存在

31．下列關于進程和線程敘述中，正確的是：

A. 不管系統是否支持線程，進程都是資源分配的基本單位。

B. 線程是資源分配的基本單位，進程是調度的基本單位。

C. 系統級線程和用戶級線程的切換都需要內核支持。

D. 同一進程中的各個線程擁有各自不同的地址空間。

32．下列選項中，不能改善磁盤設備I/O性能的是：

A. 重排I/O請求次序

B. 在一個磁盤上設置多個分區

C. 預讀和滯后寫

D. 優化文件物理的分布

33．在TCP/IP體系結構中，直接為ICMP提供服務協議的是：

A. PPP

B. IP

C. UDP

D. TCP

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

A. 機械特性

B. 功能特性

C. 過程特性

D. 電氣特性

38．ARP協議的功能是：

A. 根據IP地址查詢MAC地址

B. 根據MAC地址查詢IP地址

C. 根據域名查詢IP地址

D. 根據IP地址查詢域名

39．某主機的IP為180.80.77.55，子網掩碼為255.255.252.0，若該主機向其所在子網發送廣播分組，則目的地址為：

A. 180.80.76.0

B. 180.80.76.255

C. 180.80.77.255

D. 180.80.79.255

二、綜合應用題：41~47小題，共70分。

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

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

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

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

（1）假設索引表區僅采用直接索引結構，索引表區存放文件占多少字節？可支持的單個文件比較大長度是多少字節？

（2）假設索引表區采用如下結構：0——7字節采用<起始塊號，塊數>格式表示文件創建時預分配的連續存儲空間，其中起始塊號占6B，塊數2B，剩余504字節采用直接索引結構，一個索引占6B，則可支持單個文件比較大長度是多少個字節？為了使單個文件的長度達到比較大，請指出起始塊號和塊數分別所占字節數的合理值并說明理由。