(NOIP)提高級語言試題附答案

(NOIP)提高級語言試題[復(fù)制]考生注意事項:

●試題紙共有10頁，答題紙共有1頁，滿分100分請在答題紙上作答，寫在試題紙上的一律無效。

●不得使用任何電子設(shè)備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共15題，每題2分，共計30分;每題有且僅有一個正確選項）1.下列有關(guān)信息的說法，正確的是（）[單選題]*A.信息在計算機內(nèi)部采用二進制代碼表示(正確答案)B.只有最新的信息才具有價值C.只能借助計算機才能處理信息D.信息不能脫離它所反應(yīng)的事物被存儲答案解析：A2八位二進制補碼下，01010100與11110010的差是多少()[單選題]*A.98B.97(正確答案)C.70D-97答案解析：B

/item/%E8%A1%A5%E7%A0%81/6854613?fr=aladdin3.分辨率為2560×1440、256位色圖，存儲圖像信息所需的空間為（）。[單選題]*A.255.5MBB.256MBC.112.5MB(正確答案)D.128MB答案解析：C

2560×1440×256÷8÷1024÷1024=112.54.設(shè)G是有n個結(jié)點、m條邊（n≤m）的連通圖，必須刪去G的（）條邊，才能使得G變成一棵樹。[單選題]*A.n–m+1(正確答案)B.m+n+1C.m–nD.m–n+1答案解析：A

樹的邊數(shù)=點數(shù)-1=n-1,所以就要減去m-n+15.若f[0]=0,f[1]=1,f[n+1]=((f[n]+f[n-1]))/2，則隨著i的增大，f[i]將接近于()。[單選題]*A.1/2B.2/3(正確答案)C.(√5-1)/2D.1答案解析：B

6.以比較作為基本運算，在N個數(shù)中找最小數(shù)的最少運算次數(shù)為（）。[單選題]*A.NB.N-1(正確答案)C.N^2DlogN答案解析：B

提示：比較次數(shù)7.有以下程序

#include<iostream>

usingnamespacestd;

intmain()

{

intk=6,n=2;

while(n<k)

{

n++;

if(n%3!=0)

continue;

k--;

}

cout<<k<<","<<n<<endl;

return0;

}[單選題]*A.4,5B5,5(正確答案)C6,5D4.6答案解析：C

tips：自己手模8.將47個名額分給4個不同的班級，允許有的班級沒有名額，有（）種不同的分配方案。[單選題]*A.19600(正確答案)B.20400C.14400D.25500答案解析：A

將47個名額分給4個班級，因為每個班級有可能取0個，所以先加上4個名額，保證滿足插板法（即每個班級至少1個）。于是運用插板法51個球，50個空，一共插3塊

故答案為C(50,3)=196009.以下排序算法在最壞情況下時間復(fù)雜度最優(yōu)的是（）。[單選題]*A.冒泡排序B.快速排序C.堆順序(正確答案)D.桶排序答案解析：C

冒泡排序快速排序堆順序桶排序

最壞O(n2)O(n2)

O(nlogn)O(n2)

最優(yōu)O(n)O(nlogn)O(nlogn)O(n+k)10.一個盒子中分別有標號1，1，2，3，4共五張卡片，每次抽一張卡片后放回，小明想知道抽七張卡片至少抽到兩次1的概率為（）[單選題]*A.75209/78125(正確答案)B.14653/15625C.75210/78125D.14656/15625答案解析：考慮逆向思維

至少抽到兩次1的反面是只抽到一次1和一次也沒抽到

只抽到一次1的概率=(1/5)*(3/5)6

一次也沒抽到=(3/5)7

所以總概率為1-以上兩者之和=1-2916/7812511.在1和2020之間不能被4，5，6三個數(shù)任意一個數(shù)整除的有（）個。[單選題]*A.941B.940C.942(正確答案)D.943答案解析：C

2020

能被4整除的個數(shù)為：2020/4=505個

能被5整除個數(shù)為2020/5=404個

能被6整除，2020/6=336個

能被4和5整除，2020/20=101個

能被4和6整除，2020/12=168個

能被5和6整除的個數(shù)為2020/30=67個

能被4，5和6同時整除有2020/60=33個

所以，能被4或5或6整除的個數(shù)的計算應(yīng)該是505+404+336-101-168-67+33=942個。12.TCP協(xié)議屬于哪一層協(xié)議().[單選題]*A.應(yīng)用層B.網(wǎng)絡(luò)層C.傳輸層(正確答案)D.數(shù)據(jù)鏈路層答案解析：C

14.假設(shè)一臺抽獎機中有紅、藍兩色的球，任意時刻按下抽獎按鈕，會有1/3的概率抽中紅球，2/3的概率抽中藍球。有足夠多的人每人都用這臺抽獎機抽獎，假如他們的策略均為：抽中紅球則繼續(xù)抽球，抽中藍球則停止。最后每個人都把自己獲得的所有球放到一個大箱子里，最終大箱子里的紅球與藍球的比例接近于（）。[單選題]*A.1:2(正確答案)B.2:1C.1:3D.1:1答案解析：A

因為每次抽取都是有1/3的概率抽到紅球，與怎么抽無關(guān)。

所以為1：214.記T為一隊列，初始時為空，現(xiàn)有n個總和不超過50的正整數(shù)依次入列。如果無論這些數(shù)具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數(shù)之和恰好為11，那么n的最小值是()。[單選題]*A.28B.29(正確答案)C.30D.31答案解析：設(shè)數(shù)列i項的前綴和bi（bi不相同），可知0<bi<=50,那么為了不出現(xiàn)11，前綴和應(yīng)為{1,12}{2,13}..{10,21}

{22,33}{23,34}..{32,43}

{44}{45}{46}{47}{48}{49}{50}共28個集合，每個集合取一個可以不取到11，所以至少再取一個即29個15.假設(shè)某算法的計算時間表示為遞推關(guān)系式

T(N)=2T(N/4)+√Nlog2N

T(1)=1

則算法的時間復(fù)雜度為（）。[單選題]*

orz(正確答案)

>^<

qaq

=-=答案解析：二、閱讀程序(程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填√錯誤填×；除特殊說明外，判斷題1.5分，選擇題4分，共計40分)16.

1#include<iostream>

2usingnamespacestd;

3intdata[10],i,j,cnt,n,m;

4

5intmain(){

6

cin>>n>>m;

7

for(i=1;i<=n;++i)

8

cin>>data[i];

9

for(i=1;i<=n;++i){

10

cnt=0;

11

for(j=1;j<=n;++j)

12

if((data[i]<data[j])||(data[j]==data[i]&&j<i))

13

cnt++;

14

if(cnt==m)

15

cout<<data[i]<<endl;

16

}

17

return0;

18}

●判斷題

1）（1分）當(dāng)m=n時，程序沒有輸出___

。

2）（1分）當(dāng)m<n時，程序輸出僅為一行___。

3）把第十四行的’<’改成’>’對程序輸出結(jié)果沒有影響

___。

4）程序目標是在n個元素的序列中找出第m大的元素

___。

選擇題

5）若輸入的data數(shù)組時一個嚴格單調(diào)遞減的數(shù)列，該程序的時間復(fù)雜度為___

A.O(nlogn)

B(n)

C(n^2)

D(logn)

6)（3分）

輸入52

96-801687

輸出為___

A.96

B.-8

C.16

D.87[填空題]*空1答案：√空2答案：√空3答案：√空4答案：×空5答案：C空6答案：C17.

1#include<bits/stdc++.h>

2usingnamespacestd;

3#definelllonglong

4#definerep(i,a,b)for(registerinti=a,end##i=b;i<=end##i;++i)

5structNode

6{

7

intw,v,next;

8}e[100000];

9inthead[100010],in[3000],dp[3000];

10intvis[10000];

11intcnt;

12voidadd(intu,intv,intw)

13{

14

cnt++;

15

e[cnt].v=v;

16

e[cnt].w=w;

17

e[cnt].next=head[u];

18

head[u]=cnt;

19}

20intn,m;

21inttopo()

22{

23

queue<int>Q;

24

rep(i,1,n)dp[i]=0;

25

rep(i,1,n)if(in[i]==0)Q.push(i);

26

dp[1]=0;

27

vis[1]=1;

28

while(!Q.empty())

29

{

30

intu=Q.front();Q.pop();

31

for(inti=head[u];i;i=e[i].next)

32

{

33

intv=e[i].v;

34

vis[v]|=vis[u];

35

if(vis[v])

36

dp[v]=max(dp[v],dp[u]+e[i].w);

37

in[v]--;

38

if(!in[v])Q.push(v);

39

}

40}

41

return0;

42}

43intmain()

44{

45

scanf("%d%d",&n,&m);

46

rep(i,1,m)

47

{

48

intx,y,z;

49

scanf("%d%d%d",&x,&y,&z);

50

add(x,y,z);

51

in[y]++;

52

}

53

topo();

54

if(!vis[n])printf("%d",-1);

55

else

56

printf("%d\n",dp[n]);

57

}

1.(1分)輸入的x和z值應(yīng)在[0,n-1]的范圍內(nèi)___

2.(1分)輸入的x和y值應(yīng)在[0,n-1]的范圍內(nèi)___

3.(2分)若輸入的x和y和z均在[0,n-1]的范圍內(nèi)，則對于任意0<=i<n都有0<=in[i]<=n___

4.(2分)將第33行的"vis[v]|=vis[u]"改為"vis[v]=true",程序輸出結(jié)果不變___

5.(4分)當(dāng)n=50時,則max(in[i])(0<=i<=n)為___

6.(4分)此程序的時間復(fù)雜度是___[填空題]*空1答案：×空2答案：√空3答案：√空4答案：×空5答案：49空6答案：O(n)答案解析：x,y為點，z為邊權(quán)；

in[]數(shù)組為入度；

拓撲排序復(fù)雜度O(n)18.

1#include<iostream>

2#include<cstdio>

3#include<algorithm>

4usingnamespacestd;

5intn,el,x,ans;

6structE

7{

8

inta,b,t;

9}e[100];

10ints[100];

11intcmp(Ea,Eb)

12{

13

returna.t<b.t;

14}

15intfather(intx)

16{

17

returnx==s[x]?x:s[x]=father(s[x]);

18}

19inttogether(inta,intb)

20{

21

if(b==s[b])

22

{

23

s[b]=a;

24

}

25

else

26

{

27

together(a,s[b]);

28

}

29}

30intKruskal()

31{

32

sort(e+1,e+el+1,cmp);

33

for(inti=1;i<=el;i++)

34

if(father(s[e[i].a])!=father(s[e[i].b]))

35

{

36

together(s[e[i].a],s[e[i].b]);

37

ans+=e[i].t;

38

}

39}

40intmain()

41{

42

cin>>n;

43

for(inti=1;i<=n;i++)

44

for(intj=1;j<=n;j++)

45

{

46

scanf("%d",&x);

47

if(i>j)

48

{

49

e[++el].a=i;

50

e[el].b=j;

51

e[el].t=x;

52

}

53

}

54

for(inti=1;i<=el;i++)

55

s[i]=i;

56

Kruskal();

57

printf("%d",ans);

58}

●判斷題

1）（1分）在任何情況下，el=n*n÷2___。

2）（1分）將55行改為s[i]=0不會影響結(jié)果___。

3）對于任意0<i<=n都有0<s[i]<=n___。

4）對于任意0<i<=n都有0<e[i].t<=n___。

●選擇題

5）第三十行函數(shù)的時間復(fù)雜度為___

A.O(el)B.O(el2)C.O(ellog2el)D.(log2el)

6)將第四十七行去掉將會___

A.使ans偏大B.使ans偏小C.不改變結(jié)果D.時間復(fù)雜度增大[填空題]*空1答案：×空2答案：×空3答案：√空4答案：×空5答案：C空6答案：C三、完善程序（單選題，每小題3分，共計30分）19.

奶牛Bessie隔著柵欄來回走，當(dāng)她走過某個地方，這里的一段柵欄就被刷上了涂料。Bessie從柵欄上的位置0開始，并且遵循著一個N次移動的次序(1<=N<=100,000)。例如“10L”表示Bessie向左移動了10個單位長度，“15R”表示Bessie向右移動了15個單位長度?，F(xiàn)給出Bessie所有移動的列表，F(xiàn)armerJohn想要知道哪些區(qū)域的柵欄至少涂了兩層涂料。Bessie在她的行走中最遠到達距起始點1,000,000,000個單位長度。

第1行：一個整型數(shù)N。

第2..N+1行：每行描述了Bessie的N次移動中的一次，例如“15L”。

試補全程序

1#include<iostream>

2#include<cstdio>

3#include<algorithm>

4usingnamespacestd;

5intn,loc,x,ans;

6inta[100005],b[100005],c[100005],d[100005];

7chardir;

8intmain()

9{

10

scanf("%d",&n);

11

++n;

12

b[0]=a[0]=0;

13

for(inti=2;i<=n;i++)

14

{

15

scanf("%d%c",&x,&dir);

16

if(dir=='R')loc+=x;

17

if(dir=='L')loc-=x;

18

①;

19

}

20

sort(a+1,a+1+n);

21

intm=②;

22

for(inti=1;i<=n;i++)

23

{

24

b[i]=lower_bound(a+1,a+1+m,b[i])-a;

25

}

26

for(inti=2;i<=n;i++)

27

{

28

if(b[i]>b[i-1])

29

{

30

③

31

}

32

else

33

{

34

④

35

}

36

}

37

for(inti=1;i<=n;i++)

38

{

39

d[i]=d[i-1]+c[i];

40

if(d[i]>=2)⑤;

41

}

42

printf("%d",ans);

43

return0;

44}

1.①處應(yīng)填（___

）

A.b[i]=a[i]=x

B.b[i]=a[i]=loc

C.b[i]=loc,a[i]=x

D.a[i]=loc,b[i]=x

2.②處應(yīng)填（___

）

A.unique(a+1,a+1+n)-a

B.unique(a+1,a+1+n)-(a+1)

C.unque(a+1,a+1+n)

D.unque(a,a+n)

3.③處應(yīng)填（___

）

A.c[b[i-1]]++;c[b[i]+1]--;

Bc[b[i-1]]--;c[b[i]+1]++;

C.c[b[i-1]]--;c[b[i]]++;

D.c[b[i-1]]++;c[b[i]]--;

4.④處應(yīng)填（___

）

A.c[b[i-1]]++;c[b[i]+1]--;

Bc[b[i-1]]--;c[b[i]+1]++;

C.c[b[i-1]]--;c[b[i]]++;

D.c[b[i-1]]++;c[b[i]]--;

5.⑤處應(yīng)填（___

）

A.ans+=a[i+1]

B.ans+=a[i+1]+a[i]

C.ans+=a[i+1]-a[i]

D.ans+=a[i+1]-a[i]+1[填空題]*空1答案：B空2答案：B空3答案：D空4答案：C空5答案：A20.

老板需要你幫忙澆花。給出N滴水的坐標，y表示水滴的高度，x表示它下落到x軸的位置。

每滴水以每秒1個單位長度的速度下落。你需要把花盆放在x軸上的某個位置，使得從被花盆接著的第1滴水開始，到被花盆接著的最后1滴水結(jié)束，之間的時間差至少為D。

我們認為，只要水滴落到x軸上，與花盆的邊沿對齊，就認為被接住。給出N滴水的坐標和D的大小，請算出最小的花盆的寬度W。

輸入

第一行2個整數(shù)N和D。

第2..N+1行每行2個整數(shù)，表示水滴的坐標(x,y)。

#include<bits/stdc++.h>

usingnamespacestd;

structnode{

intx,y;

}a[100001];

noderise[100000],reduce[100000];

intn,fuck;

boolcomp1(nodex,nodey)

{

returnx.x<y.x;

}

intmain()

{

cin>>n>>fuck;

intm1=0,m2=9999999;

for(inti=1;i<=n;++i)

{

cin>>a[i].x>>a[i].y;

if(①)m1=a[i].y;

if(a[i].y<m2)m2=a[i].y;

}

if(m1-m2<fuck)

{

cout<<-1<<endl;

return0;

}

sort(a+1,a+1+n,comp1);

intnow1=0,m=9999999,now2=0;

reduce[now2].y=9999999;

for(inti=1;i<=n;++i)

{

if(a[i].y>=rise[now1].y)

{

rise[++now1].y=a[i].y;

rise[now1].x=a[i].x;

}

else

{

②

{

now1--;

}

rise[++now1].x=a[i].x;

rise[now1].y=a[i].y;

}

if(③)

{

for(inti=1;i<=now1;++i)

{

if(rise[now1].y-rise[i].y>=fuck)

{

if(rise[now1].x-rise[i].x<m)m=rise[now1].x-rise[i].x;

}

elsebreak;

}

}

if(reduce[now2].y>=a[i].y)

{

reduce[++now2].y=a[i].y;

reduce[now2].x=a[i].x;

}