Midterm Review Guide
  • What is an ADT and how would you define it?
  • What is a data structure?
  • What is the difference between an ADT and a data structure?
  • What is a precondition?
  • What are the preconditions for your List access functions?
  • Which of the List manipulation procedures require a precondition?
  • Which of the iterator functions (access and manipulation) require a precondition?
  • What is a postcondition? Give an example using your List ADT? 
  • What is an access function? Give an example from your List ADT?
  • What is a manipulation procedure? Give an example from your List ADT?
  • What is a constructor? What is its purpose?
  • What is a destructor? What is its purpose?
  • What is a copy constructor? What is its purpose? How do you call a copy constructor (2 ways)?
  • What is the difference between a deep and shallow copy?
  • What are the advantages of using an array over a linked list to store data?
  • What are the advantages of using a linked list over an array to store data?
  • How do you write insertStart and insertStop for a linked list?
  • How do you write removeStart and removeStop for a linked list?
  • What is an iterator?
  • How would you write removeIterator, insertIterator, getIterator, startIterator, advanceIterator?
  • What is the difference between a singly and doubly linked list?
  • What is the difference between a Stack and a Queue?
  • What are FIFO and LIFO and how do they relate to stacks and queues?
  • How do you write enqueue and dequeue for a Queue?
  • How do you write push and pop for a Stack?
  • How would you write the Stack and Queue constructors
  • What is recursion?
  • What are the different parts of a recursive function (hint think base case and recursive call)?
  • What is the function call stack? Describe how recursion works with the function call stack?
  • What is a stack frame?
  • What is a stack overflow error?
  • What is the difference between iteration and recursion?
  • How do you write the following recursive functions: bunnyEars, fibonnacci, powerOfN, factorial?
  • How do you print a list in reverse both iteratively and recursively
  • How do you test whether a list is sorted using recursion?
  • What is the Big-O runtime of binary search in the best, worst and average cases
  • What is the Big-O runtime of linear search in the best, worst and average cases
  • How do you write binary search for an array (recursive)?
  • How do you write linear search (not recursive)?