2020CCF-CSP-S-第一轮-C++模拟试卷(五)

CCFCSP-J2020第一轮C++语言试题卷X卷第1页共14页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.BillGates，他创办的Microsoft公司开发了Linux系列系统。B.SteveJobs，他的苹果公司开发了IOS系统。C.目前Linux和Windows系统都是开源的，网上都能搜索并下载。D.除了以上提到的所有操作系统，还有DOS，Unix等系统。Windows使用最广3.十进制表达式(3×512+7×64+4×8+3)+1的结果以二进制形式表示为A．10111100101B．11111100100C．111110100011D．111111011014.计算机能直接执行的指令包括两部分，他们是A.源操作数与目标操作数B.操作码与操作数C.ASCII码与汉字代码D.数字与字符5.以下程序段：for(i=1;i=n;i++)a[i]=i;for(i=2;i=n;i++)if(i==a[i]){for(j=1;j*i=n;j++)a[j*i]=a[j*i]/i*(i-1);}的作用是求出1至n的所有A.质数B.整数的最大因数C.整数的因数个数D.整数的ϕ(i)6.关于BIOS下面说法正确的是A.BIOS一般由操作系统厂商来开发完成。B.BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。CCFCSP-J2020第一轮C++语言试题卷X卷第2页共14页C.BIOS是计算机基本输入输出系统软件的简称。D.BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。7.命题“P→Q”可读做P蕴含Q，其中P、Q是两个独立的命题.只有当命题P成立而命题Q不成立时，命题P→Q的值为false，其它情况均为true.与命题P→Q等价的逻辑关系式是。A.﹁P∧QB.P∧QC.﹁(P∨Q)D.﹁(﹁Q∨P)8.现在有一个集合，里面包含了字符串”zlymAKIOItxdy”（不含引号）的所有字符，则请问该集合的所有非空真子集的个数为A.4095B.4096C.4094D.20469.对于完全背包问题（给出n种物品和一个容积为m的背包，每种物品有无限个，单个大小为v[i]，价值为w[i]，要求选择适当的物品放入背包，满足大小不超过容积且价值最大），设f[i]表示用去i的空间能获得的最大价值，倒序枚举i为使用的空间，正序枚举j为物品编号，则可写出动态转移方程A.f[i]=max(f[i],f[i-w[j]]+v[j])B.f[i]=max(f[i],f[i-v[j]]+w[j])C.f[i]=min(f[i],f[i-w[j]]+v[j])D.f[i]=min(f[i],f[i-v[j]]+w[j])10.小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航班准点的概率是0.9，第2个航班准点的概率为0.8,第3个航班准点的概率为0.9。如果存在第i个（i=1,2）航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是A.0.5B.0.648C.0.72D.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.5KBB.4218.75KBC.4320KBD.2880KB15.情境：一位妈妈生了n胞胎，这n个孩子长得非常相似，让人无法辨认。一天晚上，妈妈要给这n个孩子洗澡。妈妈每次从孩子中抓出一个洗澡，洗完后又把他放回孩子之中，如此重复n次。问题：若n=10，则在所有的可能中，恰好只有三个孩子没有洗澡的可能性约为CCFCSP-J2020第一轮C++语言试题卷X卷第3页共14页A.14%B.36%C.31%D.17%二、阅读程序（以下共有三段程序。每段程序后面有6个题目，前4题为判断题，后2题为选择题。对于判断题，选择A代表正确，B代表错误；对于选择题，请在ABCD选项中选择正确的一项。判断题每题1分，选择题每题3分，共30分）①#includecstdio#defineMAX_N20#definelllonglongusingnamespacestd;intn;longlongf[MAX_N][MAX_N];intmain(){scanf(%d,&n);for(inti=0;i=n;i++){f[0][i]=1;}for(inti=1;i=n;i++){for(intj=i;j=n;j++){if(i==j)f[i][j]=f[i-1][j];elsef[i][j]=f[i][j-1]+f[i-1][j];}}Coutf[n][n]endl;return0;}16.如果第3行的代码缺失，程序会出现编译错误。17.本程序中f数组内被改变过的元素的值与n无关，即对于不同的n，f数组中不为0的元素值都对应相同18.若n=10，对于任何0≤i≤n，f[0][i]=119.若n=10，对于任何0≤i≤n，f[1][i]=120.本程序没有使用的基本算法是A.模拟B.递推C.递归D.动态规划21.对于输入6，本程序输出A.5B.14C.42D.132②#includeiostream#includealgorithmusingnamespacestd;longintn,k,sum[100001],num=1,f[100001];structrenCCFCSP-J2020第一轮C++语言试题卷X卷第4页共14页{longintks,js;};renz[100001];intcmp(rena,renb){returna.ksb.ks;}intmain(){longinti,j;cinnk;for(i=1;i=k;i++){cinz[i].ksz[i].js;sum[z[i].ks]++;}sort(z+1,z+k+1,cmp);for(i=n;i=1;i--){if(sum[i]==0)f[i]=f[i+1]+1;elsefor(j=1;j=sum[i];j++){if(f[i+z[num].js]f[i])f[i]=f[i+z[num].js];num++;}}coutf[1]endl;}22.本程序使用了贪心算法23.第23行sort排序后z数组中的元素按js元素降序排序24.以下是对于本代码的一段输入，则对应的输出是31561216411858111525.本代码的24行换成for(i=1;i=n;++i)，可能会引发“数组越界”错误26.第10至12行程序定义了一个cmp函数以用于sort的比较。我们可以用含有以下的一个选项的程序段来定义适用于该结构体类型的小于运算。这个选项是CCFCSP-J2020第一轮C++语言试题卷X卷第5页共14页A.thisB.operatorC.iteratorD.it27.本程序的时间复杂度是A.O(n)B.O(k)C.O(n·log(n))D.O(nk)③//注释：本程序使用一种树形数据结构，实现了将读入的数据按照“左子树=根=右子树”的方法建树，并输出树的深度及后序遍历。#includeiostreamusingnamespacestd;structnode{intdata,left,right;};nodetree[300010];intn1;intans;intNNN(intx){n++;tree[n].data=x;tree[n].left=tree[n].right=0;returnn;}voidinsert(intx,int&idx){if(!idx){idx=NNN(x);return;}if(xtree[idx].data)insert(x,tree[idx].left);elseinsert(x,tree[idx].right);}voiddfs(intidx,intdeep){if(!idx){ans=max(ans,deep);return;}dfs(tree[idx].left,deep+1);dfs(tree[idx].right,deep+1);}CCFCSP-J2020第一轮C++语言试题卷X卷第6页共14页voidprinthx(intidx){if(idx){printhx(tree[idx].left);printhx(tree[idx].right);couttree[idx].dataendl;}}intmain(){cinn1;for(inti=1;i=n1;i++){intx;cinx;intid=1;if(i==1)NNN(x);elseinsert(x,id);}dfs(1,0);coutdeep=ansendl;printhx(1);return0;}28.在本程序中，第6行的数组必须开到数据范围的结点数的4倍以上29.存放树的节点时运用了指针思想30.程序第9至14行的NNN函数作用是给树增加一个空节点31.将程序第30行和31行交换，不会对程序产生影响32.一种树形结构是指A.权值线段树B.树状数组C.斐波那契堆D.二叉搜索树33.以下是一个对于本程序的输入，则与之对应的输出是81439103527ABCDdeep=412347910deep=642719103deep=5237103591deep=5237351094CCFCSP-J2020第一轮C++语言试题卷X卷第7页共14页353541三、补充程序（本大题共含有2篇代码，共10小题，每小题4分，共40分。请在每道小题后所给的四条代码中选出最恰当的一项，使这段代码填入完整程序中对应的空缺处能符合题意。）①《Qjl的比赛》（20分）Qjl是一名神犇，他最近出了一场盛大的AK赛。比赛共含有n(1≤n≤100000)题，由于是AK赛，任何人做了任何一道题都能保证AC。但是Qjl身为神犇，要摆神犇的架子，具体做法是对于不同的题，赋予不同的满分，这样会让AK者的分数变得好看。不过，他的比赛中不断会出现出锅的情况，也就是题目满分应该被调整。他会不断调整一些题目的满分，使之更合理。现在Qjl需要你编写程序，帮他满足两种操作，如果你写出了代码，你有可能会获得2147483648%32768分的额外满分！他首先给你两个正整数n,