Deck 4: Stacks and Queues

Question 1

The EmptyQueueException is associated with the action of attempting to remove an item from an empty queue.

Answer 1

False

Question 2

In computer science, queues are used in operating systems to keep track of tasks waiting for a scarce resource and to ensure that the tasks are carried out in the order that they were generated.

Answer 2

True

Question 3

A double-linked list requires the same amount of storage as that of a single-linked l ist.

Answer 3

False

Question 4

Although reallocating an array is an O(n) operation, it is amortized over n items, so the cost per item is O(n²).

Question 5

You can implement a queue as a single-linked list.

Question 6

A(n) _____________________ is a data structure in which objects are inserted at one end and removed from the other.

Question 7

Removal from the front of a queue is a(n) ____________________ operation.

Question 8

If a LinkedList is used, insertion at the rear of a queue is a(n) ____________________ operation.

Question 9

If the queue is empty, element method throws a(n) ____________________ exception.

Question 10

Because interface Queue extends interface ____, a full implementation of the Queue interface must implement all required methods of that interface.

Question 11

The ____________________ method creates a Random object when it is first called. It then uses that object's nextDouble method to return a random number in the range 0 to 1.

Question 12

In a(n) ____________________ array, the elements wrap around so that the first element actually follows the last.

Question 13

If an array is used to implement a Queue, insertion at the rear of the array can be done in ____________________ time.

Question 14

Through ____________________, the designers of a new system can estimate the expected performance of the system before they actually build it.

Question 15

____________________ is a technique used to study the performance of a physical system by using a physical, mathematical, or computer model of the system.

Question 16

When a queue is implemented using a circular array, removal from the rear is ____.

A) O(n)
B) O(1)
C) O(n²)
D) O(log n)

Question 17

When a queue is implemented using a circular array, insertion at the front is ____.

A) O(1)
B) O(log²n)
C) O(log n)
D) O(n)

Question 18

Complete the following code:
/** Returns the next element in the queue.
Pre: index references the next element to access.
Post: index and count are incremented.
@return The element with subscript index
*/
Public E next() {
If (!hasNext()) {
____
}
E returnValue = theData[index];
Index = (index + 1) % capacity;
Count++;
Return returnValue;
}

A) throw new NoSuchElementException();
B) throw new StackException();
C) throw new EmptyStackException();
D) throw new EmptyListException();

Question 19

Complete the following code:
/** Returns the item at the front of the queue without removing it.
@return The item at the front if successful; null if not
*/
Public E ____() {
If (size() == 0)
Return null;
Else
Return theQueue.getFirst();
}

A) poll
B) element
C) remove
D) peek

Question 20

Complete the following code.
/** Insert an item at the rear of the queue.
Post: item is added to the rear of the queue.
@param item The element to add
@return true (always successful)
*/
Public boolean ____(E item) {
// Check for empty queue.
If (front == null) {
Rear = new Node<E>(item);
Front = rear;
} else {
// Allocate a new node at end, store item in it, and
// link it to old end of queue.
Rear.next = new Node<E>(item);
Rear = rear.next;
}
Size++;
Return true;
}

A) offer
B) remove
C) peek
D) getSize

Question 21

If a non-circular array is used to implement a queue, insertion at the front is a(n) ____ operation instead of O(1).

Question 22

Complete the following code:
/** Remove the item accessed by the Iter object - not implemented. */
Public void remove() {
Throw new ____();
}

A) EmptyListException
B) EmptyQueueException
C) UnsupportedOperationException
D) LinkedListException

Question 23

____ traversal implies that you will follow one path to the end before embarking on a new path.

A) Queue
B) Depth-first
C) Breadth-first
D) Binary

Question 24

____ traversal implies that the nodes visited spread out from the starting point.

A) Depth-first
B) Binary
C) Queue
D) Breadth-first

Question 25

Which of the following contains a syntax error?

A) public int getSize() {
return size;
}
B) public boolean isEmpty() {
return theData.size() == 0;
}
C) public boolean isEmpty() {
return size == 1;
}
D) public boolean isEmpty {
return size == 0;
}

Question 26

In Java 6.0, the Deque ________________ represents a __________________ queue.

Question 27

You can use a Deque object to implement a stack.

Question 28

Two Java Collection classes that implement the Deque are ________________ and ________________.