公众号内回复【NOIP2010S】即可获取下载链接,直接打印电子版让孩子做即可,文件包含
与十六进制数 A1.2等值的十进制数是( )
本题共 1.5 分
一个字节(byte)由( )个二进制组成。
本题共 1.5 分
以下逻辑表达式的值恒为真的是( )。
本题共 1.5 分
Linux下可执行文件的默认扩展名是( )。
本题共 1.5 分
如果在某个进制下等式7*7=41
成立,那么在该进制下等式12*12
=( )也成立。
本题共 1.5 分
提出“存储程序”的计算机工作原理的是( )。
本题共 1.5 分
前缀表达式+ 3 * 2 + 5 12
的值是( )。
本题共 1.5 分
主存储器的存取速度比中央处理器(CPU)的工作速度慢的多,从而使得后者的效率受到影响。而根据局部性原理,CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是,为了提高系统整体的执行效率,在CPU中引入了( )。
本题共 1.5 分
完全二叉树的顺序存储方案,是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上,则第k号结点的父结点如果存在的话,应当存放在数组中的( )号位置。
本题共 1.5 分
以下竞赛活动中历史最悠久的是( )。
本题共 1.5 分
素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的可能是( )。
本题共 1.5 分
Pascal语言,C语言和C++语言都属于( )。
本题共 1.5 分
原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有( )。
本题共 1.5 分
在整数的补码表示法中,以下说法正确的是( )。
本题共 1.5 分
一颗二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结点的左子树的结点个数可能是( )。
本题共 1.5 分
在下列HTML语句中,可以正确产生一个指向NOI官方网站的超链接的是( )。
本题共 1.5 分
关于拓扑排序,下列说法正确的是( )。
本题共 1.5 分
一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、(0,3,0)、(2,0,0)的平面的法线是( )。
本题共 1.5 分
双向链表中有两个指针域llink和rlink,分别指向该结点的前驱及后继。设p指向链表中的一个结点,他的左右结点均为非空。现要求删除结点p,则下列语句序列中正确的是( )。
本题共 1.5 分
今年(2010年)发生的事件有( )。
本题共 1.5 分
LZW编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用于后继信息的编码。 举例说明,考虑一个待编码的信息串:“xyx yy yy xyx”。初始词典只有3个条目,第一个为x,编码为1;第二个为y,编码为2;第三个为空格,编码为3;于是串“xyx”的编码为1-2-1(其中-为编码分隔符),加上后面的一个空格就是1-2-1-3。但由于有了一个空格,我们就知道前面的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到词典里,编码为4,然后按照新的词典对后继信息进行编码,以此类推。于是,最后得到编码:1-2-1-3-2-2-3-5-3-4。 我们可以看到,信息被压缩了。压缩好的信息传递到接受方,接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的3个条目如上述,接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6,则解码后的信息串是“ ____”。
答案:
本题共 5 分
无向图G有7个顶点,若不存在由奇数条边构成的简单回路,则它至多有____条边。
答案:
本题共 5 分
记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________。
答案:
本题共 5 分
#include<iostream>
using namespace std;
int main()
{
const int SIZE=10;
int data[SIZE],i,j,cnt,n,m;
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>data[i];
for(i=1;i<=n;i++)
{
cnt=0;
for(j=1;j<=n;j++)
if( (data[i]<data[j]) || (data[j]==data[i] && j<i) )
cnt++;
if (cnt==m)
cout<<data[i]<<endl;
}
return 0;
}
输入: 5 2 96 -8 0 16 87 输出:_______
答案:
本题共 7 分
#include<iostream>
using namespace std;
int main()
{
const int SIZE=100;
int na,nb,a[SIZE],b[SIZE],i,j,k;
cin>>na;
for(i=1;i<=na;i++)
cin>>a[i];
cin>>nb;
for(i=1;i<=nb;i++)
cin>>b[i];
i=1;
j=1;
while( (i<=na)&&(j<=nb) )
{
if(a[i]<=b[j])
{
cout<<a[i]<<' ';
i++;
}
else
{
cout<<b[j]<<' ';
j++;
}
}
if(i<=na)
for(k=i;k<=na;k++)
cout<<a[k]<<' ';
if(j<=nb)
for(k=j;k<=nb;k++)
cout<<b[k]<<' ';
return 0;
}
输入: 5 1 3 5 7 9 4 2 6 10 14 输出:_______________
答案:
本题共 7 分
#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
int i;
if(n<=NUM)
return 0;
for(i=1;i<=NUM;i++)
if( r(n-i)<0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}
输入: 16 输出:______________
答案:
本题共 7 分
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
int i;
for(i=1;i<=n;i++)
if(!map[r[i]][r[i%n+1]])
return false;
return true;
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void perm(int left,int right)
{
int i;
if(found)
return ;
if(left>right)
{
if(successful())
{
for(i=1;i<=n;i++)
cout<<r[i]<<' ';
found=true;
}
return ;
}
for(i=left;i<=right;i++)
{
swap(r+left,r+i);
perm(left+1,right);
swap(r+left,r+i);
}
}
int main()
{
int x,y,i;
cin>>n>>m;
memset(map,false,sizeof(map));
for(i=1;i<=m;i++)
{
cin>>x>>y;
map[x][y]=true;
map[y][x]=true;
}
for(i=1;i<=n;i++)
r[i]=i;
found=false;
perm(1,n);
if(!found)
cout<<"No solution!"<<endl;
return 0;
}
输入: 9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9 输出:_________
答案:
本题共 7 分
(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸. 例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在一起过桥到河的左岸,总时间为2+1+4=7.
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false;
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int go(bool stage)
{
int i,j,num,tmp,ans;
if(stage==RIGHT_TO_LEFT)
{
num=0;
ans=0;
for(i=1;i<=n;i++)
if(pos[i]==RIGHT)
{
num++;
if( hour[i]>ans)
ans=hour[i];
}
if( ① )
return ans;
ans=INFINITY;
for(i=1;i<=n-1;i++)
if(pos[i]==RIGHT)
for(j=i+1;j<=n;j++)
if(pos[j]==RIGHT)
{
pos[i]=LEFT;
pos[j]=LEFT;
tmp=max(hour[i],hour[j])+ ② ;
if(tmp<ans)
ans=tmp;
pos[i]=RIGHT;
pos[j]=RIGHT;
}
return ans;
}
if(stage==LEFT_TO_RIGHT)
{
ans=INFINITY;
for(i=1;i<=n;i++)
if( ③ )
{
pos[i]=RIGHT;
tmp= ④ ;
if(tmp<ans)
ans=tmp;
⑤ ;
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>hour[i];
pos[i]=RIGHT;
}
cout<<go[RIGHT_TO_LEFT)<<endl;
return 0;
}
本题共 10 分
2.(烽火传递)烽火台又称烽燧,是重要的军事防御设施,一般建在险要处或交通要道上。一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情。在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确地传递,在连续的m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出信号的代价,请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递。 例如,有5个烽火台,他们发出信号的代价依次为1,2,5,6,2,,且m为3,则总共最少花费代价为4,即由第2个和第5个烽火台发出信号。
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
pos[SIZE],home[SIZE],opt[SIZE];
//hep[i]表示用顺序数组储存的堆heap中第i个元素的值
//pos[i]表示opt[i]在堆heap中的位置,即heap[pos[i]]=opt[i]
//home[i]表示heap[i]在序列opt中的位置,即opt[home[i]]=heap[i]
void swap(int i,int j)//交换堆中的第i个和第j个元素
{
int tmp;
pos[home[i]]=j;
pos[home[j]]=i;
tmp=heap[i];
head[i]=head[j];
heap[j]=tmp;
tmp=home[i];
home[i]=home[j];
home[j]=tmp;
}
void add(int k)//在堆中插入opt[k]
{
int i;
r++;
heap[r]= ① ;
pos[k]=r;
② ;
i=r;
while( (i>1) && (heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
}
void remove(int k)//在堆中删除opt[k]
{
int i,j;
i=pos[k];
swap(i,r);;
r--;
if(i==r+1)
return ;
while( (i>1)&&(heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
while(i+i<=r)
{
if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
j=i+i+1;
else
③ ;
if(hea[i]>heap[j])
{
④ ;
i=j;
}
else
break;
}
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i+++)
cin>>value[i];
r=0;
for(i=1;i<=m;i++)
{
opt[i]=value[i];
add(i);
}
for(i=m+1;i<=n;i++)
{
opt[i]= ⑤ ;
remove( ⑥ );
add(i);
}
cout<<heap[1]<<endl;
return 0;
}
本题共 12 分
tips
小码匠今年也要参赛,近期我正在整理CSP-J&S的知识点精简版,后面会陆续在本公众号内分享。
期待能与更多宝爸宝妈有更深度、更广度的交流,一起探讨信息学学习,让大家少走弯路。