浙江大学宁波理工学院2010–2011学年2学期
《 离散数学甲 》课程期末考试试卷（A）
考生姓名 学号 考生所在分院： 专业班级： .
一、 判断题（14分，每题1分）
1 2 3 4 5 6 7 8 9
{a,b}?{a,b,c,{a,b}}。 “火星上可以住人”是命题。
( T ) ( T ) ( F ) ( F ) ( T ) ( F ) ( T ) ( F ) ( T ) ( T ) ( T ) ( F ) ( F ) ( T )
数学结构（素数 ，＋，－，×，÷），加运算是封闭的。 BANANA 中字母的不同排列数为
p?(p?q)是重言式。
6!。 3?2p ?q的逆命题是 q ? p。
如果关系R是非对称的，那么R是反对称的。
A为某非空集合，则数学结构（P(A) ，?，?）中并运算的单位元是A。 若
是一个函数，那么
是满射当且仅当处处有定义。
10 任何偏序集都有其对偶偏序集。
11 若是根树，那么是非对称的。 12 无向连通图的最小生成树是唯一的。 13 完全图不一定是正则的。
14 如果图G有奇数度的顶点，那么在G中不可能存在欧拉回路。
二、选择题（16分，每题2分）
1. 下面哪一个不是集合A?{1,2,4,7,9}的划分?（ B )。
A.{{1,2,4,7,9}}
B. {{1,9},{2,4},{1,7}} D. {{2,4,7},{1,9}}
C. {{1},{2,7},{4,9}}
2. 设A 和 B 是集合U的子集. 则(A?B)?B等于 ( D )
A. U B. A C. A?B D. A?B
3. *设 A = Z?（ 正整数 ），并且 R 为集合A上的关系： aRb当且仅当如果存在一个正整
数k，满足 a = bk. 则 R(6)是( )
第1页（共5页）
A. {1,2,3,6} B. {6}
C. {1,2,3,4,5,6} D. {6,12,18,24,...}
4. 在如下的有向图中，从V1到V4长度为3 的道路有（ B ）条。
A．1； B．2； C．3； D．4 。
5. 在如下各图中（ B ）是欧拉图。
2?:R?R,?(x)??x?2x?1,则? 是( D ). 6. ***设R为实数集合，函数
7. 设
A.
A． 单射而非满射 C. 双射
B. 满射而非单射
D. 既不是单射也不是满射. 为（C ）。 D.
和都是X上的双射函数，则
B.
C.
8. 在任何图中必定有偶数个（ C ）。
FA. 度数为偶数的结点 ； FB. 入度为奇数的结点 ； C. 度数为奇数的结点 ； FD. 出度为奇数的结点 。
三、填空题（10分，每题2分）
1. 设A={{2},{1}}，则|A|= 2 , P(A)= 略 。 2. 设A={1,2,4,8}, B={1,4,6,9}, aRb当且仅当a|b，
则R= 略 。
3. n个结点的无向完全图Kn的边数为 n*(n-1)/2 ，欧拉图的充要条件是
略 。
第2页（共5页）
四、解答题（共计60分）
1. 求公式(~p?q)?(p?~r)的真值表，并判断公式的类型。（4分） p q r ~pvq p^~r ~pvq推出p^~r 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1
0 0 0 0 1 0 1 0
0 0 0 0 1 1 1 0
2. 证明：如果任选8个正整数，那么当用7去除时，它们当中至少有两个数有相同的余
数。（3分） 8>7
3. 序列由an??3an?1?2an?2定义，初始条件为a1??2,a2?4，求序列的显式公式。 （4
分）
x^2+3x+2=0 x=-1,-2
an=u(-1)^n+v(-2)^n
a1=-u-2v a2=u+4v
v=1 u=0
an= (-2)^n
第3页（共5页）
4. 设 A = {1, 2, 3, 4}。R是A上的关系，它的有向图如图1所示，
求1) R2; 2)R? （4分）
略
图 1
5. (12分) 设集合A＝{1, 2, 3, 4, 6, 8, 12}，R是A上的整除关系，
(1) 画出偏序集(A, R)的哈塞图；
(2) 写出A的子集{2, 4, 6, 8}的上界，下界，最小上界，最大下界； (3) 写出集合A的最大元，最小元，极大元，极小元。
略
6. (分)图给出的赋权图表示五个城市及对应两城镇间公路的长度。试给出一个最优化的设
计方案使得各城市间能够有公路连通。
B3235AC5F44GE36D262
H略
7. （12分）给出下图执行前序、中序、后序搜索的结果。
第4页（共5页）
A B D E F G I K C H J 前序：ABDEFCGHIKJ 中序：EDFBAGCKIHJ 后序：EFDBGKIJHCA
8. （10分）用Fleury算法为下图构造一条欧拉回路。
略
第5页（共5页）