《离散数学A》2011试题及答案

2010-2011-2学期《离散数学B》-B卷-参考答案第1页共5页西南科技大学2010-2011-2学期《离散数学A》本科期末考试试卷（B卷）参考答案及评分细则一、判断题（本大题共10个小题，每小题2分，共20分）将每小题的判断结果写在答题纸上，正确的写“正确”，错误的写“错误”。1.“3+3=6”,不是命题。（错误）2.命题公式（PQQ）是偶然式。（正确）3.若B中不含有x，则x（A(x)B）xA(x)B。（错误）4.如果论述域是{a，b}，则xR(x)R(a)R(b)。（错误）5.若集合A的基数|A|=5，则A的幂集的基数|(A)|=32。（正确）6.设A是一个集合，则AA=。（错误）7.设R是非空集合A上的二元关系，则R的传递闭包t(R)=RR0。（错误）8.所有欧拉图的顶点次（度）数一定是偶数。（正确）9.无向图G是二部图当且仅当G中所有回路的长度均为偶数。（正确）10.K5、K3,3都是非平面图。（正确）二、简单计算题（本大题共10个小题，每小题3分，共30分）将每小题的计算结果写在答题纸上。1.设P：我有时间；Q：我去镇上，用逻辑符合写出命题“只有我有时间，我才去镇上。”。答案：QP2.对命题公式：P（QR）PQ化为仅含和的等价表达式。答案：（PQ）3.设S(x)：x是火车，L(x)：x是卡车，F(x,y)：x比y快。在谓词逻辑中符号化命题“所有火车都比所有卡车快”。答案：x(S(x)→y(L(y)∧F（x,y）)4.求谓词公式xP(x)xQ(x)的前束范式。答案：xy(P(x)Q(x))课程代码143990230命题单位计算机科学与技术学院：软件工程系2010-2011-2学期《离散数学B》-B卷-参考答案第2页共5页5.在一个班级50个学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A，假如17人两次考试都没有得到A，问有多少学生在两次考试中都得到A？答案：14人。6.假设A是n个元素的有限集合，有多少个元素在A上的最小等价关系中？答案：n个。7.二元关系的关系图如下图所示，则R具有哪些特性（性质）？答案：R是反自反的、对称的。8.一颗树有两个顶点的度数为2，一个顶点的度数为3，三个顶点的度数为4，问它有几个度数为1的顶点？答案：9个。9.无向连通图G如下所示，则该图的最小生成树的权是多少？答案：1510.对下图所标记二叉树，写出按中序周游的结果。答案：dbheiafcg2010-2011-2学期《离散数学B》-B卷-参考答案第3页共5页三、应用题（本大题共4个小题，每小题8分，共32分）将每小题的求解或证明过程写在答题纸上。1.求命题公式：(PQ)(QP)的主析取范式和主合取范式。答案：用等值演算法、真值表法均可，根据解题过程及答案正确与否酌情给分。主吸取范式为：(PQ)(PQ)(PQ)=(0,2,3)主合取范式为：PQ2.设A={a,b,c,d}，1、2、3是A上的划分，1={{a,b},{c,d}}，2={{a},{b},{c},{d}}，3={{a,b,c,d}}，试求：（1）1所诱导出的等价关系的序偶。答案：{a,a,b,b,c,c,,d,da,b,b,a,c,d,d,c}（2）写出偏序集合{1,2,3}，细分的“细分”关系元素，并画出该偏序集合的哈斯图。答案：“细分”关系={1,1,1,3,2,2,2,3,2,1,3,3}哈斯图为：（3）求集合{1,2,3}的最大元、最小元、极大元、极小元。答案：最大元为3，最小元为2，极大元为3，极小元为2。3.有向图G如下图所示。(1)用邻接矩阵求G中v1到v4长度为3和4的路径各有几条？2010-2011-2学期《离散数学B》-B卷-参考答案第4页共5页答案：因为G的邻接矩阵为：0010101011001010A所以，1100111010201110)2(A，1020212022102120)3(A，2210323031403230)4(A故，G中v1到v4长度为3的路径为2条，长度为4的路径为3条。(2)求G的可达性矩阵。答案：因为：11001110101011102A，10101110111011103A，11101110111011104AG的可达矩阵为：1110111011101110432AAAAP。4.证明：在有6个顶点，12条边的连通平面简单图中，每个区域用3条边围成。证明：n=6，m=12，由欧拉公式得面数k=8。若有区域是用＞3条边围成的，则有2m＞3k，即24＞24，从而导致矛盾。这说明每个区域用3条边围成。四、应用题（本大题共2个小题，每小题9分，共18分）将每小题的求解或证明过程写在答题纸上。(1)将下列推理符号化并给出形式证明：每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家。证明：首先将命题符号化，个体域为全总个体域。F(x)：x是学术会成员。G(x)：x是专家。H(x)：x是工人。R(x)：x是青年人。。则该推理的形式结构为：x(F(x)H(x)G(x))，x(F(x)R(x))x(F(x)R(x)G(x))。①x(F(x)R(x))P②F(c)R(c)T，①，ES③x(F(x)H(x)G(x))P④F(x)H(x)G(x)T，③，US2010-2011-2学期《离散数学B》-B卷-参考答案第5页共5页⑤F(c)T，②，简化式⑥H(x)G(x)T，④⑤，假言推理⑦R(c)T，②，简化式⑧G(x)T，⑥，简化式⑨F(c)R(c)G(c)T，⑤⑦⑧，合取引入⑩x(F(x)R(x)G(x))T，⑨，EG(2)设7个字母在通信中出现的频率如下：A：35%B：20%C：15%D：10%E：10%F：5%G：5%采用2元前缀码，求传输数字最少的2元码（即最小前缀码），并求传输10000个按上述比例出现的八进制数字需要多少个二进制数字？若用长为3的等长码字传输需要多少个二进制数字？解答：用Huffman算法求频率（乘以100）为权的最优2元树，其中w1=5，w2=5，w3=10，w4=10，w5=15，w6=20，w7=35；最优2元树如图所示：故，可采取如下编码：A---11B---01C---101D---100E---001F---0001G---0000传输100个按比例出现的7个字母所需二进制数字的个数为w(T)=255个，故传输10000个所用二进制数字的个数为25500个。而用长为3的等长码字传输需要30000个二进制数字。