A cons is a pair of pointers; the first one is the car and the second one is the cdr.

Here, we cons something onto nil:
> (setf x (cons 'a nil))
(A)

1. A. Draw the box diagram for the above setf.
    B. >(car x) => ___
    C. >(cdr x) => ___

Building a list of multiple elements gives a chain of conses:
    >(setf y (list 'a 'b 'c))
    (A B C)
2. Draw the box and pointer diagram:

A list can have any kind of object as an element, including another list:
>(setf z (list 'a (list 'b 'c) 'd))
(A (B C) D)
3. A. Draw the box and pointer diagram:
    B. >(car (cdr z)) => _____

The function consp returns true if its argument is a cons. So listp could be defined:
(defun our-listp (x)
   (or (_______) (consp x)))

The predicate atom could be defined as:
(defun our-atom (x)
   (not (consp x))    
Does this definition work? Yes/No

4. _____ is both an atom and a list.

Each time you call cons, Lisp allocates a new piece of memory with room for two pointers. If cons is called twice with the same arguments, we get back two values that look the same, but are disjoint objects.
5. A. >(eql (cons 'a nil) (cons 'a nil))
    Is this T or NIL? _____
    B. >(equal x (cons 'a nil))
Is this T or NIL? ________

>(setf x '(a b c))
(A B C)
>(setf y x)
(A B C)
6. A. (eql x y)
    Is this T or NIL? ____
    B. (equal x y)
    T or NIL? _____

The reason Lisp has no pointers is that every value is conceptually a pointer. When you assign a value to a variable or store it in a data structure, what gets stored is actually a pointer to the value.

The function copy-list takes a list and returns a copy of it. The new list will have the same elements, but contained in new conses.
>(setf x '(a b c)
       y (copy-list x))
7. Draw the box and pointer diagram for copy-list.

8. copy-list could be defined as:
(defun our-copy-list (lst)
    (if (atom lst)
        lst
        (cons (_________) (our-copy-list (____________)))))

9. Mapcar:
>(mapcar #'(lambda (x) (+ x 10))
       '(1 2 3))
___________ ???
>(mapcar #'list
       '(a b c)
       '(1 2 3 4))
_____________???

Trees: Conses can be thought of as binary trees, with the car representing the right subtree and the cdr the left.
10. Draw as a tree shaped box and pointer diagram:
(a (b c) d)

11. The function copy-tree takes a tree and returns a copy of it. Write function our-copy-tree:
(defun our-copy-tree (tr)
    (if (atom tr)
        tr
        (cons (our-copy-tree (__________))
            (our-copy-tree (____________)))))

12. A. (eql 'a 'a) => _____
    B. (equal 'a 'a) => _____
    C. (eql '(a) '(a)) => _____
    D. (equal '(a) '(a)) => _____
    E. Explain the answer to part C.

By default, member compares objects using eql.
13. A. (member 'a '(a b)) => _____
    B. (member '(a) '((a) (b))) => _____

You can use a keyword argument to change the test.
14. (member '(a) '((a) (b)) :test #'equal) => _____

Dotted Lists.
15. >(setf pair (cons 'a 'b))
(A . B)
    Draw the box and pointer diagram for the above setf.
16. A. >'(a . (b . (c . nil))) => ___________
    B. >(cons 'a (cons 'b (cons 'c 'd))) => _________
    C. >'(a . (b . nil)) => ________
    D. >'(a . (b)) => ________
    E. >'(a b . nil) => ________

Association lists: Assoc-lists.
A list of conses is called an assoc-list or alist. Such a list could represent a set of translations, for example:
> (setf trans '((+ . "add") (- . "subtract")))

Assoc-lists are slow, but convenient in the first stages of a program. Common Lisp has a built-in function, assoc, for retrieving the pair associated with a given key:
> (assoc '+ trans)
(+ . "add")
> (assoc '* trans)
NIL

Graphs/Networks - In this example, nodes are represented as symbols, and networks (graphs) are represented as assoc-lists with elements of the form:

(node . neighbors)

A minimal network could be represented as:
> (setf min '((a b c) (b c) (c d)))
Draw the directed graph represented by this minimal network.

17. Using depth-first search, name the nodes searched to travel from node a to node d.
_____________ one possible path
_____________ second possible path

18. Using breadth first search, name the nodes searched to travel from node a to node d.
    A. _________ (2 nodes, not found a to d)
    B. _________ (2 nodes, not found a to d)
    C. _________ (3 nodes, not found a to d)
    D. _________ (3 nodes, found a to d)

Answers

1.  car of cons box points to A
    cdr of cons box points to NIL

2. Three cons boxes.  The car of the boxes point to the elements A B and C, respectively.  The cdrs:  box1 --> box2 --> box3 --> NIL

3. Three cons boxes at the upper level.
  Car of box 1 --> A, Car of box 2 --> two more cons boxes, Car of box 3 --> D
  Cdr's: box 1 --> box2 --> box 3 --> NIL

  For the sublist of two cons boxes, boxes 2a and 2b 
    car of box 2a --> B, car of box 2b --> C
    cdr's: box 2a --> 2b --> NIL
 (defun our-listp (x)
   (or (_______) (consp x)))   ans: (null x)

4.  Nil

5. A. NIL  B.  T

6.  A. T B 

4.  Nil

5. A. NIL  B.  T

6.  A. T B. T

7.  X points to three cons boxes (cons cells), the car's of each box point to 
  A, B, and C respectively.  Cdr's: Box1 --> box2 --> box 3--> nil

   Y points to three different cons boxes, but the car's of each of these boxes
    point to the A, B, and C values from above.

8. defun our-copy-list (lst)
    (if (atom lst)
        lst
        (cons (_________) (our-copy-list (____________)))))
    Ans:    (first lst)                 (rest lst)

9.  (11 12 13)
    ((a 1) (b 2) (c 3))

10.  top of tree is a cons box, the car (left ptr) points to A, and the cdr (right) pointer points to the next cons.
    In the new cons, the left pointer points to a cons representing the first
     cons of the list (b c)   etc:

        cons
     /      \
   A        cons
          /       \
        cons       cons
       /   \       /  \
     B     cons   D   nil
          /   \
        C    nil

11.
(defun our-copy-tree (tr)
    (if (atom tr)
        tr
        (cons (our-copy-tree (__________))    Ans: (first tr)
            (our-copy-tree (____________)))))  Ans: (rest tr)

12. A.  T   B. T  C. NIL  D. T
    E. The two lists are not the same cons cell

13.  A.  T   returns (a b)
     B  NIL

14.  T

15.    cons
     /     \
   A       B

16.  (a b c) for all answers

17.  a's neighbors are b and c
     b's neighbor is c
     c's neigbor is d

  A.  A B C D
  B.  A C D

18.  A. A B
     B. A C
     C. A B C
     D. A C D