南京大学数据结构试卷详解：填空与选择题详解

南京大学《数据结构》试卷是一份包含数据结构基础知识和实践应用的习题集，主要涵盖了C++语言中的数组存储、链表操作、排序算法、堆与优先队列、广义表、查找算法、栈与队列、递归调用、二叉树与森林的表示等核心知识点。 1. 数组存储：题目要求计算二维数组A的最后一个数据元素地址，C++中数组通常连续存储，因此地址计算基于起始地址和数组大小。这里提到的是按行优先存储，对于A[20][30]，元素占2个字节，所以地址计算公式是2140 + 2*(30*20-1) = 3338。 2. 链表合并：归并两个递增有序的链表A和B，要求辅助空间为常量级O(1)，这意味着不能额外分配新的内存。时间复杂度为O(m+n)，因为需要遍历两个链表，合并的过程线性完成。 3. 快速排序：快速排序是一种高效的排序算法，平均情况下，它的平均时间复杂度是O(nlogn)，这是因为它通过分治策略实现了元素的平均分布。 4. 堆与优先队列：题目中提及了最小堆的性质，一个包含9个元素的最小堆中，除了根节点，有两个较小的元素（A[0]和A[1]），有四个较大的元素（A[3]至A[7]），还有两个最大的元素（A[7]和A[8]）。 5. 广义表：给出了一个复杂结构的广义表，包括嵌套列表。它的长度是4（元素数量），深度也是4（表示嵌套层次）。 6. 查找算法：对于有序表，折半查找法能快速定位元素。如果要找到至少需要比较4次才能确定的元素，意味着它可能处于中间位置，因此是5个元素中的第三个或第四个，即3个元素。 7. 栈与队列：共享一维数组表示的双端栈中，栈满的条件是top[0]和top[1]相邻，即top[0]+1=top[1]或top[0]=top[1]+1。 8. 递归调用：计算Fibonacci数列的递归函数Fib(5)时，会产生4次递归调用，因为Fib(5)会分别调用Fib(4)和Fib(3)，而Fib(4)又会调用Fib(3)和Fib(2)，以此类推，直到n=1或n=0。 9. 二叉树：在完全二叉树中，节点编号遵循特定规则，编号为i的节点的左子节点编号为2*i+1。 10. 森林与二叉树：用子女—兄弟链表表示森林，找到第三棵树的根结点在二叉树中的对应结点，需要从根结点p开始，依次右子节点的右子节点，即p->rightchild->rightchild。 选择题部分同样包含了对数据结构基本概念的考察，如链表操作、排序算法的理解、以及二叉树和森林结构的深入理解。 这份试卷提供了丰富的实例和理论测试，适合学习者复习和巩固数据结构课程中的关键知识点。