- Binary Search Trees
- Dictionaries
- Heaps
- Balanced Search Trees

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

# | 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% |

- Matching
- Fill in
- Diagramming
- Labelling
- Coding

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

- 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)}

- 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)}

- 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)}

- 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

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

- Know how a Heap maps to an Array

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

- Classify average case growth rates - O(1), O(n), O(n
^{2}), 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)}