数据结构与算法（C++版）课后习题答案（川大）.pdf-资料库

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第1页.png

第1页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第2页.png

第2页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第3页.png

第3页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第4页.png

第4页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第5页.png

第5页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第6页.png

第6页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第7页.png

第7页 / 共101页

7c179f60-9f77-4487-b372-1fa3c360ef83.pdf-第8页.png

第8页 / 共101页

Solutions Manual for A Practical Introduction to Data Structures and Algorithm Analysis Second Edition Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 November 30, 2000 Copyright c2000 by Clifford A. Shaffer.

Contents Preface 1 Data Structures and Algorithms 2 Mathematical Preliminaries 3 Algorithm Analysis 4 Lists, Stacks, and Queues 5 Binary Trees 6 General Trees 7 Internal Sorting 8 File Processing and External Sorting 9 Searching 10 Indexing 11 Graphs 12 Lists and Arrays Revisited 13 Advanced Tree Structures ii 1 5 17 23 32 40 46 54 58 64 69 76 82 i

ii 14 Analysis Techniques 15 Limits to Computation Contents 88 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 compiled and tested. While I believe the algo- rithms 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. iii

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. 1.1 This question does not have a speciﬁc right answer, provided the student keeps to the spirit of the question. Students may have trouble with the con- cept of “operations.” 1.2 This exercise asks the student to expand on their concept of an integer repre- sentation. A good answer is described by Project 4.5, where a singly-linked list is suggested. The most straightforward implementation stores each digit in its own list node, with digits stored in reverse order. Addition and multi- plication are implemented by what amounts to grade-school 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, com- 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. 1.3 A sample ADT for character strings might look as follows (with the normal interpretation of the function names assumed). 1

2 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); // Extract a substring, starting at ‘start’, // and of length ‘length’ String extract(String s1, int start, int length); // Get the first character char first(String s1); // Compare two strings: the normal C++ strcmp func- tion. Some // convention should be indicated for how to inter- pret the // return value. In C++, this is - 1 for s1s2. int strcmp(String s1, String s2) // Copy a string int strcpy(String source, String destination) 1.4 The answer to this question is provided by the ADT for lists given in Chap- ter 4. 1.5 One’s compliment stores the binary representation of positive numbers, and stores the binary representation of a negative number with the bits inverted. Two’s compliment is the same, except that a negative number has its bits inverted and then one is added (for reasons of efﬁciency in hardware imple- mentation). This representation is the physical implementation of an ADT deﬁned by the normal arithmetic operations, declarations, and other support given by the programming language for integers. 1.6 An 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); int getvalue(Matrix M1, int row, int col); List getrow(Matrix M1, int row);

3 One implementation for the sparse matrix is described in Section 12.3 Another im- plementation is a hash table whose search key is a concatenation of the matrix coor- dinates. 1.7 Every problem certainly does not have an algorithm. As discussed in Chapter 15, there are a number of reasons why this might be the case. Some problems don’t have a sufﬁciently clear deﬁnition. Some problems, such as the halting problem, are non-computable. For some problems, such as one typically studied by artiﬁcial intelligence researchers, we simply don’t know a solution. 1.8 We must assume that by “algorithm” we mean something composed of steps are of a nature that they can be performed by a computer. If so, than any algorithm can be expressed in C++. In particular, if an algorithm can be expressed in any other computer programming language, then it can be expressed in C++, since all (sufﬁciently general) computer programming languages compute the same set of functions. 1.9 The primitive operations are (1) adding new words to the dictionary and (2) search- ing the dictionary for a given word. Typically, dictionary access involves some sort of pre-processing of the word to arrive at the “root” of the word. A twenty page document (single spaced) is likely to contain about 20,000 words. A user may be willing to wait a few seconds between individual “hits” of mis-spelled words, or perhaps up to a minute for the whole document to be processed. This means that a check for an individual word can take about 10-20 ms. Users will typically insert individual words into the dictionary interactively, so this process can take a couple of seconds. Thus, search must be much more efﬁcient than insertion. 1.10 The user should be able to ﬁnd a city based on a variety of attributes (name, location, perhaps characteristics such as population size). The user should also be able to in- sert and 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 a typical user. For an insert, delete, or exact match query, a few seconds is satisfactory. If the database is meant to support range queries and mass deletions, the entire operation may be allowed to take longer, perhaps on the order of a minute. However, the time spent to process individual cities within the range must be appropriately reduced. In practice, the data representation will need to be such that it accommodates efﬁcient processing to meet these time constraints. In particular, it may be necessary to sup- port operations that process range queries efﬁciently by processing all cities in the range as a batch, rather than as a series of operations on individual cities. 1.11 Students 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 thus is likely to be much faster). 1.12 The 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.

资料库

数据结构与算法（C++版）课后习题答案（川大）.pdf

相关推荐

课程资源

热门标签

最新资料