試題四
閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3，將解答填入對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某餐廳供應(yīng)各種標(biāo)準(zhǔn)的營(yíng)養(yǎng)套餐。假設(shè)菜單上共有n項(xiàng)食物m1，m2，…，mn，每項(xiàng)食物mi的營(yíng)養(yǎng)價(jià)值為vi，價(jià)格為pi其中i＝1，2，…，n，套餐中每項(xiàng)食物至多出現(xiàn)一次。客人常需要一個(gè)算法來(lái)求解總價(jià)格不超過(guò)M的營(yíng)養(yǎng)價(jià)值最大的套餐。
【問(wèn)題1】
下面是用動(dòng)態(tài)規(guī)劃策略求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲械目杖?1)、(2)和(3)處。
偽代碼中的主要變量說(shuō)明如下。
n：總的食物項(xiàng)數(shù)；
v：營(yíng)養(yǎng)價(jià)值數(shù)組，下標(biāo)從1到n，對(duì)應(yīng)第1到第n項(xiàng)食物的營(yíng)養(yǎng)價(jià)值；
p：價(jià)格數(shù)組，下標(biāo)從1到n，對(duì)應(yīng)第1到第n項(xiàng)食物的價(jià)格；
M：總價(jià)格標(biāo)準(zhǔn)，即套餐的價(jià)格不超過(guò)M；
x：解向量(數(shù)組)，下標(biāo)從1到n，其元素值為0或1，其中元素值為0表示對(duì)應(yīng)的食物不出現(xiàn)在套餐中，元素值為1表示對(duì)應(yīng)的食物出現(xiàn)在套餐中；
nv：n+1行M+1列的二維數(shù)組，其中行和列的下標(biāo)均從0開始，nv[i][j]表示由前i項(xiàng)食物組合且價(jià)格不超過(guò)j的套餐的最大營(yíng)養(yǎng)價(jià)值。問(wèn)題最終要求的套餐的最大營(yíng)養(yǎng)價(jià)值為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]
【問(wèn)題2】
現(xiàn)有5項(xiàng)食物，每項(xiàng)食物的營(yíng)養(yǎng)價(jià)值和價(jià)格如下表所示。

食物營(yíng)養(yǎng)價(jià)值及價(jià)格表
若要求總價(jià)格不超過(guò)100的營(yíng)養(yǎng)價(jià)值最大的套餐，則套餐應(yīng)包含的食物有  (4)  (用食物項(xiàng)的編碼表示)，對(duì)應(yīng)的最大營(yíng)養(yǎng)價(jià)值為  (5)  。
【問(wèn)題3】
問(wèn)題1中偽代碼的時(shí)間復(fù)雜度為  (6)  (用O符號(hào)表示)。

試題五
閱讀下列說(shuō)明和C函數(shù)，將應(yīng)填入  (n)  處的字句寫在對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
已知集合A和B的元素分別用不含頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，函數(shù)Difference()用于求解集合A與B的差集，并將結(jié)果保存在集合A的單鏈表中。例如，若集合A＝{5，10， 20，15，25，30}，集合B＝{5，15，35，25}，如圖(a)所示，運(yùn)算完成后的結(jié)果如圖(b)所示。

鏈表結(jié)點(diǎn)的結(jié)構(gòu)類型定義如下：
typedef struct Node{
ElemType elem；
struct Node *next；
}NodeType；
【C函數(shù)】
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；
}
}
}

試題六
閱讀下列說(shuō)明和C++代碼，將應(yīng)填入  (n)  處的字句寫在對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
已知某類庫(kù)開發(fā)商提供了一套類庫(kù)，類庫(kù)中定義了Application類和Document類，它們之間的關(guān)系如下圖所示。其中，Application類表示應(yīng)用程序自身，而Document類則表示應(yīng)用程序打開的文檔。Application類負(fù)責(zé)打開一個(gè)已有的以外部形式存儲(chǔ)的文檔，如一個(gè)文件，一旦從該文件中讀出信息后，它就由一個(gè)Document對(duì)象表示。
當(dāng)開發(fā)一個(gè)具體的應(yīng)用程序時(shí)，開發(fā)者需要分別創(chuàng)建自己的Application和Document子類，例如上圖中的類MyApplication和類MyDocument，并分別實(shí)現(xiàn)Application和 Document類中的某些方法。
已知Application類中的openDocument方法采用了模板方法(Template Method)設(shè)計(jì)模式，該方法定義了打開文檔的每一個(gè)主要步驟，如下所示：

1．首先檢查文檔是否能夠被打開，若不能打開，則給出出錯(cuò)信息并返回；
2．創(chuàng)建文檔對(duì)象；
3．通過(guò)文檔對(duì)象打開文檔；
4．通過(guò)文檔對(duì)象讀取文檔信息；
5．將文檔對(duì)象加入到Application的文檔對(duì)象集合中。
【C++代碼】
#include＜iostream＞
#include＜vector＞
using namespace std；
class Document{
public：
void save(){/*存儲(chǔ)文檔數(shù)據(jù)，此處代碼省略*/)
void open(string docName){ /*打開文檔，此處代碼省略*/)
void close(){  /*關(guān)閉文檔，此處代碼省略*/)
virtual void read(string docName) ＝0；
}；
class Appplication{
private：
vector＜  (1)  ＞  docs；  /*文檔對(duì)象集合*/
public：
bool canOpenDocument(string docName){
/*判斷是否可以打開指定文檔，返回真值時(shí)表示可以打開，
返回假值表示不可打開，此處代碼省略*/
}
void addDocument(Document * aDocument){
/*將文檔對(duì)象添加到文檔對(duì)象集合中*/
docs.push_back(  (2)  )；
}
virtual Document * doCreateDocument()＝0；/*創(chuàng)建一個(gè)文檔對(duì)象*/
void openDocument(string docName){/*打開文檔*/
if  (  (3)  ){
cout＜＜“文檔無(wú)法打開!”＜＜endl；
return；
}
(4)   adoc＝   (5)  ；
(6)  ；
(7)  ；
(8)  ；
}
}；