2011计算机考研基础题详解：时间复杂度、栈与队列操作及二叉树叶子节点计算

2011年的计算机专业基础综合考研试题涵盖了时间复杂度分析、数据结构中的栈与队列操作以及完全二叉树的性质。以下是对这些知识点的详细解析： 1. **时间复杂度分析**: 题目要求分析一个循环结构的时间复杂度，其中 `x` 的值通过 `while` 循环不断翻倍，直到达到 `n/2`。这个过程可以用对数函数表示，因为每次循环都将问题规模缩小一半。因此，当 `x` 达到 `n/2` 时，循环将执行大约 `log2(n)` 次，所以时间复杂度为 O(log2n)。答案选项A正确。 2. **栈的出栈序列**: 当元素a、b、c、d和e依次入栈时，要求d开头的出栈序列。由于d必须先于其他元素出栈，且栈遵循先进后出的原则，a、b和c必须按照abc的顺序出栈。这样，剩下的元素e就有四种可能的位置，即在d之后的位置，分别是第1、2、3或4位，对应于序列dceba、dcbae、dcbae和dcabe。因此，共有4种不同的出栈序列，答案选项B正确。 3. **循环队列初始化**: 循环队列在数组A中实现，若队列非空，front和rear分别指向前驱和后继元素。初始为空时，队头（front）应指向数组的第一个元素（即A[0]），而队尾（rear）应指向数组的最后一个元素（即A[n-1]），因为第一个元素即将被添加。因此，初始时front和rear的值分别为0和n-1，答案选项B正确。 4. **完全二叉树叶子节点**: 在完全二叉树中，除了最后一层外，每一层的节点都是满的，并且最后一层的所有节点都在左边。对于n个节点的完全二叉树，如果它是满的，则叶子节点（没有子节点的节点）数等于n/2。如果最后一层不满，叶子节点数等于满二叉树叶子节点数减去最后一层剩余节点数。题目给出有768个节点，我们可以计算叶子节点数，但由于题目未说明是否满二叉树，我们只能假设它是最少的叶子节点数，即768/2=384个。答案选项C正确。 总结起来，这四个题目考察了考生对算法分析、数据结构（栈和队列）操作的理解，以及完全二叉树的基本性质，这些都是计算机科学基础中的核心内容，对于考研备考者来说非常重要。