Chapter 4 Questions
Multiple Choice
1. What is used to start accessing a linked chain of nodes?
a. The head pointer
b. item[0]
c. item[1]
d. The null pointer
2. What value should headPtr contain if there are no nodes for it to point to?
a. The boolean value TRUE
b. nullptr
c. The constant ZERO
d. The constant NULL
3. Given the following poorly written code sequence:
headPtr = new Node<std::string>();
headPtr = nullptr;
What is the result?
a. headPtr points to the new node
b. Access the new node by use of headPtr
c. The new node is inaccessible
d. The program crashes
4. In a link-based implementation, what node is the only one to which we have direct access?
a. The last
b. All are equally direct access
c. The one at nullPtr
d. The first
5. Which of the following methods needs a counter?
a. getFrequencyOf
b. toVector
c. add
d. remove
6. What type does the method contains return?
a. int
b. bool
c. string
d. ItemType
7. What must be done with a node that is removed from the bag?
Chapter 4 Questions
a. Set it to nullptr
b. Decrement itemCount
c. Use the delete command so system can use returned memory
d. return canRmoveItem
8. A destructor’s name is a(n) ? followed by the class name.
a. ^
b. $
c. @
d. ~
9. When copying an object involves only copying the values of its data members, the copy is called
a(n) ? .
a. shallow copy
b. deep copy
c. transfer copy
d. virtual copy
10. What object oriented feature can we use to have a single test program, with one set of method
calls in which the user can decide which bag implementation (array- or link-based) needs testing?
a. copy constructor
b. polymorphism
c. toVector
d. the case statement
11. Which of the following are a good reason for using an array-based implementation of a bag?
a. An array is not fixed size
b. You must traverse n entries to get to the nth item in the array
c. Requires less memory than a link-based implementation
d. Good choice for a large bag
12. Which of the following are a good reason for using a link-based implementation of a bag?
a. A link list is fixed size.
b. You can access nodes directly with equal access time
c. A link-based implementation is good choice for a small bag
d. Linked chains do not have a fixed size
13. Given the following method
from the class Node:
What does this method do?
a. setItem
b. getItem
c. setNext
d. setPrevious
template<class ItemType>
void Node<ItemType>::doSomething(const ItemType& anItem)
{
item = anItem;
}
Chapter 4 Questions
14. Given the following method from the class LinkedBag
What does this method do?
template<class ItemType>
bool LinkedBag<ItemType>::doSomething(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
}
a. setItem
b. contains
c. isEmpty
d. destructor
Chapter 4 Questions
True or False
1. A node can be dynamically allocated.
2. Before you can assign headPtr a value, you must first create a new Node object.
3. Generally speaking, a link-based implementation does not impose a fixed maximum size on the
data structure.
4. Like an array-based implementation, a link-based implementation’s insertion and removal
operations will need to move data items.
5. For a link-based bag, the most convenient place to make an insertion is at the beginning of the
chain.
6. Even though you have allocated memory by using new, there is no need to deallocate it with the
delete command.
7. The method clear cannot simply set ItemCount to zero.
8. A class can have multiple destructors.
9. According to the text, you must write a destructor if your class allocates memory dynamically.
10. Classes that use dynamically allocated memory can depend on the compiler-generated destructor.
11. The copy constructor for our bag class requires traversing the original linked chain and
duplicating each node visited.
12. A recursive version of toVector is complicated and requires invocation of the copy
constructor.
13. Access time is a constant for an array-based implementation.
14. A link-based implementation requires less memory than an array-based implementation.
Chapter 4 Questions
15. The following method is recursive.
template<class ItemType>
void LinkedBag<ItemType>::fillVector(std::vector<ItemType>& bagContents,
Node<ItemType>* curPtr) const
{
if (curPtr != nullptr)
{
bagContents.push_back(curPtr– >getItem());
fillVector(bagContents, curPtr– >getNext());
} // end if
} // end fillVector
Chapter 4 Questions
Short Answer
1. What are the contents of a node?
2. Name two of the private members of the class LinkedBag
3. What steps must be done to implement the toVector method in a link-based implementation of
the ADT Bag?
4. What private method does the method remove invoke?
5. When is a destructor implicitly invoked?
6. Give three situations that will invoke the copy constructor.
7. What are two possible problems with using an array-based bag implementation
8. Given the following method, what does it do?
template<class ItemType>
int LinkedBag<ItemType>::doSomething(const ItemType& anEntry) const
{
int x = 0;
int counter = 0;
Node<ItemType>* curPtr = headPtr;
while ((curPtr != nullptr) && (counter < itemCount))
{
if (anEntry == curPtr– >getItem())
{
x++;
}
counter ++;
curPtr = curPtr– >getNext();
}
return x;
}