离散数学题库简答题

编号题目答案题型分值大纲难度11设集合A={a，b，c，d}上的关系R={a,b,b,a,b,c,c,d}用矩阵运算求出R的传递闭包t(R)。答:0000100001010010RM，00000000101001012RRRMMM000000000101101023RRRMMM000000001010010134RRRMMM0000100011111111432)(RRRRRtMMMMMt(R)={a,a,a,b,a,c,a,d,b,a,b,b,b,c.,b,d,c,d}简答题84.332如下图所示的赋权图表示某七个城市721,,,vvv及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。答:用Kruskal算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。简答题87.233设Z6,+6是一个群，这里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，试求出Z6,+6的所有子群。答:子群有{[0]},+6；{[0],[3]},+6；{[0],[2],[4]},+6；{Z6},+6简答题88.334权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。答:简答题87.235集合X={1,2,3,4,5,6,答:1）、简84.43…}，R={x1,y1,x2,y2|x1+y2=x2+y1}。1）说明R是X上的等价关系。（6分）2）求出X关于R的商集。（2分）1、自反性：yxyxXyx由于,,自反RRyxyx,,,2、对称性：XyxXyx2211,,,时当Ryxyx2211,,,21121221yxyxyxyx也即即有对称性故RRyxyx1122,,,3、传递性：XyxXyxXyx332211,,,,时且当RyxyxRyxyx33222211,,,,,,)2()1(23321221yxyxyxyx即23123221)2()1(yxyxyxyx即1331yxyx有传递性故RRyxyx3311,,,由（1）（2）（3）知：R是X上的先等价关系。2）、X/R=}]2,1{[R答题6设集合A={a,b,c,d}上关系R={a,b,b,a,b,c,c,d}答:简答题84.1;4.34要求1）、写出R的关系矩阵和关系图。（4分）2）、用矩阵运算求出R的传递闭包。（4分）1、0000100001010010RM；关系图2、00000000101001012RRRMMM000000000101101023RRRMMM2340000000010100101RRRRMMMM,,4635RRRRMMMM0000100011111111432)(RRRRRtMMMMMt(R)={a,a,a,b,a,c,a,d,b,a,b,b,b,c.,b,d,c,d}。7利用主析取范式，判断公式RQQP)(的类型。答:FRQQPRQQPRQQPRQQP)()()()()(简答题82.33它无成真赋值，所以为矛盾式。8在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分）答:（1）由Huffman方法,得最佳二叉树为：（2）最佳前缀码为：000，001，01，10，11简答题87.239下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。答:图中奇数点为E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF复制道路EG、GF，得图G‘，则G‘是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。简答题87.2510设S={1,2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）偏序集,S　的Hass图如何？（2）偏序集},{S　的极小答:(1)≤={1,2,1,3,1,4,1,6,1,8,1,12,1,24,2,4,2,6,2,8，2,12,2,24,3,6,3,12,3,24,4,8,4,12,4,24,6,12,6,24,8,24,12,24}SIcovS={1,2,1,3,2,4,2,6,3,6,4,8,4,12,6,12,8,24,12,24}简答题84.44元、最小元、极大元、最大元是什么?Hass图为（2）极小元、最小元是1，极大元、最大元是24。11设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数yxyxf),(，特定谓词yxyxF:),(，问公式))),(),,((),((zyfzxfFyxFzyxA的涵义如何？真值如何？答:公式A涵义为：对任意的实数x,y,z，如果xy则(x-z)(y-z)A的真值为：真（T）。简答题83.2312给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。求复合命题：)()(RPRQ的真值。答:P，Q是真命题，R是假命题。010)11()01()()(RPRQ简答题82.2313给定解释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简答题83.1;3.2314将)))()(()),(((xRzzQyxyPxwff化为与其等价的前束范式。答:))()(),(()))())((),((()))())(((),(((()))())((()),(((xRzQyxPzyxxRzQzyxPyxxRzzQyxPyxxRzzQyxPyx简答题83.2315简述关系的性质有哪些？自反性，对称性，传递性，反自反性，反对称性简答题84.3116假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。答:解：传输它们的最佳前缀码如上图所示，happynewyear的编码信息为：10011010101010011101110100001111011000附：最优二叉树求解过程如下：简答题87.2317用washall方法求图的可达矩阵，并判断图的连通性。答:0010100001011100)(GAi1：A[2，1]=1，0010100011011100A；i2：A[4，2]=1，1111100011011100Ai3：A[1，3]=A[2，3]=A[4，3]=1，1111100011011100Ai4：A[k，4]=1，k=1，2，3，4，1111111111111111Ap中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。简答题86.3318设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？答:用a,b,c,d,e,f,g7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为abdfgeca。简答题86.4319用Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a，b，c，d，e，f的频率分别为2%，3%，5%，7%，8%，9%求传输它的最佳前缀码。（答:83282729354342)(TW（1）用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e传输它们的最优前缀码为{0000，0001，001，01，10，11}。简答题87.2320构造一个结点v与边数e奇偶性相反的欧拉图。答:简答题86.4521设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。答:R={1,1,2,2,2,3,3,2,3,34,4}简答题84.4322设},,,,{54321xxxxxA，偏序集RA,的Hass图为求①A中最小元与最大元；②},,{543xxx的上界和上确界，下界和下确界。答:①A中最大元为1x，最小元不存在；②},,{543xxx上界31,xx，上确界1x；下界无，下确界无。简答题84.4323用Warshall算法，对集合A={1，2，3，4，5}上二元关系R={1,1,1,2,2,4,3,5,4,2}求t（R）。答:0000000010100000100000011RMi1时，RM[1,1]=1,A=RMi2时，M[1,2]=M[4,2]=1A=0000001010100000100001011简答题84.1;4.34i3时，A的第三列全为0，故A不变i4时，M[1,4]=M[2,4]=M[4,4]=1A=0000001010100000101001011i5时，M[3,5]=1，这时A=0000001010100000101001011所以t(R)={1,1,1,2,1,4,2,2,2,4,3,5,4,2,4,4}。24将谓词公式)()())()()()((yRyyQyxPx化为前束析取范式与前束合取范式。答:前束合取范式前束析取范式))()(())()()(()()(())())()()(()()(()()())(()()(()()())(()()(()()())()(()()(()()())(()((()()())(()()(((zRyQzRxPzyxzRyQxPzyxzRzyQyxPxyRyyQyxPxyRyyQyxPxyRyyyQxxPyRyyyQxPx简答题82.1;3.1;3.2325１)、画一个有一条欧拉回路和一条汉密尔顿回路的图。答:简答题86.43２)、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。３)、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。26求)()(QPPQ的主合取范式。答:)()()