Midterm-Type Questions

1. Understand what it means to be an ADT. For example, if you have an ADT stack, can you assume it is a linked-list or array implementation? Are you allowed to know?
2. Know the basic operations that can be performed on a Stack, Queue, Binary Tree, Linked List, Binary Search Tree.
3. Know how the various ADTs are supposed to operate.
4. Know the advantages and disadvantages of pointer-based (or linked-list based or dynamic) versus array-based (or static) implementations of ADTs. When is appropriate to use each?
5. Know how to implement the basic operations (including constructing, destroying, copying, inserting, deleting searching, etc.) for Stacks, Queues, Binary Trees, and Binary Search Trees using various implementations. (e.g. array or linked list for Stack, etc.)
6. What are some applications for Stacks, Queues, Binary Search Trees, Graphs?
7. Give code to do the following:
   • Reverse the elements on a queue or stack ADT using auxilary ADTs to help.
   • Reverse the items on a singly (or doubly) linked list in linear time (It is easy to do in quadratic time.)
   • Print (or do something else with) the values in a Binary Search Tree in order (or reverse order).