题目内容
(请给出正确答案)
[主观题]
考查如教材121页代码5.6所示的BinTree::updateHeightAbove(x)算法。a)试证明,在逆行向上依次更新x各祖先高度的过程中,一旦发现某一祖先的高度没有发生变化,算法即可提前终止;b)试按此思路改进这一算法;c)如此改进之后,算法的渐进复杂度是否会相应地降低?为什么?
查看答案
如果结果不匹配,请 联系老师 获取答案
考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树,试证明:
a)顶点v是u的祖先,当且仅当
b)v与u无承袭关系,当且仅当