合并有序链表O(m+n)时间复杂度

在数据结构试卷A1中，我们遇到了几个关键知识点： 1. **链表合并**： 题目要求将两个已知的递增有序单链表A和B合并成一个新的递增有序链表，且要求辅助空间为O(1)。这通常可以通过双指针法来实现，首先让两个链表的头节点进行比较，较小的节点添加到新链表中，然后移动较小节点的指针指向下一个元素，重复此过程直到任一链表遍历完毕。这样，时间复杂度为O(m+n)，其中m和n分别为链表A和B的长度。 2. **时间复杂度**： 快速排序的平均时间复杂度为O(nlogn)。这是因为在每次划分过程中，平均情况下都能将数组分为大小接近的两部分，递归操作的次数接近于logn，而内部的操作次数接近于n。 3. **堆性质**： 对于一个包含9个元素的最小堆，由于最小堆的性质，根节点A[3]的左边有两个元素(A[0]和A[1])一定比它小，右边有1个元素(A[7])可能小于也可能大于根，但题目没有指定具体数量，所以可能是2个大于根的元素。 4. **数据结构特性**： - 广义表的长度是指括号的个数，这里长度为4，深度是嵌套层数，也为4。 - 折半查找的特性表明，对于有序表，查找第k个元素最多需要比较log2(n+1)次，所以找到需要4次比较的元素个数为2^3-1=7个，但题目提到是10个元素，所以可能是3个元素。 5. **栈的管理**： 当两个栈共享存储区时，栈满的条件是当其中一个栈的顶部指针加1等于另一个栈的顶部指针（top[0]+1=top[1]），或者两个指针重叠（top[0]=top[1]+1）。 6. **递归调用树**： 函数Fib(5)的递归调用树高度为4，因为存在Fib(4)和Fib(3)两次递归调用，每个递归调用一层，总共4层。 7. **完全二叉树编号规则**： 在完全二叉树中，编号为i的节点的左子节点编号为2*i+1。 8. **森林和二叉树的关系**： 子女-兄弟链表表示的森林中，第三棵树的根结点在二叉树中对应的是p->rightchild->rightchild，因为每增加一个树，就需要向右子树移动。 选择题部分未给出选项，这部分主要考察对概念的理解和应用，涉及到的数据结构和算法细节。整体来看，这道试题涵盖了链表、排序、堆、广义表、查找算法、栈、递归、二叉树以及森林等核心数据结构和算法的概念，对学生的理解能力和实践能力有一定的测试。