北航自主招生：数据结构基础试题详解

北航自主招生考试题目包含了数据结构这一核心主题，旨在考察考生对基础理论的理解和应用能力。以下是部分试题及其知识点解析： **第一部分：数据结构** **1. 算法分析的目的**： 算法分析的目标在于评估算法的效率，包括时间复杂度和空间复杂度，以便优化设计、选择更高效的算法，提高程序执行效率。 **2. 链表的空间需求**： 虽然双向链表相较于单向链表可以双向访问，但并不意味着它一定占用更多空间，因为这取决于具体实现。在某些情况下，单向链表可能更节省空间，因为没有额外的指针指向前一个节点。 **3. 堆栈与线性表**： 堆栈是一种特殊的线性表，只允许在一端进行插入和删除，这种特性使得堆栈常用于后进先出（LIFO）的数据结构。 **4. 完全二叉树与满二叉树**： 完全二叉树是每一层节点都被完全填充，且除了最后一层外，最右边的节点都靠左对齐。满二叉树则是所有层级都有最大节点数，但不一定是最底层全部填满，所以完全二叉树是满二叉树的特殊情况。 **5. 二叉树遍历序列**： 前序遍历和后序遍历虽然可以重建二叉树，但不是唯一方法，还需要额外的信息，如中序遍历或层次遍历。 **6. 图的性质**： 邻接表中边结点数为偶数的图并不一定无向，因为无向图中每条边会在两个节点的邻接表中各出现一次，但总数可能是偶数。 **7. 拓扑排序**： 拓扑排序是检测有向无环图（DAG）中节点依赖关系的方法，但它不是检测有向图中存在环路的唯一方法，因为存在环路的情况下无法进行拓扑排序。 **8. 折半查找条件**： 折半查找适用于已经排序的线性表，但不一定是最高效的选择，如查找的范围很大时，哈希表或其他查找算法可能更快。 **9. 插入排序趟数**： 对于n个元素的序列，插入排序的最坏情况（逆序）下需要进行n(n-1)/2次比较，平均情况是n²/2，最好的情况是已经排序，只需进行n-1次。 **10. 快速排序效率**： 快速排序在一般情况下效率较高，但不是总是最优解，如处理近乎有序的数据时，插入排序可能更有效。 **第二部分：具体问题解答** - 顺序存储结构插入新元素：需移动`i-1`个元素。 - 双向循环链表插入操作：`p->rlink=q->llink;q->llink=p;p->rlink=p->llink->rlink;`。 - 堆栈动态存储：链式堆栈，因为它能动态扩展。 - 队列输出序列：对于队列`a,b,c,d`，按照先进先出原则，输出为`d,c,b,a`。 - 二叉树指针域：对于具有n个节点的二叉树，共有n-1个非叶子节点，每个非叶子节点有两个指针，因此有n-1个`NULL`。 - 后序遍历：根据已知的前序和中序遍历，可以推断后序遍历为`DCBGFEA`。 - 二叉排序树查找比较次数：查找62时，从根节点开始，每次比较后缩小搜索范围，直到找到，共进行6次比较。 - 图中度数和边数的关系：所有顶点的度数之和等于所有边数的两倍（因为每条边贡献了两次度数）。 - 有向图边数：最多有`n*(n-1)`条边，其中n为顶点数。 - 无向连通图邻接矩阵：对于无向图，邻接矩阵是对称的，所以至少有n*(n-1)/2个非零元素。 - 折半查找：对于给定的10个连续偶数，查找12需要查找4次（第一次排除一半，剩下5-9，第二次排除中间的一半，剩下6，第三次排除一半得到8，第四次确定为8，共4次比较）。