Algorithms Final Exam Study Guide

53 Questions | Total Attempts: 525  Settings  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 Back to top