NOIP真题
表达式a * d - b * c 的前缀形式是（ ）。
在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。
关于Catalan 数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（ ）。
假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。
为了统计一个非负整数的二进制形式中1 的个数，代码如下：
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
________;
}
return ret;
}则空格内要填入的语句是（ ）。
NOIP 初赛中，选手可以带入考场的有（ ）。
2-3 树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同。
如果一棵2-3 树有10 个叶结点，那么它可能有（ ）个非叶结点。
下列关于最短路算法的说法正确的有（ ）。
下列说法中，是树的性质的有（ ）。
下列关于图灵奖的说法中，正确的有（ ）。
( 寻找假币 ) 现有 80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？
( 取石子游戏 ) 现有 5 堆石子，石子数依次为 3，5，7，19，50，甲乙两人轮流从任一堆中任取 ( 每 次只能取自一堆，不能不取 ) ，取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略 ( 即无论 乙怎样取，甲只要不失误，都能获胜 ) ？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：
#include<stdio.h>
int main()
{
int i,u[4],a,b,x,y=10;
for(i=0;i<=3;i++)
scanf("%d",&u[i]);
a=(u[0]+u[1]+u[2]+u[3])/7;
b=u[0]/((u[1]-u[2])/u[3]);
x=(u[0]+a+2)-u[(u[3]+3)%4];
if(x>10)
y+=(b*100-u[3])/(u[u[0]%3]*5);
else
y+=20+(b*100-u[3])/(u[u[0]%3]*5);
printf("%d,%d\n",x,y);
return 0;
} /* 注：本例中，给定的输入数据可以避免分母为 0 或下标越界。 */输入： 9 3 9 4
输出： ________________
#include <stdio.h>
int main()
{
int i,j,m[]={2,3,5,7,13};
long t;
for(i=0;i<=4;i++)
{
t=1;
for(j=1;j<m[i];j++)
t*=2;
printf("%ld ",(t*2-1)*t);
}
printf("\n");
}输出： ________________
#include "stdio.h"
#define N 7
int fun(char s[],char a,int n)
{
int j;
j=n;
while(a<s[j]&&j>0) j--;
return j;
}
int main()
{
char s[N+1];
int k,p;
for(k=1;k<=N;k++)
s[k]='A'+2*k+1;
printf("%d\n",fun(s,'M',N));
}输出： ________________
#include <stdio.h>
void digit(long n,long m)
{
if(m>0)
printf("%2ld",n%10);
if(m>1)
digit(n/10,m/10);
printf("%2ld",n%10);
}
int main()
{
long x,x2;
printf("Input a number:\n");
scanf("%ld",&x);
x2=1;
while(x2<x)
x2*=10;
x2/=10;
digit(x,x2);
printf("\n");
}输入： 9734526
输出： ________________
( 全排列 ) 下面程序的功能是利用递归方法生成从 1 到 n(n<10) 的 n 个数的全部可能的排列 ( 不一定 按升序输出 ) 。例如，输入 3，则应该输出 ( 每行输出 5 个排列 ) ：
123 132 213 231 321 312
程序：
#include<stdio.h>
int n,a[10]; /*a[1],a[2], …,a[n] 构成 n 个数的一个排列 */
long count=0; /* 变量 count 记录不同排列的个数，这里用于控制换行 */
void perm(int k)
{
int j,p,t;
if(______ ①______)
{
count++;
for(p=1;p<=n;p++)
printf("%1d",a[p]); /* "%1d" 中是数字 1，不是字母 l */
printf(" ");
if(______ ②______)
printf("\n");
return;
}
for(j=k;j<=n;j++)
{
t=a[k];
a[k]=a[j];
a[j]=t;
______③______;
t=a[k]; ______④______;
}
}
int main()
{
int i;
printf("Entry n:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
______⑤______;
}由键盘输入一个奇数 P(P<100,000,000) ，其个位数字不是 5，求一个整数 S，使 P×S=1111...1( 在给定的条件下，解 s 必存在) 。要求在屏幕上依次输出以下结果：
(1) S 的全部数字。除最后一行外，每行输出 50 位数字。
(2) 乘积的数字位数。
例 1：输入 P=13，由于 13*8547=111111，则应输出 (1) 8547 ，(2) 6
例 2：输入 P=147，则输出结果应为 (1) 755857898715041572184429327286470143613 (2) 42 ，即 等式的右端有 42个 1。
程序：
#include<stdio.h>
int main()
{
long p,a,b,c,t,n;
int bl;
while(1)
{
printf(" 输入 p, 最后一位为 1 或 3 或 7 或 9：\n");
scanf("%ld",&p);
if((p%2!=0)&&(p%5!=0)) /* 如果输入的数符合要求，结束循环 */
______⑥______;
}
a=0; n=0;
while(a<p);
{
a=a*10+1;n++;/*变量a存放部分右端项，n为右端项的位数*/
}
t=0;
do
{
b=a/p;
printf("%1ld",b);
t++;
if(___________⑦__________)
printf("\n");
c=_________⑧_________;a=________⑨______;n++;
}while(c>0);
printf("\nn=%ld\n".__________⑩_______);
}将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且：
（1）在每个子集中，没有人认识该子集的所有人。
（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。
（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只 有 1 个人认识这两个人。
则满足上述条件的子集最多能有 ___________个？
将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线， 得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线， 起点是最上面的一个小三角形，终点是最 下面一行位于中间的小三角形。在通路中， 只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三 角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的 例 子）。设 n=10，则该正三角形的不同的通路的总数为_____________。
