Sample Data Structures Questions
Chapter 7
Queues

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

The Purpose of These Questions

Short Answers

Short Answers Sections 7.1 - 7.2 Queues and Their Applications

1. Complete the body of this method. Use a CharQueue to store the input line as it is being read. The parameter is an EasyReader from Appendix B of the text. Use the method in.charInput( ) to read and return the next character of the EasyReader, and use in.isEOLN( ) to determine whether the next input character is the end-of-line.

   
       public static int counter(EasyReader in)
       // Precondition: There is a line of input waiting to be read from in.
       // Postcondition: A line of input has been read from in, up to but not
       // including the newline character. The return value of the method
       // is the number of times that the LAST character of the line appeared
       // somewhere in this line.
       // EXAMPLE Input: ABBXDXXZX
       // The value returned by counter would be 4 for this input since there
       // are 4 X's in the input line.
   

   Short Answers Section 7.3 Implementations of the Queue ADT

2. I am going to execute this code with THREE inserts and ONE get_front:

   
      IntQueue q = new IntQueue( );
      q.insert(1);
      q.insert(2);
      q.insert(3);
      System.out.println(q.getFront( ));
   

   Suppose that q is represented by a circular array. Draw the state of these private instance variables of q after the above code:

   
              _______            __________________________________
        front|       |      data|      |      |      |      |      |
             |_______|          |______|______|______|______|______|
                                  [0]    [1]    [2]    [3]    [4]
   

3. I am going to execute this code with THREE insert and ONE get_front:

   
      IntQueue q = new IntQueue( );
      q.insert(1);
      q.insert(2);
      q.insert(3);
      System.out.println(q.getFront( ));
   

   Suppose that q is represented by a linked list. Draw the state of the private instance variables of q after the above code:

   
                  _______      
            front|       |  
                 |_______|     
                  _______      
             rear|       |  
                 |_______|     
   

4. Describe why it is a bad idea to implement a linked list version a queue which uses the head of the list as the rear of the queue.

   Short Answers Section 7.4 Priority Queues

5. Suppose that you want to implement the PriorityQueue so that insertions occur in constant time, but getFront requires linear time. You will use these class definitions, where the data entering the PriorityQueue is a String and the priorities are ints.

   
       public class PriorityQueue
       {
          // A PriorityNode is a node from a linked list of strings, with
          // methods for getString, setString, getPriority, setPriority,
          // getLink, and setLink.
          private PriorityNode head;
           
          public void insert(String entry, int priority)...
          public String getFront( )...
          ...
       }
   

   (A) Write ONE sentence to describe how the insert method will work (with constant time). (B) Then implement the getFront method (which will have linear worst-case time). In your implementation, you DO NOT have to worry about items with equal priority (they may come out of the prioirty queue however you like, without necessarily having FIFO behavior). To remove the head node of a linked list, use the assignment:

      head = head.getLink( );
   

Multiple Choice

Multiple Choice Sections 7.1-7.2 Queues and Their Applications

1. One difference between a queue and a stack is:
   • A. Queues require linked lists, but stacks do not.
   • B. Stacks require linked lists, but queues do not.
   • C. Queues use two ends of the structure; stacks use only one.
   • D. Stacks use two ends of the structure, queues use only one.

2. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?
   • A. ABCD
   • B. ABDC
   • C. DCAB
   • D. DCBA

3. Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).
   • A. Math.random() < P
   • B. Math.random() > P
   • C. Math.random() < P * 100
   • D. Math.random() > P * 100

   Multiple Choice Section 7.3 Implementations of the Queue ADT

4. Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The current capacity is 42. Where does the insert method place the new entry in the array?
   • A. data[1]
   • B. data[2]
   • C. data[11]
   • D. data[12]

5. Consider the implementation of the Queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).
   • A. The constructor would require linear time.
   • B. The getFront method would require linear time.
   • C. The insert method would require linear time.
   • D. The isEmpty method would require linear time.

6. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?
   • A. At the head
   • B. At the tail
   • C. After all other entries that are greater than the new entry.
   • D. After all other entries that are smaller than the new entry.

7. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?
   • A. getFront
   • B. insert when the capacity has not yet been reached
   • C. isEmpty
   • D. None of these operations require linear time.

8. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?
   • A. getFront
   • B. insert
   • C. isEmpty
   • D. None of these operations require linear time.

9. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?
   • A. (rear % 1) + CAPACITY
   • B. rear % (1 + CAPACITY)
   • C. (rear + 1) % CAPACITY
   • D. rear + (1 % CAPACITY)

10. I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems?
    • A. manyItems must be zero.
    • B. manyItems must be equal to the current capacity.
    • C. count could be zero or the capacity, but no other values could occur.
    • D. None of the above.

11. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?
    • A. Neither changes
    • B. Only front changes.
    • C. Only rear changes.
    • D. Both change.

12. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?
    • A. Neither changes
    • B. Only front changes.
    • C. Only rear changes.
    • D. Both change.

    Multiple Choice Section 7.4 Priority Queues

13. Suppose getFront is called on a priority queue that has exactly two entries with equal priority. How is the return value of getFront selected?
    • A. One is chosen at random.
    • B. The one which was inserted first.
    • C. The one which was inserted most recently.
    • D. This can never happen (violates the precondition)

14. An array of queues can be used to implement a priority queue, with each possible priority corresponding to its own element in the array. When is this implementation not feasible?
    • A. When the number of possible priorities is huge.
    • B. When the number of possible priorities is small.
    • C. When the queues are implemented using a linked list.
    • D. When the queues are implemented with circular arrays.