Chapter 12  Lists and Array Revisited: Instructor's CD questions

1. A Skip List will typically have better performance than a BST
because:
a) It is always balanced.
b) The amount of balance in the Skip List is driven by the data
values.
*c) The amount of balance in the Skip List is driven by random chance
independent of the data values.

2. The Skip List is an example of a:
a) Greedy data structure.
*b) Probabilistic data structure.
c) Direct access data structure.

3. The average access time for the Skip List is:
a) O(1).
*b) O(log n).
c) O(n).
d) O(n log n).
e) O(n^2).

4. The average number of links store with each Skip List node is:
*a) O(1).
b) O(log n).
c) O(n).
d) O(n log n).
e) O(n^2).

5. A "pure list" form of a multilist is, structurally, most like a:
a) Linked list.
*b) Binary tree.
c) Heap.
d) Graph.
e) Directed acyclic graph.

6. A "reentrant list" form of a multilist is, structurally, most like a:
a) Linked list.
b) Binary tree.
c) Heap.
d) Graph.
*e) Directed acyclic graph.

7. A "cyclic list" form of a multilist is, structurally, most like a:
a) Linked list.
b) Binary tree.
c) Heap.
*d) Graph.
e) Directed acyclic graph.

8. If a data element requires 4 bytes and a pointer requires 4 bytes,
then an orthogonal list representation will be more space efficient
than a standard array representation when the fraction of non-zero
elements is less than about:
a) 100%
b) 75%
c) 25%
*d) 15%
e) 5%
f) never

9. External fragmentation occurs when:
*a) The memory requests create lots of small free blocks, no one of
which is useful for servicing typical requests.
b) More space is allocated to a request than required.
c) The disk has no room for the file.

10. Which of the following is not the name for a standard
sequential-fit technique for allocating space from a memory pool:
a) first fit.
b) best fit.
c) worst fit.
*d) priority fit.

11. The buddy method creates which form of fragmentation?
*a) Internal.
b) External.

12. The best-fit method creates which form of fragmentation?
a) Internal.
*b) External.