CPTR 318 Data Structures Test 2 Study Guide

The material presented in this guide covers the concepts emphasized on Test 2. It is meant to guide students studying and reviewing for Test 2; it is not guaranteed to be comprehensive. Actual test questions will differ from the examples given here. Students should use this guide in addition to other study activities (like reading Chapters 4-5, reviewing completed assignments, quizzes, etc.)

• Know the following concepts. Understand where they apply and when they should or could be used.
  • Linear data structures: stacks and queues

  • Trees: terminology and implementations, binary trees, BSTs, complete binary trees, insertion, deletion, traversals, etc.

  • Priority queues and heaps: enqueuing, dequeuing, array representation

  • Huffman trees

  • Disjoint set with union/find operations

• Be able to do the following tasks.
  • Determine the absolute and/or asymptotic complexity of a given C++ function.

  • Be able to write code concerning linear structures such as stacks, queues, and binary trees.