厦门大学《       ＿数据结构＿    》课程期末试卷
        信息科学与技术 学院 计算机科学 系 2004 年级＿＿＿专业
            主考教师：＿＿＿＿试卷类型： （Ａ卷/B 卷）

一、试设计算法在 O(n)时间内将数组 A[1..n] 划分为左右两个部分， 使得左边的所有元素奇数，
右边的所有元素均为偶数，要求所使用的辅助存储空间大小为     O(1)。
解：该题算法的主要思路如下：
（1）设置两个指针 i 和 j ，其中 i=1，j=n。
（2）当 i<j 时作如下循环：
     i 不断自加从左往右找到第一个偶数
     j 不断自减从右往左找到第一个奇数
     A[i] 与 A[j] 交换
（3）算法结束
Adjust(int A[1..n])
{
  int i=1, j=n;
  while (i<j ){
     while (A[i] % 2 != 0 && i<=n) i++;
     while (A[i] % 2 = =0 && j>=1) j--;
     if (i>n || j<1) break;
     i ...