2014年考研计算机统考408真题版.doc

【知识点详解】 1. 时间复杂度分析：第一题考察了时间复杂度的计算。程序段中的两个嵌套循环，外层循环是以2为底的指数增长，内层循环是线性的，因此总的时间复杂度是O(nlog2n)。 2. 中缀表达式转后缀表达式：第二题涉及到中缀表达式转换为后缀表达式的过程，栈在其中起着关键作用。当扫描到'f'时，栈中元素应保留运算符，按照运算符优先级，'f'前应有'*'和'-'，因此正确答案是D。 3. 循环队列：第三题考察循环队列的队空和队满条件。队空条件是头尾指针相等，队满条件是加入一个元素后头尾指针相等，考虑到模M操作，所以正确答案是B。 4. 二叉树线索化：第四题中，中序线索化二叉树的线索指向的是其前驱或后继节点。根据中序遍历规则，x的左线索指向的应该是其左子节点，没有左子节点时指向其前驱；右线索指向的应该是其右子节点，没有右子节点时指向其后继。根据题目描述，x的左线索指向e，右线索指向a。 5. 森林转化为二叉树：第五题提到，森林F转化为对应的二叉树T，F中的叶子个数等于T中度为1的结点个数，因为每个叶结点在转化后会成为度为1的结点的左孩子。 6. 前缀编码：第六题中，前缀编码是指没有一个编码是另一个编码的前缀，选项C的编码"000"是"0"的前缀，所以不是前缀编码。 7. 拓扑排序：第七题中，拓扑排序是对有向无环图(DAG)进行排序的一种方法。给出的拓扑序列必须满足无环条件，A和C两个选项中，5指向6，不能出现在6之前，因此排除。 8. 散列冲突处理：第八题中，堆积（聚焦）现象会导致冲突增多，影响到查找效率，即平均查找长度。 9. B树结构：第九题中，4阶B树的最大关键字个数在非叶结点中是4，叶结点中是5，所以15个关键字的4阶B树最多有6个含关键字的结点。 10. 希尔排序增量选择：第十题中，希尔排序的增量序列应逐渐减小，第一趟排序后序列间隔较大，所以可能的增量是5。 11. 快速排序结果：第十一题中，快速排序每次划分后，数组分为两部分，一部分的所有元素都比另一部分的小。选项D中序列已经有序，不符合快速排序的特点。 12. CPU执行时间：第十二题中，执行时间的变化与指令数和CPI(Cycles Per Instruction)有关。根据给定条件，执行时间变为原时间的70% * 1.2=84%，即14秒。 13. 定点补码运算溢出：第十三题中，溢出发生在加法和减法运算中，当结果超出数据类型表示范围时。x+y不会溢出，–x+y可能会溢出，因为x+y的结果可能是负数，再加负号可能会超出范围。 14. 浮点数比较：第十四题中，IEEE754单精度浮点格式比较，通过比较其二进制表示的值和符号位，可以确定x<y且符号相同。 15. DRAM芯片引脚数：第十五题中，256MB的存储器由4M*8位的DRAM组成，每块4M对应2^22地址，加上8位数据线，总共需要22根地址线和8根数据线，总引脚数为22+8=30。 16. 指令Cache与数据Cache分离：第十六题中，这样做的主要目的是减少指令流水线资源冲突，提高处理器性能。 17. 寻址方式：第十七题中，Store指令的偏移量使用补码表示，32位定长指令，8位操作码，因此剩余24位用于寻址，补码表示的范围是-2^23到2^23-1，即-8388608到8388607。 18. 微程序控制器：第十八题涉及微程序控制器的细节，但具体内容不全，无法提供详细解答。 以上是对2014年考研计算机统考408真题部分题目的解析，涵盖了算法、数据结构、操作系统、计算机组成原理等多个方面的知识点。