发帖
雷达卡
2014年全国硕士研究生入学统一考试计算机学科专业基础综合试题精选解析
以下程序段的时间复杂度为（ ）。
count =0;
for(k = 1; k <= n; k *= 2)
for(j = 1; j <= n; j++)
count++;A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n)
考虑一个初始为空的栈，将中缀表达式 a/b+(c*d*e*f)/g 转换为其等价的后缀表达式。在扫描到字符 f 时，栈内当前所包含的元素依次是（ ）。
A. +(–
B. +(*
C. /+(*
D. /+
设循环队列存储于一维数组 A[0..M-1] 中，其中 end1 指向队头元素，end2 指向队尾元素的下一个位置。允许在两端进行入队和出队操作，队列最多容纳 M-1 个元素，初始状态为空。下列关于队空与队满的判断条件中，正确的是（ ）。
A. 队空：end1 == end2；队满：end1 == (end2 + 1) mod M
B. 队空：end1 == end2；队满：end2 == (end1 + 1) mod (M - 1)
C. 队空：end1 == (end1 + 1) mod M；队满：end1 == (end2 + 1) mod M
D. 队空：end1 == (end2 + 1) mod M；队满：end2 == (end1 + 1) mod (M - 1)
将森林 F 转换为其对应的二叉树 T，则 F 中叶子节点的数量等于（ ）。
A. T 中叶结点的个数
B. T 中度为 1 的结点个数
C. T 中左孩子指针为空的结点个数
D. T 中右孩子指针为空的结点个数
对于 5 个字符的四种编码方案，其中不属于前缀编码的是（ ）。
A. 01, 0000, 0001, 001, 1
B. 011, 000, 001, 010, 1
C. 000, 001, 010, 011, 100
D. 0, 100, 110, 1110, 1100
使用哈希（散列）方法处理冲突时可能产生堆积（聚集）现象。下列选项中，直接受该现象影响的是（ ）。
A. 存储效率
B. 散列函数
C. 装填（装载）因子
D. 平均查找长度
在一棵含有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多可达（ ）。
A. 5
B. 6
C. 10
D. 15
采用希尔排序对某一数据序列进行排序，若第一趟排序结果为：9, 1, 4, 13, 7, 8, 20, 23, 15，则该趟所使用的增量（间隔）可能是（ ）。
A. 2
B. 3
C. 4
D. 5
下列选项中，不可能是快速排序执行至第二趟后的排序结果的是（ ）。
A. 2, 3, 5, 4, 6, 7, 9
B. 2, 7, 5, 6, 4, 3, 9
C. 3, 2, 5, 4, 7, 6, 9
D. 4, 2, 3, 5, 7, 6, 9
某程序 P 在机器 M 上的执行时间为 20 秒。经编译优化后，其执行的指令条数减少为原来的 70%，而 CPI 增加为原来的 1.2 倍。则优化后 P 在 M 上的执行时间变为（ ）。
A. 8.4 秒
B. 11.7 秒
C. 14 秒
D. 16.8 秒
若 x = 103，y = -25，在采用 8 位定点补码进行运算时，下列哪个表达式会发生溢出？（ ）
A. x + y
B. -x + y
C. x - y
D. -x - y
float 类型数据通常以 IEEE 754 单精度浮点格式表示。假设两个 float 变量 x 和 y 分别存放在 32 位寄存器 f1 和 f2 中，且 (f1) = CC90 0000H，(f2) = B0C0 0000H，则 x 与 y 的关系为（ ）。
A. x < y 且符号相同
B. x < y 且符号不同
C. x > y 且符号相同
D. x > y 且符号不同
某容量为 256MB 的存储器由若干片 4M×8 位的 DRAM 芯片构成，则每片 DRAM 芯片的地址引脚与数据引脚总数为（ ）。
A. 19
B. 22
C. 30
D. 36
将指令 Cache 与数据 Cache 分离的主要目的是（ ）。
A. 降低 Cache 缺失损失
B. 提高 Cache 命中率
C. 降低 CPU 平均访存时间
D. 减少指令流水线中的资源冲突
京公网安备 11010802022788号
