爱迪国际C++章节测试-基础算法

*
您的姓名：
1.
填空题
完善程序*
(大整数开方) 输入一个正整数n（1≤n≤10100），试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
[ ① ] +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
[ ② ];
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= [ ③ ] ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=([ ④ ])*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
[ ⑤ ];
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
int i;
if([ ⑥ ])
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]-[ ⑦ ];
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over([ ⑧ ]))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
①：②：③：④：⑤：⑥：⑦：⑧：
*
2.
单选题
（）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。
A. 动态规划
B. 贪心
C. 分治
D. 搜索
*
3.
填空题
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
cin>>a[i];
left = 1;
right = n;
do {
middle = (left + right) / 2;
if (f <= a[middle])
right = middle;
else
left = middle + 1;
} while (left < right);
cout<<left<<endl;
return 0;
}

输入：
12 17
2 4 6 9 11 15 17 18 19 20 21 25
输出：__________________
4.
填空题
完善程序：*
(中位数 median) 给定n(n 为奇数且小于1000)个整数，整数的范围在0-m(0<m<2的31次方)之间，请使用二分法求这n 个整数的中位数。所谓中位数，是指将这n 个数排序之后，排在正中间的数。
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, lbound, rbound, mid, m, count;
int x[MAXN];
int main()
{
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> x[i];
lbound = 0;
rbound = m;
while (①)
{
mid = (lbound + rbound) / 2;
②;
for (i = 0; i < n; i++)
if (③)
④;
if (count > n / 2)
lbound = mid + 1;
else
⑤;
cout << mid << " " << lbound << " " << rbound << " " << count << endl;
}
cout << rbound << endl;
return (0);
}
①：②：③：④：⑤：
*
5.
单选题
给定含有n 个不同的数的数组L=<x1,x2,...,xn>。如果L中存在Xi（1＜i＜n)使得x1<x2<...<xi−1<xi>xi+1>...>xn则称L是单峰的，并称xi是L的“峰顶”。现在已知L是单峰的,请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。
a.Search(k+1, n)
b.Search(1, k-1)
c.return L[k]
Search(1, n)
1. k←⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then __________
6. else __________

正确的填空顺序是( )。

A. c,a,b
B. c,b,a
C. a,b,c
D. b,a,c

A、c,a,b
B、c,b,a
C、a,b,c
D、b,a,c
6.
填空题
完善程序：*
（郊游活动）有n 名同学参加学校组织的郊游活动，已知学校给这n 名同学 的郊游总经费为A 元，与此同时第i 位同学自己携带了Mi元。
为了方便郊 游，活动地点提供B(≥n)辆自行车供人租用，租用第j辆自行车的价格为Cj元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管 理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间[l,r] ，我们取中间点mid 并判断租用到自行车的人数能否达到mid。判断的过程是利用贪心算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
int count = 0, i, j;
i = ①;
j = 1;
while (i <= n) {
if(②)
count += C[j] - M[i];
i++;
j++;
}
return ③;
}
void sort(int a[], int l, int r) {
int i = l, j = r, x = a[(l + r) / 2], y;
while (i <= j) {
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++)
cin >> M[i];
for (i = 1; i <= B; i++)
cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
l = 0;
r = n;
while (l <= r) {
mid = (l + r) / 2;
if(④){
ans = mid;
l = mid + 1;
}else
r = ⑤;
}
cout << ans << endl;
return 0;
}
①：②：②：②：②：
7.
填空题
*
#include<iostream>
using namespace std;
int x, p, m, i, result;
int main(){
cin >> x >> p >> m;
result = ①;
while (②){
if (p % 2 == 1)
result = ③;
p /= 2;
x = ④;
}
cout << ⑤ << endl;
return 0;
}
①：②：③：④：⑤：
8.
填空题
完善程序：*
（切割绳子）有n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m 条长度相同的绳段，求绳段的最大长度是多少。
输入：第一行是一个不超过 10的六次方的正整数n，第二行是n 个不超过0的六次方的正整数，表示每条绳子的长度，第三行是一个不超过10的八次方的正整数m。 输出：绳段的最大长度，若无法切割，输出Failed。
#include<iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main()
{
cin >> n;
count = 0;
for (i = 0; i < n; i++)
{
cin >> len[i];
①;
}
cin >> m;
if (②)
{
cout << "Failed" << endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while (③)
{
mid = ④;
count = 0;
for (i = 0; i < n; i++)
⑤;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
①：②：③：④：⑤：
*
9.
单选题
设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）。
A.7
B.10
C.6
D.8
*
10.
选择题

1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 5000;
6 int n, m;
7 struct segment { int a, b; } A[MAXN];
8
9 void sort() // 排序
10 {
11 for (int i = 0; i < n; i++)
12 for (int j = 1; j < n; j++)
13 if (①)
14 {
15 segment t = A[j];
16 ②
17 }
18 }
19
20 int main()
21 {
22 cin >> n >> m;
23 for (int i = 0; i < n; i++)
24 cin >> A[i].a >> A[i]・b;
25 sort();
26 int p = 1;
27 for (int i = 1; i < n; i++)
28 if (③)
29 A[p++] = A[i];
30 n = p;
31 int ans =0, r = 0;
32 int q = 0;
33 while (r < m)
34 {
35 while (④)
36 q++;
37 ⑤;
38 ans++;
39 }
40 cout << ans << endl;
41 return 0;
42 }

①处应填（ ）
A、A[j].b＞A[j-1].b
B、A[j].a＜A[j-1].a
C、A[j].a＞A[j-1].a
D、A[j].b＜A[j-1].b
*
11.
单选题

1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 5000;
6 int n, m;
7 struct segment { int a, b; } A[MAXN];
8
9 void sort() // 排序
10 {
11 for (int i = 0; i < n; i++)
12 for (int j = 1; j < n; j++)
13 if (①)
14 {
15 segment t = A[j];
16 ②
17 }
18 }
19
20 int main()
21 {
22 cin >> n >> m;
23 for (int i = 0; i < n; i++)
24 cin >> A[i].a >> A[i]・b;
25 sort();
26 int p = 1;
27 for (int i = 1; i < n; i++)
28 if (③)
29 A[p++] = A[i];
30 n = p;
31 int ans =0, r = 0;
32 int q = 0;
33 while (r < m)
34 {
35 while (④)
36 q++;
37 ⑤;
38 ans++;
39 }
40 cout << ans << endl;
41 return 0;
42 }
②处应填（ ）
A、A[j+1]=A[j];A[j]=t;
B、A[j-1]=A[j];A[j]=t;
C、A[j]=A[j+1];A[j+1]=t;
D、A[j]=A[j-1];A[j-1]=t;
*
12.
单选题

1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 5000;
6 int n, m;
7 struct segment { int a, b; } A[MAXN];
8
9 void sort() // 排序
10 {
11 for (int i = 0; i < n; i++)
12 for (int j = 1; j < n; j++)
13 if (①)
14 {
15 segment t = A[j];
16 ②
17 }
18 }
19
20 int main()
21 {
22 cin >> n >> m;
23 for (int i = 0; i < n; i++)
24 cin >> A[i].a >> A[i]・b;
25 sort();
26 int p = 1;
27 for (int i = 1; i < n; i++)
28 if (③)
29 A[p++] = A[i];
30 n = p;
31 int ans =0, r = 0;
32 int q = 0;
33 while (r < m)
34 {
35 while (④)
36 q++;
37 ⑤;
38 ans++;
39 }
40 cout << ans << endl;
41 return 0;
42 }
③处应填（ ）
A、A[i].b＞A[p-1].b
B、A[i].b＜A[i-1].b
C、A[i].b＞A[i-1].b
D、A[i].b＜A[p-1].b
*
13.
单选题

1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 5000;
6 int n, m;
7 struct segment { int a, b; } A[MAXN];
8
9 void sort() // 排序
10 {
11 for (int i = 0; i < n; i++)
12 for (int j = 1; j < n; j++)
13 if (①)
14 {
15 segment t = A[j];
16 ②
17 }
18 }
19
20 int main()
21 {
22 cin >> n >> m;
23 for (int i = 0; i < n; i++)
24 cin >> A[i].a >> A[i]・b;
25 sort();
26 int p = 1;
27 for (int i = 1; i < n; i++)
28 if (③)
29 A[p++] = A[i];
30 n = p;
31 int ans =0, r = 0;
32 int q = 0;
33 while (r < m)
34 {
35 while (④)
36 q++;
37 ⑤;
38 ans++;
39 }
40 cout << ans << endl;
41 return 0;
42 }
④处应填（ ）
A、q+1＜n＆＆A[q+1].a＜=r
B、q+1＜n＆＆A[q+1].b＜=r
C、q＜n＆＆A[q].a＜=r
D、q＜n＆＆A[q].b＜=r
*
14.
单选题

1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 5000;
6 int n, m;
7 struct segment { int a, b; } A[MAXN];
8
9 void sort() // 排序
10 {
11 for (int i = 0; i < n; i++)
12 for (int j = 1; j < n; j++)
13 if (①)
14 {
15 segment t = A[j];
16 ②
17 }
18 }
19
20 int main()
21 {
22 cin >> n >> m;
23 for (int i = 0; i < n; i++)
24 cin >> A[i].a >> A[i]・b;
25 sort();
26 int p = 1;
27 for (int i = 1; i < n; i++)
28 if (③)
29 A[p++] = A[i];
30 n = p;
31 int ans =0, r = 0;
32 int q = 0;
33 while (r < m)
34 {
35 while (④)
36 q++;
37 ⑤;
38 ans++;
39 }
40 cout << ans << endl;
41 return 0;
42 }
⑤处应填（ ）
A、r=max(r,A[q+1].b)
B、r=max(r,A[q].b)
C、r=max(r,A[q+1].a)
D、q++
*
15.
判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，
该算法最准确的时间复杂度分析结果为𝑂(log 𝑛 + 𝑘)。（ ）
对
错
*
16.
判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，
当输入为“9801 1”时，输出的第一个数为“99”。（ ）
对
错
*
17.
判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）
对
错
*
18.
判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，
该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将mid 强制转换为 64 位整数再计算。（ ）
对
错
*
19.
单选题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，当输入为“2 1”时，输出的第一个数最接近（ ）。
A、1
B、1.414
C、1.5
D、 2
*
20.
单选题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，当输入为“3 10”时，输出的第一个数最接近（ ）。
A、1.7
B、 1.732
C、1.75
D、2
*
21.
单选题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，当输入为“256 11”时，输出的第一个数（ ）。
A、等于 16
B、接近但小于 16
C、接近但大于 16
D、前三种情况都有可能
*
22.
单选题
以下关于高精度运算的说法错误的是()
A、高精度计算主要是用来处理大整数或需要保留多位小数的运算
B、大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
C、高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
D、高精度加法运算的关键在于逐位相加并处理进位
*
23.
单选题
(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

①处应填（ ）
A、1
B、nums
C、right
D、left
*
24.
单选题

(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。


②处应填（ ）
A、left=mid+1
B、right=mid-1
C、right=mid
D、left=mid
*
25.
单选题
(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

③处应填（ ）
A、left=mid+1
B、right=mid-1
C、right=mid
D、right+1
*
26.
单选题
(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

④处应填（ ）
A、left+nums [θ]
B、right+nums [θ]
C、mid+nums[θ]
D、right+1
*
27.
单选题
(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

⑤处应填（ ）
A、nums[θ]+n
B、nums[θ]+n-1
C、nums[θ]+n+1
D、nums[n-1]
*
28.
单选题
设有100个数据元素，采用折半搜索时，最大比较次数为( )。
A、 6
B、7
C、8
D、10
*
29.
填空题
把M个同样的球放到N个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用
K表示)。 例如M＝7，N＝3时，K＝8；在这里认为和是同一种放置方法。 问：M＝8，N＝5时，K＝___ 。
问卷星提供技术支持
举报