中大复试离散数学_中大复试题目

中大复试离散数学由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“中大复试题目”。

2003: 离散部分

1)R是A上的一个对称和传递的关系,对于任意a属于A,都存在一个b属于A,使得属

于R,证明R是一个等价关系。

2)是一个半群,对于任意a, b属于G,a!=b,则a*b!=b*a。试证:对任一元素a属于

G,有a*a=a。

3)证明一个图G,它顶点的最小顶点度不小于2,证明它存在圈。4)求(PVQ)P主析取范式。

04 年

8．证明对于集合A、B、C，如果有A∩B=B∩C，并且A∩B=A*∩C，其中A*为A的补集，则一定有B=C。（10分）。9．证明：一个连通且每个顶点的度数都为偶数的图一定没有割边。（10分）

10．设代数系统（G，*）为一个半群，且有左单位元e，对于任意一个x均有x’,使得x’*x=e。证明：对于任意a、b、c，如果b*a=b*c，则一定有a=c。（15分）11．根据已知前提，证明如下结论（10分）前提：P ┑RVP, Q 结论：R

11年

离散总共五道题，第一道关于一阶逻辑求主析取范式、主合取范式、真值表(只要看了书，计算细心点，这道题一般能拿满分）

第二道对循环关系有如下定义：对于A上的关系R，若对任意属于R且属于R，则属于R.证明：R是自反和循环关系当且仅当R是等价关系。（我当时不知道什么是循环关系，悲剧了）

第三道考得是集合的求解，思想与课本上的200能被3、5、7整除解法类似，（文氏图法或都公式法）

第四道考得Dijkstra算法，初试数据结构是重点章节，问题不大

第五道证明对于任意一个具有6个顶点的简单图，要么它包含一个三角形，要么它的补图包含一个三角形（这个题当时很晕，不知如何下手）