高级数据结构与算法习题（9）

作者：菜鸟追梦旅行 | 2024-05-08 05:24:09

踩

高级数据结构与算法习题（9）

一、判断题

1、Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity am must be included in all the maximum-size subset of mutually compatible activities of S.

T F

解析：F。设S是活动选择问题中的一组活动。那么，S的相互兼容活动必须有一些最大大小的子集，其中包括最早完成的活动am。但是并不是最早完成活动am必须包括在S的所有相互兼容活动的最大规模子集中。

2、Let C be an alphabet in which each character c in C has frequency c.freq. If the size of C is n, the length of the optimal prefix code for any character c is not greater than n−1.

T F

解析：T。根据哈夫曼树的性质，对于字符集大小为 n 的情况，任何一个字符的最优编码长度不会超过 n-1。这是因为在哈夫曼树中，从根节点到叶子节点的路径长度即为该字符的编码长度，而哈夫曼树的最短路径长度为 1，最长路径长度为 n-1。

二、单选题

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.
The coins of the lowest denomination（面额） is the cent.

(I) Suppose that the available coins are quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The greedy algorithm always yields an optimal solution.

(II) Suppose that the available coins are in the denominations that are powers of c, that is, the denominations are $c^0, c^1, ..., c^k$ for some integers $c>1$ and $k\geq1$ . The greedy algorithm always yields an optimal solution.

(III) Given any set of k different coin denominations which includes a penny (1 cent) so that there is a solution for every value of n, greedy algorithm always yields an optimal solution.

Which of the following is correct?

A.Statement (I) is false.

B.Statement (II) is false.

C.Statement (III) is false.

D.All of the three statements are correct.

解析：A。贪心算法有时候算出的结果并不是

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/553024