数据结构与算法JAVA语言描述课后习题参考答案

CHAPTER 1

Introduction

1.4

The general way to do this is to write a procedure with heading

void processFile( String fileName );

processFile( SomeFile );

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 )

consider any 2p < Y  4p (p  1). Then log Y = 1 + log(Y/2)< 1 + Y/2 < Y/2 + Y/2  Y, where the first

inequality follows by the inductive hypothesis.

(b) Let 2

= A. Then A

= XB. Since X = log A, the theorem is proved.

1.8

(a) The sum is 4/3 and follows directly from the formula.

(b)

S 



2



3

. By part (a), 3S = 4/3 so S = 4/9.

(c)

S 



4





Subtracting the first equation from the second gives

20/27.

N–2

1.9

1.10 2

4

= 16  1 (mod 5). (2

4

)

25

 1

25

(mod 5). Thus 2

100

 1 (mod 5).

1.11 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for N = 1, 2, ... , k.

k+3

for N = k + 1, and hence for all N.

As in the text, the proof is by induction. Observe that

+ 1 =

2

. This implies that

–1

+

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

 F

 F

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.

CHAPTER 2

Algorithm Analysis

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

(b) O(log log D)

(III)

The running time is O(N

3

(IV)

(V)

j can be as large as i

2

(because it is true exactly i times for each i). Thus the innermost loop is only executed O(N

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

none can occur. It is also clear that the first two algorithms are completely random, and that each permutation

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

 

log N )

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.

1