阅读下列函数说明和C函数，将应填入（n)处的字句写在对应栏内。 【说明】 函数DeleteNode（Bitree*r，in

阅读下列说明和图，回答问题1至问题3。

【说明】

某公司的主要业务是出租图书和唱碟。由于业务需求，该公司委托软件开发公司A开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。A公司决定采用面向对象的分析和设计方法开发此系统。如图3-2所示为某类图书或唱碟被借阅时应记录的信息，如图3-3所示描述了系统定义的两个类Book和CD，分别表示图书和唱碟的信息。

经过进一步分析，设计人员决定定义一个类Items_on_loan，以表示类Book和ED的共有属性和方法。请采用图3-3中属性和方法的名称给出类Items_on_loan应该具有的属性和方法 (注意：不同名称的属性和方法表示不同的含义，如CD中的composer与Book中的author无任何关系)。

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

【说明】

函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：

typedef struct Tnode{

int data； /*结点的键值*/

struct Tnode *Lchild, *Rchild； /*指向左、右子树的指针*/

}*Bitree：

在二叉查找树上删除一个结点时，要考虑3种情况：

①若待删除的结点p是叶子结点，则直接删除该结点；

②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；

③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。

【函数】

int DeleteNode (Bitree *r，int e) {

Bitree p=*r,pp，s，c；

while ( (1) ){ /*从树根结点出发查找键值为e的结点*/

pp=p;

if(e＜p-＞data) p=p-＞Lchild；

else p=p-＞Rchild；

}

if(!P) return-1； /*查找失败*/

if(p-＞Lchild && p-＞Rchild) {/*处理情况③*/

s=(2)；pp=p

while (3) {pp=s；s=s-＞Rchild;}

p-＞data=s-＞data； p=s；

}

/*处理情况①、②*/

if ( (4) ) c=p-＞Lchild；

else c=p-＞Rchild；

if(p==*r) *r=c；

else if ( (5) ) pp-＞Lchild=c；

else pp-＞Rchild=c；

free (p)；

return 0；

}

缺。

SELECT Mno, Mname, price

FROM Merchandise(1)

WHERE(2)

(SELECT(3)

FROM lnvoicedetail

WHERE A. Mno=lnvoicedetail. Mno)；

0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，，且总重量不超过背包容量，即，其中，xi∈{0,1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品 放入背包。

【问题1】（8分）

用回溯法求解此0-1背包问题，请填充下面伪代码中（1）~（4）处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。

下面给出0-1背包问题的回溯算法伪代码。

函数参数说明如下：

W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。

变量说明如下：

cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。

BKNAP(W,n,w,v,fw,fp,X）

1 cw ← cp ← 0

2 （1）

3 fp ← -1

4 while true

5 while k≤n and cw＋w[k]≤W do

6 （2）

7 cp ← cp＋v[k]

8 Y[k]← 1

9 k ← k+1

10 if k＞n then

11 if fp＜cp then

12 fp ← cp

13 fw ← ew

14 k ← n

15 X ← Y

16 else Y(k)← 0

17 while BOUND(cp,cw,k,W) ≤fp do

18 while k≠0 and Y(k)≠1 do

19 （3）

20 if k＝0 then return

21 Y[k]←0

22 cw ← cw ← w[k]

23 cp ← cp ← v[k]

24 （4）

选出正确的关系代数表达式。

查询所有“外科”病区和“内科”病区的所有医生姓名； A．σName="外科"∨Name="内科"(π4(Q))

B．σName="外科"∧Name="内科"(π4(Q))

C．π4(σName="外科"∨Name="内科"(Q))

D．π4(σName="外科"∧Name="内科"(Q))

【说明】

某直达列车车票预售系统接受顾客的订票、取票和售票处工作人员的查询业务。

1．顾客为了提前订票，可向系统提供个人信息及其预订购的车次及日期，系统根据个人信息是否齐全以及车次是否正确来判断订票单是否合格。对于合格的订票单系统，如果相应的车次有剩余票，则记录顾客个人信息以及订票信息，并向顾客提供取票单。

2．到了可以取票的时间，顾客向系统提供取票单，在检查单据合格的情况下，系统向顾客提供火车票。

3．售票处的工作人员可以利用系统查询各车次车票的售票情况。

该直达列车车票预售系统的分层数据流图中部分数据流和文件的组成如下：

文件：

火车时刻表=车次+开车时间+到站时间+起始站+终点站+上铺票价+下铺票价

订票信息表=车次+车票日期+旅客身份证号+座位号+是否领票

旅客信息表=旅客身份证号+姓名+性别+联系电话

座位表=车次+座位号

数据流：

订票单=旅客姓名+性别+身份证号+联系电话+车次十车票日期

车票=车次+起始站生终点站+开车日期+开车时间+座位号+票价

假定顶层图是正确的，“火车时刻表”和“座位表”文件已由其他系统生成。

指出哪张图的哪个文件可以不必画出。

流名称。