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

4星 · 超过85%的资源需积分: 45 681 浏览量更新于2023-06-05 评论 8 收藏 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页未读，继续阅读

m0_51406875

2021-03-18

我下载了，麻烦告诉我一下怎么打开呢？在下载里面点进去，又回到了这个页面

longdeliu

粉丝: 4
资源: 3

会员权益专享

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

评论4

会员权益专享

最新资源

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

评论4

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

数学建模历年赛题的分析qin\数学建模历年赛题的分析

1994-2008年考研英语历年阅读题短文.pdf

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

历年计算机一级MSoffice考试试题精选及答案(1).doc

北京航空航天大学计算机研究生考试必备（一）.pdf

历年全国数学建模试题及解法归纳.doc

1986-2020年考研英语二历年真题及答案详解.pdf

apmcm数据分析数字建模历年卷

历年noip普及组初赛试题

历年全国数学建模试题及解法归纳.pdf

pyecharts+snapshot绘制甘肃历年学生数据的散点图代码

电气自动化专业历年试题一览表

自考 电子技术基础（三）历年考题及答案

华为历年校招机试真题 java

python蓝桥杯历年真题

如何根据历年数据自动生成文章

理光sc代码+解决方法(历年经验).doc

会员权益专享

最新资源

自考电子技术基础（三）历年考题及答案