算法设计与分析答案2023

第九章测试

1.不属于贪婪技术的算法是（ ）
A:哈夫曼编码 B:Kruskal算法 C:Floyd算法 D:Dijkstra算法

答案:C
2.如果e是加权连通图中权重最小的边，它（ ）图的一棵最小生成树的边。
A:必定不是 B:必定是 C:不一定是
3.

对于包含负权重边的图，Prim 算法( )正确工作。

A:不一定能 B:不能 C:不确定 D:能 4.如果加权连通图中每条边的权重是都是互不相同的，该图必定只有一棵最小生成树。( )
A:对 B:错 5.

哈夫曼编码频率相同的所有字符都具有相同的码长。 ( )

A:错 B:对 6.频率较高的字符的码长不一定小于频率较低的字符的码长。( )
A:对 B:错 7.Prim算法总是通过把离树中顶点最近的顶点包含进来，从而生成一棵最小生成树。 ( )
A:对 B:错 8.对于包含负权重边的图， Kruskal 算法可能会无效。( )
A:错 B:对 9.对于包含负权重边的图， Dijkstra算法也是正确有效的。( )
A:错 B:对 10.Dijkstra算法是解决单起点最短路径问题的。 ( )
A:错 B:对 11.Dijkstra算法和Floyd算法采用了相同的算法设计技术。( )
A:对 B:错 12.Dijkstra算法和Floyd算法都是是解决完全最短路径问题的。 ( )
A:对 B:错 13.贪婪算法在对问题求解时，总是做出当前看来最好的选择。( )
A:对 B:错 14.哈夫曼编码的压缩率通常在20%～80%之间。( )
A:错 B:对 15.哈夫曼编码总是最优前缀码。 ( )
A:错 B:对