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，则可支持单个文件比较大长度是多少个字节？为了使单个文件的长度达到比较大，请指出起始块号和块数分别所占字节数的合理值并说明理由。