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

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

线性搜索算法如下:设A的n个元素都不相同.r已在A中的概率为p（0≤p≤1),并且当x在A中时,x等于A的每

线性搜索算法如下:

设A的n个元素都不相同.r已在A中的概率为p(0≤p≤1),并且当x在A中时,x等于A的每一个元素的可能性相等.试分析算法的平均时间复杂度.

24题的循环右移方法，将这两个有序表归并成一个有序表，仍然存放于A[]的left~right位置。要求算法的空间复杂性为O(1)

如图2-3所示。图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。

(1)编写一个算法，从任一给定的位置(pr，p)开始，将指针p右移k个结点。如果p移出链表，则将p为0，并让pr停留在链表最右边的结点上。

(2)编写一个算法，从任一给定的位置(pr，p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。

求最优二叉搜索树算法的时间复杂度为O（n²)，下面给出一个求拟最优二叉搜索树的试探算法，

可将算法的时间复杂度降低到O(nlog₂n)，算法的思想是对于关键码序列(key_low，key_low+1，…，key_high)，轮流以key_k为根，k=low，low+1，…，h，求使得|W[low-1][k-1]-W[k][high]|达到最小的k，用key_k作为由该序列构成的拟最优二叉搜索树的根。然后对以keyu为界的左子序列和右子序列，分别施行同样的操作，建立根key_k的左子树和右子树，试编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog₂n)。

计数排序方法。该方法在声明元素时为每个元素增加一个计数域count，用于存放在已排好序的序列中该元素前面的元素数日，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个元素的序列，为确定所有元素的count值，最多需要进行n(n-1)/2次排序码比较。

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

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

A.O（logn）（以2为底）

B.O（1）

C.O（n）

D.O（n*n）

试利用循环队列编写求k阶斐波那契序列中前n+l项（f.，fi.….，f.)的算法。要求满足：fn≤max面fn+i>m

ax，其中max为某个约定的常数。(注意：本题所用循环队列的容世仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那奥序列中的最后k项。

二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。