noip初賽-模擬賽附答案

noip初賽—模擬賽[復(fù)制]您的姓名：[填空題]*_________________________________1.一個家具公司生產(chǎn)桌子和椅子?，F(xiàn)在有113個單位的木材。每張桌子要使用20個單位的木材，售價是30元；每張椅子要使用16個單位的木材，售價是20元。使用已有的木材生產(chǎn)桌椅（不一定要把木材用光），最多可以賣（）元錢[單選題]*140150156160(正確答案)2.75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂場總共收入700，可知有（）名兒童沒有玩過其中任何一種。[單選題]*15910(正確答案)123.已知隊(duì)列(13，2，11，34，41，77，5，7，18，26，15)，第一個進(jìn)入隊(duì)列的元素是13，則第五個出隊(duì)列的元素是（）。[單選題]*7753441(正確答案)4.對有序數(shù)組{5,13,19,21,37,56,64,75,88，92，100}進(jìn)行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（）。[單選題]*342(正確答案)15.將數(shù)組{18,23,24,16,77,5,33,106，12，-7}中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換（）次。[單選題]*6457(正確答案)6.無向圖G有16條邊，有3個4度頂點(diǎn)、4個3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少有（）個頂點(diǎn)。[單選題]*121511(正確答案)107.約定二叉樹的根節(jié)點(diǎn)深度為1。一棵結(jié)點(diǎn)數(shù)為2020的完全二叉樹的節(jié)點(diǎn)最大深度為（），最大深度的葉子結(jié)點(diǎn)有（）個。[單選題]*10和99711和99811和997(正確答案)10和9988.圖中每條邊上的數(shù)字表示該邊的長度,則從A到E的最短距離是[單選題]*11(正確答案)101249.（）就是把一個復(fù)雜的問題分成兩個或更多的相同類似的子問題，再把子問題分解成更小的子問題……直到最后的子問題可以簡單地直接求解。而原問題的解就是子問題解的并。[單選題]*分治(正確答案)貪心搜索動態(tài)規(guī)劃10.原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串。則字符“AAABBBCCC”共有（）個不同的非空子串。[單選題]*336(正確答案)451211.一個字長為10位的整數(shù)的補(bǔ)碼是1111100001，則它的原碼是（）[單選題]*01111000011000011111(正確答案)1111100001000000011112.無向完全圖是圖中每對頂點(diǎn)之間都恰好有一條邊的簡單圖。已知無向完全圖G有7個頂點(diǎn)，則它共有（）條邊。[單選題]*7424921(正確答案)13.如果樹根算第1層，那么一棵n層的二叉樹最多有（）個節(jié)點(diǎn)。[單選題]*2^n+12^n-1(正確答案)2^n2^(n+1)14.十進(jìn)制小數(shù)125.125對應(yīng)的8進(jìn)制數(shù)是（）[單選題]*100.175100.1175.175175.1(正確答案)15.滿二叉樹的葉節(jié)點(diǎn)個數(shù)為N，則它的節(jié)點(diǎn)總數(shù)為（）。[單選題]*N2N2N-1(正確答案)2N+116.有n名同學(xué)參加學(xué)校組織的郊游活動，已知學(xué)校給這n名同學(xué)的郊游總經(jīng)費(fèi)為A元，與此同時第i位同學(xué)自己攜帶了Mi元。為了方便郊游，活動地點(diǎn)提供B(≥n)輛自行車供人租用，租用第j輛自行車的價格為Cj元，每位同學(xué)可以使用自己攜帶的錢或者學(xué)校的郊游經(jīng)費(fèi)，為了方便賬務(wù)管理，每位同學(xué)只能為自己租用自行車，且不會借錢給他人，他們想知道最多有多少位同學(xué)能夠租用到自行車。

本題采用二分法。對于區(qū)間[l,r]，我們?nèi)≈虚g點(diǎn)mid并判斷租用到自行車的人數(shù)能否達(dá)到mid。判斷的過程是利用貪心算法實(shí)現(xiàn)的。

#include<iostream>

usingnamespacestd;

#defineMAXN1000000

intn,B,A,M[MAXN],C[MAXN],l,r,ans,mid;

boolcheck(intnn){

intcount=0,i,j;

i=(1);

j=1;

while(i<=n){

if(2)

count+=C[j]-M[i];

i++;

j++;

}

return(3);

}

voidsort(inta[],intl,intr){

inti=l,j=r,x=a[(l+r)/2],y;

while(i<=j){

while(a[i]<x)i++;

while(a[j]>x)j--;

if(i<=j){

y=a[i];

a[i]=a[j];

a[j]=y;

i++;

j--;

}

}

if(i<r)sort(a,i,r);

if(l<j)sort(a,l,j);

}

intmain(){

inti;

cin>>n>>B>>A;

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

cin>>M[i];

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

cin>>C[i];

sort(M,1,n);

sort(C,1,B);

l=0;

r=n;

while(l<=r){

mid=(l+r)/2;

if(4){

ans=mid;

l=mid+1;

}else

r=(5);

}

cout<<ans<<endl;

return0;

}[單選題]*n-nnn-nn-2n-nn+1(正確答案)n-nn-117.標(biāo)題[單選題]*M[i]>C[j]M[i]<C[j](正確答案)M[I]>=C[j]M[i]<=C[j]18.標(biāo)題[單選題]*count<=A(正確答案)count>Acount>=Acount<A19.標(biāo)題[單選題]*check(mid-1)check(mid)(正確答案)check(mid+1)check(mid)+120.標(biāo)題[單選題]*mid+1mid-i-1mid-i+1mid-1(正確答案)21.給定一個字符串S（S僅包含大小寫字母），下面的程序?qū)中的每個字母用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結(jié)果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S，第二個字符串S’由26個字母組成，它是a-z的任一排列，大小寫不定，S’規(guī)定了每個字母對應(yīng)的替換字母：S’中的第一個字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S’中的第二個字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；……以此類推。

#include<iostream>

#include<string.h>

charchange[26],str[5000];

usingnamespacestd;

voidCheckChangeRule(void){

inti;

for(i=0;i<26;i++){

if(1)

change[i]-='A'-'a';

}

}

voidChangeString(void){

inti;

for(i=0;i<strlen(str);i++){

if(2)

str[i]=change[str[i]-'A']-'a'+'A';

else

3;

}

}

intmain(){

inti;

cin>>str;

cin>>change;

CheckChangeRule();

4;

cout<<str<<endl;

return0;

}[單選題]*change[i]>'A'&&change[I]<'Z'change[i]<'A'&&change[I]>'Z'change[i]>='A'&&change[i]<='Z'(正確答案)change[i]<='A'&&change[I]>='Z'22.標(biāo)題[單選題]*str[I]<'A'&&str[I]>'Z'str[I]<='A'&&str[I]>='Z'str[i]>='A'&&str[i]<='Z'(正確答案)str[i]>'A'&&str[i]<'Z'23.標(biāo)題[單選題]*str[i]=change[str[i]-'a'+1]str[i]=change[str[i]-'a'](正確答案)str[i]=change[str[i]-'a'-1]str[i]=change[str[I]+'a']24.標(biāo)題[單選題]*ChangeString()-1ChangeString(0)ChangeString()(正確答案)ChangeString(1)25.題目描述

給出一個正整數(shù)，判斷這個數(shù)是否是質(zhì)數(shù)。

輸入:

一個正整數(shù)n(1≤n≤10000)。

輸出:

如果n是質(zhì)數(shù)，輸出"YES"；否則，輸出"NO"。

輸入樣例:

10

輸出樣例:

NO

#include<stdio.h>

intmain(){

int1;

scanf("%d",&n);

if(n==2)puts(2);

elseif(3||n%2==0)puts("NO");

else

{

i=3;

while(i*i<=n){

if(4)