![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
[主观题]
中序遍历迭代式算法的第三个版本(教材131页代码5.18),需反复地调用succ()接口以定位直接后继,从而会相应地增加计算成本。试问,该算法的渐进时间复杂度是否依然保持为o(n)?若是,请给出证明;否则试举一例。
查看答案
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.遍历的基本算法有两种:深度遍历和广度遍历
C.图的深度遍历不适用于有向图
D.图的深度遍历是一个递归过程
的最小值称为数据包序列
的均衡负载量.
算法设计:对于给定的数据包序列,计算m个处理器的均衡负载量.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.n表示数据包个数,m表示处理器数.接下来的1行中有n个整数,表示n个数据包的大小.
结果输出:将计算的处理器均衡负载量输出到文件output,txt,且保留2位小数.
在c语言标准库中,Brian W. Kernighan和Dennis M. Ritchie设计的随机数发生器如下:
a)阅读这段代码,并理解其原理:
b)试说明,若采用rand()的这个版本实现permute()算法,则上题的结论a)和b)并不能兑现;
c)试说明,采用此类伪随机数发生器实现permute()算法,上题的结论a)和b)必然无法兑现;
d)针对b)和c)所指出的不足,应如何改进rand()和permute()算法?
序列中元素A[i]和A[j]若满足i<j且A[i]>A[j],则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort(),试证明:
a)若所有逆序对的间距均不超过k,则运行时间为o(kn);
b)特别地,当k为常数时,插入排序可在线性时间内完成;
c)若共有I个逆序对,则关键码比较的次数不超过o(I);
d)若共有I个逆序对,则运行时间为o(n+I)。