問題解答

問2.59

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(define (adjoint-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

(define (union-set set1 set2)
  (if (null? set1)
      set2
      (adjoint-set (car set1) (union-set (cdr set1) set2))))

(define s1 (list 1 2 3 4))
(define s2 (list 3 4 5 6))

(union-set s1 s2)

問2.60
adjoin-set を変更するだけで対応できる

(define (adjoint-set x set)
  (cons x set))

重複しているアイテムを全て処理しなければいけないので CPU 時間もメモリも負荷は増える。
ただ、オーダー的には一緒。

本文

順序づけられたリストとしての集合

集合の要素をソートした状態で格納した場合の計算量への影響

問2.61,2.62 は手の運動なのでパス。

二進木としての集合、集合と情報検索
このあたりは一通り把握している内容なので問題の中身はきちんと確認しつつ飛ばす。