东大22春《数据结构Ⅱ》在线作业：关键知识点回顾

本资源是东大22春季《数据结构Ⅱ》在线平时作业的第二部分，主要考察了数据结构的基础概念和算法理解。以下是针对每一道题目详细解析的知识点： 1. **BFS算法与最短路径问题**：BFS（广度优先搜索）适用于解决单源最短路径问题，前提是所有边的权值必须是**相等**的，因为算法按照广度优先的顺序遍历节点，确保先访问距离起点近的节点。 2. **堆的构造**：不构成堆的序列特点是父节点的值应该大于或等于其子节点的值（对于最大堆）或小于或等于（对于最小堆）。选项D中，最后一个元素10没有满足堆的性质，因此不构成堆。 3. **单链表插入操作**：在单链表中，在结点p之后插入结点s，应将s的next指针指向p的下一个结点，然后更新p的next指针指向s，即`s-next=p-next; p-next=s;`。 4. **B-树结点分裂**：9阶B-树在插入关键字后可能会导致结点分裂，这意味着插入前结点最多可以容纳9个关键字（包括中心结点），所以插入一个新关键字后，结点内关键字数量为9+1=10个。 5. **散列表冲突处理**：采用线性探测解决冲突时，若连续插入n个同义词，每次插入都会查找下一个空闲位置，直到找到一个，因此查找最后一个插入的关键字需要做n次比较，因为需要回溯到第一个冲突的位置。 6. **主关键字的作用**：在文件中，主关键字用于唯一标识一个**记录**，即数据库中的每一行数据。 7. **循环队列的实现**：在循环队列中，队头元素的位置可以通过rear指针计算得出，即`(rear-length)％m`，因为队尾之后紧接着队头，当指针超过数组长度时，会自动回绕。 8. **分块查找性能**：对于123个元素的线性表，分为3块后，平均查找长度取决于查找成功的概率，每个元素被均匀分布到三个块中，查找每个块的概率相同，所以在确定块并查找时，平均查找长度为(1+2+3)/3 = 2.3，即23。 9. **数据结构中的数据元素**：数据结构中定义的数据元素通常是表示数据的**基本单位**，它是最小的、不可再分割的存储单元。 10. **快速排序空间复杂度**：快速排序的平均空间复杂度为O(logn)，因为递归调用栈的最大深度为logn，与n个关键字的数量无关。 11. **括号匹配算法**：为了检查混合嵌套括号的正确性，通常使用递归或栈作为辅助结构，例如使用栈来保存左括号，遇到右括号时检查是否与栈顶匹配。 12. **数据结构的正确说法**：题目中没有给出具体选项，但从上下文推测，正确的数据结构定义或特性的表述可能是关于数据元素的独立性和唯一标识的。 13. **数据元素的唯一标识**：在数据结构中，每个数据元素可能只有一个**标识符**，用来唯一地标识和区分不同的数据元素。 这些题目涵盖了数据结构的基本概念、搜索算法、链表操作、B-树、散列表、队列、排序、查找算法、数据结构元素以及表达式匹配等多个方面的知识。通过解答这些问题，可以检验学生对数据结构深入理解和应用能力。