《数据结构与算法分析C++版答案文档推荐》由会员分享，可在线阅读，更多相关《数据结构与算法分析C++版答案文档推荐（50页珍藏版）》请在金锄头文库上搜索。
1、Data Structures and Algorithm 习题答案 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 Gr
2、aphs 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
3、 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 algorithms to be essentially correct there may be errors in syntax as
4、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 qu
5、estions are mainly intended to get students thinking about data structures issues 1 1 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 1 2 This exercise asks the student to expand on
6、their concept of an integer representation 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 multiplication are implemented by what amounts
7、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 combine the addition function with a new function t
8、hat 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 s
9、hould not be required 1 3 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 Extract a
10、 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 function Some convention should be indicated for how to interpret the return value In C this is 1 for s1s2 int strcmp S
11、tring 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 Chapter 4 1 5 One s compliment stores the binary representation of positive numbers and stores the binary representation of a negative number with th
12、e 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 efficiency in hardware implementation This representation is the physical implementation of an ADT defined by the normal arithmetic operations declarations and other
13、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
14、 getrow Matrix M1 int row One implementation for the sparse matrix is described in Section 12 3 Another implementation is a hash table whose search key is a concatenation of the matrix coordinates 1 7 Every problem certainly does not have an algorithm As discussed in Chapter 15 there are a number of
15、 reasons why this might be the case Some problems don t have a sufficiently clear definition Some problems such as the halting problem are non computable For some problems such as one typically studied by artificial intelligence researchers we simply don t know a solution 1 8 We must assume that by
16、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 sufficiently 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 searching the dictionary for a given word Typically dictio
