习题2.2没有全部做，我读书的速度远远超过做习题的进度，没办法，时间有限，晚上的时间基本用来看书了，习题也都是在工作间隙做的，慢慢来了，前两章读完再总结下。回到2.3节，这一节在前几节介绍数值型符号数据的基础上引入了符号数据，将任意符号作为数据的能力非常有趣，并给出了一个符号求导的例子，实在是太漂亮了。
习题2.53，直接看结果：
>
(list
'
a
'
b
'
c)
(a b c)
>
(list (list
'
george))
((george))
>
(cdr
'
((x1 x2) (y1 y2)))
((y1 y2))
>
(cadr
'
((x1 x2) (y1 y2)))
(y1 y2)
>
(pair? (car
'
(a short list)))
#
f
>
(memq?
'
red
'
((red shoes) (blue socks)))
#
f
>
(memq?
'
red
'
(red shoes blue socks)) (red shoes blue socks)
习题2.54，equal?过程的定义，递归定义，很容易
(define (equal? a b) (cond ((
and
(
not
(pair? a)) (
not
(pair? b)) (eq? a b))
#
t)
((
and
(pair? a) (pair? b)) (
and
(equal? (car a) (car b)) (equal? (cdr a) (cdr b)))) (
else
(display
"
a and b are not equal
"
))))
注意，在DrScheme实现中,eq?可以用于比较数值，比如(eq? 1 1)也是返回真
习题2.55，表达式(car ''abracadabra)其实就是
(car (quote (quote abracadabra)))，也就是(car '(quote abracadabra))，显然将返回quote
习题2.56，求幂表达式的导数，学着书中的代码写，也很容易了，先写出constructor和selector：
(define (make
-
exponentiation base e) (cond ((
=
e 0)
1
) ((
=
e
1
) base) (
else
(list
'
** base e))))
(define (base x) (cadr x)) (define (exponent x) (caddr x)) (define (exponentiation? x) (
and
(pair? x) (eq? (car x)
'
**)))
用**表示幂运算，因此(make-exponentiation x 3)表示的就是x的3次方。
修改deriv过程，增加一个条件分支：
(define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (
if
(same
-
variable? exp var)
1
0)) ((sum? exp) (make
-
sum (deriv (addend exp) var) (deriv (augend exp) var))) ((product? exp) (make
-
sum (make
-
product (multiplier exp) (deriv (multiplicand exp) var)) (make
-
product (multiplicand exp) (deriv (multiplier exp) var)))) ((exponentiation? exp) (let ((n (exponent exp))) (make
-product (make-product n (make-exponentiation (base exp) (- n 1
))) (deriv (base exp) var)))) (
else
error
"
unknown expression type -- Deriv
"
exp)))
粗体的就是我们增加的部分，两次运用make-product做乘法。
测试下：
>
(deriv
'
(** x 3)
'
x) (
*
3
(
**
x
2
))
>
(deriv
'
(** (+ x 1) 5)
'
x) (
*
5
(
**
(
+
x
1
)
4
))
习题2.57，只要修改selector函数就够了，如果是多项的和或者积，那么被乘数和被加数也是列表，可以直接表示为符号表达式而不求值
(define (augend s) (let ((rest (cddr s))) (
if
(null? (cdr rest)) (car rest) (cons
'
+ rest))))
(define (multiplicand p) (let ((rest (cddr p))) (
if
(null? (cdr rest)) (car rest) (cons
'
* rest))))
习题2.58，分为a和b，a倒是很容易解答，修改下谓词、选择函数和构造函数就可以了，将运算符号放在列表中间，注意，题目已经提示，假设+和*的参数都是两个，因此
(a)题目：
(define (
=
number? x y) (
and
(number? x) (
=
x y))) (define (variable? x) (symbol? x)) (define (same
-
variable? v1 v2) (
and
(variable? v1) (variable? v2) (eq? v1 v2))) (define (sum? x) (let ((op (cadr x))) (
and
(symbol? op) (eq? op
'
+))))
(define (addend s) (car s)) (define (augend s) (caddr s)) (define (make
-
sum a1 a2) (cond ((
=
number? a1 0) a2) ((
=
number? a2 0) a1) ((
and
(number? a1) (number? a2)) (
+
a1 a2)) (
else
(list a1
'
+ a2))))
(define (product? x) (let ((op (cadr x))) (
and
(symbol? op) (eq? op
'
*))))
(define (multiplier x) (car x)) (define (multiplicand x) (caddr x)) (define (make
-
product a1 a2) (cond ((
or
(
=
number? a1 0) (
=
number? a2 0)) 0) ((
=
number? a1
1
) a2) ((
=
number? a2
1
) a1) ((
and
(number? a1) (number? a2)) (
*
a1 a2)) (
else
(list a1
'
* a2))))
测试下：
>
(deriv
'
(x + (3 * (x + (y + 2))))
'
x)
4
>
(deriv
'
(x + 3)
'
x)
1
>
(deriv
'
((2 * x) + 3)
'
x)
2
>
(deriv
'
((2 * x) + (3 * x))
'
x)
5
习题2.59，求集合的交集，遍历集合set1，如果(car set1)不在集合set2中，就将它加入set2，否则继续，当集合set1为空时返回set2。
(define (union
-
set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) ((element
-
of
-
set? (car set1) set2) set2) (
else
(union
-
set set1 (cons (car set1) set2)))))
习题2.60，需要修改的仅仅是adjoin-set：
(define (adjoin
-
set x set) (cons x set))
效率由原来的n变成常量。其他操作的效率与原来的一样。有重复元素的集合，比如成绩单、钱币等等。
习题2.61，关键点就是在于插入元素后要保持集合仍然是排序的，如果x小于(car set)，那么最小的就应该排在前面了，如果大于(car set)，那么将(car set)保留下来，继续往下找：
(define (adjoin
-
set x set) (cond ((null
?
set) (list x)) ((
=
x (car set)) set) ((
<
x (car set)) (cons x set)) (
else
(cons (car set) (adjoin
-
set x (cdr set))))))
习题2.62，与求交集类似：
(define (union
-
set set1 set2) (cond ((null
?
set1) set2) ((null
?
set2) set1) (
else
(let ((x1 (car set1)) (x2 (car set2))) (cond ((
=
x1 x2) (cons x1 (union
-
set (cdr set1) (cdr set2)))) ((
<
x1 x2) (cons x1 (union
-
set (cdr set1) set2))) ((
>
x1 x2) (cons x2 (union
-
set set1 (cdr set2)))))))))
测试下：
>
(define set1 (list
2
3
4
5
9
20
))
>
(define set2 (list
1
2
3
5
6
8
))
>
(union
-
set set1 set2) (
1
2
3
4
5
6
8
9
20
)
习题2.63，其实两个变换过程都可以看成是对树的遍历
a)通过测试可以得知，产生一样的结果，两者都是中序遍历二叉树，书中图的那些树结果都是(1 3 5 7 9 11)
b)对于tree->list-1过程来说，考虑append过程，并且每一步并没有改变搜索规模，而append的增长阶是O(n)，因此tree->list-1的增长阶应该是O(n2)，n的二次方
而对于tree-list-2过程，增长阶显然是O(n)
习题2.64，这题非常有趣，用一个数组构造一棵平衡的树，显然，方法就是将数组对半拆分，并分别对两个部分进行构造，这两个部分还可以拆分直到遇到数组元素（左右子树都是'())，中间元素作为entry。这个过程可以一直递归下去。这里采用的正是这种方式
a)解释如上，(1 3 5 7 9 11)将形成下列的二叉树：
5
/ \
1 9
\ / \
3 7 11
显然，列表的对半拆分，以5作为根节点，然后左列表是(1 3)，右列表是(7 9 11)，左列表拆分就以1为节点，右列表拆分以9为节点，其他两个为子树。
b)仍然是O(n)
习题2.65，很简单了，转过来转过去就是了：
(define (union-set-1 tree1 tree2) (list->tree (union-set (tree->list-2 tree1) (tree->list-2 tree2)))) (define (intersection-set-1 tree1 tree2) (list->tree (intersection-set (tree->list-2 tree1) (tree->list-2 tree2))))
习题2.66，与element-of-set?类似：
(define (lookup given-key set-of-records) (cond ((null? set-of-records) #f) ((= given-key (key (entry set-of-records))) (entry set-of-records)) ((
<
given-key
(key (entry set-of-records))) (lookup given-key (left-branch set-of-records))) ((
>
given-key (key (entry set-of-records))) (lookup given-key (right-branch set-of-records)))))
习题2.67，结果是(a d a b b c a) ，DrScheme字母符号是小写
习题2.68，使用到memq过程用于判断符号是否在列表中：
(define (encode-symbol symbol tree) (define (iter branch) (if (leaf? branch) '() (if (memq symbol (symbols (left-branch branch))) (cons 0 (iter (left-branch branch))) (cons 1 (iter (right-branch branch)))) )) (if (memq symbol (symbols tree)) (iter tree) (display "bad symbol -- UNKNOWN SYMBOL")))
习题2.69，因为make-leaf-set产生的已经排序的集合，因此从小到大两两合并即可：
(define (generate
-
huffman
-
tree pairs) (successive
-
merge (make
-
leaf
-
set pairs)))(define (successive-merge set)
(if (= 1 (length set))
(car set)
(successive-merge
(adjoin-set (make-code-tree (car set) (cadr set)) (cddr set)))))
习题2.70，利用generate-huffman-tree和encode过程得到消息，使用length测量下消息长度就知道多少位了：
(define roll
-
tree (generate
-
huffman
-
tree
'
((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1)))) (define message (encode
'
(Get a job Sha na na na na na na na na Get a job Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom) roll
-
tree))
>
(
length
message)
84
通过huffman编码后的位数是84位，如果采用定长编码，因为需要表示8个不同符号，因此需要log2(8)=3位二进制，总位数至少是36*3=108位，压缩比为22.22% 习题2.71，很显然，最频繁出现的符号肯定在根节点下来的子树，位数是1，而最不频繁的符号是n-1位
文章转自庄周梦蝶 ，原文发布时间2007-07-03
相关资源：sicp第二章练习题的解答
