给定解释I如下:个体域为整数集合DI;DI中特定元素a0=0,a1=1;DI上特定函数f(x,y)=x-y,g(x,y)=x+y;DI上特定谓
给定解释I如下:个体域为整数集合DI;DI中特定元素a0=0,a1=1;DI上特定函数f(x,y)=x-y,g(x,y)=x+y;DI上特定谓词F(x,y)为x<y.
给定以下公式,并在解释I下,求出公式的真值.
给定解释I如下:个体域为整数集合DI;DI中特定元素a0=0,a1=1;DI上特定函数f(x,y)=x-y,g(x,y)=x+y;DI上特定谓词F(x,y)为x<y.
给定以下公式,并在解释I下,求出公式的真值.
第1题
给定公式
(1)在解释I1中,个体域D={a},证明公式A在I1下的真值为1。
(2)在解释I2中,个体域D={a1,a2,…,an},n≥2,A在I2下的真值还一定是1吗?为什么?
第2题
设解释I为:
(a)个体域为实数集R。
(b)R上特定元素
(c)R上特定函数
(d)R上特定谓词
I下的赋值σ:σ(x)=1,σ(y)=-1。
讨论下列各式在I和σ下的真值。
第3题
v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)×d(u,v).树根处已设置了服务机构,现在要在树T中增设k处独立服务机构,使得整棵树T的服务转移费用最小.服务机构的独立性是指任例两个服务机构之间都不存在有向路径.
算法设计:对于给定的有向树T:计算在树T中增设k处独立服务机构的最小服务转移费用.
数据输入:由文件input.txt.给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数:k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.接下来的n行中,每行存表示有向树T的一条有向边的3个整数.第i+1行的3个整数wi、vi、di分别表示编号为i的顶点的权为wi,相应的有向边为(i,vi),其边长为di.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
第7题
代数系统<l,+>(其中I是整数集合+是管通加法),I对+的幺元为().零元为().对任一=().
第8题
0-1背包问题描述如下:给定n种物品和一背包.物品i的重量是wi,其价值为vi,背包的容量为C.问应如何选择装入背包的物品,使得装入背包中物品的总价值最大,在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定C>0,wi>0,vi>0(1≤i≤n),要求n元0-1向量,使得,而且达到最大.因此,0-1背包问题是一个特殊的整数规划问题.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和C,分别表示有n种物品,背包的容量为C.接下来的2行中,每行有n个数、分别表示各物品的价值和重量.
结果输出:将最佳装包方案及其最大价值输出到文件output.txt.文件的第1行是最大价值,第2行是最佳装包方案.
第9题
在整数集合I中,+是普通加法运算,关于+的幺元为(),关于+的零元(),对任意xI,
-1=().
第10题
根据文字说明,请在以下______处填充适当的语句。
采用静态链表作存储结构,设置一个大小为2n-1的数组,令数组的每个元素由四个域组成:wt是结点的权值;lehild、rchild分别为结点的左、右孩子指针;parent是结点的双亲在数组中的下标。其数组元素类型定义如下:
typedef struet
{ float wt; /*权值*/
int parent,lchild rchild; /*指针域*/
}node;
typedef node hftree[2*n-1];
在这种存储结构上的哈夫曼算法可描述如下:
void huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/
{ int i,j,x,y;
float m,n;
for(i=0;i<2*k-1;i++)
{ T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;
if(______)T[i].wt=W[i];
else T[i].wt=0
}
for(i=0;i<k-1;i++)
{ x=0;y=0;m=maxint;n=maxint;
for(j=0;j<k-i,j++)
if(T[j].wt<m)&&(T[j].parent==-1){n=m;y=___;m=___;x=j;}
else if(T[j].wt<n)&&(T[j].parent==-1)){n=T[j].wt;y=j;)
}
T[x].parent=______;T[y].parent=______;
T[k+i].wt=______;
T[k+i].lchild=______;T[k+i].rchild=______;
}