- Stack Implementations Chapter 6 Test Bank Answers

Chapter 6 - Stack Implementations

True/False (10)

1. In a linked-chain implementation of the Stack ADT, the first node references the stack’s top entry.
2. In an array-based implementation of the Stack ADT, it is more efficient to have the first array location reference the top of the stack.
3. In an array-based implementation of the Stack ADT, the cost of doubling the array size is amortized over all additions to the stack.
4. A vector will grow in size as needed.
5. A vector is analogous to a resizable linked-chain.
6. A vector is manipulated with methods.
7. A vector’s entries are indexed beginning with 0.
8. In a vector-based implementation of the Stack ADT, the most efficient place to maintain the top entry of a stack is in the vector’s first element.
9. Using a resizable array to implement the stack ADT avoids the condition where a stack is too full to accept another entry.
10. In an array-based implementation of the Stack ADT, spreading the cost of the push operation when the stack is full yields a performance of O(n).

Short Answer (5)

1. Why is it a bad programming practice for the Stack ADT clear method to simply set the topIndex to -1 in an array-based implementation?
2. In an array based implementation of a Stack ADT, explain why it is a bad idea to use the first location of the array to reference the top of a stack.
3. When would amortizing the cost of doubling an array size over all the additions to the stack work not out to be negligible?
4. In a vector based implementation of a Stack ADT, explain why it is not necessary to keep track of the index to the top entry of the stack.
5. In each of the array-based, link-chain, and vector implementations of a Stack ADT, describe how ensuring there is enough room to add an entry to a stack is handled.

array-based: the programmer must allocate a new array larger than the original, copy the
contents of the original to the new array and return a reference to the new array

link-chain: the programmer must allocate a new node for each new entry

vector: the Vector method takes care of it

Multiple Choice (20) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. The Stack ADT may be implemented with
   1. a linked-chain
   2. an array
   3. a vector
   4. all of the above
2. The node that is easiest to access in a linked-chain is
   1. the head node
   2. the tail node
   3. access time is the same for all nodes
   4. it cannot be determined
3. In a linked-chain implementation of a Stack ADT, the performance of pushing an entry onto the stack is
   1. O(1)
   2. O(2)
   3. O(n)
   4. O(n2)
4. In a linked-chain implementation of a Stack ADT, the performance of looking at the first entry on the stack without removing it is
   1. O(1)
   2. O(2)
   3. O(n)
   4. O(n2)
5. In a linked-chain implementation of a Stack ADT, the performance of popping an entry from the stack is
   1. O(1)
   2. O(2)
   3. O(n)
   4. O(n2)
6. In a linked-chain implementation of a Stack ADT, when a node is popped from the stack
   1. the original first node will no longer be referenced
   2. the original first node will be deallocated
   3. the new first node will reference what was the second node in the chain
   4. all of the above
7. In an array-based chain implementation of a Stack ADT, the entry peek returns may be found at
   1. the last occupied location in the array
   2. the last location in the array
   3. the first location in the array
   4. none of the above
8. In an array-based chain implementation of a Stack ADT, what value at the top of the stack indicated that it is empty?
   1. -1
   2. 0
   3. 1
   4. null
9. In an array-based chain implementation of a Stack ADT, what is the performance of the ensureCapacity method when the array is full?
   1. O(n)
   2. O(1)
   3. O(n log n)
   4. O(n2)
10. In an array-based chain implementation of a Stack ADT, what is the performance of the ensureCapacity method when the array is not full?
    1. O(1)
    2. O(n)
    3. O(n log n)
    4. O(n2)
11. What object behaves like a high-level array?
    1. vector
    2. linked-chain
    3. array-chain
    4. all of the above
12. In the Java Class Library, the default constructor Vector creates an empty vector with an initial capacity of
    1. 10
    2. 0
    3. 100
    4. user-defined
13. When a vector needs to increase its size
    1. the capacity is doubled
    2. the capacity is increased by 10 empty entries
    3. the capacity is increased by 1 as needed
    4. the capacity increase is user-defined
14. Which method accesses the last entry of a vector?
    1. lastElement
    2. last
    3. endOfVector
    4. you can’t access the last entry directly
15. In a vector implementation of a Stack ADT, you add an entry to the top of a stack using which vector method?
    1. add
    2. push
    3. put
    4. none of the above
16. In a vector implementation of a Stack ADT, you retrieve the top entry without removing it using which vector method?
    1. lastElement
    2. peek
    3. look
    4. none of the above
17. In a vector implementation of a Stack ADT, you remove an entry from the top of a stack using which vector method?
    1. remove
    2. pop
    3. retrieve
    4. none of the above
18. In a vector implementation of a Stack ADT, you check for an empty stack using which vector method?
    1. isEmpty
    2. empty
    3. stackEmpty
    4. none of the above
19. In a vector implementation of a Stack ADT, you clear all of the contents of a stack using which vector method?
    1. clear
    2. delete
    3. deleteAll
    4. none of the above
20. Which statement is true about the VectorStack class methods?
    1. they invoke the methods of the Vector class
    2. they require about the same execution time as the ArrayStack methods
    3. both a & b
    4. none of the above