9.7 简答题·综合题讲评

回指原理与建模

简答题用“结论—条件—依据—边界”四句式。复杂度结论必须说最坏/平均/均摊；结构比较必须带工作负载。

手工推演与代码证据

问数组与链表：数组随机访问O(1)、局部性好；链表已知结点处改链O(1)、扩展灵活；若需定位位序，链表仍O(n)。

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

错因与迁移

错因是罗列优缺点却不关联场景。迁移：解释动态数组尾插均摊O(1)，依据倍增后总搬移为几何和。