2012-2013(1)离散数学试卷及答案B卷
- 格式：doc
- 大小：17.00 KB
- 文档页数：5
浙江工业大学期终考试命题稿
2010 /2011 学年第 1 学期
命题注意事项：
一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑墨水书写，保持字迹清晰，页码完整。
二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处抽定A、B卷。
三、命题稿必须经学院审核，并在考试前两周交教务处。
浙江工业大学2012/2013 学年
第1学期试卷
课程＿＿＿＿＿＿＿＿ 姓名 ＿＿＿＿＿＿＿＿
班级＿＿＿＿＿＿＿＿ 学号 ＿＿＿＿＿＿＿＿
一、选择 15分 （每小题 3分）
1．下列语句是命题的是（ A ）。
A、离散数学是重要的一门必修课。 B、1+101=110？
C、我正在说谎。D、全体起立！
2．图 的邻接矩阵为( C )。
A、 B、 C、 D、
3．下列排列能构成图的顶点度序列的是（ A ）。
A、1,2,2,3,4 B、2,3,4,5,6,7 C、2,1,1,1,2 D、3,3,5,6,0
4．设，则IA =（ D ）。
A、 A ； B、A×IA； C、 IA×A； D、。
5．下述命题公式中，是重言式的为（ C ）。
A、； B、；
C、； D、。 二、填空题15分 （每小题 3分）
1已知一棵无向树T有三个3度顶点,一个2度顶点,其余的都是1度顶点,
则T中有 5 个1度顶点。
2．设A={1，2，3，4}，A上二元关系R={<2,2>,< 2,3>, < 3,2>, <
3,1>}，则S(R)=
{<2,2>,<2,3>,<3,2>,<3,1>,<1,3>}。
3．A={1，2，3，4，5，6}，A上二元关系，则用列举法给出T={<2,1>,<3,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<4,2>,<6,3>,<5,1>,<6,2>}。
4．任何(n,m)图 G=(V,E),边数与顶点数的关系是 m=n-1/sum(d(vi))=2m
5．设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是
对于任何素数都存在一个能整除它的奇数
三、计算或推理题（30’，每题6分）
1、 求前束范式。
2、证明：PÚQ，Q®R，P®S，ØS Þ R
证明：
(1) ØS P前提
(2) P®S P前提
(3) ØP T(1)(2)I拒取式
(4) PÚQ P前提
(5) Q T(3)(4)I析取三段论
(6) Q®R P前提
(7) R T(5)(6)I假言推理 3．设A={a,b,c,d}，R为A上的关系，R={
r(R)={
s(R)={
t(R)={
4．已知偏序集
A={a,b,c,d,e,f,g,h}
R={
5．列举集合A＝{a,b,c,d}上所有不同的等价关系。
只要求出A上的全部划分，即为等价关系。
划分为一个块的情况：1种，即{a,b,c,d}
划分为两个块的情况：7种，即
{{a,b},{c,d}}，{{a,c},{b,d}}，{{a,d},{b,c}}
{{a},{b,c,d}}，{{b},{a,c,d}}，{{c},{a,b,d}}，
{{d},{a,b,c}}
划分为三个块的情况：6种，即
{{a,b},{c},{d}}，{{a,c},{b},{d}}，{{a,d},{b},{c}},
{{a},{b},{c,d}}，{{a},{c},{b,d}}，{{a},{d},{b,c}}
划分为四个块的情况：1种，即{a},{b},{c},{d}}
因此，共有15种不同的等价关系。
四 逻辑推理(10’)： 有些女孩喜欢各种香水，但女孩都不喜欢有毒物体，所以香水都不是有毒物体。
答：
M(x): x是女孩， D(x): x是香水， Q(x): x是有毒的， L(x,y): x喜欢y
前提：
结论：
五 树的应用（10’）
根据下图求最小生成树，假设生成树中五个节点a, b, c, d, e的权重分别为12、8、15、7、6，求传输它们的最佳前缀码（构造最优二叉树）。
a: 00 c: 11 e: 101
b: 01 d: 100
六、（10’）
●
画出该图形的对偶图形，为对偶图按韦尔奇.鲍威尔方法按步骤进行着色（颜色用数字表示）。要求着色的过程和每一步骤都要具体写出。
排序 ：a b c d e f
第一次：a e
第二次：b f
第三次：c
第四次：d
七、包含排斥原理（10’）
24名科技人员，每人至少会1门外语.
英语：13； 日语：5； 德语：10； 法语：9
英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语
求：只会 1 种语言人数，会 3 种语言人数？
x+2(4-x)+y1+2=13
x+2(4-x)+y2=10
x+2(4-x)+y3=9
x+3(4-x)+y1+y2+y3=19
x=1, y1=4, y2=3, y3=2
