Description
Topics
List Based Structures vs Array Based Structures
Stacks & Queues
Linked Lists
Binary Search (Array Based)
Array Based Binary Tree
Binary Heap
List VS Array
Overview
Heap Memory VS Stack Memory
Overview
Binary Trees
– Tree components
– Array implementation
Heaps
Overview
Run Time Complexities
| Cheat Sheet 1 | Cheat Sheet 2 | |:———:|:—————:| | |
Example Questions
For everything you do on this test, know its complexity.
Be able to write a basic sorting routine like a bubble sort or selection sort and know the difference between them. Given an array, perform a binary search to find a specific key.
Describe the difference between searching: a list
an array an ordered list an ordered array
a bst
Heap
What is it?
What can it be used for?
Describe the difference between inserting items into a heap and building a heap from an array of values
Given a list of unordered numbers, load them into an array based binary search tree Given a list of unordered numbers, load them into a binary search tree Given a list of unordered numbers, load them into a heap.
Delete a value from a given binary tree
Write a recursive traversal of a binary search tree.
Do an inorder, preorder, and postorder traversal of a tree.
