Sample Questions: SICP Section 2.3

Symbolic Data

Quoting

  1. What is the print value of the expression (list '1 2 3)?
    1. ('1 2 3)
    2. (1 2 3)
    3. (list (quote 1) 2 3)
    4. (list 1 2 3)
  1. Assuming a and b have value 2 and 3, respectively, what is the print value of the expression (list 'a b)?
    1. ((quote 2) 3)
    2. (a 3)
    3. (list (quote a) 3)
    4. (list a 3)
  1. Assuming a and b have value 2 and 3, respectively, what is the print value of the expression '(list 'a b)?
    1. (list (quote a) b)
    2. (list a b)
    3. (list a 3)
    4. ((quote a) b)
  1. Assuming a and b have value 2 and 3, respectively, what is the print value of the expression ('list a b)?
    1. no value, an error occurs
    2. (list a b)
    3. (list 2 3)
    4. ((quote list) 2 3)
  1. Assuming a and b have value 2 and 3, respectively, what is the print value of the expression '('list a b)?
    1. no value, an error occurs
    2. ((quote list) a b)
    3. (list a b)
    4. ((quote list) 2 3)
  1. 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))?
    1. list
    2. a
    3. (quote a)
    4. 2
  1. 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))?
    1. (quote a)
    2. a
    3. list
    4. (quote list)
  1. 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))?
    1. (a b c)
    2. (b c)
    3. (2 3 4)
    4. (3 4)
  1. What does the function bound to = do?
    1. performs pointer equality
    2. performs assignment
    3. performs structural equality
    4. performs numeric equaility
  1. What does the function bound to eq? do?
    1. performs structural equality
    2. performs pointer equality
    3. performs numeric equaility
    4. performs assignment
  1. What does the function bound to equal? do?
    1. performs numeric equaility
    2. performs pointer equality
    3. performs structural equality
    4. performs assignment
  1. T or F: (eq? '(a b) '(a b))
  1. T or F: (equal? (list 'a 'b) '(a b))
  1. T or F: (equal? (list 2 'b) '(2 'b))

Symbolic differentiation

  1. Consider adding exponentiation to the differentiation program with ** as the exponentiation operator. What would be a vaild implementation for exponentiation?.
    1. (define (exponentiation? p) (eq? (cadr p) '**))
    2. (define (exponentiation? p) (cons '** (deriv p)))
    3. (define (exponentiation? p) (cadr p))
    4. (define (exponentiation? p) (eq? (car p) '**))
  1. Consider adding exponentiation to the differentiation program with ** as the exponentiation operator. What would be a vaild implementation for base.
    1. (define (base p) (if (= (exponent p) 0) 1))
    2. (define (base p) (if (= (exponent p) 1) (base p)))
    3. (define (base p) (car p))
    4. (define (base p) (cadr p))
  1. Consider adding exponentiation to the differentiation program with ** as the exponentiation operator. What would be a vaild implementation for exponent.
    1. (define (exponent p) (caddr p))
    2. (define (exponent p) (if (= (base p) 1) (exponent p)))
    3. (define (exponent p) (car p))
    4. (define (exponent p) (if (= (exponent p) 0) 1))
  1. Consider adding exponentiation to the differentiation program with ** as the exponentiation operator. Which of the following cases is correct for the make-exponentiation working on an expression p that has a base of zero? Assume the exponent is non-zero.
    1. (make-product (make-product (exponent p) (make-exponentiation (base p) (- (exponent p) 1))) (derive (base p) var))
    2. 1
    3. (make-product (exponent p) (make-exponentiation (base p) (- (exponent p) 1)))
    4. 0
  1. Consider modifying the make-sum 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 right-hand-side operand.
    1. (apply make-sum (cddr s))
    2. (make-sum (caddr s) (make-sum (cadddr s))))
    3. (make-sum (car s) (cadr s)))
    4. (caddr s)
  1. Consider modifying the make-sum 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?
    1. (make-sum (caddr s) (make-sum (cadddr s))))
    2. (apply make-sum (cddr s))
    3. (make-sum (car s) (cadr s)))
    4. (caddr s)
  1. Consider modifying the make-sum 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?
    1. (make-sum (cadr s) (make-sum (caddr s))))
    2. (apply make-sum (cddr s))
    3. 0
    4. (caddr s)

Representing sets

  1. 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?
    1. linear, linear, quadratic, quadratic
    2. linear, linear, linear, quadratic
    3. constant, linear, linear, linear
    4. constant, linear, quadratic, quadratic
    5. linear, linear, linear, linear
    6. constant, linear, linear, quadratic
  1. 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.
    1. constant, quadratic, cubic, quartic
    2. linear, linear, quadratic, cubic
    3. constant, quadratic, quadratic, quadratic
    4. linear, linear, quadratic, quadratic
    5. constant, quadratic, quartic, quartic
    6. constant, quadratic, cubic, cubic
  1. Define the adjoin operation for unordered lists, both with and without duplicates.
  1. 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.
    1. log, log, quadratic, quadratic
    2. linear, linear, linear, quadratic
    3. log, log, linear, linear
    4. log, linear, linear, linear
    5. linear, linear, linear, linear
  1. 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.
    1. linear, log, linear, linear
    2. log, log, quadratic, quadratic
    3. log, log, linear, linear
    4. log, linear, linear, linear
    5. linear, linear, linear, quadratic
  1. 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.
    1. log, log, quadratic, quadratic
    2. linear, linear, linear, quadratic
    3. log, linear, linear, linear
    4. linear, linear, linear, linear
    5. linear, linear, quadratic, quadratic
    6. log, log, linear, linear

Huffman encodings

Expect questions in the same vein as the previous set.