Individual Exam 1

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
  • Abstract Data Types and their associated operations
    • Lists
    • Stacks
    • Queues
    • Deques
  • Array-Based Data Structures
    • Array-based list implementations and their associated trade-offs
    • Stack/Queue/Deque implementations and their associated trade-offs
    • How to conceptually visualize these structures and their associated operations
    • Times when it is appropriate to use these structures
  • Linked List Based Data Structures
    • Singly vs. Doubly linked lists: implementation
    • Linked list implementations and their associated trade-offs
    • How to conceptually visualize these structures and their associated operations
    • Times when it is appropriate to use these structures

The following topics will not be covered.

  • Specific big-Oh runtimes of any operations or calculations of runtime
  • Syntax for pointers (address-of & and dereference * operators)
  • Templates/overrides/namespaces
  • Linked-list based stacks/queues/deques (they are subsumed by the List)

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.

Can you follow along with the display() method of each function at each step, and draw what the data structure looks like?

Can you follow along with what is happening between displays of the data structure, when elements are being moved around inside the container itself?

Return to your Homeworks 0, 1, and 2 to note any feedback you have received, and try revising those assignments based on the feedback.