CSP-J模拟卷11
选择题
- （2分）Linux下可执行文件的默认扩展名为（）。{{ select(1) }}
- A. exe
- B. com
- C. dll
- D. 以上都不是
- （2分）对n个数用冒泡排序算法排序，最少需要比较多少次？（）{{ select(2) }}
- A. n²
- B. n-2
- C. n-1
- D. n
- （2分）地址总线为32位时，理论最大可寻址内存空间为（）。{{ select(3) }}
- A. 128KB
- B. 1MB
- C. 1GB
- D. 4GB
- （2分）无向完全图G有7个顶点，共有（）条边。{{ select(4) }}
- A. 7
- B. 21
- C. 42
- D. 49
- （2分）下列说法正确的是（）。{{ select(5) }}
- A. CPU的主要任务是执行数据运算和程序控制
- B. 存储器信息任何时候都不会丢失
- C. 显示器尺寸相同则分辨率必定相同
- D. 个人用户只能用Wifi连接Internet
- （2分）以A0为起点深度优先遍历无向图，不可能的顺序是（）。{{ select(6) }}
- A. A1
- B. A2
- C. A0
- D. A3
- （2分）完全二叉树中第k号结点的父结点存于数组的（）号位置。{{ select(7) }}
- A. 2k
- B. 2k+1
- C. ⌊k/2⌋
- D. ⌊(k+1)/2⌋
- （2分）书写错误的32位IP地址是（）。{{ select(8) }}
- A. 162.105.135.27
- B. 192.168.0.1
- C. 256.256.129.1
- D. 10.0.0.1
- （2分）三进制下等式XY + ZX = XYX成立，则XY * ZX =（）。{{ select(9) }}
- A. YXZ
- B. ZXY
- C. XYZ
- D. XZY
- （2分）7个苹果放到3个盘子（可空），有（）种放法。{{ select(10) }}
- A. 7
- B. 8
- C. 21
- D. 37
- （2分）“之”“乎”“者”“也”出现次数为700、600、300、400，“也”的编码长度可能是（）。{{ select(11) }}
- A. 1
- B. 2
- C. 3
- D. 4
- （2分）递推式T(n)=T(n-1)+n，T(0)=1，时间复杂度为（）。{{ select(12) }}
- A. O(logn)
- B. O(nlogn)
- C. O(n)
- D. O(n²)
- （2分）能让果树浇上水的阀门设置是（）。{{ select(13) }}
- A. B打开，其他关
- B. AB打开，CD关
- C. A打开，其他关
- D. D打开，其他关
- （2分）10000以内与10000互质的正整数有（）个。{{ select(14) }}
- A. 2000
- B. 4000
- C. 6000
- D. 8000
- （2分）5位车牌倒过来仍是原车牌的数量为（）。{{ select(15) }}
- A. 60
- B. 125
- C. 75
- D. 100
阅读理解1（12分）
#include<iostream>
using namespace std;
int main() {
const int SIZE=10;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for(int i=0;i<n;i++) {
cin>>height[i];
num[i]=1;
for(int j=0;j<i;j++) {
if((height[j]<height[i])&&(num[j]>=num[i]))
num[i]=num[j]+1;
}
}
ans=0;
for(int i=0;i<n;i++){
if(num[i]>ans) ans=num[i];
}
cout<<ans<<endl;
return 0;
}
第16题（1.5分）
height数组输入负数会出错。（）{{ select(16) }}
- 正确
- 错误
第17题（1.5分）
输出ans≤n。（）{{ select(17) }}
- 正确
- 错误
第18题（1.5分）
将12行num[j]>=num[i]改为num[j]>num[i]，结果不变。（）{{ select(18) }}
- 正确
- 错误
第19题（1.5分）
将18行num[i]>ans改为num[i]>=ans，结果不变。（）{{ select(19) }}
- 正确
- 错误
第20题（3分）
输入10个1，输出：{{ select(20) }}
- A. 4
- B. 3
- C. 2
- D. 1
第21题（3分）
输入3 2 5 11 12 7 4 10 15 6，输出：{{ select(21) }}
- A. 4
- B. 5
- C. 6
- D. 7
阅读理解2（14分）
#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
if (l > r)
return 0;
int min = maxn, mink;
for (int i = l; i <= r; ++i) {
if (min > a[i]) {
min = a[i];
mink = i;
}
}
int lres = f(l, mink - 1, depth + 1);
int rres = f(mink + 1, r, depth + 1);
return lres + rres + depth * b[mink];
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
cout << f(0, n - 1, 1) << endl;
return 0;
}
第22题（2分）
若a数组有重复数字，程序会出错。（）{{ select(22) }}
- 正确
- 错误
第23题（2分）
若b数组全为0，输出为0。（）{{ select(23) }}
- 正确
- 错误
第24题（2分）
n=100时，最坏情况下第12行比较次数接近：{{ select(24) }}
- A. 5000
- B. 600
- C. 6
- D. 100
第25题（2分）
n=100时，最好情况下第12行比较次数接近：{{ select(25) }}
- A. 100
- B. 6
- C. 5000
- D. 600
第26题（3分）
n=10时，b[i]=i+1，输出最大为：{{ select(26) }}
- A. 386
- B. 383
- C. 384
- D. 385
第27题（3分）
n=100时，b[i]=1，输出最小为：{{ select(27) }}
- A. 582
- B. 580
- C. 579
- D. 581
阅读理解3（14分）
#include<bits/stdc++.h>
using namespace std;
#define MOD 19260817
#define MAXN 1005
long long A[MAXN][MAXN]={0}, sum[MAXN][MAXN]={0};
int n, m, q;
int main(){
A[1][1]=A[1][0]=1;
for(int i=2;i <= 1000; i++) {
A[i][0]=1;
for(int j = 1; j <= i; j++)
A[i][j]=(A[i-1][j]+A[i-1][j-1])%MOD;
}
for(int i =1;i <= 1000; i++)
for(int j=1;j<=1000;j++)
sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j]+MOD)%MOD;
int q;
cin >> q;
while(q--){
int n, m;
cin >> n >> m;
cout << sum[n][m] << endl;
}
return 0;
}
第28题（1.5分）
i≤j时，A[i][i]=0。（）{{ select(28) }}
- 正确
- 错误
第29题（1.5分）
i>j时，A[i][j]是i选j的排列数。（）{{ select(29) }}
- 正确
- 错误
第30题（3分）
sum[i][j]≥sum[i-1][j-1]。（）{{ select(30) }}
- 正确
- 错误
第31题（3分）
第12行改为A[i][j]=(A[i-1][j]+A[i-1][j-1]+MOD)%MOD，结果不变。（）{{ select(31) }}
- 正确
- 错误
第32题（3分）
A[i][j]（1≤i,j≤10）的最大值是：{{ select(32) }}
- A. 126
- B. 276
- C. 252
- D. 210
第33题（3分）
输入1/5 3，输出：{{ select(33) }}
- A. 10
- B. 35
- C. 50
- D. 24
编程填空1（15分）
题目描述: 切割绳子
#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;
}
第34题（3分）①处应填（）{{ select(34) }}
- A.
count = count + len[i] - B.
count += len[i] - C.
count = len[i] - D.
count += 1
第35题（3分）②处应填（）{{ select(35) }}
- A.
count < m - B.
count > m - C.
m == 0 - D.
n < m
第36题（3分）③处应填（）{{ select(36) }}
- A.
lbound >= ubound - B.
lbound < ubound - C.
lbound > ubound - D.
lbound != ubound
第37题（3分）④处应填（）{{ select(37) }}
- A.
(lbound + ubound) / 2 - B.
(lbound + ubound + 1) / 2 - C.
lbound + (ubound - lbound) / 2 - D.
ubound - (ubound - lbound) / 2
第38题（3分）⑤处应填（）{{ select(38) }}
- A.
count += len[i] % mid - B.
count += len[i] / mid - C.
count = len[i] / mid - D.
count = len[i] % mid
编程填空2（15分）
题目描述: 排列数
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE =25;
bool used[SIZE];
int data[SIZE];
int n,m,i,j,k;
bool flag;
int main()
{
cin>>n>>m;
memset(used,false,sizeof(used));
for(i=1;i<=m;i++)
{
data[i]=i;
used[i]=true;
}
flag=true;
while(flag)
{
for(i=1;i<=m-1;i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag= [ ① ] ;
for(i=m;i>=1;i--)
{
[ ② ];
for(j=data[i]+1;j<=n;j++)
if(!used[j])
{
used[j]=true;
data[i]=[ ③ ] ;
flag=true;
break;
}
if(flag)
{
for(k=i+1;k<=m;k++)
for(j=1;j<= [ ④ ];j++)
if(!used[j])
{
data[k]=j;
used[j]=true;
break;
}
[ ⑤ ];
}
}
}
return 0;
}
第39题（3分）①处应填（）{{ select(39) }}
- A.
true - B.
false - C.
i < m - D.
i > 1
第40题（3分）②处应填（）{{ select(40) }}
- A.
used[data[i]] = true - B.
used[data[i]] = false - C.
data[i] = 0 - D.
used[i] = false
第41题（3分）③处应填（）{{ select(41) }}
- A.
i - B.
j - C.
data[i] + 1 - D.
n
第42题（3分）④处应填（）{{ select(42) }}
- A.
m - B.
n - C.
i - D.
k
第43题（3分）⑤处应填（）{{ select(43) }}
- A.
break - B.
continue - C.
flag = false - D.
used[j] = false