【离散试卷】2009-2010-1.docVIP

上 海 海 事 大 学 试 卷 2009 — 2010 学年第一学期期末考试 《 离散数学 》（A卷） 班级 学号 姓名 总分 题 目 得 分 阅卷人 说明：在复合函数中，f表示第一函数。 1(5’)已知命题的前提为：如果天下雨，那么我将开车或乘公交车；我没开车；天在下雨。结论为：我将乘公交车。 先将该命题符号化，并给出形式证明。 2(5’)(a)用真值表判断命题的类型. (b)用主析取范式判断命题的类型. 3(5’)判断以下关于集合A，B，C的命题是否成立，正确的给出证明，错误的给出反例。 （a）。 （b）。 4(5’)(a)在1到1000之间（包含1和1000在内）既不能被2和5，也不能被17整除的整数有多少个？ (b)能被2整除，但不能被5和17整除的整数又有多少个？ 5(5’)（a）不使用否定连接词“﹃”写出下面谓词公式的否定式：。 （b）当x，y，z的论域分别为R，Q，N，Z时，确定P的真值。 6(5’)符号化下面命题并推证其结论 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。 7(5’)f和g是用向上取整函数（ceiling）和向下取整函数（floor）定义的两个函数。 （a） （b） 8(6’)f和g是两个定义在N上的函数：f(n)=n+1, g(n)=max{0,n-1}. (a)当n=0,1,2,3,4,73时计算f(n)的值。 (b)当n=0,1,2,3,4,73时计算g(n)的值。 (c)证明f是单射，但不是满射。 (d)证明g是满射，但不是单射。 (e) 9(5’)设函数f: R×R→R×R定义为 f(x,y)=(x+y,x-y) 该函数是可逆的，证明其反函数为 10(5’)已知f: S→T, g: T→U是可逆函数，所以。 11(5’)定义Z上的等价关系R如下： R有多少个等价类？ 给下列每个等价类列出3个元素: [1], [-73], [73], [4]. 求自然映射g: Z→Z/R. 12(5’)考虑下图给出的三个格 (a)计算。你能得出怎样的结论？ (b)计算。你能得出怎样的结论？ (c)计算。 13(5’)设(S, |)是偏序集，其中基本集合是S={2,3,4,5,6,…,500}，| 是偏序关系，m|n表示m整除n。 (a)该偏序集有250个极大元素，它们是哪些元素？ (b)描述极小元素的情况，并写出4个极小元素。 (c)给出(S, |)中两个极大链的例子 (d)下列值如果在S中存在的话，请写出具体的值：lub{24,54},glb{24,54},lub{3,5},glb{3,5},lub{2,73} 14(5’)设S={2，3，4，5，6，7，8，9，10，11，12}，关系R定义为。 (a) r(R)=R吗？如果不相等，写出一个属于r(R)但不属于R的序对。 (b) s(R)=R吗？如果不相等，写出一个属于s(R)但不属于R的序对。 (c) t(R)=R吗？如果不相等，写出一个属于t(R)但不属于R的序对。 (d) 对等价关系tsr(R)，找出包含12的等价类。 15(5’)参照下面两个图G和H回答以下问题： (a)图G有欧拉回路吗？说明理由。 (b)写出图H中一条欧拉路的顶点序列。 (c)写出图H中一个圈的顶点序列。 (d)图G中的每个简单回路都是圈吗？说明理由。 (f)图G有哈密顿路吗？说明理由。 16(4’)参考下列加权图，其中W(e1)W(e2) … W(e11)W(e12) 用Kruskal算法求最小生成树，按照算法的选择顺序列出边的序列。 17(5’)有5条记录按字母表顺序从左到右安排在如下二叉树中： (a)描述如何在该树中有哪些信誉好的足球投注网站记录goo。 (b)描述如何在该树中有哪些信誉好的足球投注网站记录poo。 (c)将该二叉树修改为新的二叉树，使得新树中包含原有的全部记录和一条新记录poo，并且树的高度保持不变。 18(5’)下列4个图中哪些图同构？对于同构的图同构关系(直接标在图上)，对于不同构的图说明理由。 19(5’)如下图，5个房间16道门，现在要求从某点出发每道门恰走一次回到出发点。 (a)这样的走法存在吗？解释理由。 (b)若把连接两个大房间的门封掉，结果会怎样变化？ 20(5’)考虑有n个顶点的树，它恰有n-1条边，所以它的顶点度数的和是2n-2。 (a)某棵树有2个顶点度数是4，一个顶点度数是3，一个顶点度数是2。