Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. Indicate whether a stack would be a suitable data structure for each of the following applications.

    1. A program to evaluate arithmetic expressions according to the specific order of operators.

    2. A bank simulation of its teller operation to see how waiting times would be affected by adding another teller.

    3. A program to receive data that are to be saved and processed in the reverse order.

    4. An address book to be maintained.

    5. A word processor to have a PF key that causes the preceding command to be redisplayed. Every time the user presses the PF key, the program shows the command that preceded the one currently displayed.

    6. A dictionary of words used by a spelling checker to be built and maintained.

    7. A program to keep track of patients as they check into a medical clinic, assigning patients to doctors on a first come, first served basis.

    8. A data structure used to keep track of the return addresses for nested functions while a program is running.

  2. Describe the accessing protocol of a stack at the abstract level.

  3. Show what is written by the following segments of code, given that item1, item2, and item3 are int variables.

    1. StackType<int> stack;
      item1 = 1;
      item2 = 0;
      item3 = 4;
      stack.Push(item2);
      stack.Push(item1);
      stack.Push(item1 + item3);
      stack.Pop(item2);
      stack.Push(item3*item3);
      stack.Push(item2);
      stack.Push(3);
      stack.Pop(item1);
      cout  << item1  << end1  << item2  << end1  << item3
            << end1;
      while (!stack.IsEmpty())
      {
        stack.Pop(item1);
        cout << item1 << end1;
      }
      
    2. StackType<int> stack;
      item1 = 4;
      item3 = 0;
      item2 = item1 + 1;
      stack.Push(item2);
      stack.Push(item2 + 1);
      stack.Push(item1);
      stack.Pop(item2);
      item1 = item2 + 1;
      stack.Push(item1);
      stack.Push(item3);
      while (!stack.IsEmpty())
      {
        stack.Pop(item3);
        cout << item3  << end1;
      }
      cout << item1 << end1  << item2  << end1  << item3  << end1;
      

    Use the following information for Exercises 4-7. The stack is implemented as a class containing an array of items, a data member indicating the index of the last item put on the stack (top), and two Boolean data members, underFlow and overFlow. The stack items are characters and MAX_ITEM is 5. In each exercise, show the result of the operation on the stack. Put a T or F for true or false, respectively, in the Boolean data members.

  4. stack.Push(letter);

    Click To expand
  5. stack.Push(letter);

    Click To expand
  6. stack.Pop(letter);

    Click To expand
  7. stack.Pop(letter);

    Click To expand
  8. Write a segment of code to perform each of the following operations. You may call any of the member functions of StackType. The details of the stack type are encapsulated; you may use only the stack operations in the specification to perform the operations. (You may declare additional stack objects).

    1. Set secondElement to the second element in the stack, leaving the stack without its original top two elements.

    2. Set bottom equal to the bottom element in the stack, leaving the stack empty.

    3. Set bottom equal to the bottom element in the stack, leaving the stack unchanged.

    4. Make a copy of the stack, leaving the stack unchanged.

  9. (Multiple choice) The statement

    stack.items[0] = stack.items[1];
    

    (setting the top element equal to the second element) in a client program of the stack class

    1. would cause a syntax error at compile time.

    2. would cause a run-time error.

    3. would not be considered an error by the computer, but would violate the encapsulation of the stack data type.

    4. would be a perfectly legal and appropriate way to accomplish the intended task.

  10. (Multiple choice) The statements

    stack.Push(item1 + 1);
    stack.Pop(item1 + 1);
    

    in the client program

    1. would cause a syntax error at compile time.

    2. would cause a run-time error.

    3. would be legal, but would violate the encapsulation of the stack.

    4. would be perfectly legal and appropriate.

  11. Given the following specification of the Top operation:

    Assume Top is not a stack operation and Pop returns the item removed. Write this function as client code, using operations from the nontemplate version of the StackType class. Remember-the client code has no access to the private members of the class.

  12. Two stacks of positive integers are needed, one containing elements with values less than or equal to 1,000 and the other containing elements with values larger than 1,000. The total number of elements in the small-value stack and the large-value stack combined are not more than 200 at any time, but we cannot predict how many are in each stack. (All of the elements could be in the small-value stack, they could be evenly divided, both stacks could be empty, and so on.) Can you think of a way to implement both stacks in one array?

    1. Draw a diagram of how the stack might look.

    2. Write the definitions for such a double-stack structure.

    3. Implement the Push operation; it should store the new item into the correct stack according to its value (compared to 1,000).

  13. A stack of integer elements is implemented as an array. The index of the top element is kept in position 0 in the array, and the stack elements are stored in stack[1]..stack[stack[0]}.

    1. How does this implementation fare when assessed against the idea of an array as a homogeneous collection of data elements?

    2. How would this implementation change the stack specifications? How would it change the implementations of the functions?

  14. Using one or more stacks, write a code segment to read in a string of characters and determine whether it forms a palindrome. A palindrome is a sequence of characters that reads the same both forward and backward-for example: ABLE WAS I ERE I SAW ELBA.

    The character '.' ends the string. Write a message indicating whether the string is a palindrome. You may assume that the data are correct and that the maximum number of characters is 80.

  15. Write the body for a function that replaces each copy of an item in a stack with another item. Use the following specification. (This function is in the client program.)

    You may use any of the member functions of the nontemplate version of StackType, but you may not assume any knowledge of the stack's implementation.

  16. In each plastic container of Pez candy, the colors are stored in random order. Your little brother likes only the yellow ones, so he painstakingly takes out all the candies, one by one, eats the yellow ones, and keeps the others in order, so that he can return them to the container in exactly the same order as before-minus the yellow candies, of course. Write the algorithm to simulate this process. You may use any of the stack operations defined in the Stack ADT, but may not assume any knowledge of the stack's implementation.

  17. The specifications for the Stack ADT have been changed. The class representing the stack must now check for overflow and underflow and sets an error flag (a parameter) to true if either occurs. (See the discussion on page 206.)

    1. Rewrite the specifications incorporating this change.

    2. What new data members must you add to the class?

    3. What new member functions must you add to the class?

  18. Implement the following specification for a client Boolean function that returns true if two stacks are identical and false otherwise.

    You may use any of the member functions of StackType, but you may not assume any knowledge of the stack's implementation.

The following code segment (used for Exercises 19 and 20) is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a stack depending on the result of the Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the stack are popped and printed. Because of the logical properties of a stack, this code segment cannot print certain sequences of the values of the loop counter. You are given an output and asked to determine whether the code segment could generate the output.

      for (count = 1; count <= 5; count++)
        if (RanFun())
          cout  <<  count;
        else
         stack.Push(count);
      while (!stack.IsEmpty())
      {
         stack.Pop(number);
         cout << number;
      }
  1. The following output is possible using a stack: 1 3 5 2 4

    1. True

    2. False

    3. Not enough information to determine

  2. The following output is possible using a stack: 1 3 5 4 2

    1. True

    2. False

    3. Not enough information to determine

  3. Based on the following declarations, tell whether each statement below is syntactically legal (yes) or illegal (no).

    int* p;
    int* q;
    int* r;
    int a;
    int b;
    int c;
    
     

    yes/no

    1. p = new int ;

    _____

    1. q* = new int;

    _____

    1. a = new int;

    _____

    1. p = r;

    _____

    1. q = b;

    _____

    1. r = NULL;

    _____

    1. c = *p;

    _____

    1. p = *a;

    _____

    1. delete b;

    _____

    1. q = &c ;

    _____

    1. delete r;

    _____

    1. a = new p;

    _____

    1. q* = NULL;

    _____

    1. *p = a;

    _____

    1. c = NULL;

    _____

  4. The following program has careless errors on several lines. Find and correct the errors and show the output where requested.

    #include <iostream>
    int main ()
    {
      using namespace std;
      int* ptr;
      int* temp;
      int x;
    
      ptr = new int ;
      *ptr = 4;
      "temp = *ptr;
      cout  << ptr  << temp;
      x = 9;
      *temp = x;
      cout  << *ptr  << *temp;
      ptr = new int;
      ptr = 5 ;
      cout  << *ptr  << *temp;  // Output:______________
      return 0;
    }
    
  5. Describe the accessing protocol of a queue at the abstract level.

  6. Show what is written by the following segments of code, given that item1, item2, and item3 are int variables.

    1. QueType<int> queue;
      
      item1 = 1;
      item2 = 0;
      item3 = 4;
      queue.Enqueue(item2);
      queue.Enqueue(item1);
      queue.Enqueue(item1 + item3);
      queue.Dequeue(item2);
      queue.Enqueue(item3*item3);
      queue.Enqueue(item2);
      queue.Enqueue(3); queue.Dequeue(item1);
      cout  << item1  << end1  << item2  << end1  << item3
            << end1;
      while (!queue.IsEmpty())
      {
         queue.Dequeue(item1);
         cout << item1 << end1;
      }
      
    2. QueType<int> queue;
      item1 = 4;
      item3 = 0;
      item2 = item1 + 1;
      queue.Enqueue(item2);
      queue.Enqueue(item2 + 1);
      queue.Enqueue(item1);
      queue.Dequeue(item2);
      item1 = item2 + 1;
      queue.Enqueue(item1);
      queue.Enqueue(item3);
      while (!queue.IsEmpty())
      {
        queue.Dequeue(item3);
        cout << item3  << end1;
      }
      cout << item1 << end1  << item2  << end1  << item3  << end1;
      
  7. The specifications for the Queue ADT have been changed. The class representing the queue must now check for overflow and underflow and set an error flag (a parameter) to true if either occurs.

    1. Rewrite the specifications incorporating this change.

    2. What new data members must you add to the class?

    3. What new member functions must you add to the class?

Use the following information for Exercises 26-31. The queue is implemented as a class containing an array of items, a data member indicating the index of the last item put on the queue (rear), a data member indicating the index of the location before the first item put on the queue (front), and two Boolean data members, underFlow and overFlow, as discussed in this chapter. The item type is char and maxQue is 5. For each exercise, show the result of the operation on the queue. Put a T or F for true or false, respectively, in the Boolean data members.

  1. queue.Enqueue(letter);

    Click To expand
  2. queue.Enqueue(letter);

    Click To expand
  3. queue.Enqueue(letter);

    Click To expand
  4. queue.Dequeue(letter);

    Click To expand
  5. queue.Dequeue(letter);

    Click To expand
  6. queue.Dequeue(letter);

    Click To expand
  7. Write a segment of code to perform each of the following operations. You may call any of the member functions of QueType. The details of the queue are encapsulated; you may use only the queue operations in the specification to perform the operations. (You may declare additional queue objects.)

    1. Set secondElement to the second element in the queue, leaving the queue without its original front two elements.

    2. Set last equal to the rear element in the queue, leaving the queue empty.

    3. Set last equal to the rear element in the queue, leaving the queue unchanged.

    4. Make a copy of the queue, leaving the queue unchanged.

  8. (Multiple choice) The statement

    queue.items[1] = queue.items[2];
    

    (setting one element equal to the next element) in a client program of the queue class

    1. would cause a syntax error at compile time.

    2. would cause a run-time error.

    3. would not be considered an error by the computer, but would violate the encapsulation of the queue data type.

    4. would be a perfectly legal and appropriate way to accomplish the intended task.

  9. (Multiple choice) The statements

    queue.Enqueue(item1 + 1);
    queue.Dequeue(item1 + 1);
    

    in the client program

    1. would cause a syntax error at compile time.

    2. would cause a run-time error.

    3. would be legal, but would violate the encapsulation of the queue.

    4. would be perfectly legal and appropriate.

  10. Given the following specification of a Front operation:

    1. Write this function as client code, using operations from the QueType class. (Remember-the client code has no access to the private members of the class.)

    2. Write this function as a new member function of the QueType class.

  11. Write the body for a function that replaces each copy of an item in a queue with another item. Use the following specification. (This function is in the client program.)

    You may use any of the member functions of QueType, but you may not assume any knowledge of the queue's implementation.

  12. Indicate whether each of the following applications would be suitable for a queue.

    1. An ailing company wants to evaluate employee records so as to lay off some workers on the basis of service time (the most recently hired employees are laid off first).

    2. A program is to keep track of patients as they check into a clinic, assigning them to doctors on a first come, first served basis.

    3. A program to solve a maze is to backtrack to an earlier position (the last place where a choice was made) when a dead-end position is reached.

    4. An inventory of parts is to be processed by part number.

    5. An operating system is to process requests for computer resources by allocating the resources in the order in which they are requested.

    6. A grocery chain wants to run a simulation to see how the average customer wait time would be affected by changing the number of checkout lines in its stores.

    7. A dictionary of words used by a spelling checker is to be initialized.

    8. Customers are to take numbers at a bakery and be served in order when their numbers come up.

    9. Gamblers are to take numbers in the lottery and win if their numbers are picked.

  13. Implement the following specification for a Boolean function in the client program that returns true if two queues are identical and false otherwise.

    You may use any of the member functions of QueType, but you may not assume any knowledge of the queue's implementation.

  14. Implement the following specification for an integer function in the client program that returns the number of items in a queue. The queue is unchanged.

  15. One queue implementation discussed in this chapter dedicated an unused cell before the front of the queue to distinguish between a full queue and an empty queue. Write another queue implementation that keeps track of the length of the queue in a data member length.

    1. Write the class definition for this implementation.

    2. Implement the member functions for this implementation. (Which of the member functions have to be changed and which do not?)

    3. Compare this new implementation with the previous one in terms of Big-O notation.

  16. Write a queue application that determines if two files are the same.

  17. Discuss the difference between the MakeEmpty operation in the specification and a class constructor.

The following code segment (used for Exercises 43 and 44) is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a queue depending on the result of the Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the queue are dequeued and printed. Because of the logical properties of a queue, this code segment cannot print certain sequences of the values of the loop counter. You are given an output and asked to determine whether the code segment could generate the output.

      for (count = 1; count <= 5; count++)
        if (RanFun())
          cout << count;
        else
          queue.Enqueue(count);
      while (!queue.IsEmpty())
      {
        queue.Dequeue(number);
        cout << number;
      }
  1. The following output is possible using a queue: 1 2 3 4 5

    1. True

    2. False

    3. Not enough information to determine

  2. The following output is possible using a queue: 1 3 5 4 2

    1. True

    2. False

    3. Not enough information to determine

  3. Change the code for the program Balanced so that the calls to Push, Pop, and Top are embedded within a try clause. The catch clause should print an appropriate error message and halt.

  4. Rewrite QueType as a class template.

  5. Define and implement a counted stack, which inherits from StackType.



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