Ujimatsu Chiya
0%

算法导论（第4版）部分题目解答

目前有计划重新阅读算法导论。以下是本人解答课后习题的一些答案。尽量独立完成，有一部分参考了其他人的解决方案。

如下题目仍有待思考（没想出来，或者是证明出来的结论和书上的不一样）：

1
2
3
4
5
6
7
8
9
6.4-4
6.4-5
16-4
32-1-b
32-1-c
33.2-3
33.2-4
33-1-b
33-2

Chapter 1

Exercise 1 1.1-1 1.1-2 1.1-3 1.1-4 1.1-5 1.1-6
Exercise 2 1.2-1 1.2-2 1.2-3
Problems 1-1

Chapter 2

Exercise 1 2.1-1 2.1-2 2.1-3 2.1-4 2.1-5
Exercise 2 2.2-1 2.2-2 2.2-3 2.2-4
Exercise 3 2.3-1 2.3-2 2.3-3 2.3-4 2.3-5 2.3-6 2.3-7 2.3-8
Problems 2-1 2-2 2-3 2-4

Chapter 3

Exercise 1 3.1-1 3.1-2 3.1-3
Exercise 2 3.2-1 3.2-2 3.2-3 3.2-4 3.2-5 3.2-6 3.2-7
Exercise 3 3.3-1 3.3-2 3.3-3 3.3-4 3.3-5 3.3-6 3.3-7 3.3-8 3.3-9
Problems 3-1 3-2 3-3 3-4 3-5 3-6 3-7

Chapter 4

Exercise 1 4.1-1 4.1-2 4.1-3 4.1-4
Exercise 2 4.2-1 4.2-2 4.2-3 4.2-4 4.2-5 4.2-6
Exercise 3 4.3-1 4.3-2 4.3-3
Exercise 4 4.4-1 4.4-2 4.4-3 4.4-4
Exercise 5 4.5-1 4.5-2 4.5-3 4.5-4 4.5-5
Exercise 6 4.6-1 4.6-2 4.6-3
Exercise 7 4.7-1 4.7-2 4.7-3 4.7-4 4.7-5 4.7-6
Problems 4-1 4-2 4-3 4-4 4-5 4-6 4-7

Chapter 5

Exercise 1 5.1-1 5.1-2 5.1-3
Exercise 2 5.2-1 5.2-2 5.2-3 5.2-4 5.2-5 5.2-6
Exercise 3 5.3-1 5.3-2 5.3-3 5.3-4 5.3-5
Exercise 4 5.4-1 5.4-2 5.4-3 5.4-4 5.4-5 5.4-6 5.4-7 5.4-8
Problems 5-1 5-2

Chapter 6

Exercise 1 6.1-1 6.1-2 6.1-3 6.1-4 6.1-5 6.1-6 6.1-7 6.1-8
Exercise 2 6.2-1 6.2-2 6.2-3 6.2-4 6.2-5 6.2-6 6.2-7
Exercise 3 6.3-1 6.3-2 6.3-3 6.3-4
Exercise 4 6.4-1 6.4-2 6.4-3
Exercise 5 6.5-1 6.5-2 6.5-3 6.5-4 6.5-5 6.5-6 6.5-7 6.5-8 6.5-9 6.5-10 6.5-11
Problems 6-1 6-2 6-3

Chapter 7

Exercise 1 7.1-1 7.1-2 7.1-3 7.1-4
Exercise 2 7.2-1 7.2-2 7.2-3 7.2-4 7.2-5 7.2-6
Exercise 3 7.3-1 7.3-2
Exercise 4 7.4-1 7.4-2 7.4-3 7.4-4 7.4-5 7.4-6
Problems 7-1 7-2 7-3 7-4 7-5 7-6 7-7

Chapter 8

Exercise 1 8.1-1 8.1-2 8.1-3 8.1-4
Exercise 2 8.2-1 8.2-2 8.2-3 8.2-4 8.2-5 8.2-6 8.2-7
Exercise 3 8.3-1 8.3-2 8.3-3 8.3-4 8.3-5 8.3-6
Exercise 4 8.4-1 8.4-2 8.4-3 8.4-4 8.4-5 8.4-6
Problems 8-1 8-2 8-3 8-4 8-5 8-6 8-7

Chapter 9

Exercise 1 9.1-1 9.1-2 9.1-3 9.1-4
Exercise 2 9.2-1 9.2-2 9.2-3 9.2-4
Exercise 3 9.3-1 9.3-2 9.3-3 9.3-4 9.3-5 9.3-6 9.3-7 9.3-8 9.3-9 9.3-10
Problems 9-1 9-2 9-3 9-4 9-5 9-6

Chapter 10

Exercise 1 10.1-1 10.1-2 10.1-3 10.1-4 10.1-5 10.1-6 10.1-7 10.1-8
Exercise 2 10.2-1 10.2-2 10.2-3 10.2-4 10.2-5 10.2-6
Exercise 3 10.3-1 10.3-2 10.3-3 10.3-4 10.3-5 10.3-6
Problems 10-1 10-2 10-3

Chapter 11

Exercise 1 11.1-1 11.1-2 11.1-3 11.1-4
Exercise 2 11.2-1 11.2-2 11.2-3 11.2-4 11.2-5 11.2-6
Exercise 3 11.3-1 11.3-2 11.3-3 11.3-4 11.3-5 11.3-6
Exercise 4 11.4-1 11.4-2 11.4-3 11.4-4 11.4-5 11.4-6
Exercise 5 11.5-1 11.5-2 11.5-3
Problems 11-1 11-2 11-3 11-4

Chapter 12

Exercise 1 12.1-1 12.1-2 12.1-3 12.1-4 12.1-5
Exercise 2 12.2-1 12.2-2 12.2-3 12.2-4 12.2-5 12.2-6 12.2-7 12.2-8 12.2-9
Exercise 3 12.3-1 12.3-2 12.3-3 12.3-4 12.3-5 12.3-6
Problems 12-1 12-2 12-3 12-4

Chapter 13

Exercise 1 13.1-1 13.1-2 13.1-3 13.1-4 13.1-5 13.1-6 13.1-7 13.1-8
Exercise 2 13.2-1 13.2-2 13.2-3 13.2-4 13.2-5
Exercise 3 13.3-1 13.3-2 13.3-3 13.3-4 13.3-5 13.3-6
Exercise 4 13.4-1 13.4-2 13.4-3 13.4-4 13.4-5 13.4-6 13.4-7 13.4-8 13.4-9
Problems 13-1 13-2 13-3

Chapter 14

Exercise 1 14.1-1 14.1-2 14.1-3 14.1-4 14.1-5 14.1-6
Exercise 2 14.2-1 14.2-2 14.2-3 14.2-4 14.2-5 14.2-6
Exercise 3 14.3-1 14.3-2 14.3-3 14.3-4 14.3-5
Exercise 4 14.4-1 14.4-2 14.4-3 14.4-4 14.4-5 14.4-6
Exercise 5 14.5-1 14.5-2 14.5-3 14.5-4
Problems 14-1 14-2 14-3 14-4 14-5 14-6 14-7 14-8 14-9 14-10 14-11 14-12

Chapter 15

Exercise 1 15.1-1 15.1-2 15.1-3 15.1-4 15.1-5
Exercise 2 15.2-1 15.2-2 15.2-3 15.2-4 15.2-5 15.2-6 15.2-7
Exercise 3 15.3-1 15.3-2 15.3-3 15.3-4 15.3-5 15.3-6 15.3-7 15.3-8
Exercise 4 15.4-1 15.4-2 15.4-3 15.4-4
Problems 15-1 15-2

Chapter 16

Exercise 1 16.1-1 16.1-2 16.1-3
Exercise 2 16.2-1 16.2-2 16.2-3
Exercise 3 16.3-1 16.3-2 16.3-3 16.3-4 16.3-5 16.3-6
Exercise 4 16.4-1 16.4-2 16.4-3 16.4-4
Problems 16-1 16-2 16-3

Chapter 17

Exercise 1 17.1-1 17.1-2 17.1-3 17.1-4 17.1-5 17.1-6 17.1-7 17.1-8
Exercise 2 17.2-1 17.2-2 17.2-3
Exercise 3 17.3-1 17.3-2 17.3-3 17.3-4 17.3-5 17.3-6
Problems 17-1 17-2

Chapter 18

Exercise 1 18.1-1 18.1-2 18.1-3 18.1-4 18.1-5
Exercise 2 18.2-1 18.2-2 18.2-3 18.2-4 18.2-5 18.2-6 18.2-7
Exercise 3 18.3-1 18.3-2
Problems 18-1 18-2

Chapter 19

Exercise 1 19.1-1 19.1-2 19.1-3
Exercise 2 19.2-1 19.2-2 19.2-3 19.2-4 19.2-5 19.2-6
Exercise 3 19.3-1 19.3-2 19.3-3 19.3-4 19.3-5
Exercise 4 19.4-1 19.4-2 19.4-3 19.4-4 19.4-5 19.4-6 19.4-7
Problems 19-1 19-2 19-3

Chapter 20

Exercise 1 20.1-1 20.1-2 20.1-3 20.1-4 20.1-5 20.1-6 20.1-7 20.1-8
Exercise 2 20.2-1 20.2-2 20.2-3 20.2-4 20.2-5 20.2-6 20.2-7 20.2-8
Exercise 3 20.3-1 20.3-2 20.3-3 20.3-4 20.3-5 20.3-6 20.3-7 20.3-8 20.3-9 20.3-10 20.3-11 20.3-12 20.3-13
Exercise 4 20.4-1 20.4-2 20.4-3 20.4-4 20.4-5
Exercise 5 20.5-1 20.5-2 20.5-3 20.5-4 20.5-5 20.5-6 20.5-7 20.5-8
Problems 20-1 20-2 20-3 20-4 20-5

Chapter 21

Exercise 1 21.1-1 21.1-2 21.1-3 21.1-4 21.1-5 21.1-6 21.1-7 21.1-8 21.1-9 21.1-10 21.1-11
Exercise 2 21.2-1 21.2-2 21.2-3 21.2-4 21.2-5 21.2-6 21.2-7 21.2-8
Problems 21-1 21-2 21-3 21-4

Chapter 22

Exercise 1 22.1-1 22.1-2 22.1-3 22.1-4 22.1-5 22.1-6 22.1-7
Exercise 2 22.2-1 22.2-2 22.2-3 22.2-4
Exercise 3 22.3-1 22.3-2 22.3-3 22.3-4 22.3-5 22.3-6 22.3-7 22.3-8 22.3-9 22.3-10 22.3-11 22.3-12
Exercise 4 22.4-1 22.4-2 22.4-3 22.4-4 22.4-5 22.4-6 22.4-7 22.4-8 22.4-9 22.4-10 22.4-11 22.4-12
Exercise 5 22.5-1 22.5-2 22.5-3 22.5-4 22.5-5 22.5-6 22.5-7 22.5-8
Problems 22-1 22-2 22-3 22-4 22-5 22-6

Chapter 23

Exercise 1 23.1-1 23.1-2 23.1-3 23.1-4 23.1-5 23.1-6 23.1-7 23.1-8 23.1-9 23.1-10
Exercise 2 23.2-1 23.2-2 23.2-3 23.2-4 23.2-5 23.2-6 23.2-7 23.2-8 23.2-9
Exercise 3 23.3-1 23.3-2 23.3-3 23.3-4 23.3-5 23.3-6
Problems 23-1 23-2

Chapter 24

Exercise 1 24.1-1 24.1-2 24.1-3 24.1-4 24.1-5 24.1-6 24.1-7
Exercise 2 24.2-1 24.2-2 24.2-3 24.2-4 24.2-5 24.2-6 24.2-7 24.2-8 24.2-9 24.2-10 24.2-11 24.2-12 24.2-13
Exercise 3 24.3-1 24.3-2 24.3-3
Problems 24-1 24-2 24-3 24-4 24-5 24-6 24-7

Chapter 25

Exercise 1 25.1-1 25.1-2 25.1-3 25.1-4 25.1-5 25.1-6
Exercise 2 25.2-1 25.2-2 25.2-3 25.2-4 25.2-5
Exercise 3 25.3-1 25.3-2 25.3-3 25.3-4 25.3-5 25.3-6 25.3-7
Problems 25-1 25-2 25-3 25-4 25-5

Chapter 26

Exercise 1 26.1-1 26.1-2 26.1-3 26.1-4 26.1-5 26.1-6 26.1-7 26.1-8 26.1-9 26.1-10
Exercise 2 26.2-1 26.2-2 26.2-3 26.2-4 26.2-5
Exercise 3 26.3-1 26.3-2 26.3-3 26.3-4 26.3-5
Problems 26-1 26-2 26-3 26-4 26-5 26-6

Chapter 27

Exercise 1 27.1-1 27.1-2 27.1-3
Exercise 2 27.2-1 27.2-2 27.2-3 27.2-4
Exercise 3 27.3-1 27.3-2 27.3-3 27.3-4 27.3-5
Problems 27-1 27-2

Chapter 28

Exercise 1 28.1-1 28.1-2 28.1-3 28.1-4 28.1-5 28.1-6 28.1-7
Exercise 2 28.2-1 28.2-2 28.2-3 28.2-4 28.2-5
Exercise 3 28.3-1 28.3-2 28.3-3 28.3-4 28.3-5 28.3-6 28.3-7
Problems 28-1 28-2

Chapter 29

Exercise 1 29.1-1 29.1-2 29.1-3 29.1-4 29.1-5 29.1-6 29.1-7 29.1-8
Exercise 2 29.2-1 29.2-2 29.2-3 29.2-4 29.2-5 29.2-6 29.2-7
Exercise 3 29.3-1 29.3-2 29.3-3 29.3-4 29.3-5 29.3-6 29.3-7 29.3-8
Problems 29-1 29-2 29-3 29-4 29-5

Chapter 30

Exercise 1 30.1-1 30.1-2 30.1-3 30.1-4 30.1-5 30.1-6 30.1-7
Exercise 2 30.2-1 30.2-2 30.2-3 30.2-4 30.2-5 30.2-6 30.2-7 30.2-8
Exercise 3 30.3-1 30.3-2 30.3-3 30.3-4 30.3-5
Problems 30-1 30-2 30-3 30-4 30-5

Chapter 31

Exercise 1 31.1-1 31.1-2 31.1-3 31.1-4 31.1-5 31.1-6 31.1-7 31.1-8 31.1-9 31.1-10 31.1-11 31.1-12 31.1-13 31.1-14
Exercise 2 31.2-1 31.2-2 31.2-3 31.2-4 31.2-5 31.2-6 31.2-7 31.2-8 31.2-9
Exercise 3 31.3-1 31.3-2 31.3-3 31.3-4 31.3-5
Exercise 4 31.4-1 31.4-2 31.4-3 31.4-4
Exercise 5 31.5-1 31.5-2 31.5-3 31.5-4
Exercise 6 31.6-1 31.6-2 31.6-3 31.6-4 31.6-5
Exercise 7 31.7-1 31.7-2 31.7-3
Exercise 8 31.8-1 31.8-2 31.8-3
Problems 31-1 31-2 31-3 31-4

Chapter 32

Exercise 1 32.1-1 32.1-2 32.1-3 32.1-4
Exercise 2 32.2-1 32.2-2 32.2-3 32.2-4
Exercise 3 32.3-1 32.3-2 32.3-3 32.3-4 32.3-5 32.3-6
Exercise 4 32.4-1 32.4-2 32.4-3 32.4-4 32.4-5 32.4-6 32.4-7 32.4-8
Exercise 5 32.5-1 32.5-2 32.5-3 32.5-4
Problems 32-1 32-2 32-3

Chapter 33

Exercise 1 33.1-1 33.1-2 33.1-3 33.1-4
Exercise 2 33.2-1 33.2-2
Exercise 3 33.3-1 33.3-2 33.3-3 33.3-4 33.3-5 33.3-6 33.3-7
Problems 33-1 33-3 33-4

Chapter 34

Exercise 1 34.1-1 34.1-2 34.1-3 34.1-4 34.1-5 34.1-6
Exercise 2 34.2-1 34.2-2 34.2-3 34.2-4 34.2-5 34.2-6 34.2-7 34.2-8 34.2-9 34.2-10 34.2-11
Exercise 3 34.3-1 34.3-2 34.3-3 34.3-4 34.3-5 34.3-6 34.3-7 34.3-8
Exercise 4 34.4-1 34.4-2 34.4-3 34.4-4 34.4-5 34.4-6 34.4-7
Exercise 5 34.5-1 34.5-2 34.5-3 34.5-4 34.5-5 34.5-6 34.5-7 34.5-8 34.5-9
Problems 34-1 34-2 34-3 34-4

Chapter 35

Exercise 1 35.1-1 35.1-2 35.1-3 35.1-4 35.1-5
Exercise 2 35.2-1 35.2-2 35.2-3 35.2-4 35.2-5 35.2-6
Exercise 3 35.3-1 35.3-2 35.3-3 35.3-4 35.3-5
Exercise 4 35.4-1 35.4-2 35.4-3 35.4-4
Exercise 5 35.5-1 35.5-2 35.5-3 35.5-4 35.5-5
Problems 35-1 35-2 35-3 35-4 35-5 35-6 35-7

Chapter A

Exercise 1 A.1-1 A.1-2 A.1-3 A.1-4 A.1-5 A.1-6 A.1-7 A.1-8 A.1-9 A.1-10 A.1-11
Exercise 2 A.2-1 A.2-2 A.2-3 A.2-4 A.2-5
Problems A-1

Chapter B

Exercise 1 B.1-1 B.1-2 B.1-3 B.1-4 B.1-5 B.1-6
Exercise 2 B.2-1 B.2-2 B.2-3 B.2-4 B.2-5
Exercise 3 B.3-1 B.3-2 B.3-3 B.3-4
Exercise 4 B.4-1 B.4-2 B.4-3 B.4-4 B.4-5 B.4-6
Exercise 5 B.5-1 B.5-2 B.5-3 B.5-4 B.5-5 B.5-6 B.5-7 B.5-8
Problems B-1 B-2 B-3

Chapter C

Exercise 1 C.1-1 C.1-2 C.1-3 C.1-4 C.1-5 C.1-6 C.1-7 C.1-8 C.1-9 C.1-10 C.1-11 C.1-12 C.1-13 C.1-14 C.1-15 C.1-16
Exercise 2 C.2-1 C.2-2 C.2-3 C.2-4 C.2-5 C.2-6 C.2-7 C.2-8
Exercise 3 C.3-1 C.3-2 C.3-3 C.3-4 C.3-5 C.3-6 C.3-7 C.3-8 C.3-9 C.3-10
Exercise 4 C.4-1 C.4-2 C.4-3 C.4-4 C.4-5 C.4-6 C.4-7 C.4-8 C.4-9 C.4-10
Exercise 5 C.5-1 C.5-2 C.5-3 C.5-4 C.5-5 C.5-6 C.5-7
Problems C-1 C-2

Chapter D

Exercise 1 D.1-1 D.1-2 D.1-3 D.1-4
Exercise 2 D.2-1 D.2-2 D.2-3 D.2-4 D.2-5 D.2-6 D.2-7 D.2-8
Problems D-1 D-2