北京交通大学数据结构期末试题

"这是一份来自北京交通大学的2009-2010学年第二学期期末考试的《数据结构》试卷，由李向前、赵帅峰、徐薇三位教师出题。试卷包含了填空题，涉及了数据结构的基础概念、算法分析、线性表操作、字符串处理、广义表、稀疏矩阵、二叉树、哈夫曼树、中序线索二叉树、图的遍历、邻接表、无向图的度数、关键路径、拓扑排序、有向强连通图、顺序表的查找以及B树和排序方法等多个知识点。" 详细说明： 1. 算法构成：算法由控制结构（如顺序、选择、循环等）和数据操作组成，其效率取决于这两部分的综合效果。 2. 顺序表插入：在长度为n的顺序表中，有n+1个插入位置；在第i个元素之前插入新元素需移动i个元素。 3. 循环队列计算：当头指针front=1，尾指针rear=0时，队列中元素个数为(rear - front + n) % n = (0 - 1 + 7) % 7 = 6。 4. 字符串操作：StrDelete函数删除子串，所以S=‘MBNDEFLGEFK’删除第3位到第6位后变为‘MBNLFGEFK’。 5. 广义表长度与深度：广义表的长度是元素总数，深度是表中最大子表的嵌套层数。此例中长度为6，深度为3。 6. 稀疏矩阵转置：元素（5，7，9）在转置矩阵中变为（7，5，9）。 7. 完全二叉树叶子节点：完全二叉树的叶子节点数量与总节点的关系可以通过公式2^(h-1) ≤ n ≤ 2^h - 1计算，其中h为高度。此处为800个节点，可得出约20个叶子节点。 8. 中序线索二叉树：无右子树的结点前驱是中序遍历中前一个结点，若无左子树且无前驱，则其前驱为左孩子。 9. 森林的中序遍历：等同于遍历每一棵树的中序遍历顺序。 10. 有向完全图邻接表：有n个顶点的有向完全图有n(n-1)个弧结点。 11. 无向图度数之和：所有顶点的度数之和等于边的数量的两倍，即2e。 12. 网的处理：网可以求关键路径，也可进行拓扑排序。 13. 有向强连通图：至少需要n条弧才能构成有向强连通图，每个顶点都必须能到达其他所有顶点。 14. 折半查找平均查找长度：对于15个元素，平均查找长度可通过数学模型计算得出。 15. 完全二叉树平衡因子：所有结点的平衡因子之和等于0，因为完全二叉树是平衡的。 16. 7阶B_树：非终端结点最少包含2个关键字，最多7个。 17. 稳定排序方法：包括冒泡排序、插入排序、选择排序、归并排序、基数排序等。 这份试卷全面覆盖了数据结构的核心概念，旨在考察学生对这些基础知识的理解和应用能力。