《离散数学题库简答题》由会员分享，可在线阅读，更多相关《离散数学题库简答题（18页珍藏版）》请在金锄头文库上搜索。
1、编号题目答案题型分值大纲难度1 1设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 答: ， t (R)= , , , , , , , , 简答题84.33如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。答: 用Kruskal算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。简答题87.23设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出的所有子群。答: 子群有；简答题88.33权数1，4，9，16，25
2、，36，49，64，81，100构造一棵最优二叉树。答: 简答题87.23集合X=, , , ，R=,|x1+y2 = x2+y1 。1） 说明R是X上的等价关系。 （6分）2） 求出X关于R的商集。（2分）答: 1）、1、 自反性： 2、 对称性：3、 传递性：即由（1）（2）（3）知：R是X上的先等价关系。2）、X/R=简答题84.43设集合A= a ,b , c , d 上关系R= , , , 要求 1）、写出R的关系矩阵和关系图。（4分） 2）、用矩阵运算求出R的传递闭包。（4分）答: 1、； 关系图2、t (R)= , , , , , , , , 。简答题84.1;4.34利用主析取
3、范式，判断公式的类型。答: 它无成真赋值，所以为矛盾式。简答题82.33在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分）答: （1）由Huffman方法,得最佳二叉树为：（2）最佳前缀码为：000，001，01，10，11简答题87.23下图所示带权图中最优投递路线并求出投递路线长度（邮局在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+
4、12+10+23=281。简答题87.25设S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?答: (1)=,，,covS=, ,Hass图为（2）极小元、最小元是1，极大元、最大元是 24。简答题84.44设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？答: 公式A涵义为：对任意的实数x,y,z，如果xy 则 (x-z) (y-z) A的真值为： 真（T）。简答题83.23给定3个命题：P：北京比天津人口多；Q：2大
5、于1；R：15是素数。 求复合命题：的真值。答: P，Q是真命题，R是假命题。简答题82.23给定解释I：D=2，3，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。答: 简答题83.1;3.23将化为与其等价的前束范式。答: 简答题83.23简述关系的性质有哪些？自反性，对称性，传递性，反自反性，反对称性简答题84.31假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new ye
6、ar的编码信息。答:解：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：简答题87.23用washall方法求图的可达矩阵，并判断图的连通性。答: 1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。简答题86.33设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、
7、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？答:用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为a b d f g e c a。简答题86.43用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（答: （1） 用0000传输a、0001传输b、
8、001传输c、01传输f、10传输d、11传输e传输它们的最优前缀码为0000，0001，001，01，10，11 。简答题87.23构造一个结点v与边数e奇偶性相反的欧拉图。答: 简答题86.45设A=1，2，3，4，S=1，2，3，4，为A的一个分划，求由S导出的等价关系。答: R= , , , , 简答题84.43设，偏序集的Hass图为求 A中最小元与最大元； 的上界和上确界，下界和下确界。答: A中最大元为 ，最小元不存在； 上界 ，上确界；下界无，下确界无。简答题84.43用Warshall算法，对集合A=1，2，3，4，5上二元关系R=,求t（R）。答: 1时，1,1=1, A
9、=2时，M1,2=M4,2=1A=3时，A的第三列全为0，故A不变4时，M1,4=M2,4=M4,4=1A= 5时，M3,5=1 ，这时A=所以t (R)=, , 。简答题84.1;4.34将谓词公式化为前束析取范式与前束合取范式。答: 简答题82.1;3.1;3.23)、画一个有一条欧拉回路和一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。)、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。答:简答题86.43求的主合取范式。答: 简答题82.33在下面关系中:判定关系的性质。答: R自反任意实数x，x-x+20 ， x-x-20 , 所以直线y=x上的点在区域内
10、，即 , 故R自反； R对称若 有 得 即 所以 R对称；因R自反且结点集非空，故R非反自反；因R对称且结点集非空，并非全是孤立点，故R不是反对称；由 得 所以 而 所以R4不是传递的。简答题84.34求图的邻接矩阵和可达矩阵。答: ， ， ，。所以可达矩阵简答题86.33已知某有向图的邻接矩阵如下： 试求：到的长度为4的有向路径的条数。答: ， ， ， ，由到长度为4的有向路径的条数为3条。简答题86.33已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。答: 设该树有t 片树叶，总结点数为 总边数为 所以 ， 29+t=2(8+t) 即 t=13 。 该树
11、有13片树叶。简答题87.1;7.23设和是A上的任意二元关系，如果和是自反的，是否也是自反的，为什么？如果和是对称的，是对称的吗？答: 若是自反的，则也是自反的。因为 自反，从而 ，即也是自反的。 若是对称的，但不一定是对称的。 如：A = a , b , c，则是对称的，但不是对称的。简答题84.34如图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。答: 要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造价为：1+2+3+5+7=18。简答题87.1;7.23设S = R - -1（R为实数集），。 说明是否构成群； 答: 1），即运算*是封闭的。 2）而，即*可结合。 3）设S关于*有幺元e，则。而 。4） 设有逆元 。则，即 ，即 S中任意元都有逆元，综上得出，构成群。简答题88.35将公式划为只含有联结词的等价公式。答: 原式
