"2013年计算机考研专业综合真题及答案一览"

根据给出的题目内容，总结如下： 题目1：已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是？ 题目2：一个栈的入栈序列为 1,2,3,...,n，其出栈序列是 123,...,npppp。若 23p，则 3p 可能取值的个数是？ 题目3：若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是？ 题目4：已知三叉树 T 中有 6 个叶子节点，且有一个节点的度数为 3，其余节点的度数均为 2，则 T 中的节点个数是？ 根据以上题目内容，我们可以进行如下的总结和分析。 题目1要求合并两个升序链表，并将它们合并为一个降序链表。注意题目中提到的关键词是“最坏情况下的时间复杂度”。根据题目所给的信息，可以使用归并排序的方式进行链表合并，时间复杂度为O(m+n)。答案选项C. (min(m,n))O(m+n) 符合要求。 题目2描述了一个栈的入栈和出栈操作，问题是根据已知的出栈序列找到可能的入栈序列。已知 23p，可以确定栈中的顶部元素是3，也就是说，当3作为栈顶元素时，p的取值有多少种可能。由于栈的特性先进后出，可以推断出前面的元素都比3大，所以3p的取值个数就是n-3+1=n-2。答案选项A.3n 符合要求。 题目3涉及到平衡二叉树的插入和平衡因子的计算。根据题目所给的关键字依次插入到空的平衡二叉树中，得到的树为AVL树。平衡二叉树的平衡因子定义为左子树的高度减去右子树的高度，因此只有当左右子树的高度相等时，分支节点的平衡因子才为0。按照所给的关键字插入，可以得到一个平衡二叉树，其中2和6的左右子树都为空，所以平衡因子为0的分支节点个数为2。答案选项B.1 符合要求。 题目4描述了一个三叉树的节点情况，已知有6个叶子节点和一个度数为3的节点。根据树的性质，叶子节点的度数为0，所以三叉树中除了叶子节点外，还需要一个根节点和一个度数为3的节点。又根据节点度数与边的关系，可以得出节点个数=边数+1，而边数=叶子节点数+分支节点数*度数。带入已知条件，可以得到叶子节点数+1+1=6+度数，解方程可以得到分支节点数=5/度数=5/3。答案选项是D.5/3，但此选项不是整数，所以无法确定。 综上所述，根据题目要求总结出的答案如下： 1. 题目1的最坏情况下的时间复杂度是C. (min(m,n))O(m+n)。 2. 题目2中3p的取值个数是A. 3n。 3. 题目3中平衡因子为0的分支节点个数是B. 1。 4. 题目4中无法确定节点个数。