离散数学题库简答题

1、编题分难 答案题目 大纲度号 型 值3 d上的关系简8 1 4.3 1 设集合A=a，b，c，: 答答 R=a , b , , , 10010010? 的用矩阵运算求出R题?01110100? 传递闭包t (R)。?MM?MM? ， ?RRR2R10000000 ? 00000000?10010101?10010101?M?M?MM?M?M?RR3234RRRR00000000?00000000?1111?1111?M?M?M?M?M ?R)t(R432RRR1000?0000?t (R)= , , , , , , , , 2 简8 7.2 3 用答: 如下图所示的赋权图表示某七个Kruska

2、l算法求产生的最优树。算法略。结果如图：答 vv,v,?及预先算出它城市 题721们之间的一些直接通信线路造价，试给出一个设计方案，使得 各城市之间能够通信而且总造价最小。 树权C(T)=23+1+4+9+3+17=57即为总造价。 3 答: 子群有； 简8 8.3 3 6是模是一个群，这里+,+设Z66666666答 ，3，2，1=0 加法，Z， 题6的所有4，,+，试求出566 子群。 3 ，权数 4 149答，2536498 简: 7.2 ，16，答，64 构造一棵最优二叉树。，81100 题 5 集合X=, , , +y,y|x ，R=,x2 21121x+y 。 12= 1） 说明R

3、是X上的等价关系。（ 6 分） 分）（X关于R的商集。22） 求出 的关系矩阵和关要求 1）、写出R、用矩阵运算求）分） 2系图。（4 分）4出R的传递闭包。（ 分）对应的二元前缀码。（4求T? 是什么 ， d ， c求W（T）。若传递a ，b， %，e， f 的频率分别为2%， 3% ，5 求传输它的最佳前9%7% ，8% ， （缀码。 、: 1答）yx?y?x?x,y?X,由于 自反性：1、?R自反?x,y?R,?x,y? ?x,y?X,?x,y?X 2对称性：、 2112当?x,y?,?x,y?R时即x?y?x?y也即x?y?x?y 212212121112故?x,y?,?x,y?R?R

4、有对称性 1221?x,y?X,?x,y?X?x,y?X 3、 传递性：311232当?x,y?,?x,y?R且?x,y?,?x,y?R时 33122122x?y?x?y(1)?1212即 ?)(y2x?y?x?2332x?y?x?y2(1)?()?x?y?x?y 22121332x?y?x?y 即1331故?x,y?,?x,y?R?R有传递性 3113由（1）（2）（3）知：R是X上的先等价关系。 ?1,2? 、X/R=）2R?M 关系图；1、 ?R1000?0000?1001?1000?0100? 简答题题8 4.4 3 6 上关设集合A= a ,b , c , d R= , , , ?0

5、110? ? 0110?MM?M?、 2?RR2R0000?0000?0101?0110?M?M?M ?R23RR0000?0000?0110?1001?MM?M?M?M,M?M,M? ?R4563342RRRRRRR0000?0000?1111?1111?M?M?M?M?M ?R(tR)432RRR1000?0000? t (R)= , , , , , , , , 。 7 利用主析取范式，判断公式简8 2.3 3 )RQ)?(Q?(P?Q)?Q?R?P?( 答: 答RQ(P?)?Q?F?QR?(Q?R)?P?Q?(P?Q)? 的类型。 题它无成真赋值，所以为矛盾式。 3 简8 7.2 8 ,

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

7、, , , 设S=1 2 3 4, , , : =,答?上整除关系，S”为,问：（1）ScovS=, , S?,的极2）偏序集图如何？（Hass图为 小元、最小元、极大元、最大元 （2）极小元、最小元是1，极大元、最大元是 24。 11 简8 3.2 3 (x-z) (y-z) 则，如果xy 答D是实数集，D: 公式A涵义为：对任意的实数x,y,z设解释R如下：RR答 中特定元素a=0，D中特定函数。 A的真值为： 真（T） 题R f(x,y)?x?y，特定谓词F(x,y):x?y，问公式A?x?y?z(F(x,y)?的涵义)z(y,(x,z),ffF( 如何？真值如何？ 简8 2.2 P：北

8、京比天津人3 个命题： 12 给定3 ，答: PQR是真命题，是假命题。答 是素数。15：R；1大于2：Q口多；求复合命题：题 0?0?1(1?1)?(P?R)?(1?0)?(Q?R) (Q?R)?(P?R)的真值。 13 给定解释I：D=2，3，L（x,y）简8 3.1;3.3 )L(3,3)2?(L(2,3)?yy)?L(3,)?(L(2,2)?L(3,)?y?xL(x,y?y(L(2: 答2 1 , 答) = L ( 3 , 3 ) = 为L( 2 , 2 00?(0?1)?0?(1?0) L ( 2 , 3 ) = L (3 , 2 )=0 ,题)?y?xL(x,y求谓词合式公式 的真

9、值。简8 3.2 3 14 : 答)ywff?(?yP(x,x?(为化将答)(xz)?RzQ?(?()?xR(,y)?(?(?zQ(zPx)?y)(?(?zQ(z?R(x)?(?(?y(?(xx(x?(?y?P(, 题 )x)?R(?x?y?z(Px,y)?Qz(z()(?x(y(Px,y?z?Q()?Rx) 与其等价的前束范式。简8 4.3 自反性，对称性，传递性，反自反性，反对称性 1 15 简述关系的性质有哪些？答 题16 假设英文字母，a，e，h7.2 ，n，p，答:解：传3 输它们的最佳前简8 上码如缀，y出现的频率分别为12%happy 图所示，答，r，wyear，new 题的编码

10、信息为： 10%10%，6%，5%，7%15%8%，求传输它们的最佳前缀码，并给011 10 的编码信息。出happy new year0101 0101 0100 111 110 001 111 011 000 001 附：最优二叉树求解过程如 下：17 用washall方法求图的可达矩阵，简8 6.3 3 1001?答 并判断图的连通性。0110?(AG) : 答 题 01010110? 10110111?AA?i?i? ，2； ： A4，2=1，1：A21=1， ?10000010?11110010?0101?1110?A?i，3=1，3=A2， 3=A43： A1?0100?1111?

11、1111?1111?A?i ，3 Ak4：，4=1，k=1，2，4?1111?1111?p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。 3 gfecb、d、七个简8 6.4 a 18 设有 : 答答他们分别会讲的语言如下：a：人，用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一 题：英、西班牙、：汉、英，英，bc：德、西班牙，e：日、汉，d俄，条无向边连结，所得无向图为 ：法、德，能：法、日、俄，fg此图中的Hamilton回路即是圆桌安排座位的顺序。 否将这七个人的座位安排在圆桌Hamilton旁，使得每个人均能与他旁边的回路为a b d f g e c

12、a。 人交谈？19 用 Huffman算法求出带权为2，3，简8 7.2 3 : 答答，并，8，9的最优二叉树T5，7 W(T)?2?4?3?4?5?3?9?2?7?2?8?2?83 （1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为0000，0001，001，01，10，11 。 20 构造一个结点v与边数e奇偶性简8 6.4 5 答 相反的欧拉图。 题答: 简8 4.4 3 21 设A=1，2，3，4，S=1，2，答: R= , , , , 3，4，为答A的一个分划，求 导出的等价关系。S由 题22 简8 4.4 3 xx,x

13、,x,x,A?x，偏序设 答: A中最大元为，最小元不存在；523141答 题xxx,x,x,x?,R?A 上界，上确界 ；下界无，下确界无。的Hass图为集 345311 求 A中最小元与最大元；x,x,x的上界和上确界，下534界和下确界。 23 简8 4.1;4.4 A=1，:答用Warshall算法，对集合3 答11000?系2，3，4，5上关二元 题?00010?R=,求10000? 00000?MMi? 1,1=1, A =时， 1RRi?2时，M1,2=M4,2=1 11010?00100?10000 A=?10010?00000?)、画一个有一条欧拉回路，但没有一条汉密尔顿回路

14、的图。 )、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。 i?3时，A的第三列全为0，故A不变 i?4时，M1,4=M2,4=M4,4=1 11010?10100?i?100005时，M3,5=1 A= ，这时 ?10010?00000?10110?10010?10000 A=?10100?00000?所以t (R)=, , 。 0011010110?2?G?A)(A(G)0010000000 ， ，?0010001000?24 式词公谓将(?x)P(x)? (?y)Q(y)?(?y)R(y)化为前束析取范式与前束合取范 式。 (?x)(P(x)?(?yQ(y)?(?y)R(y)?(?xP

15、(x)?(?yQ(y)?(?y)R(y)y()(Q(y)?y)R(?)?(?(?xP(x)?(y)R(Qy)?(?y)(y?x)?(?x?P()?(y?)zz)?P?(x)?(x)(?yQ(y?(?)R( 答: ?(?x)(?y)(?z)(?P(x)?Q(y)?R(z)前束析取范式?(?x)(?y)(?z)(?P(x)?R(z)?(?Q(y)?R(z)前束合取范式简答题8 2.1;3.1;3.2 3 25 、画一个有一条欧拉回路和一) 条汉密尔顿回路的图。答: 简答题8 6.4 3 简8 2.3 3 26 (Q?P)?(?P?Q)?(?Q?P)?(?P?Q)Q?P?Q?P)?(合求的主答?(?

16、Q?P?Q)?(P?P?Q)?F 答: 题 取范式。?(P?Q)?(P?Q)?(?P?Q)?(?P?Q)4 27 4.3 简8 R自反答: 在下面关系中: 答?R?故, 所以直线y=x上的点在区域内，即 x-x+20 任意实数x， x-x-20 , 0?y?2?0?x?R?x,y?xy?2 题 R自反；判定关系的性质。 R对称 x?y?2?0y?x?2?(x?y?2)?0?x,y?R?y,x?R 有 若 得 即?x?y?2?0y?x?2?(x?y?2)?0?所以 R对称； 因R自反且结点集非空，故R非反自反； 因R对称且结点集非空，并非全是孤立点，故R不是反对称； x?y?2?0?1?1,?R

17、?1,?1?R?x2?yx?2 而 所以 由得?x?y?2?04?所以R不是传递的。 428 简8 6.3 3 求图的邻接矩阵和可达矩阵。答 :答 题 0000000000? 0000000000?00000?00100?43(G)?AO?G)A(00000。， 55?00000?00000?00000?10011?432?A?AA?AP?10000所以可达矩阵 ?10010?00000?29 3 8 6.3 答: 简已知某有向图的邻接矩阵如下：答021010001111? 题v0001?011231100101?1?23A?A?A ， ， ?v1001?0211232111102?A? ?v

18、1110011110000001?3?v0010?42123?3134vv?的有的长度为试求：到4431?Avv长度为4的有向路径的条数为3 ，由到条。 ?311533? 向路径的条数。1102? 30 已知某树有2个2度结点、3个3简8 7.1;7.3 ?t?t?29?2?33?4?4?d(v)?2 t 片树叶，总结点数为 答: 设该树有2 答4度结点，问有几个度结点、4个t?3?4?t?1?8?e?v?1?2 题叶子点（无其它度数点）。 总边数为 片树叶。该树有13即 t=13 。 29+t=2所以 ，(8+t) 31 简8 4.3 4 RR?RR,RR A上的任意二元关是自反的，则也是自

19、反的。因为答: 设和若是212211答 题?R?a?RR,R?a,RR?a?A,?Ra?a,a?R,?a,，即反的，自反， ，从而如系，果和自是22211121R?RR?R也是自反的。 是否也是自反的，为什2211R,RRRR?R不一定是对称的。是对称的，但 果么？如若和称是对的，212112R?a,b?,?b,a?R?b,c?,?c,b?R,RR?R是对称的吗？ 如：A = a , b , c ，则，是，222111 ?RR?a,?c 不是对称的。对称的，但21 32 7.1;7.简8 3 如图给出的赋权图表示六个城市答: 要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路

20、、边权之和2 答最小的子图即最小生成树，由避圈法或破圈法可得： f,d,e,a,bc及架起城市间直接 题其最小生成 树为：通讯线路的预测造价。试给出一 个设计方案使得各城市间能够通 讯且总造价最小，并计算出最小 总造价。 。1+2+3+5+7=18其树权即最小造价为： 33 简8 8.3 5 ，设S = R - -1（R为实数集）Sb?ab?Sb?易证a?b?a?a, : 1），即运算*是封闭的。答答ab?ba?b?a 。 题S?a,b,c? 2）?,?S 是否构成群； 说明?(a?b)?c?(a?b?ab)?c?a?b?ab?c?(a?b?ab)c ?a?b?c?ab?ac?bc?abc,而

21、 a?(b?c)?a?(b?c?bc)?a?(b?c?bc)?a(b?c?bc) ?a?b?c?bc?ab?ac?abc,?(a?b)?c?a?(b?c)，即*可结合。 ?a?S,e?a?a?e?a。 有幺元e，则关于 3）设S*?e?,0?ea?a?ae?e?a?ae。而 ?11?1?aaa?a?aeSa?，。则 设有逆元 ）4?a?1?11?0?a?aaa?a?S,?中任意元都有逆元，综上得出，即， S ，即a?1构成群。 34 将公式 (P?Q)?R）?(P?R)划为?，只含有联结词的等价公式。 )RP?Q)?R?(R)?)?(P?R)?(?P?(P?Q 答: 原式)RP?(?(P?Q)

22、?R?( 。 简答题8 2.1;2.2 3 35 ?,?H?K,?和都是群设?G,K?H?,?的子群，问?G?,?H?K,是否是和 的子群并说明理由。 ?G,K?H?,?GK?H?,?,? : 答 是 不一定是的子群，的子群。?,?ba,?ab?H?K,则,b?H,a,?K,由?H,?和?K?G,的 都是 子群，?1?1?1?H?K,?,是?bG,?K,?a?b?Ha?bKa?H且 ?G,?为群。且H = 112乘，则，5，K = 1的子群。如：G = 1，5，7，11，：模?H,?和?K,?G,?H?K?1,5,7，的 群，但子皆为7?H?K,?G,?5?7?11?H?K，即运算不封闭。的子

23、群。因为不是 简答题8 8.3 5 36 94，?A2，3，设12,，B?2，47，10到A，从 B的关系R?a,b?a?A,b?B,且a整除b的关系图和关系矩R，试给出?4,12?,?,3,12?,?44?,?,?R?2,2,?24?,2,10,?212?R: 答则B A 的关系图为：2 2 4 3 7 4 10 9 12 简答题8 5.2;4.2 4 阵，并说明此关系是否为函 数？为什么？ R的关系矩阵为 11011?00001?M ?R10001?00000?关系R不是A到B的函数，因为 元素2，4的象不唯一（或元素9无象）。 0121?37 OS?,?是左零是半群，设LOx?x?S,是

24、否是左元，对任L 零元？为什么？O?yOx?OOSy? 是左零元，所以，又仍是左零元。因为答: ，由于LLLL?S,? 为半群，所以*可结合。 Ox?O?x?(x?O)?yx?(O?y) 所以，仍是左零元。，所以，LLLL简答题8 8.1 3 38 某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由） : 可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图答G?V,E?，即要找一个过每个点一次且仅一次得回路。20人围一桌，使每人邻做都是朋友，?deg(u)?deg(v)?2010?v)?10,deg(u?u

25、,v?V,deg(，由判定定 ，由题已知，理，G中存在一条汉密尔顿回路。即所谈情况可能。 简答题8 6.4 3 39 通过主合取范式，求出使公式RP?Q?)?(?的真的值为F 值指派。)R)?(?Q?P?(?P?Q)?R?(?R)(原式?P?Q?R)?R?(?P)?(?QR)?P?QRQ?RQP(?)(P? : 答M?MM010110100?(?P?Q)?R 的真值指派为：F的值为使公式简答题8 2.2;2.3 3 P:1P:1P:0?Q:0Q:1Q:1 。 ； ；?R:0R:R:00?40 简8 4.1;4.3 ?a,b,cA?,?c,c?c,b?,?b,b?r(?)?a,a?,?a,b,?

26、b,c?, A，上的关设系 答: ，3 答 题?a,a?,?a,b?,?)?a,a?,?a,b?,?bs(,c?,?c,b?,?b,a?， ，?c,b,?b,c?2?c?c,?b,b?,?a,a?,?a,b?,?a,?c? ， ?)t()(和),s(r。 求出32?a,a?,?a,b?,?a,c?,?a?,b?,?b,c?,?c,b?， ?2?a,a?,?a,b?,?a,c?,?b,bt()?,?c,c?,?b,c?,?c,b?。 简 41 8 8.1;8.5 ?G，?1?G，4，65，32，: 。因为：，5已知答的运算表为： 既构成群，又构成循环群，其生成元为37773 答 题 明为。法乘模

27、7试说?G，?是否构成群？是7否为循环群？若是，生成元是什么？ ?封闭； 1）由运算表知，7? ）2可结合（可自证明）73）1为幺元； ?1?1?11?1?1?56?5336?2?124?14?， ，4），?G，综上所述，构成群。 712345613?3?53?33?23?63?4的逆3，3， 由。所以，为其生成元， 也为其生成元。元5?G，故为循环群。 742 简8 2.1;2.3 原式用等值演算法求下面公式的主析答: 3 答?(P?Q)?R?(?P?Q)?R?(?P?Q?R)?(?P?Q?R)? 取范式，并求其成真赋值。 题(P?Q?R)?(P?Q?R)?(?P?Q?R)?(?P?Q?R)

28、 (P?Q)?R m?mm?m?m?m?011111000001001101 使其成真赋值为：P0P0P1P1P0P0?Q0Q0Q1Q0Q0Q1 ， ， ， ， ， ?R1RRR11R01R1?43 简8 4.1;4.3 : 答,12,3,4A?系合上的关集3 答1010? 题? ?2,1?,?13?,?2,?R?1,1000?M,?33?,?34?,?31, R的关系图为 ?R1110?,?34,?4?,4?1010?M，画出关系，写出关系矩阵 R 是自反、对称的。图并讨论R的性质。 R 简8 7.1;7.3 44t3?1?度结点，2一棵树T中，有3个 ，则树tT的结点数为结点数 1，又边数 = 答: （1）设该树树叶数为2 答?度结点，其余结点都是树3一个倍2?边数deg(v)?12(3?t?1?3?2?13?t?1? ， 题i）画2中有几个结点；（T叶。（1）3?6?2tt9?t ， T中 ， 7个结点。即出具有上述度数的所有非同构的 3度结点，3片树叶的树（非同构的）共有以下三种：（2）具有3个两度结点，一个 无向图。 简8 4.4 3 45 的划分。）都不是（答: 设A=1,2,10。下列哪个是A1）和（2A答 的划分。其诱导的等价关系是3的划分？若是划分，则它们诱导）是A（ 题 的等价关系是什么？