Sample Questions: SICP Section 2.2
Hierarchical Data and the Closure Property
Cons structures

How many cons cells make up the structure
with the print value of
(1 (2 3) 4)
?
 4
 6
 5
 3

How many cons cells make up the structure
with the print value of
(1 (2 3) . 4)
?
 5
 4
 6
 3

How many cons cells make up the structure
with the print value of
(1 (2 . 3) . 4)
?
 4
 6
 3
 5

How many cons cells make up the structure
with the print value of
(1 (2 . 3) 4)
?
 5
 4
 6
 3

What is the minimum number of cons cells needed to bundle up 4 numbers
into a single cons structure?
 6
 5
 4
 3

What is the minimum number of cons cells needed to bundle up 4 numbers
into a single list structure (i.e. no nested lists)?
 6
 5
 4
 3
Heirarchical structures

Draw a cons structure in the style of the text
that represents a binary search tree with the
elements 3, 1, 2, 5 inserted in that order.
Use nils to indicate missing children.

Draw a cons structure in the style of the text
that represents a trinary search tree with the
elements 3, 1, 2, 1, 5, 1 inserted in that order. A trinary search tree
behaves just as a binary search tree except
duplicates are inserted as middle children.
Use nils to indicate missing children.

Consider the singlylinked list
$2\to 5\to 3\to $nil.
Draw a cons cell representation of this list,
assuming there is only a head pointer. Use the style of the text.
Use the variable items to point to this list.

Consider the singlylinked list
$2\to 5\to 3\to $nil.
Draw a cons cell representation of this list,
assuming there is a head and a tail pointer. Use the style of the text.
Use the variable items to point to this list.
Conventional interfaces

(3 points)
Define a function named flatten that takes deeply nested list and
returns a flat list of all the elements in the original list. For example,
(flatten '((a (b)) c))
evaluates to
(a b c)
.
You may find the functions pair? or atom? useful.

ount the number of.Sum the odd values in a deeply
nested list.
Pick from
the components flatten, map, keep, remove, accumulate,
append, and odd?.
Assume the name of the incoming list is items.

Suppose I wish to find the product of
all the prime numbers from 1 to n?
Pick from
the components enumerate, map, keep, remove, accumulate,
and prime?.
Start with n.

Suppose I wish to collect
all the nonprime numbers from 1 to n?
Pick from
the components enumerate, map, keep, accumulate,
and prime?.
Start with n.
Note: remove is not available.

Sum of
all the even numbered squares of the numbers
in a given list named items.
Pick from
the components enumerate, map, remove, accumulate,
square, and even?.
Note: keep is not available.

Collect
all the odd numbered squares of the numbers
in a given list named items.
Pick from
the components enumerate, map, remove, accumulate,
square, and even?.

Collect the squares of
all the Mersenne primes generated from a list of exponents, named raises.
A Mersenne prime has the form ${2}^{n}1$.
Pick from
the components enumerate, map, keep, remove, accumulate,
prime?, square, and expt.
Nested mappings

(2 points)
Collect all the pairs $(i,j)$
such that $0\le i<n$ and $0\le j<n$.
Pick from
the components enumerate, map, keep, remove, accumulate,
and expand.
The expand function takes a list, a single item, and
a location,
and creates a list of lists composed each of the list
items and the single item.
For example,
(expand '(1 4 2) 0 'back)
evaluates to
((1 0) (4 0) (2 0))
,
while
(expand '(1 4 2) 0 'front)
evaluates to
((0 1) (0 4) (0 2))
.
Start with n.

(2 points)
Collect all the pairs $(i,j)$
such that $0\le i<n$ and $0\le j<i$.
Pick from
the components enumerate, map, keep, remove, accumulate,
and expand.
The expand function takes a list, a single item, and
a location,
and creates a list of lists composed each of the list
items and the single item.
For example,
(expand '(1 4 2) 0 'back)
evaluates to
((1 0) (4 0) (2 0))
,
while
(expand '(1 4 2) 0 'front)
evaluates to
((0 1) (0 4) (0 2))
.
Start with n.

(2 points)
Collect all the pairs $(i,j)$
such that $0\le i<n$ and $i\le j<n$.
Pick from
the components enumerate, map, keep, remove, accumulate,
and expand.
The expand function takes a list, a single item, and
a location,
and creates a list of lists composed each of the list
items and the single item.
For example,
(expand '(1 4 2) 0 'back)
evaluates to
((1 0) (4 0) (2 0))
,
while
(expand '(1 4 2) 0 'front)
evaluates to
((0 1) (0 4) (0 2))
.
Start with n.
Programming tasks

(3 points)
Define a function named index that retrieves the ${i}^{th}$ element
of a given list. Do not perform any error checking.

(3 points)
Define a function named list? that determines whether a given
cons structures is a list at the top level.
Do not check if substructures are lists.
Do not perform any error checking.

(3 points)
Define a function named ntail that returns the ${n}^{th}$ tail of
a given list. When passed a value of 0, ntail should return the
given list; when passed a value of 1, ntail should return the cdr
of the list, and so on. Do not perform any error checking.

(3 points)
Define a function named list+ that returns the sum of all the elements
in a given list made up of numbers.
The list does not have any sublists.
Do not perform any error checking.

(3 points)
Define a function named list+ that returns the sum of all the elements
in a given list made up of numbers.
The list may have sublists that need to be considered.
Assume the existence of the predicate list?.
Do not perform any error checking.

(3 points)
Define a function named oddCount that returns the number of elements
in a given list that are odd.
The list does not have any sublists.
You must use the predefined predicate function even?.
Do not perform any error checking.

(3 points)
Define a function named evenCount that returns the number of elements
in a given list that are even.
The list may have sublists that need to be considered.
You must use the predefined predicates even? and list?.
Do not perform any error checking.

(3 points)
Define a function named consCount that counts
the number of cons cells
in a given structure. Assume the existence of the predicate pair?
which returns true if its argument is a cons cell.

(3 points)
Define a function named doubleList that returns a new list
composed of the numbers that are twice that in a given list of numbers
(in the same order).
Do not use map.
Do not perform any error checking.