试卷查看

第 1 题下面四个数中，值与其他三个不同的是( )。

第 2 题如果树根算第1层，那么一棵n层的满二叉树有( ) 个非叶子结点。

A. $2^{n+1}-2^n-1$

B. $2^{n-1}$

C. $2^n-2^{n-1}-1$

D. $2^{n-1}+1$

第 3 题 30000 以内，与30000 互质的正整数有( ) 个。

第 4 题如果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是( )。

第 5 题十进制算术表达式:11x128+3x32+7, 运算结果用二进制表示为( )。

第 6 题在程序运行过程中，如果递归调用的层数过多，会因为( ) 引发错误。

第 7 题 FTP可以用于( )。

第 8 题有7个一模一样的苹果，放到3个一样的盘子中，一共有( )种放法。

第 9 题以下不是存储设备的是( )。

第 10 题设A=B=false, C=D=true, 以下逻辑运算表达式值为真的有( )。

第 11 题如果在某个进制下等式13*13=171 成立，那么在该进制下 12*12= ( )。

第 12 题以下哪个排序不是稳定的排序( )。

第 13 题若字符串S="abcabcbc",其本质不同非空子串的个数是( )。

第 14 题定义给一个长度为n的排列a进行一轮冒泡排序指从1到n-1 枚举i，如果$a_i>a_{i+1}$就交换$a_i 和 a_{i+1}$。已知排列a=(3,2,1,4,5)是由另一个排列b经过2轮冒泡排序后得到的排列，那么一共有( ) 个满足条件的排列b。

第 15 题表达式a*(b+c)*d的后缀形式是( )。

二、判断题（每题 2 分，共 20 分）

第 16 题

#include<bits/stdc++.h>
using namespace std;
int main() 
{
	unsigned long long x,y,z;
	cin>>x>>y>>z;
	for (int i=1; i<=5; i++) x++;
	x*=y;
	z=x+z;
	x=x+z;
	cout<<x<<endl;
}

判断题

第 16 题将第7行的for语句改为X+=5;输出不变。( )

第 17 题输入的y可以为0。( )

第 18 题若输入的数均为正整数，并且输入的z是奇数，那么输出的数可能为偶数。( )

第 19 题程序输出的结果可能会为负数。( )

第 20 题若输入为3 2 5,那么输出的数等于( )。

第 21 题若输入为-6 1 3,那么输出的数等于( )。

第 23 题

#include<bits/stdc++.h>
using namespace std;
int n, a[100000], f[100000], ans=1;
int main()
{
	cin>>n;
	for (int i=1; i<=n; i++)
		cin>>a[i];
	for (int i=1; i<=n; i++)
	{
		f[i]=1;
		for (int j=1; j<i; j++)
			if (a[j]<a[i]) f[i]=f[j]+1;
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
}

判断题

第 23 题输入的n可以为100000。 ( )

第 24 题若输入的n>=0，输出的ans一定<=n。( )

第 25 题输入的n不能<0,否则- -定会发生运行错误。( )

第 30 题

#include<bits/stdc++.h>
using namespace std;
int a[105],n,x,ans=0;
int main ()
{
	cin>>n;
	for (int i=1; i<=n; i++)
	{
		cin>>x;
		a[x]++;
	}
	for (int i=0; i<=100; i++)
	{
		ans+=a[i]%2;
		a[i+1]+=a[i]/2;
	}
	cout<<ans<<endl ;
	return 0;
}

假设输入的n是不超过20的正整数，x是不超过100非负整数，完成下面的判断题和单选题:

判断题

第 30 题该算法的输出可能大于n。( )

第 31 题当n=59时，存在一种输入，使得输出的ans为1。 ( )

第 32 题当n=60时，存在一种输入，使得输出的ans为1。 ( )

第 33 题若输入为5 1 1 2 3 3,则输出为()。

第 34 题若输入的n 等于35，接下来的输入全为0，则输出为( )。

第 35 题若输入的n等于15，接下来的输入全为98，则输出为( )。

三、编程题（每题 25 分，共 50 分）

第 37 题 (波浪数)我们将一类正整数称为“波浪数”，它的每个数位上的数都大于或小于两边数位上的数。例如，32570, 102, 747, 20和3都是波浪数:而123, 1000 和2212不是波浪数。给你一个5位数n,请你找到最小的比n大的波浪数。输入保证$10000 \leq n \leq 99999$。提示: 枚举每个5位波浪数和6位波浪数来找到答案。试补全程序。

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	int ans=___(1)___;
	cin>>n;
	for (int i=1; i<=9; i++)
	for (int j=0; j<=9; j++)
		if (j!=i)
		for (int ka((i<j)?0: ___(2)___); k<=((i<j)?___(3)___:9); k++)
		for (int x*=((j<k)?0:k); x<=((j<k)?k:9); x++)
			if (x!=k)
			for (int y=0; y<=9; y++)
				if (y!=x&&k<x!=x<y)
				{
					int v=___(4)___;
					if (v>n)
						ans=min(ans,v);
				}
	for (int i=1; i<=9; i++)
	for (int j=0; j<=9; j++)
		if (j!=i)
		for (int k((i<j)?:j); k<=((i<j)?j:9); k++)
		if (k!=j)
		for (int x=((j<k)?0:k); x<=((j<k)?k:9); x++)
			if (x!=k)
			for (int y=0; y<=9; y++)
				if (y!=x&&k<x!=x<y)
				for (int p=0; p<=9; p++)
					if (p!=y&&x<y!=y<p)
					{
						int v=___(5)___;
						if (v>n)
							ans=min(ans,v);
					}
	cout<<ans<<endl;
}

第 37 题 ⑴处应填( )。

第 38 题 ⑵处应填( )。

第 39 题 ⑶处应填( )。

第 40 题 ⑷处应填( )。

第 41 题 ⑸处应填( )。

第 43 题 (列队)有n个人排成一排，第i个人的体力为ai,你只能挑选出一段连续的人让他们出列去跑操。因为你不敢选一些体力太差的人去跑，担心他们太累，所以你选的人的体力值不能小于X。可是你希望每次能多选一些人去跑操，你需要求出至少能够选y个人去跑操时x的最大值。如果始终都不能选出y个人，输出-1。输入的第一行是两个正整数n和y ($ 1 \leq n \leq 10^5 ,1 \leq y \leq 10^5$)。输入的第二行是n个正整数$a_i (1\leq a_i\leq 2 \times 10^9)$。提示:使用二分答案解决这个问题，二分答案为x，判断是否至少能够选出y个人。试补全程序。

#include<bits/stdc++.h>
using namespace std;
int n,y,a[100005];
int chk(int x)
{
    int ans=0;
    int tot=0;
    for (int i=1; i<=___(1)___; i++)
	{
        if (a[i]>=x) tot++;
        else
		{
            ___(2)___;
        }
        ans=max(ans,tot);
    }
    return ans>=y;
}
int main()
{	
	cin>>n>y;
	for (int i=1; i<=n; i++) cin>>a[i];
	int ans=___(3)___;
	int l=1, r=200000000;
	while (___(4)___)
	{
	    int mid=___(5)___;
	    if (chk(mid))
	    {
	    	ans=mid;
	    	l=mid+1;
		}else
	    	r=mid-1;
	}
	cout<<ans<<endl;
}

第 43 题 ⑴处应填( )。

第 44 题 ⑵处应填( )。

第 45 题 ⑶处应填( )。

第 46 题 ⑷处应填( )。

第 47 题 ⑸处应填( )。

2022上虞区中小学生编程比赛 [小学组]