投砾石应采取哪些措施防止卡砾石？

答案：B

参考答案：利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移(即k-1);若当前元素是红色砾石，分i>=j(这时尚没有白色砾石)和i　　为方便处理，将三种砾石的颜色用整数1、2和3表示。
　　[算法描述]：
　　void QkSort(rectype r[],int n) {
　　// r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储，
　　//本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。
　　int i=1,j=1,k=n,temp;
　　while (k!=j){
　　while (r[k].key==3) k--;// 当前元素是兰色砾石，指针左移
　　if (r[k].key==1) // 当前元素是红色砾石
　　if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;}
　　//左侧只有红色砾石，交换r[k]和r[i]
　　else {temp=r[j];r[j]=r[i];r[i]=temp; j++;
　　//左侧已有红色和白色砾石，先交换白色砾石到位
　　temp=r[k];r[k]=r[i];r[i]=temp; i++;
　　//白色砾石(i所指)和待定砾石(j所指)
　　} //再交换r[k]和r[i]，使红色砾石入位。
　　if (r[k].key==2)
　　if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;}
　　// 左侧已有白色砾石，交换r[k]和r[j]
　　else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;}
　　//i、j分别指向红、白色砾石的后一位置
　　}//while
　　if (r[k]==2) j++; /* 处理最后一粒砾石
　　else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; }
　　//最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1
　　}//结束QkSor算法
　　[算法讨论]若将j(上面指向白色)看作工作指针，将r[1..j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。从j=1开始查看，若r[j]为白色，则j=j+1;若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1;若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。
　　算法片段如下：
　　int i=1,j=1,k=n;
　　while(j<=k)
　　if (r[j]==1) //当前元素是红色
　　{temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++; }
　　else if (r[j]==2) j++; //当前元素是白色
　　else //(r[j]==3 当前元素是兰色
　　{temp=r[j]; r[j]=r[k]; r[k]=temp; k--; }
　　对比两种算法，可以看出，正确选择变量(指针)的重要性。

参考答案：C