2012年计算机科学专业基础综合试题.doc

2012年计算机科学专业基础综合试题一、单项选择题：140小题，每小题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. 5B. 7C. 8D. 113 若一棵二叉树的前序遍历序列为a、e、b、d、c，后序遍历序列为b、c、d、e、a，则根结点的孩子结点：A. 只有eB. 有e、bC. 有e、cD. 无法确定 4若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为 ：A. 10 B. 20C. 32D. 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. PPPB. IPC. UDPD. TCP 34在物理层接口特性中用于描述完成每种功能的事件发生顺序的是：A. 机械特性B. 功能特性C. 过程特性D. 电气特性 38ARP协议的功能是：A. 根据IP地址查询MAC地址B. 根据MAC地址查询IP地址C. 根据域名查询IP地址D. 根据IP地址查询域名 39某主机的IP为180.80.77.55，子网掩码为255.255.252.0，若该主机向其所在子网发送广播分组，则目的地址为：A. 180.80.76.0B. 180.80.76.255C. 180.80.77.255D. 180.80.79.255 二、综合应用题：4147小题，共70分。41设有6个有序表ABCDEF分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列，要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小，请回答：（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并过程，描述n（n2）个不等长升序表的合并策略，并说明理由。46某文件系统空间的最大容量为4TB，（1T=240），以磁盘块为基本分配单位，磁盘块大小为1KB，文件控制块（FCB）包含一个512B的索引表区。请回答：（1）假设索引表区仅采用直接索引结构，索引表区存放文件占多少字节？可支持的单个文件最大长度是多少字节？（2）假设索引表区采用如下结构：07字节采用格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数2B，剩余504字节采用直接索引结构，一个索引占6B，则可支持单个文件最大长度是多少个字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。