Algorithms Final Exam Study Guide

53 Questions | Total Attempts: 525

SettingsSettingsSettings
Please wait...
Algorithms Final Exam Study Guide

Exam 1-3, True/False questions & multiple choice questions.


Questions and Answers
  • 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

Back to Top Back to top