在长度为n的顺序表中的第i个位置上插入一个元素，其算法时间复杂度为（）

A.n-i

B.i

C.n-i+1

D.n-i-1

对于顺序存储的线性表，其算法的时间复杂度为Q（1)的运算应是（)。

A、将n个元素从小到大排序

B、从线性表中删除第i个元素(1≤i≤n)

C、查找第i个元素(1≤i≤n)

D、在第i个元素(1≤i≤n)后插人一个新元素

设有一个长度为n的一维数组A[n]=（a0,a1，…，an-1)，请编写一个算法，将该数组中的所有元素左移p个位置，要求算法的时间复杂度为O（n)，空间复杂性为O（1).

在一个顺序表的表尾插入一个元素的时间复杂度为（)。

A.O(n)

B.O(1)

C.O(n*m)

D.Olog2n)

试编写一个算法，将元素序列（x1，x2，…，xn)循环右移p个位置，0≤p≤n。要求该算法的时间复杂度为O（n)而空间复杂度为O（1)。

若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插人一个数据元素，i的合法值应该是（)。

A、i>0

B、1≤i≤n

C、0≤i≤n-1

D、0≤i≤n

利用C的库函数stren,trepy和strcat写一个算法将串T插入到S的第i个位置上。若i大于s的长度，则插入不执行。

设在有序顺序表中搜索x的过程为：首先用x与表中的第4i（i=0，1，…)个元素做比较，如果相等，则搜索

成功;否则确定下一步搜索的区间为4(i-1)+1到4i-1.然后在此区间内与第4i-2个元素作比较，若相等则搜索成功，否则继续与第4i-3或4i-1个元索进行比较，直到搜索成功。

(1)给出实现算法。

(2)试面出当表长n=16时的判定树，并推导此搜索方法的平均搜索长度(考虑搜索元素等概率和n%4=0的情况)。

利用C的库函数strlen,strcpy和streat写一个算法void StrInsert（char *S,char *T,int i)，将串T插入到S的第i个位置上。若i大于S的长度，则插入不执行。

编写一个递归算法，在一棵有n个结点的随机建立起来的二叉搜索树上搜索第k（1≤k≤n)小的元素，并返

回指向该结点的指针。要求算法的平均时间复杂度为O(log2n)。二叉搜索树的每个结点中除data、ieftChild、rightChild等数据成员外、增加一个count成员，保存以该结点为根的子树上的结点个数。