Sample Data Structures Questions
Chapter 7
Queues

Data Structures and Other Objects Using Java Third Edition
by Michael Main

The Purpose of These Questions

Short Answers

Short Answers Sections 7.1 - 7.2 Queues and Their Applications

1. I am going to execute this code with THREE adds and ONE remove:

   
      ArrayQueue<Integer> q = new ArrayQueue<Integer>( );
      q.add(1);
      q.add(2);
      q.add(3);
      System.out.println(q.remove( ));
   

   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]
   

2. I am going to execute this code with THREE adds and ONE removet:

   
      ArrayQueue<Integer. q = new ArrayQueue<Integer>( );
      q.add(1);
      q.add(2);
      q.add(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|       |  
                 |_______|     
   

3. 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.
   

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.