（NEW）[答案]2019信息学奥赛CSP-J入门组试卷+答案+解析
2019CCF非专业级别软件能力认证第一轮
（CSP-J）入门级C++语言试题A卷
（B卷与A卷仅顺序不同）
解析：答案A。
中国国家顶级域名即是，域名由国家管理。cn也是中国的缩写。
解析：答案D。
与运算是两者有一个0结果就是0，两者都是1才是1。
11 1011 1001 0111
01 0110 1110 1011
——————————&
01 0010 1000 0011
解析：答案C。
1字节?=8位。32除以8等于4，所以选C。
解析：答案A。
上述程序其实是计算出s减去c个1后等于多少，也就是a-c等于多少。所以选A。
解析：答案A。
二分查的次数为logN。计算得出?所以选A。
解析：答案D。
链表和数组不同的是他不能随机访问，只能“随藤摸瓜”的。
解析：答案C。
数据比较小，可以用列举法来做。如果袋子中最大8个球的情况有1种，最大7个球有
1种，最大6个球有2种，最大5个球有3种，最大4个球有5种，最大3个球有4种，最大2个球有2种。一共18种。
c++判断素数解析：答案C。
先将其补充成完全二叉树，此时树的结点总数是15，所以答案选C。
解析：答案B。
素数是能能被自己和1整除的数。从100开始推算，100不是素数，99也不是…. 97只
能被1和自己整除，所以选B。
解析：答案C.
用短除法可以算出29。
解析：答案C。
性价比最高的是方案二，那么在周五、周六和周日这三天用方案二，跑了15公里，1800千卡。
还剩6公里，在周一到周二跑完，消耗600千卡。那么一总消耗2400千卡。
解析：答案A。
鸽笼原理。因为求最少的可能性，那么我们可以构造一个尽量花不一样的情况。
红、黄、蓝、绿、红、黄、蓝、绿、红、黄、蓝、绿。已有12张牌，剩下不管拿到什么
颜都会构成四种颜相同。所以选A。
解析：答案C。
显然中间一位数字只能为1和0，接着去列举其他四位即可。
解析：答案B。
通过后序遍历不难看出根结点是A，那么左子树结点为DBGEHJ，右子树为CIF。因为求
的是前序遍历，那么选项中如果右子树出现在了左子树前面，即可排除。再根据后序遍历的序列构建整个二叉树即可得出B。
解析：答案A。
图灵奖（Turing Award），全称“A.M.?图灵奖（A.M Turing
Award）”，由于ACM于1966年设立，专门奖励那些对计算机事业作出重要贡献的个人。
二、阅读程序
程序大意：对于字符串中的第i位，如果i是n的约数，并且第i个字符比‘a’(97)要大，
就减少‘a’(97)-‘A’(65)。
#include#includeusing namespace std;char st[100];int main()
{scanf(“%s”,?st);int n=strlen(st); //
计算字符串的长度for (int i=1; i <=n; ++i) { //
对字符串中的第i个字符进行循环枚举if (n % i==0) { // 判断i是否是n的约数char
c=st[i -
1]; // 取出字符串中的第i个字符if (c >=‘a’) // 判断字符是否大于97st[i - 1]=c
- ‘a’ + ‘A’; // 将字符减少32}}printf(“%s”, st); // 输出字符串return 0;}
1）考察程序的输入输出。
程序中没有对字符串中的字符范围进行任何要求。
2）考察表达式运算，除法和取模。
如果i=0，那么在n对i进行取模运算时就会报错，因为除以0了。
3）考察约数判断，注意不是素数判定。
判断素数的时候通常用这种方式进行加速，是因为sqrt(n)之后的约数与之前的约数是一一对应的，这也就说明了sqrt(n)之后还有约数。
如果将循环范围缩小了，就不会处理后面的约数，导致答案不一样。
4）考察数据类型，字符型的存储与表示。
大写字母的ASCII码都要小于‘a’(97)，所以不会对字符串进行修改。
5）考察数学，约数数量计算。
将要计算的数分解质因数，每个质因数的出现次数加1，再乘起来就是约数个数。
最多时每个约数的位置都可以修改，18有6个约数。
6）考察数学，约数数量计算。
10000=2^5 5^5，一共有(5 + 1) (5
+ 1)=36个约数。
不会求约数个数的同学可以暴力算一下其他几个数的约数个数，用排除法也能得到这个
答案。
程序大意：有ab两组元素，两组元素之间可以两两配对（0可以任意次配对）。
初始时所有元素都和另一组的0配对，每次考察a组的第x个元素和b组的第y个元素，如果这两个元素之前的配对交叉了，则把它们之前的配对元素都重新配对到0，并将这两
个元素配对。
最后求有多少个元素和0配对。
#includeusing namespace std;int n, m;int a[100],
b[100];
int main()
{scanf(“%d%d”,?&n,?&m);?//?n个数与m次操作for
(int i=1; i <=n; ++i) // 初始时所有数都跟0配对
a[i]=b[i]=0;for?(int?i?=?1;?i?<=?m;?++i)?{int
x,
y;scanf(“%d%d”,?&x,?&y);if?(a[x]?
的一对配对是否交叉if?(a[x]?>?0)?//?将原先的配对元素重新和0配对b[a[x]]=0;if (b[y] > 0)a[b[y]]?=?0;a[x]?=?y;?//?当前两个元素建立新的配对a[y]=x;}}int
ans=0;for?(int?i?=?1;?i?<=?n;?++i)?{?//?统计和0配对的元素数量if
(a[i]==0)++ans;if (b[i]==0)++ans;}printf(“%dn”, ans);return
0;}
1）考察对程序含义的理解。
m > 0时一定会有一个配对，所以和0配对的元素的数量一定小于2n。
2）考察对程序含义的理解，反例设计。
统计是按照元素编号的顺序进行的，如果有一个x <
y的配对，那么统计完b中的第x个元素时ans会变成奇数。
3）考察对程序含义的理解，反例设计。
如果ab中的第i个元素进行配对，则a[i]和b[i]同时>0。
4）考察对程序含义的理解，反例设计。
x总是小于y不代表x之前没有别的配对，如果x之前有别的配对，则照样会执行清理。? ? ? ? ?可以依次对(1, 1)和(1,
2)进行配对，则第二次操作时会对1的配对进行清理。
5）考察对程序含义的理解。
x和y两两不同时，每次都会成功进行配对，m次会产生m对配对，所以和0配对的元
素数量为2n - 2m。
6）考察对程序含义的理解。
x各不相同，y每次相等，那么x和y配对时每次都会清理掉之前的配对，最终只会产
生一组配对，所以和0配对的元素数量为2n
- 2。
程序大意：将一个元素序列根据a值构造成一棵二叉树，每次在序列中选择a值最小且
最靠前的元素作为根，根之前的序列构建左子树，根之后的序列构建右子树。
最后求出每个节点的深度乘以b值的和。
#includeusing namespace std;const int maxn=10000;int
n;int a[maxn];int b[maxn];int f(int l, int r, int depth) { //
计算序列中l到r这几个元素构成的根深度为depth的子树的权值if (l > r) // 判断空子树return
0;int min=maxn, mink;for (int i=l; i <=r; ++i) { //
查a值最小的最靠左的元素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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。