计算机学科专业基础2010 真题档案

答案：

（1）算法基本设计思想
将数组视为前p个元素组成的子数组a和后n-p个元素组成的子数组b。通过三次逆置操作实现循环左移：先逆置a，再逆置b，最后逆置整个数组。即先将数组ab转换为a⁻¹b，再转换为a⁻¹b⁻¹，最终得到ba。

（2）算法描述（C语言）

void Reverse(int R[], int from, int to) {
    int i, temp;
    for (i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);       // 逆置前p个元素
    Reverse(R, p, n - 1);       // 逆置后n-p个元素
    Reverse(R, 0, n - 1);       // 逆置整个数组
}

（3）时间复杂度和空间复杂度
时间复杂度：O(n)，其中三次逆置操作总代价为O(p + (n-p) + n) = O(n)。
空间复杂度：O(1)，仅使用常数个临时变量。