习题

2.1 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 3 for i = 1 to A.length if A[i]=v return i v = NIL A[1..i-1]表示位置1到i-1的元素都不等于v **初始化：**当i=1时，没有元素，自然也没有元素等于v **保持：**每次循环会将不等于v的元素加入到A[i..i-1]中 **终止：**如果遇到A[i]=v,循环终止。如果最后i=A.length时，A[1..i-1]中元素都不等于v也就是数组中所有元素都不等于v。 4 **输入：**两个二进制序列 $$A=<a_1,a_2,\cdots,a_n>,B=<b_1,b_2,\cdots,b_n>$$ **输出：**二进制序列 $$C=<c_1,c_2,\cdots,c_n,c_n+1>，C=A+B$$ carry = 0 for i = n downto 1 C[i] = A[i]^B[i]^carry if(A[i]+B[i]+carry>1) carry = 1 else carry = 0 c[1] = carry 2.2 1 $\theta(n^3)$...