高级数据结构与算法习题（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的相互兼容活动必须有一些最大大小的子集，其中包括最早完成的活动a​m。但是并不是最早完成活动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  for some integers  and . 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。贪心算法有时候算出的结果并不是