没有合适的资源?快使用搜索试试~ 我知道了~
Data Structures and Algorithm Analysis in C(Second Edition) Solu...
5星 · 超过95%的资源 需积分: 13 218 下载量 71 浏览量
2012-08-07
22:20:53
上传
评论 2
收藏 298KB PDF 举报
温馨提示
试读
69页
Data Strutures and Algorithm Analysis in C Second Edtion Solution Manual Mark Allen Weiss Florida International University Included in this manual are answers to most of the exercises in the textbook Data Structures and Algorithm Analysis in C, second edition, published by Addison-Wesley.
资源推荐
资源详情
资源评论
Data Structures
and
Algorithm Analysis in C
Second Edition
Solutions Manual
Mark Allen Weiss
Florida International University
Preface
Included in this manual are answers to most of the exercises in the textbook Data Structures and
Algorithm Analysis in C, second edition, published by Addison-Wesley. These answers reflect
the state of the book in the first printing.
Specifically omitted are likely programming assignments and any question whose solu-
tion is pointed to by a reference at the end of the chapter. Solutions vary in degree of complete-
ness; generally, minor details are left to the reader. For clarity, programs are meant to be
pseudo-C rather than completely perfect code.
Errors can be reported to weiss@fiu.edu. Thanks to Grigori Schwarz and Brian Harvey
for pointing out errors in previous incarnations of this manual.
Table of Contents
1. Chapter 1: Introduction ...................................................................................................... 1
2. Chapter 2: Algorithm Analysis .......................................................................................... 4
3. Chapter 3: Lists, Stacks, and Queues ................................................................................. 7
4. Chapter 4: Trees ................................................................................................................. 14
5. Chapter 5: Hashing ............................................................................................................ 25
6. Chapter 6: Priority Queues (Heaps) ................................................................................... 29
7. Chapter 7: Sorting ..............................................................................................................36
8. Chapter 8: The Disjoint Set ADT ....................................................................................... 42
9. Chapter 9: Graph Algorithms ............................................................................................. 45
10. Chapter 10: Algorithm Design Techniques ...................................................................... 54
11. Chapter 11: Amortized Analysis ...................................................................................... 63
12. Chapter 12: Advanced Data Structures and Implementation ............................................ 66
-iii-
Chapter 1: Introduction
1.3 Because of round-off errors, it is customary to specify the number of decimal places that
should be included in the output and round up accordingly. Otherwise, numbers come out
looking strange. We assume error checks have already been performed; the routine
Separate
O
is left to the reader. Code is shown in Fig. 1.1.
1.4 The general way to do this is to write a procedure with heading
void ProcessFile( const char *FileName );
which opens FileName,
O
does whatever processing is needed, and then closes it. If a line of
the form
#include SomeFile
is detected, then the call
ProcessFile( SomeFile );
is made recursively. Self-referential includes can be detected by keeping a list of files for
which a call to ProcessFile
O
has not yet terminated, and checking this list before making a
new call to ProcessFile.
O
1.5 (a) The proof is by induction. The theorem is clearly true for 0 < X
O
≤ 1, since it is true for
X
O
= 1, and for X
O
< 1, log X
O
is negative. It is also easy to see that the theorem holds for
1 < X
O
≤ 2, since it is true for X
O
= 2, and for X
O
< 2, log X
O
is at most 1. Suppose the theorem
is true for p
O
< X
O
≤ 2p
O
(where p
O
is a positive integer), and consider any 2p
O
< Y
O
≤ 4p
O
(p
O
≥ 1). Then log Y
O
= 1 + log (Y
O
/ 2) < 1 + Y
O
/ 2 < Y
O
/ 2 + Y
O
/ 2 ≤ Y
O
, where the first ine-
quality follows by the inductive hypothesis.
(b) Let 2
X
O
= A
O
. Then A
O
B
O
= (2
X
O
)
B
O
= 2
XB
O
. Thus log A
O
B
O
= XB
O
. Since X
O
= log A
O
, the
theorem is proved.
1.6 (a) The sum is 4/3 and follows directly from the formula.
(b) S
O
=
4
1
__
+
4
2
2
___
+
4
3
3
___
+
. . .
.4S
O
= 1+
4
2
__
+
4
2
3
___
+
. . .
. Subtracting the first equation from
the second gives 3S
O
= 1 +
4
1
__
+
4
2
2
___
+
. . .
. By part (a), 3S
O
= 4/ 3soS
O
= 4/ 9.
(c) S
O
=
4
1
__
+
4
2
4
___
+
4
3
9
___
+
. . .
.4S
O
= 1 +
4
4
__
+
4
2
9
___
+
4
3
16
__ _
+
. . .
. Subtracting the first equa-
tion from the second gives 3S
O
= 1+
4
3
__
+
4
2
5
___
+
4
3
7
___
+
. . .
. Rewriting, we get
3S
O
= 2
i
O
=0
Σ
∞
4
i
O
i
___
+
i
O
=0
Σ
∞
4
i
O
1
___
. Thus 3S
O
= 2(4/ 9) + 4/ 3 = 20/ 9. Thus S
O
= 20/ 27.
(d) Let S
N
O
=
i
O
=0
Σ
∞
4
i
O
i
O
N
O
__ _
. Follow the same method as in parts (a) - (c) to obtain a formula for S
N
O
in terms of S
N
O
−1
, S
N
O
−2
, ..., S
O
0
and solve the recurrence. Solving the recurrence is very
difficult.
-1-
_______________________________________________________________________________
_______________________________________________________________________________
double RoundUp( double N, int DecPlaces )
{
int i;
double AmountToAdd = 0.5;
for( i = 0; i < DecPlaces; i++ )
AmountToAdd /= 10;
return N + AmountToAdd;
}
void PrintFractionPart( double FractionPart, int DecPlaces )
{
int i, Adigit;
for( i = 0; i < DecPlaces; i++ )
{
FractionPart *= 10;
ADigit = IntPart( FractionPart );
PrintDigit( Adigit );
FractionPart = DecPart( FractionPart );
}
}
void PrintReal( double N, int DecPlaces )
{
int IntegerPart;
double FractionPart;
if( N < 0 )
{
putchar(’-’);
N = -N;
}
N = RoundUp( N, DecPlaces );
IntegerPart = IntPart( N ); FractionPart = DecPart( N );
PrintOut( IntegerPart ); /* Using routine in text */
if( DecPlaces > 0 )
putchar(’.’);
PrintFractionPart( FractionPart, DecPlaces );
}
Fig. 1.1.
_______________________________________________________________________________
_______________________________________________________________________________
1.7
i
O
=
OI
N
O
/ 2
OK
Σ
N
i
1
__
=
i
O
=1
Σ
N
i
1
__
−
i
O
=1
Σ
OI
N
O
/ 2 − 1
OK
i
1
__
∼
∼
ln N
O
− ln N
O
/ 2
∼
∼
ln 2.
-2-
剩余68页未读,继续阅读
走走—逛逛
- 粉丝: 12
- 资源: 28
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Surfer,线性函数
- MyBatis 的动态 SQL 是其核心特性之一.txt
- 时代的sdddsddsddsd
- 基于哈希链表的简单人员信息管理系统
- 其他类别JdonFramework开源框架 v5.1 Build20071025-jdonframework-5.1.rar
- 2001~2022年上市公司数字赋能指数.dta
- 2001~2022年上市公司数字赋能指数.xlsx
- 信息办公石大在线财务管理系统(含源码)-shidacaiwu.rar
- 信息办公电信计费系统完整代码-netctossconformity.rar
- matlab实现TD-SCDMA中初始同步捕捉DwPTS下行同步导频时隙的仿真.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
- 4
前往页