第二章单元测试
- 若
，则
。 （ ） - 设
为
阶方阵。现用以下算法求
。
算法：
For i = 1 to n do
For j = 1 to n do
= 0
For k = 1 to n do
输出
该算法的时间复杂度为（ ）。 - 若
NP，以下能说明
是NP-C问题的是（ ）。 - 设有
个城市的TSP问题实例，城市之间距离为
，以下是该实例规模合理表达式的有（ ）。 - 设一平行机排序问题算法的时间复杂度为
，其中
分别为机器数和工件数，
为一与实例无关的常数。以下说法准确的有（ ）。
A:错 B:对
答案:错
A:
B:
C:
D:
答案:
A:对任意
NP，
。B:存在
NP，。C:对任意
NP-C，
。D:存在
NP-C，。答案:对任意
NP，。A:
B:
C:
D:
答案:
###
###
A:若在该问题中，机器数是一个固定常数，该算法是一个指数时间算法。
B:若在该问题中，机器数是一个固定常数，该算法是一个多项式时间算法。
C:若在该问题中，机器数可能随实例不同而变化，该算法是一个指数时间算法。
D:若在该问题中，机器数可能随实例不同而变化，该算法是一个多项式时间算法。
答案:若在该问题中，机器数是一个固定常数，该算法是一个多项式时间算法。
###若在该问题中，机器数可能随实例不同而变化，该算法是一个指数时间算法。
