题目内容
(请给出正确答案)
[主观题]
考查如教材76页代码3.14所示的List::deduplicate()算法。a)给出其中循环体所具有的不变性,并通过数学归纳予以证明;b)试举例说明,该算法在最好情况下仅需o(n)时间;c)试改进该算法,使其时间复杂度降至o(nlogn);d)o(nlogn)的效率是否还有改进的余地?为什么?
查看答案
如果结果不匹配,请 联系老师 获取答案
考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树,试证明:
a)顶点v是u的祖先,当且仅当
b)v与u无承袭关系,当且仅当