【正文】 An ADT for twodimensional arrays might look as follows. Matrix add(Matrix M1, Matrix M2)。 // Compare two strings: the normal C++ strcmp function. Some // convention should be indicated for how to interpret the // return value. In C++, this is 1 for s1s2。 // Extract a substring, starting at ‘start’, // and of length ‘length’ String extract(String s1, int start, int length)。Data Structures and Algorithm 習(xí)題答案Preface ii 1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17 4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46 8 File Processing and External Sorting 54 9Searching 58 10 Indexing 64 11 Graphs 69 12 Lists and Arrays Revisited 76 13 Advanced Tree Structures 82 i ii Contents 14 Analysis Techniques 88 15 Limits to Computation 94 Preface Contained 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 problems requiring an algorithm I have given actual code. In a few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been piled and tested. While I believe the algorithms to be essentially correct, there may be errors in syntax as well as semantics. Most importantly, these solutions provide a guide to the instructor as to the intended answer, rather than usable programs. 1 Data Structures and Algorithms Instructor’s note: Unlike the other chapters, many of the questions in this chapter are not really suitable for graded work. The questions are mainly intended to get students thinking about data structures issues. This 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.” This exercise asks the student to expand on their concept of an integer representation. A good answer is described by Project , where a singlylinked list is suggested. The most straightforward implementation stores each digit in its own list node, with digits stored in reverse order. Addition and multiplication are implemented by what amounts to gradeschool arithmetic. For addition, simply march down in parallel through the two lists representing the operands, at each digit appending to a new list the appropriate partial sum and bringing forward a carry bit as necessary. For multiplication, bine the addition function with a new function that multiplies a single digit by an integer. Exponentiation can be done either by repeated multiplication (not really practical) or by the traditional Θ(log n)time algorithm based on the binary representation of the exponent. Discovering this faster algorithm will be beyond the reach of most students, so should not be required. A 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 strings String strcat(String s1, String s2)。 // Return the length of a string int length(String s1)。 // Get the first character char first(String s1)。 0 for s1=s2。 Matrix multiply(Matrix M1, Matrix M2)。 void setvalue(Matrix M1, int row, int col, int val)。 List getrow(Matrix M1, int row)。 for (int i=0。 i++) if (S[i] == ’(’) count++。 count。 else return FALSE。 int count = 0。 ilength(S)。 if (S[i] == ’)’) { if (()) return i。 } } if (()) return 1。 } Answers to this question are discussed in Section . This is somewhat different from writing sorting algorithms for a puter, since person’s “working space” is typically limited, as is their ability to physically manipulate the pieces of paper. Nonetheless, many of the mon sorting algorithms have their analogs to solutions for this problem. Most typical answers will be insertion sort, variations on mergesort, and variations on binsort. Answers to this question are discussed in Chapter 8. 2 Mathematical Preliminaries (a) Not reflexive if the set has any members. One could argue it is symmetric, antisymmetric, and transitive, since no element violate any of the rules. (b) Not reflexive (for any female). 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 antisymmetric. Transitive, but vacuously so (there can be no distinct a, b,and c where aRb and bRc). (e) Reflexive. Symmetric, so not antisymmetric. Transitive (but sort of vacuous). (f) Reflexive – check all the cases. Since it is only true when x = y,it is technically symmetric and antisymmetric, but rather vacuous. Likewise, it is technically transitive, but vacuous. In general, prove that something is an equivalence relation by proving that it is reflexive, symmetric, and transitive. (a) This is an equivalence that effectively splits the integers into odd and even sets. It is reflexive (x + x is even for any 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 nonzero rational numbers into positive and negative. It is reflexive since x ˙x 0. It is symmetric since xy˙ = yx˙. It is transitive since any two members of the given class satisfy the relationship. 5 Chap. 2 Mathematical Preliminaries