离散数学题库简答题45526.pdf

《离散数学题库简答题45526.pdf》由会员分享，可在线阅读，更多相关《离散数学题库简答题45526.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、v1.0 可编辑可修改 1 编号 题目 答案 题型 分值 大纲 难度 1 1 设集合 A=a，b，c，d上的关系R=,用矩阵运算求出 R 的传递闭包 t(R)。答:0000100001010010RM ，00000000101001012RRRMMM 000000000101101023RRRMMM000000001010010134RRRMMM0000100011111111432)(RRRRRtMMMMM t(R)=,简答题 8 3 2 如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造答:用 Kruskal 算法求产生的最优树。算法略。结果如图：简答题

2、8 3 v1.0 可编辑可修改 2 价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。树权 C(T)=23+1+4+9+3+17=57 即为总造价。3 设是一个群，这里+6是模 6加法，Z6=0，1，2，3，4，5，试求出的所有子群。答:子群有；简答题 8 3 4 权数 1，4，9，16，25，36，49，64，81，100 构造一棵最优二叉树。答:简答题 8 3 v1.0 可编辑可修改 3 5 集合 X=,，R=,|x1+y2=x2+y1。1）说明R是X上的等价关系。（6分）2）求出 X 关于 R 的商集。（2 分）答:1）、1、自反性：yxyxXyx由于,自反RRyxyx,2、

3、对称性：XyxXyx2211,时当Ryxyx2211,21121221yxyxyxyx也即即 有对称性故RRyxyx1122,3、传递性：XyxXyxXyx332211,时且当RyxyxRyxyx33222211,简答题 8 3 v1.0 可编辑可修改 4)2()1(23321221yxyxyxyx即 23123221)2()1(yxyxyxyx 即1331yxyx 有传递性故RRyxyx3311,由（1）（2）（3）知：R 是 X 上的先等价关系。2）、X/R=2,1R 6 设集合 A=a,b,c,d 上关系 R=,要求 1）、写出 R 的关系矩阵和关系图。（4 分）2）、用矩阵运算求出 R

4、 的传递闭包。（4 分）答:1、0000100001010010RM；关系图 2、00000000101001012RRRMMM 简答题 8;4 v1.0 可编辑可修改 5 000000000101101023RRRMMM 2340000000010100101RRRRMMMM,4635RRRRMMMM 0000100011111111432)(RRRRRtMMMMM t(R)=,。7 利 用 主 析 取 范 式，判 断 公 式RQQP)(的类型。答:FRQQPRQQPRQQPRQQP)()()()()(它无成真赋值，所以为矛盾式。简答题 8 3 8 在二叉树中:1)求带权为 2，3，5，7，

5、8 的最优二叉树 T。（4 分）2)求 T 对应的二元前缀码。（4 分）答:（1）由 Huffman 方法,得最佳二叉树为：简答题 8 3 v1.0 可编辑可修改 6 （2）最佳前缀码为：000，001，01，10，11 9 下图所示带权图中最优投递路线并求出投递路线长度（邮局在 D点）。答:图中奇数点为 E、F，d(E)=3,d(F)=3,d(E,F)=28 p=EGF复制道路 EG、GF，得图 G，则 G是欧拉图。由 D 开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。简答题 8 5 10 设 S

6、=1,2,3,4,6,8,12,24，“”为 S 上整除关系，问：（1）偏序集,S的 Hass图如何（2）偏序集,S的极小元、最小元、极大元、最大元是答:(1)=,，,SI covS=,Hass 图为 简答题 8 4 v1.0 可编辑可修改 7 什么 （2）极小元、最小元是 1，极大元、最大元是 24。11 设解释 R 如下：DR是实数集，DR中特定元素 a=0，DR中特定函数yxyxf),(，特 定 谓 词yxyxF:),(，问公式),(),(),(zyfzxfFyxFzyxA的涵义如何真值如何 答:公式 A 涵义为：对任意的实数 x,y,z，如果 xy 则 (x-z)(y-z)A 的真值为

7、：真（T）。简答题 8 3 12 给定 3 个命题：P：北京比天津人口多；Q：2 大于 1；R：15 是素数。求复合命题：答:P，Q 是真命题，R 是假命题。010)11()01()()(RPRQ 简答题 8 3 v1.0 可编辑可修改 8)()(RPRQ的真值。13 给定解释 I：D=2，3，L（x,y）为 L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求谓词合式公式),(yxxLy的真值。答:000)10()01()3,3()3,2()2,3()2,2(),3(),2(),(LLLLyLyLyyxxLy 简答题 8;3 14 将)()(),(xRzzQyxyPxwff化

8、为与其等价的前束范式。答:)()(),()()(),()()(),()()(),(xRzQyxPzyxxRzQzyxPyxxRzzQyxPyxxRzzQyxPyx 简答题 8 3 15 简述关系的性质有哪些 自反性，对称性，传递性，反自反性，反对称性 简答题 8 1 16 假设英文字母，a，e，h，n，p，r，w，y 出现的频率分别为 12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出 happy new year 的编码信息。答:解：传输它们的最佳前缀码如上图所示，happy new year 的编码信息为：10 011 0101 0101 001 110

9、 111 0100 001 111 011 000 简答题 8 3 v1.0 可编辑可修改 9 附：最优二叉树求解过程如下：17 用 washall方法求图的可达矩阵，并判断图的连通性。答:0010100001011100)(GA i 1：A2，1=1，0010100011011100A；i2：A4，2=1，1111100011011100A i3：A1，3=A2，3=A4，3=1，1111100011011100A 简答题 8 3 v1.0 可编辑可修改 10 i4：Ak，4=1，k=1，2，3，4，1111111111111111A p 中的各元素全为 1，所以 G 是强连通图，当然是单向

10、连通和弱连通。18 设有 a、b、c、d、e、f、g 七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈 答:用 a,b,c,d,e,f,g 7 个结点表示 7 个人，若两人能交谈可用一条无向边连结，所得无向图为 此图中的 Hamilton 回路即是圆桌安排座位的顺序。Hamilton 回路为 a b d f g e c a。简答题 8 3 19 用 Huffman 算法求出带权为 2，3，5，7，8，9 的最优二叉树 T，并求 W（T）。若传递 a，b

11、，c，d，e，f 的频率分别为2%，3%，5%，7%，8%，9%求传输它的最佳前缀码。（答:简答题 8 3 v1.0 可编辑可修改 11 83282729354342)(TW（1）用 0000 传输 a、0001 传输 b、001 传输 c、01 传输 f、10 传输 d、11 传输 e 传输它们的最优前缀码为0000，0001，001，01，10，11。20 构造一个结点 v 与边数 e 奇偶性相反的欧拉图。答:简答题 8 5 21 设 A=1，2，3，4，S=1，2，3，4，为 A 的一个分划，求答:R=,简答8 3 v1.0 可编辑可修改 12 由 S 导出的等价关系。题 22 设,54

12、321xxxxxA，偏序集RA,的 Hass 图为 求 A 中最小元与最大元；,543xxx的上界和上确界，下界和下确界。答:A 中最大元为1x，最小元不存在；,543xxx上界31,xx，上确界1x；下界无，下确界无。简答题 8 3 23 用 Warshall 算法，对集合 A=1，2，3，4，5 上 二 元 关 系R=,求 t（R）。答:0000000010100000100000011RM i 1 时，RM1,1=1,A=RM i2 时，M1,2=M4,2=1 简答题 8;4 v1.0 可编辑可修改 13 A=0000001010100000100001011 i3 时，A 的第三列全为

13、 0，故 A 不变 i4 时，M1,4=M2,4=M4,4=1 A=0000001010100000101001011 i5 时，M3,5=1，这时 A=0000001010100000101001011 所以 t(R)=,。v1.0 可编辑可修改 14 24 将谓词公式)()()()()()(yRyyQyxPx 化为前束析取范式与前束合取范式。答:前束合取范式前束析取范式)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(zRyQzRxPzyxzRyQxPzyxzRzyQyxPxyRyyQyx

14、PxyRyyQyxPxyRyyyQxxPyRyyyQxPx 简答题 8;3 25 )、画一个有一条欧拉回路和一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。答:简答题 8 3 26 求)()(QPPQ的主合取范式。答:)()()()()()()()()()(QPQPQPQPFQPPQPQQPPQQPPQ 简答题 8 3 27 在下面关系中:答:R 自反 简 8 4 v1.0 可编辑可修改 15 0202,yxyxyxR判定关系的性质。任意实数 x，x-x+20 ，x-x-20,所以直线 y=x 上的点在区域内，即

15、R,故R 自反；R 对称 若Ryx,有 0202yxyx 得 0)2(20)2(2yxxyyxxy 即 Rxy,所以 R 对称；因 R 自反且结点集非空，故 R 非反自反；因 R 对称且结点集非空，并非全是孤立点，故 R 不是反对称；由0202yxyx 得 22xyx 所以R41,1 而 R1,1 所以 R4不是传递的。答题 28 求图的邻接矩阵和可达矩阵。答:0000000100000010110100000)(GA ，0000000001000000010100000)(2GA，简答题 8 3 v1.0 可编辑可修改 16 0000000000000000000100000)(3GA，55

16、4)(OGA。所以可达矩阵0000000101000010110100000432AAAAP 29 已知某有向图的邻接矩阵如下：00011011110001004321vvvvA 试求：3v到1v的长度为 4 的有向路径的条数。答:0001101111000100A，01001201101210112A，10112123130112013A，12013513313421234A，由3v到1v长度为 4 的有向路径的条数为 3 条。简答题 8 3 30 已知某树有 2 个 2 度结点、3 个 3度结点、4 个 4 度结点，问有几个叶子点（无其它度数点）。答:设该树有 t 片树叶，总结点数为 tt

17、vd29443322)(总边数为 ttve814321 简答题 8;3 v1.0 可编辑可修改 17 所以，29+t=2(8+t)即 t=13。该树有 13 片树叶。31 设1R和2R是 A 上的任意二元关系，如果1R和2R是自反的，21RR 是否也是自反的，为什么如果1R和2R是对称的，21RR 是对称的吗 答:若21,RR是自反的，则21RR 也是自反的。因为 21,RRAa自反，21,RaaRaa，从而 21,RRaa，即21RR 也是自反的。若21,RR是对称的，但21RR 不一定是对称的。如：A=a,b,c，,1abbaR，,2bccbR，则21,RR是对称的，但,21caRR 不是

18、对称的。简答题 8 4 32 如图给出的赋权图表示六个城市fedcba,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。答:要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造价为：1+2+3+5+7=18。简答题 8;3 v1.0 可编辑可修改 18 33 设 S=R-1（R 为实数集），abbaba。说明,S是否构成群；答:1）SabbabaSba易证,，即运算*是封闭的。2）Scba,)()()(abcbcacabcbacabb

19、acabbacabbacba 而,)()()()(abcacabbccbabccbabccbabccbacba)()(cbacba，即*可结合。3）设 S 关于*有幺元 e，则aeaaeSa,。而 0,eaeaeaaeea。4）Sa 设有逆元1a。则eaaaa11，简答题 8 5 v1.0 可编辑可修改 19 即 011aaaa，aaa11，即 S 中任意元都有逆元，综上得出，,S构成群。34 将公式)()(RPRQP）划 为只含有联结词，的等价公式。答:原式)()()()(RPRQPRPRQP )()(RPRQP。简答题 8;3 35 设,H和,K都 是 群,G的子群，问,KH和,KH是否是

20、,G的子群并说明理由。答:,KH 是,G的子群，,KH不一定是,G的子群。,KHKbaHbaKHba和由则都 是,G的子群，,1,11GKHKHbaKbaHba是且 的子群。如：G=1，5，7，11，：模 12 乘，则,G为群。且 H=1，5，K=1，7，,KH和皆 为,G的 子 群，但7,5,1 KH，,KH不是,G的子群。因为 KH 1175，即运算不封闭。简答题 8 5 36 设9432，A，12,10742，B，从 A 到B 的关系 答:12,4,4,4,12,3,12,2,10,2,4,2,2,2R则 R的关系图为：简答题 8;4 A 2 3 4 9 B 2 4 7 10 12 v1

21、.0 可编辑可修改 20,baBbAabaR整除且，试给出 R 的关系图和关系矩阵，并说明此关系是否为函数为什么 R 的关系矩阵为 00000100101000011011RM 关系 R 不是 A 到 B 的函数，因为 元素 2，4 的象不唯一（或元素 9 无象）。37 设,S是半群，LO是左零元，对任LOxSx,是否是左零元为什么 答:LOx仍是左零元。因为Sy，由于LO是左零元，所以，LLOyO，又 ,S为半群，所以*可结合。所以，LLLOxyOxyOx)()(，所以，LOx仍是左零元。简答题 8 3 38 某次会议有 20 人参加，其中每人至少有 10 个朋友，这 20 人拟围一桌入席，

22、用图论知识说明是否可能每人邻做的都是朋友（理由）答:可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图 EVG,，20 人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，10)deg(,10)deg(,vuVvu，20)deg()deg(vu，由判定定理，G 中存在一条汉密尔顿回路。即所谈情况可能。简答题 8 3 v1.0 可编辑可修改 21 39 通过主合取范式，求出使公式RQP)(的值为 F 的真值指派。答:010110100)()()()()()()()(MMMRQPRQPRQPRQPRQRPRQPRQP原式 使公式RQP)(的值为 F 的

23、真值指派为：0:0:1:RQP ；0:1:1:RQP ；0:1:0:RQP。简答题 8;3 40 设,cbaA，A 上的关系,bccbbaaa，求出)()(,)(tsr和。答:,)(ccbbbccbbaaar，,)(abbccbbaaas，,2ccbbcabaaa，,23bccbbacabaaa，,)(2bccbccbbcabaaat。简答题 8;3 41 已知654321，G，7为 模7乘 法。试 说 明7，G是否构成群是否为循环群若是，生成元是什么 答:7，G既构成群，又构成循环群，其生成元为 3，5。因为：7的运算表为：简答题 8;5 v1.0 可编辑可修改 22 1）由运算表知，7封闭

24、；2）7可结合（可自证明）3）1 为幺元；4）111，421，531，241，351，661，综上所述，7，G构成群。由331，232，633，434，535，136。所以，3 为其生成元，3 的逆元 5 也为其生成元。故7，G为循环群。42 用等值演算法求下面公式的主析取范式，并求其成真赋值。答:原式 简答题 8;3 v1.0 可编辑可修改 23 RQP)(011001101111000001)()()()()()()()(mmmmmmRQPRQPRQPRQPRQPRQPRQPRQP 使其成真赋值为：100RQP，000RQP，111RQP，101RQP，100RQP，110RQP 43 集

25、合4,3,2,1A上的关系4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1R，写出关系矩阵RM，画出关系图并讨论 R 的性质。答:1100110100100101RM R 的关系图为 R 是自反、对称的。简答题 8;3 44 一棵树 T 中，有 3 个 2 度结点，一个 3 度结点，其余结点都是树叶。（1）T 中有几个结点；（2）画出具有上述度数的所有非同构的无向图。答:（1）设该树树叶数为 t，则树 T 的结点数为t13，又边数=结点数 1，倍边数2)deg(iv，)113(213123tt 即tt269，3t，T 中 7 个结点。（2）具有 3 个两度结点，一个 3 度结点，

26、3 片树叶的树（非同构的）共有以下三种：简答题 8;3 v1.0 可编辑可修改 24 45 设 A=1,2,10。下列哪个是 A的划分若是划分，则它们诱导的等价关系是什么（1）B=1,3,6,2,8,10,4,5,7;（2）C=1,5,7,2,4,8,9,3,5,6,10;（3）D=1,2,7,3,5,10,4,6,8,9 答:（1）和（2）都不是 A 的划分。（3）是 A 的划分。其诱导的等价关系是 IA,。简答题 8 3 46 设有向图 G=(V,E)如下图所示，试用邻接矩阵方法求长度为 2 的路 答:M=1100101010110011 M2=2110211121211011 简答题 8

27、 4 v1.0 可编辑可修改 25 的总数和回路总数。Mijji2141418,Miji2146 G 中长度为 2 的路总数为 18，长度为 2 的回路总数为 6。47 设 A=1,2,3,4,5,A 上偏序关系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。答:偏序关系 R 的哈斯图为 (2)B 的最大元：无，最小元：无；极大元：2，5，极小元：1，3 下界：4，下确界 4；上界：无，上确界：无 (2)B 的最大元：无，最小元：无；极大元：2，5，

28、极小元：1，3 下界：4，下确界 4；上界：无，上确界：无 简答题 8 4 48 求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。答:原式(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)简答题 8;3 v1.0 可编辑可修改 26 P(QQ)P(QQ)(PQ)(PQ)命题为真的赋值是 P=1,Q=0 和 P=1,Q=1 49 求 公 式 (x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。答:原式(x1F(x1,y)y1G(x,y1)x2H(x2)(换名)x1y1(F(x1,y)G(x,y1)x2H(x2)x1y1(F(x1,y1)G(x,y1)x2H(x2)x1y1x2(F(x1,y1)G(x,y1)H(x2)简答题 8 3 50 设 A=a,b,c，P（A）是 A 的幂集，是集合对称差运算。已知是群。在群中，找出其幺元。找出任一元素的逆元。求元素 x 使满足ax=b。答:e=;任一元素 x 的逆元 x-1;x=a-1b=ab=a,b。简答题 8;3