Sample

Question 1

Quicksort - when available, tail recursion eliminates stack overflows caused by pathological pivot selection.

Answer 1

True

Question 2

With proper pivot selection, Quicksort performs in Θ(n) in the best case of inputs.

Answer 2

False

Question 3

Quicksort - Diverting to a heap sort after a certain depth can prevent Θ(n^2) complexity in the worst case.

Answer 3

True

Question 4

Quicksort always performs more efficiently than merge sort.

Answer 4

False.

Question 5

A pathological case for quicksort when always selecting the rightmost value as the pivot would be to sort an already sorted data.

Answer 5

True

Question 6

When available, tail recursion can prevent Θ(n^2) complexity in the worst case.

Answer 6

False.

Question 7

Linked lists can deal with growth effectively by doubling its size when it reaches half capacity.

Answer 7

False.

Question 8

Linked lists can be readily traversed using the next operator.

Answer 8

True.

Question 9

Linked lists are more efficient data structures than array-based lists of size 2n by a constant factor when performing a merge sort.

Answer 9

False.

Question 10

Linked lists can deal with growth effectively by keeping a pool of unused nodes.

Answer 10

True.

Question 11

Linked lists are less effective than an Array-based list when the values stored in each node are objects of varying size.

Answer 11

False.

Question 12

Linked lists are composed of nodes or links.

Answer 12

True.

Question 13

You can use a priority queue to build a Huffman coding tree.

Answer 13

True.

Question 14

Huffman coding trees support variable-length encoding.

Answer 14

True.

Question 15

In Huffman coding trees, more frequently occurring characters will be closer to the top.

Answer 15

True.

Question 16

Huffman coding trees support fixed-length encoding.

Answer 16

False.

Question 17

Huffman coding trees have minimum external path weight.

Answer 17

True.

Question 18

Huffman - if the frequencies of characters are different on the text to be encoded, the Huffman coding still always outperforms fixed-length encoding.

Answer 18

False.

Question 19

The combined weight of all edges yields the weighted path length.

Answer 19

False.

Question 20

How do you obtain the weighted path length of a leaf?

Answer 20

Multiply its weight (frequency) by its depth.

Question 21

How do you obtain the external path weight of a Huffman tree?

Answer 21

By summing the weighted path lengths of its leaves.

Question 22

In the average case, BST access time can be Θ(n).

Answer 22

True (unbalanced).

Question 23

Given an array of sorted values, it takes a best Θ(n log n) operations to create a balanced BST.

Answer 23

False.

Question 24

When removing a node from a BST, the smallest node form its right subtree can be promoted to replace the removed node.

Answer 24

True.

Question 25

Binary search trees do not work when duplicates are allowed.

Answer 25

False

Question 26

When removing a node from a BST, the smallest node from its right subtree can be promoted to replace the removed node.

Answer 26

True.

Question 27

BST are most commonly implemented within arrays.

Answer 27

False.

Question 28

In a Huffman coding tree, what is the weight of the root node?

Answer 28

It is the sum of the weights of its leaves.

Question 29

Asymptotic complexity of dictionary operations depends on the underlying storage mechanism.

Answer 29

True.

Question 30

Dictionary - All possible keys are considered when comparing two records for placement.

Answer 30

False.

Question 31

Dictionary - Finding a record with a sorted array-based list as the underlying storage mechanism is of complexity Θ(n).

Answer 31

False.

Question 32

Dictionary search keys are comparable.

Answer 32

True.

Question 33

Dictionary - Removing a record with an unsorted array based list as the underlying storage mechanism is of complexity Θ(n).

Answer 33

True.

Question 34

Dictionaries cannot be used with multi-dimensional keys, like points.

Answer 34

False.

Question 35

A heap in an array will generally always be complete.

Answer 35

True.

Question 36

The height of a heap in an array is known if know how many elements are in it.

Answer 36

True.

Question 37

Finding an element in a heap takes Θ(n) operations.

Answer 37

True - complete heap traversal is required.

Question 38

Finding an element in a heap takes Θ(log n) operations.

Answer 38

False.

Question 39

Starting from the end of the array where a heap is stored, it takes Θ(n) operations to find the first non-leaf node.

Answer 39

False.

Question 40

A heap in an array will in general always be full.

Answer 40

False.

Question 41

If you add one child to any node that has only one child, and two children to every leaf node, you have added n + 1 nodes.

Answer 41

True.

Question 42

Postorder is a traversal of a binary tree where children are processed before the parent node is processed.

Answer 42

True

Question 43

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

Answer 43

True.

Question 44

Binary trees must be traversed depth-first.

Answer 44

False.

Question 45

Preorder is a traversal of a binary tree where children are processed after the parent node is processed.

Answer 45

True.

Question 46

If you add one child to any node that has only one child, and two children to every leaf node, you have added n nodes.

Answer 46

False.

Question 47

Preorder is a traversal of a binary tree where the left child is processed before the parent node, and the right child is processed last.

Answer 47

False - this is inorder traversal.

Question 48

A heap is the standard BST used in priority queues.

Answer 48

False.

Question 49

Θ(n log n) is a realistic complexity to find the next item, for a well written priority queue.

Answer 49

False.

Question 50

Adding/removing nodes and retrieving the highest priority element will have the same complexity for a heap.

Answer 50

True.

Question 51

Θ(log n) is a realistic complexity to find the next item, for a well written priority queue.

Answer 51

True.

Question 52

A max-heap, where the key is the priority, is the optimal form of heap for a priority queue.

Answer 52

True.

Question 53

Θ(n) is a realistic complexity to find the next item, for a well written priority queue.

Answer 53

False.