2.5.2 真题
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2.5.2 真题
【2010年42 题】（13 分）设将n（n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移p(0 < p < n）个位置，即将R 中的数据由(Xx0, X1, . . ., Xn−1)变换为(Xp, Xp+1,. . ., Xn−1, X0, Xx1, . .,Xp−1)。要求： (1)给出算法的基本设计思想。(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。
<!-- page 48 -->
【2011年42题】（15分）—个长度为L（L≥1）的升序序列S，处在第「L/21个位置的数称为 S 的中位数。例如，若序列S1 = (11，13，15, 17，19)，则S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2= (2,4,6,8,20)，则S1 和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。(3)说明你
<!-- page 49 -->
【2013 年41 题】 （13 分）已知—个整数序列 A =(a0, a1，.， an−1)，其中 0 ≤ ai < n(0 ≤ i< n)。若存在 ap1 = ap2 =... = apm = x 且 m > n/2 (0 ≤ pk < n, 1 ≤ k ≤ m)，则称 x 为 A 的主元素。例如 A = (0, 5, 5, 3, 5, 7, 5, 5)，则 5 为主元素；又如 A = (0, 5, 5, 3, 5, 1,5, 7)，则 A 中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：（1）给出算法的基本设计思想。(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。(3）说明你所设计算法的时间复杂度和空间复杂度。
<!-- page 50 -->
【2016 年43题】 （13 分)已知由 n(n ≥ 2)个正整数构成的—个集合A= {ak | 0 ≤ k <n}，将其划分为两个不相交的子集 A1 和 A2，元素个数分别是n1 和 n2，A1 和 A2 中元素之和分别为 S1 和 S2。设计一个尽可能高效的划分算法，满足 |n1 - n2| 最小且 |S1 - S2| 最大。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(3)说明你所设计算法的平均时间复杂度和空间复杂度。
<!-- page 51 -->
【2018年41题】（13 分）给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1，2，3}中未出现的最小正整数是4。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。 X
<!-- page 52 -->
【2020年41题】（13 分）定义三元组(a，b，c)（a，b，c均为正数）的距离D=|a− b|+|b － c + |c － a|。给定3 个非空整数集合 S1、S2 和S3，按升序分别存储在3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a，b，c)(a∈S1，b∈S2，c∈S3) 中的最小距离。例如 S1 = {-1，0，9}，S2 = {-25， -10，10， 11}，S3 = {2，9,17，30，41}，则最小距离为2，相应的三元组为(9，10，9)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。
<!-- page 53 -->
【2025 年 41 题】(13 分)有两个长度均为 n 的一维整型数组 A[n]、res[n]，计算 A[i]与A[j](0≤i≤j≤n-1) 乘积的最大值，并将其保存到 res[i]中。若 A[] = {1, 4, -9, 6}，则得到 res[] ={6, 24, 81, 36}。现给定数组 A，请设计时间空间上尽可能高效的算法 CalMulMax，求 res 中各元素的值。函数原型为：void CalMulMax(int A[], int res[], int n)。(1)给出算法的基本思想。(4 分)(2)用C/C++描述算法关键之处给出注释。(7 分) (3)说明时间、空间复杂度。(2 分) 当计
<!-- page 54 -->
## 2.6 章节答案
## 2.6.1 习题
## \*习题2-1
(13 分)已知升序数组 A含有n 个整数，求是否存在值为x的元素，存在返回数组下标，不存在则返回-1。设计一个在时间上尽可能高效的算法实现该功能。例：A={1,2,3,7,8,11，15}，n = 7，x = 8，则返回数组下标为 4。 (1)给出算法的基本设计思想。 (2) 根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>枚举</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>折半查找</td><td rowspan=1 colspan=1>O(logn)</td><td rowspan=1 colspan=1>O(1)</td><td rowspan=1 colspan=1>13</td></tr></table>
## 【解法1】暴力解：枚举
(1)遍历一趟数组，依次判断每个元素是否为x，是则返回数组下标，如果遍历完还没找到则返回-1。（2)伪代码如下：
int ans(int A[], int n, int x)
{
for (int i=0; i<n; i++)
if (A[i]==x) return i;
return -1;
}
int B_Search(int A[], int L, int R, int x)
{
while (L <= R)
{
int mid = L + (R - L) / 2;
if (x == A[mid]) return mid;
if (x < A[mid]) R = mid - 1;
else L = mid + 1;
}
return -1;
}
//快速排序函数
void Qsort(int A[], int L, int R)
{
if (L >= R) return; //区间≤1,返回
int i = L, j = R;
int pivot = A[L]; //选首元素为基准
//不断交换左边比pivot 大的数和右边比 pivot 小的数
while (i < j) {
while (i < j && A[j] >= pivot) j--; // 从右找第—个 <pivot 的数
while (i < j && A[i] <= pivot) i++; // 从左找第—个 >pivot 的数
if (i < j) swap(A[i], A[j]);
}
//将基准值A[L] 与A[i]交换
swap(A[L], A[i]);
//递归处理左右两个子区间
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
int ans(int A[], int n, int B[], int m)
{
int C[m + n];
for (int i = 0; i < n; i++)
C[i] = A[i];
for (int i = 0; i < m; i++)
C[n + i] = B[i];
Qsort(C, 0, m + n - 1);
输出数组C
}
void Merge(int A[], int n, int B[], int m)
{
int C[m + n];
int i = 0, j = 0, k = 0;
//比较并合并
while (i < n && j < m)
{
if (A[i] < B[j]) C[k++] = A[i++];
else C[k++] = B[j++];
}
// 复制剩余元素
while (i < n) C[k++] = A[i++];
while (j < m) C[k++] = B[j++];
输出数组C
}
int ans(int A[], int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (A[i] == A[j]) return A[i];
return -1;
}
// 快速排序函数
void Qsort(int A[], int L, int R)
{
if (L >= R) return; // 区间≤1，返回
int i = L, j = R;
int pivot = A[L]; // 选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[j] >= pivot) j--; // 从右找第一个 <pivot 的数
while (i < j && A[i] <= pivot) i++; // 从左找第一个 >pivot 的数
if (i < j) swap(A[i], A[j]);
}
// 将基准值 A[L] 与 A[i] 交换
swap(A[L], A[i]);
// 递归处理左右两个子区间
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
int ans(int A[], int n)
{
Qsort(A, 0, n - 1);
for (int i = 1; i < n; i++)
if (A[i] == A[i - 1]) return A[i];
return -1;
}
int ans(int A[], int n)
{
int count[n] = {0};
for (int i = 0; i < n; i++)
{
if (count[A[i]] > 0) return A[i];
count[A[i]]++;
}
return -1;
}