Midterm 1 Review Guide

The below questions serve as a guide to help you prepare for the midterm. Note that no questions will be asked from material that does not appear either on this guide or the lesson review questions or quizzes.

Lesson 1 Review

  • 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 is a postcondition?
  • What is an access method? What is the typical signature for an accessor method?
  • What is a mutator method? What is the typical signature for a mutator method?
  • What is a constructor? What is the typical signature for a constructor?

Lessons 2 - 4 Review

  • 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?
  • Give an example of two different preconditions from your List ADT.
  • What is the postcondition for addLast()? What is the postcondition for removeIterator()?
  • Give an example of an accessor method from your List ADT
  • Given an example of a mutator method from your List ADT
  • What is a constructor? What is its purpose?
  • What is a copy constructor? What is its purpose? How do you call a copy constructor?
  • 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 addFirst and addLast for a linked list (singly and doubly linked)?
  • How do you write removeFirst and removeLast for a linked list(singly and doubly linked)?
  • What is an iterator?
  • How would you write removeIterator, addIterator, getIterator, pointIterator, advanceIterator (doubly linked)?
  • What is the difference between a singly and doubly linked list?

Lesson 5 - 6 Review

  • 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 do you write getFront and peek, including handling the preconditions as described in class?
  • How would you write the Stack and Queue constructors?
  • Give an example of an access method and mutator method from the Queue and Stack.
  • What is the precondition for dequeue? What is the precondition for pop?
  • Draw the Stack and Queue that result from inserting the data 5, 10, 20 in that exact order. Be sure to label front, end and top.

Lesson 7 Review

  • What is recursion?
  • What are the different parts of a recursive method (hint think base case and recursive call)?
  • What is the method call stack? Describe how recursion works with the method 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 methods: bunnyEars, fibonnacci, powerOfN, factorial?

Lesson 8 Review

  • 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)?