Last name: _____________________
Given name: ____________________
CSE373 Winter 2005
Miniquiz #3 with notes
Feb. 2, 2005
2 pts. per question unless noted

Suppose we have a doubly-linked list with a Node defined as follows:
    class Node {
        Object element;
        Node prev, next;
}
In the list implementation, prev is null for the first node in the list, and next is null for the last node in the list.  (For our present purposes, there is no separate head node).
1. Draw a picture of a list with exactly four nodes, containing elements A, B, C, and D in that order.  Show the value of element, prev, and next for each node (drawing arrows may be an appropriate way to show values...).



2. Suppose we want to delete node D.  What must change?  Circle all that apply.  (The notation is informal.  A.prev means "the prev field of the node containing the element A", etc.)
    A.element  A.prev  A.next
    B.element  B.prev  B.next
    C.element  C.prev  C.next
    D.element  D.prev  D.next

Note that it is not necessary to make any changes to D.  However, many programmers would null out D's element and prev pointers (the next pointer is already null).  This allows C to be garbage-collected at some point in the future when there are no longer any references to it.  It's not really an issue, actually, unless there is a live reference to D somewhere.  Once all references to D are gone, D can be garbage collected even if it contains non-null references itself.

3. Starting back from the original list of four elements, suppose we want to swap node C with its predecessor.  What must change?  Circle all that apply.
    A.element  A.prev  A.next
    B.element  B.prev  B.next
    C.element  C.prev  C.next
    D.element  D.prev  D.next

4. "Locality of reference" in computer situations (like some discussed Monday) is most like which of these everyday situations?

A. If I was in a certain location yesterday, I'm likely to be near there again today.
B. My GPS device tells me my location.
C. Referring to Feb. 2 as Groundhog Day is purely a local custom.
D. I was unable to locate the lost sock even though I knew where it should have been.
E. My neighbor referred me to the location a good video rental store.

See definition on p.231

5.  Suppose a Favorites List is implemented with the Move to Front heuristic.   Suppose that at one point in time the list has the contents (the numbers are the access counts):

(front of list) Homer(1000)  Hesiod(801)  Pope(700)  Byron(21)  Dylan(13)  Frost(2)

Show the list contents after the following sequence of accesses
    Dylan
    Pope

Pope(701) Dylan(14) Homer(1000) Hesiod(801) Byron(21) Frost(2)

Code for a Favorites List with the Move to Front heuristic is given on p.230.  It extends an implementation (p.226) which uses what I called in class the Move Up by One heuristic.  The two versions result in rather different orderings, especially when many of the accesses are to infrequent (low-count) elements.

6. If a Stack is LIFO, and a stack is FIFO, then a priority queue should be... (make up and explain an acronym).