Exam 3 Review, CS 250

New Topics:

  • Binary Search Trees
  • Dictionaries
  • Heaps
  • Balanced Search Trees

New Returning Topics:

  • Pointers
  • Dynamic Arrays
  • Linked Lists
  • Stacks and Queues
  • Algorithm Efficiency

Question Breakdown:

# Question Weight
1 Binary Search Trees – Terminology 1 2%
2 Binary Search Trees – Terminology 2 2%
3 Binary Search Trees – In-order Traversal 5%
4 Binary Search Trees – Pre-order Traversal 5%
5 Binary Search Trees – Post-order Traversal 5%
6 Binary Search Trees – Properties 1 3%
7 Binary Search Tree – Properties 2 3%
8 Binary Search Tree – Build with Push 1 8%
9 Binary Search Tree – Build with Push 2 10%
10 Dictionaries – Collision 2%
11 Heaps – Heap Array 5%
12 Balanced Search Tree – Balance Factor 5%
13 Dynamic Variables – Coding 8%
14 Dynamic Arrays – Coding 8%
15 Linked List – Coding a Node 5%
16 Linked List – Coding a Push 5%
17 Linked List – Coding a Pop 5%
18 Linked List – Coding GetAtIndex 5%
19 Stacks & Queues – Linked List mappings 5%
20 Efficiency 4%
21 Extra Credit +5%

Question types:

  • Matching
  • Fill in
  • Diagramming
  • Labelling
  • Coding

What to review:

Some questions are off previous exams (Exam 1 and Exam 2)


Things to know:

Dynamic Variables and Arrays

  • How to allocate and deallocate memory and assign values for a dynamic variable using a pointer. (See previous exam)
  • How to allocate and deallocate memory and assign values for a dynamic array using a pointer. (See previous exam)

Linked Lists

  • Write the code for a Node (that belongs to a Linked List) (See previous exam)
  • Write the code or pseudocode for either PushFront or PushBack (See previous exam)
  • Write the code or pseudocode for either PopFront or PopBack (See previous exam)
  • Write the code or pseudocode for GetAtIndex (See previous exam)

Stacks and Queues

  • Know which Linked List functions a Stack calls for Push, Pop, and Top. (See previous exam)
  • Know which Linked List functions a Queue calls for Push, Pop, and Front. (See previous exam)

Binary Search Trees

  • Understand the following terminology:
    • Root
    • Leaf
    • Edge
    • Height
    • Depth
    • Complete
    • Full
    • Binary tree vs. not a binary tree
  • Be able to do an in-order traversal
  • Be able to do a pre-order traversal
  • Be able to do a post-order traversal
  • Given a list of Push commands, be able to construct a binary search tree diagram

Dictionaries

  • Be able to execute a collision solution (Linear Probe, Quadratic Probe, Double Hash) with the necessary functions already defined.

Heaps

  • Know how a Heap maps to an Array

Balanced Search Trees

  • Be able to calculate node Heights
  • Be able to calculate node Balance Factors

Growth Rates

  • Classify average case growth rates - O(1), O(n), O(n2), O(log n) - for Search and Push functions of structures:
    • Dynamic Arrays (Vectors)
    • Linked Lists
    • Binary Search Tree
    • Heap (This is in the slides)
    • AVL Balanced Search Tree(This is in the slides)