2012 年全国硕士研究生入学统一考试计算机专业基础综合试题2012 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码 408）12012 年全国硕士研究生入学统一考试计算机专业基础综合试题一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1求整数 n(n0)阶乘的算法如下，其时间复杂度是int fact(int n)if (n=1)return 1;return n*fact(n-1);A. O(log2n)B. O(n)C. (nlog2n)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. 10B. 20C. 32D. 335对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是A. O(n)B. O(e)C. O(n+e)D. O(n*e)6若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是A. 存在，且唯一C. 存在，可能不唯一B. 存在，且不唯一D. 无法确定是否存在7对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是22012 年全国硕士研究生入学统一考试计算机专业基础综合试题A.d,e,fB.e,d,fC. f,d,eD.f,e,d8下列关于最小生成树的说法中，正确的是I. 最小生成树树的代价唯一II. 权值最小的边一定会出现在所有的最小生成树中III. 用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV. 普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A. 仅 IB. 仅 IIC. 仅 I、IIID. 仅 II、IV9设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是A. 60B. 60, 62C. 62, 65D. 6510在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是I. 简单选择排序II. 希尔排序III. 快速排序IV 堆排序V. 二路归并排序A. 仅 I、III、IVC. 仅 II、III、IVB. 仅 I、III、VD. 仅 III、IV、V11对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是A. 排序的总趟数C. 使用辅助空间的数量B. 元素的移动次数D. 元素之间的比较次数12假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是A. 55 秒B. 60 秒C. 65 秒D. 70 秒13假定编译器规定 int 和 short 类型长度占 32 位和 16 位，执行下列 C 语言语句unsigned short x = 65530;unsigned int y = x;得到 y 的机器数为32012 年全国硕士研究生入学统一考试计算机专业基础综合试题A. 0000 7FFAB. 0000 FFFAC. FFFF 7FFAD. FFFF FFFA14float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是A. 2126-2103B. 2127-2104C. 2127-2103D.2128-210415某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下：structint a;char b;short c; record;record.a=273;若 record 变量的首地址为 0Xc008，则低至 0Xc008 中内容及 record.c 的地址分别为A. 0x00、0xC00DC. 0x11、0xC00DB. 0x00、0xC00ED. 0x11、0xC00E16下列关于闪存（Flash Memory）的叙述中，错误的是A. 信息可读可写，并且读、写速度一样快B. 存储元由 MOS 管组成，是一种半导体存储器C. 掉电后信息不丢失，是一种非易失性存储器D. 采用随机访问方式，可替代计算机外部存储器17假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法。当访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是A. 1B. 2C. 3D. 418某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有A. 5 位B. 6 位C.15 位D. 33 位19某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传送一次地址或者数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是A. 20nsB. 40nsC. 50nsD. 80ns20下列关于 USB 总线特性的描述中，错误的是42012 年全国硕士研究生入学统一考试计算机专业基础综合试题A. 可实现外设的即插即用和热拔插B. 可通过级联方式连接多台外设C. 是一种通信总线，连接不同外设D. 同时可传输 2 位数据，数据传输率高21下列选项中，在 I/O 总线的数据线上传输的信息包括I. I/O 接口中的命令字II. I/O 接口中的状态字III.中断类型号A. 仅 I、IIB. 仅 I、IIIC. 仅 II、IIID. I、II、III22响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括I. 关中断II.保存通用寄存器的内容III.形成中断服务程序入口地址并送 PCA. 仅 I、IIB. 仅 I、IIIC. 仅 II、IIID. I、II、III23下列选项中，不可能在用户态发生的事件是A. 系统调用B. 外部中断C. 进程切换D. 缺页24中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是A. 程序计数器C. 通用数据寄存器25下列关于虚拟存储器的叙述中，正确的是A. 虚拟存储只能基于连续分配技术C. 虚拟存储容量只受外存容量的限制B. 程序状态字寄存器D. 通用地址寄存器B. 虚拟存储只能基于非连续分配技术D. 虚拟存储容量只受内存容量的限制26操作系的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序是A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序27假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3，这些资源总数分别为 18、6、22。T0 时刻的资源分配情况如下表所示，此时存在的一个安全序列是52012 年全国硕士研究生入学统一考试计算机专业基础综合试题进程P0P1P2P3P4R134423已分配资源R220001R333544R155444资源最大需求R253022R31061154A. P0, P2, P4, P1, P3C. P2，P1，P0，P3，P4B. P1, P0, P3, P4, P2D. P3, P4, P2, P1, P028若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是I.