Test Questions & Answers Chapter.17 - Sorted Lists

Chapter 17 - Sorted Lists

True/False (14)

1. Entries in a sorted list are ordered simply by their positions within the list.
2. In a sorted list, you do not specify where in the list the entry belongs.
3. The entries in a sorted list must be objects that can be compared to each other.
4. The ADT sorted list cannot contain null entries.
5. In a sorted list with entries in ascending order, you insert a new entry just after the first entry that is not smaller than the new entry.
6. If a sorted list is empty, a call to the getNodeBefore method returns null.
7. In the LinkedSortedList implementation, when you try to add an entry that already exists in the list, it is added after the last duplicate occurrence.
8. In the LinkedSortedList, a recursive addition to a chain of nodes locates and remembers the nodes prior to the insertion point.
9. The linked implementation of the ADT sorted list maintains a tail reference.
10. In the ADT sorted list, the worst-case time efficiency of the array implementation and the linked implementation add operation is the same.
11. In the ADT sorted list, the worst-case time efficiency of the array implementation and the linked implementation getEntry operation is the same.
12. In the SortedList implementation, the add method sets the sign of the integer it returns to indicate whether the entry exists in the list already.
13. The ADT sorted list, the time efficiency of the getPosition method depends on the efficiency of the getEntry method.
14. The ADT sorted list, the time efficiency of the getEntry is independent of which implementation of the ADT list you use.

Short Answer (5)

1. Explain why the client must not be able to specify where a new entry will be placed in a sorted list.
2. In the ADT sorted list, why is it not necessary for the remove method to return the object removed from the list?
3. In the ADT sorted list, why does the remove(givenPosition) throw an exception if the search fails?
4. Why is using recursion to process a chain of linked nodes for the sorted list implementation more complex that the iterative approach?
5. Explain when you wouldn’t need to check the sign of the integer returned by the add method in the SortedList implementation.

Multiple Choice (31) 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 list where entries are compared to each other and ordered accordingly is called a
   1. sorted list
   2. ordered list
   3. comparative list
   4. stream lined list
2. Which operation(s) behave(s) the same for both the ADT list and the ADT sorted list?
   1. getEntry(givenPosition)
   2. contains(anEntry)
   3. clear()
   4. all of the above
3. Which operation(s) behave(s) the same for both the ADT list and the ADT sorted list?
   1. remove(givenPosition)
   2. getPosition(anEntry)
   3. add(newEntry)
   4. all of the above
4. In the ADT sorted list, what does the getPosition method do when the entry being searched for is not in the list?
   1. return a negative number
   2. return 0
   3. return false
   4. throw an UnfoundElementException
5. In the ADT sorted list, what does the getPosition method do?
   1. searches for an entry in the list
   2. returns the position number if the entry is found in the list
   3. returns a negative number where the entry belongs in the list if it is not found
   4. all of the above
6. In the ADT sorted list, if an entry being searched for is not found but belongs at position 7, what does the getPosition method do?
   1. return -7
   2. return 7
   3. return 0
   4. throws an UnfoundElementException
7. In the ADT sorted list, what does the getPosition method do when the list is empty?
   1. return -1
   2. return 1
   3. return 0
   4. throw an UnfoundElementException
8. In the ADT sorted list, why is there no functionality to add an entry at a given position?
   1. the client could destroy the order of the list
   2. the client would have too much information about the underlying code
   3. the client would be able to access the list illegally
   4. none of the above
9. Which method that is part of the ADT list is not supported in the ADT sorted list?
   1. replace
   2. remove
   3. add
   4. getEntry
10. Which functionality is part of the ADT sorted list given the entry as an argument?
    1. add
    2. remove
    3. locate
    4. all of the above
11. In the ADT sorted list, what happens when the remove(anEntry) is called?
    1. it removes the given entry
    2. it returns true if it succeeded
    3. it returns false if it failed
    4. all of the above
12. In the ADT sorted list, what happens when the remove(anEntry) does not find the entry in the sorted list?
    1. it returns false
    2. it returns null
    3. it returns a negative number
    4. it throws an exception
13. In the ADT sorted list, what happens when the remove(givenPosition) does not find the entry in the sorted list?
    1. it throws an exception
    2. it returns a negative number
    3. it returns false
    4. it returns null
14. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the list look like after the following operations?
    amphibianList.add(“iguana”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.add(“lizard”);
    1. gecko, iguana, lizard, toad
    2. iguana, gecko, toad, lizard
    3. lizard, toad, gecko, iguana
    4. none of the above
15. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the statement
    amphibianList.getPosition(“iguana”)
    produce after the following operations?
    amphibianList.add(“iguana”);
    amphibianList.add(“salamander”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.add(“lizard”);
    1. 2
    2. 1
    3. 3
    4. 4
16. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the statement
    amphibianList .contains(“frog”)
    return after the following operations?
    amphibianList.add(“iguana”);
    amphibianList.add(“salamander”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList .add(“lizard”);
    1. false
    2. 0
    3. null
    4. throws an exception
17. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the list look like after the following operations?
    amphibianList.add(“salamander”);
    amphibianList.add(“iguana”);
    amphibianList.add(“lizard”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.remove(“iguana”);
    1. gecko, lizard, salamander, toad
    2. salamander, lizard, gecko, toad
    3. toad, gecko, lizard, salamander
    4. none of the above
18. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the list look like after the following operations?
    amphibianList.add(“salamander”);
    amphibianList.add(“iguana”);
    amphibianList.add(“lizard”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.remove(4);
    1. gecko, iguana, lizard, toad
    2. toad, salamander, lizard, gecko
    3. salamander, iguana lizard, toad
    4. none of the above
19. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what does the list look like after the following operations?
    amphibianList.add(“salamander”);
    amphibianList.add(“iguana”);
    amphibianList.add(“lizard”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.remove(6);
    1. throws an exception
    2. salamander
    3. 0
    4. null
20. Given the following definition,
    SortedListInterface<String> amphibianList = new SortedList<>();
    what happens after the following operations?
    amphibianList.add(“salamander”);
    amphibianList.add(“iguana”);
    amphibianList.add(“lizard”);
    amphibianList.add(“gecko”);
    amphibianList.add(“toad”);
    amphibianList.remove(“snake”);
    1. false
    2. throws an exception
    3. -1
    4. null
21. You can implement a sorted list with
    1. an array
    2. a chain of linked nodes
    3. an instance of a vector
    4. all of the above
22. In the LinkedSortedList implementation, how many references do you need to traverse the list?
    1. two
    2. three
    3. one
    4. none
23. What happens when a call to the getNodeBefore method is made on an empty list?
    1. null
    2. 0
    3. -1
    4. throws an exception
24. What happens when the add method is called with an entry that is already on the list?
    1. it inserts the entry before the first occurrence
    2. it inserts the entry after the last occurrence
    3. it throws a NodeConflictException
    4. it ignores the entry and returns true
25. If a list contains seven duplicate objects on a list and you remove one of them, which one is removed?
    1. the first one
    2. the second one
    3. the seventh one
    4. it is nondeterministic
26. In the link-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the add(newEntry) method?
    1. O(n²)
    2. O(n)
    3. O(log n)
    4. O(1)
27. In the array-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the add(newEntry) method?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
28. In the link-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the remove(givenPosition) method?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
29. In the array-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the remove(givenPosition) method?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
30. In the link-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the getEntry(givenPosition) method?
    1. O(n)
    2. O(n²)
    3. O(log n)
    4. O(1)
31. In the array-based list implementation of the ADT sorted list, what is the worst-case time efficiency of the getEntry (givenPosition) method?
    1. O(1)
    2. O(n²)
    3. O(log n)
    4. O(n)