Deck 14: Introduction to Collections and Stacks

Question 1

A postfix expression can be easily evaluated using a queue.

Answer 1

False
Explanation: A postfix expression can be easily expressed using a stack.

Question 2

A queue is a ____________________ data structure.

A) LIFO
B) FIFO
C) link based
D) array based
E) none of the above

Answer 2

B
Explanation: A queue is a FIFO (first in, first out) data structure, meaning that the first element that is put into the queue is the first element to be removed from the queue.

Question 3

It is only possible to implement a queue using an array-based structure.

Answer 3

False
Explanation: A queue can be implemented using a linked structure or an array-based structure.

Question 4

In an ideal implementations of a stack and a queue, all operations are ______________________ .

A) O(1)
B) O(n)
C) O(n log n)
D) O(n²)
E) it depends on the operation

Question 5

Which of the following methods removes an element from a queue?

A) enqueue
B) dequeue
C) first
D) pop
E) push

Question 6

A queue is helpful in implementing a __________________ sort.

A) insertion
B) selection
C) quick
D) radix
E) merge

Question 7

A queue is a FIFO structure.

Question 8

In a radix sort, the radix refers to __________________________ .

A) a circular array
B) the number of elements being sorted
C) the range of values of the sort key
D) a stack
E) a queue

Question 9

A stack is a ___________________ data structure.

A) LIFO
B) FIFO
C) link based
D) array based
E) none of the above

Question 10

It is only possible to implement a stack using a linked structure.

Question 11

What exception is thrown if the pop method is called on an empty stack?

A) EmptyStackException
B) NoSuchElementException
C) ArrayOutOfBoundsException
D) EmptyCollectionException
E) none of the above

Question 12

A stack is the ideal collection to use when _______________________ .

A) implementing a radix sort
B) evaluating a postfix expression
C) evaluating an infix expression
D) implementing a quick sort
E) none of the above

Question 13

In a array-based implementation of a queue that stores the front of the queue at index 0 in the array, the dequeue operation is ___________________.

A) impossible to implement
B) has several special cases
C) O(n)
D) O(n²)
E) none of the above

Question 14

Which of the following is not a valid postfix expression?

A) 5 4 +
B) 6 5 4 + -
C) 4 + 5
D) 8 2 + 2 /
E) all of the above are valid postfix expressions

Question 15

Which of the following is not an operation on a stack?

A) push
B) pop
C) peek
D) dequeue
E) all of the above are operations on a stack

Question 16

Which of the following is not a queue operation?

A) enqueue
B) dequeue
C) first
D) isEmpty
E) all of the above are queue operations

Question 17

A stack is a LIFO structure.

Question 18

A queue is the ideal collection to use when ____________________ .

A) implementing a radix sort
B) evaluating a postfix expression
C) evaluating an infix expression
D) implementing a quick sort
E) none of the above

Question 19

What is the result of evaluating the following postfix expression: 4 8 + 2 *

A) 40
B) 24
C) 64
D) 20
E) none of the above are correct

Question 20

Which of the following methods inserts an element into a stack data structure?

A) enqueue
B) dequeue
C) push
D) pop
E) peek

Question 21

Write an enqueue method for a queue implemented as a linked structure. You may assume that the class has references to LinearNode objects called front and rear, which represent the front and rear of the queue respectively. You may also assume that the class has a variable called count, which represents the number of elements in the queue.

Question 22

What is the fundamental difference between radix sort and the other sorting techniques that have been studies.

Question 23

In a circular array-based implementation of a queue, the elements must all be shifted when the dequeue operation is called.

Question 24

What is wrong with implementing a queue via an array where index 0 represents the front of the queue?

Question 25

A radix sort is a comparison-based sorting algorithm.

Question 26

Suppose the following sequence of elements are inserted into a stack and a queue in the following order: 50, 26, 32, 18, 26, 51. What is the result of three pop operations of the stack and three dequeue operations of the queue?

Question 27

List the five basic operations on a queue.

Question 28

What is wrong with the java.util.Stack implementation of a stack?

Question 29

The peek operation on a stack returns a reference to the element at the bottom of the stack.

Question 30

It is possible to implement a stack and a queue in such a way that all operations take a constant amount of time.

Question 31

Write a push method for a stack implemented as a linked structure. You may assume that the implementation has the top element of the stack referenced by a LinearNode reference top and that an integer variable count keeps track of the number of elements in the stack.

Question 32

Write out the order of elements that are contained in a queue after the following operations are performed.
myQueue.enqueue(new Integer(8));
myQueue.enqueue(new Integer(6));
Integer num1 = myQueue.dequeue();
myQueue.enqueue(new Integer(3));
myQueue.enqueue(new Integer(4));
myQueue.enqueue(new Integer(15));
myQueue.enqueue(new Integer(12));
myQueue.enqueue(new Integer(9));
myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();
myQueue.enqueue(new Integer(19));

Question 33

In a linked implementation of a stack, a pushed element should be added to the end of the list.

Question 34

Explain how a queue can be implemented using an array, where the enqueue and the dequeue operations are both constant time operations (for simplicity, we'll assume we will never need to expand the capacity of the array).

Question 35

Suppose there were no count variable stored for the linked implementation of a queue. Would it still be possible to implement a constant time size operation? How about if there were no count variable stored for an array based implementation of a queue?

Question 36

List the five basic operations on a stack.

Question 37

Write out the order of elements that are contained in a stack after the following operations are performed.
myStack.push(new Integer(8));
myStack.push(new Integer(6));
Integer num1 = myStack.pop();
myStack.push(new Integer(3));
myStack.push(new Integer(4));
myStack.push(new Integer(15));
myStack.push(new Integer(12));
myStack.push(new Integer(9));
myStack.pop();
myStack.pop();
myStack.pop();
myStack.push(new Integer(19));

Question 38

Write an enqueue method for a queue implemented as a circular array. You may assume that you have access to a method called expandCapacity that will double the size of the array if necessary. The class has instance variables front and rear, which represent the indexes of the front and rear of the queue. It also has an integer variable called count that represents the number of elements in the queue, as well as an array of generic T types called queue that represents the queue.

Question 39

Write a push method for a stack implemented with an array. You may assume that the stack is referenced by an array named stack, and that there is an integer variable named count that keeps track of the number of elements in the stack. You may not assume that you have access to an expandCapacity method (meaning that your method should include code to expand the capacity of the array if it is full).

Question 40

In an array-based implementation of a stack, which end of the contents of the array represents the bottom of the stack and why?