CPSC 221H: Data Structures & Algorithms
Information and Review Questions for Exam I
Spring 2009
General Information
The first exam will be on Tuesday February 24.
It will cover material from Chapters 4, 5, 6, and 7, in the text.
It will be a closed book exam (no notes, books, or neighbors)
except you will be allowed a one page (8.5x11), two side cheat sheet which must
be turned in with the exam.
There will be 5 questions, each worth 20 points, for a total of 100 points.
Remember to show your work - partial credit will be given.
Material
All of the following are considered to be fair game:
-
Reading.
Chapters 4 (except section 4.6),
5, 6, and 7.
-
Lectures (class and lab). You are responsible for things that we went over that
were either not covered in the text, or that were done differently than
in the text.
-
Homeworks.
Know how to do all the problems on homeworks #1,
#2, #3, and #4.
-
Quizzes.
Understand and know the answers to all the questions on Quizzes 1-4.
Review Questions
Below are some suggested review exercises/problems for the exam.
It is strongly recommended that you be able to do all of these
problems. Solutions will not be handed out.
Finally, be sure to check your email -- clarifications
and/or explanations will be mailed to the class if needed.
-
Study Homeworks 1-4, Quizzes 1-4, and the in class assignments;
variations of some of these questions
will appear on the exam.
-
Know the space usage and the running times for performing operations on
all of the data structures we have studied in class.
Be able to answer questions of the following form for all combinations
of ADTs and implementations (there are just a few shown below):
-
If a Stack ADT is implemented using an array,
then the top() operation takes time
,
the push(o) operation takes time
,
the pop() operation takes time
,
the isEmpty() operation takes time
,
and the size() operation takes time
.
-
If a PQ ADT is implemented using an unordered sequence,
then the insertItem(k,e) operation takes time
,
the minElement() operation takes time
,
the minKey() operation takes time
,
the removeMin() operation takes time
,
the isEmpty() operation takes time
.
and the size() operation takes time
.
-
If a PQ ADT is implemented using an ordered sequence,
then the insertItem(k,e) operation takes time
,
the minElement() operation takes time
,
the minKey() operation takes time
,
the removeMin() operation takes time
,
the isEmpty() operation takes time
.
and the size() operation takes time
.
-
If a PQ ADT is implemented using a heap, which is implemented using an array,
then the insertItem(k,e) operation takes time
,
the minElement() operation takes time
,
the minKey() operation takes time
,
the removeMin() operation takes time
,
the isEmpty() operation takes time
.
and the size() operation takes time
.
-
Describe, in pseudo-code with accompanying pictures, how to
swap two nodes x and y in a singly linked list L given pointers
only to x and to y.
Repeat this exercise for the case when L is a doubly linked list.
What are the running times of each of these functions in terms
of n, the number of nodes in L?
-
Answer the following questions about binary trees.
-
Draw a binary tree with height 7 and maximum number of leaves.
-
What is the minimum number of leaves for a binary tree with
height h? Justify your answer and draw an example tree for h=7.
-
What is the maximum number of leaves for a binary tree with
height h? Justify your answer and draw an example tree for h=7.
-
What is the maximum height for a binary tree with n nodes?
Justify your answer and draw an example tree for n=15.
-
What is the minimum height for a binary tree with n nodes?
Justify your answer and draw an example tree for n=15.
-
Design an algorithm based on the
Priority Queue ADT, implemented with a heap (which is in turn
implemented with a vector-based structure for binary trees),
where the element with the maximum key is stored at the root
of the heap (often called a max-heap).
The algorithm should find
the kth largest element in a list of n elements.
The only (non-trivial) operations your algorithm should perform are:
- the insertItem operation
- the maxElement and removeMax operations,
Describe your algorithm in pseudo code and words,
discuss its correctness, and
analyze its complexity.