算法分析与设计答案2023

第十一章测试

1.

蒙特卡罗算法的结果肯定是一个正确解。

A:错 B:对
答案:A
2.

Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。

A:对 B:错 3.

借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。

A:对 B:错 4.

随机算法共同点是计算时间越多或运行次数越多,正确性越高.

A:对 B:错 5.

增加拉斯维加斯算法的反复求解次数, 可使求解无效的概率任意小。

A:对 B:错 6.

在下列算法中有时找不到问题解的是

A:数值随机算法 B:舍伍德算法 C:蒙特卡罗算法 D:拉斯维加斯算法 7.

肯定获得可行解，但不一定是正确解的算法是

A:舍伍德算法 B:数值随机算法 C:拉斯维加斯算法 D:蒙特卡罗算法 8.

在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（  ）对输入进行预处理。

A:舍伍德算法 B:拉斯维加斯算法 C:蒙特卡罗算法 D:数值随机化算法 9.

下面说法正确的是

A:求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。 B:舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。 C:现实计算机上无法产生真正的随机数 D:蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。 10.

下面说法正确的是（）

A:随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法 B:线性同余法是产生伪随机数的最常用的方法 C:当最坏和平均情况差别较大时, 舍伍德算法可以消除好坏实例的差别，达到平均实例的性能 D:增加蒙特卡罗算法的求解次数, 可使求解错误的概率任意小。 11.

确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所得结果完全相同。

A:对 B:错 12.

舍伍德算法总是有解, 且解总是正确的，但最坏性能未改变。

A:对 B:错 13.

拉斯维加斯算法肯定得到一个正确解。

A:对 B:错 14.随机抽取数组元素k次,从最接近搜索元素x 的位置顺序搜索,  顺序搜索的平均比较次数为O(n/(k+1)). 
A:错 B:对