华东交大 试卷五试题与答案

一、

填空

．给定命题公式A、B，若 ，则称A和B是逻辑相等的。 2．命题公式(PQ)的主析取范式为 ，主合取范式

的编码表示为 。

3．设E为全集， ，称为A的绝对补，记作～A，

且～（～A）= ，～E = ，～= 。 4．设A{a,b,c}考虑下列子集

S1{{a,b},{b,c}}，S2{{a},{a,b},{a,c}}，S3{{a},{b,c}}，S4{{a,b,c}} S5{{a},{b},{c}}，S6{{a},{a,c}}

则A的覆盖有 ，A的划分有 。 5．设S是非空有限集，代数系统＜P（S），，＞中，P（S）对的幺元为 ， 零元为 。P（S）对的幺元为 ，零元为 。

6．若GV,E为汉密尔顿图，则对于结点集V的每个非空子集S，均有

W(G-S) S成立，

其中W(G-S)是 。

7、 n阶完全图结点v的度数d(v) = 。

8、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，

Nk+1个k+1度顶点，则N k = 。 9、 如图

给出格L，则e的补元是 。

10、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。

二、选择

1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（ ）。

A、群；B、环；C、域；D、格。 2、设[{a , b , c}，*]为代数系统，*运算如下：

* a b c 则零元为（ ）。

A、a； B、b； C、c； D、没有。

a a b c b b a c c c c c 3、如右图 相对于完全图K5的补图为（ ）。

4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）

4度结点。

A、1； B、2； C、3； D、4。

5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A，

+，·]是整环。

A、{x|x2n,nZ}； B、{x|x2n1,nZ}；

4C、{x|x0,且xZ}； D、{x|xab5,a,bR}。

6．任意具有多个等幂元的半群，它（ ）。

A、不能构成群； B、不一定能构成群； C、不能构成交换群； D、能构成交换群。

7．设A,是一个有界格，它也是有补格，只要满足（ ）。

A、每个元素都有一个补元； B、每个元素都至少有一个补元； C、每个元素都无补元； D、每个元素都有多个补元。 8．设GV,E为无向图，V7,E23，则G一定是（ ）。

A、完全图； B、树； C、简单图； D、多重图。

9．给定无向图GV,E，如下图所示，下面哪个边集不是其边割集（ ）。

A、{v1,v4,v3,v4}； B、{v1,v5,v4,v6}； C、{v4,v7,v4,v8}； D、{v1,v2,v2,v3}。

10．有n个结点(n3)，m条边的连通简单图是平面图的必要条件（ ）。

A、n3m6； B、n3m6； C、m3n6； D、m3n6。

三、证明

n2m4。1、设G是（n,m）简单二部图，则（10分）

2、设G为具有n个结点的简单图，且

m1(n1)(n2)2，则G是连通图。（10分）

3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：

+ 0 1 0 0 1 1 1 0

· 0 0 1 0 0 1 0 1 证明它是一个环，并且是一个域。（14分） 4、用推理规则证明：

(AB)(CD),(BE)(DF),(EF),AC├ A

5、有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种药品？

四、如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信

成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。

答 案

一、填空

1,P2,,Pn任意一组真值指派，A和B的真值相同。 1．对于A，B中原子变元P2．PQ,M00M01M11。

3．集A关于E的补集E – A ；A ；Φ；E 。 4．S1,S2,S3,S4,S5；S3，S4，S5。 5．；S；S；。 6．；GS的连通分支数。 7、n-1； 8、n(k+1)-2m； 9、0 ； 10臂力小者 二、选择 题号 答案 二、 证明

1、 证：设G=（V，E）

1 D 2 C 3 A 4 A 5 D 6 A 7 B 8 D 9 B 10 D VXY,Xn1,Yn2,n1n2n

21n2n2mn1n2n1(nn1)nn1n(n1)24 对完全二部图有

n2nn12时，完全二部图(n,m)的边数m有最大值4 当

n2m(n,m)4。 故对任意简单二部图有

2、 证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2

的顶点数分别为n1和n2，显然n1n2n

n11n21n1n1n2n1 mn1(n11)n2(n21)(n1)(n1n22)(n1)(n2)2222

与假设矛盾。所以G连通。 3、 （1）[{0，1}，+，·]是环

①[{0，1}，+]是交换群

乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；

（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0； （1+1）+1=1+（1+1）=0 „„ 结合律成立。

幺：幺元为0。

逆：0，1逆元均为其本身。 ②[{0，1}，·]是半群 乘：由“· ”运算表知封闭

群： （0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；

（0·1）·0=0·（1·0）=0 ； （0·1）·1=0·（1·1）=0； （1·1）·1=1·（1·1）=0 。 ③·对+的分配律 x,y{0,1} Ⅰ 0·（x+y）=0=0+0=(0·x)+(0·y)； Ⅱ 1·（x+y） 当x=y (x+y)=0 则

00(10)(10)1(xy)100(1x)(1y)11(11)(11)；

当xy（xy1）则

10(11)(10)1(xy)111(1x)(1y)01(10)(11)

所以x,y,z{0,1}均有z(xy)(zx)(zy)

同理可证：(xy)z(xz)(yz) 所以·对+ 是可分配的。

由①②③得，[{0，1}，+，·]是环。 （2）[{0，1}，+，·]是域

因为[{0，1}，+，·]是有限环，故只需证明是整环即可。 ①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1·1=1≠0

因此[{0，1}，+，·]是整环，故它是域。

4、证明：（1）A P（附加前提） （2）AC P

（3）C T（1）（2）I （4）(AB)(CD) P （5）CD T（4）I

（6）D T（3）（5）I （7）(BE)(DF) P （8）(BE)(DF) T（7）E （9）DF T（8）I （10）F T（6）（9）I （11）AB T（4）I （12）B T（1）（11）I （13）BE T（8）I （14）E T（12）（13）I （15）EF T（10）（14）I （16）(EF) P

（17）(EF)(EF) T（15）（16）I ∴结论有效。

5、解：用n个结点表示n个药箱，当两种药箱放一种相同药时，则对应的两点连一条边，

1n(n1)则得到一个无向完全图，因而所求药品数即为该图边数=2。

四、解： 用库斯克（Kruskal）算法求产生的最优树。算法为：

w(v1,v7)1w(v7,v2)4w(v7,v3)9w(v3,v4)3w(v4,v5)17w(v1,v6)23结果如图：

选e1v1v7选e2v7v2选e3v7v3选ev3v4选ev4v5选ev1v6

树权C(T)=23+1+4+9+3+17=57（万元）即为总造价