Data Structures Review

Quick Sort runs in O(n) if all elements are equal.

• True

• False

Binary search is an example of binary recursion

• True

• False

Bucket sort is always better than quick sort because it has linear time complexity.

• True

• False

Let n be the number of elements in the stack. The push method of the stack runs in

• O(logn)

• O(n)

• O(n^2)

• O(1)

The space usage of ArrayQueue is O(n) where n is the number of elements in the queue.

• True

• False

One of these is not a method from the Positional List ADT

• addFirst(p, e)

• addBefore(p, e)

• set(p, e)

• addAfter(p, e)

The return type of the 'set' method of Positional List is

• void

• E

• Position<E>

• None of the above

The remove method of Linked Positional List runs in O(n) time, where n is the size of the list, because we need to shift the positions after the removal.

• True

• False

Let n be the number of nodes in an Array-Based Binary Tree. The running time of removing a node is

• O(n)

• O(logn)

• O(1)

• O(n^2)

A binary tree with nodes that have either zero or two

children, is called

• perfect

• complete

• proper

• balanced