NOIP2015普及组初赛试题

缺乏、安全感 2021-11-08 20:30 367阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

[https://blog.csdn.net/a2392008643/article/details/81781766][https_blog.csdn.net_a2392008643_article_details_81781766]

二、问题求解

1. 重新排列1234使得每一个数字都不在原来的位置上，一共有（ ）重排法

答案：9种

> 数比较少可以用枚举：
> 
> 刚开始的排列 1 2 3 4，则求1 不能排在第1个位置，2不能排在第二个位置，3不能排在第3个位置、4不能排在第4个位置的情况。
> 
> 假设第一个数是2：
> 
> 2 1 4 3
> 
> 2 3 4 1
> 
> 2 4 1 3
> 
> 假设第一个数是3：
> 
> 3 1 4 2
> 
> 3 4 1 2
> 
> 3 4 2 1
> 
> 假设第一个数是4：
> 
> 4 1 2 3
> 
> 4 3 1 2
> 
> 4 3 2 1
> 
> 一共有9种。
> 
> 实际上这种错位排列有一个简单的公式：\{n!/e\}，\{x\}表示接近x的整数。e=2.71828……

2. 一颗节点数为2015的二叉树最多有（ ）个叶子节点。

答案：1008

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

> 解析：这个二叉树最多有n层。
> 
> 2^n-1=2015 -> n=11
> 
> 最后一层的叶子节点个数（总的节点数减去前面一层以前的所有节点数）：2015-（2^10-1)=992个
> 
> 倒数第二层的叶子节点数（倒数第二层的叶子节点总数减去最后一层叶子节点数/2取上限）：2^9-ceil(992/2)=16个
> 
> 总的节点数：992+16=1008个。

三、阅读程序写结果

#include<iostream>
    using namespace std;
    int main()
    {
    	int a,b,c;
    	a = 1; b = 2; c = 3;
    	if(a>b)
    	{
    		if(a>c)
    			cout << a <<' ';
    		else
    			cout << b << ' ';
    	}
    	cout << c << endl;
    	return 0;
     }

答案：3

> 解析：当执行到第一个if语句时，a>b不成立，所有整个\{\}中的语句都不执行，直接执行cout<<c<<endl.

#include<iostream>
    using namespace std;
    struct point{
    	int x;
    	int y;
    };
    int main()
    {
    	struct EX{
    		int a;
    		int b;
    		point c;
    	}e;
    	e.a = 1;
    	e.b = 2;
    	e.c.x = e.a+e.b;
    	e.c.y = e.a*e.b;
    	cout << e.c.x << ',' << e.c.y << endl;
    	return 0;
    }

答案：3，2

> 解析：
> 
>     e.c.x = e.a+e.b;//e.c.x=1+2=3
>     	e.c.y = e.a*e.b;//e.c.x=1*2=2

#include<iostream>
    #include<string>
    using namespace std;
    int main()
    {
    	string str;
    	int i;
    	int count;
    	count = 0;
    	getline(cin,str);
     	for(i = 0; i < str.length();i++)
    	{
    		if(str[i]>='a' && str[i] <= 'z')
    			count++;
    	}
    	cout << "It has " << count << " lowercases" << endl;
    	return 0;
    }

输入：NOI2016 will be held in Mian Yang.

输出：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

答案： It has 18 lowercases

> 解析：本题主要是统计字符串中小写字母的个数。需要注意的是输出的时候原样输出，不要加多余的句号。

#include<iostream>
    using namespace std;
    int fun(char *a, char *b)
    {
    	a = b;
    	(*a)++;
    }
    int main()
    {
    	char c1,c2,*p1,*p2;
    	c1='A';
    	c2='a';
    	p1 = &c1;
    	p2 = &c2;
    	fun(p1,p2);
    	cout << c1 << c2 << endl;
    }

答案：Ab

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]

> 解析：本题需要注意a,b,p1,p2都是指针，a=b只是将a指向了b的地址。
> 
> （\*a++)是将a指向地址中的值增加了1.

四、完善程序

1.（打印月历）输入月份m(1<=m<=12)，按一定格式打印2015第m月的月历。

例如，2015年一月的月历打印效果如下（第一列为周日）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4][]

#include<iostream>
    using namespace std;
    const int dayNum[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};
    int m,offset,i;
    int main()
    {
    	cin >> m;
    	cout <<"S\tM\tT\tW\tT\tF\tS"<<endl;//'\t'为tab制表符 
    	offset = 4;//一月份第一行前面空了4个制表符 
    	for(i = 1; i < m; i++)//计算第一行前面要空几个制表符 
    		offset = (offset+dayNum[i])%7;
    	for(i = 0; i < offset; i++)
    		cout <<'\t';
    	for(i = 1; i <= dayNum[m];i++)
    	{
    		cout << i;
    		if(i==dayNum[m]||(offset+i)%7==0)//判断什么时候换行 
    			cout << endl;
    		else
    			cout <<'\t';
    	 } 
    	return 0;
    }

2. (中位数）给定n(n为奇数且小于1000）个整数，整数的范围在0~m(0<m<2^31)之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 5][]

![20190806175222171.png][]

> 解析：中位数肯定是下标为n/2的数，只需要统计大于mid的数目count， 然后不断的缩小范围，直到找到目标值。
> 
> 这个题具体加不加等号，rbound=mid或者mid-1,可以带入具体的数值进行运算。
> 
> n = 3 m=7 n/2=1
> 
> 2 3 5
> 
> lbount = 0, rbound = 7, mid = 3, count = 1;
> 
> lbound = 0, rbound = 3, mid = 1, count = 3
> 
> lbound = 2, rbound = 3, mid = 2, count = 2
> 
> lbound = 3, rbound = 3;
> 
> cout： 3

样例：

![20190806181018717.png][]

#include<iostream>
    using namespace std;
    const int MAXN = 1000;
    int n,i,lbound,rbound,mid,m,count;
    int x[MAXN];
    int main()
    {
    	cin >> n >> m;//n个整数，每个整数的范围在0~m之间
    	for(i = 0; i < n; i++)
    		cin >> x[i];
    	lbound = 0;rbound = m;
    	while(lbound < rbound){
    		mid=(lbound+rbound)/2;//首先假设中位数为（最小值+最大值）/2 
    		count = 0;
    		for(i = 0; i < n; i++)//统计大于中位数的数的个数 
    		{
    			if(x[i] > mid)
    				count++;
    		}
    		if(count > n/2)//如果统计出的数超过一半，说明假设的这个中位数小了 
    			lbound = mid + 1;
    		else
    			rbound = mid;
    	} 
    	cout << rbound << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20211108/2d9ca67870a34bd784aa1d6c07ccf7f4.png
[https_blog.csdn.net_a2392008643_article_details_81781766]: https://blog.csdn.net/a2392008643/article/details/81781766
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20211108/d5d6ba737fc042d582d7c2f72839948f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20211108/eaec044740ba481690211e7f03603fcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3]: /images/20211108/ddb4c210dfbb403e86ebe1871709713c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4]: /images/20211108/62c29625883e415e8ab0eab7f0e9cc85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 5]: /images/20211108/080a7e40ed954a749d7c16dd6469e8f7.png
[20190806175222171.png]: /images/20211108/131b427341f64a0c85b34fcebb5c4f91.png
[20190806181018717.png]: /images/20211108/5a64538a94f54fcc9be2a57b7425e58b.png