# Sample Flashcards

1
Q

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

A

True

2
Q

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

A

False

3
Q

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

A

True

4
Q

Quicksort always performs more efficiently than merge sort.

A

False.

5
Q

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

A

True

6
Q

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

A

False.

7
Q

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

A

False.

8
Q

A

True.

9
Q

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

A

False.

10
Q

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

A

True.

11
Q

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

A

False.

12
Q

A

True.

13
Q

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

A

True.

14
Q

Huffman coding trees support variable-length encoding.

A

True.

15
Q

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

A

True.

16
Q

Huffman coding trees support fixed-length encoding.

A

False.

17
Q

Huffman coding trees have minimum external path weight.

A

True.

18
Q

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

A

False.

19
Q

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

A

False.

20
Q

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

A

Multiply its weight (frequency) by its depth.

21
Q

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

A

By summing the weighted path lengths of its leaves.

22
Q

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

A

True (unbalanced).

23
Q

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

A

False.

24
Q

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

A

True.

25
Q

Binary search trees do not work when duplicates are allowed.

A

False

26
Q

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

A

True.

27
Q

BST are most commonly implemented within arrays.

A

False.

28
Q

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

A

It is the sum of the weights of its leaves.

29
Q

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

A

True.

30
Q

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

A

False.

31
Q

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

A

False.

32
Q

Dictionary search keys are comparable.

A

True.

33
Q

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

A

True.

34
Q

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

A

False.

35
Q

A heap in an array will generally always be complete.

A

True.

36
Q

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

A

True.

37
Q

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

A

True - complete heap traversal is required.

38
Q

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

A

False.

39
Q

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

A

False.

40
Q

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

A

False.

41
Q

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.

A

True.

42
Q

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

A

True

43
Q

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

A

True.

44
Q

Binary trees must be traversed depth-first.

A

False.

45
Q

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

A

True.

46
Q

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.

A

False.

47
Q

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.

A

False - this is inorder traversal.

48
Q

A heap is the standard BST used in priority queues.

A

False.

49
Q

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

A

False.

50
Q

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

A

True.

51
Q

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

A

True.

52
Q

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

A

True.

53
Q

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

A

False.