Individual Exam 2

Your individual exam will be a paper exam consisting of conceptual questions related to the course topics. There will not be any C++ syntax on the exam. There will be conceptual questions related to programming in C++, in particular pointers and an understanding of linked-list data structure implementations.

The following topics may be covered (not all will be).

• Big-Oh runtime
• Comparison of abstract data types
  • Lists, stacks, queues, deques, sets – definitions
  • Scenarios in which it is appropriate to use one kind of data structure over another
• Searching and Sorting
  • Linear search and binary search
  • Insertion sort and merge sort
  • Runtime of sorting algorithms
  • Runtime of searching algorithms
• Tree-Based Data Structures
  • Binary trees vs. balanced binary trees - the difference between the two
  • How to conceptually visualize binary tree structures and their associated operations
  • Implementations of binary trees and their trade-offs
  • Traversal of binary trees (breadth-first vs depth-first)

The following topics will not be covered.

• Syntax for addition and removal from any data structures
• Inductive proofs
• Heaps

How to Study

Go back to the data structures and their implementatios. Try first working with the data structures in C++ code, then try drawing out the data structures that you have created in the code.

Return to your Homeworks 3 and 4 to note any feedback you have received, and try revising those assignments based on the feedback. (Feedback for Homework 4 will be posted by the end of the day Thursday.)

Go back to your first exam; what were the places that your feedback indicated you needed to focus in?