当前位置：文档之家 › 离散数学试卷八试题与答案

离散数学试卷八试题与答案

  • 格式：doc
  • 大小：109.00 KB
  • 文档页数：6

试卷八试卷与答案
一、 填空 15% （每小题 3分）

1、 n阶完全图Kn的边数为。
2、 右图的邻接矩阵A= 。

3、 图的对偶图为。
4、 完全二叉树中，叶数为nt，则边数m= 。
5、 设< {a,b,c}, * >为代数系统，* 运算如下：
则它的幺元为；零元为；
a、b、c的逆元分别为。

二、 选择 15% （每小题 3分）

1、 图相对于完全图的补图为（）。

2、 对图G 则)(),(),(GGGk分别为（）。
A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。
3、 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树
叶，则T中有（）片树叶。
A、3； B、4； C、5； D、6

* a b c
a a b c
b b a c
c c c c
4、 设是代数系统，其中+，·为普通的加法和乘法，则A=（）时+，·>是整环。

A、},2|{Znnxx； B、},12|{Znnxx；
C、},0|{Zxxx且； D、},,5|{4Rbabaxx。
5、 设A={1，2，…，10 }，则下面定义的运算*关于A封闭的有（）。

A、 x*y=max(x ,y)； B、x*y=质数p的个数使得ypx；
C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公约数)；
D、x*y=lcm(x ,y) （lcm(x ,y) 表示x和y的最小公倍数）。

三、 证明 45%

1、设G是（n,m）简单二部图，则42nm。（8分）
2、设G为具有n个结点的简单图，且)2)(1(21nnm则G是连通图。（8分）
3、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图。（14分）
4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算
和乘法运算。如下：
+ 0 1 · 0 1
0 0 1 0 0 0
1 1 0 1 0 1

证明它是一个环，并且是一个域。（15分）
四、 生成树及应用 10%
1、（10分）如下图所示的赋权图表示某七个城市
721
,,,vvv
及预先测算出它们之间的一些直接通信线路

造价，试给出一个设计方案，使得各城市之间既能够通信
而且总造价最小。
2、（10分）构造H、A、P、N、E、W、R、对应的前缀
码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR的编码信息。
五、 5%
对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写
“Y”或“N”。
Max Min +
可结合性
可交换性
存在幺元
存在零元

答案：
一、 填空 15%（每小题3分）

1、)1(21nn；2、0110001011001010；3、；4、)1(2tn；5、a，
c，a、b、没有
二、 选择 15%（每小题 3分）
题目
1 2 3 4 5

答案
A A C D

A，

C

三、 证明 45%
1、 （8分）：设G=（V，E），
nnnnYnXYXV2121,,,则

对完全二部图有4)2()(2211211121nnnnnnnnnnnm
当21nn时，完全二部图),(mn的边数m有最大值42n。
故对任意简单二部图),(mn有42nm。
2、 （8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设

G1和G2的顶点数分别为n1和n2，显然nnn21。
11112121nnnnnn
4 / 6

2)2)(1(2)2)(1(2)1(2
)1(212211nnnnnnnnn
m

与假设矛盾。所以G连通。

3、（14分）（1）当n=11时，11KGG11K边数5521011'm条，因而必
有G或G的边数大于等于28，不妨设G的边数28m，设G有k个连通分支，则G
中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则

1,1kinm
ii


,mmnnkiikii11,11


kiikiikknnmm11
11)1(28

矛盾）

下面用反证法证明G为非平面图。
假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3 。于是G

的每个面至少由g (3g)条边围成，由点、边、面数的关系)1(2knggm，
得：

2723113))11(11(3))1(11(133)111(228kkggm
而2728矛盾，所以G为非平面图。
（2）当n>11时，考虑G的具有11个顶点的子图'G，则'G或'G必为非平面图。
如果'G为非平面图，则G为非平面图。
如果'G为非平面图，则G为非平面图。
4、 （15分）
1）[{0，1}，+，·]是环
①[{0，1}，+]是交换群
乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。
群：（0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
（0+1）+0=0+（1+0）=1 ；（0+1）+1=0+（1+1）=0；
（1+1）+1=1+（1+1）=0 ……
结合律成立。
幺：幺元为0。
逆：0，1逆元均为其本身。所以，<{0，1}，+>是Abel群。
②<{0，1}，·>是半群
乘：由“·”运算表知封闭
群： (0·0)·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）=1；
（0·1）·0=0·（1·0）=1 ；（0·1）·1=0·（1·1）=0；
（1·1）·1=1·（1·1）=0 ；…
③·对+的分配律

对}1,0{,yx
Ⅰ 0·（x+y）=0=0+0=(0·x)+(0·y)
Ⅱ 1·（x+y）
当x=y (x+y)=0 则

)1()1()11()11()01()01(1100001)(1yxyx
当yx（1yx）则
)1()1()11()01()01()11(1001111)(1yxyx
所以}1,0{,,zyx均有)()()(yzxzyxz
同理可证：)()()(zyzxzyx
所以·对+ 是可分配的。
由①②③得，<{0，1}，+，·>是环。
（2）<{0，1}，+，·>是域
因为<{0，1}，+，·>是有限环，故只需证明是整环即可。
①乘交环：由乘法运算表的对称性知，乘法可交换。
②含幺环：乘法的幺元是1
③无零因子：1·1=1≠0
因此[{0，1}，+，·]是整环，故它是域。

四、树的应用 20%
1、（10分）解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：
树权C(T)=23+1+4+9+3+17=57即为总造价
五、（10分）
由二叉树知

H、A、P、Y、N、E、W、R对应
的编码分别为
000、001、010、011、100、101、110、111。
显然{000，001，010，011，100，101，110，111}为前缀码。
英文短语HAPPY NEW YEAR 的编码信息为
000 001 010 010 011 100 101 001 001 101 001 111
六、5%

Max Min +
可结合性 Y Y Y
可交换性
Y Y Y

存在幺元
N N Y

存在零元 N N N

合集下载

离散考试试题及答案

离散考试试题及答案

离散考试试题及答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念不是布尔代数的基本运算？A. 与B. 或C. 非D. 模答案：D2. 集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A3. 命题逻辑中，下列哪个符号表示“蕴含”关系？A. ∧B. ∨C. →D. ↔答案：C4. 关系R在集合A上是自反的，意味着什么？A. 对于所有a∈A，(a, a)∈RB. 对于所有a∈A，(a, a)∉RC. 对于所有a∈A，(a, b)∈RD. 对于所有a∈A，(a, b)∉R答案：A二、填空题（每题5分，共20分）1. 一个集合的基数是集合中元素的________。

答案：数量2. 在有向图中，如果存在一条从顶点u到顶点v的路径，则称顶点v 是顶点u的________。

答案：可达的3. 一个图是连通的，当且仅当图中任意两个顶点都是________。

答案：连通的4. 在命题逻辑中，一个命题的否定是________。

答案：它的对立命题三、简答题（每题10分，共30分）1. 请解释什么是图的哈密顿回路。

答案：哈密顿回路是一个图中的闭合回路，它恰好访问图中的每个顶点一次。

2. 描述一下什么是二元关系，并给出一个例子。

答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。

例如，小于关系是数字集合上的一个二元关系。

3. 什么是图的生成树？答案：图的生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树，即它是连通的且没有环。

四、计算题（每题15分，共30分）1. 给定一个集合A={1,2,3,4,5}，计算它的幂集。

答案：幂集P(A)={∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5},{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}, A}。

长江大学08级离散试卷A答案

长江大学08级离散试卷A答案

一 判断题(每小题1分，共 15分)1、 若图G 是自对偶的，则e=2v-2 (T)2、 “离散数学是很有趣的一门课程”，这句话是命题。

（T ）3、 函数的复合既能交换也能结合。

（F ）4、 如果A ∨C ⇔B ∨C ，则A ⇔B （F ）5、 设G=<V,E>为连通图，且e ∈E,则当e 是G 的割边时，e 才在G 的每棵生成树中。

（T ）6、 )()(R Q P Q ∨↔→是合式公式。

（T ）7、 任何阶数为4的群都是阿贝尔群。

（T ）8、 设G 是简单连通图，且有v 个结点，e 条边，若G 是平面图，则e ≤3v-6。

（T ）9、 一个循环群的生成元是唯一的。

（F ）10、有任意集合A 、B ，则f(A ∩B)⊆f(A)∩f(B)且f(A)∩f(B)⊆f(A ∩B)。

（F ） 11、)()()()())()()((x B x x A x x B x A x ∃∧∃⇔∧∃（F ） 12、对任意集合A ，B ，C ，如果A ∈B 以及B ⊆C ，则A ⊆C 。

（F ） 13、整数集上的同余类是对整数集的一个划分。

（T ） 14、有限半群中存在等幂元。

（T ） 15、 设<A,*>是一个代数系统，且|A|>1，若该代数系统中存在幺元和零元，则幺元与零元相等。

（F ）二 、选择题(每小题2分，共 22分)1、 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，则该树有（D ）片树叶。

B. 7C. 82、图1中v 1到v 4 长度为2的路有（A ）条A. 1B. 2C. 3v 4v 1图13、设A={1，2，3，4}，B={a ，b ，c ，d}，f 定义为：{<1,a>,<2,b>,<3,c>,<4,d>}，则f （D ）。

A.不是函数B.仅为入射函数C.仅为满射函数D.是双射函数4、设F(x)：x 是乌鸦；G(x,y)：x 与y 一般黑，则“天下乌鸦一般黑”可以符号化为：(A)A.)),()()()()((y x G y F x F y x →∧∀∀B.)),()()()()((y x G y F x F y x →∧∃∀C.)),()()()()((y x G y F x F y x →∧∃∃D.)),()()()()((y x G y F x F y x →∧∀∃5、给定下列谓词公式，则是矛盾式的公式为（C ）A.))()()((x P x P x ⌝→⌝∀B. )()()()(x P x x P x ∃→∀C.)()())()(()()((y Q y y Q y x P x ∀∧∀→∀⌝D.),())((),())((y x P y x y x P y x ∀∃→∃∀6、设有下列四个集合，偏序关系为整除，则是全序关系的为（D ）A. {3,5,15}B.{1,2,3,6,12}C.{3,4,12}D.{3,9,27,54}7、设集合P={x1，x2，x3，x4，x5}上的偏序关系如图2所示，则下列说法中正确的是（A ）A 、P 的最大元素为x1 ，无最小元素，极小元素为x4，x5 ，极大元为素x1B 、P 无最大元素，也无最小元素，极小元素为x4，x5 ，极大元为素x1C 、P 的最大元素为x1 ，无最小元素，也无极小元素 ，极大元为素x1D 、P 的最大元素为x1 ，最小元素为x4，x5，极小元素为x4，x5 ，极大元为素x1x 1x 4x 5x 2图28、集合A={a ，b ，c}，A 上的关系R={（a ，b ），（a ，c ），（b ，a ），（b ，c ），（c ，a ），（c ，b ），（c ，c ）}，则R 具有关系的（B ）性质。

离散数学考试试题及答案

离散数学考试试题及答案

离散数学考试试题及答案一、选择题1. 在一个聚会中，有9名男生和11名女生。

问这些学生中，至少有一个女朋友的学生人数的奇偶性是怎样的？答案：奇数2. 设A、B、C是三个命题。

已知命题A为真，命题B为假，命题C为真，则下列命题中，一定为假的是：A) A → (B ∨ C)B) (A → C) ∨ BC) (A ∧ B) ∨ CD) A ↔ (B ∧ C)答案：D) A ↔ (B ∧ C)3. 设集合A={x | -3 < x ≤ 2}，集合B={y | -4 ≤ y < 3}，则下列集合中，既是A的子集又是B的子集的集合是：A) {-2, -1, 0, 1, 2}B) {-3, -2, -1, 0, 1, 2}C) {-4, -3, -2, -1, 0, 1, 2}D) {-4, -3, -2, -1, 0, 1, 2, 3}答案：B) {-3, -2, -1, 0, 1, 2}4. 设A={1, 2, 3, 4}，B={3, 4, 5, 6}，C={4, 5, 6, 7}，则(A ∪ B) ∩ C等于：A) {1, 2, 3, 4, 5, 6}B) {3, 4, 5, 6}C) {4}D) {4, 5, 6}答案：C) {4}二、填空题1. 一个完全图有9条边，则该完全图的顶点数为________。

答案：52. 若一个集合有n个元素，则该集合的幂集的元素个数为________。

答案：2^n3. 设a是整数，若3a-5能被4整除，则a的一个可能的取值是________。

答案：24. 设n为正整数，若C(n, 3) = 1，则n的值为________。

答案：4三、解答题1. 证明：设A、B、C为三个集合，要证明A ∩ (B ∪ C) = (A ∩ B)∪ (A ∩ C)。

解答：对于任意元素x，若x ∈ A ∩ (B ∪ C)，则x ∈ A 且 x ∈ (B∪ C)。

根据集合的交和并的定义，可得x ∈ A 且 (x ∈ B 或 x ∈ C)。

(完整word版)离散数学试卷及参考答案()

(完整word版)离散数学试卷及参考答案()

一、填空题:(每空1分，本大题共15分）1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2．命题公式)(Q P →⌝的主析取范式为 ，主合取范式的编码表示为 。

3．设E 为全集， ,称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ，～Φ= 。

4．设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =,}},,{{4c b a S =}}{},{},{{5c b a S =，}},{},{{6c a a S =则A 的覆盖有 ，A 的划分有 。

5．设S 是非空有限集，代数系统＜（S ），，＞中，（S)对的幺元为 ，零元为 。

（S ）对的幺元为 ，零元为 .6．若>=<E V G ,为汉密尔顿图，则对于结点集V 的每个非空子集S ，均有W(G-S) S 成立，其中W （G —S)是 。

二、单项选择题：（每小题1分，本大题共10分)1．下面命题公式（ )不是重言式。

A 、)(Q P Q ∨→；B 、P Q P →∧)(；C 、)()(Q P Q P ∨⌝∧⌝∧⌝;D 、)()(Q P Q P ∨⌝↔→。

2．命题“没有不犯错误的人”符号化为( ）。

设x x M ：)(是人，x x P ：)(犯错误。

A 、))()((x P x M x ∧∀; B 、)))()(((x P x M x ⌝→∃⌝；C 、)))()(((x P x M x ∧∃⌝；D 、)))()(((x P x M x ⌝∧∃⌝。

3．设}{Φ=A ，B =((A ））,下列各式中哪个是错误的（ ）。

A 、B ⊆Φ; B 、B ⊆Φ}{，C 、B ∈Φ}}{{；D 、⊆ΦΦ}}{,{(A ）。

4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）.A 、),min(b a b a =*;B 、b a b a 2+=*;C 、3++=*b a b a ；D 、)3(mod ,b a b a =*。