Chapter.13 Full Test Bank Linked Structures - Stacks

Chapter 13: Linked Structures - Stacks

Multiple Choice Questions:

1) In an ideal implementation of a stack, all operations are ______________________ .

a) O(1)

b) O(n)

c) O(n log n)

d) O(n²)

e) it depends on the operation

2) A(n) _____________________ is a data structure that uses object reference variables to create links between objects.

a) link structure

b) exception structure

c) interface

d) stack

e) array-based data structure for a stack

3) A(n) ____________________ is another way to refer to an object reference variable.

a) referer

b) pointer

c) stack collection

d) primitive variable

e) instantiated object

4) A self-referential object is an object that

a) is its own parent class

b) is its own child class

c) has a pointer to itself

d) has a pointer to another object of the same type

e) none of these is correct

5) A linked list can hold ______ nodes

a) 10

b) 100

c) 1000

d) a number specified when the linked list is instantiated.

e) any number of

6) The pointer to the first element in a linked list

a) can be used to traverse the list

b) can be modified in any way necessary

c) should only be modified by the code that adds nodes to the list and deletes nodes from the list

d) is optional

e) is inefficient

7) Creating a separate node class that holds a reference to another node and a reference to an object that is being stored in a list is a good design because it

a) makes the code more complicated

b) hides the implementation details of a collection

c) reduces code reuse

d) all of the above

e) neither a, b nor c

8) Java provides two Collections classes that can be used to implement stacks. They are ______ and _____.

a) the Stack class, the LinkedList class

b) one-dimensional arrays, multidimensional arrays

c) Exceptions, Errors

d) data structures, list structures

e) none of the above

9) An activation record represents

a) which students are currently logged in to a campus computer

b) which students are enrolled and actively pursuing a degree

c) a method that was called and has not yet completed its execution

d) a method that terminates due to an exception

e) both a) and b)

10) Recursion occurs when

a) a program never ends

b) a program terminates abnormally

c) a program ends normally

d) a method calls itself

e) none of the above

11) Which of the stack operations must be supported in a linked list implementation?

a) push and pop

b) push and peek

c) pop and peek

d) push, pop, and isEmpty

e) all of them

12) The constructor for a stack implemented using a linked list creates space for how many elements?

a) 0

b) 10

c) 100

d) 1000

e) whatever number the programmer specified when the linked list was instantiated.

13) The push operation of a stack implemented using a linked list is O(1) when

a) the stack is empty

b) the stack is full

c) the top of the stack is at the front of the linked list

d) the top of the stack is at the end of the linked list

e) none of the above

14) Which of the following is not part of the pop operation for a stack implemented using a linked list?

a) determine if the stack is full

b) determine if the stack is empty

c) declare a temporary reference variable and set it to point to the element at the top of the stack

d) adjust the top reference variable to point to the node pointed to by the next field of the node at the top of the stack

e) all of these are part of the pop operation for a stack implemented using a linked list

15) Traversing a linked list is

a) the process of deleting the list

b) the process of visiting every node for some purpose

c) the process of removing every node, one at a time

d) the process of creating a new linked list with twice the capacity

e) none of the above

True/False Questions:

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

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

3) When an object contains an instance field that is a reference to another object of the same type, we say that the object is self-identifying

4) A linked list is a linear ordering of objects in which an object has a reference to the next object in the list

5) An object can only contain one field that is a reference to another object of the same type.

6) When working with a linked list, the first element of the list must be treated in a different way than the other elements.

7) In a doubly linked list, each element has a reference to the element that immediately precedes it in the list and the element that immediately follows it in the list.

8) In the linked list implementation of a stack, capacity represents the number of elements for which space is allocated when the list is instantiated.

9) Using the rear of the linked list as the top of the stack is the most efficient way to manage the stack.

10) When working with a linked list implementation of a stack, the push operation should throw an exception if the stack is empty.

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

2) What is wrong with using the LinkedList class, which implements the Deque interface, to implement a stack?

3) 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<T> reference top and that an integer variable count keeps track of the number of elements in the stack.

public void push(T element) {

LinearNode<T> newNode = new LinearNode<T>(element);

newNode.setNext(top);

top = newNode;

count++;

}

4) When working with a linked list, how do you determine the last element in the list?

5) Is there a limit to the number of self-references that an object may have? Explain.

6) A linked list is described as a dynamic structure. What does this mean?

7) Consider the following sequence of steps to add a node to the front of a linked list:

- Set the reference field to refer to the first node in the current list.

- Set the reference to the front of the list to refer to the new node.

Is the order of these steps important? Explain your answer.

8) When working with a linked list implementation of a stack, what task must be performed by a pop operation that is not performed by a peek operation?

9) A linked list can be designed so that the nodes consist of just two reference variables. One refers to the element, while the other node is a self-reference for linked list purposes. What is the benefit of this design for a linked list?

10) A sentinel, or dummy, node can be used at the front of a linked list. What purpose does this serve?

11) A linked list implementation for a stack can be written using the LinkedList class, which implements the Deque interface. The Deque interface supports methods that are not part of a stack How can a programmer use the LinkedList class to implement a stack?

12) What is the first task that a pop operation should perform?

13) Write a peek 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<T> reference top.

public T peek() throws EmptyCollectionException

{

if (isEmpty() )

throw new EmptyCollectionException("stack");

T result = top.getElement();

return result;

}

14) Explain how activation records and the program stack are used to manage the invocation of and return from methods.

When the program begins executing, the activation record for the main method is put on the program stack. Whenever a method is called, its activation record is put on the stack and it begins to execute. A method’s activation record is removed from the program stack when the method terminates, at which time control is passed to the method that is now at the top of the program stack.

15) Someone tells you that a particular program uses recursion. What does this mean?