【计算机科学与技术学科联考真题解析】
1. 时间复杂度分析：
程序片段 `while(x<n/2) x=2*x;` 实现了每次循环都将 `x` 乘以2，直到 `x >= n/2`。初始 `x=2`，每次循环后 `x` 翻倍，所以这个循环会执行 log2(n/2) 次，即 log2n - log22 = log2n - 1 次。因此，时间复杂度为 O(log2n)。
2. 栈的操作与序列生成：
元素 a, b, c, d, e 进栈后，每个元素都可以停留或出栈，直到所有元素都出栈。对于以 d 开头的序列，d 必须是第一个出栈的元素，a 和 b 可以先出栈，然后 c 再出栈，或者 b 先出栈，a 和 c 出栈，d 才出栈。有以下几种情况：d, b, c, a, e；d, a, c, b, e；d, b, a, c, e。如果 a 先出栈，b 可以在 a 之后立即出栈，或者在 c 出栈后再出栈，这样 d, a, b, c, e 也是可能的序列。所以共有4种以 d 开头的出栈序列。
3. 循环队列的初始化：
循环队列存储在一维数组 A[0... n-1] 中，非空时 front 和 rear 分别指向队头和队尾。初始为空时，front 和 rear 应该都指向数组的第一个元素，即 front 和 rear 的值分别是 0, 0。
4. 完全二叉树的叶节点数量：
完全二叉树的叶节点数与总节点数的关系可通过公式 N0 = N / 2 + N / 4 + ... 推导得出，其中 N0 是叶节点数，N 是总节点数。当 N 为2的幂时，公式简化为 N0 = N / 2。所以有 768 / 2 = 384 个叶节点。
5. 二叉树遍历序列：
前序遍历为 1, 2, 3, 4，后序遍历为 4, 3, 2, 1，说明 1 是根节点，2 和 3 是左子树，4 是右子树。在中序遍历中，根节点左侧是左子树，右侧是右子树。因此，2, 3, 4 应该出现在 1 之后，不可能出现 4, 3, 2, 1 这样的中序遍历序列。
6. 树与二叉树的对应关系：
已知一棵有 2011 个结点的树，叶结点个数为 116。该树对应的二叉树中，无右孩子的结点包括所有叶结点和部分非叶结点。根据满二叉树的性质，如果 2011 个结点全部是叶结点，那么非叶结点（即内部结点）个数应该是 2010，但因为不是满二叉树，所以内部结点少于 2010。现在叶结点为 116，那么内部结点为 2011 - 116 = 1895，所以无右孩子的结点（即只有左孩子的结点）至少为 116，最多为 1895。因此，答案可能是 115 或 116，但根据题目给的选项，选择 1896。
7. 二叉排序树查找路径：
二叉排序树中查找路径的序列必须满足左子树的所有节点小于根节点，右子树的所有节点大于根节点。A、B、D选项均满足这一条件，而C选项 21, 89, 77, 29, 36, 38 的顺序意味着 21 后面是 89，但 89 大于 21，违反了二叉排序树的定义。
8. 图的特性：
I. 回路是简单路径，不一定正确，回路可以是简单路径，也可以包含重复顶点。
II. 存储稀疏图，用邻接矩阵不如邻接表节省空间，因为邻接矩阵对空边也要占用存储。
III. 若有向图存在拓扑序列，则该图不存在回路，正确。有向无环图（DAG）才可能存在拓扑排序。
9. 提高散列表查找效率：
I. 增大装填因子会导致冲突增加，降低查找效率。
II. 设计冲突少的散列函数能提高查找效率。
III. 处理冲突时避免产生聚集可以减少查找链的长度，提高效率。
10. 快速排序的存储方式：
快速排序适用于顺序存储结构，因为需要频繁地进行相邻元素的交换。
11. 大根堆的调整：
已知序列25, 13, 10, 12, 9 是大根堆，插入 18 后，需要从下往上调整，每次比较父节点和子节点。由于18小于25，需要交换，此时比较次数为1；接着18与13比较，不需要交换；然后18与10比较，也不需要交换。所以调整过程中元素之间进行的比较次数是1次。
12. 浮点数操作速度指标：
MFLOPS (Millions of Floating-point Operations Per Second) 描述浮点数运算速度。
13. IEEE 754 单精度浮点数表示：
-8.25 的二进制表示为 -1.01001001000001010…（小数点后部分）。转换成IEEE 754格式，最高位为符号位1，接下来是8位指数位，然后是23位尾数。指数部分需要加上偏置值127，得到 -127（即-127+127=0），所以指数部分是0，尾数部分是1001001000001010…，但是由于单精度浮点数尾数只有23位，所以需要截断。最后结果是 C1C2 OOOOH。
14. 非随机存取方式的存储器：
CDROM 使用只读光存储，不能随机存取。
15. 存储器地址寄存器位数：
32MB 主存储器，每个存储单元8位，所以总地址空间为 2^25 字节。因此，至少需要25位地址来寻址。
16. 偏移寻址方式：
间接寻址是通过一个地址字段间接寻址，不涉及与形式地址相加；而基址寻址、相对寻址和变址寻址都是基于某种形式地址加上偏移量得到有效地址。
17. 条件转移指令：
'hgt' 指令在无符号整数比较大于时转移，转移条件是 CF=0 且 ZF=0，即没有进位且不等于零。
18. 指令系统特点与指令流水线：
I. 规整的指令格式和长度一致利于流水线的执行。
II. 数据对齐方便多级流水线同时访问数据。
III. 只有Load/Store指令访问存储器，其他指令操作寄存器，减少访存延迟，利于流水线。
19. 中断状态下的指令执行：
不采用Cache和指令预取技术，开中断状态下，中断请求一旦发生，CPU需要停止当前指令执行，保存上下文，处理中断，再恢复上下文，继续原指令，这会影响指令执行效率。
以上是针对2011年计算机408统考真题的详细解析，涵盖了时间复杂度、数据结构（栈、队列、二叉树）、图论、散列、存储器组织、浮点数表示、寻址方式、指令系统等多个知识点。
评论0