更多“考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树,试证明:a)顶点v是u的祖先,当且仅当b)v与”相关的问题
第1题
考查教材39页代码2.10中的无序向量查找算法find(e,lo,hi)。a)在最好情况下,该算法需要运行多少时间?为什么?b)若仅考查成功的查找,则平均需要运行多少时间?为什么?
点击查看答案
第2题
考查如教材75页代码3.11所示的List::remove()算法。当待副除的节点既是首节点也是末节点(即列表仅含单个节点)时,该算法是否依然适用?为什么?
点击查看答案
第3题
考查教材40页代码2.11中的无序向量插入算法insert(r,e)。试证明,若插入位置r等概率分布,则该算法的平均时间复杂度为0(n),n为向量的规模。
点击查看答案
第4题
考查如教材348页代码12.10所示的quickSelect()算法。a)试举例说明,最坏情况下该算法的外循环需要执行Ω(n)次;b)在各元素独立等概率分布的条件下,该算法的平均时间复杂度是多少?
点击查看答案
第5题
考查GS[]表构造算法(教材326页代码11.8),记模式串的长度|P|=m。试证明:a)buildSS()过程的运行时间为o(m);b)buildGS()过程的运行时间为o(m)。
点击查看答案
第6题
考查教材41页代码2.12中的无序向量删除算法remove(lo,hi)。a)若以自后向前的次序逐个前移后继元素,可能出现什么问题?b)何时出现这类问题?试举一例。
点击查看答案
第7题
考查如教材121页代码5.6所示的BinTree::updateHeightAbove(x)算法。a)试证明,在逆行向上依次更新x各祖先高度的过程中,一旦发现某一祖先的高度没有发生变化,算法即可提前终止;b)试按此思路改进这一算法;c)如此改进之后,算法的渐进复杂度是否会相应地降低?为什么?
点击查看答案
第8题
考查教材37页代码2.7中的permute()算法,假设rand()为理想的随机数发生器,试证明:a)通过反复调用permute()算法,可以生成向量V[0,n)的所有n!种排列:b)由该算法生成的排列中,各元素处于任一位置的概率均为1/n;c)该算法生成各排列的概率均为1/n!。
点击查看答案
第9题
考查如教材76页代码3.14所示的List::deduplicate()算法。a)给出其中循环体所具有的不变性,并通过数学归纳予以证明;b)试举例说明,该算法在最好情况下仅需o(n)时间;c)试改进该算法,使其时间复杂度降至o(nlogn);d)o(nlogn)的效率是否还有改进的余地?为什么?
点击查看答案
第10题
考查如教材83页代码3.23所示的List::mergeSort()算法,试证明:a)若为节省每次子列表的划分时间,而直接令m=min(c,n/2),其中c为较小的常数(比如5),则总体复杂度反而会上升至o(n2);b)特别地,当取c=1时,该算法等效地退化为插入排序。
点击查看答案
第11题
考查如教材24页代码1.12所示的二分递归版fib(n)算法,试证明:a)对任一整数1≤k≤n,形如fib(k)的递归实例,在算法执行过程中都会先后重复出现fib(n-k+1)次;b)该算法的时间复杂度为指数量级;c)该算法的最大递归深度为o(n);d)该算法具有线性的空间复杂度。
点击查看答案