CPS 181-Chapter 20 Review

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 correct code for a constructor for such a linked list class?

front = null; rear = null;

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?

return front == null;

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 correct code for void add(String x) operation? Such an operation adds x to the queue.

if (rear != null)

{

rear.next = new Node(x, null);

rear = rear.next;

}

else

{

rear = new Node(x, null);

front = rear;

}

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.

if (front == null)

throw new RuntimeException("Empty");

String temp = front.element;

front = front.next;

if (front == null)

rear = null;

return temp;

A queue invariant is a condition ________.

that is required to be true after the execution of each queue class method

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

in a first-in-first-out fashion

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

return top == null;

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

if (top != null)

{

String el = top.element;

top = top.next;

return el;

}

else throw new RuntimeException("Empty Stack");

return top.element;

top = top.next;

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

if (top != null)

return top.element

else

throw new RuntimeException("Empty Stack");

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

top = new Node(x, top);

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

in a last-in-first-out fashion

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

queue

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

Stack

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:

if (top == 0){

return true;

}

else {

return false;

}

return top;

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

Correct if (top < s.length)

{

s[top] = x;

top++;

}

else

throw new RuntimeException("Overflow");

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

if (top == 0){

throw new RuntimeException("Underflow");}

else {

return s[top-1];

}

return s[top];

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

if (top == 0)

throw new RuntimeException("Underflow");

top--;

String temp = s[top];

s[top] = null;

return temp;

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

Correct if (top == s.length-1)

throw new RuntimeException("Overflow");

top++;

s[top] = x;

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

if (top == -1)

throw new RuntimeException("Empty Stack");

String temp = s[top];

s[top] = null;

top--;

return temp;

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

if (top > -1)

return s[top];

else

throw new RuntimeException("Empty Stack");

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

The rear of the queue

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

The front of the queue

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

The top of the stack

In a queue implementation that uses an array of fixed size ________.

It is necessary to use the array as a circular buffer

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

Throw some appropriately defined exception

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

The new item has the lowest index of all items in the list

The JCF Stack class is used to instantiate a stack:

Stack intStack = new Stack();

The statements

int k = 77;

intStack.push(k*k);

use the primitive type int instead of the wrapper type Integer. These statements ________.

compile and execute correctly

The operation for adding an item to a queue is called ________.

Enqueue

The operation for removing an item from a queue is called ________

Dequeue

The stack empty operation ________.

Checks to see if there is at least one item in the stack

The stack peek operation ________.

returns the item at the top of the stack, but does not remove it

The stack pop operation ________.

extracts one element from the stack and returns it

The stack pull operation ________.

Does not exist: There is no such stack operation

The stack push operation ________.

Adds a single item to the stack

The Stack class provided by the Java Collections Framework ________.

Cannot be used to instantiate a stack of int. or of any primative type

Which of the following operations is not a stack operation?

set the element at the bottom of the stack to a specified value

remove and return the item at a specified position

remove and return an item with a specified value

(Basically, all of the above)

T/F A Binary tree is a tree in which each node can have at most two children

True

T/F A Binary tree is a tree that has at most one parent

True

T/F The Depth of a node is the number of edges from the node to the root

True

T/F The Height of a node is the number of edges from the node to the leaf on the longest path

True