北航数据结构与C语言考研真题详解及答案

本资料汇集了北京航空航天大学软件学院2008年至2010年期间多次软件工程硕士研究生入学考试的数据结构与C语言程序设计试题及答案，共计6套，旨在为报考北航软件学院的考生提供宝贵的复习参考资料。考试内容涉及数据结构理论、算法分析、C语言编程基础以及图论等多个方面。 **数据结构部分** 1. **时间复杂度**：O(1)表示算法在最坏、最好或平均情况下执行时间与问题规模n无关，例如在数组中查找特定值的索引操作，无论数组大小如何，查找时间都是常数。 2. **堆栈序列**：当5个元素A、B、C、D、E入栈后，出栈序列中第一个元素为C且第二个元素为D的情况不唯一，可能的序列是C-B-E-D 或 C-E-D-B，因为堆栈遵循先进后出的原则。 3. **满二叉树叶结点**：非空满二叉树的叶结点数等于其高度加1。例如，对于高度为h的满二叉树，叶节点数为2^(h+1)-1。 4. **有向图拓扑排序**：给定图G的顶点和弧，拓扑序列的构建依赖于每个顶点的入度。G的拓扑序列为v1, v3, v4, v2, v5，因为v1的入度为0，可以先出队，后续节点的出队需满足入度为0。 5. **查找算法效率**：折半查找法在有序数组中效率较高，但并非总比顺序查找快，这取决于具体条件，如数组是否有序，数据分布等。在无序情况下，顺序查找可能更快。 **C语言与算法部分** 1. **影响算法效率的因素**：主要包括问题规模、数据组织、算法复杂度（如时间复杂度和空间复杂度）、计算机硬件特性等，其中算法本身的选择和优化至关重要。 2. **递归算法功能**：给出的递归函数`ALGORISM`用于计算单链表的节点数，返回链表的长度。 3. **二叉排序树构建**：题目要求根据字符的字典序构建二叉排序树，首先比较首字母，将“Nov”作为根，然后依次插入其余元素，构建一颗有序的二叉树。 4. **无向图边数**：无向图中任意两个不同顶点之间最多有一条边，推导过程是考虑每一对不同的顶点之间恰好有一条边，因此最多有C(n,2) = n*(n-1)/2条边。 5. **堆积排序**：堆积排序的第一趟从序列的最后一个元素开始，将其与第一个元素进行比较，如果第一个元素小于新元素，则交换位置，然后继续处理剩余元素，直至形成一个最小堆。 这些题目涵盖了数据结构的基础概念、递归算法的理解、排序算法的应用以及图论的基本理论，对备考者来说具有较高的参考价值。通过解答这些问题，考生可以检验自己的理论知识掌握程度，并提升实际编程能力。