Fundamentals of algorithms Flashcards
1
Q
What are the 2 types of graph-traversal?
A
Depth-first and breadth-first
2
Q
What are the 3 types of tree traversal?
A
Pre-order, In-order, Post-order
3
Q
What does a pre-order traversal give you?
A
A copy of the tree.
4
Q
What does an in-order traversal give you?
A
Gives you the contents of the tree in ascending order
5
Q
What does a post-order traversal give you?
A
Gives you the reverse polish notation
6
Q
What data structure does reverse polish mimic?
A
A stack
7
Q
What is the time complexity of a linear search?
A
O(n)
8
Q
What is the time complexity of a binary search?
A
O(logn)
9
Q
What is the time complexity of a bubble sort?
A
O(n^2)
10
Q
What is the time complexity of a merge sort?
A
O(nlogn)
