试卷查看

第 1 题不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢排列的是（）

第 2 题 RAM中的信息是( )

第 3 题在24*24 点阵的字库中，汉字“一”与“编”的字模占用字节数分别是（）

第 4 题计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知64位的奔腾处理器一次能处理 64个信息，相当于（）字节

第 5 题在计算机领域中，通常用英文单词“BYTE”来表示（）

第 6 题 GB2312-80规定了- -级汉字3755 个，二级汉字3008 个，其中二级汉字字库中的汉字是以（）为序排列的。

第 7 题设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4, 5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈):进栈、进栈、进栈、出栈进栈、出栈、进栈。试问出栈的元素序列是（）

第 8 题设循环队列中数组的下标范围是n,其中头尾指针分别是f和r，则其元素个数是（）

第 9 题电线上停着两种鸟(A, B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类: 一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）

第 10 题从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为（）

第 11 题对一个满二叉树，m个树叶，1分枝结点，n个结点，则（）

第 12 题下列哪个软件不是操作系统软件的名字（）。

第 13 题下列哪个不是个人计算机的硬件组成部分（）。

第 14 题已知元素(8，25，14，87，51, 90，6，19， 20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足:8在51前面:90在87的后面;20在14的后面:25在6的前面；19在90的后面。（）

第 15 题假设我们用d=(a1,a2....,a5), 表示无向图G的5个顶点的度数，下面给出的哪组d值合理（）。

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

第 16 题

#include<iostream>
using namespace std;
#include<cmath>

bool IsPrime(int num)
{
	for (int i = 2; i <= sqrt(num); i++)
	{
		if (num%i == 0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	int num = 0;
	cin >> num;
	if (IsPrime(num))
	{
		cout << "YES" << endl;
	}
	else
	{
		cout<< "NO"<<endl;;
	}
	system("pause");
	return 0;
}

判断题

第 16 题 (1分)第19行输入97时，输出为“NO” (不含引号)。

第 17 题 (1分)第19行输入119时，输出为“YES” (不含引号)。

第 18 题若将第7行的“<=”改成“<”，程序输出的结果一定不会改变。

第 19 题当程序执行第14行时，i 值为 sqrt(num) 。

第 20 题（3分）最坏情况下，此程序的时间复杂度是（）。

第 21 题若输入的 num 为 20 以内的正整数，则输出为 “YES” 的概率是（）。

第 23 题

#include<bits/stdc++.h>
using namespace std;
const int mod=2048;
long long c,n;
long long kasumi(long long x,long long mi) {
	long long res=1;
	while(mi) {
		if(mi&1) {
			res=(res*x)%mod;
		}
		x=(x*x)%mod;
		mi>>=1;
	}
	return res;
}
int main() {
	cin>>n>>c;
	if(n==3) {
		printf("%lld",c*(c-1));
		return 0;
	}
	long long ans=((kasumi(c-1,n)+(c-1)*kasumi(-1,n))%mod+mod)%mod;
	cout<<ans ;
	return 0;
}

判断题

第 23 题 (1分)将第9行和第11行的括号去掉，程序输出结果一定不变。

第 24 题 (1分)将第12行的“mi>>=1”改为“mi*=0.5”，程序输出结果一定不变。

第 25 题若输入为“4 4”，则输出为“78”。

第 26 题此程序的时间复杂度为O(logn )。

第 27 题若输入为“34”，则输出为（）。

第 28 题 kasumi (2046,13)的返回值为（）。

第 30 题

#include<cstdio>
int n,r,num[ 10000];
bool mark[10000];
void print()
{
	for(int i=1; i<=r; i++)
		printf("%d ",num[i]);
	printf("\n");
}
void search(int x)
{
	for(int i=1; i<=n; i++)
		if(!mark[i])
		{
			num[x]=i;
			mark[i]=true;
			if(x==r) print();
			search(x+1);
			mark[i]=false;
		}
}
int main()
{
	scanf("%d%d",&n,&r);
	search(1);
}

判断题

第 30 题 (1分)程序结束时，对任意1≤i≤n， mark[i]=0。

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

第 37 题克鲁斯卡尔求最小生成树思想:首先将n个点看做n个独立的集合，将所有边快排(从小到大)。然后，按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于一个集合。若是，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若否，则跳过。直到找到n-1条边为止。

#include<iostream>
#include<algorithm>
using namespace std;
struct point {
	int x;
	int y;
	int v;
};
point a[10000];

int cmp(const point &a,const point &b) {
	if(___(1)___) return 1;
	else return 0;
}

int fat[101];
int father(int x) {
	if(fat[x] !=x) return fat[x]= ___(2)___;
	else return fat[x];
}

void unionn(int x,int y) {
	int fa=father(x);
	int fb=father(y);
	if(fa!=fb) fat[fa]=fb;
}

int main() {
	int i,j,n,m, k=0, ans=0,cnt=e;
	cin>>n;
	for(i=1; i<=n; i++)
	for(j=1; j<=n; j++)
	{
		cin>>m;
		if(m!=0) {
			k++;
			a[k].x=i;
			a[k].y=j;
			a[k].v=m;
		}
	}
	sort(a+1,a+1+k; ___(3)___ );
	
	for(i=1; i<=n; i++) {
		fat[i]=i;
	}
	
	for(i=1; i<=k; i++) {
		if(father(a[i].x)!=___(4)___) {
			ans+=a[i].v;
			unionn(a[i].x,a[i].y);
			cnt++;
		}
		if(___(5)___) break ;
	}
	cout<<ans;
	return 0;
}

第 37 题 ①处应填( )

第 38 题 ②处应填( )

第 39 题 ③处应填( )

第 40 题 ④处应填( )

第 41 题 ⑤处应填( )

第 43 题欧拉回路问题由七桥问题而来，其基本问题是是否能一次性不重复地走遍这七座桥，转换为数学问题中的图论就是指的是从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边，算法代码如下：

#include <iostream>
#include <ctime>
using namespace std;

int G[5][5];
int visited[5][5];
int n = 5;
void euler(int u) {
	for (int v = e; v < n; v++) {
		if (G[u][v] & ___(1)___) {
			cout << u <<"->" << v << endl;
			visited[u][v]= visited[v][u] = ___(2)___;
			 ___(3)___
		}
	}
}

int main() {
	G[1][2] = G[2][1] = G[1][3] =  ___(4)___= 1;
	G[2][4] = G[4][2] = G[3][4] =  ___(5)___= 1;
	euler(1);
	return 0;
}

第 43 题 ①处应填( )

第 44 题 ②处应填( )

第 45 题 ③处应填( )

第 46 题 ④处应填( )

第 47 题 ⑤处应填( )

2021入门组 CSP-J 初赛模拟试题 (4)