Deck 21: Stacks and Queues

Question 1

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = 0;
A method that implements the String peek()operation can be written as

A) return s[top];
B) if (top == 0.
Throw new RuntimeException("Underflow".;
Else
Return s[top];
C) if (top == 0.
Throw new RuntimeException("Underflow".;
Else
Return s[top-1];
D) return s[top-1];

Answer 1

C

Question 2

In a list implementation of a queue,the end of the list from which elements are removed is called

A) the front of the queue
B) the rear of the queue
C) the top of the queue
D) the bottom of the queue

Answer 2

A

Question 3

The stack pull operation

A) increases the capacity of a stack that is about to fill up
B) extracts one element from the stack and returns it
C) brings two stacks together and combines their elements
D) does not exist: There is no such stack operation

Answer 3

D

Question 4

The stack class provided by the Java Collections Framework

A) can be used to hold values of any type
B) can be used to create stacks of int
C) cannot be used to instantiate a stack of int,or of any primitive type
D) is not efficient,so its use is not recommended

Question 5

In a list implementation of a stack,the end of the list at which elements are added and removed is called

A) the active end of the stack
B) the head of the stack
C) the top of the stack
D) the bottom of the stack

Question 6

Compilers of modern programming languages support method calls and returns with an internal

A) priority queue
B) hash set
C) stack
D) queue

Question 7

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = 0;
A method for adding an item x to the stack can be written as

A) s.add(top,x);
B) if (top == s.length.
Throw new RuntimeException("Overflow".;
Else
{
Top ++;
S[top] = x;
}
C) if (top < 0.throw new IndexOutBoundsException(.
S[top] = x;
Top ++;
D) if (top < s.length.
{
S[top] = x;
Top ++;
}
Else
Throw new RuntimeException("Overflow".;

Question 8

A queue is a container that allows elements to be stored and removed

A) in a last-in-first-out fashion
B) in a first-in-first-out fashion
C) in a first-in-last-out fashion
D) quickly and efficiently

Question 9

The stack empty operation

A) removes all elements from the stack
B) checks to see if there is at least one item on the stack
C) destroys the stack and creates a new empty one in its place
D) None of the above

Question 10

The JCF Stack class is used to instantiate a stack:
Stack< Integer > intStack = new Stack< Integer >();
The statements
Int k = 77;
IntStack.push(k*k);
Use the primitive type int instead of the wrapper type Integer.These statements

A) cause a compile time error
B) compile and execute correctly
C) cause a ClassCastException
D) None of the above

Question 11

The stack push operation

A) is normally implemented through a hash set
B) removes and returns an item from the stack
C) returns the item at the top of the stack,but does not remove it
D) adds a single item to the stack

Question 12

A stack is a container that allows elements to be stored and removed

A) in a last-in-first-out fashion
B) in a first-in-first-out fashion
C) last-in-last-out fashion
D) according to priority

Question 13

In a list implementation of a queue,the end of the list at which elements are added is called

A) the front of the queue
B) the rear of the queue
C) the head of the queue
D) the bottom of the queue

Question 14

A stream of cars going through a toll booth is an example of a

A) priority queue
B) hash set
C) stack
D) queue

Question 15

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = 0;
A method that implements the String pop()operation can be written as

A) if (top == 0)
Throw new RuntimeException("Underflow");
Top--;
String temp = s[top];
S[top] = null;
Return temp;
B) if (top == 0.
Throw new RuntimeException("Underflow".;
String temp = s[top];
Top--;
S[top] = null;
Return temp;
C) if (top == 0.
Throw new RuntimeException("Underflow".;
Return s[top-1];
Top --;
S[top] = null;
D) top--;
Return s[top];

Question 16

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = 0;
The boolean method to check for an empty stack can be written as:

A) return top;
B) if (top == 0.
Return true;
Else
Return false;
C) if (s == null.
Return true;
Else
Return false;
D) if
Return true;
Else
Return false;

Question 17

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = -1;//Note top == -1 indicates stack is empty
A method that implements a void push(String x)operation can be written as

A) if (top == s.length-1)
Throw new RuntimeException("Overflow");
Top ++;
S[top] = x;
B) if (top == s.length.
Throw new RuntimeException("Overflow".;
Top ++;
S[top] = x;
C) if (top == s.length-1.
Throw new RuntimeException("Overflow".;
S[top] = x;
Top ++;
D) if (top == s.length.
Throw new RuntimeException("Overflow".;
S[top] = x;
Top ++;

Question 18

The stack pop operation

A) removes all items currently on the stack
B) extracts one element from the stack and returns it
C) removes from the stack the number of elements specified by its integer parameter
D) does not exist: There is no such stack operation

Question 19

In an array-based implementation of a stack,an operation that needs to add a new element to the stack may not be able to complete because the array is full.In this case,the failed operation should

A) print an error message and return from the method
B) throw some appropriately defined exception
C) print an error message and exit
D) alert the user before continuing execution

Question 20

The stack peek operation

A) checks a stack to see if there are any elements in it
B) removes and returns an item from the stack
C) returns the item at the top of the stack,but does not remove it
D) adds a single item to the stack

Question 21

A stack based on a linked list is based on the following code
Class Node{
String element;
Node next;
Node(String el,Node n){
Element = el;
Next = n;
}
}
Node top = null;
The code for implementing the String pop()operation is

A) if (top != null)
{
Top = top.next;
String el = top.element;
Return el;
}
Else throw new RuntimeException("Empty Stack");
B) if (top != null.
{
String el = top.element;
Top = top.next;
Return el;
}
Else throw new RuntimeException("Empty Stack".;
C) if (top != null.
{
String el = top.element;
Top = null;
Return el;
}
Else throw new RuntimeException("Empty Stack".;
D) return top.element;
Top = top.next;

Question 22

A stack based on a linked list is based on the following code
Class Node{
String element;
Node next;
Node(String el,Node n){
Element = el;
Next = n;
}
}
Node top = null;
The code for implementing the String peek()operation is

A) String temp = top.element;
If (temp != null)return temp;
Else
Throw new RuntimeException("Empty Stack");
B) if (top != null.
Return top.element;
Else return top.next;
C) if (top != null.
Return top.element
Else
Throw new RuntimeException("Empty Stack".;
D) if (top != null.
Return top;

Question 23

A queue based on a linked list uses the following code
Class Node{
String element;
Node next;
Node (String el,Node n){
Element = el;
Next = n;
}
}
Node front,rear;
What is the right code for a constructor for such a linked list class?

A) element = el;next = n;
B) front = rear;
C) front = null;rear = null;
D) front = element;rear = front;

Question 24

In a queue implementation that uses an array of fixed size,

A) the array must be made so large that the queue will never run out of space
B) it is necessary to use the array as a circular buffer
C) the array must be created from an ArrayList object
D) the queue must implement the List interface

Question 25

A stack based on a linked list is based on the following code
Class Node{
String element;
Node next;
Node(String el,Node n){
Element = el;
Next = n;
}
}
Node top = null;
The code for implementing the operation void push(String x)can be written as

A) top = new Node(x,top);
B) if (top == full.
Throw new RuntimeException("Overflow".;
Else
Top = new Node(x,top.;
C) top.add(x.;
D) top = add(Node x.;

Question 26

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = -1;// Note top == -1 indicates stack is empty
A method that implements a String pop()operation can be written as

A) if (top == -1)
Throw new RuntimeException("Empty Stack");
Top --;
String temp = s[top];
S[top] = null;
Return temp;
B) if (top == -1.
Throw new RuntimeException("Empty Stack".;
S[top] = null;
Top--;
Return s[top ];
C) if (top == -1.
Throw new RuntimeException("Empty Stack".;
String temp = s[top];
S[top] = null;
Top--;
Return temp;
D) None of the above

Question 27

In an implementation of a stack based on a singly-linked list,it is most efficient to add a new item so that

A) the new item has the highest index of all items in the list
B) the new item has the lowest index of all items in the list
C) the new item is not duplicated by any other item already in the stack
D) the items in the stack stay sorted in ascending order

Question 28

The operation for removing an item from a queue is called

A) enqueue
B) dequeue
C) extract
D) disqueue

Question 29

Consider a class that uses the following variables to implement an array-based stack:
String [ ] s = new String[100];
Int top = -1;// Note top == -1 indicates stack is empty
A method that implements a String peek()operation can be written as

A) if (top == -1)
Throw new RuntimeException("Empty Stack");
Else
Return s[top -1];
B) if (top > -1.
Return s[top];
Else
Throw new RuntimeException("Empty Stack".;
C) top --;
If (top == -1.
Throw new RuntimeException("Empty Stack".;
Else
Return s[top];
D) if (top == 0.
Throw new RuntimeException("Empty Stack".;
Else
{
Top --;
Return s[top];
}

Question 30

A queue based on a linked list uses the following code
Class Node{
String element;
Node next;
Node (String el,Node n){
Element = el;
Next = n;
}
}
Node front = null,rear = null;
What is the right code for void add(String x)operation? Such an operation adds x to the queue

A) rear = new Node(x,null);
B) rear = new Node(x,null.;rear = rear.next;
C) if (rear != null.
{
Rear.next = new Node(x,null.;
Rear = rear.next;
}
Else
{
Rear = new Node(x,null.;
Front = rear;
}
D) if (rear != null.
{
Rear.next = new Node(x,null.;
Rear = rear.next;
}
Else
{
Rear.next = new Node(x,null.;
Front = rear;
}

Question 31

A queue invariant is a condition

A) obeyed by queues that need to remain constant
B) that is required to be true after the execution of each queue class method
C) that is more stringent than invariants for other types of collections
D) that is true regardless of the actual type used to instantiate a generic queue.

Question 32

The operation for adding an item to a queue is called

A) requeue
B) enqueue
C) dequeue
D) proqueue

Question 33

Which of the following operations is not a stack operation?

A) remove and return an item with a specified value
B) set the element at the bottom of the stack to a specified value
C) remove and return the item at a specified position
D) All of the above: that is,none of the above are stack operations

Question 34

A queue based on a linked list uses the following code
Class Node{
String element;
Node next;
Node (String el,Node n){
Element = el;
Next = n;
}
}
Node front = null,rear = null;
What is the right code for the boolean empty()method?

A) return front == null;
B) if (rear == front.return true;
Else
Return false;
C) if (front == null.
Throw new RuntimeException("Empty".;
Else
Return false;
Return true;
D) return front == rear;

Question 35

A queue based on a linked list uses the following code
Class Node{
String element;
Node next;
Node (String el,Node n){
Element = el;
Next = n;
}
}
Node front = null,rear = null;
What is the right code for String remove()operation? Such an operation removes and returns an element from the queue.

A) if (rear== null)
Throw new RuntimeException("Empty");
String temp = rear.element;
Rear = rear.next;
If (front == null)
Rear = null;
Return temp;
B) if (front == rear.
Throw new RuntimeException("Empty".;
String temp = front.element;
Front = front.next;
If (front == null.
Rear = null;
Return temp;
C) if (front == null.
Throw new RuntimeException("Empty".;
String temp = front.element;
Front = front.next;
If (front == null.
Front = rear;
Return temp;
D) if (front == null.
Throw new RuntimeException("Empty".;
String temp = front.element;
Front = front.next;
If (front == null.
Rear = null;
Return temp;

Question 36

A stack based on a linked list is based on the following code
Class Node{
String element;
Node next;
Node(String el,Node n){
Element = el;
Next = n;
}
}
Node top = null;
The code for testing whether the stack is empty is

A) return top == null;
B) return top = null;
C) if (top == null.
Return true;
Else throw new RunTimeException(.;
D) if (top == 0.
Return true;
Else
Return false;