Sample Data Structures Exam Questions for Lists, Stacks, and Queues

This is a list of exam questions I've asked on past exams for my data structures class at the University of Pittsburgh.

1. What is the computational complexity when iterating over a linked list *without* using an iterator?  Why?
2. Explain how using an iterator improves computational complexity.
3. What is a circular array?
4. What are 2 advantages of using a circular array for building a queue, instead of linked nodes?
5. Using words and a drawing, explain what happens when you insert an item into the middle of a linked list.
6. Using words and a drawing, explain what happens when you insert an item into the middle of an array list.
7. Explain the behavior of a queue, including the operations a queue should be able to perform.
8. In a queue implemented using a circular array, why do we need to know more than just the start and end positions to know if the queue is full?
9. Explain why removing the first item in an array list is more work than removing the first item from a linked list.
10. What are all of the things you would you have to do to improve the computational complexity of the size() method?
11. In your own words, explain the relationship between encapsulation and abstraction.
12. In the context of data structures, why is abstraction important?
13. How could abstraction be dangerous?  Give an example.
14. What is the purpose of leaving one index empty in an array-backed implementation of a Queue?  Why is this necessary?
15. Using pictures, illustrate the steps that occur when an item is removed from a linked-node based queue.
16. Using pictures, illustrate the steps that occur an item is added to a linked-node based queue.
17. Using pictures, illustrate the steps that occur when an item is removed from an array based queue.
18. Using pictures, illustrate the steps that occur an item is added to an array based queue.
19. For the add(T), remove(int), and get(int) operations, what is the difference between a LinkedList and an ArrayList implementation?  What must be done for each?
20. Describe one situation where an ArrayList would be preferable and one situation where a LinkedList would be preferable.
21. Explain some of the tradeoffs in using array-backed data structures.  When are array-based structures valuable?  Why do we need linked structures?
22. Explain why using a "tail" property in our Linked List makes it more efficient.
23. Describe two situations where you might need to use a List; one where a Linked List would be preferred, and one where an Array List would be preferred.
24. What is the computational complexity of the operation add(T) in our array-based queue implementation?  Why?
25. Name the 3 operations that a Stack should be able to perform, and explain what they do.  What is the computational complexity of each of these operations?
26. Why isn’t iterating through a Linked List (using a traditional while loop or for loop) an efficient operation?
27. Why is encapsulation important when designing data structures?  Name a problem that could occur if your data structure is not properly encapsulated.
28. Describe, using words and drawings, how a remove(int) operation occurs in a Linked List.
29. Describe, using words and drawings, how a remove(int) operation occurs in an Array List.
30. Why is encapsulation important when designing data structures?  Using one of the data structures we discussed in class, identify a specific problem that could occur if your data structure is not properly encapsulated.
31. Write code for a public int pop() method for the following IntStack class.
    
32. Assuming you have the following code in your class, how would you implement the “public void push(Object value)” and “public Object pop()” methods for a stack?
    
33. Given the following code, implement an Iterator with the methods public T next() and public boolean hasNext() for this Linked List.
    
34. Implement the following ensureCapacity method for a Queue implemented with a circular array. This method should ensure that there is room in the values array.