绍兴市绍兴市中小学生编程比赛

不是VIP会员，不能显示答案，请在后台“我的信息” 在线升级 VIP 。

一、单项选择题(共 20题，每题1.5分，共计30分;每题有且仅有一个正确选项)

1. 5G网络指( )。

A.第5代蜂窝技术网络
B.最大传输速率为5 Gbps 的网络
C.基站重量为5克的网络
D.信号频率为5 GHz的网络

查看

2. 以下整数中( ) 是质数。

A.(110)2
B.(57)8
C.(119)10
D.(41)16

查看

3. 现代计算机所应用的存储程序原理是( )提出的。

A.阿兰·图灵
B.冯·诺依曼
C.理查德·斯托曼
D.罗伯特·塔扬

查看

4. 深度优先搜索通常使用( ) 数据结构进行实现。

A.堆
B.栈
C.二叉搜索树
D.队列

查看

5. 如果图G不连通且包含25条边，那么图G至少包含( ) 个节点。

查看

6. 如果数据被存储在链表中，那么( ) 算法的时间复杂度要比数据存储在数组中高。

A.冒泡排序
B.插入排序
C.选择排序
D.堆排序

查看

7. unsigned long long 进行加法运算等价于对( ) 取模。

A.2^31
B.2^32
C.2^63
D.2^64

查看

8. 仅使用乘法计算x^15至少需要( ) 次乘法运算。

A.5
B.6
C.7
D.14

查看

9. 在一棵n个点的二叉搜索树上查找一一个元素的最差时间复杂度是( )。

A.Θ(1)
B.Θ(1og(n))
C.Θ(n)
D.Θ(n^2)

查看

10. n*(n+2)*(n+4)-定是 ( ) 的倍数。

查看

11. 8732517 和 8732532的最大公约数是( )。

A.1
B.3
C.5
D.15

查看

12. 下列字符串中字典序最小的是( )。

A.b
B.acd
C.abc
D.ac

查看

13. ( )算法不是用于解决最小生成树问题的算法。

A.Dijkstra
B.Prim
C.Kruskal
D.Boruvka

查看

14. 求n个数的中位数的最优时间复杂度为( )。

A.Θ(log(n))
B.Θ(n)
C.Θ(n*log(n))
D.Θ(n)

查看

15. 已知T(n)=T(√n)+Θ(n) (n>=2), T(1)=Θ(1)，那么有( )。

A.T(n)=Θ(n*log(n))
B.T(n)=Θ(n)
C.T(n)=Θ(n*log(log(n)))
D.T(n)= Θ(n*(log(n))^2)

查看

16. 下列哪个选项不是计算机网络中常见的传输媒介( )。

A.光纤
B.无线电波
C.包裹邮件
D.双绞线

查看

17. 两个人玩石头剪刀布，期望( ) 轮分出胜负。

A.1.5
B.2
C.2.5
D.3

查看

18. 字符串banana 有( ) 个本质不同的非空子串。

A.15
B.16
C.17
D.21

查看

19. 一个字节由相邻的( ) 个二进制位组成。

A.2
B.4
C.8
D.16

查看

20. 下图中将ABCD四个区域用至多四种颜色染色，使得相邻区域颜色不同的方案数是( )。

A.48
B.4
C.12
D.24

查看

二、程序阅读理解题(共3大题，每大题分判断题和选择题，判断题1.5分,选择题4分，共计40分)

#include<iostream>

#include<vector>

int cmp(int x, int y)

{

	if(x>y)return 1;

	else if(x==y)return 0;

	else return -1;

}

int main()

{

	int n;

	std::cin>>n;

	std::vector<int> a(n+5);

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

		std::cin>>a[i];

	int now=-1;

	for(int i=2; i<=n; i++)

	{

		int c=cmp (a[i-1],a[i]);

		if (c>=now) now=c;

		else

		{

			std::cout<<"NO"<<std::endl;

			return 0;

		}

	}

	std::cout<<"YES" <<std::endl;

	return 0;

}

判断题

1) 如果输入满足 1≤n≤100, 1≤a[i]≤1000 (下同)，则程序只会输出YES或NO两种结果。( )

2) cmp函数的作用是比较两个数x,y的大小，如果x较大返回-1，如果y较大返回1，如果一样大返回0。( )

3) 该程序的时间复杂度为0(n)。 ( )

选择题

4) 输入为( ) 时输出为YES。

5) 如果将第24行去掉，这时输出中最多包含( )个大写字母 0。

查看

#include<iostream>

int main()

{

	int n, a, b, c=0, bad=0;

	std::cin>>n>>a>>b;

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

	{

		int t;

		std::cin>>t;

		if(t==1)

		{

			if(a)a--;

			else if(b)b--, c++;

			else if(c)c--;

			else bad++;

		}

		else

		{

			if(b)b--;

			else bad+=2;

		}

	}

	std::cout<<bad<<std:: endl;

	return 0;

}

判断题

1) 如果输入满足1≤n, a, b≤100000,1≤t≤2(下同),那么输出的bad一定不会大于n。( )

2) 程序运行过程中变量c的值不会小于0。( )

3) 将输入的所有 t打乱顺序不会影响程序运行结果。( )

选择题

4) 如果输入为4 1 1 1 1 2 1,那么输出的bad的值是( )。

5) 如果n固定，那么程序运行至for循环结束时，变量c的最大值为( )。

查看

#include<iostream>

#include<vector>

int main()

{

	int n;

	std::cin>>n;

	std::vector<std::vector<int> > a(n+5, std::vector<int> (n+5));

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

		for(int j=1; j<=n; j++)

			std::cin>>a[i][j];

	int good=1 ;

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

		for(int j=1; j<=n; j++)

			if(a[i][j]!=1)

			{

				int chk=0;

				for(int r=1; r<=n; r++)

					for(int c=1; c<=n; c++)

						chk|=(a[i][r]+a[c][j]==a[i][j]);

				good&=chk ;

			}

	std::cout<< (good?"YES":"N0")<<std::endl;

	return 0;

}

判断题

1) 如果输入满足1≤n≤300, 1 ≤ a[i][j]≤100000000 (下同)，那么程序不会发生整型溢出。( )

2) 输入3 1 5 2 1 1 1 1 2 3 时程序输出YES。( )

选择题

3) 该程序的空间复杂度为( )。

4) 该程序的时间复杂度为( )。

5) n=3 时如果要使得程序的输出为YES，则a数组中最大值至多是( )。

查看

三、程序完善题(共2题，每题5个选择题，每个选择题3分，共计30分)

1. (瓷砖问题)有一条高度为1,长度为n (1<=n<=50)的墙。有两类瓷砖可以铺在墙上: 第二类是长度为1的正方形瓷砖，第二类是长度大于等于3的长方形瓷砖。两块第二类瓷砖之间至少需要隔一块第一类瓷砖。问一共有多少种满足条件的铺瓷砖方案。

#include<iostream>

#include<vector>

int main()

{

	int n;

	std::cin>>n;

	__(1)__;

	__(2)__;

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

	{

		__(3)__;

		for(__(4)__)

			__(5)__;

	}

	std::cout<<f[n]<<std::endl;

	return 0;

}

选择题

1) ⑴处应填( )。

2) ⑵处应填( )。

3) ⑶处应填( )。

4) ⑷处应填( )。

5) ⑸处应填( )。

查看

2. (数位和的幂问题)定义一个数是好数，当且仅当这个数至少包含两位数，且等于它本身在十进制下所有数位之和的若干次幂。形式化地，设ds(x)表示x在十进制下的所有数位之
和，则x是好数当且仅当x≥10且存在正整数k使得(ds(x))^k=x。例如ds(512)=8, 8^3=512,
所以512是一个好数。
给定n (1000<=n<=10^18),求不超过n的所有好数，按升序输出，每个数一行。

#include<iostream>

#include<vector>

#include<algorithm>

long long ds(long long x)

{

	if (x<=9) return x;

	else return __(1)__;

}

const int dslim=18*9;

int main() {

	long long n;

	std::cin>>n;

	std::vector<long long> ans;

	for (long long i=2; i<=dslim; i++)

	{

		long long t=i;

		while(__(2)__)

		{

			__(3)__;

			if(__(4)__)

				ans.push_back(t);

		}

	}

	__(5)__;

	for (auto x:ans) std::cout<<x<<std::endl;

	return 0;

}

选择题