CCF认证CSP-J入门组模拟测试题第一套
三、完善程序题
第一题 九宫格
请完善下面的程序,将1~9个数字分别填人3x3的九宫格中,第一行的三个数字组成一个三位数。要使第二行的三位数是第一行的2倍,第三行的三位数是第一行的3倍且每个格子里的数字都不能重复,现在要求输出所有的填充方案,以每种方案中的第一行组成的三位数升序输出。
输出格式：
每一种方案输出共三行,每行中每两个数没有空格,每种方案输出后要输出一个空行。
最后一行一个数字,表示方案的总数。
#include<bits/stdc++.h>
using namespace std;
#define n 9
int a[10],b[10],t1,t2,t3,c;
void f(int s){
int i;
if(①){
t1=a[1]*100+a[2]*10+a[3];
t2=a[4]*100+a[5]*10+a[6];
t3=a[7]*100+a[8]*10+a[9];
if(②){
cout<<t1<<endl<<t2<<endl<<t3<<endl<<endl;
c++;
}
return;
}
for(i=1;i<=n;i++){
if(b[i]==0){
___③___
b[i]=1;
___④___
___⑤___
}
}
}
int main()
{
f(1);
cout<<c<<endl;
}程序分析：此程序是通过回溯法找到满足条件的1-9的三个宫格里面的数字，首先定义了两个数组a和b，其中a用于存放1-9的数，b用于标记是否已经使用过某个数。函数f用于递归地生成所有可能的排列。参数s表示当前要填入的位置。当s等于n+1时，表示已经生成了一个完整的排列。然后计算t1、t2和t3的值，并判断是否满足条件。如果满足条件，则输出t1、t2和t3，并将计数器c加1。在f函数中，通过for循环尝试将1-9的数填入当前位置s，如果某个数i没有被使用过，则将它填入a[s]，并将b[i]标记为已使用。然后递归调用f函数继续填下一个位置s+1。递归回来后，需要将b[i]标记为未使用，以便后续的排列。
单选题
①处应该填
A. s==n+1
B. s==n
C. s<n
D. s>=n
答案：A
答案分析：此处要填的是完成了一次9个数字的排列，所以答案A
②处应该填
A. t3*2==t2&&t3*3==t1
B. t1*2==t2&&t2*3==t3
C. t1*3==t2&&t1*2==t3
D. t1*2==t2&&t1*3==t3
答案：D
答案分析：此处是满足第二行是第一行2倍，第三行是第一行三倍，所以答案D
③处应该填
A. a[c]=i;
B. a[s]=i;
C. a[i]=s;b[c]=i;
D. b[s]=i;
答案：B
答案分析：此处是要将第s个位置上的数填上i，所以答案B
④处应该填
A. f(i+1);
B. f(s+1);
C. f(c+1);
D. f(c+i+1):
答案：B
答案分析：填完第s个数字后，往后填s+1个位置对应的数，所以答案B
⑤处应该填
A. a[s]=0;
B. f(s-1);
C. a[s]=i;
D. b[i]=0:
答案：D
答案分析：填完了数字，需要回溯，将i标记为未使用，所以答案D
第二题 拓扑排序
输人一张n节点m条边的有向图,用求该图的一个拓扑排序的方式判断该图是否存在有向环,若有拓扑排序输出拓扑排序,并输出“不存在有向环”,否则直接输出“存在有向环”。
输人:
第一行两个正整数n,m表示节点数和边数。
接下来 m行,每行2个正整数x,y表示节点 x->y 之间有一条边。
输出:
一个拓扑序:按拓扑序输出点的编号。若拓扑序不唯一,输出任意一个均可,并输出“存在有向环”。若无拓扑序,直接输出“不存在有向环”.
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define N 1001
using namespace std;
int n,m,x,y;
vector<int>G[N];
stack<int>q;
int cnt[N],tpc;
bool pd()
{
for(int i=l;i<=n;i++)
if(__①__)q.push(i);
while(!q.empty())
{
int u=q.top();
q.pop();
tpc++;
cout<<u<<" ";
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
__②__
if(!cnt[v])__③__
}
}
if(__④__)return 1;
else return 0;
}
int main()
{
cin>>n>>m;
while(m--)
{
cin>>x>>y;
G[x].push_back(y);
__⑤__
}
if(pd())cout<<"存在有向环";
else cout<<"不存在有向环";
}程序分析：此程序的主要思路是使用拓扑排序来判断有向图是否存在环。
首先，定义了一个函数pd()用来进行拓扑排序和判断是否存在有向环。在pd()函数中，首先初始化了一个栈q和一个计数器tpc，用来存储拓扑排序的结果。然后，将所有入度为0的节点压入栈q中。接下来，利用栈q进行拓扑排序的过程，依次从栈中弹出节点u，将节点u输出，并将u的所有邻接节点的入度减1。然后，如果某个邻接节点的入度变为0，就将该节点压入栈q中。最后，判断tpc的值是否等于节点个数n，若相等则表示不存在有向环，否则存在有向环。
单选题
①处应该填
A. !cnt[i]
B. cnt[i]
C. cnt[i]=0
D. cnt[i]==1
答案：A
答案分析：此处就似乎将所有入读为0的节点压入栈q中；所以答案A
②处应该填
A. q.push(v);
B. q. pop( );
C. cnt[u]--;
D. cnt[v]--;
答案：D
答案分析：此处就是将相邻节点的入度减1，所以答案D
③处应该填
A. q.pop();
B. q.push(v);
C. tpc--;
D. tpc++;
答案：B
答案分析：此处就是将入度为0的节点压入栈中；所以答案B
④处应该填
A. tpc!=n
B. tpc==n
C. tpc==0
D. tpc!=0
答案：A
答案分析：这里双分支条件是计数器不等于输入n就表示存在有向环，否则就是不存在，所以答案A
⑤处应该填
A. cnt[x]++;
B. G[y].push(x)
C. cnt[y]++;
D. push_back(x)
答案：C
答案分析：此处是更新节点y的入度，所以答案C
