Test Bank Introduction To Collections - Stacks Ch12

Chapter 12: Introduction to Collections - Stacks

Multiple Choice Questions:

1) A stack is a ___________________ data structure.

a) LIFO

b) FIFO

c) link based

d) array based

e) none of the above

2) 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

3) 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

4) 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

5) What exception is thrown if the pop method is called on an empty stack, implemented using the ArrayStack class?

a) EmptyStackException

b) NoSuchElementException

c) ArrayOutOfBoundsException

d) EmptyCollectionException

e) none of the above

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

a) enqueue

b) dequeue

c) push

d) pop

e) peek

7) A stack is the ideal collection to use when _______________________ .

a) implementing a radix sort

b) evaluating a postfix expression

c) modeling customers standing in line at the checkout of a grocery store

d) finding the largest number in an array

e) none of the above

8) A(n) ______ is an object that gathers and organizes other objects.

a) abstraction

b) collection

c) exception

d) algorithm

e) none of the above

9) In Java, type compatibility is enforced by _____________.

a) compile-time type checking

b) convention

c) an Enforcer object

d) an exception

e) Java does not enforce type compatibility

10) Java uses ________ to allow us to define a class and not specify the type of the objects that the class employs until the class is instantiated.

a) exceptions

b) widgets

c) inheritance

d) interfaces

e) generic types

11) Which of the following stack operations is not likely to cause an exception to be thrown?

a) adding an item to the stack when the stack is full

b) adding an item that has the same value as one that is already in the stack

c) removing an item when the stack is empty

d) all of a), b), and c)

e) All of these are likely to cause an exception to be thrown

12) A Stack interface is defined and has an isEmpty() abstract method. What should this method return?

a) an int representing the number of items in the stack

b) a double representing the average of the values of the items in the stack

c) a String representing the contents of the items in the stack.

d) a boolean value representing whether the stack is empty or not.

e) the item that is at the top of the stack

13) Which of the following situations could be implemented using a Stack?

a) cars waiting to pay and exit a parking garage

b) people who have appointments in the reception area of a doctor’s office

c) students passing through the serving line in a cafeteria

d) a person who wants to un-do several changes that were made to the document that she is editing.

e) none of the above

14) In an array implementation of a stack, we can include code that will automatically allocate more memory if every element of the array is occupied. Which stack operation should invoke this code?

a) push

b) pop

c) peek

d) poke

e) none of the above

15) The peek operation of a stack is

a) O(1)

b) O(n)

c) O()

d) O(n log n)

e) none of the above

True/False Questions:

1) A postfix expression can be easily evaluated using a stack.

2) A stack is a LIFO structure.

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

4) An abstract datatype is a data type that is not known to the programmer

5) Creating a data structure that holds Objects makes a lot of sense, since all objects inherit from the Object class.

6) The postfix expression 5 3 * 2 5 + - 4 * 2 / evaluates to 16

7) An exception should be thrown if an attempt is made to pop an item from an empty stack.

8) The peek operation can retrieve a value from anywhere in the stack.

9) An array-based implementation of a stack can be designed so that all stack operations are O(1).

10) The isEmpty() method determines if the store of extra memory for use by the stack is empty.

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

2) Suppose the following sequence of elements are pushed onto a stack named myStack in the following order: 50, 26, 32, 18, 26, 51. What is the output of the following code?

for (int count = 1; count <=3; count++)

System.out.println(myStack.pop() );

3) Write out the order of elements that are contained in a stack after the following operations are performed.

4) 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, nor should your code throw an exception if the stack is full. Your method should include code to expand the capacity of the array if it is full.

5) List the five basic operations on a stack. You may assume that there is an integer variable named

6) Write an isEmpty method for a stack implemented with an array. You may assume that there is an integer variable named count that keeps track of the number of elements in the stack.

7) A collection is an object. A collection is also an abstraction. Explain how these two sentences can both be true.

8) Java has existing collections that implements the stack data type. Why is it important to know how to implement our own stack data types?

9) Suppose NumberValue is class that uses a generic type:

10) What should happen if a user attempts to pop an element from an empty stack?

11) What should a stack data type do if a push operation cannot succeed because there is no more room in the data structure to hold another item?

12) What benefit is gained by placing the bottom of the stack at array index 0 when designing an array-based stack data type?

13) The pop operation should throw an exception if the stack is empty. What should the peek operation do if the stack is empty?

14) How should the constructor for an array-based stack data type be designed to support user choice for stack size?

15) How are Javadoc comments useful in documenting code?