CSP-J 模拟9
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
答案解析 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.已知数组A中，每个元素A[i][j]在存储时要占3字节，设i从1变化到8，j从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A[4][7]的 起始地址是什么？（） {{ select(1) }}
- A. SA+108
- B. SA+141
- C. SA+111
- D. SA+126
2.以下关于算法的描述正确的是（）。 {{ select(2) }}
- A.算法可以没有输出
- B.算法至少有一个输入
- C.算法必须在计算机上用某种语言实现
- D.算法的改进在很大程度上推动了计算机科学与技术的进步
3.执行下述C+代码，输出的结果是（）。 {{ select(3) }}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int pos=2;
string s=("noip");
cout<<s[++pos]<<endl;
return 0;
}
A.o B.i C.p D.空格
4.（）表示只读存储器。{{ select(4) }}
- A. HDD
- B. SSD
- C.ROM
- D. RAM
5.有关下面C+代码的说法，正确的是（）。 {{ select(5) }}
int cnt;
int fun(int a, int b)
{
int tmp;
if(0==b) tmp=a;
else{
tmp = fun(b,a%b);
cnt++;
}
return tmp;
}
- A.fun函数可以求出a和b的最大公共质因子
- B.fun函数可能会死循环
- C.如果a小于9，那么cnt的值不会超过20
- D.fun函数能够求出a和b的最小公倍数
6.以下哪个不属于与STL有关的函数？（） {{ select(6) }}
- A.swap
- B.sort
- C.max
- D.freopen
7. 在顺序表(1,3，7,10，14,15，19、26.38.47.85)中，用二分法查找13，所需的关键较的次数为( )。 {{ select(7) }}
- A.2
- B.3
- C.4
- D.5
8. 在下列各种排序算法中，关键字比较的次数与记录的初始排列次序无关的是() {{ select(8) }}
- A.插入排序
- B.快速排序
- C.选择排序
- D.冒泡排序
9.下列说法中正确的是（ )。 {{ select(9) }}
- A.计算机网络按照地理范围分为局域网、城域网和广域网
- B.互联网的基础TCP/IP是七层协议
- C.每台计算机配置的都是C类IP地址
- D.中国的计算机IP地址已经全部升级到了IPv6地址
10.在C盘中发现计算机病毒后，较为彻底的清除方法是（) {{ select(10) }}
- A.删除C盘文件
- B.格式化C盘
- C.用消毒水喷洒在C盘上
- D.用杀毒软件处理
11.下列关于十进制数101的说法中错误的是() {{ select(11) }}
注：这里B表示二进制 Binary，H表示十六进制Hexadecimal。
- A.该数原码为01100101 B
- B.该数反码为65H
- C.该数真值为01100011 B
- D.该数补码为65 H
12. 动态规划将一个问题分解为一系列子问题来求解。下面关于子问题的描述中正确的是（ )。 {{ select(12) }}
- A.具有重叠子问题的性质
- B.和分治法的子问题类似
- C.不具有最优子结构的性质
- D.问题的最优解可以由部分子问题的非最优解推导出来
13. 在下面的有向图中，有多少个强连通分量？ (） {{ select(13) }}
- A.3
- B.4
- C.5
- D.6
14.从4台甲型电视机和5台乙型电视机中任意取出3台，其中至少要甲型电视机与乙型电视机各一台，则不同的取法共有( )种。 {{ select(14) }}
- A.140
- B.70
- C.80
- D.35
15.在32位计算机中，用补码表示的C++的整型变量int能够表示的数据范围是()。 {{ select(15) }}
- A.0-2-1
- B.0-222
- C.-21-2"-1
- D.-2"+1~231
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填V，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）
(1)
```C++
#include <bits/stdc++.h>
using namespace std;
priority_queue c int, vectorkint,greatercint?)
int main()
{
int n,x,ans=0,t1=0，t2=0，t3=0;
cin >> n;
for(int i=0; icn; i++)
{
cin>>×;
q.push(x);
}
for(int i=n;i>1;i--)
{
t1 =q.top();
q.pop()；
t2 = q.top();
q.pop()；
t3 = t1+t2;
ans += t3;
q.push(t3);
}
cout<<ans<<endl;
return 0;
}
判断题 16.priority_queue是STL中的优先队列。() {{ select(16) }} 17.将第3行中的greater<int>去掉，不管输入如何，程序的运行结果都不变() {{ select(17) }} 18.将第15行和第17行互换，不管输人如何，程序的运行结果都不变。() {{ select(18) }} 19.将第21行去掉，不管输入如何，程序的运行结果都不变。() {{ select(19) }} 选择题 20.若输入312 9.则输出ans为() {{ select(20) }}
- A.12
- B.22
- C.23
- D.15
21 若输入4 5 4 3 6，则输出ans为() {{ select(21) }}
- A.30
- B.36
- C.37
- D.38
(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL fun(LL a, LL b, LL &×, LL 5y)
{
LL t;
if(O==b)
{
x=1;
y=0;
return a;
}
Ll d = fun(b,a%b,x,y);
t=x;
x=y;
y=t-(a/b)*y;
return d;
}
int main()
{
LL a，b，x=0，y=0;
cin >> a >> b;
cout << fun(a, b, x, y)<< endl;
cout << x << ""<< y << endl;
return 0;
}
判新题 将第3行中的typedef long long LL改为#define long long LL，程序的运( ） {{ select(22) }} 行结果不会改变 将第4行中的两个5去掉，程序的运行结果不会改变 () {{ select(23) }} 若输入b=0，则输出结果是a （ ） {{ select(24) }} 不国入两个为索数的正整数，则输出结果中，x和y一定有负数 （ ） {{ select(25) }} 选择题 26.若输入为02024，则输出为（ )。 {{ select(26) }}
- A.2024 1 1
- B.2024 0 1
- C.0 1 1
- D.0 0 1
27.若输入为36 48，则输出为（ )。 {{ select(27) }}
- A.144 1 -1
- B.144 -1 1
- C.12 1 -1
- D.12 -1 1
(3)
#include <bits/stdc++.h>
using namespace std;
int a[101][3], b[101];
void dfs(int k, int w){
if(1==w）
cout<<k<<"";
if(a[k][1]!=0)
dfs(a[k][1],w);
if(2==w)
cout<<k<<"";
if(a[k][2]!=0)
dfs(a[k][2],w);
if(3==w)
cout<<k<<"";
}
int main( )
{
int n,m,t,root;
cin>>n;
for(int j=1; ic=n; i++)
{
cin>t;
cinxxaltl(1l>>aft][2);
bfaft](1)]-1;
bla[t][2)]-1;
}
for (inr lsl;jcsn; j++)
if(b[i]==0){
root=i;
break;
}
dfs(root,1);
cout<<endl;
return 0;
}
判断题 28. dfs函数是处理二叉树的前、中、后序遍历的。 （） {{ select(28) }} 29.若将第24行cin>>altJ(1J>>altJ[2)更改为cin>>a[1][t]>>a[2][t]，程序的运行结不会改变。( ) {{ select(29) }} 30.若将第29行去掉，程序的运行结果不会改变。 ( ) {{ select(30) }} 31.若将第34行dfs(root，1)更换为dfs(root，4)，程序的运行结果不会改变。() {{ select(31) }} 选择题 32.若输入如下数据，则输出是( )。 {{ select(32) }} 8 124 200 4 80 315 5 6 0 6 0 7 8 0 0 70 0
- A.31248567
- B.2 1 8 4 3 6 7 5
- C.2 8 4 1 7 6 5 3
- D.3 2 1 8 4 5 7 6
33 若输入和第32题一样，将第34行dfs(root，1)更换为dfs(root，2)，则输出是( )。{{ select(33) }}
- A.3 1 2 4 8 5 6 7
- B.2 1 8 4 3 6 7 5
- C.2 8 4 1 7 6 5 3
- D.3 2 1 8 4 5 7 6
34.(4分)若输入和第32题一样，将第34行dfs(root，1)更换为dfs(root，3)，则输出是（)。 {{ select(34) }}
- A.3 1 2 4 8 5 6 7
- B.2 1 8 4 3 6 7 5
- C.2 8 4 1 7 6 5 3
- D.3 2 1 8 4 5 7 6
三、完善程序（单选题，每小题3分，共计30分） （1）米老鼠上次在唐老鸭的迷宫城堡里玩了很久，现在她也想设计一个迷宫让唐老鸭来 走。但是她设计迷宫的思路不一样，她认为所有的通道都应该是双向连通的，也就 是说，如果有一个通道连通了房间A和房间B，那么既可以通过它从房间A走到房 间B，也可以通过它从房间B走到房间A。为了提高难度，米老鼠希望任意两个房 间有且仅有一条路径可以相通（除非走了回头路)。米老鼠现在把她的设计图给你 让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合 条件的，但是最后一个有两种方法从5到达8。 输入格式： 输入包含多组数据，每组数据是一个以00结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1， ，且不超过 100 000。每两组数 据之间有一个空行。整个输入以两个-1结尾。 输出格式： 对于输人的每一组数据，输出仅包括一行。如果该迷官符合米老鼠的思路， 么输出YES，否则输出NO. 输入样例： 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 输出样例： YES YES NO
#include<iostream>
using namespace std;
#define MAXN 100005
int fa[MAXN];
int visit[MAXN];
int path, node;
void init(int n){
for(int i=1;ic=n;++i){
fa[i]=i;
visit[i] = 0;
}
path= 0;
node = 0;
int get(int x)t
if(x == fa[x])
return x;
else
return ①;
}
int main(){
int a,b；
bool flag;
cin>>a>>b;
while(a!=-1 66 b!=-1){
init(MAXN);
flag = true;
if(O==a 66 0==b)
path--;
while（②){
path++;
if(visit[a]==0){
visit[a]=1;
node++;
}
}
if(visit[b]==0){
visit[b]=1;
node++;
}
int root1=get(a);
int root2=get(b);
if(③)
flag = false;
else
;
cin>>a>>b;
if(⑤)
cout<<"NO"<<endl;
else cout<<"YES"<<endl;
cin>>a>>b;
}
return 0;
}
- ①处应填( )。 {{ select(35) }}
- A.fa[x]
- B.×
- C.fa[x]= get(fa[x])
- D.1
- 2处应填() {{ select(36) }}
- A.a！=0 1| b!=0
- B.a！=0 88 b!=0
- C.a！=0
- D.b!=0
- ③处应填( )。 {{ select(37) }}
- A.root1 == root2
- B.root1 != root2
- C.flag == true
- D.visit[a]== visit[b]
38.④处应填( )。 {{ select(38) }}
- A.fa[root1]= root1
- B.fa[root2]= root2
- C.fa[root1]= root2
- D.flag = true
39.⑤处应填（ ) {{ select(39) }}
- A.path != node 85 I flag
- B.path != node ll !flag
- C.path != node-1 68 !flag
- D.path != node-1 ll !flag
(2)给定一个字符串，请计算至少添加几个字符，可以让其构成回文字符串 输入样例： 5 acbed 输出样例： 2
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
char str1[MAXN], str2[MAXN];
int maxlen[2][MAXN];
int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;++i)
cin>>str1[i];
str1[n+1]='\0';
for(int i=1; i<=n;++i)
①;
memset(maxlen,0,sizeof(maxlen));
int x=0;
for(int i=1; i<=n; ++i)
{
x=1-×;
for(int j=0; j<=n; ++j)
{
if(str1[i] == str2[j])
2;
else
int len1 =3;
int len2 = maxlen[1-x][j];
if(④)
maxlen[x][j]= len1;
else
maxlen[x][j]= len2;
}
}
cout<<⑤<<endl;
}
return 0;
}
40.①处应填( )。 {{ select(40) }}
- A.str2[i]= str1[i]
- B.str2[i]= str1[n-1-i]
- C.str2[i]= str1[n-i]
- D.str2[i]= str1[n+1-i]
41.②处应填（ )。 {{ select(41) }}
- A.maxlen[x][j]= maxlen[1-x][j-1] + 1
- B.maxlen[x][j] = maxlen[x-1][j-1] + 1
- C.maxlen[x][j]= maxlen[1-x][j] + 1
- D.maxlen[x][j]= maxlen[x-1][j] + 1
42.③处应填() {{ select(42) }}
- A.maxlen[x][j]
- B.maxlen[x][j+1]
- C.maxlen[x][j-1]
- D.maxlen[1-x][j-1]
43.④处应填( )。 {{ select(43) }}
- A.Len1 > len2 +1
- B.len1 > len2
- C.len2 > len1
- D.len2 > len1 + 1
44.⑤处应填( ） {{ select(44) }}
- A.maxlen[xj[n]
- B.n-maxlen[x][n]
- C.maxten[1-x][n]
- D.n-maxlen[1-x][n]
[2024笔试] CSP - J考前刷题
- Status
- Done
- Rule
- OI
- Problem
- 10
- Start at
- 2024-8-12 4:30
- End at
- 2024-8-12 5:30
- Duration
- 1 hour(s)
- Host
-
东明张展奕
- Partic.
- 2
