算法设计与分析章节练习(2020.04.01)

问答题
用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
答案：斜线标识的部分完成的功能为：提前更新bestw值；
这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxlo...
填空题
5台主机A、B、C、D、E分属（）个网段。
答案：3
单项选择题
希尔排序就稳定性而言属于（）。
A.稳定排序
B.不稳定排序
C.可能是稳定的也可能是不稳定，根据情况不同而不同
D.其它选项都不对
问答题
结合所做的改进，为冒泡排序写一段伪代码.
答案：
问答题
Dijkstra算法求单源最短路径。
答案：
填空题
θ记号在算法复杂性的表示法中表示（）
答案：紧致界
判断题
数据结构与算法里，冒泡排序的时间复杂度是O（n*n）。
答案：正确
判断题
汉诺塔的时间复杂度从阶梯来讲，属于指数阶。
答案：正确
单项选择题
当输入规模为n时，算法增长率最大的是（）
A.5ⁿ
B.20log₂ⁿ
C.2n²
D.3nlog₃ⁿ
单项选择题
下面程序执行后输出的结果是（）。
A.123
B.1230
C.12356789
D.123056789