DSAJ5 Test Bank Chapter 06

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.
Answer: true
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.
Answer: false
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.
Answer: true
4. A vector will grow in size as needed.
Answer: true
5. A vector is analogous to a resizable linked-chain.
Answer: false
6. A vector is manipulated with methods.
Answer: true
7. A vector’s entries are indexed beginning with 0.
Answer: true
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.
Answer: false
9. Using a resizable array to implement the stack ADT avoids the condition where a stack is too full
to accept another entry.
Answer: true
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).
This study source was downloaded by 100000831236167 from CourseHero.com on 03-06-2022 14:14:50 GMT -06:00
https://www.coursehero.com/file/54287116/DSAJ5-Test-Bank-Chapter-06docx/
Answer: false
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?
Answer: The objects in the stack remain allocated.
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.
Answer: You must move all of the entries in the array every single time you push or pop an entry
causing excessive time.
3. When would amortizing the cost of doubling an array size over all the additions to the stack work
not out to be negligible?
Answer: When the array must be resized many times.
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.
Answer: We can directly infer the index from the vector’s size.
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.
Answer:
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

a. a linked-chain
b. an array
c. a vector
d. all of the above **
2. The node that is easiest to access in a linked-chain is

a. the head node **
b. the tail node
c. access time is the same for all nodes
d. it cannot be determined
3. In a linked-chain implementation of a Stack ADT, the performance of pushing an entry onto the
stack is
a. O(1) **
b. O(2)
c. O(n)
d. 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
a. O(1) **
b. O(2)
c. O(n)
d. O(n2)
5. In a linked-chain implementation of a Stack ADT, the performance of popping an entry from the
stack is
a. O(1) **
b. O(2)
c. O(n)
d. O(n2)
6. In a linked-chain implementation of a Stack ADT, when a node is popped from the stack
a. the original first node will no longer be referenced
b. the original first node will be deallocated
c. the new first node will reference what was the second node in the chain
d. all of the above **
7. In an array-based chain implementation of a Stack ADT, the entry peek returns may be found at
a. the last occupied location in the array **
b. the last location in the array
c. the first location in the array
d. 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?
a. -1 **
b. 0
c. 1
d. 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?
a. O(n) **
b. O(1)
c. O(n log n)
d. 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?
a. O(1) **
b. O(n)
c. O(n log n)
d. O(n2)
11. What object behaves like a high-level array?

a. vector **
b. linked-chain
c. array-chain
d. all of the above
12. In the Java Class Library, the default constructor Vector creates an empty vector with an initial
capacity of
a. 10 **
b. 0
c. 100
d. user-defined
13. When a vector needs to increase its size

a. the capacity is doubled **
b. the capacity is increased by 10 empty entries
c. the capacity is increased by 1 as needed
d. the capacity increase is user-defined
14. Which method accesses the last entry of a vector?

a. lastElement **
b. last
c. endOfVector
d. 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?
a. add **
b. push
c. put
16. In a vector implementation of a Stack ADT, you retrieve the top entry without removing it using
which vector method?
a. lastElement **
b. peek
c. look
17. In a vector implementation of a Stack ADT, you remove an entry from the top of a stack using
which vector method?
a. remove **
b. pop
c. retrieve
18. In a vector implementation of a Stack ADT, you check for an empty stack using which vector
method?
a. isEmpty **
b. empty
c. stackEmpty
19. In a vector implementation of a Stack ADT, you clear all of the contents of a stack using which
vector method?
a. clear **
b. delete
c. deleteAll
20. Which statement is true about the VectorStack class methods?

a. they invoke the methods of the Vector class
b. they require about the same execution time as the ArrayStack methods
c. both a & b **
Powered by TCPDF (www.tcpdf.org)

DSAJ5 Test Bank Chapter 06

Uploaded by

Copyright:

Available Formats

DSAJ5 Test Bank Chapter 06

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DSAJ5 Test Bank Chapter 06

Uploaded by

Copyright:

Available Formats

Chapter 6 - Stack Implementations

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.

Short Answer (5)

Answer: The objects in the stack remain allocated.

Answer: When the array must be resized many times.

vector: the Vector method takes care of it

1. The Stack ADT may be implemented with

2. The node that is easiest to access in a linked-chain is

9. In an array-based chain implementation of a Stack ADT, what is the performance of the

11. What object behaves like a high-level array?

13. When a vector needs to increase its size

14. Which method accesses the last entry of a vector?

20. Which statement is true about the VectorStack class methods?

You might also like