數(shù)據(jù)結(jié)構(gòu)與算法分析C++版答案

1、.Data Structures and Algorithm習(xí)題答案Preface ii1 Data Structures and Algorithms 12 Mathematical Preliminaries 53 Algorithm Analysis 174 Lists, Stacks, and Queues 235 Binary Trees 326 General Trees 407 Internal Sorting 468 File Processing and External Sorting 549Searching 5810 Indexing 6411 Graphs 6912

2、Lists and Arrays Revisited 7613 Advanced Tree Structures 82i.ii Contents14 Analysis Techniques 8815 Limits to Computation 94.PrefaceContained herein are the solutions to all exercises from the textbook A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition.For most of the pr

3、oblems requiring an algorithm I have given actual code. Ina few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been compiled and tested. While I believe the algorithmsto be essentially correct, there may be errors in syntax as well as seman

4、tics. Most importantly, these solutions provide a guide to the instructor as to the intendedanswer, rather than usable programs.1Data Structures and AlgorithmsInstructor s note: Unlike the other chapters, many of the questions in this chapter are not really suitable for graded work. The questions ar

5、e mainly intended to getstudents thinking about data structures issues.1.1This question does not have a specific right answer, provided the student keeps to the spirit of the question. Students may have trouble with the concept of “operations. ”1.2This exercise asks the student to expand on their co

6、ncept of an integer representation.A good answer is described by Project 4.5, where a singly-linkedlist is suggested. The most straightforward implementation stores each digitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplicationare implemented by what amounts to grade-school arit

7、hmetic. Foraddition, simply march down in parallel through the two lists representingthe operands, at each digit appending to a new list the appropriate partialsum and bringing forward a carry bit as necessary. For multiplication, combinethe addition function with a new function that multiplies a si

8、ngle digitby an integer. Exponentiation can be done either by repeated multiplication(notreally practical) or by the traditional(log n)-time algorithm based onthe binary representation of the exponent. Discovering this faster algorithm will be beyond the reach of most students, so should not be requ

9、ired.1.3A sample ADT for character strings might look as follows (with the normal interpretation of the function names assumed).Chap. 1 Data Structures and Algorithms/ Concatenate two stringsString strcat(String s1, String s2);/ Return the length of a string int length(String s1);/ Extract a substri

10、ng, starting atstart ,/ and of lengthlength String extract(String s1, int start, int length);/ Get the first character char first(String s1);/ Compare two strings: the normal C+ strcmp function. Some/ convention should be indicated for how to interpretthe/ return value. In C+, this is 1 for s1<s2

11、; 0 for s1=s2;/ and 1 for s1> strcmp(String s1, String s2)/ Copy a stringint strcpy(String source, String destination)1.4The answer to this question is provided by the ADT for lists given in Chapter4.1.5Ones compliment stores the binary representation of positive numbers, andstores the bina

12、ry representation of a negative number with the bits inverted.Twos compliment isthe same, except that a negative number has its bitsinvertedandthenoneisadded(forreasonsofefficiencyinhardwareimplementation).This representation is the physical implementation of an ADT.defined by the normal arithmetic

13、operations, declarations, and other support given by the programming language for integers.1.6An ADT for two-dimensional arrays might look as follows.Matrix add(Matrix M1, Matrix M2);Matrix multiply(Matrix M1, Matrix M2);Matrix transpose(Matrix M1);void setvalue(Matrix M1, int row, int col, int val)

14、;int getvalue(Matrix M1, int row, int col);List getrow(Matrix M1, int row);.One implementation for the sparse matrix is described in Section 12.3 Another implementationis a hash table whose search key is a concatenation of the matrix coordinates.1.7Every problem certainly does not have an algorithm.

15、 As discussed in Chapter 15,there are a number of reasons why this might be the case. Some problems donthave a sufficiently clear definition. Some problems, such as the halting problem,are non-computable.For some problems,such as one typicallystudied by artificialintelligence researchers, we simply

16、dont know a solution.1.8We must assume that by“algorithm” we mean something composed of steps areof a nature that they can be performed by a computer. If so, than any algorithmcan be expressed in C+. In particular, if an algorithm can be expressed in anyother computer programming language, then it c

17、an be expressed in C+, since all(sufficiently general) computer programming languages compute the same set offunctions.1.9The primitiveoperationsare(1) addingnew words tothe dictionaryand (2)searchingthe dictionary for a given word. Typically, dictionary access involves some sortof pre- processing o

18、f the word to arrive at the“root ” of the word.A twenty page document (single spaced) is likely to contain about 20,000 words. Auser may be willingto wait a few seconds between individual“hits” of mis -spelledwords, or perhaps up to a minute for the whole document to be processed. Thismeans that a c

19、heck for an individual word can take about 10-20 ms. Users willtypicallyinsertindividualwords into thedictionaryinteractively,so this processcantake a couple of seconds. Thus,search must bemuch more efficient thaninsertion.1.10The user should be able to find a city based on a variety of attributes (

20、name,location,perhaps characteristics such as population size). The user should also be able toinsertand delete cities. These are the fundamental operations of any database system:search, insertion and deletion.A reasonable database has a time constraint that will satisfy the patience of atypicaluse

21、r. For an insert, delete, or exact match query, a few seconds is satisfactory.If thedatabaseismeant tosupportrangequeriesand mass deletions,theentireoperationmay be allowed to take longer, perhaps on the order of a minute. However, the timespent toprocessindividualcitieswithintherangemust be appropr

22、iatelyreduced.Inpractice, the data representation will need to be such that it accommodates efficient processing to meet these time constraints. In particular, it may be necessary tosupportoperations that process range queries efficiently by processing all cities in the range as a batch, rather than

23、 as a series of operations on individual cities.1.11Students at this level are likely already familiar with binary search. Thus, they should typically respond with sequential search and binary search. Binary search should be described as better since it typically needs to make fewer comparisons (and

24、 thus is likely to be much faster).1.12The answer to this question is discussed in Chapter 8. Typical measures of cost will be number of comparisons and number of swaps. Tests should include running timings on sorted, reverse sorted, and random lists of various sizes.Chap. 1 Data Structures and Algo

25、rithms1.13The first part is easy with the hint, but the second part is rather difficult to do withouta stack.a) bool checkstring(string S) int count = 0;for (int i=0; i<length(S); i+)if (Si =( ) count+;if (Si =) ) if (count = 0) return FALSE;count-;if (count = 0) return TRUE;else return FALSE;b)

26、int checkstring(String Str) Stack S;int count = 0;for (int i=0; i<length(S); i+)if (Si =( )S.push(i);if (Si =) ) if (S.isEmpty() return i;S.pop();.if (S.isEmpty() return -1;else return S.pop();1.14Answers to this question are discussed in Section 5This is somewhat different from writing so

27、rting algorithms for a computer, sinceperson s “workingspace” is typicallylimited,as istheirabilityto physicallymanipulatethe pieces of paper. Nonetheless, many of the common sorting algorithms havetheiranalogsto solutionsforthisproblem.Most typicalanswers willbe insertionsort, variations on mergeso

28、rt, and variations on binsort.1.16Answers to this question are discussed in Chapter 8.2Mathematical Preliminaries2.1(a) Not reflexive if the set has any members. One could argue it is symmetric, antisymmetric, and transitive, since no element violate any ofthe rules.(b)Not reflexive (for any female)

29、. Not symmetric (consider a brother and sister). Not antisymmetric (consider two brothers). Transitive (for any 3 brothers).(c)Not reflexive. Not symmetric, and is antisymmetric. Not transitive (only goes one level).(d)Not reflexive (for nearly all numbers). Symmetric since a+ b = b+ a,so not antisy

30、mmetric. Transitive, but vacuously so (there can be no distinct a, b,and cwhere aRband bRc).(e)Reflexive. Symmetric, so not antisymmetric. Transitive (but sort ofvacuous).(f)Reflexive check all the cases. Since it is only true when x = y,itis technically symmetric and antisymmetric, but rather vacuo

31、us. Likewise, it is technically transitive, but vacuous.2.2In general, prove that something is an equivalence relation by proving that itis reflexive, symmetric, and transitive.(a)This is an equivalence that effectively splits the integers into odd andeven sets. It is reflexive (x+ xis even for any

32、integer x), symmetric(since x+ y = y.+ x) and transitive (since you are always adding two odd or even numbers for any satisfactory a, b,and c).(b)This is not an equivalence. To begin with, it is not reflexive for any integer.(c)This is an equivalence that divides the non-zero rational numbers into p

33、ositive and negative. It is reflexive since xx>0. It is symmetric sincexy= yx . It is transitive since any two members of the given class satisfy the relationship.5.Chap. 2 Mathematical Preliminaries(d)This is not an equivalance relation since it is not symmetric. For example, a=1and b=2.(e)This

34、is an eqivalance relation that divides the rationals based on their fractional values. It is reflexive since for all a, a.a =0. It is symmetricsince if a.b=xthen b.a=.x. It is transitive since any two rationalswith the same fractional value will yeild an integer.(f)This is not an equivalance relatio

35、n since it is not transitive. For example,4.2=2and 2.0=2,but 4.0=4.2.3A relation is a partial ordering if it is antisymmetric and transitive.(a)Not a partial ordering because it is not transitive.(b)Is a partial ordering bacause it is antisymmetric (if ais an ancestor ofb, then bcannot be an ancesto

36、r of a) and transitive (since the ancestor of an ancestor is an ancestor).(c)Is a partial ordering bacause it is antisymmetric (if ais older than b,then bcannot be older than a) and transitive (since if ais older than band bis older than c, ais older than c).(d)Not a partial ordering, since it is no

37、t antisymmetric for any pair of sisters.(e)Not a partial ordering because it is not antisymmetric.(f)This is a partial ordering. It is antisymmetric (no violations exist) and transitive (no violations exist).2.4A total ordering can be viewed as a permuation of the elements. Since there are n!permuat

38、ions of nelements, there must be n!total orderings.2.5This proposed ADT is inspired by the list ADT of Chapter 4.void clear();void insert(int);void remove(int);void sizeof();bool isEmpty();bool isInSet(int);2.6This proposed ADT is inspired by the list ADT of Chapter 4. Note that while it is similiar

39、 to the operations proposed for Question 2.5, the behaviour is somewhat different.void clear();void insert(int);void remove(int);void sizeof();.7bool isEmpty();/ Return the number of elements with a given valueint countInBag(int);2.7The list class ADT from Chapter 4 is a sequence.2.8long ifact(int n

40、) / make n <= 12 so n! for long intlong fact = 1;Assert(n >= 0) && (n <= 12), "Input out of range");for (int i=1; i<= n; i+)fact = fact * i;return fact;2.9void rpermute(int *array, int n) swap(array, n-1, Random(n);rpermute(array, n-1);2.10(a) Most people will find the

41、recursive form natural and easy to understand. The iterative version requires careful examination to understand whatit does, or to have confidence that it works as claimed.(b)Fibr is so much slower than Fibi because Fibr re-computes the bulk of the series twice to get the two values to add. What is

42、much worse, the recursive calls to compute the subexpressions also re-compute the bulk of the series, and do so recursively. The result is an exponential explosion. In contrast, Fibicomputes each value in the seriesexactly once, and so its running time is proportional to n. 2.11/ Array curri indicat

43、es current position of ring i.void GenTOH(int n, POLE goal, POLE t1, POLE t2,POLE* curr) if (currn = goal) / Get top n-1 rings set upGenTOH(n-1, goal, t1, t2, curr);.else if (currn = t1) swap(t1, t2); / Get names right/ Now, ring n is on pole t2. Put others on t1.GenTOH(n-1, t1, goal, t2, curr);move

44、(t2, goal);GenTOH(n-1, goal, t1, t2, curr); / Move n-1 back2.12At each step of the way, the reduction toward the base case is only half as far as the previous time. In theory, this series approaches, but never reaches, 0, so it will go on forever. In practice, the value should become computationally

45、 indistinguishable from zero, and terminate. However, this is terrible programming practice.Chap. 2 Mathematical Preliminaries2.13void allpermute(int array, int n, int currpos) if (currpos = (n-1) printout(array);return;for (int i=currpos; i<n; i+) swap(array, currpos, i);allpermute(array, n, cur

46、rpos+1);swap(array, currpos, i); / Put back for next pass2.14In the following, function bitposition(n, i) returns the value (0 or1) at the ith bit position of integer value n. The idea is the print out the elements at the indicated bit positions within the set. If we do this for values in the range 0 to 2n.1, we will get the entire powerset. void powerset(int n) for (int i=0; i<ipow(2, n); i+) for (int j=0; j<n; j+)if (bitposition(n, j)