2.1-1
(ａ) 31 - 【41】 - 59 - 26 - 41 - 58
(ｂ) 31 - 41 - 【59】 - 26 - 41 - 58
(ｃ) 31 - 41 - 59 - 【26】 - 41 - 58 ( 31、41、59 右移一个位置，在原 31 的位置插入 26)
(ｄ) 26 - 31 - 41 - 59 - 【41】 - 58 ( 59 右移一个位置，在原 59 的位置插入 41)
(ｅ) 26 - 31 - 41 - 41 - 59 - 【58】 ( 59 右移一个位置，在原 59 的位置插入 58)
(ｆ) 26 - 31 - 41 - 41 - 58 - 59
“【】” 中的数字被临时存储在 key 中。
2.1-2
INSERTION-SORT(A) for j = 2 to A.length key = A[j] i = j - 1
while i > 0 and A[i] < key A[i+1] = A[i] i = i - 1 A[i+1] = key
2.1-3
// We use loop invariants to help us understand why an algorithm is correct.
尝试证明:
初始化：证明第一次迭代之前循环不变式成立。当输入规模为 1 （数组长度），数组仅由单个元素 A[1] 组成，经过一次相等判断后，输出要么取 i = 1（这个数恰好等于 v），要么取 v = NIL （这个数不为 v ），循环不变式成立。
保持：证明每次迭代保持循环不变式。假设输入规模为 n 时循环不变式成立，即要么在数组 n 中取到了下标 i （A[i] == v），要么就没有找到（ v = NIL）。那么再增加一个元素，令规模为 n+1 ，容易知道，规模 n 既然成立（可以得到一个有用的性质、结论），规模 n+1 至多增加一次相等判断（也就是在原数组中没取到 i 的情况），最终也能获得有用的结论。故迭代（这里指规模+1）将保持循环不变式。
终止：最后研究循环终止时发生了什么。导致迭代终止的条件是 i > A.length=n 或者取到了下标 i ，倘若是前者那么令 v = NIL，这个时候已经得到了有用的结论，所以算法正确。
网上找的：
初始化： i=1，子数组为 A[1..i]，只有一个元素 A[1],如果 v=A[1]就返回 1,否则返回 NIL， 算法显然是正确的。 保持：若算法对数组 A[1..i]正确，则在数组增加一个元素 A[i+1]时，只需要多作一次比较， 因此显然对 A[1..i+1]也正确。 终止：算法如果在非最坏情况下定能返回一个值此时查找成功，如果 n 次查找（遍历了所有 的数）都没有成功，则返回 NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明 查找成功并给出下标，要么说明无此值。因此算法正确。
2.1-4
输入：长度均为 n 的数组 A、B，分别存储一个 n 位的二进制整数。（最高位必须是 1，其它位为 0 或者 1）
输出：长度为 n+1 的数组 C，存储 A 与 B 存储的二进制整数之和。
伪代码：
ADD(A, B, C) for k = 1 to A.length C[k] = A[k] + B[k] if C[k] >= 2 C[k+1] = C[k+1] + 1 C[k] = C[k] - 2
这个算法的正确性也可以用循环不变式理解。