0-ANSWER.docx

图论、排序算法、散列表等知识点总结 在这篇文章中，我们将对图论、排序算法和散列表等知识点进行总结和分析。 图论 1. 图的邻接矩阵可能是对称的或非对称的，具体取决于图的类型。如果图是无向图，那么其邻接矩阵一定是对称的；如果图是有向图，那么其邻接矩阵可能是非对称的。 2. 图的遍历有两种方法：深度优先遍历（DFS）和广度优先遍历（BFS）。DFS相当于二叉树的先序遍历或后序遍历，而BFS则是从某个顶点开始，逐步访问其邻接点，直到访问所有顶点。 3. 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，那么G中一定有回路或两个连通分量。 4. 在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。 排序算法 1. 直接插入排序算法在最好情况下的时间复杂度为O(n)。 2. 快速排序是稳定的算法，但在待排序数据基本有序的情况下，快速排序效果最好。 3. 希尔排序也是稳定的算法，但由于其最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。 散列表 1. 在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素。 2. 查找某元素时，折半查找法的查找速度一定比顺序查找法快。 3. 散列函数越复杂越好，因为这样随机性好，冲突概率小。 其他 1. 在一个无向图中，所有顶点的度之和等于边数的两倍。 2. 若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是完全图。 3. 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 4. 在图中自a点开始进行深度优先遍历算法可能得到的结果为a,b,e,c,d,f。 本文对图论、排序算法和散列表等知识点进行了总结和分析，为读者提供了有价值的参考信息。