# Sample Flashcards

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

True

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

False

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

True

Quicksort always performs more efficiently than merge sort.

False.

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

True

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

False.

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

False.

Linked lists can be readily traversed using the next operator.

True.

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

False.

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

True.

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

False.

Linked lists are composed of nodes or links.

True.

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

True.

Huffman coding trees support variable-length encoding.

True.

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

True.

Huffman coding trees support fixed-length encoding.

False.

Huffman coding trees have minimum external path weight.

True.

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

False.

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

False.

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

Multiply its weight (frequency) by its depth.

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

By summing the weighted path lengths of its leaves.