1) What is the running time required for adding an item to a linked stack?

A) O(1)

B) O(log N)

C) O(N)

D) O(N/2)

2) What is the running time required for removing an item from a queue?

A) O(1)

B) O(log N)

C) O(N)

D) O(N/2)

3) Which of the following is a LIFO structure?

A) array

B) queue

C) stack

D) tree

4) Deques are traversable data structures

True or False

5) If a stack contained the entries w, x, y, z (with w at the top and z at the bottom), which of the following would be the contents after two entries were removed and the entry r was inserted? (Note: the answers below are given with the first letter at the top and the last letter at the bottom.)

A) w,x,r

B) y,z,r

C) r,y,z

D) r,w,x