东北大学数据结构II X试卷解析：拓扑排序与哈希表

"东北大学数据结构II X课程的试卷及答案，包含数据结构相关的算法实现和哈希表问题解析" 本文将深入探讨数据结构中的两个关键知识点：拓扑排序算法和哈希表的线性探测再散列。这些概念在计算机科学尤其是数据处理和算法设计中具有重要意义。 首先，我们来看拓扑排序。拓扑排序是针对有向无环图（DAG，Directed Acyclic Graph）的一种排序方法，它能够将图中的所有顶点排成一个线性的序列，使得对于图中的每条有向边 (u, v)，顶点 u 都在这个序列之前出现。在提供的代码段中，`toposort` 函数以逆邻接表作为存储结构实现了一个有向图的拓扑排序。该函数首先计算每个顶点的出度，然后将出度为零的顶点入栈。每次从栈中弹出一个顶点并访问，更新其相邻顶点的出度，如果某个相邻顶点的出度变为零，则将其入栈。最后，若栈为空且已遍历所有顶点，说明图没有环，返回有效的拓扑排序序列；否则，返回0表示存在环。 接下来，我们讨论哈希表和线性探测再散列。哈希表是一种数据结构，通过哈希函数将关键字映射到特定的存储位置，以实现快速查找。线性探测再散列是一种解决哈希冲突的方法，当关键字哈希到的位置已有其他元素时，会沿着表的顺序方向寻找下一个空位置。题目中给出了一个哈希表长度为13，哈希函数定义为 `H(key) = key % 13`，并依次插入了9个关键字。线性探测的过程显示了如何在冲突发生时找到下一个可用的槽位。例如，关键字25和23冲突，都哈希到位置0，所以23被探测到位置1；同理，关键字36和34分别与29和23冲突，都被放置在了位置4。哈希表的构造完成后，可以计算在等概率情况下查找成功的平均查找长度。通常，平均查找长度会考虑查找失败的情况，这里未给出查找失败的计算，但一般来说，线性探测再散列的平均查找长度会随着哈希表装载因子的增加而增加。 总结来说，本资料涵盖了数据结构中重要的拓扑排序算法和哈希表的线性探测再散列技术，这些都是理解和应用数据结构基础的重要部分，对于计算机科学的学习者和从业者都有很高的参考价值。