数据结构与算法分析（Java语言描述）习题答案（第三版）.docx

. 4S  1  2  3 .

4

42

. 4S  1  4  9  16 .

4

4243

CHAPTER 1

Introduction

is made recursively. Self-referential includes can be detected by keeping a list of files for which a call to

processFile has not yet terminated, and checking this list before making a new call to processFile.

1.5 public static int ones( int n )

{

}

1.7 (a) The proof is by induction. The theorem is clearly true for 0 < X  1, since it is true for X = 1, and for X <

1, log X is negative. It is also easy to see that the theorem holds for 1 < X  2, since it is true for X = 2, and

(b)

S 

1

Subtracting the first equation from the second gives

4

3S  1 

1

1

4

.

4

4

4

4

4

20/27.

S

N–2

,..., S

N

/

2

1.9

i

N

/

i

1

Then

Fi

Fi





1. By the induction hypothesis, the value of the sum on the right is F

1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, ... , k.



F

by the definition, and we can use the inductive hypothesis on the right-hand side, obtaining

F

k

1



k



k

1

and proving the theorem.

(c) See any of the advanced math references at the end of the chapter. The derivation involves the use of

generating functions.

N N N

1.12 (a)

(2i  1)  2

CHAPTER 2

Algorithm Analysis

log

The second limit is zero by the inductive hypothesis, proving the claim.

2.5 Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is

even. Then the ratio f(N)/g(N) oscillates between 0 and inf.

2.6 (a) 2

(III) The running time is O(N

).

(IV) The running time is O(N

).

(V) j can be as large as i

. k can be as large as j, which is N

is thus proportional to NN

).

Each time through, it takes O(j

) time, for a total of O(N

). This is an example where multiplying

loop sizes can occasionally give an overestimate.

2.8 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have tests

to guarantee no duplicates; the third algorithm works by shuffling an array that initially has no duplicates, so

is equally likely. The third algorithm, due to R. Floyd, is not as obvious; the correctness can be proved by

induction. See J. Bentley, “Programming Pearls,” Communications of the ACM 30 (1987), 754–757. Note

that if the second line of algorithm 3 is replaced with the statement

swap References( a[i], a[ ran dint( 0, n–1 ) ] );

then not all permutations are equally likely. To see this, notice that for N = 3, there are 27 equally likely ways

earlier is O(i). The expected number of random numbers that need to be tried is N/(N – i). This is obtained





2

The second algorithm saves a factor of i for each random number, and thus reduces the time bound to

O(N log N) on average. The third algorithm is clearly linear.

(c,d) The running times should agree with the preceding analysis if the machine has enough memory. If not,

the third algorithm will not seem linear because of a drastic increase for large N.