北邮《数据结构》期末考试样题解析

"北邮数据结构期末考试样题，涵盖了数据结构的基础概念、算法复杂度分析、线性表、链表、栈、队列、图、查找和排序等相关知识点。" 1. 算法复杂度分析：题目中提到的程序片段用于统计字符串中空格的个数，算法复杂度为线性时间复杂度，即O(N)，其中N表示字符串的长度。这意味着程序会按顺序遍历整个字符串，时间成本与字符串长度成正比。 2. 顺序存储的线性表插入：在顺序存储的线性表中，如果在任何位置插入元素的概率相等，那么平均需要移动的元素数量是 (n+1)/2。这是因为当在表中间插入时，需要移动一半的元素，而在两端插入则不需要移动。 3. 链式存储的线性表：链式存储的线性表地址可以是连续的，也可以是不连续的，这取决于实际的存储分配策略。 4. 头节点的作用：链表中增加头节点主要是为了方便插入和删除操作，头节点使得插入和删除不必考虑首元素的特殊性。 5. 循环队列遍历二叉树的空间复杂度：最坏情况下，需要存储整棵树的所有节点，因此空间复杂度为O(N)，其中N是二叉树的节点数。 6. 栈和队列的特性：栈和队列都是限制存取点的线性结构，栈是后进先出（LIFO），队列是先进先出（FIFO）。 7. 对称矩阵的图：无向图的邻接矩阵是对称的，因为无向边连接的两个节点在矩阵中对应的位置都有值。 8. 折半查找的要求：适用于折半查找的表需以顺序方式存储且元素有序，这样才能利用二分查找法快速定位目标。 9. 静态查找表与动态查找表的区别：它们的主要区别在于存储实现，静态查找表在创建后元素位置固定，而动态查找表允许在运行时添加或删除元素。 10. 排序所需辅助空间：在排序顺序表中的数据时，归并排序通常需要额外的存储空间来合并两个子序列，是这些排序方法中辅助空间需求最多的。 接下来是判断题： 1. 递归与非递归转化：正确，任何递归过程理论上都可以转换为非递归的循环操作。 2. 链表实现栈和队列：正确，链表可以灵活地实现栈和队列的数据结构。 3. 最小代价生成树：错误，最小代价生成树的形状可能不唯一，但总代价是唯一的。 4. 二叉树遍历时间复杂度：错误，二叉树的遍历时间复杂度在最坏情况下是O(N)，无论是否为平衡树。 5. 森林转化为二叉树：正确，所有森林都可以通过一定的规则转化为一棵二叉树。 6. 完全二叉树与左孩子：错误，完全二叉树中，若一个节点没有左孩子，它可能是叶节点，也可能是只有一个右孩子的节点。 7. 折半查找最快：错误，折半查找的速度依赖于具体情况，不是所有情况下都最快。 8. 带环有向图拓扑排序：正确，带环的有向图无法进行拓扑排序。 9. 归并排序时间复杂度：错误，归并排序的最好和最坏时间复杂度都是O(NlogN)。