Data Structures and Algorithms
A linked-list implementation of a stack guarantees constant time performance but
requires more space than an array implementation. - Answer- TRUE
Both implementations of pop and push guarantee constant time performance. Linked
lists require additional memory (space) for storing a reference to the next node.
An algorithm that uses 12n2 + 4n log n operations is a ∼n2 algorithm. - Answer-
FALSE
It is a ∼ 12n2 algorithm.
Big-Oh notation is more precise than tilde notation at describing the growth of a
function. - Answer- FALSE
Big-Oh notation only provides an upper bound on the growth rate of a function. Tilde
approximation approaches the original function as N grows.
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects. -
Answer- TRUE
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects.
Mergesort - Answer- Stable and fast
Quicksort - Answer- Fast general-purpose sort
Shellsort - Answer- Not analyzed
Insertion sort - Answer- Works well with order
Selection sort - Answer- Optimal data movement
3-way quicksort - Answer- Works well with duplicates
Heapsort - Answer- Optimal time and space
Height of a binary heap with N keys. - Answer- log N
A binary heap is a complete tree. A complete tree is a tree with n levels, where for
each level d ≤ n − 1, the number of existing nodes at level d is equal to 2d. The
height of a binary heap is logN.
Height of a BST with N keys. - Answer- N
In the worst-case, the height of a BST is N, e.g., when keys are inserted in
increasing or de- creasing order.
A linked-list implementation of a stack guarantees constant time performance but
requires more space than an array implementation. - Answer- TRUE
Both implementations of pop and push guarantee constant time performance. Linked
lists require additional memory (space) for storing a reference to the next node.
An algorithm that uses 12n2 + 4n log n operations is a ∼n2 algorithm. - Answer-
FALSE
It is a ∼ 12n2 algorithm.
Big-Oh notation is more precise than tilde notation at describing the growth of a
function. - Answer- FALSE
Big-Oh notation only provides an upper bound on the growth rate of a function. Tilde
approximation approaches the original function as N grows.
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects. -
Answer- TRUE
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects.
Mergesort - Answer- Stable and fast
Quicksort - Answer- Fast general-purpose sort
Shellsort - Answer- Not analyzed
Insertion sort - Answer- Works well with order
Selection sort - Answer- Optimal data movement
3-way quicksort - Answer- Works well with duplicates
Heapsort - Answer- Optimal time and space
Height of a binary heap with N keys. - Answer- log N
A binary heap is a complete tree. A complete tree is a tree with n levels, where for
each level d ≤ n − 1, the number of existing nodes at level d is equal to 2d. The
height of a binary heap is logN.
Height of a BST with N keys. - Answer- N
In the worst-case, the height of a BST is N, e.g., when keys are inserted in
increasing or de- creasing order.
