[专业课]2012年计算机科学专业基础综合试题

《[专业课]2012年计算机科学专业基础综合试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012年计算机科学专业基础综合试题一、单项选择题：1～40小题，每小题2分，共80分。在每题给出的四个选项中，只有一个选项最符合试题要求。1．求整数n（n>=0）阶乘的算法如下，其时间复杂度：Intfact（intn）{if（n<=1）return1；returnn*fact（n-1）；}A.O(log2n)B.O(n）C.(alog2n)D.O(n2)2．已知操作符包括‘+’，‘-’，‘*’，‘/’，‘（’和‘）’，将中缀表达式a+b-a*((c+d)/e-f)+g转化为等价的后缀表达式ab+acd+e

2、/f-*-g+时，用栈来存放暂时还不能确定的运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是：A.5B.7C.8D.113．若一棵二叉树的前序遍历序列为a、e、b、d、c，后序遍历序列为b、c、d、e、a，则根结点的孩子结点：A.只有eB.有e、bC.有e、cD.无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为：A.10B.20C.32D.335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是：A

3、.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

4、.重排I/O请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理的分布33．在TCP/IP体系结构中，直接为ICMP提供服务协议的是：A.PPPB.IPC.UDPD.TCP34．在物理层接口特性中用于描述完成每种功能的事件发生顺序的是：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

5、.0，若该主机向其所在子网发送广播分组，则目的地址为：A.180.80.76.0B.180.80.76.255C.180.80.77.255D.180.80.79.255二、综合应用题：41~47小题，共70分。41．设有6个有序表ABCDEF分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列，要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小，请回答：（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并过程，描述n（n≥2

6、）个不等长升序表的合并策略，并说明理由。46．某文件系统空间的最大容量为4TB，（1T=240），以磁盘块为基本分配单位，磁盘块大小为1KB，文件控制块（FCB）包含一个512B的索引表区。请回答：（1）假设索引表区仅采用直接索引结构，索引表区存放文件占多少字节？可支持的单个文件最大长度是多少字节？（2）假设索引表区采用如下结构：0——7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数2B，剩余504字节采用直接索引结构，一个索引占6B，则可支持单个文件最大长度是多

7、少个字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。