9.8 其他综合题·选择题讲评

回指原理与建模

综合选择题先分类到线性表、树、图、查找、排序，再调用该章不变量排除。涉及多个算法时建立条件表，不凭熟悉度。

手工推演与代码证据

要求稳定、最坏nlogn且允许O(n)空间，可选归并；要求原地最坏nlogn可选堆，但不稳定。条件逐项过滤。

代码题必须运行空输入、单元素、一般输入和失败边界；讲评要指出状态为何保持。

错因与迁移

错因是只看时间。迁移：非负单源最短路选Dijkstra；有负边不能选它。