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 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 compiled 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.
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 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 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 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).
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 function.
Some
// convention should be indicated for how to interpret
the
// return value. In C++, this is 1
for s1<s2; 0 for s1=s2;
// and 1 for s1>s2.
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 Chapter
4.
1.5
One’s compliment stores the binary representation of positive numbers, and

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。