Computer Programming                                                                                    Name -
Data Structures Worksheet #1

1. Consider the following sequence of operations on an empty stack:

PUSH(Z), PUSH(W), PUSH(Y), PUSH(T), POP, POP, PUSH(B), PUSH(B), POP

What is the next element that would be popped off of the stack with another POP command?

2. Consider the same sequence of operations in Problem #1 above on an empty queue. What would be the next element to be popped off of the queue?

3. What do FIFO and LIFO stand for with regard to data structures?

4. Draw the binary search tree that would be formed by processing the letters A L P H A B E T in that order.

5. Answer the following questions based on your answer to Problem #4 above.

a/ What is the height of the tree?

b/ What is the internal path length?

c/ What is the external path length?

d/ How many external nodes are there?

e/ How many leaf nodes are there?