北航研究生算法答案

判断题： 1-5: T F F F F 6-10: F T F F F 11-16: F T T F T F 问答题： 1.（1）属于减可变规模变种的应用。（2）当节点个数等于二叉查找树的高度时表现出最差的效率。（3）此时查找和插入算法在最坏情况的时间复杂度都是O(n)。 2.（1）伪多项式时间算法是一种在L值的多项式时间内运行的算法，其中L是输入实例中的最大数值。 （2）Monte Carlo算法每次都能得到问题的解，但不保证所得解的准确性；Las Vegas算法是每次不一定得到问题的解，只要得到的解一定是正确的解；可以在Monte Carlo算法后加上一个验证算法，如果正确就得到解，如果错误就不能生成问题的解，这样Monte Carlo算法便转化为了Las Vegas算法。 3. AVL树和2-3树能够维持树的平衡，避免树的退化，它们在最坏情况下插入和查找的时间复杂度均为O(log2n)。 4. 0/1背包问题的一个多项式等价判定问题是给定价值为V1, V2, …, Vn，重量为W1, W2, …, Wn的n个项和两个整数v*和w*，问是否存在一个子集S，使得