Sample Questions: SICP Section 2.3
Symbolic Data
Quoting

What is the print value of the expression
(list '1 2 3)
?

('1 2 3)

(1 2 3)

(list (quote 1) 2 3)

(list 1 2 3)

Assuming a and b have value 2 and 3, respectively,
what is the print value of the expression
(list 'a b)
?

((quote 2) 3)

(a 3)

(list (quote a) 3)

(list a 3)

Assuming a and b have value 2 and 3, respectively,
what is the print value of the expression
'(list 'a b)
?

(list (quote a) b)

(list a b)

(list a 3)

((quote a) b)

Assuming a and b have value 2 and 3, respectively,
what is the print value of the expression
('list a b)
?
 no value, an error occurs

(list a b)

(list 2 3)

((quote list) 2 3)

Assuming a and b have value 2 and 3, respectively,
what is the print value of the expression
'('list a b)
?
 no value, an error occurs

((quote list) a b)

(list a b)

((quote list) 2 3)

Assuming a, b, and c have value 2, 3, and 4, respectively,
what is the print value of the expression
(car (list 'a 'b 'c))
?

list

a

(quote a)

2

Assuming a, b, and c have value 2, 3, and 4, respectively,
what is the print value of the expression
(car '(list 'a 'b 'c))
?

(quote a)

a

list

(quote list)

Assuming a, b, and c have value 2, 3, and 4, respectively,
what is the print value of the expression
(cdr (list 'a 'b 'c))
?

(a b c)

(b c)

(2 3 4)

(3 4)

What does the function bound to
=
do?
 performs pointer equality
 performs assignment
 performs structural equality
 performs numeric equaility

What does the function bound to eq? do?
 performs structural equality
 performs pointer equality
 performs numeric equaility
 performs assignment

What does the function bound to equal? do?
 performs numeric equaility
 performs pointer equality
 performs structural equality
 performs assignment

T or F:
(eq? '(a b) '(a b))

T or F:
(equal? (list 'a 'b) '(a b))

T or F:
(equal? (list 2 'b) '(2 'b))
Symbolic differentiation

Consider adding exponentiation to the differentiation program with
**
as the exponentiation operator. What would be a vaild implementation
for exponentiation?.

(define (exponentiation? p) (eq? (cadr p) '**))

(define (exponentiation? p) (cons '** (deriv p)))

(define (exponentiation? p) (cadr p))

(define (exponentiation? p) (eq? (car p) '**))

Consider adding exponentiation to the differentiation program with
**
as the exponentiation operator. What would be a vaild implementation
for base.

(define (base p) (if (= (exponent p) 0) 1))

(define (base p) (if (= (exponent p) 1) (base p)))

(define (base p) (car p))

(define (base p) (cadr p))

Consider adding exponentiation to the differentiation program with
**
as the exponentiation operator. What would be a vaild implementation
for exponent.

(define (exponent p) (caddr p))

(define (exponent p) (if (= (base p) 1) (exponent p)))

(define (exponent p) (car p))

(define (exponent p) (if (= (exponent p) 0) 1))

Consider adding exponentiation to the differentiation program with
**
as the exponentiation operator.
Which of the following cases is correct
for the makeexponentiation working on an expression p
that has a base of zero? Assume the exponent is nonzero.

(makeproduct (makeproduct (exponent p) (makeexponentiation (base p) ( (exponent p) 1))) (derive (base p) var))
 1

(makeproduct (exponent p) (makeexponentiation (base p) ( (exponent p) 1)))
 0

Consider modifying the makesum function of the text's
differentiation program to handle arity of
2 or more operands. Which of the following cases is correct
for the addend selector if a sum s has three or more operands?
Note: the addend is the righthandside operand.

(apply makesum (cddr s))

(makesum (caddr s) (makesum (cadddr s))))

(makesum (car s) (cadr s)))

(caddr s)

Consider modifying the makesum function of the text's
differentiation program to handle arity of
one or more operands. Which of the following cases is correct
for the addend selector if a sum s has exactly two operands?

(makesum (caddr s) (makesum (cadddr s))))

(apply makesum (cddr s))

(makesum (car s) (cadr s)))

(caddr s)

Consider modifying the makesum function of the text's
differentiation program to handle arity of
1 or more operands. Which of the following cases is correct
for the addend selector if a sum s has exactly one operands?

(makesum (cadr s) (makesum (caddr s))))

(apply makesum (cddr s))
 0

(caddr s)
Representing sets

What is the time complexity of
adjoin, member?, union, and intersection operations on
sets if the sets are represented as unordered lists with no duplicates?
 linear, linear, quadratic, quadratic
 linear, linear, linear, quadratic
 constant, linear, linear, linear
 constant, linear, quadratic, quadratic
 linear, linear, linear, linear
 constant, linear, linear, quadratic

What is the time complexity of
adjoin, member?, union, and intersection operations on
sets if the sets are represented as unordered lists with duplicates allowed?
Assume there will never be more than n duplicates per element
where n is the number of (unique) elements in the set.
 constant, quadratic, cubic, quartic
 linear, linear, quadratic, cubic
 constant, quadratic, quadratic, quadratic
 linear, linear, quadratic, quadratic
 constant, quadratic, quartic, quartic
 constant, quadratic, cubic, cubic

Define the adjoin operation for unordered lists, both with and without
duplicates.

What is the time complexity of
adjoin, member?, union, and intersection operations on
sets if the sets are represented as ordered lists? Assume
the sets are roughly equal in size.
 log, log, quadratic, quadratic
 linear, linear, linear, quadratic
 log, log, linear, linear
 log, linear, linear, linear
 linear, linear, linear, linear

What is the time complexity of
adjoin, member?, union, and intersection operations on
sets if the sets are represented as ordered arrays? Assume
the sets are roughly equal in size.
 linear, log, linear, linear
 log, log, quadratic, quadratic
 log, log, linear, linear
 log, linear, linear, linear
 linear, linear, linear, quadratic

What is the time complexity of
adjoin, member?, union, and intersection operations on
sets if the sets are represented as ordinary binary search trees? Assume
the sets are roughly equal in size.
 log, log, quadratic, quadratic
 linear, linear, linear, quadratic
 log, linear, linear, linear
 linear, linear, linear, linear
 linear, linear, quadratic, quadratic
 log, log, linear, linear
Huffman encodings
Expect questions in the same vein as the previous set.