《河海大学文天学院2008既计算机专业离散数学期末试卷》由会员分享，可在线阅读，更多相关《河海大学文天学院2008既计算机专业离散数学期末试卷（6页珍藏版）》请在金锄头文库上搜索。
1、12009-20102009-2010 学年第一学期离散数学期末试卷学年第一学期离散数学期末试卷（计算机科学与技术专业（计算机科学与技术专业 20082008 级）级）学院学院_学号学号_姓名姓名_成绩成绩_一、判断题（本题共一、判断题（本题共 1515 小题，每小题小题，每小题 1 1 分，满分分，满分 1515 分）分） （答题要求：请用大写英文字母“T”表示正确， “F”表示错误） （1） （5）（6） （10）（11） （15）（1）命题、都是真命题。 （2）对于任意正确的推理，其命题逻辑的推理形式结构一定是重言蕴涵式。 （3）设 G 是 n 个结点的 m 条边的简单有向连通图，那么
2、n-1mn(n-1)/2。 （4）设 R 是非空集合 A 上的关系，R 是反对称关系当且仅当 RR-1IA。 （5）设 G 为无向图，若 G 中恰有 n 个结点，n-1 条边，则 G 必为一棵树。 （6）含 n（n1）个命题变项的公式共有 2n个不同的赋值。 （7）设 R1和 R2是传递的二元关系，则 R1R2也是传递的。 （8）在有限偏序集中，极小元一定存在，但最小元不一定存在。 （9）设 G 是 n（n3）阶哈密顿图，则 G 中任意两个不相邻的顶点的度数之和均不小于 n。 （10）设 A 为 n 元集，R 是 A 上的关系，则存在自然数 s 和 t，使得 Rs=Rt。 （11）公式xF(x
3、)(xyG(x,y)xF(x)是永真式。 （12）设 R 是任意的关系，则 srt(R)一定是等价关系。 （13）若个体域为实数集，F(x,y): x=y，G(x,y): x2 与 31 互为充要条件。2三、三、 （本题满分（本题满分 6 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 6 分）分）设 F，G，H 为任意的
4、关系，证明 F(GH)=FGFH，其中“”为 关系的复合运算。五、五、 （本题满分（本题满分 6 6 分）分）设无向树 T 有三个 3 度分支点，一个 2 度分支点，其余均为树叶。 （1）求 T 中有几片树叶？（2）画出两棵满足上述要求的不同构的树。3六、六、 （本题满分（本题满分 8 8 分）分）某大学计算机专业 100 名学生中，C 语言课有 32 人优秀，数据结构 课有 20 人优秀，离散数学课有 45 人优秀。并且 C 语言和数据结构两门课都优秀的有 15 人； C 语言和离散数学两门课都优秀的有 7 人；数据结构和离散数学两门课都优秀的有 10 人。 此外，还有 30 人一门优秀都没
5、得到。如果获得 3 门优秀者可得奖学金 100 元，获得 2 门优 秀者可得奖学金 60 元，仅获得一门优秀者可得奖学金 20 元，问为该专业学生发奖学金需 多少元？七、七、 （本题满分（本题满分 8 8 分）分）求公式（pq）（qr）的主析取范式与主合取范式，并分别写出 公式的成真赋值和成假赋值。4八、八、 （本题满分（本题满分 8 8 分）分）设 A=a, b, c, d，R 为定义在 A 上的二元关系，其关系图如下图所示。（1）说明 R 是偏序关系。 （2）画出偏序集的哈斯图。 （3）设 B=b, c，求 B 的上界和上确界，下界和下确界。九、九、 （本题满分（本题满分 8 8 分）分）
6、假设传输由 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（n2）的信息平均需要多少比特？5十、十、 （本题满分（本题满分 8 8 分）分）使用谓词逻辑构造证明法构造下面推理的证明：每个喜欢步行的人都 不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以 有的人不喜欢步行。 （个体域为人类集合）十一、十一、 （本题满分（本题满分 8 8 分）分）设 A=0，1，2，3，A 上的二元关系 R=|x=yx+yA。列 出关系 R，求 R 的关系图和关系矩阵，并判断 R 的性质。6十二、十二、 （本题满分（本题满分 1111 分）分）对于右图所示的有向图， （1）给出该有向图的邻接矩阵； （2）求顶点 v1 到 v4 长度为 1，2，3，4 的通路分别有几条？ （3）求顶点 v4 到自身长度为 1，2，3，4 的通路分别有几条？ （4）求出长度为 4 的通路和回路分别有几条？ （5）求出长度为小于等于 4 的非回路通路和回路各有几条？
