2-5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？

插入：一个有128个位置可以插入，平均移动元素个数为
n=(127+126+125+...+2+1+0)/128=(127+0)*128/2/128=63.5个
删除:一共127个元素可以删除，平均移动元素个数为
n=(126+125+...+2+1+0)/127=63个

2-6 若矩阵A(m×n)中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置(若鞍点存在时)，并分析该函数的时间复杂度。

如果写成 z=A[x][y] 那么就可以在空间坐标中，画出这些点，并用光滑的曲面连接这些点，就可以得到一个曲面。比较容易想像鞍点的样子。同时这个鞍点只能有一个，这和连续曲面有所不同。
感觉没有什么特别的办法，只能一行一行的扫描，然扫描这些行最小值的列号。用s[i]来存储。

int saddle(int A[][],const int m,const int n){
  int *s=new int[m];        //s[i]用来存储行最小值的列号
  int *c=new int[n];        //c[j]用来存储列最大值的行号
  int i, j,k;
  for (i=0;i < m;i++;){
     s[i]=0;                 //用来存j
     for (j=1;j < n;j++)          // 扫描各行，将最小值的j存入s[i]
         if (A[i][j] < A[i][s[i]]) s[i]=j;
  }
  for (j=0;j < n;j++) c[j]=-1;  //-1标记没有访问过
  for (i=0;i < m;i++){        //循s[i]
     tmp=0;
     if (c[s[i]] == -1){
        for (k=0;k < m;k++)      //扫描s[i]列,找出最大的行号
             if (A[k][s[i]] > A[tmp][s[i]])  tmp=k;
        c[s[i]]=tmp;
     }
     if (c[s[i]]==i){                //扫描了s[i]列如果A[i][s[i]]是鞍点
          cout << "The saddle point is :(" << i << "," << s[i] << ")" << endl;
         return 1;            //找到鞍点
     }
  }
  return 0;                   //未找到鞍点
}

当m远小于n时，这段程序的执行效率略高于答案。
算法的基础是考虑，首先找出各行的最小列号。然后，我们要比较的列，只有这几个出现的列号，而不需寻找所有的列（答案就搜索了所有列）。同时会出现不同行的最小列号有可能相等，用c[j]数组去标记该列有没有被查找过,如果查过就存入最大行号。答案似乎没有认识到鞍点只有一个

该算法的总时间复杂度还是O(m×n)

2-7 设有一个二维数组A[m][n]，假设A[0][0]存放在位置644（十进制，后同），A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？

如果是行优先的话，那么数组的存储方式一定是
A[0][0] A[0][1] A[0][2]...A[1][0]A[1][1]A[1][2]...A[2][0]A[2][1]...
所以loc(2,2)-loc(0,0)=2*m+2 m=15
A[3][3]=3*15+3+644=692
列优先与行优先的情况时一样的。

2-8 计算多项式Pn(x)=a0x^n+a1x^(n-1)+a2x^(n-2)+...+a(n-1)x+an的值。可以用递归的方法求解Pn(x)=x*P(n-1)(x)+an.试写出这个递归函数。

系数存储在double coef[n+1]中，不另作声明

double poly(int n,double x){
    if (n == 0) return coef[n];
    else return x*poly(n-1,x)+coef[n];
}