1. What is the state of the stack after the following sequence of pushes and pops:
Stack s;
s.push( 3 );
s.push( 5 );
s.push( 2 );
s.push( 15 );
s.push( 42 );
s.pop();
s.pop();
s.push( 14 );
s.push( 7 );
s.pop();
s.push( 9 );
s.pop();
s.pop();
s.push( 51 );
s.pop();
s.pop();
2. Suppose the numbers 0, 1, 2, …, 9 were pushed onto a stack in that order, but that pops
occurred at random points between the various pushes. The following is a valid sequence in
which the values in the stack could have been popped:
3, 2, 6, 5, 7, 4, 1, 0, 9, 8
Explain why it is not possible that
3, 2, 6, 4, 7, 5, 1, 0, 9, 8
is a valid sequence in which the values could have been popped off the stack.
3. What is the state of the queue after the following sequence of pushes and pops:
Queue q;
q.push( 3 );
q.push( 5 );
q.push( 2 );
q.push( 15 );
q.push( 42 );
q.pop();
q.pop();
q.push( 14 );
q.push( 7 );
q.pop();
q.push( 9 );
q.pop();
q.pop();
q.push( 51 );
q.pop();
q.pop();
4. Perform depth-first, pre-order depth-first and post-order depth-first traversals on the tree
shown in Figure 1.
5. What is the maximum size of the queue if a queue is used for performing a breadth-first
traversal on the tree in Figure 1?
6. You are given that a tree has pre- and post-order depth first traversals of
A B D E G C F
D G E B F C A
respectively. Can you determine the original tree from this information?
7. You are given that a tree has pre-order depth-first and breadth-first traversals of
A B C D E G F
A B C D E F G
respectively. Can you determine the original tree from this information?
8. Show that the maximum number of nodes in a binary tree of height ℎ is 2
ℎ+1 − 1.
9. A full node is a node with two children. Prove that the number of full nodes plus one is
equal to the number of leaves in a nonempty binary tree.
10. Suppose a binary tree has leaves 𝑙1, 𝑙2, . . . , 𝑙𝑀 at depths 𝑑1, 𝑑2, . . . , 𝑑𝑀,
respectively. Prove that ∑ 2
−𝑑𝑖 ≤ 1
𝑀
𝑖=1
and determine when the equality is true.
11. The following is an array representation of a complete binary tree. What is the actual tree?
0 1 2 3 4 5 6 7 8 9 10 12 13
84 57 81 42 54 73 60 31 25 14
Without referring to the binary tree, what are the parent and children of the entry containing
42 and 54?
12. Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 2.
Figure 2.
13. a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search
tree.
b. Show the result of deleting the root.
14. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. What is
the result after erasing 5 from the tree?
15. Perform an in-order traversal of the binary tree shown in Figure 3.
Figure 3
16. What are the number of inversions in the following unsorted list?
6, 7, 3, 1, 2, 4, 5, 8
17. Sort the above sequence using insertion sort.
18. Suppose we exchange elements 𝑎[𝑖] and 𝑎[𝑖 + 𝑘], which were originally out of order.
Prove that at least 1 and at most 2𝑘 − 1 inversions are removed.
19. Sort 3, 7, 4, 1, 5, 9, 2, 6 using merge sort.
20. Sort 3, 7, 4, 1, 5, 9, 2, 6 using quick sort with median-of-three partitioning.
21. Given the following hash table, remove the following values from the hash table of size
10 using linear probing using the least-significant digit as the hash value:
821, 636, 594, 399
0 1 2 3 4 5 6 7 8 9
219 821 981 388 594 192 636 144 170 399
22. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function ℎ(𝑥) =
𝑥(𝑚𝑜𝑑 10), show the resulting
a. separate chaining hash table
b. hash table using linear probing
c. hash table using quadratic probing (𝑘 × 𝑘 + 𝑘)
d. hash table with second hash function ℎ2
(𝑥) = 7 − 𝑥(𝑚𝑜𝑑 7)
23. Find the shortest path from A to all other vertices for the graph in Figure 4.
Figure 4
24. Find a minimum spanning tree for the graph in Figure 5 using both Prim’s and Kruskal’s
algorithms.
Figure 5
25. If a graph is bipartite, then all its circuits are of even length.
26. Find a topological ordering for the graph in Figure 6.
Figure 6