广东外语外贸大学信息学院
《离散数学》课程2010-2011学年第二学期期末考试试卷（A）
考卷适应信息学院2010级计算机、软件工程专业时间：120分钟
学号班级姓名成绩
一、选择题：（从四个答案中选取唯一的正确答案填到右边空格内，每题2分，共20分）：1．下列语句中是命题的为（）
A．他正在说谎； B.不准喧哗；
C．雪是黑的, 还是白的？ D. 1+Y=X。

2．设A（x）：x是人，B（x）：x犯错误，命题“如果是人，必然会犯错误”符号为（）A．∀x(A(x) →B(x));
B. ∀x(A(x)∧B(x));
C. ﹁（∃x(A(x)→⌝B(x))）;
D. ﹁（∃x(A(x)∧B(x))）.
3．设A={1，{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的为（）
A．1∈A；B. φ∈A，C。

{{4，5}}∈A；D。

{1，2}∈A.
4．集合A上的相容关系和等价关系之间的关系是（）
A．相容关系是等价关系；B。

他们都有传递性；
C．等价关系是相容关系；D。

等价关系与相容关系无关.
5．设A={a,b,c}, B={1,2} 令f：A→B，则不同的函数的个数为（）
A．2+3个；B。

2³个C。

2×3个，D。

3²个.
6．I是整数集合，函数f定义为I→I，f（x）=5x，则f是（）
A．单射；B。

满射；C。

双射；D。

非单射也非满射。

7．在自然数集N上，下列哪个运算是可结合的（）
A．a*b=min（a,b）； B. a*b=a-b； C.a*b=a+2b；D.a*b=|a-b| .
8.下列运算中，哪个运算关于自然数集不能构成半群（）
A．a هb=max（a,b）； B. a هb=b ; C. a هb= -b ; D. a هb=a+b .
9.在有n个结点的连通图中，其边数（）
A．最多有n（n-1）/2条；B。

至少有n/2条；C。

最多有n条；D。

至少有n条。

10．判定2个图同构，可靠的方法为（）
A．边数一样多；B。

点数一样多；C。

边和点一样多；D。

邻接矩阵置换等价。

二、填空题（每空1分，共20分）
1．等价关系的3个条件是、和传递。

2.（P→Q）的主析取范式为，主合取范式的编码表示为。

3. 前提：P→R, ﹁R∨S, ﹁S的有效结论是。

4. 设R是集合X上的二元关系，则r(R)= 、s(R)=、t(R)=。

5.设代数系统为：
* a b c
a a
b c
b b
c a
c c a b
幺元是，满足交换率吗？，每个元素是否有逆元。

6.设G=<V, E>, 点|V|=m, 边|E|=n, v是G中度数为L的结点，e是G的一条边，则G\v（删去结点v）后还有个结点，条边；G\e(删去边e)中有个结点，条边。

7.无向图G具有一条欧拉路，当且仅当G是，且具有
奇数度结点。

8.路与迹的区别是.
9.一个图含有K3，3子-图，还有可能是平面图吗？。

10.下图的对偶图共有个结点。

三、判断题（在括号内填上“√”或“×”，每题1分，共10分）
1．（）A：小张或小李是广外大学生，则﹁A：小张和小李都不是广外大学生。

2．（）二元关系矩阵主对角线上全是0，则必为反自反的。

3．（）每一个有限的全序集合，一定是良序集合。

4．（）实数集R上的大于等于关系“≥”是偏序关系。

5．（）设<A,﹡> 是一个代数系统，a∈A ，如果a 有左零元则必有右零元。

6．（）具有n个结点的简单图，每对结点度数之和>n，则图一定是汉密尔顿图。

7．（）具有两个元素的集合A，它的幂集中的元素数是5个。

8．（）连通图必有桥。

9．（）有一条欧拉回路的图是汉密尔顿图。

10．（）连通平面图的点数v，边数e，面数r的关系是v + e –r =2。

四、画出具有下列条件的有5个结点的无向图.
(1)不是哈密顿图，也不是欧拉图；
(2) 有哈密顿回路，没有欧拉回路；
(3) 没有哈密顿回路，有欧拉回路；
(4) 是哈密顿图，也是欧拉图.（10分）
五、偏序集< A， >的哈斯图如右图，请写出所有的序偶，A的最大元，最小元，极大元和
极小元.（10分）
b
六、每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。

（10分）
七、对于任何图G，其边的连通度为λ（G），图的各点的最小度为δ（G）。

证明：λ（G）≤δ（G）(6分)
八、试证明下图中两个无向图是不同构的。

（８分）
九．设<G， >为群,G中元素a的阶为k,那么,a n = e当且仅当k整除n（６分）。