- A List Implementation That Links Data Exam Prep Chapter 12

Chapter 12 - A List Implementation that Links Data

True/False (13)

1. Adding a node to an empty chain is the same as adding a node to the beginning of a chain.
2. Adding a node at the end of a chain of n nodes is the same as adding a node at position n.
3. You need a temporary variable to reference nodes as you traverse a list.
4. The efficiency of the displayList method is directly related to the efficiency of the getEntry method.
5. You cannot use an assert statement to determine if a list is empty.
6. A fundamental operation of a list is a traversal.
7. You must know how much memory to allocate before creating a linked implementation of a list.
8. A linked implementation of a list grows and shrinks dynamically as nodes are added and deleted.
9. In a linked implementation of a list, you only call the method getNodeAt to remove an entry other than the first one.
10. Replacing a node in a linked implementation of a list only requires locating the node and replacing the data portion of the node.
11. In a linked implementation of a list, the replace method replaces the entire node.
12. Retrieving a list entry using a linked implementation is faster than using an array representation.
13. Replacing a list entry using an array implementation is faster than using a linked representation.

Short Answer (6)

1. Explain why a public method should be declared to be final if it is called by a constructor.
2. In the linked implementation of a list, why shouldn’t the constructor call the method clear even though they do the same exact assignment statements?
3. Outline the basic steps to add a node to the end of a linked implementation of a list.

2) traverse the list and find the last node
3) set the last node to reference the new node

1. Outline the basic steps to add a node to the beginning of an empty linked implementation of a list.

2) set the new node to reference the node the first node references
3) set the first node to reference the new node

1. Outline the basic steps to add a node to the beginning of a non-empty linked implementation of a list.

2) set the new node to reference the node the first node references
3) set the first node to reference the new node

(note, yes this is the same answer as #4 but the question is slightly different – empty vs. non-empty)

1. Outline the basic steps to remove a node from the beginning of a list.

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

1. A linked implementation of a list
   1. uses memory only as need for new entries
   2. returns unneeded memory to the system when an entry is removed
   3. avoids moving data when adding or removing entries
   4. all of the above
2. In a chain of linked nodes you can
   1. add nodes from the beginning of a chain
   2. add nodes from the end of a chain
   3. add nodes that are between other nodes
   4. all of the above
3. In a chain of linked nodes you can
   1. remove nodes from the beginning of a chain
   2. remove nodes from the end of a chain
   3. remove nodes that are between other nodes
   4. all of the above
4. If a chain is empty, the head reference
   1. is null
   2. is an empty node with the data field not set
   3. is in an illegal state
   4. none of the above
5. When inserting a node between adjacent nodes in a chain you must locate
   1. the node before the insertion position and the node after the insertion position
   2. the first node and the node before the insertion position
   3. the first node and the node after the insertion position
   4. the last node and the node after the insertion position
6. Adding a node at the end of a chain of n nodes is the same as adding a node at position
   1. n + 1
   2. n
   3. n – 1
   4. 0
7. If the reference to the first node is null, this means
   1. the list is empty
   2. the list is full
   3. the garbage collector should be invoked
   4. the list is in an unstable state
8. The last node is a list has a reference to
   1. null
   2. itself
   3. the node before it
   4. none of the above
9. To locate a node within a chain that is near the end of the list, we must
   1. start at the first node and traverse the chain
   2. start at the last node and traverse the chain
   3. directly access the node
   4. none of the above
10. Moving through a linked implementation of a list from one node to another is called
    1. traversing
    2. walking
    3. hopping
    4. none of the above
11. In the LList implementation of a list, when a list is empty the firstNode is _____ and the numberOfEntries is _____.
    1. null, 0
    2. null, 1
    3. an empty node, 0
    4. an empty node, 1
12. In the LList implementation of a list, the constructor and the clear method
    1. have the same functionality
    2. do completely different things
    3. unnecessary
    4. none of the above
13. In the linked implementation of a list, the add method
    public void add(T newEntry)
    inserts a new entry
    1. at the end of the list
    2. at the beginning of the list
    3. between adjacent nodes of the list
    4. all of the above
14. In the linked implementation of a list, the add method
    public void add(int newPosition, T newEntry)
    inserts a new entry
    1. between adjacent nodes of the list
    2. at the end of the list
    3. at the beginning of the list
    4. all of the above
15. In the linked implementation of a list, what happens when you try to add a node at an invalid position?
    1. it throws an IndexOutOfBoundsException
    2. it throws an InvalidLinkException
    3. it returns null
    4. it returns false
16. To determine if a list is empty you can
    1. check to see if the length of the list is zero
    2. check to see if the reference to firstNode is null
    3. use an assertion on firstNode == null
    4. all of the above
17. In the LList implementation of a list, given a node called currentNode, which statement moves the node’s reference to the next node?
    1. currentNode.getNextNode();
    2. currentNode.get();
    3. currentNode.forward();
    4. currentNode.traverse();
18. A reference to the last node in a linked implementation of a list is commonly called the
    1. tail
    2. end
    3. final
    4. none of the above
19. Including a tail reference to a linked implementation of a list makes which functionality more efficient?
    1. adding a node to the end of a list
    2. searching for a node on the list
    3. removing a node from the list
    4. all of the above
20. In a linked implementation of a list with a tail reference, removing an entry affects the tail reference if
    1. the list has multiple entries and the entry to be removed is the last one
    2. the list has multiple entries and the entry to be removed is the first one
    3. the list is empty
    4. all of the above
21. In a linked-based implementation of the ADT list with only a head reference, what is the performance of adding an entry at the end of the list?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
22. In a linked-based implementation of the ADT list with a tail reference, what is the performance of adding an entry at the end of the list?
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
23. In a linked-based implementation of the ADT list with a tail reference, what is the performance of adding an entry that is not at the beginning of the list?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
24. In a linked-based implementation of the ADT list with only a head reference, what is the performance of removing an entry at the beginning of the list?
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
25. In a linked-based implementation of the ADT list with only a head reference, what is the performance of removing an entry at the end of the list?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
26. In a linked-based implementation of the ADT list with a tail reference, what is the performance of removing an entry at the beginning of the list?
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
27. In a linked-based implementation of the ADT list with a tail reference, what is the performance of removing an entry that is not at the beginning of the list?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
28. In a linked-based implementation of the ADT list with only a head reference, which method has a time efficiency of O(1)?
    1. clear
    2. toArray
    3. contains
    4. all of the above
29. In a linked-based implementation of the ADT list with a tail reference, which method has a time efficiency of O(1)?
    1. adding an entry to the end of the list
    2. adding an entry to the beginning of the list
    3. clear
    4. all of the above