河海大学文天学院2008既计算机专业离散数学期末试卷

12009-2010学年第一学期离散数学期末试卷（计算机科学与技术专业2008级）学院____________学号____________姓名___________成绩____________一、判断题（本题共15小题，每小题1分，满分15分）（答题要求：请用大写英文字母“T”表示正确，“F”表示错误）（1）——（5）（6）——（10）（11）——（15）（1）命题、{}、{}都是真命题。（2）对于任意正确的推理，其命题逻辑的推理形式结构一定是重言蕴涵式。（3）设G是n个结点的m条边的简单有向连通图，那么n-1≤m≤n(n-1)/2。（4）设R是非空集合A上的关系，R是反对称关系当且仅当R∩R-1IA。（5）设G为无向图，若G中恰有n个结点，n-1条边，则G必为一棵树。（6）含n（n1）个命题变项的公式共有2n个不同的赋值。（7）设R1和R2是传递的二元关系，则R1R2也是传递的。（8）在有限偏序集中，极小元一定存在，但最小元不一定存在。（9）设G是n（n3）阶哈密顿图，则G中任意两个不相邻的顶点的度数之和均不小于n。（10）设A为n元集，R是A上的关系，则存在自然数s和t，使得Rs=Rt。（11）公式xF(x)→(xyG(x,y)→xF(x))是永真式。（12）设R是任意的关系，则srt(R)一定是等价关系。（13）若个体域为实数集，F(x,y):x=y，G(x,y):xy，则xy(┐F(x,y)→G(x,y))的真值为0。（14）若两个无向图的顶点数、边数以及顶点的度数列分别相等，则是它们同构的。（15）设G为无向图，如果G中恰有两个奇度顶点，那么这两个奇度顶点之间必有通路。二、（本题共8小题，每小题1分，满分8分）符号化下列命题。（要求：命题1-4在命题逻辑中符号化，命题5-8在一阶逻辑中符号化）（1）王欢与王强组成一个小组。（2）只有6被2整除，6才能被4整除。（3）王红和李刚仅有一人通过了面试。（4）小王边走路边听音乐。（5）没有不犯错误的人。（6）说火车比汽车跑的快是不对的。（7）除非李键是东北人，否则他一定怕冷。（8）42与3≥1互为充要条件。2三、（本题满分6分）已知有四个非负整数列（2，3，3，5，5，6，6）、（3，2，2，2）、（2，2，2，2，3，3，）和（4，4，3，2，1）。（1）判断这四个非负整数列中哪些数列是可图化的？哪些数列是可简单图化的？（2）对于可简单图化的非负整数列，给出两个不同构的简单图。四、（本题满分6分）设F，G，H为任意的关系，证明F·(G∪H)=F·G∪F·H，其中“·”为关系的复合运算。五、（本题满分6分）设无向树T有三个3度分支点，一个2度分支点，其余均为树叶。（1）求T中有几片树叶？（2）画出两棵满足上述要求的不同构的树。3六、（本题满分8分）某大学计算机专业100名学生中，C语言课有32人优秀，数据结构课有20人优秀，离散数学课有45人优秀。并且C语言和数据结构两门课都优秀的有15人；C语言和离散数学两门课都优秀的有7人；数据结构和离散数学两门课都优秀的有10人。此外，还有30人一门优秀都没得到。如果获得3门优秀者可得奖学金100元，获得2门优秀者可得奖学金60元，仅获得一门优秀者可得奖学金20元，问为该专业学生发奖学金需多少元？七、（本题满分8分）求公式（pq）∧（qr）的主析取范式与主合取范式，并分别写出公式的成真赋值和成假赋值。4八、（本题满分8分）设A={a,b,c,d}，R为定义在A上的二元关系，其关系图如下图所示。（1）说明R是偏序关系。（2）画出偏序集A,R的哈斯图。（3）设B={b,c}，求B的上界和上确界，下界和下确界。九、（本题满分8分）假设传输由7个符号a、b、c、d、e、f、g组成的信息，经统计这7个符号出现的概率分别为0.2、0.19、0.18、0.17、0.15、0.1、0.01。（1）求传输这7个符号的最佳二元前缀码（要求画出Huffman编码树）；（2）若记信息的长度为该信息所含符号的个数，则传输长度为10n（n≥2）的信息平均需要多少比特？5十、（本题满分8分）使用谓词逻辑构造证明法构造下面推理的证明：每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域为人类集合）十一、（本题满分8分）设A={0，1，2，3}，A上的二元关系R={x,y|x=y∨x+yA}。列出关系R，求R的关系图和关系矩阵，并判断R的性质。6十二、（本题满分11分）对于右图所示的有向图，（1）给出该有向图的邻接矩阵；（2）求顶点v1到v4长度为1，2，3，4的通路分别有几条？（3）求顶点v4到自身长度为1，2，3，4的通路分别有几条？（4）求出长度为4的通路和回路分别有几条？（5）求出长度为小于等于4的非回路通路和回路各有几条？