2.7 练习题
2-1. 当我们用Python中的list构建一个多维数组时，通常需要使用循环来完成（或某种与list推导式等效的技术），为什么不能用表达式[[0]10]10来创建一个10×10的数组呢？这样做会有什么问题吗？
2-2. 让我们来做个假设（也许会有点不切实际）：如果我们允许在分配内存时出现未初始化的情况（也就是说，这块内存中还保有上一次被使用时留下的“垃圾数据”），并且分配内存也只需要常数时间。这时如果您想创建一个含有n 个整数的数组，并且希望跟踪其每一项——看看它是处于非初始化状态，还是您已经在它里面保存过一个数字了。这种检查操作也是可以在常数时间内完成的。那么，我们究竟应该怎样做，才能保证它在常数时间内完成它的初始化操作呢？（以及应该如何在常数时间里完成一个空邻接数组的初始化操作，以避免其成为一个以平方级时间为最小运行时间的操作？）
2-3. 请证明O 与Ω的性质正好相反，即如果f = O (g )，那么g = Ω(f )，反之亦然。
2-4. 对数通常有各自不同的底数，但在算法学上，我们往往并不会太在意它。为了明白其中的原因，我们可以来考虑一下这个等式：logbn= (logan )/(logab)。首先，您知道这个等式为什么成立吗？其次，为什么它能告诉我们不需要去操心对数的底数问题？
2-5. 请证明任何指数级操作（Θ(kn )，其中k > 1）的增长都要快于多项式级操作（Θ(nj )，其中j > 0）。
2-6. 请证明任何多项式操作（Θ(nk )，其中k 为任意常数且k > 0）的渐近增长都要快于对数级操作（Θ(lg n )）。（值得注意的是，这里的多项式中包括根数在内，如平方根（k = 0.5）等）。
2-7. 请研究或推算一下Python list类型上各个操作的渐近复杂度，如索引、元素项赋值、顺序反转、元素的追加及插入（最后两项我们在list的黑盒子专栏中已经讨论过了）。如果我们改用链表类型来实现这些操作会有什么不同？请以list.extend为例加以说明。
2-8. 请证明表达式Θ(f ) + Θ(g ) = Θ(f + g ) and Θ(f ) · Θ(g ) = Θ(f · g )成立。另外，您也可以试试是否能证明max(Θ(f ), Θ(g )) = Θ(max(f , g )) = Θ(f + g )成立。
2-9. 在附录C中，您会找到一组与树有关的、带编号的陈述句，请证明它们是等效的。
2-10. 假设T 是一棵有根树，它至少应包含三个节点，并且每个内部节点下面又正好都有两个子节点。那么，如果T 上有n 个叶节点，树上到底应有多少个节点呢？
2-11. 请证明一个DAG可以由任何形式的（底层）结构组成。换言之，任何（无向）图结构都可以成为一个DAG的底层图结构。或者说，对于任何给定的图结构，我们都可以通过调整其边线方向，从中产生出一个有向图，而它正好是一个DAG。
2-12. 请考虑下面这种图结构的表示法：我们使用字典类型，设置其每个键为两个节点的元组，然后将该元组的值设置为边的权值，如W[u, v] = 42。请问：该表示法有什么优点和缺点？您有办法弥补这些缺点吗？