1.
The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
2.
An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
3.
For a node A at index i in a heap, the right child of A can be computed as 2*i.
4.
The master method can be used to solve all recurrence equations that have the form T(n) = aT(n/b) + f(n).
5.
Quicksort has a worst-case running time of θ(n^2).
6.
One good reason for using a hash table would be to reduce storage requirements.
7.
If we are using the division method for our hashing function, a table size of 64 would be a good choice.
8.
Printing every node in a binary tree takes θ(lg n) time.
9.
We do not have to make any key comparisons to find the min or max nodes of a binary search tree.
10.
Open addressing is usually preferred over chaining for solving hash function collisions.
11.
Red-black trees are an attempt to minimize the time of dynamic set operations by creating a balanced tree.
12.
In a red-black tree, a black node must have only red children.
13.
A problem that generates completely new subproblems at each step is a good candidate for a dynamic programming solution.
14.
Dynamic programming has the potential to transform exponential-time algorithms to polynomial time.
15.
A topological sort for a directed acyclic graph (DAG) can be created by performing a breadth-first search on the DAG.
16.
A minimum spanning tree for a graph with N vertices will have N-2 edges.
17.
A matrix is a good choice for representing a dense graph.
18.
Both matrix and lists can be used to represent weighted graphs.
19.
In Kruskal's algrorithm for building a minimum spanning tree, we proceed node by node, adding the connecting edges to the tree.
20.
Huffman encoding uses a dynamic programming strategy to compress data.
21.
Which one of the following is a true for a red-black tree?
A.
B.
The root and leaves are black.
C.
All simple paths from a node to the leaves contain the same number of red and black nodes.
D.
A red node can have only one black child.
22.
What distinguishing feature should cause us to choose dynamic programming rather than a divide-and-conquer approach to a problem?
A.
It is an optimization problem.
B.
The problem can be solved recursively.
C.
The problem does not have a brute force solution.
D.
The subproblems for the solution overlap.
23.
Which of the following is true regarding Prim's algorithm for finding a minimum spanning tree?
A.
The starting node must be connected to the edge with the least weight.
B.
The algorithm grows only a single tree from start to finish.
C.
"Marked" nodes indicate nodes that will not be in the final tree.
D.
When selecting the next edge, we consider only edges that connect unmarked nodes to the other unmarked nodes.
24.
Which of the following is NOT a property of a minimum spanning tree?
A.
It may have one or more cycles.
B.
C.
It is not necessarily unique.
D.
The sum of weights of the edges is minimal.
25.
What is the name of the technique that stores computed values for future lookup, rather than recomputing them?