【正确答案】顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。

【正确答案】算法实现如下：
void SearchExchangeInsert(ElemType a[], ElemType x)
//a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序
{
low=0;
high=n-1; //low和high指向线性表下界和上界的下标
while(low＜=high){
mid=(low+high)/2; //找中间位置
if(a[mid]==x)break; //找到x,退出while循环
else if(a[mid]＜x) low=mid+1; //到中点mid的右半去查
else high=mid-1; //到中点mid的左部去查
}
if(a[mid]==x && mid! =n) //若最后一个元素与x相等，则不存在与其后继交换的操作
{
t=a[mid];
a[mid]=a[mid+1];
a[mid+1]=t;
} //数值x与其后继元素位置交换
if(low＞high) //查找失败，插入数据元素x
V{
for(i=n-1;i＞high;i--)
a[i+1]=a[i]; //后移元素
a[i+1]=x; //插入x
} //结束插入
} //结束本算法

【正确答案】折半的时间复杂度为O(logn)，如果不存在x的情况下，在线性表中插入元素的时候，时间复杂度取决于x插入的位置，最坏情况下为O(n)。算法实现过程中使用的辅助空间为常量，空间复杂度为O(1)。