2021年程序员押题密卷2

阅读下列说明和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 N4/*判断第k个皇后目前放置位置是否与前面的皇后冲突*/in isplace(int pos[],int k) {int i;for(i=1; i＜k; i++) {if( （1） || fabs(i-k) ══fabs(pos[i] - pos[k])) {return();}}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）。

阅读下列说明和C++代码，回答问题，将解答填入答题纸的对应栏内。

【说明】

某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌灯具的开关，现采用Command(命令)模式实现该遥控器的软件部分。Command模式的类图如下图所示。

【C++代码】

class Light {public: Light(stringname) { /* 代码省略 */ } void on() {/* 代码省略 */ } // 开灯 void off() {/* 代码省略 */ } // 关灯};class Command {public: （1） ;}；class LightOnCommand:public Command { // 开灯命令private: Light* light;public: LightOnCommand(Light* light) { this->light=light; } voidexecute() { （2） ; }};class LightOffCommand:public Command { // 关灯命令private: Light *light;public: LightOffCommand(Light* light) { this->light=light; } voidexecute() { （3） ; }};class RemoteControl{ // 遥控器private: Command*onCommands[7]; Command*offCommands[7];public: RemoteControl() { /* 代码省略*/ } voidsetCommand(int slot, Command* onCommand, Command* offCommand) { （4） =onCommand; （5） =offCommand; } voidonButtonWasPushed(int slot) { （6） ; } voidoffButtonWasPushed(int slot) { （7） ; }};int main() { RemoteControl* remoteControl=new RemoteControl(); Light*livingRoomLight=new Light("Living Room"); Light*kitchenLight=new Light("kitchen"); LightOnCommand*livingRoomLightOn=newLightOnCommand(livingRoomLight); LightOffCommand* livingRoomLightOff=newLightOffCommand(livingRoomLight); LightOnCommand*kitchenLightOn=new LightOnCommand(kitchenLight); LightOffCommand* kitchenLightOff=new LightOffCommand(kitchenLight); remoteControl->setCommand(0, livingRoomLightOn, livingRoomLightOff); remoteControl->setCommand(1,kitchenLightOn, kitchenLightOff); remoteControl->onButtonWasPushed(0); remoteControl->offButtonWasPushed(0); remoteControl->onButtonWasPushed(1); remoteControl->offButtonWasPushed(1); /* 其余代码省略 */ return 0;}

阅读下列说明和C代码，回答问题，将解答填入答题纸的对应栏内。

【说明】

计算一个整数数组a的最长递增子序列长度的方法描述如下：

假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为 ；其中b[i]满足最优子结构，可递归定义为：

【C代码】

下面是算法的C语言实现。

（1）常量和变量说明

a：长度为n的整数数组，待求其最长递增子序列

b：长度为n的数组，b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度，其中0≤i＜n

len：最长递增子序列的长度

i, j：循环变量

temp：临时变量

（2）C程序

#include ＜stdio.h>int maxL(int*b, int n) {int i, temp=0;for(i=0; i＜n; i++) { if(b[i]>temp) temp=b[i]; } return temp;}int main() { int n,a[100], b[100], i, j, len; scanf("%d", &n); for(i=0;i＜n; i++) { scanf("%d", &a[i]); } (1) ; for(i=1;i＜n; i++) { for(j=0,len=0; (2) ; j++) { if( (3) && len＜b[j]) len=b[j]; } (4) ; } Printf("len:%d\n", maxL(b,n)); printf("\n");}

【问题1】（8分）

根据说明和C代码，填充C代码中的空（1）～（4）。

【问题2】（4分）

根据说明和C代码，算法采用了 （5） 设计策略，时间复杂度为 （6） （用O符号表示）。

【问题3】（5分）

已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。

阅读以下说明和C程序，将应填入 (n) 处的字句写在对应栏内。 2、【说明】下面的程序按照以下规则输出给定名词的复数形式。 a．若名词以“y”结尾，则删除y并添加“ies”； b．若名词以“s”、“ch”或“sh”结尾，则添加“es”； c．其他所有情况，直接添加“s”。【C程序】 #include ＜stdio．h＞ #include ＜string．h＞ char*plural(char *word) { int n； char *pstr； n＝strlen(word)； /*求给定单词的长度*/ pstr＝(char*)malloc(n+3)；/*申请给定单词的复数形式存储空间*/ if (!pstr||n＜2) return NULL； strcpy(pstr，word)； /*复制给定单词*/ if ( (1) ) { pstr[n-1]＝'i'；pstr[n] ＝'e'；pstr[n+1]＝'s'； (2) ； } else if(pstr[n-1]＝＝'s'| |pstr[n-1]＝＝'h'&&( (3) )) { pstr[n]＝'e'；pstr[n+1]＝'s'；pstr[n+2]＝'\0'； } else { pstr[n]＝'s'；pstr[n+1]＝'\0'；) (4) ； } main() { int i； char *ps； char wc[9][10]＝ {"chair"，"dairy"，"boss"，"circus"，"fly"，"dog"，"church"，"clue"，"dish")； for(i ＝ 0；i＜9； i++) { ps＝ (5) ； printf("%s： %s\n"，wc[i]，ps)； /*输出单词及其复数形式*/ free(ps)； /*释放空间*/ } system("pause")； }

阅读下列说明和Java代码，回答问题，将解答填入答题纸的对应栏内。

【说明】

某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌灯具的开关，现采用Command(命令)模式实现该遥控器的软件部分。Command模式的类图如下图所示。

【Java代码】

class Light { public Light() {} public Light(String name) { /* 代码省略 */ } public void on() { /* 代码省略 */ } // 开灯 public void off() { /* 代码省略 */ } // 关灯 // 其余代码省略} （1） { public void execute();} class LightOnCommandimplements Command { // 开灯命令 Light light; public LightOnCommand(Light light) {this.light=light; } public void execute() { （2） ; }}class LightOffCommandimplements Command { // 关灯命令 Light light; public LightOffCommand(Light light) {this.light=light; } public void execute(){ （3） ; }}class RemoteControl { //遥控器 Command[] onCommands=new Command[7]; Command[] offCommands=new Command[7]; public RemoteControl() { /* 代码省略 */ } public void setCommand(int slot, CommandonCommand, Command offCommand) { （4） =onCommand; （5） =offCommand; } public void onButtonWasPushed(int slot) { （6） ; } public void offlButtonWasPushed(int slot){ （7） ; }}class RemoteLoader { public static void main(String[] args) { RemoteControl remoteControl=newRemoteControl(); Light livingRoomLight=newLight("Living Room"); Light kitchenLight=newLight("kitchen"); LightOnCommand livingRoomLightOn=newLightOnCommand(livingRoomLight); LightOffCommand livingRoomLightOff=newLightOffCommand(livingRoomLight); LightOnCommand kitchenLightOn=newLightOnCommand(kitchenLight); LightOffCommand kitchenLightOff=newLightOffCommand(kitchenLight); remoteControl.setCommand(0,livingRoomLightOn, livingRoomLightOff); remoteControl.setCommand(1, kitchenLightOn,kitchenLightOff); remoteControl.onButtonWasPushed(0); remoteControl.offButtonWasPushed(0); remoteControl.onButtonWasPushed(1); remoteControl.offButtonWasPushed(1); }}