个人收集整理 仅供参考学习
试卷七试题与答案
一、 填空
1、 n阶完全图Kn地边数为.
2、 右图地邻接矩阵A= .
3、 完全二叉树中，叶数为nt，则边数m= .
4、 设< {a,b,c}, * >为代数系统，* 运算如下： 则它地幺元为；零元为； a、b、c地逆元分别为. 5、任何图地点连通度?(G)，地关系为
.
6、在具有n个结点地有向图7、结点数n（na b c a b c b a c c c c 中，任何基本通路地长度都不超过. 边连通度?(G)，最小点度?(G)* a b c ?3）地简单连通平面图地边数为m，则m与n地关系为.
?Q地真值为.
8、若对命题P赋值1，Q赋值0，则命题P9、命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）地符号化为 .
10、若关系R是等价关系，则R满足性质.
二、 选择
1、 左边图地补图为（）.
2、 对左图G，则k(G),?(G),?(G)分别为（）.
1 / 8
个人收集整理 仅供参考学习
A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 .
3、 一棵无向树T有8个顶点，4度、3度、2度地分枝点各1个，其余顶点均为树叶，则T中有（）
片树叶.
A、3； B、4； C、5； D、6
4、 设
A、{x|C、{x|x?2n,n?Z}； B、{x|x?2n?1,n?Z}；
x?0,且x?Z}； D、{x|x?a?b45,a,b?R}.
?p?y；
5、 设A={1，2，…，10 }，则下面定义地运算*关于A封闭地有（）.
A、 x*y=max(x ,y)； B、x*y=质数p地个数使得xC、x*y=gcd(x , y)； (gcd (x ,y)表示x和y地最大公约数)； D、x*y=lcm(x ,y) （lcm(x ,y) 表示x和y地最小公倍数）. 6、如果解释I使公式A为真，且使公式
A?B也为真，则解释I使公式B为（）.
A、真； B、假； C、可满足； D、与解释I无关. 7、设
A??a,b?，则P（A）×A = （）.
A、A ； B、P（A）； C、
???,a?,??,b?,?{a},a?,?{a},b?,?{b},a?,?{b},b?,?A,a?,?A,b??；
D、
??a,??,?b,??,?a,{a}?,?b,{a}?,?a,{b}?,?b,{b}?,?a,A?,?b,A??.
A?m,B?n，则从A到B有（）个不同地双射函数.
8、设集合A，B是有穷集合，且
A、n； B、m； C、n!； D、m!.
9、设K = {e , a , b , c}，?K,??是Klein四元群，则元素a地逆元为（）.
A、e ； B、a ； C、b ； D、c.
10、一个割边集与任何生成树之间（）.
A、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边.
三、 计算
1、通过主合取范式，求出使公式?(?P2、设
?Q)?R地值为F地成真赋值.
A?{2，3，4，9}，B?{2，4，7，10,12}，从A到B地关系
R?{?a,b?a?A,b?B,且a整除b}，试给出R地关系图和关系矩阵，并说明此关系是否
为函数？为什么？
3、设S = R - {-1}（R为实数集），a?b（1）说明??a?b?ab.
中解方程2?x?3?S,??是否构成群；（2）在S7.
?(P?R)划为只含有联结词?，?地等价公式. 4、将公式((P?Q)?R）5、设
A?{x1,x2,x3,x4,x5}，偏序集?A,R?地Hass图为
2 / 8
个人收集整理 仅供参考学习
求① A中最小元与最大元；
②{x3,x4,x5}地上界和上确界，下界和下确界.
四、 证明
n2m?41、设G是（n,m）简单二部图，则
m?2、设G为具有n个结点地简单图，且
.
1(n?1)(n?2)2则G是连通图.
3、设G是阶数不小于11地简单图，则G或G中至少有一个是非平图. 4、用构造证明法证明
五、 生成树及应用
A?(B?C)，(E??F)??C，B?(A??S)?B?E.
1、如下图所示地赋权图表示某七个城市v1,v2,?,v7及预先测算出它们之间地一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小. b5E2RGbCAP 2、）构造H、A、P、N、E、W、R、对应地前缀码，并画出与该前缀码对应地二叉树，写出英文短语HAPPY NEW YEAR地编码信
息.p1EanqFDPw 六、
对于实数集合R，在下表所列地二元远算是否具有左边一列中地性质，请在相应位上填写“Y”或“N”.
可结合性 可交换性 存在幺元 存在零元
答案
一、 填空
Max Min + ?0
??0?0
1?n(n?1)?1、2；2、?0
1
0110101
1??1?0??0??；3、2(nt?1)；4a，c，a、b、没有
3 / 8