离散数学AB卷2套期末考试卷带答案-模拟试卷-测试卷-期末考试题.doc

一、单选题（20小题，每小题2分，共40分）
得分

1、若集合的基数为4，则集合上的共有（ ）个不同的等价关系。
A．15 　 B．16 　　C．14 　 D．12
2、集合上的关系为一个偏序关系，当且仅当具有（ ）。
A．自反性、对称性和传递性　 B．自反性、反对称性和传递性
C．反自反性、对称性和传递性 D．反自反性、反对称性和传递
3、设是集合上的二元运算，称元素为关于运算“”的幺元，如果（　 ）。
A．，且对任意元素，使
B．，且对任意元素，使
C．，且存在元素，使
D．，且存在元素，使
4、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（　　）。
A．ｎ－ｍ－１ 　B．ｎ－ｍ＋１　 　C．ｍ－ｎ＋１ 　D．ｍ－ｎ－１
5、设，为集合上的等价关系，的对应于的划分是，则=( )。
A． B．
C． D．
6、设是一个格，对，下列命题中不一定为真的是（ ）。
A． B．
C． D．
7、n阶完全图的边数为（ ）。
A．n(n-1)/2 B．n-1 C．n+1 D．2n(n-1)
8、下面推理中，正确的是（ ）。
A．（1）("x) (F(x) ÚG(x)) P
（2）F(a) ÚG(b) US
B．（1）F(a) ®G(b) P
（2）($x) (F(x) ®G(x)) EG
C．（1）F (x ) ®G(b) P
（2）($x) (F(x) ®G(x)) EG
D．（1）("x) (F(x) ®G(x)) P
（2）F(y)®G(y) US
9、下面四组数能构成无向图的度数列的有（ ）。
A．2,3,4,5,6,7 B．1,2,2,3,4 C．2,1,1,1,2 D．3,3,5,6,0
10、设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（ ）个三角形。
A．100 B．200 C．300 D．600
11、下面所示的偏序集中，哪一个是格？（ ）。

A B C D
12、下列各图是欧拉图的是（　 　　）。

A． B． C． D．
13、下面哪个偏序集构成有界格（ ）。
A．；　　　　 B．／，其中／为整除关系；
C．；　　　　 D．；其中，为的幂集．
14、下面哈斯图所示的有界格中，哪个不是有补格（　　　）。

15、无向图是欧拉图，当且仅当（　 　　）。
A．连通且所有结点的度数为偶数；　　B．的所有结点的度数为偶数；
C．连通且所有结点的度数为奇数；　 D．的所有结点的度数为奇数．
16、在下述公式中是重言式为（ ）
A．¬ B．
C． D．ØP®（QÙR）
17、设，以下哪一个关系是从到的满射 ( )。
A．
B．
C．
D．
18、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）
假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。
A．("x) (H（x）Ù ( $y)( (C（y）Ù F(x,y)))
B．("x) (H（x）® ( $y)( (C（y）® F(x,y)))
C．("x) (H（x）® ( $y)( (C（y）Ù F(x,y)))
D．( $y) ("x) (H（x）® ( (C（y）Ù F(x,y)))
19、下列各式哪个是错的（ ）？
A．Æ Í Æ ; B．Æ Î {Æ} ; C．Æ Ì Æ ; D．Æ Î {Æ , {Æ}
20、下列符号串是合式公式的是（ ）
A． B． C． D．
二、填空题（20小题，每空1分，共20分）
得分

1、设〈A，≤〉是一个偏序集，如果A中任意两个元素都有 ，则称〈A，≤〉是一个格。
2、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的上确界是 。
3、完全图K5 的连通分支数是 。
4、在下图所给的偏序集中，集合的下确界是 。

5、设，则 A的幂集= 。
6、设〈A , ≤〉是一个有界格，如果 ，则称此格为有补格。
7、谓词公式Ø（F（x,y）ÚR（x,y））Ù R（x,y）是 （重言式，矛盾式，可满足式）。
8、设是到的函数，如果，则称为 。
9、如果有一台计算机，它有一条加法指令，可计算四个数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。
10、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。
11、命题公式（ØP ®Q）®（Ø QÚ P）的主析取范式为 。
12、公式 的真值表中共有 种真值指派。
13、在任何图中，= 。
14、设S为非空集合，为集合S的幂集。代数系统〈〉中，关于“”的零元为 。
15、设集合，R和S均为A上的二元关系，且，则_ 。
16、设是集合上的二元关系，则= 。
17、设表示“天下雨”， 表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为 。
18、设S为非空集合，为集合S的幂集。代数系统〈〉中，关于“”的零元为 。
19、设N为自然数集合，在N上定义运算☆：对任意a，b∈N，a☆b=a+b+3，则〈 N，☆〉不是一个群，因为 。
20、设R是实数集合， ，，且，则 。
三、简答题（4小题，每小题6分，共24分）
得分

1、对有向图，通过邻接矩阵解下列问题：
（1）从到长度为4的路有几条？
（2）中长度为3的回路有几条？

2、以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树。

3、设={2，3，6，12，24，36},”/”为的整除关系，
(1)．说明〈，／〉是否为偏序集，若是，画出其哈斯图；
(2)．说明〈，／〉是否为格？为什么？

4、设Z是整数集，是Z上的模3同余关系，即，试根据等价关系决定Z的一个划分。

四、证明题（2小题，每小题8分，共16分）
得分

1、设为 ，证明：是双射。

2、符号化下列命题并推证其结论。
任何人如果违反交通规则，就要被处罚；总有些人违反了交通规则。因此有些人被处罚。（使用全总个体域，设：是人，：违反交通规则，：被处罚）。

一、单选题（20小题，每小题2分，共40分）
1、A
2、B
3、A
4、C
5、C
6、D
7、A
8、D
9、B
10、B
11、B
12、B
13、D
14、A
15、A
16、B
17、B
18、C
19、C
20、C
二、填空题（20小题，每空1分，共20分）
1、最大下界和最小上界
2、12
3、1
4、
5、
6、集合A中的每一个元素都存在补元
7、矛盾式
8、满射
9、9
10、出度为0的结点
11、或（PÙQ）Ú（PÙØ Q）Ú（ØPÙØQ）
12、16
13、2│E│
14、
15、{<1,3>,<3,1>}
16、
17、
18、S
19、〈 N，☆〉中不存在幺元
20、
三、简答题（4小题，每小题6分，共24分）
1、解：
，（1分）（1分）
所以，（1）从到长度为4的路有4条。它们是：；；；。（2分）
（2）中长度为3的回路有3条。它们是：；；。（2分）
2、（根据树的完整程度酌情减分）
3、解：(1)．〈，／〉是偏序集． 其哈斯图为：
（4分）
(2)．〈，／〉不是格．因为2和3无下确界或24和36 无上确界 （2分）
4、答案：由决定的Z的划分为：， 其中：

四、证明题（2小题，每小题8分，共16分）
1、证明：
1）先证明是入射（3分）
对任意的则有，从而有，故是入射。
2) 再证明是满射（3分）
对任意的从而是满射。
综合（1）、（2）知是双射。（2分）
2、命题符号化为： （2分）
证明：
(1) P
(2) ES(1) （1分）
(3) T(2) I （1分）
(4) P
(5) US(4) （1分）
(6) T(2)(5) I （1分）
(7) T(3)(6) I （1分）
(8) EG(7) （1分）

一、单选题（20小题，每小题2分，共40分）
得分

1、设是一个格，对，下列命题中不一定为真的是（ ）。
A． B．
C． D．
2、下列各式哪个是错的（ ）？
A．Æ Í Æ B．Æ Î {Æ} C．Æ Ì Æ D．Æ Î {Æ , {Æ}
3、设是集合上的二元运算，称元素为关于运算“”的幺元，如果（　 ）。
A．，且对任意元素，使
B．，且对任意元素，使
C．，且存在元素，使
D．，且存在元素，使
4、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（　　）。
A．ｎ－ｍ－１ 　B．ｎ－ｍ＋１ 　　C．ｍ－ｎ＋１ 　D．ｍ－ｎ－１
5、在下述公式中是重言式为（ ）。
A．¬ B．
C． D．ØP®（QÙR）
6、无向图是欧拉图，当且仅当（　 　　）。
A．连通且所有结点的度数为偶数　　B．的所有结点的度数为偶数
C．连通且所有结点的度数为奇数　 D．的所有结点的度数为奇数
7、下面推理中，正确的是（ ）。
A．（1）("x) (F(x) ÚG(x)) P
（2）F(a) ÚG(b) US
B．（1）F(a) ®G(b) P
（2）($x) (F(x) ®G(x)) EG
C．（1）F (x ) ®G(b) P
（2）($x) (F(x) ®G(x)) EG
D．（1）("x) (F(x) ®G(x)) P
（2）F(y)®G(y) US
8、下面所示的偏序集中，哪一个是格？（ ）。

A B C D
9、下面哈斯图所示的有界格中，哪个不是有补格（　　　）。

10、下面哪个偏序集构成有界格（ ）。
A． 　　　　 B．／，其中／为整除关系
C． 　　　　 D．；其中，为的幂集
11、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）。
假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。
A．("x) (H（x）Ù ( $y)( (C（y）Ù F(x,y)))
B．("x) (H（x）® ( $y)( (C（y）® F(x,y)))
C．("x) (H（x）® ( $y)( (C（y）Ù F(x,y)))
D．( $y) ("x) (H（x）® ( (C（y）Ù F(x,y)))
12、设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（ ）个三角形。
A．100 B．200 C．300 D．600
13、下列符号串是合式公式的是（ ）
A、 B、 C、 D、
14、集合上的关系为一个偏序关系，当且仅当具有（ ）。
A．自反性、对称性和传递性　 B．自反性、反对称性和传递性
C．反自反性、对称性和传递性 D．反自反性、反对称性和传递
15、设，为集合上的等价关系，的对应于的划分是，则=( )。
A． B．
C． D．
16、n阶完全图的边数为（ ）。
A．n(n-1)/2 B．n-1 C．n+1 D．2n(n-1)
17、下列各图是欧拉图的是（　 　　）。

A B C D
18、若集合的基数为4，则集合上的共有（ ）个不同的等价关系。
A．15 　 B．16 　　C．14 　 D．12
19、设，以下哪一个关系是从到的满射 ( )。
A．
B．
C．
D．
20、下面四组数能构成无向图的度数列的有（ ）。
A．2,3,4,5,6,7 B．1,2,2,3,4 C．2,1,1,1,2 D．3,3,5,6,0
二、填空题（20小题，每空1分，共20分）
得分

1、设S为非空集合，为集合S的幂集。代数系统〈〉中，关于“”的零元为 。
2、设〈A , ≤〉是一个有界格，如果 ，则称此格为有补格。
3、设R是实数集合， ，，且，则 。
4、设〈A，≤〉是一个偏序集，如果A中任意两个元素都有 ，则称〈A，≤〉是一个格。
5、公式 的真值表中共有 种真值指派。
6、命题公式（ØP ®Q）®（Ø QÚ P）的主析取范式为 。
7、在下图所给的偏序集中，集合的下确界是 。

8、完全图K5 的连通分支数是 。
9、设是集合上的二元关系，则= 。
10、设N为自然数集合，在N上定义运算☆：对任意a，b∈N，a☆b=a+b+3，则〈 N，☆〉不是一个群，因为 。
11、设表示“天下雨”， 表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为 。
12、设集合，R和S均为A上的二元关系，且，则_ 。
13、设是到的函数，如果，则称为 。
14、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的上确界是 。
15、设S为非空集合，为集合S的幂集。代数系统〈〉中，关于“”的零元为 。
16、在任何图中，= 。
17、如果有一台计算机，它有一条加法指令，可计算四个数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。
18、设，则 A的幂集= 。
19、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。
20、谓词公式Ø（F（x,y）ÚR（x,y））Ù R（x,y）是 （重言式，矛盾式，可满足式）。
三、简答题（4小题，每小题6分，共24分）
得分

1、设Z是整数集，是Z上的模3同余关系，即，试根据等价关系决定Z的一个划分 。

2、以给定权2， 4， 5， 8， 13， 15， 18， 25构造一棵最优二叉树。

3、对有向图，通过邻接矩阵解下列问题：
（1）从到长度为4的路有几条？
（2）中长度为3的回路有几条？

4、设={2，3，6，12，24，36},”/”为的整除关系，
(1)．说明〈，／〉是否为偏序集，若是，画出其哈斯图；
(2)．说明〈，／〉是否为格？为什么？

四、证明题（2小题，每小题8分，共16分）
得分

1、符号化下列命题并推证其结论．
任何人如果违反交通规则，就要被处罚；总有些人违反了交通规则。因此有些人被处罚。（使用全总个体域，设：是人，：违反交通规则，：被处罚）

2、设为 ，证明：是双射。

一、单选题（20小题，每小题2分，共40分）
1、D
2、C
3、A
4、C
5、B
6、A
7、D
8、B
9、A
10、D
11、C
12、B
13、C
14、B
15、C
16、A
17、B
18、A
19、B
20、B
二、填空题（20小题，每空1分，共20分）
1、S
2、集合A中的每一个元素都存在补元
3、
4、最大下界和最小上界
5、16
6、或（PÙQ）Ú（PÙØ Q）Ú（ØPÙØQ）
7、
8、1
9、
10、〈 N，☆〉中不存在幺元
11、
12、{<1,3>,<3,1>}
13、满射
14、12
15、
16、2│E│
17、9
18、
19、出度为0的结点
20、矛盾式
三、简答题（4小题，每小题6分，共24分）
1、答案：由决定的Z的划分为：， 其中：

2、（根据树的完整程度酌情减分）
3、解：
，（1分）（1分）
所以，（1）从到长度为4的路有4条。它们是：；；；。（2分）
（2）中长度为3的回路有3条。它们是：；；。（2分）
4、解：(1)．〈，／〉是偏序集． 其哈斯图为：
（4分）
(2)．〈，／〉不是格．因为2和3无下确界或24和36 无上确界 （2分）
四、证明题（2小题，每小题8分，共16分）
1、命题符号化为： （2分）
证明：
(1) P
(2) ES(1) （1分）
(3) T(2) I （1分）
(4) P
(5) US(4) （1分）
(6) T(2)(5) I （1分）
(7) T(3)(6) I （1分）
(8) EG(7) （1分）
2、证明：
1）先证明是入射（3分）
对任意的则有，从而有，故是入射。
2) 再证明是满射（3分）
对任意的从而是满射。
综合（1）、（2）知是双射。（2分）

2 A 第 22 页 共 22 页