离散数学测试.doc

离散数学测试卷 使用专业、班级 学号 姓名 l 题 数 一 二 三 四 五 六 七 总 分 得 分 一、填空题每小题 2 分，共计 20分 1、集合 A=,的幂集P(A)=。2、设 A=1，2，3，4，A上二元关系 R=，画出 R 的关系图 。3、设 A=,B=,则BA=。BA=。4、设|A|=3，则 A 上有 个二元关系。5、A=1，2，3上关系 R=时，R 既是对称的又是反对称的。6、偏序集RA,的哈斯图为，则R=。江 南 大 学 考 1 考试形式开卷（）、闭卷（），在选项上打（）开课教研室 命题教师 命题时间 使用学期 s 7、0|xZxxZ，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是 ，零元是 。8设,cbaX，X 上的关系 R 的关系矩阵是111011101RM，则 RRM 9 某人有三个儿子，组成集合 A=S1,S2,S3，在 A上的兄弟关系 具有 性质。10 已知一棵无向树 T 有三个 3 顶点,一个 2 度顶点,其余的都是 1 度顶点,则 T 中有 个 1 度顶点。试 卷 专 用 纸 总张数 教研室主任审核签字 江 南 大 学 考 二、选择题20 分 1集合 A=1，2，3，4上的偏序关系图为 则它的哈斯图为（）。2、N是自然数集，定义3mod )()(,:xxfNNf（即 x 除以 3的余数），则 f是（）。2 A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。3 下列语句不是命题的有（）。A、x=13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；D、太阳系以外的星球上有生物；E、你打算考硕士研究生吗？4 下图中是哈密顿图的为（）。5 设4,41,3,31,2,21,1s，*为普通乘法，则S，*是（）。A、代数系统；B、半群；C、群；D、都不是。6 对图 G 则)(),(),(GGGk分别为（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。7 一棵无向树 T有 8 个顶点，4度、3度、2度的分枝点各 1个，其余顶点均为树叶，则 T中有（）片树叶。A、3；B、4；C、5；D、6 8设 A=1，2，3，4，S=1，2，3，4，为 A的一个分划，求由 S 导出的等价关系。（4分）试 卷 专 用 纸 江 南 大 学 考 9设 A=1，2，10，则下面定义的运算*关于 A封闭的有（）。A、x*y=max(x,y)；B、x*y=质数 p的个数使得ypx；C、x*y=gcd(x,y)；(gcd(x,y)表示 x 和 y的最大公约数)；D、x*y=lcm(x,y)（lcm(x,y)表示 x 和 y的最小公倍数）。10在（）下有ABA。A、BA；B、AB；C、BA；D、BA或 三、计算解答题40 分 3 1、设 G的邻接矩阵为 A=011110100求 G 的可达阵。（10 分）2、在二叉树中 1）求带权为 2，3，5，7，8 的最优二叉树 T。（5分）2）求 T对应的二元前缀码。（5 分）3 下图所示带权图中最优投递路线并求出投递路线长度（邮局在 D点）。（10 分）4设 A=1，2，3，4，5，A上的偏序关系为 求 A的子集3，4，5和1，2，3，的上界，下界，上确界和下确界。（10 分）试 卷 专 用 纸 江 南 大 学 考 四、证明题15分 1.(7分)设 R 是上的二元关系，则 R 反对称 iff R RcIx。4 2.(5分)证明循环群的同态像必是循环群。3.证明如果 f是由到的同态映射，g是由到的同态映射，则fg 是由到的同态映射。（8分）试 卷 专 用 纸