


版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
、單項(xiàng)選擇題(共15題,每題1.5分,共計(jì)22.5分;每題有且僅有一個(gè)正確選項(xiàng))1?從()年開(kāi)始,NOIP競(jìng)賽將不再支持Pascal語(yǔ)言。2020B.2021C.2022D.20232?在8位二進(jìn)制補(bǔ)碼中,10101011表示的數(shù)是十進(jìn)制下的()。A.433?分辨率為1600x900、16位色的位圖,存儲(chǔ)圖像信息所需的空間為()。2017年10月1日是星期日,1949年10月1日是()。A.星期三B.星期日C.星期六D.星期二設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊(n<m)的連通圖,必須刪去G的()條邊,才能使得G變成一棵樹(shù)。A.m-n+1B.m-nC.m+n+1D.n—m+1若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式:T(N)=2T(N/2)+NlogNT(1)=1則該算法的時(shí)間復(fù)雜度為()。A.O(N)B.O(NlogN)C.O(Nlog2N)D.O(N2)表達(dá)式a*(b+c)*d的后綴形式是()。A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d由四個(gè)不同的點(diǎn)構(gòu)成的簡(jiǎn)單無(wú)向連通圖的個(gè)數(shù)是()。A.32B.35C.38D.41將7個(gè)名額分給4個(gè)不同的班級(jí),允許有的班級(jí)沒(méi)有名額,有()種不同的分配方案。A.60B.84C.96D.120若f[0]=0,f[1]=1,f[n+1]=(f[n]+f[n-1])/2,則隨著i的增大,f[i]將接近和()。A.1/2B.2/3D.1設(shè)A和B是兩個(gè)長(zhǎng)為n的有序數(shù)組,現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組,請(qǐng)問(wèn)任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做()次比較。
在n(n>=3)枚硬幣中有一枚質(zhì)量不合格的硬幣(質(zhì)量過(guò)輕或質(zhì)量過(guò)重),如果只有一架天平可以用來(lái)稱(chēng)重且稱(chēng)重的硬幣數(shù)沒(méi)有限制,下面是找出這枚不合格的硬幣的算法。請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中。AXUYAZn|A|算法Coin(A,n)kn/3將A中硬幣分成X,YZ三個(gè)集合,使得|X|=|Y|=k,|Z|=n-2kifW(X)工W(Y)//W(X),W(Y)分別為X或Y的重量thenelseifn>2thengoto1ifn=2then任取A中1枚硬幣和拿走硬幣比較,若不等,則它不合格;若相等,貝UA中剩下的硬幣不合格ifn=1thenA中硬幣不合格正確的填空順序是()。A.b,c,aB.c,b,aC.c,a,bD.a,b,c在正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示,第一行的數(shù)為a11;第二行的數(shù)從左到右依次為a21,a22;…第n行的數(shù)為an1,an2,…,ann。從a11開(kāi)始,每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個(gè)數(shù)a(i+1)j和a(i+1)(j+1)。用動(dòng)態(tài)規(guī)劃算法找出一條從a11向下通到an1,an2,…,ann中某個(gè)數(shù)的路徑,使得該路徑上的數(shù)之和達(dá)到最大。令C[i,j]是從a11到aij的路徑上的數(shù)的最大和,并且C[i,0]=C[0,j]=0,則C[i,j]=()。max{C[i-1,j-1],C[i-1,j]}+aijC[i-1,j-1]+c[i-1,j]max{C[i-1,j-1],C[i-1,j]}+1max{C[i,j-1],C[i-1,j]}+aij小明要去南美洲旅游,一共乘坐三趟航班才能到達(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)問(wèn)小明此次旅行成功的概率是()。歡樂(lè)噴球:兒童游樂(lè)場(chǎng)有個(gè)游戲叫“歡樂(lè)噴球”,正方形場(chǎng)地中心能不斷噴出彩色乒乓球,以場(chǎng)地中心為圓心還有一個(gè)圓軌道,軌道上有一列小火車(chē)在勻速運(yùn)動(dòng),火車(chē)有六節(jié)車(chē)廂。假設(shè)乒乓球等概率落到正方形場(chǎng)地的每個(gè)地點(diǎn),包括火車(chē)車(chē)廂。小朋友玩這個(gè)游戲時(shí),只能坐在同一個(gè)火車(chē)車(chē)廂里,可以在自己的車(chē)廂里撿落在該車(chē)廂內(nèi)的所有乒乓球,每個(gè)人每次游戲有三分鐘時(shí)間,則一個(gè)小朋友獨(dú)自玩一次游戲期望可以得到()個(gè)乒乓球。假設(shè)乒乓球噴出的速度為2個(gè)/秒,每節(jié)車(chē)廂的面積是整個(gè)場(chǎng)地面積的1/20。
二、不定項(xiàng)選擇題(共5題,每題1.5分,共計(jì)7.5分;每題有一個(gè)或多個(gè)正確選項(xiàng),多選或少選均不得分)以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有()。A.冒泡排序B.快速排序C.歸并排序D.堆排序?qū)τ谌霔m樞驗(yàn)閍,b,c,d,e,f,g的序列,下列()不可能是合法的出棧序列。A.a,b,c,d,e,f,gB.a,d,c,b,e,g,fC.a,d,b,c,g,f,eD.g,f,e,d,c,b,a下列算法中,()是穩(wěn)定的排序算法。A.快速排序B.堆排序C希爾排序D.插入排序以下是面向?qū)ο蟮膯J級(jí)語(yǔ)言的是()。A.匯編語(yǔ)言以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)是()。A.奧斯卡獎(jiǎng)B.圖靈獎(jiǎng)C.諾貝爾獎(jiǎng)D.王選獎(jiǎng)三、問(wèn)題求解(共2題,每題5分,共計(jì)10分)如圖所示,共有13個(gè)格子。對(duì)任何一個(gè)格子進(jìn)行一次操作,會(huì)使得它自己以及和它上下左右相鄰的格子中的數(shù)字改變(由1變0,或由0變1)。現(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?,至少需要3次操作。如圖所示,A到B是連通的。假設(shè)刪除一條細(xì)的邊的代價(jià)是1,刪除一條粗的邊的代價(jià)是2,要讓A、B不連通,最小代價(jià)是4(2分),最小代價(jià)的不同方案數(shù)是9(3分)。(只要有一條刪除的邊不同,就是不同的方案)四、閱讀程序?qū)懡Y(jié)果(共4題,每題8分,共計(jì)32分)1.#includeusingnamespacestd;intg(intm,intn,intx){intans=0;inti;if(n==1)return1;for(i=x;i<=m/n;i++)ans+=g(m-i,n-1,i);returnans;
intmain(){intt,m,n;cin>>m>>n;cout<<g(m,n,0)<<endl;return0;}輸入:84輸出:152.#includeusingnamespacestd;intmain(){intn,i,j,x,y,nx,ny;inta[40][40];for(i=0;i<40;i++)for(j=0;j<40;j++)a[i][j]=0;cin>>n;y=0;x=n-1;n=2*n-1;for(i=1;i<=n*n;i++){a[y][x]=i;ny=(y-1+n)%n;nx=(x+1)%n;if((y==0&&x==n-1)||a[ny][nx]!=0)y=y+1;else{y=ny;x=nx;}}for(j=0;j<n;j++)cout<<a[0][j]<<cout<<endl;return0;}輸入:3輸出:172418153.#includeusingnamespacestd;intn,s,a[100005],t[100005],i;voidmergesort(intl,intr){if(l==r)return;
intmid=(I+r)/2;intp=I;inti=I;intj=mid+1;mergesort(I,mid);mergesort(mid+1,r);while(i<=mid&&j<=r){if(a[j]<a[i]){i+1;s+=mid-t[p]=a[j];i+1;P++;P++;j++;i++;i++;}else{t[p]=a[i];p++;}}while(i<=mid){i++;}else{t[p]=a[i];p++;}}while(i<=mid){t[p]=a[i];P++;i++;}while(j<=r){t[p]=a[j];P++;j++;}for(i=l;i<=r;i++)a[i]=t[i];}intmain(){cin>>n;for(i=1;i<=n;i++)cin>>a[i];mergesort(1,n);cout<<s<<endl;return0;}輸入:6263451輸出:84.#includeusingnamespacestd;intmain(){intn,m;cin>>n>>m;intx=1;inty=1;intdx=1;intdy=1;intent=0;while(ent!=2){ent=0;x=x+dx;y=y+dy;if(x==1||x==n){++cnt;dx=-dx;}if(y==1||y==m){++cnt;dy=-dy;}}cout<<x<<""<<y<<endl;return0;}輸入1:43輸出1:13(2分)輸入2:20171014輸出2:20171(3分)輸入3:987321輸出3:1321(3分)五、完善程序(共2題,每題14分,共計(jì)28分)1.大整數(shù)除法:給定兩個(gè)正整數(shù)p和q,其中p不超過(guò)10100,q不超過(guò)100000,求p除以q的商和余數(shù)。(第一空2分,其余3分)輸入:第一行是p的位數(shù)n,第二行是正整數(shù)p,第三行是正整數(shù)q。輸出:兩行,分別是p除以q的商和余數(shù)。#includeusingnamespacestd;
intp[100];intn,i,q,rest;charc;intmain(){cin>>n;for(i=0;i<n;i++){cin>>c;p[i]=c-‘O'}cin>>q;rest=p[0];i=1;while(rest<q&&i<n){rest=rest*10+p[i];i++;}if(rest<q)cout<<0<<endl;else{cout<<rest/q;while(i<n){rest=rest%q*10+p[i];i++;cout<<rest/q;}cout<<endl;cout<<rest%q<<endl;return0;}2.最長(zhǎng)路徑:給定一個(gè)有向五環(huán)圖,每條邊長(zhǎng)度為1,求圖中的最長(zhǎng)路徑長(zhǎng)度。(第五空2分,其余3分)輸入:第一行是結(jié)點(diǎn)數(shù)n(不超過(guò)100)和邊數(shù)m,接下來(lái)m行,每行兩個(gè)整數(shù)a,b,表示從結(jié)點(diǎn)a到結(jié)點(diǎn)b有一條有向邊。結(jié)點(diǎn)標(biāo)號(hào)從0到(n-1)。輸出:最長(zhǎng)路徑長(zhǎng)度。提示:先進(jìn)行拓?fù)渑判?,然后按照拓?fù)渑判蛴?jì)算最長(zhǎng)路徑。#includeusingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph[100][100];II用鄰接矩陣存儲(chǔ)圖intdegree[100];II記錄每個(gè)結(jié)點(diǎn)的入度intlen[100];II記錄以各結(jié)點(diǎn)為終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度
intqueue[100];//存放拓?fù)渑判蚪Y(jié)果intmain(){cin>>n>>m;for(i=0;i<n;i++)for(j=0;j<n;j++)graph[i][j]=0;for(i=0;i<n;i++)degree[i]=0;for(i=0;i<m;i++){cin>>a>>b;graph[a][b]=1;degree[b]++;}tail=0;for(i=0;i<n;i++)if(degree[i]==0){queue[tail]=i;tail++;}head=0;while(tail<n-1){for(i=0;i<n;i++)if(graph[qu
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 共情教育塑造孩子情感智商的必由之路
- 智慧辦公樓宇的水資源管理與節(jié)能創(chuàng)新
- 醫(yī)學(xué)倫理與心理關(guān)懷的結(jié)合
- BJ-13-生命科學(xué)試劑-MCE
- 2024年天津市河北區(qū)九上化學(xué)期末聯(lián)考試題含解析
- 石家莊財(cái)經(jīng)職業(yè)學(xué)院《攝影攝像基礎(chǔ)》2023-2024學(xué)年第一學(xué)期期末試卷
- 新疆博樂(lè)市第九中學(xué)2025屆九年級(jí)化學(xué)第一學(xué)期期末質(zhì)量跟蹤監(jiān)視模擬試題含解析
- 湖北鐵道運(yùn)輸職業(yè)學(xué)院《西方史學(xué)史》2023-2024學(xué)年第一學(xué)期期末試卷
- 公共衛(wèi)生設(shè)施建設(shè)在城市社區(qū)安全防范體系中的應(yīng)用與研究報(bào)告
- 共享出行市場(chǎng)2025年共享電動(dòng)平衡車(chē)商業(yè)模式創(chuàng)新報(bào)告:競(jìng)爭(zhēng)格局演變
- 血液凈化護(hù)理知識(shí)競(jìng)賽考試題庫(kù)500題(含答案)
- 帶孩子免責(zé)協(xié)議書(shū)范本
- 守護(hù)生命之窗-氣管切開(kāi)患者護(hù)理
- 信息技術(shù)咨詢(xún)服務(wù)合同5篇
- 2022年6月天津市普通高中學(xué)業(yè)水平合格性考試化學(xué)試卷
- 生豬購(gòu)銷(xiāo)合同協(xié)議
- 蘇教版六年級(jí)科學(xué)下冊(cè)期末測(cè)試卷及答案
- 人教版高中物理(必修一)同步講義+練習(xí)4.6 超重和失重(含解析)
- 血糖儀操作技術(shù)并發(fā)癥
- 2022年江蘇省常州市強(qiáng)基計(jì)劃選拔數(shù)學(xué)試卷(附答案解析)
- 三年級(jí)數(shù)學(xué)下冊(cè)計(jì)算題大全(每日一練共18份)
評(píng)論
0/150
提交評(píng)論