全国入门组 CSP-J 初赛模拟试题 (4)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
7) 设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4, 5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈):进栈、进栈、进栈、出栈进栈、出栈、进栈。试问出栈的元素序列是（）
9) 电线上停着两种鸟(A, B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类: 一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）
14) 已知元素(8，25，14，87，51, 90，6，19， 20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足:8在51前面:90在87的后面;20在14的后面:25在6的前面；19在90的后面。（）
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题4分，共计40分）
#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;
}#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;
}#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);
}三、完善程序
（单选题，每题3分，共计30分）
克鲁斯卡尔求最小生成树思想:首先将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;
}欧拉回路问题由七桥问题而来，其基本问题是是否能一次性不重 复地走遍这七座桥，转换为数学问题中的图论就是指的是从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边，算法代码如下：
#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;
}