《2013级工程硕士《离散数学》试卷》由会员分享，可在线阅读，更多相关《2013级工程硕士《离散数学》试卷（3页珍藏版）》请在金锄头文库上搜索。
1、1工程硕士离散数学 试卷一、填空题（共 10 分，每小题 2 分）(1) ，*表示求两数的最小公倍数的运算（ Z 表示整数集合） ，对于0|xZ*运算的幺元是 ，零元是 。(2)代数系统中，|B|1 ，如果 分别为的幺元和零元，和e则 的关系为 。和e(3)设 是一个群，是阿贝尔群的充要条件是 。(4) 图的完全关联矩阵为 。(5)一个图是平面图的充要条件是 。二、选择题（共 10 分，每小题 2 分）(1)下面各集合都是 N 的子集， （ ）集合在普通加法运算下是封闭的。A、x | x 可以被 16 整除； B、x | x 与 5 互质；C、x | x 是 30 的因子； D、x | x 是
2、 30 的倍数。(2)设 ， ，其中 表示模 3 加法，*表示模 2 乘法，则积,210G,*102G代数 的幺元是（ ） 。1A、； B、； C、； D、 。(3)设集合 S=1,2,3,6， “”为整除关系，则代数系统是（ ） 。A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统。(4)设 n 阶图 G 有 m 条边，每个结点度数不是 k 就是 k+1，若 G 中有 Nk 个 k 度结点，2则 Nk=（ ） 。A、nk； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。(5)一棵树有 7 片树叶，3 个 3 度结点，其余全是 4 度结点，则该树有 (
3、 )个 4 度结点。A、1； B、2； C、3； D、4 。三、判断题（共 10 分，每小题 2 分）(1)（ ）设 ，+,为普通加法和乘法，则 是NxZS0|域。(2)（ ）在布尔格 中，对 G 中任意原子 a，和另一非零元 b，在 或a中有且仅有一个成立。ba(3)（ ）没 T 是一棵 m 叉树，它有 t 片树叶，i 个分枝点，则 (m-1)i = t-1。(4)（ ）设 A=1, 2，则 A 在普通加法和乘法运算下都不封闭。(4)（ ）一条回路和任何一棵生成树至少有一条公共边。四、证明题（共 34 分）(1)（10 分）对代数系统 ，*是 A 上二元运算，e 为 A 中幺元，如果*是可结
4、合的且每个元素都有右逆元，则 1）中的每个元素在右逆元必定也是左逆元。2）每个元素的逆元是唯一的。(2)（12 分）设论域 D=a , b , c，求证： 。)()()( xBxBx(3)（12 分）设 R 是 A 上一个二元关系，试证),(),(|, RbccaAcaS 且有对 于 某 一 个明若 R 是 A 上一个等价关系，则 S 也是 A 上的一个等价关系。五、应用题（共 36 分）（1）某年级共有 9 门选修课程，期末考试前必须提前将这 9 门课程考完，每人每天只在下午3考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右） ，问至少需几天？（9 分）（2）用 washall 方法求图 的可达矩阵，并判断图的连通性。 （9 分）（3）符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草” 。并推证其结论。 （9 分）（4）用 Huffman 算法求出带权为 2，3，5，7，8，9 的最优二叉树 T，并求 W（T） 。若传递 a ，b， c， d ，e， f 的频率分别为 2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。 （9 分）
