北航2011硕士研究生入学：数据结构与C语言试题详解

本资源提供了2011年中国北京航空航天大学硕士研究生入学考试“数据结构与C语言程序设计”（科目代码：991）的试题及部分答案。这部分内容主要考察了以下几个知识点： 1. **线性表的存储结构**： - 顺序存储结构的特点：A选项指出顺序存储结构隐含地存储了数据元素之间的逻辑关系，这是正确的。顺序存储要求连续的内存空间，B选项正确。 - 链式存储结构：C选项描述了链式存储结构通过指针表示逻辑关系，这也是链表的主要特性。 - 链式存储空间分布：D选项提到链式存储空间不一定是连续的，这是链表的常见特性。 2. **队列操作**： - 队列插入操作：题目中的队列插入过程涉及到队头（front）和队尾（rear）指针，正确操作应是将新元素指向队尾，然后更新队尾指针，C选项`rear->link=p; rear=p;`是正确的。 3. **二叉树特征**： - A选项提到二叉树的度可以小于2，这是正确的，因为每个节点最多只有两个子节点。 - C选项指出至少有一个节点度为2，但没有强制规定所有节点都必须如此，所以不是强制条件。 4. **图论概念**： - 有向图的邻接矩阵：如果主对角线以下元素全为0，意味着图中不存在自环，但不保证唯一拓扑序，B选项“存在但可能不惟一”正确。 5. **网络图（AOE）**： - AOE网是带权的有向图，但不一定是强连通或无回路的，D选项更准确。 6. **查找算法**： - 顺序查找适用于顺序和链式存储，A正确；顺序查找不一定能找到首次出现元素，B错误，D正确。 - 折半查找对于相同元素，不一定能查找到首次出现，因为可能在中间部分查找，C错误。 7. **二叉排序树查找效率**： - 查找效率与二叉树的深度有关，A正确。 8. **排序算法特性**： - 插入排序、快速排序、堆排序在每趟排序后不能保证确定元素最终位置，A正确。 - 二路归并排序是稳定的，且在元素已有序的情况下，排序效率高，但不保证每趟确定位置，B、C、D错误。 通过这份试题，考生需要熟悉数据结构的基础理论，如线性表、队列、二叉树、图论和排序算法，并能应用到实际问题中。解答这些问题有助于评估考生在数据结构和C语言编程方面的理论知识和实践能力。