Data Structures
查看显示器尺寸
and Algorithm Analysis in C
(cond edition)
Solutions Manual
Mark Allen Weiss
Florida International University
Preface
Included in this manual are answers to most of the exercis in the textbook Data Structures and Algorithm Analysis in C,cond edition,published by Addison-Wesley.The answers reflect the state of the book in thefirst printing.
Specifically omitted are likely programming assignments and any question who solu-tion is pointed to by a reference at the end of the chapter.Solutions vary in degree of complete-ness;generally,minor d
金银馒头的做法etails are left to the reader.For clarity,programs are meant to be pudo-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.Chapter1:Introduction (1)
2.Chapter2:Algorithm Analysis (4)
3.Chapter3:Lists,Stacks,and Queues (7)
4.Chapter4:Trees (14)
5.Chapter5:Hashing (25)
6.Chapter6:Priority Queues(Heaps) (29)
7.Chapter7:Sorting (36)
8.Chapter8:The Disjoint Set ADT (42)
9.Chapter9:Graph Algorithms (45)
10.Chapter10:Algorithm Design Techniques (54)
11.Chapter11:Amortized Analysis (63)
12.Chapter12:Advanced Data Structures and Implementation (66)
Chapter 1:Introduction
1.3Becau 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.Otherwi,numbers come out looking strange.We assume error checks have already been performed;the routine Separate 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, does whatever processing is needed,and then clos 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 has not yet terminated,and checking this list before making a new call to ProcessFile.
珀耳修斯1.5(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 e that the theorem holds for 1 < X ≤ 2,since it is true for X = 2,and for X < 2,log X is at most 1.Suppo the theorem is true for p < X ≤ 2p (where p is a positive integer),and 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 ine-quality follows by the inductive hypothesis.农民伯伯乡下
(b)Let 2X = A .Then A B = (2X )B = 2XB .Thus log A B = XB .Since X = log A ,the theorem is proved.
1.6(a)The sum is 4/3and follows directly from the formula.
(b)S = 41__ + 422___ + 433___ + . . . .4S = 1+42__ + 42
3___ + . . . .Subtracting the first equation from the cond gives 3S = 1 + 41__ + 4
22___ + . . . .By part (a),3S = 4/ 3so S = 4/ 9.(c)S = 41__ + 424___ + 439___ + . . . .4S = 1 + 44__ + 429___ + 4316___ + . . . .Subtracting the first equa-tion from the cond gives 3S = 1+43__ + 425___ + 437___ + . . . .Rewriting,we get 3S = 2i =0Σ∞4i i ___ + i =0Σ∞4
i 1___.Thus 3S = 2(4/ 9) + 4/ 3 = 20/ 9.Thus S = 20/ 27.
(d)Let S N = i =0Σ∞4i i N ___.Follow the same method as in parts (a)-(c)to obtain a formula for S N in terms of S N −1,S N −2,...,S 0and solve the recurrence.Solving the recurrence is very difficult.kickasstorrents
36dm_______________________________________________________________________________
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.7i = N / 2 ΣN
i 1__ = i =1ΣN i 1__ − i =1Σ N / 2 − 1 i 1__ ∼∼ ln N − ln N / 2 ∼∼ ln 2.
