[Back]

2.3 符号数据

2.53

(list `a `b `c) ;(a b c)
(list (list `george)) ;((george))
(cdr `((x1 x2) (y1 y2))) ;((y1 y2))
(car (cdr `((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

(define (equal? a b)
    (cond ((and (not (pair? a)) (not (pair? b))) (eq? a b))
          ((or (not (pair? a)) (not (pair? b))) #f)
          (else (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))))

2.55

翻译成本质其实是

(car (quote (` abracadabra)))

这当然是`了

2.56

(define (exp? x)
    (and (pair? x) (eq? (car x) `**)))
(define (base x) (car (cdr x)))
(define (exponent x) (car (cdr (cdr x))))
(define (make-exp a1 a2)
    (cond ((=number? a2 1) a1)
          ((=number? a2 0) 1)
          ((and (number? a1) (number? a2)) (exp a1 a2))
          (else (list `** a1 a2))))
(define (deriv expr var)
    (cond ((number? expr) 0)
          ((variable? expr) (if (same-variable? expr var) 1 0))
          ((sum? expr)
            (make-sum (deriv (addend expr) var)
                    (deriv (augend expr) var)))
          ((product? expr)
            (make-sum (make-product (multiplier expr) (deriv (multiplicand expr) var))
                      (make-product (multiplicand expr) (deriv (multiplier expr) var))))
          ((exp? expr)
            (make-product (exponent expr)
                    (make-product (make-exp (base expr) (make-sum (exponent expr) (- 1)))
                                  (deriv (base expr) var))))
          (else 
            (display "unknown expression type -- DERIV" exp))))

2.57

(define (augend x) 
    (if (null? (cdr (cdr (cdr x)))) 
        (car (cdr (cdr x))) 
        (cons `+ (cdr (cdr x)))))
(define (multiplicand p) 
    (if (null? (cdr (cdr (cdr p)))) 
        (car (cdr (cdr p))) 
        (cons `* (cdr (cdr p)))))

2.58

; A)
(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 (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))))
(define (sum? exp)
    (and (pair? exp) (eq? (car (cdr exp)) `+)))
(define (addend x) (car x))
(define (augend x)
    (car (cdr (cdr x))))
(define (product? exp)
    (and (pair? exp) (eq? (car (cdr exp)) `*)))
(define (multiplier p) (car p))
(define (multiplicand p)
    (car (cdr (cdr p))))
; B)
; 失败的波兰表达式
(define (poland-expr expr)
    (cond ((null? expr) `())
          (not (pair? expr) expr)
          ((pair? (car expr)) (list (car (cdr expr)) (car expr) (poland-expr (car (cdr (cdr expr))))))
          (else 
            (poland-expr (cons (list (car (cdr expr)) (car expr) (car (cdr (cdr expr))))
                            (cdr (cdr (cdr expr))))))))

; 详见二义性

2.59

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((element-of-set? (car set1) set2)
          (union-set (cdr set1) set2))
          (else (cons (car set1)
                    (union-set (cdr set1) set2)))))

2.60

(define (adjoin-set x set)
	(cons x set))

只需修改adjoin即可,这个时间效率是O(size(n)*size(m))的,随着插入元素个数的增多,交并效率会变慢,但是查询效率和插入效率会不变甚至变快,适合于大量操作和查询的场合,事实上,还可以写一个number-of-element的函数

(define (number-of-element x set)
    (cond ((null? set) 0)
          ((equal? x (car set)) (+ 1 (number-of-element x (cdr set))))
          (else (number-of-element x (cdr set)))))

2.61

(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))))))

The function here has the same format like (element-of-set?), it joins the element when search it, just like optimize the search function, the complexity of this is

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)))
                          (else (cons x2 (union-set set1 (cdr set2)))))))))

2.63

A) 这两种方法都对树进行了前序遍历,因此他们的结果一定是一样的。

B) 第一种方法使用了append来合并子树,这个复杂度是 的,因此它的复杂度大致是 ,而第二种直接使用了cons,复杂度应该为

2.64

由于传入的参数就是一张有序表,因此我们对它严格二分就可以构建出平衡的二叉搜索树,考虑一个序对二分,如果序对是奇数个,那么中间的数据可以作为根节点,而左右子树各拥有(n-1)/2个数据,而如果是偶数个,我们可以给左子树(n-1)/2个数据,而将剩余数据根节点和右子树,这样也是大致平衡的,递归的执行这个过程,直到只剩下0个的长度就返回。

其复杂度大致是 的。(实际上,要想构建完整的二叉平衡树,必须要遍历到完整的列表,所以复杂度不会小于

2.65

(define (intersection-tree tree1 tree2)
    (let ((set1 (tree->list tree1))
          (set2 (tree->list tree2)))
        (list->tree (intersection-set set1 set2))))
(define (union-tree tree1 tree2)
    (let ((set1 (tree->list tree1))
          (set2 (tree->list tree2)))
        (list->tree (union-set set1 set2))))

2.66

(define (look-up given-key set-of-records)
    (cond ((null? set-of-records) false)
          ((= given-key (entry set-of-records)) (entry-set-of-records))
          ((< given-key (entry-set-of-records)) (look-up given-key (left-branch set-of-records)))
          (else (look-up given-key (right-branch set-of-records)))))

2.67

照着打了一遍 答案是 (A D A B B C A)

2.68

(define (encode-symbol sym tree)
    (if (leaf? tree) `()
        (let ((left-symbol (symbols (left-branch tree)))
              (right-symbol (symbols (right-branch tree))))
            (cond ((element-of-set? sym left-symbol) (cons 0 (encode-symbol sym (left-branch tree))))
                  ((element-of-set? sym right-symbol) (cons 1 (encode-symbol sym (right-branch tree))))
                  (else (display "Not in this tree" sym))))))

2.69

(define (successive-merge set)
    (if (= (length set) 1)
        (car set)
        (let ((min-pair (car set))
              (min2-pair (car (cdr set))))
            (successive-merge (adjoin-set (make-code-tree min-pair min2-pair) (cdr (cdr set)))))))

2.70

(define rock-words-tree (generate-huffman-tree `((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1))))
    (length (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) rock-words-tree))

使用了84味编码,如果使用定长编码,需要108位

2.71

最频繁的只用了一位,而最不频繁的则需要用n-1位,这是极度不平衡的Huffman树(也是最坏情况)

2.72

对于最频繁的,由于他只编码了一位,消耗的仅仅是遍历一遍集合的代价,因此是 的,而对于最不频繁的,在每一位的遍历代价分别是n n-1 n-2 ……,执行次数是n-1,因此复杂度是 的。

Huffman树基于贪心的方法构建,由于面向的是实际的编码序列,因此它的实际工作期望也是介于这两个复杂度之间的。

对于相对平衡的Huffman树,它的复杂度应在 左右。