Sample Questions: SICP Section 2.2

Hierarchical Data and the Closure Property

Cons structures

  1. How many cons cells make up the structure with the print value of (1 (2 3) 4)?
    1. 4
    2. 6
    3. 5
    4. 3
  1. How many cons cells make up the structure with the print value of (1 (2 3) . 4)?
    1. 5
    2. 4
    3. 6
    4. 3
  1. How many cons cells make up the structure with the print value of (1 (2 . 3) . 4)?
    1. 4
    2. 6
    3. 3
    4. 5
  1. How many cons cells make up the structure with the print value of (1 (2 . 3) 4)?
    1. 5
    2. 4
    3. 6
    4. 3
  1. What is the minimum number of cons cells needed to bundle up 4 numbers into a single cons structure?
    1. 6
    2. 5
    3. 4
    4. 3
  1. What is the minimum number of cons cells needed to bundle up 4 numbers into a single list structure (i.e. no nested lists)?
    1. 6
    2. 5
    3. 4
    4. 3

Heirarchical structures

  1. 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.
  1. 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.
  1. Consider the singly-linked list 2 5 3 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.
  1. Consider the singly-linked list 2 5 3 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

  1. (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.
  1. 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.
  1. 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.
  1. Suppose I wish to collect all the non-prime numbers from 1 to n? Pick from the components enumerate, map, keep, accumulate, and prime?. Start with n. Note: remove is not available.
  1. 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.
  1. 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?.
  1. 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

  1. (2 points) Collect all the pairs ( i , j ) such that 0 i < n and 0 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.
  1. (2 points) Collect all the pairs ( i , j ) such that 0 i < n and 0 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.
  1. (2 points) Collect all the pairs ( i , j ) such that 0 i < n and i 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

  1. (3 points) Define a function named index that retrieves the i t h element of a given list. Do not perform any error checking.
  1. (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 sub-structures are lists. Do not perform any error checking.
  1. (3 points) Define a function named ntail that returns the n t h 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.
  1. (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 sub-lists. Do not perform any error checking.
  1. (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 sub-lists that need to be considered. Assume the existence of the predicate list?. Do not perform any error checking.
  1. (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 sub-lists. You must use the predefined predicate function even?. Do not perform any error checking.
  1. (3 points) Define a function named evenCount that returns the number of elements in a given list that are even. The list may have sub-lists that need to be considered. You must use the predefined predicates even? and list?. Do not perform any error checking.
  1. (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.
  1. (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.