### 北航 991 数据结构与C语言 1998~2015 真题 #### 知识点解析 ##### 一、单项选择题 **1. 递归定义的问题** 递归算法与非递归算法在时间效率上的比较： - **选项A**：“前者要比后者快”不正确。递归算法通常会因为反复调用自身而带来额外的开销（如栈空间的管理），因此在很多情况下递归实现可能比非递归实现慢。 - **选项B**：“前者要比后者慢”可能更接近实际情况，尤其是在处理大规模问题时，递归算法的调用开销可能导致其运行速度较慢。 - **选项C**：“前者与后者相同”也并不总是成立，因为具体性能取决于递归的深度以及具体的实现方式。 - **选项D**：“两者不能做比较”并不准确，因为在特定条件下，可以通过分析算法的具体实现来比较两者的性能。 **正确答案**: B **2. 线性表采用顺序存储结构的优点** 线性表采用顺序存储结构的主要优点之一： - **选项A**：“存储密度(即存储利用率)高”正确。顺序存储由于所有元素紧密相连，没有额外的空间浪费，因此存储密度较高。 - **选项B**：“适用于各种逻辑结构的存储表示”不正确，顺序存储更适合于实现线性结构，如数组。 - **选项C**：“在表中进行插入操作的时间效率高”不正确，插入操作可能需要移动大量元素。 - **选项D**：“在表中进行删除操作的时间效率高”也不正确，删除操作同样可能导致大量元素的移动。 **正确答案**: A **3. 堆栈及其操作** 堆栈采用顺序存储结构的相关描述： - **选项A**：“堆栈的大小为n”正确，这里的n指的是最大容量。 - **选项B**：“堆栈为空时n=0”不正确，n表示的是堆栈的最大容量而非当前元素数量。 - **选项C**：“最多只能进行n次进栈和出栈操作”不正确，堆栈的进出栈操作不受限制，只要不超过最大容量即可。 - **选项D**：“n个元素依次进栈后，它们的出栈顺序一定与进栈顺序相反”正确。这是堆栈后进先出(LIFO)特性的直接体现。 **正确答案**: D **4. 二叉树形态** 形态上深度为n的二叉树的数量： - **选项A** 和 **选项B** 的描述存在显示问题，无法直接判断。 - **选项C** 和 **选项D** 同样存在显示问题，但根据常识推断，对于深度为n的二叉树，形态种类应该是2^(n-1)种。 **正确答案**: C 或 D (实际应为2^(n-1)) **5. 二叉树遍历方法** 给定的二叉树遍历顺序为4,6,7,5,2,3,1，根据这个顺序判断遍历方法： - **选项A**：“前序遍历”不正确，前序遍历根节点在前。 - **选项B**：“中序遍历”正确，中序遍历左子树—根节点—右子树。 - **选项C**：“后序遍历”不正确，后序遍历左子树—右子树—根节点。 - **选项D**：“按层次遍历”不正确，按层次遍历是从左到右，从上到下。 **正确答案**: B **6. 拓扑排序** 给定无回路有向图的邻接表，判断哪个顶点序列不是拓扑序列： - **选项A**：“v1,v2,v3,v5,v4”可能是拓扑序列。 - **选项B**：“v1,v2,v3,v4,v5”可能是拓扑序列。 - **选项C**：“v2,v1,v3,v5,v4”不可能是拓扑序列，因为拓扑排序要求所有入度为0的节点首先被列出。 - **选项D**：“v2,v1,v5,v3,v4”可能是拓扑序列。 **正确答案**: C **7. 连通图的邻接矩阵** 连通图邻接矩阵中的非零元素最少数量： - **选项A**：“2(n-1)”正确，连通图至少有一棵树构成，树中有n-1条边。 - **选项B** 和 **选项C** 不正确。 - **选项D**：“n/2”不正确。 **正确答案**: A **8. 折半查找** 长度为n的有序顺序表进行折半查找，每个元素的比较次数： - **选项A**：“大于”不正确。 - **选项B**：“等于”不正确。 - **选项C**：“小于”不正确。 - **选项D**：“小于或等于”正确。折半查找的比较次数不会超过对应判定树的深度。 **正确答案**: D **9. 散列表** 散列表的平均查找长度与哪些因素有关： - **选项A**：“与m直接相关”不完全正确。 - **选项B**：“与n直接相关”不完全正确。 - **选项C**：“与α直接相关”正确，α是装填因子，是影响散列表性能的关键指标。 - **选项D**：“与m、n和α都直接相关”最全面。 **正确答案**: D **10. 排序方法** 根据排序过程判断排序方法： - **选项A**：“插入排序法”不正确，插入排序每次只移动一个元素。 - **选项B**：“选择排序法”不正确，选择排序每次移动的都是当前未排序序列中的最小元素。 - **选项C**：“冒泡排序法”正确，冒泡排序每次将相邻元素比较并交换。 - **选项D**：“快速排序法”不正确，快速排序涉及分区操作。 **正确答案**: C ##### 二、填空题 **1. 线性表存储结构** 频繁插入或删除操作，线性表宜采用**链式存储结构**。 **2. 单链表链接** 若要以O(1)的时间代价链接两个单链表，则这两个链表的尾部结点应该分别具有指向另一个链表头部的指针，即**循环双链表**。 **3. 堆栈插入操作** 在基于单链表的堆栈中插入一个新结点的操作：`top->link = p; top = p;` **4. 满二叉树叶结点数目** 素数在20至40之间：23、29、31、37。满二叉树的叶结点数目为2^(log2(n)+1)-1，其中n为结点总数，所以n=23时，叶结点数目为12。 **5. 二叉树后序遍历** 给定的中序遍历和按层次遍历，构建二叉树后得到的后序遍历序列为**d,b,f,e,c,a**。 **6. 非连通无向图的顶点数** 至少有顶点数为36+1=37个，因为非连通无向图至少有一个孤立顶点。 **7. 判断有向图是否存在回路的方法** 除了拓扑排序，还可以使用**深度优先搜索**（DFS）来检测环的存在。 **8. 折半查找** 在给定顺序表中查找37的过程：65,37 **9. 散列函数构造** 为了降低散列冲突的可能性，最好选择一个与关键字范围内的数字**互质**的数作为p。 **10. 排序方法** 描述的排序方法是**快速排序**。 ##### 三、综合题 **1. 时间复杂度分析** 函数main的时间复杂度为**O(logn)**，因为x每次翻倍直到接近n/2，因此循环次数与n的对数成正比。 **2. 二叉树遍历** 给定的前序遍历序列A,B,E,F,G,C,H,D，构建二叉树后，可以得到相应的中序遍历序列和后序遍历序列等信息，这有助于理解二叉树的结构。 以上是对北航 991 数据结构与C语言 1998~2015 真题的部分知识点解析。
5星
