作业 9
第 9 课作业：围绕 set-car!/set-cdr!、SICP 3.13-3.27 以及向量相关编程的练习题。
模板
在终端输入下面的命令，把模板文件复制到当前目录（注意末尾的句点）：
cp ~cs61as/autograder/templates/hw9.scm .也可以点击此处下载模板。
练习 1
假设已有如下定义：
(define x (cons 1 3))
(define y 2)一位 CS 61AS 同学想把 x 的值改成一个 car 为 1、cdr 为 2 的序对，他输入的是 (set! (cdr x) y) 而不是 (set-cdr! x y)，结果报错了。请解释原因。
练习 2
a) 在下面的空格中填入两次 set-cdr! 调用的参数，使 list1 和 list2 产生所示的变化。不要创建任何新序对，只重新安排指向已有序对的指针。
> (define list1 (list (list 'a) 'b))
list1
> (define list2 (list (list 'x) 'y))
list2
> (set-cdr! ________ ________)
okay
> (set-cdr! ________ ________)
okay
> list1
((a x b) b)
> list2
((x b) y)b) 填好上面的空格、并对 list1 和 list2 产生指定效果之后，画一个盒式指针图，说明求值表达式 (set-car! (cdr list1) (cadr list2)) 的效果。
练习 3
完成 Abelson 与 Sussman 教材中的练习 3.13 和 3.14。
练习 4
完成 Abelson 与 Sussman 教材中的练习 3.16、3.17、3.21、3.25 和 3.27。
笔记
注意：练习 3.27 不需要画环境图，请用 trace 过程给出要求的解释。表操作 lookup 和 insert! 视为原语，即不要跟踪它们调用的过程；同时假设这些过程是常数时间运行的。我们关心的是 memo-fib 被调用的次数。
练习 5
编写 vector-append：接受两个向量作为参数，返回一个包含两个参数全部元素的新向量，功能类似于列表的 append。
警告
不要把列表用作中间值（即任何时候都不要把向量转换成列表）。
练习 6
编写 vector-filter：接受一个谓词函数和一个向量作为参数，返回一个新向量，只保留参数向量中使谓词返回 true 的那些元素。新向量的大小应恰好容纳选中的元素。将你的程序与下面这个版本的运行时间进行比较：
(define (vector-filter pred vec)
(list->vector (filter pred (vector->list vec))))警告
不要把列表用作中间值（即任何时候都不要把向量转换成列表）。
练习 7
给向量排序：
a) 编写 bubble-sort!：接受一个数字向量，把它们重排为递增顺序。（你需要修改传入的向量，不要创建新向量。）请按下面的算法来定义：1. 从头到尾遍历数组，每次看相邻的两个元素，从第 0 和第 1 个元素开始。如果前一个元素比后一个元素大，就交换它们。然后看下一对相邻元素（先 0 和 1，再 1 和 2，依此类推）。2. 对除最后一个元素（它现在是最大的元素）以外的所有元素递归地执行 bubble-sort。3. 当只剩一个元素要排序时，停止。
b) 证明这个算法确实能完成向量排序。提示：证明第 2 步括号中的论断。
c) 这个算法运行时间的增长阶是多少？
警告
不要把列表用作中间值（即任何时候都不要把向量转换成列表）。
选做练习 8（面向高手）
想做就做，不计分。
Abelson 与 Sussman 教材练习 3.19 和 3.23。
练习 3.19 特别难，能做出来的话值得为自己点赞。你需要翻一翻本节中可能跳过的其他练习。练习 3.23 稍容易一些，但要注意 运行时间的要求。
选做练习 9（面向高手）
想做就做，不计分。
编写过程 cxr-name。它的参数是由 car 和 cdr 组合而成的函数，它应返回该函数对应的名称：
> (cxr-name (lambda (x) (cadr (cddar (cadar x)))))
CADDDAADAR提交作业！
提交方法请参阅这份指南，其中涵盖基本的终端命令和作业提交流程。
提交过程中如有任何困难，别犹豫，尽管问助教！