阅读下列说明和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

int maxL(int*b, int n) {

int i, temp=0;

for(i=0; 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

scanf("%d", &a[i]);

}

(1) ;

for(i=1; i

for(j=0, len=0; (2) ; j++) {

if( (3) && len

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的元素值。

答案：

本题解析：

【问题1】

（1）b[0]=1

（2）j＜i

（3）a[j]＜=a[i]

（4）b[i]=len+1

【问题2】（4分）

（5）动态规划法

（6）O(n2)

【问题3】（5分）

B={1，2，2，3，3，4}

更新时间：2022-10-25 15:26

纠错

你可能感兴趣的试题

问答题

查看答案

问答题

阅读下列说明和C++代码，将应填入（ ）处的字句写在答题纸的对应栏内。

【说明】

某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件，且能够Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，现采用桥接（Bridge）模式进行设计，得到如图5-1所示的类图。

【c++代码】

#include

#include

using namespace std;

class matrix{//各种格式的文件最终都被转化为像素矩阵

//此处代码省略

};

class implement{

public:

(1) ;//显示像素矩阵m

};

class winimp:public implementor{

public:

void dopaint(matrix m){/*调用windows系统的绘制函数绘制像素矩阵*/}

};

class linuximp: public implementor{

public:

void dopaint(matrix m){/*调用linux系统的绘制函数绘制像素矩阵*/}

};

class imag{

public:

void setimp(implementor *imp){this.imp=imp;}

virtual void parsefile(string filename)=0;

protected:

implenentor *imp;

};

class bmpimage:public image{

//此处代码省略

};

class gifimage:public image{

public:

void parsefile(string filename){

//此处解析gif文件并获取一个像素矩阵对象m

(2) ;//显示像素矩阵m

}

};

class jpegimage:public image{

//此处代码省略

};

int main(){

public static void main(string[] args){

//在linux操作系统上查看demo.gif图像文件

imag imag= (3) ;

implementor imageimp= (4) ;

(5) ;

image.parsefile(“demo.gif”);

}

}

查看答案

问答题

某咖啡店售卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如下表所示。

查看答案

问答题

阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。

【说明】

一个无向连通图G点上的哈密尔顿（Hamiltion）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。哈密尔顿回路算法的基础如下：假设图G存在一个从顶点V0出发的哈密尔顿回路V1--V2--V3--...--Vn-1--V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，..。；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。

【C代码】

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

（1）常量和变量说明

n :图G中的顶点数

c［］［］:图G的邻接矩阵

K:统计变量，当前已经访问的顶点数为k+1

x［k］:第k个访问的顶点编号，从0开始

Visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问

（2）C程序

#include

#include

#define MAX 100

void Hamilton（int n,int x［MAX] , int c[MAX][MAX]）｛

int i;

int visited[MAX];

int k;

/*初始化x数组和visited数组*/

for （i=0:i

x[i]=0;

visited [i]=0;

｝

/*访问起始顶点*/

k=0

（1）；

x[0]=0 ;

k=k+1 ;

/*访问其他顶点*/

while（k>=0）｛

x[k]=x[k]+1;

while（x[k]

if （（2）&& c [x[k-1]] [x[k]] ==1）｛/*邻接顶点x[k]未被访问过*/

break；

｝else｛

x[k] = x[k] +1

｝

｝

if（x[k]

for （k=0;k

printf（〝%d--〝,x[k] ) ; /*输出哈密尔顿回路*/

｝

printf（〝%d\n〝,x[0] ) ;

return；

｝else if (x[k]

（4）

k=k+1;

｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/

x[k]=0；

visited [x[k]]=0；

（5）；

｝

｝

｝

【问题1】（10分）

根据题干说明。填充C代码中的空（1）～（5）。

【问题2】（5分）

根据题干说明和C代码，算法采用的设计策略为（ ），该方法在遍历图的顶点时，采用的

是（ ）方法（深度优先或广度优先）。

查看答案

问答题

阅读以下说明和C程序，将应填入 (n) 处的字句写在对应栏内。[说明]

下面的程序用Dole Rob算法生成N阶(N为奇数)魔方阵(各行、列、对角线数字之和相等)。该算法的过程为：从1开始，按如下方法依次插入各自然数，直到N2为止。

①在第一行的正中插入1。

②新位置应当处于最近插入位置的右上方，若该位置已超出方阵的上边界，则新位置取应选列的最下一个位置；若超出右边界，则新位置取应选行的最左一个位置。

③若最近插入的元素是N的整数倍，则选同列的下一行位置为新位置。

例如，3阶魔方阵如下所示：

8 1 6

3 5 7

4 9 2

[C程序]

include＜stdio.h＞

include＜stdlib.h＞

define SIZE 50

main()

{

int row, col, n, value;

int a[SIZE+1][SIZE+1]; /*不使用下标为0的元素*/

printf("请输入要输出魔方阵的阶数n(奇数, ＜%d):n=", SIZE);

scanf("%d", &n);

if(!(n%2) || n＜1 || (1) ){

printf("输入数据有误!\n");

exit(0);

}

row=1; col=(n+1)/2; value=1;

while(value＜= (2) ) {

a[row][col]=value;

/*计算下一位置*/

if(value%n!=0){

row--; (3) ;

if(row＜1)row=n;

if(col＞n) (4) ;

}

else row++;

value= (5) ;

}

printf("\n%d阶魔方阵如下所示：\n\n", n);

for(row=1; row＜=n; row++){

for(col=1; col＜=n; col++)

printf("%5d", a[row][col]);

printf("\n");

}

}

查看答案

问答题

阅读下列说明和Java代码，将应填入（ ）处的字句写在答题纸的对应栏内。

【说明】

某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件，且能够在Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，现采用桥接模式进行设计，得到如图6-1所示的类图。

【Jave代码】

【Jave代码】

Import java.util.*;

class Matrix{ //各种格式的文件最终都被转化为像素矩阵

//此处代码省略

｝；

abstract class Implementor｛

Public（1）;//显示像素矩阵 m

｝；

class WinImp extends Implementor｛

public void doPaint（Matrix m）{ //调用 Windows 系统的绘制函数绘制像素矩阵

｝

｝；

class LinuxImp extends Implementor{

public void doPaint（Matrix m）{ //调用 Linux 系统的绘制函数绘制像素矩阵

｝

｝；

abstract class Image｛

public void setImp（Implementor imp）{ this.imp= imp; }

public abstract void parseFile（String fileName）;

protected Implementor imp;

｝;

class BMPImage extends Image｛

//此处代码省略

｝；

class GIFImage extends Image｛

public void parseFile（String fileName） ｛

//此处解析BMP文件并获得一个像素矩阵对象m

（2）；//显示像素矩阵m

｝

｝；

Class Main｛

Public static viod main（String[]args）｛

//在Linux操作系统上查看demo.gif图像文件

Image image=（3）

Implementor imageImp=（4）

（5）

Image.parseFile（〝demo.gif〝）；

｝

｝

查看答案

问答题

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

【说明】

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

【Java代码】

【Java代码】

class Light {

public Light() {}

public Light(String name) { /* 代码省略 */ }

public void on() { /* 代码省略 */ } // 开灯

public void off() { /* 代码省略 */ } // 关灯

// 其余代码省略

}

（1） {

public void execute();

}

class LightOnCommand implements Command { // 开灯命令

Light light;

public LightOnCommand(Light light) { this.light=light; }

public void execute() { （2） ; }

}

class LightOffCommand implements 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, Command onCommand, 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=new RemoteControl();

Light livingRoomLight=new Light("Living Room");

Light kitchenLight=new Light("kitchen");

LightOnCommand livingRoomLightOn=new LightOnCommand(livingRoomLight);

LightOffCommand livingRoomLightOff=new LightOffCommand(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);

}

}

查看答案

问答题

阅读以下说明和C程序，将应填入(n)处的字句写在对应栏内。

【说明】

下面的程序按照以下规则输出给定名词的复数形式。

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')；

}

查看答案

问答题

阅读下列说明和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

int maxL(int*b, int n) {

int i, temp=0;

for(i=0; 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

scanf("%d", &a[i]);

}

(1) ;

for(i=1; i

for(j=0, len=0; (2) ; j++) {

if( (3) && len

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代码，回答问题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；

/*尝试摆放第1个皇后

/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）。

查看答案