Algorithms Final Exam Study Guide
Exam 1-3, True/False questions & multiple choice questions.
- 1.The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
- A.
True
- B.
False
- 2.An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
- A.
True
- B.
False
- 3.For a node A at index i in a heap, the right child of A can be computed as 2*i.
- A.
True
- B.
False
- 4.The master method can be used to solve all recurrence equations that have the form T(n) = aT(n/b) + f(n).
- A.
True
- B.
False
- 5.Quicksort has a worst-case running time of θ(n^2).
- A.
True
- B.
False
- 6.One good reason for using a hash table would be to reduce storage requirements.
- A.
True
- B.
False
- 7.If we are using the division method for our hashing function, a table size of 64 would be a good choice.
- A.
True
- B.
False
- 8.Printing every node in a binary tree takes θ(lg n) time.
- A.
True
- B.
False
- 9.We do not have to make any key comparisons to find the min or max nodes of a binary search tree.
- A.
True
- B.
False
- 10.Open addressing is usually preferred over chaining for solving hash function collisions.
- A.
True
- B.
False
- 11.Red-black trees are an attempt to minimize the time of dynamic set operations by creating a balanced tree.
- A.
True
- B.
False
- 12.In a red-black tree, a black node must have only red children.
- A.
True
- B.
False
- 13.A problem that generates completely new subproblems at each step is a good candidate for a dynamic programming solution.
- A.
True
- B.
False
- 14.Dynamic programming has the potential to transform exponential-time algorithms to polynomial time.
- A.
True
- B.
False
- 15.A topological sort for a directed acyclic graph (DAG) can be created by performing a breadth-first search on the DAG.
- A.
True
- B.
False
- 16.A minimum spanning tree for a graph with N vertices will have N-2 edges.
- A.
True
- B.
False
- 17.A matrix is a good choice for representing a dense graph.
- A.
True
- B.
False
- 18.Both matrix and lists can be used to represent weighted graphs.
- A.
True
- B.
False
- 19.In Kruskal's algrorithm for building a minimum spanning tree, we proceed node by node, adding the connecting edges to the tree.
- A.
True
- B.
False
- 20.Huffman encoding uses a dynamic programming strategy to compress data.
- A.
True
- B.
False
- 21.Which one of the following is a true for a red-black tree?
- A.
The root is red.
- 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.
It has |V| -1 edges.
- 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?
- A.
Overlapping subproblems
- B.
Topological sort
- C.
Memoization
- D.
Dynamic recursion
Related Topics
Recent Quizzes
Back to top