2020CCF-CSP-S-第一轮-C++模拟试卷(五)(共23页).docx

精选优质文档-倾情为你奉上2020CCF非专业级别软件能力认证第一轮X卷（CSP-S）提高级C+语言试题卷认证时间: 2020年10月17日14:30-16:30考生注意事项:试题纸共有12页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。不得使用任何电子设备 (如计算器、手机、电子词典等)或查阅任何书籍资料。一、选择题（以下共有15道题目，对于每道题目，在ABCD选项中选择正确的一项。每题2分，共30分）1.以下关于CCF组织举办的竞赛说法不正确的是A.CSP认证每年举办一次，分“入门组”和“提高组”，分两轮进行。B.NOIP竞赛有悠久的历史，最早于1996年开始举办。C.NOI竞赛始于1983年，该竞赛不仅可以现场参加，还可以通过网上报名参加同步赛。D.各省的省队选拔独立进行，分两轮，初中选手只拥有E类名额。2.以下关于个人计算机操作系统的说法正确的是A.Bill Gates，他创办的Microsoft公司开发了Linux系列系统。B.Steve Jobs，他的苹果公司开发了IOS系统。C.目前Linux和Windows系统都是开源的，网上都能搜索并下载。D.除了以上提到的所有操作系统，还有DOS，Unix等系统。Windows使用最广3.十进制表达式(3×512+7×64+4×8+3)+1的结果以二进制形式表示为A B C1 D4.计算机能直接执行的指令包括两部分，他们是A.源操作数与目标操作数 B.操作码与操作数C.ASCII码与汉字代码 D.数字与字符5.以下程序段：for (i=1;i<=n;i+) ai=i;for (i=2;i<=n;i+) if (i=ai) for (j=1;j*i<=n;j+) aj*i=aj*i/i*(i-1); 的作用是求出1至n的所有A.质数 B.整数的最大因数 C.整数的因数个数 D.整数的(i) 6.关于BIOS下面说法正确的是A. BIOS一般由操作系统厂商来开发完成。 B. BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。C.BIOS是计算机基本输入输出系统软件的简称。D. BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。7.命题“PQ”可读做P蕴含Q， 其中P、Q是两个独立的命题. 只有当命题P成立而命题Q不成立时， 命题"PQ"的值为false， 其它情况均为true. 与命题"PQ"等价的逻辑关系式是。A. P Q B. P Q C. (P Q) D. (Q P )8.现在有一个集合，里面包含了字符串”zlymAKIOItxdy”（不含引号）的所有字符，则请问该集合的所有非空真子集的个数为A.4095 B.4096 C.4094 D.20469.对于完全背包问题（给出n种物品和一个容积为m的背包，每种物品有无限个，单个大小为vi，价值为wi，要求选择适当的物品放入背包，满足大小不超过容积且价值最大），设fi表示用去i的空间能获得的最大价值，倒序枚举i为使用的空间，正序枚举j为物品编号，则可写出动态转移方程A.fi=max(fi,fi-wj+vj)B.fi=max(fi,fi-vj+wj)C.fi=min(fi,fi-wj+vj)D.fi=min(fi,fi-vj+wj)10.小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 1 个航班 准点的概率是 0.9，第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为 0.9。如果存在第 i 个（i=1,2）航班晚点，第 i+1 个航班准点，则小明将赶不 上第 i+1 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请 问小明此次旅行成功的概率是A. 0.5 B. 0.648 C. 0.72  D. 0.7411.以下关于CSP非专业级认证与NOIP竞赛关系的说法最恰当的是A.完全无关 B.组织者相同 C.举办目标相同 D.从属关系，CSP从属于NOIP12.关于信息学竞赛涉及算法，以下说法不正确的是A.搜索分为深度优先和广度优先两种，特点是代码难度低，但都很费时B.模拟是一种最基本的算法，就是按照题目要求做。广义的模拟还包含其他算法C.贪心算法类似于“鼠目寸光”，该算法前提是满足“部分最优组成全局最优”D.动态规划包含了很多类型和优化，动态转移方程是该算法的核心13.如图，小圆圈表示网络的结点，结点之间的连线表示它们有网线相联，连线标注的数字表示该段网线单位时间内可以通过的最大信息量，现从结点B向结点A传递信息，信息可以分开沿不同的路线同时传递，则单位时间内传递的最大信息量为A、19B、20C、24D、2514.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为A. 2812.5KB  B. 4218.75KB C. 4320KB D. 2880KB15.情境：一位妈妈生了n胞胎，这n个孩子长得非常相似，让人无法辨认。一天晚上，妈妈要给这n个孩子洗澡。妈妈每次从孩子中抓出一个洗澡，洗完后又把他放回孩子之中，如此重复n次。问题：若n=10，则在所有的可能中，恰好只有三个孩子没有洗澡的可能性约为A.14% B.36% C.31% D.17% 二、阅读程序（以下共有三段程序。每段程序后面有6个题目，前4题为判断题，后2题为选择题。对于判断题，选择A代表正确，B代表错误；对于选择题，请在ABCD选项中选择正确的一项。判断题每题1分，选择题每题3分，共30分）#include<cstdio>#define MAX_N 20#define ll long longusing namespace std;int n;long long fMAX_NMAX_N;int main() scanf("%d",&n); for(int i=0;i<=n;i+) f0i=1; for(int i=1;i<=n;i+) for(int j=i;j<=n;j+) if(i=j)fij=fi-1j; else fij=fij-1+fi-1j; Cout<<fnn<<endl; return 0;16. 如果第3行的代码缺失，程序会出现编译错误。17. 本程序中f数组内被改变过的元素的值与n无关，即对于不同的n，f数组中不为0的元素值都对应相同18. 若n=10，对于任何0in，f0i=1 19. 若n=10，对于任何0in，f1i=120. 本程序没有使用的基本算法是A. 模拟 B.递推 C.递归 D.动态规划21. 对于输入6，本程序输出A. 5 B.14 C.42 D.132#include<iostream>#include<algorithm>using namespace std;long int n,k,sum,num=1,f;struct ren long int ks,js; ; ren z; int cmp(ren a,ren b) return a.ks>b.ks; int main() long int i,j; cin>>n>>k; for(i=1;i<=k;i+) cin>>zi.ks>>zi.js; sumzi.ks+; sort(z+1,z+k+1,cmp); for(i=n;i>=1;i-) if(sumi=0) fi=fi+1+1; else for(j=1;j<=sumi;j+) if(fi+znum.js>fi) fi=fi+znum.js; num+; cout<<f1<<endl;22. 本程序使用了贪心算法23.第23行sort排序后z数组中的元素按js元素降序排序24.以下是对于本代码的一段输入，则对应的输出是315 61 21 64 118 58 111 525.本代码的24行换成for (i=1;i<=n;+i)，可能会引发“数组越界”错误26.第10至12行程序定义了一个cmp函数以用于sort的比较。我们可以用含有以下的一个选项的程序段来定义适用于该结构体类型的小于运算。这个选项是A. this B.operator C.iterator D.it27. 本程序的时间复杂度是A.O(n) B.O(k) C.O(n·log(n) D.O(nk)/注释：本程序使用一种树形数据结构，实现了将读入的数据按照“左子树<=根<=右子树”的方法建树，并输出树的深度及后序遍历。#include<iostream>using namespace std;struct node int data,left,right;node tree;int n1;int ans;int NNN(int x) n+; treen.data=x; treen.left=treen.right=0; return n;void insert(int x,int& idx)if(!idx) idx=NNN(x); return ; if(x<treeidx.data) insert(x,treeidx.left); else insert(x,treeidx.right);void dfs(int idx,int deep)if(!idx) ans=max(ans,deep); return ; dfs(treeidx.left,deep+1); dfs(treeidx.right,deep+1);void printhx(int idx)if(idx) printhx(treeidx.left); printhx(treeidx.right); cout<<treeidx.data<<endl; int main() cin>>n1;for(int i=1;i<=n1;i+) int x; cin>>x; int id=1; if(i=1) NNN(x); else insert(x,id); dfs(1,0); cout<<"deep="<<ans<<endl; printhx(1); return 0;28.在本程序中，第6行的数组必须开到数据范围的结点数的4倍以上29.存放树的节点时运用了指针思想30.程序第9至14行的NNN函数作用是给树增加一个空节点31.将程序第30行和31行交换，不会对程序产生影响32. 一种树形结构是指A. 权值线段树 B.树状数组 C.斐波那契堆 D.二叉搜索树33.以下是一个对于本程序的输入，则与之对应的输出是81 4 3 9 10 35 2 7ABCDdeep=41234791035deep=64271910335deep=52371035914deep=52373510941三、补充程序（本大题共含有2篇代码，共10小题，每小题4分，共40分。请在每道小题后所给的四条代码中选出最恰当的一项，使这段代码填入完整程序中对应的空缺处能符合题意。）Qjl的比赛（20分）Qjl是一名神犇，他最近出了一场盛大的AK赛。比赛共含有n(1n)题，由于是AK赛，任何人做了任何一道题都能保证AC。但是Qjl身为神犇，要摆神犇的架子，具体做法是对于不同的题，赋予不同的满分，这样会让AK者的分数变得好看。不过，他的比赛中不断会出现出锅的情况，也就是题目满分应该被调整。他会不断调整一些题目的满分，使之更合理。现在Qjl需要你编写程序，帮他满足两种操作，如果你写出了代码，你有可能会获得%32768分的额外满分！他首先给你两个正整数n,m，表示题目数与操作数；然后他会给你n个正整数，表示这些题目初始的满分。接下来他会不断给你发m条操作指令：1 x y k：表示将题号ix,y的题目的满分都加上k；2 x y：表示询问题号ix,y的所有题目的AK分（即总分和。）请你编写程序，以享受AK的快感。#include<bits/stdc+.h>#define int long longusing namespace std;struct pointint lft,rgt,num,lzy; a;int b,n,m,i,x,y,z,t;void build(int p,int l,int r)ap.lft=l;ap.rgt=r;if (l=r)ap.num=bl;return;build( ,l,(l+r)/2);build( ,(l+r)/2+1,r);ap.num=ap*2.num+ap*2+1.num;void down(int p)if ( )ap*2.num+=ap.lzy*(ap*2.rgt-ap*2.lft+1);ap*2+1.num+=ap.lzy*(ap*2+1.rgt-ap*2+1.lft+1);ap*2.lzy+=ap.lzy;ap*2+1.lzy+=ap.lzy; ;void add2(int nd,int st,int ed,int x)if (st<=and.lft && ed>=and.rgt)and.num+= ;and.lzy+=x;return;down(nd);if (st<=(and.lft+and.rgt)/2) add2(nd*2,st,ed,x);if (ed>=(and.lft+and.rgt)/2+1) add2(nd*2+1,st,ed,x);and.num=and*2.num+and*2+1.num;int Find(int nd,int l,int r)if ( ) return ;down(nd);int bb=0;if (l<=(and.lft+and.rgt)/2) bb+=Find(nd*2,l,r);if (r>=(and.lft+and.rgt)/2+1) bb+=Find(nd*2+1,l,r);return bb;signed main()scanf("%lld%lld",&n,&m);for (i=1;i<=n;i+)scanf("%lld",&bi);build(1,1,n);for (i=1;i<=m;i+)scanf("%lld",&t);if (t=1)scanf("%lld%lld%lld",&x,&y,&z);add2(1,x,y,z);elsescanf("%lld%lld",&x,&y);printf("%lldn",Find(1,x,y);34. 填入和的代码分别是A.p*2；p*2+1B.p*2+1；p*2C.p+1；p+2D.p+2；p+135填入处的代码是A.ap.num=0B.ap.num!=0C.ap.lay=0D.ap.lzy!=036.填入处的代码是A.ap.num=0B.ap.lzy=0C.ap.num=ap.lzy=0D.down(p*2);down(p*2+1);37.填入处的代码是A.and.rgt-and.lft+1B.and.rgt-and.lftC.x*(and.rgt-and.lft+1)D.x*(and.rgt-and.lft)38.填入和处的代码分别是A.l<=and.lft && and.rgt<=r；and.numB.l<=and.lft && and.rgt<=r；and.num*(l-r+1)C.and.lft<=l && r<=and.rgt；and.num*(l-r+1)D.and.lft<=l && r<=and.rgt；and.num奶牛也感染（20分）每头奶牛都不想成为被新型病毒感染的奶牛。被所有奶牛接触的奶牛就是一头被感染的奶牛。因为奶牛喜欢偷偷摸摸地行动，所有接触是单向的，所有奶牛都与自己接触。奶牛之间的接触是可以传递的如果 A接触过 B，B接触过C，那么A也接触过C。牛栏里共有N头奶牛，给定一些奶牛之间的接触关系，请你算出有多少头奶牛不幸被感染。输入的第一行是两个用空格分开的整数N 和 M。接下来 M 行每行两个用空格分开的整数A 和 B，表示 A接触过B。输出被感染的奶牛的数量。#include<bits/stdc+.h>using namespace std;struct edgeint v,next; p50001;int front10001,M;void Add(int u,int v)+M;pM.v=v; ;frontu=M;int dfn10001,low10001,N,s;stack<int> zhan;int which10001;int Out10001,id,large10001;int n,m;int dfs(int x)+N;dfnx=lowx=N;zhan.push(x);for (int i=frontx;i;i=pi.next)if ( )dfs(pi.v); else lowx=min(lowx,dfnpi.v);if (dfnx=lowx)+s;int S=0;int v;dov=zhan.top();zhan.pop(); +S; while (x!=v);Larges=S;int main()int i,j;scanf("%d%d",&n,&m);for (i=1;i<=m;+i)int x,y;scanf("%d%d",&x,&y);Add(x,y);for (i=1;i<=n;+i) if (dfni=0) dfs(i);for (i=1;i<=n;+i) for (j=fronti;j;j=pj.next) if (whichpj.v!=whichi) ;for (i=1;i<=s;+i) if (Outi=0) if (id!=0) printf("%dn",0); return 0; id=i; printf("%dn",largeid); return 0;39.处填入的代码是A.pM.next=uB.pM.next=vC.pM.next=frontuD.pM.next=frontv40.处填入的代码是A.!dfnpi.vB.dfnpi.vC.lowpi.vD.!lowpi.v41.处填入的代码是A.dfnx=min(dfnx,dfnpi.v);B.dfnx=max(dfnx,lowpi.v);C.lowx=max(lowx,dfnpi.v);D.lowx=min(lowx,lowpi.v);42.处填入的代码是A.+s;B.whichv=s;C.x=zhan.top(),zhan.pop();D.zhan.push(x+v);43.处填入的代码是A.+OutwhichiB.+whichOutiC.+OutOutiD.+whichwhichi说明：试题卷至上一页结束，以下为答案和答题卷（不怎么好看，选择使用），请在下发试题之前把以下两页保存到新的文档后删除。答案：12345678910ADBBDCDDBD11121314151617181920BAAABBAABC21222324252627282930DBBBBBDBAA31323334353637383940ADDADBCDCB414243DBA2020CCF非专业级别软件能力认证第一轮X卷（CSP-S）提高级C+语言答题卷认证时间: 2020年10月17日14:30-16:30-一、 选择题（共15小题，共30分）二、 阅读程序（共12道判断题，每题1分，6道选择题，每题3分，共30分）三、补充程序（共10小题，每小题4分，共40分。）专心-专注-专业