1
Name:_______________________
Covers
50 min
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State University
Instructor: Y. Daniel Liang
Total (41 pts)
0. (3 pts)
Given f(n) = 5n3 + 8n2, answer the following questions:
1. Is f(n) O(n2)? no
2. Is f(n) O(n3)? yes
3. Is f(n) O(n4)? yes
4. Is f(n) Ω(n2)? yes
5. Is f(n) Ω(n3)? yes
6. Is f(n) Ω(n4)? no
7. Is f(n) Θ(n2)? no
8. Is f(n) Θ(n3)? yes
9. Is f(n) Θ(n4)? no
1. (3 pts)
Suppose you need to store a list of elements, if the number
of elements in the program is fixed, what data structure
should you use? (array, ArrayList, or LinkedList)
If you have to add or delete the elements at the beginning
of a list, should you use ArrayList or LinkedList?
If most of operations on a list involve retrieving an
element at a given index, should you use ArrayList or
LinkedList?
2. (3 pts) Show the BST after inserting 35, 85 and 103.
A:
2
60
root
3. (3 pts) Show the BST after deleting 15 from the
following BST.
60
root
3
60
root
4. (3 pts) Show the BST after deleting 60 from the
following BST.
60
root
A:
57
root
5. (6 pts) Show the inorder, preorder, and postorder of the
following BST.
4
60
root
A:
inorder: 15 49 57 60 64 67 100 107
6. (2 pts) Given the following heap, show the resulting
heap after adding 63 to the heap.
62
A:
5
63
7. (2 pts) Given the following heap, show the resulting
heap after removing 62 from the heap.
62
A:
59
6
8. (8 pts) Add a void instance method replaceAll(E oldE, E newE) in the MyLinkedList
class to replace the occurrence of all oldE value with the specified newE value in O(n).
Implement this method.
public void replaceAll(E oldE, E newE) {
Node<E> current = head;
9. (8 pts) Add an instance method max() in the BST class to return the largest element in
this tree. Returns null if it does not exist.
// Use recursion
public E max() {
7
}
// Alternatively
}
10. (8 pts) Implement the removeAll method in the MyHashSet class.
@Override
public boolean removeAll(Collection<?> arg0) {