Chapter 12 Questions
Multiple Choice
1. Which of the following operations was NOT included in the ADT sorted list operations?
a. print the sorted list
b. insert an entry into a sorted list
c. remove the entry at a given position from a sorted list
d. remove a given entry from a sorted list
2. Which of the following operations from the ADT sorted list behave as they do in the ADT list?
a. getPosition(anEntry)
b. getLength()
c. removeSorted(anEntry)
d. insertSorted(newEntry)
3. Given the following sequence of names added to an ADT sorted list:
nameListPtr–>insertSorted(“Tammie”);
nameListPtr–>insertSorted(“Brenda”);
nameListPtr–>insertSorted(“Sarah”);
nameListPtr–>insertSorted(“Tom”);
nameListPtr–>insertSorted(“Carlos”);
What would be returned by the call
nameListPtr–> getPosition(“Tammie”)
a. 1
b. 3
c. 4
d. 5
4. In the class LinkedSortedList, which of the following items are private?
a. the constructor
b. isEmpty()
c. getEntry(position)
d. getNodeAt(position)
5. Given a sorted list with entries in ascending order, where do you insert a new entry?
a. just before the first entry that is not smaller than the new entry
b. just after the first entry that is not smaller than the new entry
c. just before the first entry that is not larger than the new entry
d. at the end of the list
Chapter 12 Questions
6. Given the following figure to the right:
According to the text, what is the relationship between List A
and List B?
a. List A is composed of an instance of List B
b. List B is composed of an instance of List A
c. List A is concatenated to list B
d. List B is a subset of list A
7. When an ADT sorted list is implemented using an instance of the ADT list which is link based,
what is the worst case efficiency?
a. O(1)
b. O(n)
c. O(n2)
d. O(n * log2 n)
8. When an ADT sorted list is implemented using an instance of the ADT list which is link based,
which of the following operations has worst case efficiency?
a. insertSorted (newEntry)
b. getEntry (position)
c. clear()
d. isEmpty()
9. Given the following figure to the right:
According to the text, what is the relationship between List A
and List B?
a. List B is a descendant of List B
b. List A is a descendant of List A
c. List A comes after list B
d. List B is a clone of list A
10. In the class LinkedSortedList, the method copyChain(ptr)is classified as which of the
following?
a. public
b. private
c. shared
d. virtual
11. In the array based implementation of the ADT List operation replace, what is the efficiency?
a. O(n)
b. O(n2)
c. O(1)
d. O(log n)
Chapter 12 Questions
12. Which operation creates a new list and then copies the entries in the given sorted list to the new
list. a. newList
b. destructor
c. constructor
d. copy constructor
Chapter 12 Questions
True or False
1. One of the most frequently performed computing tasks is the maintenance of a collection of data
in some specified order.
2. The ADT list maintains its entries in sorted order.
3. The ADT sorted list in the text allowed the sorted list to contain duplicate items.
4. A sorted list will allow you to add or replace an entry by position.
5. In the class LinkedSortedList, the method copyChain(ptr), is private.
6. The ADTs sorted list and list are completely different in their implementations.
7. The addition to a sorted list is an O(n) operation.
8. It is not possible to use the ADT list when implementing an ADT sorted list.
9. The copy constructor creates a new list and then copies the entries in the given sorted list to the
new list.
10. The implementation of the sorted list using containment is both easy to write and efficient if the
underlying list uses a chain of linked nodes.
11. An is-a relationship implies public inheritance.
12. According to the text most operations for the ADT list are exactly the same as the corresponding
operations for the ADT sorted list.
13. Private inheritance enables you to use the methods of a base class without giving a client access
to them.
14. In an ADT sorted list, the client software determines where to place an entry.
Chapter 12 Questions
15. According to the text, a chain of linked nodes provides a reasonably efficient implementation of
the sorted list.
16. A sorted list is-a list. It is appropriate to use public inheritance.
17. Private inheritance does not allow you to use an instance of SortedListAsA wherever you can
use an instance of LinkedList.
Chapter 12 Questions
Short Answer
1. State three ways in which a sorted list may be implemented.
2. What does adding an entry to a sorted list require?
3. Given the following sorted chain of linked nodes.
According to the text, where would you insert a new node with the string “Sue”
4. What pointers are needed in the method getNodeBefore from the class
LinkedSortedList?
5. Deriving a class of sorted lists from a class of lists using public inheritance is not appropriate.
What extra steps must be taken to do this?
6. Given nameListPtr points to an empty ADT sorted list. Also given the following sequence of
names added to an ADT sorted list:
nameListPtr–>insertSorted(“Tammie”);
nameListPtr–>insertSorted(“Darlah”);
nameListPtr–>insertSorted(“Sarah”);
nameListPtr–>insertSorted(“Tom”);
nameListPtr–>insertSorted(“Carlos”);
What would be returned by the call nameListPtr–>getEntry(2)
7. Given nameListPtr points to an empty ADT sorted list. Also the following sequence of
method calls on this instance of the list.
nameListPtr–>insertSorted(“Tammie”);
nameListPtr–>insertSorted(“Darlah”);
nameListPtr–>insertSorted(“Sarah”);
nameListPtr–>insertSorted(“Tom”);
nameListPtr–>insertSorted(“Carlos”);
nameListPtr–>remove(“Carlos”);
nameListPtr–>remove(1);
What would be returned by the call nameListPtr–>getEntry(2);
Chapter 12 Questions
8. What two operations have efficiency O(n) for both array-based and link-based ADT list
implementations?
9. What two operations have efficiency O(1) for both array-based and link-based ADT sorted list
implementations?
10. When using public inheritance from the ADT list to create an ADT sorted list, why were the
inherited methods insert and replace overridden?
11. When is the only time to use public inheritance?
12. What advantage does private inheritance give in a non is-a relationship between two classes?