北航2011年991数据结构与C语言考研真题及解析

"2011年北航研究生入学考试数据结构与C语言程序设计991科目的真题及答案，涵盖了数据结构和C语言的相关知识点，包括线性表的存储结构、队列操作、二叉树性质、图的邻接矩阵、AOE网、线性表查找方法以及排序算法等核心概念。" 1. **线性表的存储结构**：线性表的顺序存储结构意味着数据元素存储在一块连续的内存区域，逻辑顺序与物理顺序一致，而链式存储结构通过指针链接元素，存储空间不一定要连续。 2. **队列操作**：向链接队列中插入元素通常涉及更新队尾指针，选项C（rear->link=p; rear=p;）描述了这个过程，将新元素p链接到队尾，并更新队尾指针。 3. **二叉树的概念**：二叉树的度是指其最大孩子数，可以小于2，因此A和B不正确；二叉树中至少有一个节点的度可以是2，C选项正确；D选项错误，因为不是所有节点的度都必须为2。 4. **二叉树的叶节点与总节点数**：一棵二叉树如果有40个叶节点，根据满二叉树的性质，它的节点总数最少是79个（第n层满二叉树的叶子数为2^(n-1)，当n=6时，2^5=32，加上根节点，总共33个非叶节点，加上40个叶节点是73，再加上第7层的一个节点即为79）。 5. **有向图的拓扑序列**：邻接矩阵主对角线以下元素为0表示没有环，因此图是无环的，有向无环图(DAG)的拓扑排序可能存在多个不同的序列，答案是B。 6. **AOE网**：AOE网是活动-on-edge网络，代表带权的有向无环图，用于项目计划调度，C选项正确。 7. **线性表查找**：顺序查找适用于任何线性结构，但不一定能找到首次出现的元素；折半查找在有序表中适用，但不一定能找到首次出现的元素，D选项正确。 8. **二叉排序树**：在二叉排序树中查找的效率与树的深度密切相关，A选项正确。 9. **排序算法**：插入排序、快速排序和堆积排序在每趟排序后都能确定部分元素的位置，但二路归并排序不能，因为它是稳定的排序，可能需要多趟合并。 10. **排序算法效率**：如果序列已有序，插入排序的时间复杂度为O(n)，快速排序和堆积排序平均性能仍然优于冒泡排序，但冒泡排序在最好情况下（已排序）的时间复杂度为O(n)。 这些知识点展示了数据结构和算法的基础，对于理解和解决相关问题至关重要。通过深入学习这些内容，可以提升编程能力，特别是在处理复杂数据组织和优化算法效率时。