南京大学计算机复试线 历年南京大学计算机考研复试离散数学题集.doc

南京大学计算机复试线 历年南京大学计算机考研复试离散数学题集 导读：就爱阅读网友为您分享以下“历年南京大学计算机考研复试离散数学题集”资讯，希望对您有所帮助，感谢您对92的支持! 严禁用于商业用途?前言?? 本文收集了 1997、 1998 年和 2001 年到 2007 年和 2009 年南京大学研究生入学考试科目 《离 散数学》的试卷以及相应试卷答案。2008 年试题未找到，1997 年到 2007 年试题给出本人所做 的答案，因为离散数学难度大，很多答案问过原来教我们离散数学的老师，老师也只能给出部 分答案，所以不能保证全部答案的正确性，2009 年试题答案未与同学核对，同样不能确保答 案正确性，故不在此给出。部分答案有更优解，需要同学们自己开发。? ? 南京大学从 2005 年开始把《离散数学》作为复试科目，满分为 80 分，与《编译原理》同 为笔试项目，总分 150 分。主要考试部分为数理逻辑、集合论、代数结构和图论。推荐复习时 候以南大课件为主，课件在网上可以查到，有宋方敏和陈道旭两种版本。通过真题发现，很多 题目都是课件上证明题的原题，而且考试重点与课件也吻合。? ? 离散数学特点就是难度大，上手容易深入难。代数系统和图论两章难度非常大，所以复习 好离散数学要有一定的耐心和钻研精神。? 相信天下无难事，只怕有心人。祝愿所有有志考南大 CS 的同学金榜提名。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 冷城? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2009 年 7 月? ? ? ? ?? ? ??? 1?/?30? ?严禁用于商业用途?1996 年?一．试证：? a.自然数集为无限集中势最小者。? b.不存在最大的势。? ? 二．任给无向图 G，其联结矩阵为 A=[aij]， （即若存在边(vi,vj)则 aij=1 否则 aij=0）试定义矩阵运 算并给出关于 A 的矩阵的表达式，B=E(A)，使得矩阵 B=[bij]满足：对于 G 中的任意两结点 vi,vj 若其间存在通路则 bij=1 否则 bij=0。? ? 三．任给无向图 G，? 对 G 中的边赋予方向得图 G，试证：存在 G 满足对任意两点 v1,v2 G， 不论从哪点为始终端均有有向通路到达另一点的充分条件是原图 G 连通且不存在割边。? ? 四．试分别用永真推理过程和假设推理过程证明：? ? ? ? (?α→?(?β?→?γ?)?)?→?(?(?α??β?)?→?γ?)? ? 五．试给出下式的析合范式和合析范式：? ? ? ? (?p?→?q?)?→?(?p?→?r?)? ? 六．试用谓词演算公式来描述一个代数系统(A,*)为一个群。? ? 七．任给一个集合 S，S 到自身的一一对应的映射成为 S 上的置换，试证：S 上置换的全体关于 置换的复合运算构成群。? ? ? ?? 2?/?30? ?严禁用于商业用途?1996 年答案?一．证明：? a.? 无限集 A，将 A 中元素按照某种次序（任意规则）排序，以 0,1,2,……,n 来表示 A 中某 元素排列的位置，所以存在自然数集 N 到集合 A 的单射， N A。 得证。? b.? 无限集 A， 元素α A， 设B A α ， A 到 B 有单射关系”=”， α A， A B。? 则 A B， 比 A 势更大的集合。因为对任一集合均有比其更大的势的集合。得证。? ? 二．B?=?E(?An?)，其中 An?=? ? A? ? n?=?1 时? 运算定义为：两矩阵相乘? n?–?1 A? n??1 时? E 为 An 运算收敛后若元素不为 0，则将其置为 1? ? ? ? ? ? ? A ? 三．证明：? ? 1.? 对于 G 中任一条边，先证其必在一个圈中：? 设存在边 e，e 不在一个圈中，e 的两个断点记为 u，v。若去掉边 e， u,?v 不在一个圈中，? ? ? ? ? u，v 间无通路，即 P(?G?–?e?)??P(G)。 e 为桥，与题设矛盾。得证。? 2.? 再证不存在桥的连通图 G 赋予边以方向后，G为强连通图。? 设不存在这样的圈，则存在对两个顶点 u,?v 没有经过它们的圈。 G是连通的， u 到 v 有 通路，设通路上的点为 u,?v1,?v2,?……,?vn，v 对于与 u,?v 相关联边，必有圈，v1,?v2 间必有圈， 则可将两圈合并，得到必有 u 到 v2 的圈，同理可得 u 到 v3 的圈，以此类推可得到 u 到 v 的圈，与假设不成立。 必存在将所有顶点连接的圈，将其以逆时针赋予方向后得经过每 个点至少一次的回路， G 为强连通图。? 得证。? ? 四．证明：? ? 永真推理：?