SICP 习题参考答案 2.3

win_hate

1. 
   
2. (define (union-set set1 set2)
   
3.   (cond ((null? set1) set2)
   
4.         ((null? set2) set1)
   
5.         (else (let ((x1 (car set1)) (x2 (car set2))
   
6.                     (s1 (cdr set1)) (s2 (cdr set2)))
   
7.                 (cond ((= x1 x2) (cons x1 (union-set s1 s2)))
   
8.                       ((> x1 x2) (cons x2 (union-set set1 s2)))
   
9.                       (else (cons x1 (union-set s1 set2))))))))
   

复制代码

win_hate

Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

win_hate

• a. 一样的，都是中序遍历一棵树；
• b. 第二个写法的复杂度为 O(n)，本质上是通过  cons 把一棵树的 n 个节点串成一个表。第一个写法在递归时使用了 append，所以会慢得多。cons 是个 O(1) 的操作，而 (append  L1 L2) 的复杂度为 O( |L1| ).
  
  设第一个写法的复杂度为 T(n)，有 T(n)=2 T(n/2) + n/2，可以算出，其复杂度为 O(n log n).
  

win_hate

Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

Exercise 2.64.  The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).

b. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?

[ 本帖最后由 win_hate 于 2008-11-6 22:41 编辑 ]

win_hate

a. 递归，先构造出左子树，提取当前节点，再构造出右子树.

对指定数据产生的树为 (5 (1 () 3) (9 7 11))

b. 把表遍历两次， O(n).

[ 本帖最后由 win_hate 于 2008-11-6 22:42 编辑 ]

win_hate

Exercise 2.65.  Use the results of exercises 2.63 and  2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

win_hate

tree->list-2 是 O(n) 的, list->tree 也是 O(n) 的， union-set 和 intersection-set 都是 O(n) 的。所以只要

• tree->list-2 变为排序表
• union-set, intersection-set
• list->tree 变为树
  

win_hate

Exercise 2.66.  Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

win_hate

<wait>

这题没有什么意思，以后再做。

win_hate

Exercise 2.67.  Define an encoding tree and a sample message:

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Use the decode procedure to decode the message, and give the result.


======================================================

参考资料

Huffman never tried to patent an invention from his work. Instead, he concentrated his efforts on education. In Huffman's own words, "My products are my students."

• Huffman 的生平见 [David A. Huffman]
  
• Huffman 编码见 [Huffman coding]
  

David A Huffman

1925 - 1999

美国

信息论、编码专家

[ 本帖最后由 win_hate 于 2008-11-14 21:18 编辑 ]