试题七
阅读下列说明和Java代码,将应填入 (n) 处的字句写在对应栏内。
【说明】
已知某类库开发商捉供了一套类库,类库中定义了Application类和Document类,它们之间的关系如下图所示,其中,Application类表示应用程序自身,而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档,如一个文件,一旦从该文件中读出信息后,它就由一个Document对象表示。
当开发一个具体的应用程序时,开发者需要分别创建自己的Application和Document子类,例如上图中的类MyApplication和类MyDocument,并分别实现Application和 Document类中的某些方法。
已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式,该方法定义了打开文档的每一个主要步骤,如下所示:
1.首先检查文档是否能够被打开,若不能打开,则给出出错信息并返回;
2.创建文档对象;
3.通过文档对象打开文档;
4.通过文档对象读取文档信息;
5.将文档对象加入到Application的文档对象集合中。
【Java代码】
abstract class Document{
public void save(){/*存储文档数据,此处代码省略*/ )
public void open(String docName){ /*打开文档,此处代码省略*/)
public void close(){ /*关闭文档,此处代码省略*/)
public abstract void read(String docName);
};
abstract class Appplication{
private Vector< (1) > docs; /*文档对象集合*/
public boolean canOpenDocument(String docName){
/*判断是否可以打开指定文档,返回真值时表示可以打开,
返回假值表示不可打开,此处代码省略*/
}
public void addDocument(Document aDocument){
/*将文档对象添加到文档对象集合中*/
docs.add( (2) );
}
public abstract Document doCreateDocument();/*创建一个文档对象*/
public void openDocument(String docName){/*打开文档*/
if ( (3) ) {
System.out.println(“文档无法打开!”);
return;
}
(4) adoc= (5) ;
(6) ;
(7) ;
(8) ;
}
};
试题四
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。
【说明】
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
【问题1】
下面是用动态规划策略求解该问题的伪代码,请填充其中的空缺(1)、(2)和(3)处。
伪代码中的主要变量说明如下。
n:总的食物项数;
v:营养价值数组,下标从1到n,对应第1到第n项食物的营养价值;
p:价格数组,下标从1到n,对应第1到第n项食物的价格;
M:总价格标准,即套餐的价格不超过M;
x:解向量(数组),下标从1到n,其元素值为0或1,其中元素值为0表示对应的食物不出现在套餐中,元素值为1表示对应的食物出现在套餐中;
nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下:
MaxNutrientValue(n,v,p,M,x)
1 for i=0 to n
2 nv[i][0] = 0
3 for j=1 to M
4 nv[0][j]=0
5 for i=1 to n
6 for j=1 to M
7 if j<p[i] //若食物mi不能加入到套餐中
8 nv[i][j] = nv[i-1][j]
9 else if (1)
10 nv[i][j]= nv[i-1][j]
11 else
12 nv[i][j]= nv[i-1][j-p[i]] + v[i]
13 j = M
14 for i=n downto 1
15 if (2)
16 x[i] = 0
17 else
18 x[i] = 1
19 (3)
20 return x and nv[n][M]
【问题2】
现有5项食物,每项食物的营养价值和价格如下表所示。
食物营养价值及价格表
若要求总价格不超过100的营养价值最大的套餐,则套餐应包含的食物有 (4) (用食物项的编码表示),对应的最大营养价值为 (5) 。
【问题3】
问题1中伪代码的时间复杂度为 (6) (用O符号表示)。
试题五
阅读下列说明和C函数,将应填入 (n) 处的字句写在对应栏内。
【说明】
已知集合A和B的元素分别用不含头结点的单链表存储,函数Difference()用于求解集合A与B的差集,并将结果保存在集合A的单链表中。例如,若集合A={5,10, 20,15,25,30},集合B={5,15,35,25},如图(a)所示,运算完成后的结果如图(b)所示。
链表结点的结构类型定义如下:
typedef struct Node{
ElemType elem;
struct Node *next;
}NodeType;
【C函数】
void Difference(NodeType **LA,NodeType *LB.
{
NodeType *pa, *pb, *pre, *q;
pre=NULL;
(1) ;
while (pa) {
pb=LB;
while( (2) )
pb=pb->next;
if( (3) ) {
if(!pre)
*LA= (4) ;
else
(5) =pa->next;
q = pa;
pa=pa->next;
free(q);
}
else {
(6) ;
pa=pa->next;
}
}
}
试题六
阅读下列说明和C++代码,将应填入 (n) 处的字句写在对应栏内。
【说明】
已知某类库开发商提供了一套类库,类库中定义了Application类和Document类,它们之间的关系如下图所示。其中,Application类表示应用程序自身,而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档,如一个文件,一旦从该文件中读出信息后,它就由一个Document对象表示。
当开发一个具体的应用程序时,开发者需要分别创建自己的Application和Document子类,例如上图中的类MyApplication和类MyDocument,并分别实现Application和 Document类中的某些方法。
已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式,该方法定义了打开文档的每一个主要步骤,如下所示:
1.首先检查文档是否能够被打开,若不能打开,则给出出错信息并返回;
2.创建文档对象;
3.通过文档对象打开文档;
4.通过文档对象读取文档信息;
5.将文档对象加入到Application的文档对象集合中。
【C++代码】
#include<iostream>
#include<vector>
using namespace std;
class Document{
public:
void save(){/*存储文档数据,此处代码省略*/)
void open(string docName){ /*打开文档,此处代码省略*/)
void close(){ /*关闭文档,此处代码省略*/)
virtual void read(string docName) =0;
};
class Appplication{
private:
vector< (1) > docs; /*文档对象集合*/
public:
bool canOpenDocument(string docName){
/*判断是否可以打开指定文档,返回真值时表示可以打开,
返回假值表示不可打开,此处代码省略*/
}
void addDocument(Document * aDocument){
/*将文档对象添加到文档对象集合中*/
docs.push_back( (2) );
}
virtual Document * doCreateDocument()=0;/*创建一个文档对象*/
void openDocument(string docName){/*打开文档*/
if ( (3) ){
cout<<“文档无法打开!”<<endl;
return;
}
(4) adoc= (5) ;
(6) ;
(7) ;
(8) ;
}
};