York University
CSE 2011Z Winter 2014 – Final Exam Practice Problems
Instructor: James Elder
1. Binary Search Trees
Insert, into an empty binary search tree, entries with keys 30, 40, 24, 58, 48, 26, 11, 13 (in this order).
Draw the tree after each insertion.
• Answer: The final tree should appear as follows:
30
24 40
11 26 58
13 48
2. AVL Trees
Insert, into an empty binary search tree, entries with keys 62, 44, 78, 17, 50, 88, 48, 54 (in this order).
Now draw the AVL tree resulting from the removal of the entry with key 62.
• Answer: The final tree should appear as follows:
3. Splay Trees
Perform the following sequence of operations in an initially empty splay tree and draw the tree after
each set of operations.
(a) Insert keys 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, in this order.
• Answer:
1
18
16
14
12
10
(b) Search for keys 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, in this order.
• Answer:
18
16
14
12
10
(c) Delete keys 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, in this order.
• Answer: The tree is empty.
4. Comparison Sorts
Of the n! possible inputs to a given comparison-based sorting algorithm, what is the absolute maximum
number of inputs that could be sorted with just n comparisons?
• Answer: A decision tree of height n can store 2n external nodes. Thus a maximum of 2n inputs
can be sorted with n comparisons.
2
5. Comparison Sorts
Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which
insertion sort takes O(n) time. What if the list is reversed?
• Answer: Merge-sort and heap-sort both take O(n log n) time on a sorted list, while insertion
sort takes O(n) time. If the list is reversed, merge-sort and heap-sort still take O(n log n) time,
while insertion sort takes O n2 time.
6. Stack-Based Quicksort
Describe in pseudocode a non-recursive version of the quick-sort algorithm that explicitly uses a stack.
• Answer:
QuickSort(A)
stack S
push A onto S
while S ≠ ∅
A = pop(S)
if A.length > 1
(L, R) = Partition(A)
push R onto S
push L onto S
7. Linear Sorts
Given an array of n integers, each in the range 0, n2 − 1 , describe a simple method for sorting the
array in O(n) time.
• Answer: Notice that each integer can be coded by log n2 = d2 log ne ≤ 2 dlog ne bits. We choose
CSE
2011Z
2012W
to represent each integer by two dlog ne-bit words, each of which
can
dlog
assume 2
ne
Prof.
J.
Eld
values. We
dlog ne
then use radix sort to sort the integers, which takes O 2 n + 2 ∈ O (2 (n + 2n)) ∈ O (n)
time. Graphs
8. Topological Sorts R-‐13.6
Suppose
that
you
wish
to
take
a
sequence
of
language
courses
with
the
following
Suppose that you wish to take aprerequisites:
sequence of language courses with the following prerequisites:
Course
Prerequisite
LA15
none
LA16
LA15
LA22
none
LA31
LA15
LA32
LA16,
LA31
LA126
LA22,
LA32
LA127
LA16
LA141
LA22,
LA16
LA169
LA32
a. Draw
a
directed
graph
that
represents
these
dependencies.
3 LA126
(a) Draw a directed graph that represents these dependencies.
• Answer:
LA126
LA22 LA141
LA15 LA16 LA127
LA32 LA169
LA31
(b) Use the topological sorting algorithm to compute a feasible sequence.
• Answer: Let’s assume that vertices and edges are processed in the order indicate by the
table above. Then the first call to Topological Visit will be from LA15, and will produce
the list {LA15,LA31,LA16,LA141,LA127,LA32,LA169,LA126}. The second and last call to
Topological Visit will be from LA22, which will simply preprend LA22 onto the list. Thus the
final linear ordering will be {LA22,LA15,LA31,LA16,LA141,LA127,LA32,LA169,LA126}.
CSE
2011Z
2012W
Prof.
J.
Elde
9. DFS and BFS
Let G be an undirected graph whose
R-‐13.8
vertices
Let
G
be
aare labelled by
n
undirected
thewintegers
graph
1 through
hose
vertices
8, andby
having
are
labelled
the 1
through
8,
and
the
integers
following edges: having
the
following
edges:
Vertex
Edges
1
2,
3,
4
2
1,
3,
4
3
1,
2,
4
4
1,
2,
3,
6
5
6,
7,
8
6
4,
5,
7
7
5,
6,
8
8
5,
7
Assume that, in a traversal of G,Assume
that,
in
vertices
the adjacent a
traversal
of oaf
given
G,
the
vertex
adjacent
are vertices
returned of
a
giniven
thevorder
ertex
aabove.
re
returned
in
the
order
above.
(a) Draw G. a. Draw
G
• Answer:
b. Give
the
sequence
of
vertices
of
G
visited
using
a
DFS
traversal
starting
at
vertex
1.
{1,
2,
3,
4,
6,
5,
7,
8}
c. Give
the
sequence
of
vertices
visited
using
a
BFS
traversal
starting
at
vertex
1.
The
order
is
the
same
in
this
case:
{1,
2,
3,
4,
6,
5,
7,
8}
4
(b) Give the sequence of vertices of G visited using a DFS traversal starting at vertex 1.
• Answer: 1, 2, 3, 4, 6, 5, 7, 8.
(c) Give the sequence of vertices visited using a BFS traversal starting at vertex 1.
• Answer: The order is the same in this case: 1, 2, 3, 4, 6, 5, 7, 8
