软件设计师2015年上半年下午卷试题解析.pdf

软酷网官网 ： 2015年软件设计师上半年下午卷解析 ——试题四 【2015-05 试题四】 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 n-皇后问题是在n行n列的棋盘上放置n个皇后，使得皇后彼此之间不受攻击， 其规则是任意两个皇后不在同一行、同一列和相同的对角线上。 拟采用以下思路解决n-皇后问题：第i个皇后放在第i行。从第一个皇后开始， 对每个皇后，从其对应行 （第i个皇后对应第i行）的第一列开始尝试放置，若可 以放置，确定该位置，考虑下一个皇后；若与之前的皇后冲突，则考虑下一列；若 超出最后一列，则重新确定上一个皇后的位置。重复该过程，直到找到所有的放置 方案。 【C 代码】 下面是算法的C语言实现。 (1) 常量和变量说明 pos：一维数组，pos[i]表示第i个皇后放置在第i行的具体位置 count：统计放置方案数 i，j，k：变量 N：皇后数 (2) C程序 #include stdio.h #include math.h #define N 4 /*判断第k 个皇后目前放置位置是否与前面的皇后冲突*/ in isplace(int pos[], int k) { int i; for(i 1; ik; i++) { if( （1） ||fabs(i-k) fabs(pos[i] - pos[k])) { return 0; } } return 1; } int main() { int i,j,count 1; int pos[N+1]; //初始化位置 软酷网官网 ： for(i 1; i N; i++) { pos[i] 0; } （2） ； while(j 1) { pos[j] pos[j]+1； /*尝试摆放第i 个皇后*/ while(pos[j] N （3）_) { pos[j] pos[j]+1; } /*得到一个摆放方案*/ if(pos[j] N j══ N) { printf(方案%d: , count++); for(i 1; i N; i++){ printf(%d ,pos[i]); } printf(\n); } /*考虑下一个皇后*/ if(pos[j] N （4） ) { j j+1; } else{//返回考虑上一个皇后 pos[j] 0; （5） ; } } return 1; } 【问题1】（10 分） 根据以上说明和C 代码，填充C 代码中的空 （1）～ （5）。 【问题2】（2 分） 根据以上说明和C代码，算法采用了 （6） 设计策略。 【问题3】（3 分） 上述C 代码的输出为： （7） 。 软酷网官网 ： 【参考答案】 【问题1】 （1）pos[i] pos[k] （2）j 1 （3）isplace(pos,j) 0 （4）jN （5）j j-1 【问题2】 （6）回溯法 【问题3】 （7） 方案1：2 4 1 3 方案2：3 1 4 2 问题分析 问题描述： 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 n-皇后问题是在n行n列的棋盘上放置n个皇后，使得皇后彼此之间不受攻击