Chapter 9 Questions
Multiple Choice Questions
1. A pointer variable contains the ______ of a memory cell.
a. content
b. address
c. data type
d. ADT
2. The members of a node structure can be accessed with the ______ operator.
a. []
b. &
c. ->
d. at
3. A pointer variable whose sole purpose is to locate the first node in a linked list is called ______.
a. the list’s top
b. the node’s link
c. the list’s link
d. the list’s head
4. A(n) ______ operation sequentially visits each node in a linked list.
a. access
b. delete
c. get
d. traverse
5. To remove a node N from a linear linked list, you will need to ______.
a. set the pointer next in the node that precedes N to point to the node that follows N
b. set the pointer next in the node that precedes N to point to N
c. set the pointer next in the node that follows N to point to the node that precedes N
d. set the pointer next in N to point to the node that follows N
6. Which of the following statements deletes the node to which cur points?
a. prev->next = cur;
b. cur->next = prev;
c. cur->next = cur->next;
d. prev->next = cur->next;
7. Which of the following statements deletes the first node of a linear linked list that has 10 nodes?
a. head->next = cur->next;
b. prev->next = cur->next;
c. head = head–>next;
d. head = NULL;
8. Which of the following statements inserts a new node, pointed to by newPtr, at the end of a linear linked list?
a. newPtr->next = cur;
prev->next = newPtr;
Chapter 9 Questions
b. newPtr->next = head;
head = newPtr;
c. newPtr->next = NULL;
d. prev->next = cur;
newPtr->next = cur;
9. A ______ allows the deletion of a node from a linked list without the need to traverse the list to establish a
trailing reference.
a. head pointer
b. dummy head node
c. tail pointer
d. precede pointer
10. The author suggests that when you first look at implementing an ADT List, that “list” is simply a fancy name
for a. an array
b. a bag
c. a linked list
d. a stack
11. What operation does the ADT List have that an array does not?
a. identify their items by number
b. getLength()
c. insertItem()
d. isEmpty()
12. When designing an array based implementation of an ADT List, which of the following are not specified as
private?
a. items
b. itemCount
c. clear()
d. maxItems
13. What is the return type of the list operator remove(int position)?
a. void
b. int
c. itemType
d. bool
14. Which of the following operators uses two parameters?
a. insert
b. getLength
c. remove
d. clear
15. Given the following diagram.
Chapter 9 Questions
What list operation does this depict?
a. deleting an item in the list
b. inserting an item in the list
c. expanding the array to make it larger
d. counting the number of items in the list
16. To thoroughly test the insert method in an array-based implementation of ADT List, what other method do
we need?
a. clear
b. remove
c. getEntry
d. the constructor
17. Given the following diagram.
What list operation does this depict?
a. deleting an item in the list
b. inserting an item in the list
c. expanding the array to make it larger
d. counting the number of items in the list
18. In the author’s array based implementation of the ADT List, to what one variable does the clear method
assign a value?
a. items[0]
b. items[maxItems]
c. position
d. itemCount
19. In the list based implementation of the ADT List, which of the following is not a private variable in the classe?
a. headPtr
b. isEmpty
c. itemCount
d. getNodeAt
20. Given the following diagram.
Chapter 9 Questions
What List action does this depict?
a. insert a new node
b. get the value stored at a node
c. remove a node from the chain
d. get the value stored at a node
21. In the link based implementation of the ADT List, what method does the destructor call?
a. remove
b. insert
c. isEmpty
d. clear
22. Given the following pseudocode logic:
if ( the insertion position is 1 )
Add the new node to the beginning of the chain
else
Ignore the first node and add the new node to the rest of the chain
What does this describe?
a. recursive addition of a node to the list
b. iterative addition of a node to the list
c. addition of a node to the beginning of the list
d. adding a node to the end of the list
23. In an array based implementation of the ADT List, what is a characteristic of the time required to access any
particular element in the list?
a. you have no way of knowing how long it will take
b. the time required is a constant
c. the time required is a function of the size of the list
d. It is of order O(n2)
24. When calling the insert or remove methods, what is an advantage for the link-based implementation of the
ADT List?
a. searching for that position is quicker
b. takes less memory
c. no need to shift data
d. easier to understand
25. When calling the insert or remove methods, what is an disadvantage for the link-based implementation of
the ADT List?
Chapter 9 Questions
a. searching for that position is slower
b. takes more memory
c. must shift data
d. harder to understand
26. Adding or removing an entry anywhere within a link based list requires a change of at least how many pointers?
a. one
b. two
c. three
d. four
27. A link based getEntry method requires how many steps to access the nth item in the list?
a. n – 1
b. n
c. n + 1
d. n2
28. In either the link based or array based implementation of the ADT List, what is the single parameter for both the
remove and getEntry methods?
a. itemCount
b. maxItems
c. position
d. ItemType
29. What is the last step in the insertion process for a linked implementation of the ADT List?
a. Connect the new node to the linked chain by changing pointers
b. Create a new node and store the new data in it
c. Determine the point of insertion
d. The order of these steps really doesn’t matter
30. What is the first step in the deletion process for a linked implementation of the ADT List?
a. Return the node to the system
b. Disconnect the node from the linked chain by changing pointers
c. Locate the node you want to delete
d. The order of these steps really doesn’t matter
Chapter 9 Questions
True/False Questions
1. A pointer whose value is NULL does not point to anything.
2. A newly declared pointer variable has a default value of NULL.
3. In C++, the programmer must explicitly deallocate memory.
4. If the value of the head pointer is NULL, the linked list is empty.
5. When you design an abstract data type, you concentrate on what its operations do and how you will implement
them.
6. When designing an array implementation of an ADT List class, identifiers such as DEFAULT_CAPACITY,
items, itemCount and maxItems are specified as private.
7. In an array based implementation of the ADT List, the clear method must walk through the array and set each
value to null.
8. A link based implementation of the ADT List does not shift items during insertion and deletion operations.
9. A link based implementation of the ADT List imposes a maximum length on the list.
10. Both the array based and the link based implementations of method getEntry as developed by the author
should throw an exception if the parameter position is out of bounds.
Chapter 9 Questions
Short Answer Questions
1. What is the difference between static and dynamic allocation?
2. What is a memory leak?
3. Write the code segment that inserts into a linear linked list the node to which newPtr points between the two
nodes pointed to by the variables prevPtr and curPtr.
4. Write the code segment that inserts a new node to which newPtr points at the beginning of a linear linked list.
5. Why is an array-based implementation of a list a natural choice?
6. In the array based implementation of list,why do getEntry and setEntry throw an exception?
7. What strategy is used by the author to test core group of methods for a new implementation of an ADT List
class?
8. Why must the link based implementation of the ADT List not depend on a compiler generated default
constructor?
9. What high level steps are required in the link based implementation of ADT List to insert a new item?
10. What high level steps are required in the link based implementation of ADT List to delete an existing item
from the list?
11. Why cannot the link based implementation of the ADT List use a compiler generated copy constructor?
12. You have chosen an array based implementation for an ADT List with size 100. You discover that occasionally
this size is too small. What options do you have?
13. For a link based implementations of the ADT List which two methods are treated as special cases?
Chapter 9 Questions
14. For a link based implementations of the ADT List which two methods require traversal of the underlying chain?
15. Why must you use the use this sequence of statements when removing a node from a linked implementation of
an ADT List?
curPtr->setNext( nullptr );
delete curPtr;
curPtr = nullptr ;