第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
数据结构面试题大全以及答案.pdf
Contents
Data Structures and Algorithms
Linked List Problems
Problems on Trees and Graphs
String Manipulation Problems
Recursion Problems
Problems on Searching and Sorting
Problems on Numbers
Geometry Problems
Miscellaneous Problems
Bibliography
A Collection of Technical Interview
Questions
http://www.spellscroll.com
December 3, 2008
2
Contents
1 Data Structures and Algorithms
7
7
1.1 Linked List Problems . . . . . . . . . . . . . . . . . . . . . . .
1.2 Problems on Trees and Graphs
. . . . . . . . . . . . . . . . . 17
1.3 String Manipulation Problems . . . . . . . . . . . . . . . . . . 20
1.4 Recursion Problems . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5 Problems on Searching and Sorting . . . . . . . . . . . . . . . 24
1.6 Problems on Numbers
. . . . . . . . . . . . . . . . . . . . . . 28
1.7 Geometry Problems . . . . . . . . . . . . . . . . . . . . . . . . 29
1.8 Miscellaneous Problems . . . . . . . . . . . . . . . . . . . . . . 29
Bibliography
33
4
CONTENTS
Disclaimer
All the questions (and solutions) presented in this document were originally
collected by the spellscroll.com team from various sources including books,
mailing-lists and online forums, etc. The spellscroll.com team spent signif-
icant amount of time in selecting, editing and formatting these questions
(and solutions), in the hope that our efforts will be of help to people who are
preparing technical interviews. Any comments, suggestions and corrections
are welcome. This document is free to be downloaded, copied and distributed
so long as this disclaimer is clearly reproduced at its beginning. However,
we are NOT responsible for the possible mistakes contained in this
document or any improper use of this document.
6
CONTENTS
Chapter 1
Data Structures and
Algorithms
1.1 Linked List Problems
Problems 1-7 and accompanying discussions are taken from the book [Mon07].
1. [Stack Implementation] Discuss the stack data structure.
Imple-
ment a stack in C using either a linked list or a dynamic array, and
justify your decision. Design the interface to your stack to be complete,
consistent, and easy to use.
Discussion:
• A stack is last-in-first-out data structure: Elements are always
removed in the reverse order in which they were added. The add
element and remove element operations are conventionally called
push and pop, respectively. Stacks are useful data structures for
tasks that are divided into multiple subtasks. Tracking return
addresses, parameters, local variables for subroutines is one ex-
ample of stack use; tracking tokens when parsing a programming
language is another.
• One of the ways to implement a stack is by using a dynamic array,
an array that changes size as needed when elements are added.
The main advantage of dynamic arrays over linked lists is that
arrays offer random access to the array elements. However, oper-
ations on a stack always work on one end of the data structure (the
top of the stack), so the random accessibility of a dynamic array
8
1.1. LINKED LIST PROBLEMS
gains you little. In addition, as a dynamic array grows, it must
occasionally be resized, which can be a time-consuming operation
as elements are copied from the old array to the new array.
• Conversely, linked lists usually allocate memory dynamically for
each element, and that overhead can be significant when dealing
with small-sized elements, especially if heuristics are used to min-
imize the number of times the array has to be resized. For these
reasons, a stack based on a dynamic array is usually faster than
one based on a linked list. In the context of an interview, though,
the primary concern is ease and speed of implementation: Imple-
menting a linked list is far less complicated than implementing a
dynamic array, so a linked list is probably the best choice for your
solution.
• A C-style implementation
typedef struct Element {
struct Element *next;
void *data;
} Element;
bool push( Element **stack, void *data);
bool pop( Element **stack, void **data);
bool createStack(Element **stack);
bool deleteStack(Element **stack);
bool createStack(Element **stack){
*stack = NULL;
return true;
}
bool push( Element **stack, void *data){
Element *elem = new Element;
if (!elem) return false;
elem->data = data;
elem->next = *stack;
*stack = elem;
return true;
}
bool pop(Element **stack, void **data){
