历年南京大学计算机考研复试离散数学题集_南京理工大学824离散数学

4星 · 超过85%的资源需积分: 45 102 浏览量更新于2023-03-03 评论 11 收藏 440KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

严禁用于商业用途

前言

 本文收集了 1997、1998 年和 2001 年到 2007 年和 2009 年南京大学研究生入学考试科目《离

散数学》的试卷以及相应试卷答案。2008 年试题未找到，1997 年到 2007 年试题给出本人所做

的答案，因为离散数学难度大，很多答案问过原来教我们离散数学的老师，老师也只能给出部

分答案，所以不能保证全部答案的正确性，2009 年试题答案未与同学核对，同样不能确保答

案正确性，故不在此给出。部分答案有更优解，需要同学们自己开发。

 南京大学从 2005 年开始把《离散数学》作为复试科目，满分为 80 分，与《编译原理》同

为笔试项目，总分 150 分。主要考试部分为数理逻辑、集合论、代数结构和图论。推荐复习时

候以南大课件为主，课件在网上可以查到，有宋方敏和陈道旭两种版本。通过真题发现，很多

题目都是课件上证明题的原题，而且考试重点与课件也吻合。

 离散数学特点就是难度大，上手容易深入难。代数系统和图论两章难度非常大，所以复习

好离散数学要有一定的耐心和钻研精神。

相信天下无难事，只怕有心人。祝愿所有有志考南大 CS 的同学金榜提名。



冷城

2009 年 7 月



 1/30



严禁用于商业用途

1996 年答案

一．证明：

a. 无限集 A，将 A 中元素按照某种次序（任意规则）排序，以 0,1,2,……,n 来表示 A 中某

元素排列的位置，所自集合 A 的单射，NA。 以存在然数集 N 到得证。

元素αA，设BA

󰇝

󰇞

，则 A 到 B 有单射关系”=”，αA， AB。b. 无限集 A，

AB，比 A 势更大的集合。因为对任一集合均有比其更大的势的集合。得证。



二．B=E(A

n

)，其中 A

= A n=1 时 运算定义为：两矩阵相乘

A

n–1

A n>1 时 E 为 A

运算收敛后若元素不为 0，则将其置为 1



三．证明：

 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,v

,v

,……,v

，v 对于与 u,v 相关联边，必有圈，v

,v

间必有圈，

则可将两圈合并，得到必有 u 到 v

的圈，同理可得 u 到 v

的圈，以此类推可得到 u 到 v

的圈，与假设不成立。必存在将所有顶点连接的圈，将其以逆时针赋予方向后得经过每

个点至少一次的回路，G 为强连通图。

得证。



四．证明：

 永真推理

󰇛

α ：

󰇛

α 

󰇛

β  γ

󰇜

 󰇛  β

󰇜

 γ 󰇜

 β  ﹁  󰇜  α ﹁ γ    󰇛

󰇛

α β

󰇜

 γ

  ﹁α  ﹁β  γ   󰇛 ﹁α  ﹁β  γ 󰇜

 1

 假设推理：

  前提引入 α 

󰇛

β  γ

󰇜

  结论

󰇛

α   β

󰇜

γ

  结论

󰇛

否定引入 ﹁ 󰇛 α β

󰇜

 γ 󰇜

 󰇛   󰇜

󰇛

α 

󰇛

β  γ

󰇜

 ﹁

󰇛

α β

󰇜

  α  ﹁β  γ   󰇛 ﹁α  ﹁β  γ 󰇜  ﹁

   0



五． p→ r) ( q)→(p→ 

 ﹁p p  󰇛  q 󰇜  󰇛 ﹁  r 󰇜

  p r 󰇜 ﹁󰇛 ﹁p  q 󰇜 󰇛 ﹁ 

 q ﹁p  󰇛 p  ﹁ 󰇜   r

 󰇛 ﹁ 󰇛﹁q  ﹁p󰇜  r

 3/30



 󰇛 p  p 󰇜 

 ﹁p  ﹁q  r





 M

严禁用于商业用途

1997 年

一．R

、R

分别是集合 S、T 上的关系，定义 ST 上的关系 R

：<s

>当且仅当 s

，

。

证明： (1)若 R

、R

为等价关系，则 R

为等价关系。

  (2)若 R

、R

为偏序，则 R

也是偏序。



二．证明：S 是无限集当且仅当存在 S 的真子集 S’：满足 S 与 S’等势。



三．图 G=(V

)，R

是定点集 V

上的相邻关系，即对任意 u,v∈V

，uR

v 当且仅当 u,v∈E

。

是 V

上的可达关系，即 uR

v 当且仅当在 G 中存在 vu‐通路。

证明 R2 是 R1 的传递闭包。



四．(1)T 是树，e 是 T 中任意一条边，证明：T’=T‐{e}是连通分支数为 2 的森林。

 (2)图 G=(V

)，|V

|=n，|E

|=m，G 连通且恰好含一个回路的充分必要条件是下列三项中

的任意两项成立。

(i)G 连通，(ii)G 恰好含一个回路，(iii)m=n。



五．(1)若 G 是奇数阶有限群，证明对任意 a∈G，方程 x

=a 有解。

(2)若在有限群 G 中，对任意 a，x

=a 有唯一解，则|G|必为奇数。



六．Zm、Zn 分别是 m、n 阶剩余加群。定义代数系统(ZmZn,*)：对任意 x1,x2∈Zm，y1,y2∈Zn，

(x1,y1)*(x2,y2)=(x1+mx2,y1+ny2)。

证明：若 m、n 互质，ZmZn 是循环群，生成元为(1,1)。

证明：（1）封闭性

（2）可结合性

（3）幺元 （0,0）

（4）逆元显然，对于任意（a,b） Z∈

×Z

, 有（a

‐1

,b

‐1

）

综上所述，对于任意的 m、n，（Z

×Z

,*）都是群。

显然，若 m 与 n 互质， Zm×Zn 是循环群，生成元为(1,1)。



七．试讨论在一给定公理系统的公理系统集合中添加或删除元素，对系统的性质可能产生什么

影响。（提示：在添加元素的情况下，要考虑所加公式在原系统中是否可证。）



八．给下列命题：

(1)参加展览的人中，每个 N 大学的男生都背 K 牌书包。

(2)参观展览的人中，每个背 K 牌书宝的都是来自 N 大学的男生。

(3)每个背 K 牌书包的 N 大学男生都参观了该展览。

写出相关的谓词逻辑表达式，证明：(1)(2)不能推出(3)。





 5/30



剩余29页未读，继续阅读

Jacques丶

2014-05-12

试题很有参考价值，对我帮助很大

longdeliu

粉丝: 4
资源: 3

会员权益专享

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

评论4

会员权益专享

最新资源

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

评论4

南京大学计算机系离散数学讲义（陈道蓄）

离散数学 课后习题答案 耿素云，曲婉玲 计算机专业

华东师范大学考研计算机复试机试习题.pdf

离散数学左孝凌pdf教材

计算机考研历年真题 pdf

如何期末高分通过离散数学

哈工大计算机考研历年分数线

历年考研自动化复试面试试题汇集 pan

江苏科技大学计算机科学与技术专业，考研复试科目历年真题

北京邮电计算机考研csdn

江苏科技大学计算机科学与技术专业，考研复试科目数据库系统概论历年真题

百度之星题集 pdf

2024年计算机考研院校推荐

历年北京联合大学软件工程复试题目

长安大学研究生数据库复试历年考题

哈工大计算机考研笔记

中南大学计算机专业考研历年分数线

如何具体提高计算机考研专业课的成绩，给出10条建议

严蔚敏《数据结构(c语言版)超级全的资料 加历年各个学校的考研真题

南京理工大学计算机网络复习资料

会员权益专享

最新资源

离散数学课后习题答案耿素云，曲婉玲计算机专业

严蔚敏《数据结构(c语言版)超级全的资料加历年各个学校的考研真题