Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. A priority queue containing characters is implemented as a heap stored in an array. The precondition states that this priority queue cannot contain duplicate elements. Currently, the priority queue holds 10 elements, as shown on the next page. What values might be stored in array positions 7-9 so that the properties of a heap are satisfied?

    Click To expand
  2. A minimum heap has the following order property: The value of each element is less than or equal to the value of each of its children. What changes must be made in the heap operations given in this chapter?

    1. Write a nonrecursive version of ReheapDown.

    2. Write a nonrecursive version of ReheapUp.

    3. Describe the nonrecursive versions of these operations in terms of Big-O notation.

  3. A priority queue is implemented as a heap:

    Click To expand
    1. Show how the heap would look after this series of operations:

      pq.Enqueue(28);
      pq.Enqueue(2);
      pq.Enqueue(40);
      pq.Dequeue(x);
      pq.Dequeue(y);
      pq.Dequeue(z);
      
    2. What would the values of x, y, and z be after the series of operations in part (a)?

  4. A priority queue is implemented as a linked list, sorted from largest to smallest element.

    1. How would the definition of PQType change?

    2. Write the Enqueue operation, using this implementation.

    3. Write the Dequeue operation, using this implementation.

    4. Compare the Enqueue and Dequeue operations to those for the heap implementation, in terms of Big-O notation.

  5. A priority queue is implemented as a binary search tree.

    1. How would the definition of PQType change?

    2. Write the Enqueue operation, using this implementation.

    3. Write the Dequeue operation, using this implementation.

    4. Compare the Enqueue and Dequeue operations to those for the heap implementation, in terms of Big-O notation. Under what conditions would this implementation be better or worse than the heap implementation?

  6. A priority queue is implemented as a sequential array-based list. The highest-priority item is in the first array position, the second-highest priority item is in the second array position, and so on.

    1. Write the declarations in the private part of the priority queue class definition needed for this implementation.

    2. Write the Enqueue operation, using this implementation.

    3. Write the Dequeue operation, using this implementation.

    4. Compare the Enqueue and Dequeue operations to those for the heap implementation, in terms of Big-O notation. Under what conditions would this implementation be better or worse than the heap implementation?

  7. A stack is implemented using a priority queue. Each element is time-stamped as it is put into the stack. (The time stamp is a number between 0 and INT_MAX. Each time an element is pushed onto the stack, it is assigned the next larger number.)

    1. What is the highest-priority element?

    2. Write the Push and Pop algorithms, using the specifications in Chapter 4.

    3. Compare these Push and Pop operations to the ones implemented in Chapter 4, in terms of Big-O notation.

  8. A FIFO queue is implemented using a priority queue. Each element is time-stamped as it is put into the queue. (The time stamp is a number between 0 and INT_MAX. Each time an element is enqueued, it is assigned the next larger number.)

    1. What is the highest-priority element?

    2. Write the Enqueue and Dequeue operations, using the specifications in Chapter 4.

    3. Compare these Enqueue and Dequeue operations to the ones implemented in Chapter 4, in terms of Big-O notation.

  9. A priority queue of strings is implemented using a heap. The heap contains the following elements:

    Click To expand
    1. What feature of these strings is used to determine their priority in the priority queue?

    2. Show how this priority queue is affected by adding the string "interviewing."

Use the following description of an undirected graph in Exercises 11-14.

EmployeeGraph

=

(V, E)

V(EmployeeGraph)

=

{Susan, Darlene, Mike, Fred, John, Sander, Lance, Jean, Brent, Fran}

E(EmployeeGraph)

=

{(Susan, Darlene), (Fred, Brent), (Sander, Susan), (Lance, Fran), (Sander, Fran), (Fran, John), (Lance, Jean), (Jean, Susan), (Mike, Darlene), (Brent, Lance), (Susan, John)}

  1. Draw a picture of EmployeeGraph.

  2. Draw EmployeeGraph, implemented as an adjacency matrix. Store the vertex values in alphabetical order.

  3. Using the adjacency matrix for EmployeeGraph from Exercise 12, describe the path from Susan to Lance

    1. using a breadth-first strategy.

    2. using a depth-first strategy.

  4. Which one of the following phrases best describes the relationship represented by the edges between the vertices in EmployeeGraph?

    1. "works for"

    2. "is the supervisor of"

    3. "is senior to"

    4. "works with"

Use the following specification of a directed graph in Exercises 15-18.

ZooGraph

=

(V, E)

V(ZooGraph)

=

{dog, cat, animal, vertebrate, oyster, shellfish, invertebrate, crab, poodle, monkey, banana, dalmatian, dachshund}

E(ZooGraph)

=

{(vertebrate, animal), (invertebrate, animal), (dog, vertebrate), (cat, vertebrate), (monkey, vertebrate), (shellfish, invertebrate), (crab, shellfish), (oyster, shellfish), (poodle, dog), (dalmatian, dog), (dachshund, dog)}

  1. Draw a picture of ZooGraph.

  2. Draw the adjacency matrix for ZooGraph. Store the vertices in alphabetical order.

  3. To tell if one element in ZooGraph has relation X to another element, you look for a path between them. Show whether the following statements are true, using the picture or adjacency matrix.

    1. dalmatian X dog

    2. dalmatian X vertebrate

    3. dalmatian X poodle

    4. banana X invertebrate

    5. oyster X invertebrate

    6. monkey X invertebrate

  4. Which of the following phrases best describes relation X in Exercise 17?

    1. "has a"

    2. "is an example of"

    3. "is a generalization of"

    4. "eats"

Use the following graph for Exercises 19-21.

Click To expand
  1. Describe the graph pictured above, using the formal graph notation.

    V(StateGraph) =

    E(StateGraph) =

    1. Is there a path from Oregon to any other state in the graph?

    2. Is there a path from Hawaii to every other state in the graph?

    3. From which state(s) in the graph is there a path to Hawaii?

    1. Show the adjacency matrix that would describe the edges in the graph. Store the vertices in alphabetical order.

    2. Show the array-of-pointers adjacency lists that would describe the edges in the graph.

  2. Extend the class GraphType in this chapter to include a Boolean EdgeExists operation, which determines whether two vertices are connected by an edge.

    1. Write the declaration of this function. Include adequate comments.

    2. Using the adjacency matrix implementation developed in the chapter and the declaration from part (a), implement the body of the function.

  3. Extend the class GraphType in this chapter to include a DeleteEdge operation, which deletes a given edge.

    1. Write the declaration of this function. Include adequate comments.

    2. Using the adjacency matrix implementation developed in the chapter and the declaration from part (a), implement the body of the function.

  4. Extend the class GraphType in this chapter to include a DeleteVertex operation, which deletes a vertex from the graph. Deleting a vertex is more complicated than deleting an edge from the graph. Discuss why.

  5. The DepthFirstSearch operation can be implemented without a stack by using recursion.

    1. Name the base case(s). Name the general case(s).

    2. Write the algorithm for a recursive depth-first search.

  6. Distinguish between set representations that are implicit and those that are explicit.

  7. Finish designing the algorithms for the explicit set representation.

  8. Finish designing the algorithms for the implicit set representation.

  9. Implement the copy constructor for PQType.

  10. Did you notice that we did not include a copy constructor from GraphType? Discuss the issues involved in implementing this copy constructor.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)