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.
In the average case, BST access time can be Θ(n).
True (unbalanced).
Given an array of sorted values, it takes a best Θ(n log n) operations to create a balanced BST.
False.
When removing a node from a BST, the smallest node form its right subtree can be promoted to replace the removed node.
True.
Binary search trees do not work when duplicates are allowed.
False
When removing a node from a BST, the smallest node from its right subtree can be promoted to replace the removed node.
True.
BST are most commonly implemented within arrays.
False.
In a Huffman coding tree, what is the weight of the root node?
It is the sum of the weights of its leaves.
Asymptotic complexity of dictionary operations depends on the underlying storage mechanism.
True.
Dictionary - All possible keys are considered when comparing two records for placement.
False.
Dictionary - Finding a record with a sorted array-based list as the underlying storage mechanism is of complexity Θ(n).
False.
Dictionary search keys are comparable.
True.
Dictionary - Removing a record with an unsorted array based list as the underlying storage mechanism is of complexity Θ(n).
True.
Dictionaries cannot be used with multi-dimensional keys, like points.
False.
A heap in an array will generally always be complete.
True.
The height of a heap in an array is known if know how many elements are in it.
True.
Finding an element in a heap takes Θ(n) operations.
True - complete heap traversal is required.
Finding an element in a heap takes Θ(log n) operations.
False.
Starting from the end of the array where a heap is stored, it takes Θ(n) operations to find the first non-leaf node.
False.
A heap in an array will in general always be full.
False.
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.
True.
Postorder is a traversal of a binary tree where children are processed before the parent node is processed.
True
The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
True.
Binary trees must be traversed depth-first.
False.
Preorder is a traversal of a binary tree where children are processed after the parent node is processed.
True.
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.
False.
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.
False - this is inorder traversal.
A heap is the standard BST used in priority queues.
False.
Θ(n log n) is a realistic complexity to find the next item, for a well written priority queue.
False.
Adding/removing nodes and retrieving the highest priority element will have the same complexity for a heap.
True.
Θ(log n) is a realistic complexity to find the next item, for a well written priority queue.
True.
A max-heap, where the key is the priority, is the optimal form of heap for a priority queue.
True.
Θ(n) is a realistic complexity to find the next item, for a well written priority queue.
False.
