考查教材5.4.2、5.4.3、5.4.4和5.4.5节所介绍的各种迭代式二叉树遍历算法。a)试证明，这些算法都是正确的——亦即，的确会访问每个节点一次且仅一次；b)试证明，无论递归式或迭代式，这些算法都具有线性时间复杂度；c)这些算法的空间复杂度呢？

考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树，试证明：

a)顶点v是u的祖先，当且仅当

b)v与u无承袭关系，当且仅当

若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的()。

A．前序遍历算法

B．层次遍历算法

C．后序遍历算法

D．中序遍历算法

若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ()

A．层次遍历算法

B．前序遍历算法

C．中序遍历算法

D．后序遍历算法

A.先序遍历

B.中序遍历

C.后序遍历

D.层序遍历