2008-2009学年第 1学期 考试时间共 120分钟
课程：《离散数学》（B卷） 课程代码110094 课程班号 07计机1/2、07软件1/2，06信科1/2、06应数 （共7个班，297人） 共2页
-----------------------------------------------------------------------------------------------------------------------
一、选择题（共10分，每小题1分）
1、设（A，*）是代数系统，若el是它的左幺元，则对A中任意元素a，都有：
A、el*a= el B、a *el= el C、el*a= a D、a *el= a
2、设（A， *）是代数系统，其中A是有限的非空集合，*是A上的二元运算，若（A，*）为半群，则（A，*）中必存在：
A、等幂元； B、幺元； C、逆元； D、零元。
3、已知（N11，*）中的*为模11加法运算，则（N11，*）是：
A、半群； B、独异点； C、群； D、不能确定。
4、设A，B是集合，如果A={}，B={，a，{}}，则：
A、AB且AB B、AB但AB C、AB但AB D、AB且AB
5、设R是A={a，b，c}上的二元关系，R={（a,a）,（a,b）,（a,c）,（c,a）}，则R是：
A、对称的； B、反对称的； C、可传递的； D、前面三种都不是。
6、若A={2，3，4，5，6，8，10，12，24}，R是A上的整除关系，则R是集合A上的：
A、相容关系； B、等价关系； C、偏序关系； D、不确定。
7、下列二元关系中，哪个能构成函数？
A、集合A={1，2，3}，B={4，5，6}，当aA，bB，且a C、集合A={2，3，5}，B={0，1}，对于aA，当a为素数时，（a，0）f。 D、设A={x，y}，B={1，2}，f是A到B的二元关系，并且f={（x，1），（x，2）}。 8、若T是一棵有10个顶点的无向树，那么它有多少个不同的定向图？ A、20； B、29； C、210； D、215。 9、完全二元树的顶点有： A、偶数个； B、奇数个； C、2个； D、不确定。 10、设P：我很累，Q：我去打篮球，R：我去看电影。则“如果我不累，我就去打篮球；但我很累，所以我去看电影。”可符号化为： A、（┒PQ）∨（PR）； B、（┒PQ）∧（PR）； C、（┒P∨Q）∨（PR）； D、（┒P∧Q）∨（PR）； 二、填空题（共20分，每小题2分） 1、电视台对200人进行调查的结果是：有95人喜欢电视剧甲，有128人喜欢电视剧乙，有82人喜欢电视剧丙；有61人既喜欢电视剧甲又喜欢电视剧乙，有51人既喜欢电视剧甲又喜欢电视剧丙，有40人既喜欢电视剧乙又喜欢电视剧丙；有30人对这3部电视剧都喜欢。那么对这3部电视剧都不喜欢的人数有（ ）人？ 2、设A={1，2，3，4，5，6，7，8，9，10，16，24}，B={2，4，6}，R是A上的整除关系，则集合B的下确界为（ ）。 3、设A、B是两个集合，且|A|=3，|B|=5，则A到B可以定义多少种（ ）不同的单射函数？ 4、设无向树T中有100个2度点，5个3度点，2个4度点和7个5度点，则T有（ ）片树叶？ 5、树叶权为4，2，3，5，1的霍夫曼最优树的权为（ ）。 6、设T为完全2元树，且T有t片叶子，则T共有（ ）条边。 7、设G为n阶完全图（Kn），则当n取（ ）时，G为偶拉图？ 8、设G是自对偶图，且有n个顶点，m条边，则 m=（ ）。 9、命题公式 (┓P∨┓Q)→（┓P∧R）的主合取范式为（ )。 10、在群（N13-{0}， 13）中，元素11的阶数为（ ）。 三、证明题（共40分，每小题10分） 1、如果R是有限集合A上的反自反关系和可传递关系，证明R是A上的反对称关系。 2、证明：顶点数大于等于2的无向树，至少有两片树叶。 3、证明：在简单平面图中，必有一个顶点的度数小于等于5。 4、证明（x）(A（x）→B（x）) ∧（x）A（x）（x）B（x）。 四、应用题（共20分，每小题10分） 1、设A是集合，且|A|=4，问： （1）在A上可以定义多少种不同的等价关系？ （2）在A上可以定义多少种不同的相容关系？ 2、某城市拟在六个区之间架设有线电视网，其网点间距离如下面有权图矩阵给出（如a32=4，表示a3到a2有一条长为4的电视线）。试给出架设线路的最优方案，请画出图，并计算出线路的长度。 五、综合题（共10分） 问有6个顶点的不同构的无向树有几种？试画出这些无向树。下载本文
