2020CCF-CSP-S-第一輪-C++模擬試卷五

2020CCF非專業(yè)級(jí)別軟件能力認(rèn)證第一輪X卷(CSP-S)提高級(jí)C++語言試題卷認(rèn)證時(shí)間:2020年10月17日14:30-16:30考生注意事項(xiàng):?試題紙共有12頁，答題紙共有1頁，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。?不得使用任何電子設(shè)備(如計(jì)算器、手機(jī)、電子詞典等)或查閱任何書籍資料。一、選擇題(以下共有15道題目，對(duì)于每道題目，在ABCD選項(xiàng)中選擇正確的一項(xiàng)。每題2分，共30分)1.以下關(guān)于CCF組織舉辦的競(jìng)賽說法不正確的是A.CSP認(rèn)證每年舉辦一次，分“入門組”和“提高組”，分兩輪進(jìn)行。B.NOIP競(jìng)賽有悠久的歷史，最早于1996年開始舉辦。C.NOI競(jìng)賽始于1983年，該競(jìng)賽不僅可以現(xiàn)場(chǎng)參加，還可以通過網(wǎng)上報(bào)名參加同步賽。D.各省的省隊(duì)選拔獨(dú)立進(jìn)行，分兩輪，初中選手只擁有E類名額。2.以下關(guān)于個(gè)人計(jì)算機(jī)操作系統(tǒng)的說法正確的是A.BillGates，他創(chuàng)辦的Microsoft公司開發(fā)了Linux系列系統(tǒng)。B.SteveJobs，他的蘋果公司開發(fā)了IOS系統(tǒng)。C.目前Linux和Windows系統(tǒng)都是開源的，網(wǎng)上都能搜索并下載?？?除了以上提到的所有操作系統(tǒng)，還有DOS，Unix等系統(tǒng)。Windows使用最廣.十進(jìn)制表達(dá)式(3義512+7X64+4義8+3)+1的結(jié)果以二進(jìn)制形式表示為A．10111100101B．11111100100C．111110100011D．11111101101.計(jì)算機(jī)能直接執(zhí)行的指令包括兩部分，他們是B.操作碼與操作數(shù)D.B.操作碼與操作數(shù)D.數(shù)字與字符C.ASCII碼與漢字代碼.以下程序段：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的所有C.整數(shù)的因數(shù)個(gè)數(shù)D.整數(shù)的A.質(zhì)數(shù) C.整數(shù)的因數(shù)個(gè)數(shù)D.整數(shù)的.關(guān)于BIOS下面說法正確的是BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。BIOS里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C.BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱。D.BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。7.命題“P-Q”可讀做P蘊(yùn)含Q，其中P、Q是兩個(gè)獨(dú)立的命題.只有當(dāng)命題P成立而命題Q不成立時(shí)，命題"P-Q”的值為false,其它情況均為true.與命題“P-Q”等價(jià)的邏輯關(guān)系式是。A.-1PAQB.PAQC.-1(PVQ)D.-(-QVP).現(xiàn)在有一個(gè)集合，里面包含了字符串"zlymAKIOItxdy”(不含引號(hào))的所有字符，則請(qǐng)問該集合的所有非空真子集的個(gè)數(shù)為A.4095 B.4096 C.4094 D.2046.對(duì)于完全背包問題(給出n種物品和一個(gè)容積為m的背包，每種物品有無限個(gè)，單個(gè)大小為v[i],價(jià)值為w[i],要求選擇適當(dāng)?shù)奈锲贩湃氡嘲?，滿足大小不超過容積且價(jià)值最大)，設(shè)f[i]表示用去i的空間能獲得的最大價(jià)值，倒序枚舉i為使用的空間，正序枚舉j為物品編號(hào)，則可寫出動(dòng)態(tài)轉(zhuǎn)移方程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]).小明要去南美洲旅游，一共乘坐三趟航班才能到達(dá)目的地，其中第1個(gè)航班準(zhǔn)點(diǎn)的概率是0.9，第2個(gè)航班準(zhǔn)點(diǎn)的概率為0.8,第3個(gè)航班準(zhǔn)點(diǎn)的概率為0.9。如果存在第i個(gè)(i=1,2)航班晚點(diǎn)，第i+1個(gè)航班準(zhǔn)點(diǎn)，則小明將趕不上第i+1個(gè)航班，旅行失??；除了這種情況，其他情況下旅行都能成功。請(qǐng)問小明此次旅行成功的概率是A.0.5 B.0.648 C.0.72 D.0.74.以下關(guān)于CSP非專業(yè)級(jí)認(rèn)證與NOIP競(jìng)賽關(guān)系的說法最恰當(dāng)?shù)氖茿.完全無關(guān) B.組織者相同 C.舉辦目標(biāo)相同 D.從屬關(guān)系，CSP從屬于NOIP.關(guān)于信息學(xué)競(jìng)賽涉及算法，以下說法不正確的是A.搜索分為深度優(yōu)先和廣度優(yōu)先兩種，特點(diǎn)是代碼難度低，但都很費(fèi)時(shí)B.模擬是一種最基本的算法，就是按照題目要求做。廣義的模擬還包含其他算法。貪心算法類似于“鼠目寸光”，該算法前提是滿足“部分最優(yōu)組成全局最優(yōu)”D.動(dòng)態(tài)規(guī)劃包含了很多類型和優(yōu)化，動(dòng)態(tài)轉(zhuǎn)移方程是該算法的核心.如圖，小圓圈表示網(wǎng)絡(luò)的結(jié)點(diǎn)，結(jié)點(diǎn)之間的連線表示它們有網(wǎng)線相聯(lián)，連線標(biāo)注的數(shù)字表示該段網(wǎng)線單位時(shí)間內(nèi)可以通過 ：：.??、的最大信息量，現(xiàn)從結(jié)點(diǎn)B向結(jié)點(diǎn)A傳遞信息，信息可以分開”「J—，沿不同的路線同時(shí)傳遞，則單位時(shí)間內(nèi)傳遞的最大信息量為 「、 .A、19B、20C、24D、25.分辨率為1600x900、16位色的位圖，存儲(chǔ)圖像信息所需的空間為A.2812.5KBB.4218.75KB C.4320KB D.2880KB.情境：一位媽媽生了n胞胎，這n個(gè)孩子長(zhǎng)得非常相似，讓人無法辨認(rèn)。一天晚上，媽媽要給這n個(gè)孩子洗澡。媽媽每次從孩子中抓出一個(gè)洗澡，洗完后又把他放回孩子之中，如此重復(fù)n次。問題：若n=10,則在所有的可能中，恰好只有三個(gè)孩子沒有洗澡的可能性約為A.14% B.36% C.31% D.17%二、閱讀程序(以下共有三段程序。每段程序后面有6個(gè)題目，前4題為判斷題，后2題為選擇題。對(duì)于判斷題，選擇A代表正確，B代表錯(cuò)誤；對(duì)于選擇題，請(qǐng)?jiān)贏BCD選項(xiàng)中選擇正確的一項(xiàng)。判斷題每題1分，選擇題每題3分，共30分)①#include<cstdio>#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];}}Cout<<f[n][n]<<endl;return0;}.如果第3行的代碼缺失，程序會(huì)出現(xiàn)編譯錯(cuò)誤。.本程序中f數(shù)組內(nèi)被改變過的元素的值與n無關(guān)，即對(duì)于不同的n，f數(shù)組中不為0的元素值都對(duì)應(yīng)相同.若n=10,對(duì)于任何OWiWn,f[0][i]=1.若n=10,對(duì)于任何OWWn,f[1][i]=1.本程序沒有使用的基本算法是A.模擬 B.遞推 C.遞歸 D.動(dòng)態(tài)規(guī)劃.對(duì)于輸入6，本程序輸出A.5 B.14 C.42 D.132②#include<iostream>#include<algorithm>usingnamespacestd;longintn,k,sum[100001],num=1,f[100001];structrenlongintks,js;};renz[100001];intcmp(rena,renb){returna.ks>b.ks;}intmain(){longinti,j;cin>>n>>k;for(i=1;i<=k;i++){cin>>z[i].ks>>z[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++;}}cout<<f[1]<<endl;}.本程序使用了貪心算法.第23行sort排序后z數(shù)組中的元素按js元素降序排序.以下是對(duì)于本代碼的一段輸入，則對(duì)應(yīng)的輸出是315626411858111525.本代碼的24行換成for(i=1;i<=n;++i),可能會(huì)引發(fā)“數(shù)組越界”錯(cuò)誤.第10至12行程序定義了一個(gè)cmp函數(shù)以用于sort的比較。我們可以用含有以下的一個(gè)選項(xiàng)的程序段來定義適用于該結(jié)構(gòu)體類型的小于運(yùn)算。這個(gè)選項(xiàng)是A.this B.operator C.iterator D.it.本程序的時(shí)間復(fù)雜度是A.O(n) B.O(k) C.O(n?log(n)) D.O(nk)③//注釋：本程序使用一種樹形數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了將讀入的數(shù)據(jù)按照“左子樹<=根<=右子樹”的方法建樹，并輸出樹的深度及后序遍歷。#include<iostream>usingnamespacestd;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(x<tree[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);voidprinthx(intidx){if(idx){printhx(tree[idx].left);printhx(tree[idx].right);cout<<tree[idx].data<<endl;}}intmain(){cin>>n1;for(inti=1;i<=n1;i++){intx;cin>>x;intid=1;if(i==1)NNN(x);elseinsert(x,id);}dfs(1,0);cout<<"deep="<<ans<<endl;printhx(1);return0;}.在本程序中，第6行的數(shù)組必須開到數(shù)據(jù)范圍的結(jié)點(diǎn)數(shù)的4倍以上.存放樹的節(jié)點(diǎn)時(shí)運(yùn)用了指針?biāo)枷?程序第9至14行的NNN函數(shù)作用是給樹增加一個(gè)空節(jié)點(diǎn).將程序第30行和31行交換，不會(huì)對(duì)程序產(chǎn)生影響.一種樹形結(jié)構(gòu)是指A.權(quán)值線段樹 B.樹狀數(shù)組 C.斐波那契堆 口.二叉搜索樹.以下是一個(gè)對(duì)于本程序的輸入，則與之對(duì)應(yīng)的輸出是81439103527ABCDdeep=4deep=6deep=5deep=51422223337774110357935109109910314353541三、補(bǔ)充程序(本大題共含有2篇代碼，共10小題，每小題4分，共40分。請(qǐng)?jiān)诿康佬☆}后所給的四條代碼中選出最恰當(dāng)?shù)囊豁?xiàng)，使這段代碼填入完整程序中對(duì)應(yīng)的空缺處能符合題意。)①《Qjl的比賽》(20分)Qjl是一名神犇，他最近出了一場(chǎng)盛大的AK賽。比賽共含有n(lWnWl00000)題，由于是AK賽，任何人做了任何一道題都能保證AC。但是Qjl身為神犇，要擺神犇的架子，具體做法是對(duì)于不同的題，賦予不同的滿分，這樣會(huì)讓AK者的分?jǐn)?shù)變得好看。不過，他的比賽中不斷會(huì)出現(xiàn)出鍋的情況，也就是題目滿分應(yīng)該被調(diào)整。他會(huì)不斷調(diào)整一些題目的滿分，使之更合理?，F(xiàn)在Qjl需要你編寫程序，幫他滿足兩種操作，如果你寫出了代碼，你有可能會(huì)獲得2147483648%32768分的額外滿分！他首先給你兩個(gè)正整數(shù)n,m，表示題目數(shù)與操作數(shù)；然后他會(huì)給你n個(gè)正整數(shù)，表示這些題目初始的滿分。接下來他會(huì)不斷給你發(fā)m條操作指令：1xyk：表示將題號(hào)e[x,y]的題目的滿分都加上k；2xy：表示詢問題號(hào){[x,y]的所有題目的AK分(即總分和。)請(qǐng)你編寫程序，以享受AK的快感。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;structpoint{intlft,rgt,num,lzy;}a[400401];intb[100001],n,m,i,x,y,z,t;voidbuild(intp,intl,intr){a[p].lft=l;a[p].rgt=r;if(l==r){a[p].num=b[l];return;}build( ① ,l,(l+r)/2);build( ② ,(l+r)/2+1,r);a[p].num=a[p*2].num+a[p*2+1].num;}voiddown(intp){if( ③ ){a[p*2].num+=a[p].lzy*(a[p*2].rgt-a[p*2].lft+1);a[p*2+1].num+=a[p].lzy*(a[p*2+1].rgt-a[p*2+1].lft+1);a[p*2].lzy+=a[p].lzy;a[p*2+1].lzy+=a[p].lzy;④ ;}}voidadd2(intnd,intst,inted,intx){if(st<=a[nd].lft&&ed>=a[nd].rgt){a[nd].num+=⑤ ;a[nd].lzy+=x;return;}down(nd);if(st<=(a[nd].lft+a[nd].rgt)/2)add2(nd*2,st,ed,x);if(ed>=(a[nd].lft+a[nd].rgt)/2+1)add2(nd*2+1,st,ed,x);a[nd].num=a[nd*2].num+a[nd*2+1].num;}intFind(intnd,intl,intr){if( ⑥ )return⑦ ;down(nd);intbb=0;if(l<=(a[nd].lft+a[nd].rgt)/2)bb+=Find(nd*2,l,r);if(r>=(a[nd].lft+a[nd].rgt)/2+1)bb+=Find(nd*2+1,l,r);returnbb;}signedmain(){scanf("%lld%lld",&n,&m);for(i=1;i<=n;i++){scanf("%lld",&b[i]);}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);}else{scanf("%lld%lld",&x,&y);printf("%lld\n",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.a[p].num==0B.a[p].num!=0C.a[p].lay==0D.a[p].lzy!=0.填入④處的代碼是A.a[p].num=0B.a[p].lzy=0C.a[p].num=a[p].lzy=0D.{down(p*2);down(p*2+1);}.填入⑤處的代碼是A.a[nd].rgt-a[nd].lft+1B.a[nd].rgt-a[nd].lftC.x*(a[nd].rgt-a[nd].lft+1)D.x*(a[nd].rgt-a[nd].lft).填入⑥和⑦處的代碼分別是A.l<=a[nd].lft&&a[nd].rgt<=r；a[nd].num<=a[nd].lft&&a[nd].rgt<=r；a[nd].num*(l-r+1)C.a[nd].lft<=l&&r<=a[nd].rgt；a[nd].num*(l-r+1)D.a[nd].lft<=l&&r<=a[nd].rgt；a[nd].num②《奶牛也感染》(20分)每頭奶牛都不想成為被新型病毒感染的奶牛。被所有奶牛接觸的奶牛就是一頭被感染的奶牛。因?yàn)槟膛Ｏ矚g偷偷摸摸地行動(dòng)，所有接觸是單向的，所有奶牛都與自己接觸。奶牛之間的接觸是可以傳遞的—-如果A接觸過B,B接觸過C,那么A也接觸過C。牛欄里共有N頭奶牛，給定一些奶牛之間的接觸關(guān)系，請(qǐng)你算出有多少頭奶牛不幸被感染。輸入的第一行是兩個(gè)用空格分開的整數(shù)N和M。接下來M行每行兩個(gè)用空格分開的整數(shù)A和B，表示A接觸過B。輸出被感染的奶牛的數(shù)量。#include<bits/stdc++.h>usingnamespacestd;structedge{intv,next;}p[50001];intfront[10001],M;voidAdd(intu,intv){++M;p[M].v=v;① ；front[u]=M;}intdfn[10001],low[10001],N,s;stack<int>zhan;intwhich[10001];intOut[10001],id,large[10001];intn,m;intdfs(intx){++N;dfn[x]=low[x]=N;zhan.push(x);for(inti=front[x];i;i=p[i].next){if( ② ){dfs(p[i].v);③}elselow[x]=min(low[x],dfn[p[i].v]);}if(dfn[x]==low[x]){++s;intS=0;intv;do{v=zhan.top();zhan.pop();④++S;}while(x!=v);Large[s]=S;}}intmain()inti,j;scanf("%d%d",&n,&m);for(i=1;i<=m;++i){intx,y;scanf("%d%d",&x,&y);Add(x,y);}for(i=1;i<=n;++i)if(dfn[i]==0)dfs(i);for(i=1;i<=n;++i)for(j=front[i];j;j=p[j].next)if(which[p[j].v]!=which[i])⑤for(i=1;i<=s;++i)if(Out[i]==0){if(id!=0){printf("%d\n",0);return0;}id=i;}printf("%d\n",large[id]);return0;}.①處填入的代碼是A.p[M].next=uB.p[M].next=vC.p[M].next=front[u]D.p[M].next=front[v].②處填入的代碼是A.!dfn[p[i].v]B.dfn[p[i].v]C.low[p[i].v]D.!low[p[i].v].③處填入的代碼是A.dfn[x]=min(dfn[x],dfn[p[i].v]);B.dfn[x]=max(dfn[x],low[p[i].v]);C.low[x]=max(low[x],dfn[p[i].v]);D.low[x]=min(low[x],low[p[i].v]);.④處填入的代碼是A.++s;B.which[v]=s;C.x=zhan.top(),zhan.pop();D.zhan.push(x+v);.⑤處填入的代碼是A.++Out[which[i]]B.++which[Out[i]C.++Out[Out[i]]D.++which[which[i]]說明：試題卷至上一頁結(jié)束，以下為答案和答題卷(不怎么好看，選擇使用)，請(qǐng)?jiān)谙掳l(fā)試題之前把以下兩頁保存到新的文檔后刪除。答案：12345678910ADBBDCDDBD11121314151617181920BAAABBAABC21222324252627282930DBBBBBDBAA31323334353637383940ADDADBCDCB414243DBA

2020CCF非專業(yè)級(jí)別軟件能力認(rèn)證第一輪X卷（CSP-S）提高級(jí)C++語言答題卷認(rèn)證時(shí)間:2020年10月17日14:30-16:30考生注意事項(xiàng):?試題班