第1页 / 共114页
第2页 / 共114页
第3页 / 共114页
第4页 / 共114页
第5页 / 共114页
第6页 / 共114页
第7页 / 共114页
第8页 / 共114页
计算机算法-设计与分析导论 巴斯著 课后答案（英文版）.pdf
Computer Algorithms, Third Edition,
Solutions to Selected Exercises
Sara Baase
Allen Van Gelder
February 25, 2000
ii
INTRODUCTION
This manual contains solutions for the selected exercises in Computer Algorithms: Introduction to Design and Analy-
sis, third edition, by Sara Baase and Allen Van Gelder.
Solutions manuals are intended primarily for instructors, but it is a fact that instructors sometimes put copies in
campus libraries or on their web pages for use by students. For instructors who prefer to have students work on
problems without access to solutions, we have chosen not to include all the exercises from the text in this manual. The
included exercises are listed in the table of contents. Roughly every other exercise is solved.
Some of the solutions were written specifically for this manual; others are adapted from solutions sets handed out
to students in classes we taught (written by ourselves, teaching assistants, and students).
Thus there is some inconsistency in the style and amount of detail in the solutions. Some may seem to be addressed
to instructors and some to students. We decided not to change these inconsistencies, in part because the manual will be
read by instructors and students. In some cases there is more detail, explanation, or justification than a student might
be expected to supply on a homework assignment.
Many of the solutions use the same pseudocode conventions used in the text, such as:
1. Block delimiters (“f” and “g”) are omitted. Block boundaries are indicated by indentation.
2. The keyword static is omitted from method (function and procedure) declarations. All methods declared in
the solutions are static.
3. Class name qualifiers are omitted from method (function and procedure) calls. For example, x = cons(z,
x) might be written when the Java syntax requires x = IntList.cons(z, x).
4. Keywords to control visibility, public, private, and protected, are omitted.
5. Mathematical relational operators “6=,” “,” and “” are usually written, instead of their keyboard versions.
Relational operators are used on types where the meaning is clear, such as String, even though this would be
invalid syntax in Java.
We thank Chuck Sanders for writing most of the solutions for Chapter 2 and for contributing many solutions in
Chapter 14. We thank Luo Hong, a graduate student at UC Santa Cruz, for assisting with several solutions in Chapters
9, 10, 11, and 13.
In a few cases the solutions given in this manual are affected by corrections and clarifications to the text. These
cases are indicated at the beginning of each affected solution. The up-to-date information on corrections and clarifica-
tions, along with other supplementary materials for students, can be found at these Internet sites:
ftp://ftp.aw.com/cseng/authors/baase
http://www-rohan.sdsu.edu/faculty/baase
http://www.cse.ucsc.edu/personnel/faculty/avg.html
cCopyright 2000 Sara Baase and Allen Van Gelder. All rights reserved.
Permission is granted for college and university instructors to make a reasonable number of copies, free of charge,
as needed to plan and administer their courses. Instructors are expected to exercise reasonable precautions against
further, unauthorized copies, whether on paper, electronic, or other media.
Permission is also granted for Addison-Wesley-Longman editorial, marketing, and sales staff to provide copies
free of charge to instructors and prospective instructors, and to make copies for their own use.
Other copies, whether paper, electronic, or other media, are prohibited without prior written consent of the authors.
List of Solved Exercises
1 Analyzing Algorithms and Problems: Principles and Examples
1.1 . . .
1.2 . . .
1.4 . . .
1.6 . . .
1.8 . . .
1.10 . .
1.12 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1
2
2
2
3
3
3
1.13 . . . .
1.15 . . . .
1.18 . . . .
1.20 . . . .
1.22 . . . .
1.23 . . . .
1.25 . . . .
. .
. .
. .
. .
. .
. .
. .
3
4
4
4
4
4
5
1.28 . .
1.31 . .
1.33 . .
1.35 . .
1.37 . .
1.39 . .
1.42 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5
6
6
6
6
6
7
1.44 . . . .
1.46 . . . .
1.47 . . . .
1.48 . . . .
1.50 . . . .
. .
. .
. .
. .
. .
2 Data Abstraction and Basic Data Structures
2.2 . . .
2.4 . . .
2.6 . . .
. . . .
. . . .
. . . .
9
9
9
2.8 .
. . . .
2.10 . . . .
2.12 . . . .
. .
. .
. .
9
11
11
2.14 . .
2.16 . .
2.18 . .
. . . .
. . . .
. . . .
12
13
14
3 Recursion and Induction
3.2 . . .
3.4 . . .
. . . .
. . . .
17
17
3.6 .
3.8 .
. . . .
. . . .
. .
. .
17
18
3.10 . .
3.12 . .
. . . .
. . . .
18
18
4 Sorting
4.2 . . .
4.4 . . .
4.6 . . .
4.9 . . .
4.11 . .
4.13 . .
4.15 . .
4.17 . .
4.19 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
19
19
19
19
19
20
20
20
21
4.21 . . . .
4.23 . . . .
4.25 . . . .
4.26 . . . .
4.27 . . . .
4.29 . . . .
4.31 . . . .
4.34 . . . .
4.35 . . . .
. .
. .
. .
. .
. .
. .
. .
. .
. .
21
21
22
22
23
23
23
24
24
4.37 . .
4.40 . .
4.42 . .
4.44 . .
4.45 . .
4.46 . .
4.48 . .
4.49 . .
4.51 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
24
24
24
25
25
25
25
25
26
4.53 . . . .
4.55 . . . .
4.57 . . . .
4.59 . . . .
4.61 . . . .
4.63 . . . .
4.65 . . . .
. .
. .
. .
. .
. .
. .
. .
5 Selection and Adversary Arguments
5.2 . . .
5.4 . . .
5.6 . . .
. . . .
. . . .
. . . .
31
32
32
5.8 .
. . . .
5.10 . . . .
5.12 . . . .
. .
. .
. .
33
34
34
5.14 . .
5.16 . .
5.19 . .
. . . .
. . . .
. . . .
34
34
35
5.21 . . . .
5.22 . . . .
5.24 . . . .
. .
. .
. .
6 Dynamic Sets and Searching
6.1 . . .
6.2 . . .
6.4 . . .
6.6 . . .
6.8 . . .
6.10 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
39
39
40
40
41
41
6.12 . . . .
6.14 . . . .
6.16 . . . .
6.18 . . . .
6.20 . . . .
6.22 . . . .
. .
. .
. .
. .
. .
. .
41
43
45
45
45
46
6.24 . .
6.26 . .
6.28 . .
6.30 . .
6.32 . .
6.34 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
47
47
47
47
48
49
6.36 . . . .
6.37 . . . .
6.40 . . . .
. .
. .
. .
1
7
7
7
7
8
9
17
19
26
27
27
28
28
29
29
31
35
36
37
39
49
49
50
iv
List of Solved Exercises
7 Graphs and Graph Traversals
7.1 . . .
7.3 . . .
7.4 . . .
7.6 . . .
7.8 . . .
7.10 . .
7.12 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
51
51
51
51
51
52
52
7.14 . . . .
7.16 . . . .
7.18 . . . .
7.20 . . . .
7.22 . . . .
7.24 . . . .
7.27 . . . .
. .
. .
. .
. .
. .
. .
. .
53
53
53
54
54
54
57
7.28 . .
7.30 . .
7.32 . .
7.34 . .
7.35 . .
7.37 . .
7.39 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
8 Graph Optimization Problems and Greedy Algorithms
8.1 . . .
8.3 . . .
8.5 . . .
8.7 . . .
. . . .
. . . .
. . . .
. . . .
63
63
63
64
8.8 .
. . . .
8.10 . . . .
8.12 . . . .
8.14 . . . .
. .
. .
. .
. .
64
64
64
64
8.16 . .
8.18 . .
8.20 . .
8.22 . .
. . . .
. . . .
. . . .
. . . .
57
57
57
57
58
59
59
65
65
65
67
7.40 . . . .
7.41 . . . .
7.43 . . . .
7.45 . . . .
7.47 . . . .
7.49 . . . .
. .
. .
. .
. .
. .
. .
8.24 . . . .
. .
8.26 . . . .
. .
8.27 . . . .
. .
9 Transitive Closure, All-Pairs Shortest Paths
9.2 . . .
9.4 . . .
9.6 . . .
. . . .
. . . .
. . . .
69
70
71
. . . .
9.7 .
9.8 .
. . . .
9.10 . . . .
. .
. .
. .
71
71
71
9.12 . .
9.14 . .
9.16 . .
. . . .
. . . .
. . . .
72
72
72
9.18 . . . .
. .
10 Dynamic Programming
10.2 . .
10.4 . .
10.5 . .
10.7 . .
. . . .
. . . .
. . . .
. . . .
11 String Matching
11.1 . .
11.2 . .
11.4 . .
11.6 . .
. . . .
. . . .
. . . .
. . . .
73
73
73
73
81
81
81
83
12 Polynomials and Matrices
10.9 . . . .
10.10 . . .
10.12 . . .
10.14 . . .
. .
. .
. .
. .
11.8 . . . .
11.10 . . .
11.12 . . .
11.15 . . .
. .
. .
. .
. .
73
74
75
75
84
84
84
84
10.16 .
10.18 .
10.19 .
10.21 .
. . . .
. . . .
. . . .
. . . .
11.17 .
11.19 .
11.21 .
11.23 .
. . . .
. . . .
. . . .
. . . .
75
76
77
78
84
85
85
85
10.23 . . .
10.26 . . .
. .
. .
11.25 . . .
. .
12.2 . .
12.4 . .
12.6 . .
. . . .
. . . .
. . . .
87
87
87
12.8 . . . .
12.10 . . .
12.12 . . .
. .
. .
. .
87
87
88
12.14 .
12.16 .
12.17 .
. . . .
. . . .
. . . .
88
88
88
13 N P -Complete Problems
13.2 . .
13.4 . .
13.6 . .
13.8 . .
13.10 .
13.12 .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
89
89
91
91
91
91
13.14 . . .
13.16 . . .
13.18 . . .
13.20 . . .
13.21 . . .
13.23 . . .
. .
. .
. .
. .
. .
. .
92
92
92
93
93
93
13.26 .
13.28 .
13.30 .
13.32 .
13.34 .
13.35 .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
93
93
94
94
96
96
13.37 . . .
13.39 . . .
13.42 . . .
13.44 . . .
13.47 . . .
13.49 . . .
. .
. .
. .
. .
. .
. .
51
59
59
59
60
60
61
63
67
67
67
69
72
73
78
79
81
86
87
89
96
96
98
99
99
99
List of Solved Exercises
v
13.51 .
13.53 .
. . . .
99
. . . . 100
13.54 . . .
13.55 . . .
. . 100
. . 100
13.57 .
13.59 .
. . . . 100
. . . . 101
13.61 . . .
. . 101
14 Parallel Algorithms
14.2 . .
14.4 . .
14.5 . .
14.7 . .
14.8 . .
. . . . 103
. . . . 103
. . . . 103
. . . . 104
. . . . 104
14.10 . . .
14.11 . . .
14.13 . . .
14.14 . . .
14.16 . . .
. . 104
. . 104
. . 104
. . 105
. . 105
14.18 .
14.19 .
14.20 .
14.22 .
14.24 .
. . . . 105
. . . . 106
. . . . 106
. . . . 106
. . . . 106
103
14.25 . . .
14.27 . . .
14.29 . . .
14.30 . . .
14.32 . . .
. . 106
. . 107
. . 107
. . 108
. . 108
vi
List of Solved Exercises
Analyzing Algorithms and Problems: Principles and Examples
Chapter 1
Section 1.2:
Java as an Algorithm Language
1.1
It is correct for instance fields whose type is an inner class to be declared before that inner class (as in Figure 1.2 in
the text) or after (as here). Appendix A.7 gives an alternative to spelling out all the instance fields in the copy methods
(functions).
class Personal
f
public static class Name
f
String firstName;
String middleName;
String lastName;
public static Name copy(Name n)
f
Name n2;
n2.firstName = n.firstName;
n2.middleName = n.middleName;
n2.lastName = n.lastName;
return n2;
g
g
public static class Address
f
String street;
String city;
String state;
public static Address copy(Address a) f/* similar to Name.copy() */ g
g
public static class PhoneNumber
f
int areaCode;
int prefix;
int number;
public static PhoneNumber copy(PhoneNumber n) f/* similar to Name.copy() */ g
g
Name name;
Address address;
PhoneNumber phone;
String eMail;
public static Personal copy(Personal p);
f
Personal p2;
p2.name = Name.copy(p.name);
p2.address = Address.copy(p.address);
p2.phone = PhoneNumber.copy(p.phone);
p2.eMail = p.eMail;
return p2;
g
g
2
Chapter 1 Analyzing Algorithms and Problems: Principles and Examples
Section 1.3: Mathematical Background
1.2
For 0 < k < n, we have
n 1
k =
n 1
k 1 =
Add them giving:
n 1!n k
=
n 1!
k!n 1 k!
n 1!
k 1!n k!
k!n k!
n 1!k
k!n k!
=
k
= n
n 1!n
k!n k!
k 1 and n
k = 0 in all these cases. If n < k, n 1
For 0 < n k we use the fact that a
the whole set.) Thus n 1
n 1
k 1 and n
b = 0 whenever a < b. (There is no way to choose more elements than there are in
k are both 0, confirming the equation. If n = k,
k are both 1, again confirming the equation. (We need the fact that 0! = 1 when n = k = 1.)
1.4
It suffices to show:
Consider b raised to each side.
So left side = right side.
logc xlogb c = logb x:
bleft side = blogb clogc x = blogb clogc x = clogc x = x
bright side = blogb x = x
1.6
Let x = dlgn 1e. The solution is based on the fact that 2x 1 < n 1 2x.
x = 0;
twoToTheX = 1;
while (twoToTheX < n+1)
x += 1;
twoToTheX *= 2;
return x;
The values computed by this procedure for small n and the approximate values of lgn 1 are:
n
0
1
2
3
4
5
6
7
8
9
x
0
1
2
2
3
3
3
3
4
4
lgn 1
0.0
1.0
1.6
2.0
2.3
2.6
2.8
3.0
3.2
3.3
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
