《离散数学》课程教学资源（试卷习题）试卷（题目）13

离散数学试卷（十三） 一、 填空10%（每小题2分） 1、Z*={x|x∈Z入x>0;,*表示求两数的最小公倍数的运算(Z表示整数集合)，对于*运算 的么元是 ,零元是 2、代数系统中，Al,如果e和0分别为的么元和零元 则e和8的关系为」 3、设G,>是一个群，是阿贝尔群的充要条件是 4 9/ /ea 4图 的完全关联矩阵为 5、一个图是平面图的充要条件是 二、 选择10%（每小题2分） 1、下面各集合都是N的子集，( )集合在普通加法运算下是封闭的。 A、xx的幂可以被I6整除：B、xX与5互质： C、{x1x是30的因子： D、x1x是30的倍数；。 2、设G1=,G2=,其中。表示模3加法，*表示模2乘法，则积代 数G×G,的么元是( A、:B、:C、:D、。 3、设集合S={1,2,3,6},“≤”为整除关系，则代数系统是( )。 A、域：B、格，但不是布尔代数：C、布尔代数：D、不是代数系统。 4、设n阶图G有m条边，每个结点度数不是k就是k+1,若G中有N个k度结点， 则N=( A、n·k:B、nk+1):C、nk+1)-m:D、nk+1-2m。 5、一棵树有7片树叶，3个3度结点，其余全是4度结点， 则该树有( )个4度结点。 82

离散数学试卷（十三） 82 一、 填空 10% （每小题 2 分） 1、 = { |    0} + Z x x Z x ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算 的幺元是 ，零元是 。 2、代数系统中，|A|>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 是 30 的倍数}。 2、 设 G1 ={0,1,2}, ，G2 ={0,1},*  ，其中  表示模 3 加法，*表示模 2 乘法，则积代 数 G1 G2 的幺元是（ ）。 A、； B、； C、； D、 。 3、 设集合 S={1,2,3,6}，“≤”为整除关系，则代数系统是（ ）。 A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统。 4、 设 n 阶图 G 有 m 条边，每个结点度数不是 k 就是 k+1，若 G 中有 Nk 个 k 度结点， 则 Nk=（ ）。 A、n·k； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。 5、 一棵树有 7 片树叶，3 个 3 度结点，其余全是 4 度结点， 则该树有（ ）个 4 度结点

离散数学试卷（十三） A、1:B、2:C、3:D、4。 三、判断10%（每小题2分） 1、()设S={1,2},则S在普通加法和乘法运算下都不封闭。 2、（)在布尔格中，对A中任意原子a,和另一非零元b,在a≤b或a≤b中有且 仅有一个成立。 3、( )设S={x|x∈ZAx≥0}=N,+,·为普通加法和乘法，则是域。 4、( )一条回路和任何一棵生成树至少有一条公共边。 5、( )没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i=t1。 四、证明38% 1、(8分)对代数系统,·是A上二元运算，e为A中么元，如果·是可结合的且每个元素 都有右逆元，则(1)中的每个元素在右逆元必定也是左逆元。 (2)每个元素的逆元是唯一的。 2、(12分)设是一个布尔代数，如果在A上定义二元运算☆，为 a☆b=(aAb)v(aAb),则是一阿贝尔群。 3、(10分)证明任一环的同态象也是一环。 4、(8分)若G=(=v,回=)是每一个面至少由kk≥3)条边围成的连通平面 图，则es-2 k-2 五、应用32% 1、(8分)某年级共有9门选修课程，期末考 试前必须提前将这9门课程考完，每人每天 只在下午考一门课，若以课程表示结点，有 一人同时选两门课程，则这两点间有边（其 图如右)，问至少需几天？

离散数学试卷（十三） 83 A、1； B、2； C、3； D、4 。 三、判断 10% （每小题 2 分） 1、（ ）设 S={1,2}，则 S 在普通加法和乘法运算下都不封闭。 2、（ ）在布尔格中，对 A 中任意原子 a，和另一非零元 b，在 a  b 或 a  b 中有且 仅有一个成立。 3、（ ）设 S = {x | x  Z  x  0} = N ，+,·为普通加法和乘法，则是域。 4、（ ）一条回路和任何一棵生成树至少有一条公共边。 5、（ ）没 T 是一棵 m 叉树，它有 t 片树叶，i 个分枝点，则(m-1)i = t-1。 四、证明 38% 1、（8 分）对代数系统，*是 A 上二元运算，e 为 A 中幺元，如果*是可结合的且每个元素 都有右逆元，则（1）中的每个元素在右逆元必定也是左逆元。 （2）每个元素的逆元是唯一的。 2 、（ 12 分）设  A , , ,−  是 一 个布 尔代 数 ，如 果 在 A 上 定义 二 元运 算 ☆， 为 a☆b = (a  b)  (a  b) ，则是一阿贝尔群。 3、（10 分）证明任一环的同态象也是一环。 4、（8 分）若 G =V,E  (V = v , E = e) 是每一个面至少由 k(k≥3)条边围成的连通平面 图，则 2 ( 2) − −  k k v e 。 五、应用 32% 1、 （8 分）某年级共有 9 门选修课程，期末考 试前必须提前将这 9 门课程考完，每人每天 只在下午考一门课，若以课程表示结点，有 一人同时选两门课程，则这两点间有边（其 图如右），问至少需几天？

离散数学试卷（十三） 2、用washall方法求图 的可达矩阵，并判断图的连通性。(8分) 3、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a:英，b:汉、英，c:英、 西班牙、俄，d:日、汉，e:德、西班牙，f:法、日、俄，g:法、德，能否将这七个人的 座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？(8分) 4、用Huffman算法求出带权为2,3,5,7,8,9的最优二叉树T,并求W(T)。 若传递a,b,c,d，e,f的频率分别为2%，3%，5%，7%，8%，9%求传输它 的最佳前缀码。(8分) 84

离散数学试卷（十三） 84 2、 用 washall 方法求图 的可达矩阵，并判断图的连通性。（8 分） 3、 设有 a、b、c、d、e、f、g 七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、 西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的 座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8 分） 4、 用 Huffman 算法求出带权为 2，3，5，7，8，9 的最优二叉树 T，并求 W（T）。 若传递 a ，b， c， d ，e， f 的频率分别为 2%， 3% ，5 %， 7% ，8% ，9%求传输它 的最佳前缀码。（8 分）