网站如何引导页,凡客建站快车,免费软件电视剧最全,网络域名怎么查CCF认证CSP-J入门组模拟测试题第一套
三、完善程序题
第一题 九宫格
请完善下面的程序,将1~9个数字分别填人3x3的九宫格中,第一行的三个数字组成一个三位数。要使第二行的三位数是第一行的2倍,第三行的三位数是第一行的3倍且每个格子里的数字都不能重复,现在要求输出所有的填…
CCF认证CSP-J入门组模拟测试题第一套
三、完善程序题
第一题 九宫格
请完善下面的程序,将1~9个数字分别填人3x3的九宫格中,第一行的三个数字组成一个三位数。要使第二行的三位数是第一行的2倍,第三行的三位数是第一行的3倍且每个格子里的数字都不能重复,现在要求输出所有的填充方案,以每种方案中的第一行组成的三位数升序输出。
输出格式
每一种方案输出共三行,每行中每两个数没有空格,每种方案输出后要输出一个空行。
最后一行一个数字,表示方案的总数。
#includebits/stdc.h
using namespace std;
#define n 9
int a[10],b[10],t1,t2,t3,c;
void f(int s){int i;if(①){t1a[1]*100a[2]*10a[3];t2a[4]*100a[5]*10a[6];t3a[7]*100a[8]*10a[9];if(②){coutt1endlt2endlt3endlendl;c;}return;}for(i1;in;i){if(b[i]0){___③___b[i]1;___④______⑤___}}
}
int main()
{f(1);coutcendl;
}
程序分析此程序是通过回溯法找到满足条件的1-9的三个宫格里面的数字首先定义了两个数组a和b其中a用于存放1-9的数b用于标记是否已经使用过某个数。函数f用于递归地生成所有可能的排列。参数s表示当前要填入的位置。当s等于n1时表示已经生成了一个完整的排列。然后计算t1、t2和t3的值并判断是否满足条件。如果满足条件则输出t1、t2和t3并将计数器c加1。在f函数中通过for循环尝试将1-9的数填入当前位置s如果某个数i没有被使用过则将它填入a[s]并将b[i]标记为已使用。然后递归调用f函数继续填下一个位置s1。递归回来后需要将b[i]标记为未使用以便后续的排列。
单选题
①处应该填
A. sn1 B. sn C. sn D. sn
答案A
答案分析此处要填的是完成了一次9个数字的排列所以答案A ②处应该填
A. t3*2t2t3*3t1 B. t1*2t2t2*3t3 C. t1*3t2t1*2t3 D. t1*2t2t1*3t3
答案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(i1); B. f(s1); C. f(c1); D. f(ci1):
答案B
答案分析填完第s个数字后往后填s1个位置对应的数所以答案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 之间有一条边。输出: 一个拓扑序:按拓扑序输出点的编号。若拓扑序不唯一,输出任意一个均可,并输出“存在有向环”。若无拓扑序,直接输出“不存在有向环”.
#includeiostream
#includealgorithm
#includevector
#includestack
#define N 1001
using namespace std;
int n,m,x,y;
vectorintG[N];
stackintq;
int cnt[N],tpc;
bool pd()
{for(int il;in;i)if(__①__)q.push(i);while(!q.empty()){int uq.top();q.pop();tpc;coutu ;for(int i0;iG[u].size();i){int vG[u][i];__②__if(!cnt[v])__③__}}if(__④__)return 1;else return 0;
}int main()
{cinnm;while(m--){cinxy;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. tpcn C. tpc0 D. tpc!0
答案A
答案分析这里双分支条件是计数器不等于输入n就表示存在有向环否则就是不存在所以答案A ⑤处应该填
A. cnt[x]; B. G[y].push(x) C. cnt[y]; D. push_back(x)
答案C
答案分析此处是更新节点y的入度所以答案C
