Sample Data Structures Questions

Sample Data Structures Questions
Chapter 8
Queues

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000

The Purpose of These Questions

These are typical exam questions from Chapter 8 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) There are 5 short answer questions and 13 multiple choice questions in this file.

Short Answers

Short Answers
Sections 8.1 - 8.2
Queues and Their
Applications

Complete the body of this function. Use a queue of characters to store the input line as it is being read.


    size_t counter( )
    // Precondition: There is a line of input waiting to be read from cin.
    // Postcondition: A line of input has been read from cin, up to but not
    // including the newline character. The return value of the function
    // 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.
    {
        size_t answer = 0;
        queue q;

Short Answers
Section 8.3
Implementations of
the Queue ADT

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


   queue<int> s;
   s.insert(1);
   s.insert(2);
   s.insert(3);
   cout << s.get_front( );

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


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

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


   queue<int> s;
   s.insert(1);
   s.insert(2);
   s.insert(3);
   cout << s.get_front( );

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


               _______      
     front_ptr|       |  
              |_______|     
               _______      
      rear_ptr|       |  
              |_______|

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 8.4
Priority Queues
Suppose that you want to implement the priority_queue so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:
```
    template 
    class priority_queue
    {
        typedef Item value_type;
        void push(const Item&x  entry);
        value_type top( );
        ...
    private:
        node *head_ptr;
    };
```
(A) Write ONE sentence to describe how the insert member function will work (with constant time). (B) Then implement the top function (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). You may also assume that these two toolkit functions have been modified to work with the priority_queue's node:
void list_head_remove(Node*& head_ptr); // Removes head node of a list void list_remove(Node* precursor); // Removes node after *precursor

Multiple Choice

Multiple Choice
Sections 8.1-8.2
Queues and Their
Applications

One difference between a queue and a stack is:
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?
Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <
= P <
= 1).
Multiple Choice
Section 8.3
Implementations of
the Queue ADT
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 CAPACITY is 42. Where does the push member function place the new entry in the array?
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).
In the linked list implementation of the queue class, where does the push member function place the new entry on the linked list?
In the circular array version of the queue class (with a fixed-sized array), which operations require linear time for their worst-case behavior?
In the linked-list version of the queue class, which operations require linear time for their worst-case behavior?
If data is a circular array of CAPACITY elements, and last is an index into that array, what is the formula for the index after last?
I have implemented the queue with a circular array, keeping track of first, last, and count (the number of items in the array). Suppose first is zero, and last is CAPACITY-1. What can you tell me about count?
I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?
I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?
Multiple Choice
Section 8.4
Priority Queues
Suppose top is called on a priority queue that has exactly two entries with equal priority. How is the return value of top selected?

Data Structures and Other Objects Using C++

Michael Main (main@colorado.edu)
and
Walter Savitch (wsavitch@ucsd.edu)