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

问答题
请列举几个常见的NP完全问题。
答案：1）合取范式的可满足性问题；
2）三元合取范式的可满足性问题；
3）团问题；
4）顶点覆盖...
问答题
求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？
答案：在规模为n的数据元素集合中找出最大元和最小元，至少需要3n/2-2次比较，即3n/2-2是找最大最小元算法的下界。当n=...
问答题
如何重构warshall算法最内层循环，使得它到少对于某此输入来说运行得列快？
答案：
单项选择题
使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（）
A.10
B.11
C.500
D.1000
判断题
数据结构与算法里，冒泡排序是不稳定的排序。
答案：错误
问答题
写出归并排序算法对下列实例排序的过程。（6，2，9，3，5，1，8，7）
答案：
单项选择题
一个单窗体Vb程序的运行界面如下图所示：下列说法正确的是（）（1）窗体内有1个按钮（2）窗体内有2个文本框（3）窗体内有3个标签（4）该窗体的标题（caption）属性值是“加法计算器”
A.（1）（4）
B.（3）（4）
C.（1）（2）
D.（2）（3）
单项选择题
函数调用的一种特殊，即自己调用自己称为（）。
A.嵌套调用
B.循环调用
C.连续调用
D.递归调用
问答题
现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？
答案：设新机器用同一算法在t秒内能解输入规模为n’的问题，则有
T（n）=3×2ⁿ...
单项选择题
青蛙过河问题中，如果河中没有石柱，有x片荷叶的话，那么从左岸到右岸可以过去（）只青蛙
A.x+1只
B.x+2只
C.x+3只
D.x+4只