0－1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），

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

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

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

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

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

【说明】

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

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

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

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

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

文件：

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

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

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

座位表=车次+座位号

数据流：

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

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

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

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

流名称。

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

【说明】用克鲁斯卡尔算法求解给定图的最小生成树。

include ＜stdio. h＞

include ＜stdlib. h＞

define MAXN 30

typedef struct

{ int v1,v2; /*一条边依附的两个顶点*/

int weight; /*边上的权值*/

}EDGE;

typedef struct

{ int Vnum; /*图中的顶点数目*/

EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/

}Graph;

typedef struct node{ /*用链表存储同一个连通分量的顶点*/

int v;

struct node *next;

}Alist;

void heapadjust(EDGE data[], int s, int m)

{ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/

int j;

EDGE t;

t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/

for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/

if(j＜m &&(1)) ++j;

if(!(t. weight＞data[j]. weight)) break;

data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/

}/*for*/

data[s]=t; /*将备份元素插入由s所指出的插入位置*/

}/*heapadjust*/

int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/

{ int k=0; /*记录图中边的数目*/

int n;

int v1,v2;

int w;

printf("vertex number of the graph:");

scanf("%d", &n); /*输入图中的顶点数目*/

if(n＜1) return 0;

p-＞Vnum=n;

do{ printf("edge(vertex1,vertex2,weight):");

scanf("%d %d %d", &V1, &v2, &w);

if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){

p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;

k++;

}/*if*/

}while(!( (2) ));

return k; /*返回图中边的数目*/

}/*creat_graph*/

int kruskal(Graph G, int enumber, int tree[][3])

{ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */

/*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/

int i, k, m, c=0;

int v1, v2;

Alist *p, *q, *a[MAXN];

for(i=0; i＜G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/

a[i]=(Alist*)malloc(sizeof(Alist));

if(!a[i]) {

printf("\n mernory allocation error!");

exit(0);

}/*if*/

a[i]-＞v=i; a[i]-＞next=NULL;

}/*for*/

for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/

heapadjust( (3) );

k=G. Vnum; /*k用于计算图中的连通分量数目*/

m=enumber-1;

i=0;

do{

v1=G. e[0]. v1; v2=G. e[0]. v2;

p=a[v1];

while(p && p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/

q=p; p=p-＞next;

}

if(!p){ /*当前边的顶点不在一个连通分量中*/

p=q;

p-＞next=a[G. e[0]. v2];

&nb

阅读以下说明，回答问题1～2，将解答填入对应的解答栏内。

[说明] 设某商业集团数据库中三个实体集。一是“仓库”实体集，属性有仓库号、仓库名和地址等；二是“商店”实体集，属性有商店号、商店名、地址等；三是“商品”实体集，属性有商品号、商品名、单价。

设仓库与商品之间存在“库存”联系，每个仓库可存储若干种商品，每种商品存储在若干仓库中，每个仓库每存储一种商品有个日期及存储量；商品与商品之间存在着“销售”联系，每个商品可销售若干种商品，每种商品可在若干商店里销售，每个商店销售一种商品有月份和月销售量两个属性；仓库、商店、商品之间存在着“供应”联系，有月份和月供应量两个属性。

试画出ER图，并在图上注明属性、联系类型、实体标识符；

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

[程序5说明]

下列文法可用来描述化学分子式的书写规则(例如，A12(CO3)3”Cu(OH)2)：

λ→β\βλ

β→δ\δn

δ→ξ\ξθ\(λ)

其中：λ是—个分子式；δ或是一个元素，或是一个带括号的(子)分子式，元素或是一个大写字母(记为ξ)，或是一个大写字母和一个小写字母(记为ξθ)β或是一个δ，或是在δ之后接上一个整数n，δn表示β有n个δ的元素或(子)分子式。—个完整的分子式由若干个β组成。

当然一个正确的分子式除符合上述文法规则外，还应满足分子式本身的语义要求。

下面的程序输入分子式，按上述文法分析分子式，并计算出该分子式的分子量。例如：元素H的原子量是1，元素O的原子量是16。输入分子式H2O，程序计算出它的分子量为18 (1×2+16)。程序中各元素的名及它的原子量从文件atom.dat中读入。

[程序5]

include ＜ stdio. h ＞

include ＜ string. h ＞

define MAXN 300

define GMLEN 30

struct elem { char name[ ]; /* 元素名*/

double v;/*原子量*/

} nTbl [MAXN];

char cmStr [GMLEN], * pos;

int c;FILE * fp;

double factor( );

double atom( ) /* 处理文法符号δ*/

{char w [3];int i; double num;

while((c = * pos++) =='||c =='\t'); /*略过空白字符*/

if(c == '\n') return 0.0;

if(c＞='A' && C ＜='Z') {/*将元素名存入W */

w[i =0]=c;c= * pos ++

if(c ＞='a'&& c ＜='z')w[ ++i] =c;else pos--;

w[ ++i] ='\0',

for(i =0;nTbl [i]. v ＞0.0;i ++)

if(strcmp (w,nTbl[i]. name) ==0) return nTbl [i]. v;

printf (" \n元素表中没有所输入的无素: \t%s\n',w); retur n - 1.0;

} elseif (c = ='(') {

if((num=(1)) ＜0.0)return -l.0; /*包括可能为空的情况*/

if( * pos ++ ! = ')') { printf (" 分子式中括号不匹配！/n") ;return - 1.0; }

return num;

}

printf ("分子式中存在非法字符:\t%c\n" ,c);

return - 1.0;

}

double mAtom( ) /* 处理文法符号β*/

{ double num ;int n = ];

if((num=(2)) ＜0.0)return-l.0;

c= *pos++;

if(c ＞='O'&&c ＜='9') {

n = 0; while(c ＞ = 0&&c ＜ ='9')

{n=(3);

c= *poss ++;

}

}

pos --;

return num * n;

}

double factor( ) /*处理文法符号λ*/

{ double num =0.0,d;

if(( hum = mAtom ( )) ＜ 0.0) return - 1.0;

while( * pos ＞= 'A'&& * pos ＜= 'Z'||* pos == '(') {

if((d=(4)) ＜0.0)return-1.0;

(5);

} return num;

void main( )

{ char fname[ ] ="atom. dst"; /*元素名及其原子量文件*/

int i;double num;

if((fp=fopon(fname,"r" )) == NULL) { /*以读方式打开正文文件*/

prinff("Can net open%s file. \n' ,fname) ;return /*程序非正常结束 */

i=0;

while(i ＜ MAXN&&fscanf (fp," %s%lf,bTbl[i]. name,&nTbl[i]. v) ==2)

i++;

fclose(fp) ;nTbl[i]. v =-1.0;

while(1) [/*输入分子式和计算分子量循环，直至输入空行结束*/

printf(" \n 输入分子式! (空行结束) \n" ) ;gets(cmStr);

pos = cmStr;

if(cmStr[0] == '\0') break;

if( (num = later( ) ) ＞ 0.0)

if( * pos! = '\0')printf("分子式不完整! \n" );

else printf("分子式的分子量为%f\n",num);

}