同济大学数据结构期终试题回顾与解析

本资源是一份针对同济大学软件学院的数据结构期终试卷，涵盖了数据结构的基础理论和实践应用。试题主要分为三个部分： 1. 判断选择题： - 一维数组的逻辑结构是**线性结构**，因为它们元素按照线性顺序排列。存储结构方面，一维数组通常采用**顺序存储**方式，即元素连续存储在内存中。对于二维数组，有两种存储方式：**行优先顺序**和**列优先顺序**，这取决于数组的访问模式。 - 二叉树的中序遍历和前序遍历关系：题目指出若一个结点是二叉树中某子树中序遍历的最后一个结点，它并不一定是最先被访问的，因此这个说法是**错误**（N）。 - 链表操作：在单链表中，如果要在指针p所指结点之后插入结点*s*，由于需要保持指针的正确指向，正确的操作是将*s*的next指向前一个结点的下一个位置，然后更新前一个结点的next指针，对应的操作是②（s→next=p→next;p→next=s;）。 - 关于B树的性质，9阶B树非叶子结点的关键字个数应在5到9之间，这个陈述是**正确**（Y）。 - 堆的性质：堆顶结点通常是最大（或最小）元素，题目描述的是大顶堆的情况，是正确的（Y）。 2. 回答问题： - 循环队列的队空条件是`rear == 0`且`count != 0`，队满条件是`rear + count == m`（m为数组长度）。 - 平衡二叉树的平衡因子计算方法是通过比较左右子树的高度差来确定，如果高度差超过1，则需要进行旋转调整。 - 哈希冲突解决方法主要有**开放寻址法**（线性探测、二次探测等）和**链地址法**（拉链法），这里是用到的拉链法。 - 有向图的拓扑排序中，当一个顶点被输出后，需要删除它并检查其相邻顶点的依赖关系。 3. 计算与解答： - 第一小问要求画出邻接表和深度优先/广度优先遍历序列，需要具体图的描述来完成。 - 第二小问涉及3阶B树的插入与删除操作，需要了解B树的结构变化规则。 - 第三小问是关于哈希表的构造和查找效率计算，需用给定文件中的数据和哈希函数设计哈希表，并计算平均查找长度。 总结来说，这份试卷涵盖了数据结构的多个关键概念，包括线性结构、数组、链表、树的遍历、队列、堆、哈希表、图的结构以及数据的存储和检索算法。通过解答这些问题，学生可以巩固和检验对这些概念的理解与应用能力。