《计算学院 第_二_学期《离散数学》(下)试卷(A卷)及参考答案A》由会员分享，可在线阅读，更多相关《计算学院 第_二_学期《离散数学》(下)试卷(A卷)及参考答案A（6页珍藏版）》请在金锄头文库上搜索。
1、 离散数学 试卷 第 1 页 共 4 页离散数学（下） 考试试卷（A 卷）（时间 120 分钟）院/系 专业 姓名 学号 题 号 一 二 三 四 五 六 七 总分得 分一、单项选择题（每小题 2 分，共 20 分）1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）A.自然数集合； B.整数集合； C.有理数集合； D.实数集合。2. 设 为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）IA. ； B. ； C. ； D. 。2|kI21|kI35|,mnI3. 设 ， 为模 加法，则下列元素是 的生成元的是（ ）60,15N 66,NA.2； B.3； C.4； D.5。4
2、. 设 是整环，则 不一定是（ ）,F,FA.可交换环； B.无零因子环； C.含么环； D.域。5. 格不一定具有（ ）A.交换律； B.结合律； C.分配律； D.吸收律。6. 设 ， 和 分别表示求最小公倍数和最大公约数运算，则 是（ ）1,248S ,SA.有补格； B.分配格； C.有补分配格； D.布尔代数。7. 一个含 个结点的无向图中有 个结点的度数分别为 ，则第 个结点的度数不可能是（ ）31,234A.0； B.1； C.2； D.4。8. 设连通的简单平面图 中有 10条边和 5个面，则 的结点数为（ ）GGA.6； B.7； C.8； D.9。9. 设无向树 中有 个结
3、点度数为 ， 个结点度数为 ， 个结点度数为 ，则 中的树叶数为（ T1234T）A.10； B.11； C.12； D.13。10.设 为连通的无向图，若 仅有 个结点的度数是奇数，则 一定具有（ ）GGGA、 欧 拉 路径； B、 欧 拉 回 路 ； C 、 哈密尔顿路径； D、 哈密尔顿回路。得分 离散数学 试卷 第 2 页 共 4 页二、填空题（每小空 2 分，共 20 分）1. 设 为实数集合， ，则在代数 中，R|01SxRx,maxS关于 运算的么元是 ，零元是 。Sma2. 设 为模 加法，则在 中，元素 的阶为 ， 的阶为 。1010,9, 563. 设 ， 和 分别为求最大
4、公约数和最小公倍数运算，,25,1gcdl则在布尔代数 中，原子的个数为 ，元素 的补元为 。0gcdlS 24. 在格 中， ， 当且仅当 当且仅当 。,L,abLabab5. 一个具有 个结点的简单连通无向图的边数至少为 ，至多为 。n三、解答题（第 1 小题 12 分，第 2 小题 8 分，共 20 分）1. 设图 如图 1所示，G(1) 求 的邻接矩阵 ；A(2) 求 ，说明从 到 的长为 的路径各有几条；(2)3(4),1v42,3(3) 求 的可达矩阵 ； P(4) 求 的强连通分图。G图 1得分得分 离散数学 试卷 第 3 页 共 4 页2. 求群 的所有子群及由元素 确定的各子
5、群的左陪集，其中 ， 是模 加法。8,N580,17N8四、证明题（每小题 10 分，共 40 分）1. 证明布尔恒等式： 。()()(abcbac2. 设 为实数集合， 和 为数的加法和乘法运算，对 ， ，R,abRba*证明： 为独异点。, 得分 离散数学 试卷 第 4 页 共 4 页3. 证明：若 简单无向图 满足 ，则图 是连通图。),(mnG)2(1nmG4. 设 是一个群， ；定义一个映射 ，使得对于 有 ；,GaG:fGxG1()fax证明： 是 的群自同构。f, 离散数学 试卷 第 5 页 共 4 页 离散数学 试卷 第 1 页 共 2 页安徽大学 20 07 20 08 学年
6、第 2 学期离散数学（下） （A 卷）考试试题参考答案及评分标准一、单项选择题（每小题 2 分，共 20 分）1.A； 2.C； 3.D； 4.D； 5.C； 6.B； 7.B； 8.B； 9.A； 10.A。二、填空题（每小空 2 分，共 20 分）1. ， ； 2. ， ； 3. ， ； 4. ， ； 5. ， 。03abn()/2三、解答题（第 1 小题 12 分，第 2 小题 8 分，共 20 分）1. (1) 的邻接矩阵 ； 2 分G01A(2) ； ； ； 5(2)01(3)02(4)02A分从 到 的长为 的路径的条数分别为 ； 81v42,31,2分(3) 的可达矩阵为 ； 1
7、0 分G01P(4) 因 ，故 的强连通分图的结点集为 ， 。 1201TG1v234,v分2. 的子群为： ， ， ， ； 4 分8,N80,80,246,80,48,N元素 确定的各子群的左陪集对应为： ， ， ， 。 855375分 离散数学 试卷 第 2 页 共 2 页四、证明题（每小题 10 分，共 40 分）1. 2分()()()abcbabc6分a。 101()()c分2. 因 对 和 运算封闭，故 对 运算封闭；对 ， 2 分RR,xyzR,xyzzxyyxzyxzyx )(*)(*)( z故 ，从而 上的 运算满足结合律； 6()()分因对 ， ， ，故 为 运算的么元； x
8、Rx0*0 x00*综合以上， 为 上的可结合的二元运算，且 关于 运算有么元，所以 为独异点。 10R,R分3. 假设 有 个连通分图，则因 为简单无向图，故 ， 4G(2)kG12()1)mnk分因为 ，所以 ， ， 8 分02nk01nk所以 ，这与 矛盾！112()()m12()所以图 是连通图。 10分4. 对 ，若 ，则 ，故 ，从而 为单射； 3 分12,xG12()fxf112axxa2xf， 且 ，因此 ，使 ，所以 为满射； 6yay1)yG()fy分， ，故 为同态； 9,x111()()()fxxaxayfxf分所以 是 的群自同构。 10f,G分 离散数学 试卷 第 3 页 共 2 页
