2019 Final Questions

Question 1

T/F: When I insert a value into an AVL tree, I will perform a maximum of two rotations.

Answer 1

True. After either a zig-zig or zig-zag imbalance is fixed, the tree is balanced, so you can stop.

Question 2

T/F: a(n) = O(b(n)) if there are positive constants c and n0 such that for all n > n0, ca(n) ≥ b(n).

Answer 2

False. This is backward (it’s the definition of big omega)

Question 3

Suppose I have a deque with n elements and an iterator to one of its elements. What is the running time
of deleting the element.

Answer 3

O(n). Inserting into the middle of a deque is the same as inserting into the middle of a vector.

Question 4

Suppose I have an AVL tree with n elements. What is the running time of deleting an element from it.

Answer 4

O(log n) – that’s one reason why we like AVL trees.

Question 5

Suppose I have a binary search tree with n elements. What is the running time to create a sorted vector
from the binary search tree?

Answer 5

O(n) – it’s an inorder traversal.

Question 6

What is the big-O expression for 15n^2 + 400n + 5 log(n)

Answer 6

O(n2). In a sum of expressions, it’s the big O of the largest expression, with any constant factors removed. What is the big-O expression for 15n2 + 400n + 5 log(n)

Question 7

Suppose I have a list with n elements and an iterator to one of its elements. What is the running time of
deleting the element.

Answer 7

O(1) – that’s one reason why we like lists.

Question 8

Suppose I have a binary search tree. What kind of traversal do we use to create a sorted vector from the
binary search tree.

Answer 8

See part E. It’s an inorder traversal

Question 9

T/F: If b is a map, and I put the line “a = b[i]” in my method, I can declare the method as const.

Answer 9

False. The associative array feature of a map will insert i if it’s not there. The compiler will exit with an error if you call the method const

Question 10

T/F: a(n) = O(b(n)) if there are positive constants c and n0 such that for all n > n0, cb(n) ≥ a(n)

Answer 10

True. The very definition of big O.

Question 11

Suppose I have a binary search tree with n elements. What is the running time of deleting an element
from it.

Answer 11

O(n). The tree doesn’t have to be balanced – if we insert keys from “A” to “Z” in that order, the tree has a depth of 26.

Question 12

What is the big-O expression for 55n + 4n log(n) + 20 log(n)?

Answer 12

O(n log(n)). In a sum of expressions, it’s the big O of the largest expression, with any constant factors removed.

Question 13

What is the big-O running time of inserting a value between 0 and n into a multimap with m elements
that are numbers between 0 and n.

Answer 13

O(log m). Inserting into a multimap is O(log x) where x is the number of elements in the multimap. Their values don’t matter.

Question 14

T/F: If b is a map, and I put the line “a = b.find(i)->second” in my method, I can declare the method
as const.

Answer 14

True, because b is not modified. Now, it’s a different matter as to what happens if i is not in the map, but that’s not what the question is asking.

Question 15

Suppose I have a binary search tree class. I implement Clear() without declaring any local variables.
What kind of traversal do I have to use?

Answer 15

It has to be a postorder traversal. You’ll have to call a recursive clearing method on the two children, and then you delete the node. Please see Clear() in the lecture notes on binary search trees. It calls a postorder method called recursive_destroy().

Question 16

Suppose I have a tree that represents an arithmetic expression. What kind of traversal do we use to
evaluate/calculate that expression.

Answer 16

This is also postorder – you have to calculate the expressions of the children, before you can perform an arithmetic operator on them. Please see the “Example Question” in the lecture notes on trees.

Question 17

T/F: When I delete a value from an AVL tree, I will perform a maximum of two rotations

Answer 17

False. Although you only need one rotation to fix a zig-zig and two rotations to fix a zig-zag, when they are fixed, you tree may still be unbalanced, so you have to keep traversing up to the root of the try to check imbalances.

Question 18

Suppose I have a vector with n elements and an iterator to one of its elements. What is the running time
of deleting the element

Answer 18

This is O(n).