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

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

1、下列蕴含式不成立的是（ ）.
A． B．
C． D．.
2、集合上的关系为一个偏序关系，当且仅当具有（ ）。
A．自反性、对称性和传递性　 B．自反性、反对称性和传递性
C．反自反性、对称性和传递性 D．反自反性、反对称性和传递
3、设是一个复合映射。下列哪个命题是假命题（　　）．
A．若是满射，则是满射 B．若是入射，则是入射
C．若是双射，则和都是双射 D．若和都是双射，则是双射
4、设={1，2，3}，上的二元关系=，则的对称闭包是（　 ）．
A． B． 　 C． D．
5、下列各图是欧拉图的是（ ）．

6、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（　　）．
A．ｎ－ｍ－１；　B．ｎ－ｍ＋１；　　C．ｍ－ｎ＋１；　D．ｍ－ｎ－１．
7、前提条件：P®（Q ®S），Q, PÚØR, 则它的有效推论为（ ）
A．S B． R ® S C．P D．R ® Q
8、命题公式 中极小项的个数为（ ）
A．0 B．1 C．2 D．3
9、谓词演算中，是的有效结论，其理论依据是（　　　）．
A．全称指定规则（US） 　 C．全称推广规则（UG）
B．存在指定规则（ES）　 D．存在推广规则（EG）．
10、设，集合上的等价关系所确定的的划分的是{{a},{ b, c }} ，则=( )
A． {< a, a>,,,,}
B．{< a ,b>,,,}
C．{< a ,b>,,}
D．{< a, a>,< a ,b>,,,>,}
11、设N为自然数集，：N N，则是( )．
A．是入射不是满射 B．既非入射也非满射
C．是满射不是入射 D．是双射
12、下面给出的四个图中，哪个不是汉密尔顿图（ ）．

13、下列哪个命题是假命题（　　　　）．
A．如果2+2=4，则太阳从东方升起；
B．如果2+2=4，则太阳从西方升起；
C．如果2+24，则太阳从东方升起；
D．如果2+24，则太阳从西方升起．
14、具有个结点的完全图是欧拉图，则为( )。
A．偶数； B．奇数； C．9； D．10．

15、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）
假设：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)))
16、n阶完全图结点v的度数为（ ）。
A．n； B．n-1； C．n+1； D．2(n-1)
17、下面哪个图是强连通的（ 　）．

18、设是图的邻接矩阵，，则为（　）．
A．结点的度数； B．结点的度数；
C．结点的入度； D．图中由到长度为的路径的条数．
19、设有向图，其中，，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
20、，其中，为集合的对称差运算，则方程的解为（ ）。
A．； B．； C．； D．
二、填空题（20小题，每空1分，共20分）
得分

1、在任何图中，其奇数度结点的个数必为 。
2、完全图K5 的边数是 。
3、无向图中有10条边，且每个结点的度数均为4，则结点数是 ．
4、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树根。
5、设，上的二元关系=，则具有 性。
6、在下图所给的偏序集中，集合的下确界是 。

7、设是A到B的函数，若使是B到A的函数，必须满足
8、设P，Q 的真值为0，R，S的真值为1，则
的真值= 。
9、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是
10、以为子集的最少元素的集合为 ．
11、设R是集合A上的二元关系，则r(R) =
12、设R是实数集合， ，，且，则
13、给定命题公式：P Ú（ØP®（QÚ(Ø Q®R)）则它的成假值为 。
14集合上的关系，则= 。
15、由前提（"x）（F（x）® H（x））, （"x）ØH（x）可得出的有效结论是

16、写出下表中各列所定义的命题联结词

0 0
0 1
1 0
1 1
0
0
0
1

17、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
18、设, 则= ．其中 表示集合的幂集．
19、谓词公式Ø（F（x,y）ÚR（x,y））Ù R（x,y）是 （重言式，矛盾式，可满足式）
20、设是到的函数，若 ，则称为双射。
三、简答题（4小题，每小题6分，共24分）
得分

1、对有向图求解下列问题：
1）写出邻接矩阵；
2）中由到长度为2和4的路有几条？
3）求出的可达性矩阵。

2、以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。

3、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。

4、设={1,2,3,5,6,10,15,30} ， “／” 为集合上的整除关系。〈，／〉是否为偏序集? 若是，画出其哈斯图。

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

1、符号化下列命题并推证其结论．
任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x喜欢音乐，S(x)：x喜欢体育，Ａ(x)：ｘ喜欢美术．个体域是人类集合）

2、设函数，，证明是双射的。

一、单选题（20小题，每小题2分，共40分）
1
2
3
4
5
6
7
8
9
10
A
B
C
C
B
C
B
D
A
A
11
12
13
14
15
16
17
18
19
20
B
D
B
B
C
B
A
D
C
A

二、填空题（20小题，每空1分，共20分）
1、偶数
2、10
3、5
4、入度为0的结点
5、对称
6、
7、f是双射
8、1
9、2,3
10、
11、
12、
13、000
14、
15、（"x）ØF（x）
16、∧
17、8
18、8
19、矛盾式
20、既是单射又是满射
三、简答题（4小题，每小题6分，共24分）
1、解：
1） 邻接矩阵为：
（2分）
2） （2分）
由到长度为2的路有1条，由到长度为4的路有2条。(1分）
3）的可达性矩阵为 （1分）

2、
（根据树的完整程度酌情减分）
3、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边：
（4分）
C ( A , B ) , C ( B , C ) , C ( D , E ) , C ( B , E )
C ( T ) = 3+6+2+4 = 15 ( 千万RMB ) （2分）
4、答：（1）〈，／〉是偏序集。（2分）
（2）其哈斯图为：（4分）

四、证明题（2小题，每小题8分，共16分）
1、
（1）该命题符号化为：（（ｘ）（M（x）→S（x））∧（ｘ）（S（x）∨A（x））∧（x） A（x））→（（x） M（x））（2分）
（2）（6分）证：（1）（x） A（x） P
（2） A（a） ES（1）
（3）（ｘ）（S（x）∨A（x）） P
（4）S（a）∨A（a） US（3）
（5）S（a） T（2）（4）I
（6）（ｘ）（M（x）→S（x）） P
（7）M（a）→S（a） US（6）
（8）S（a）→ M（a） T（7）E
（9） M（a） T（5）（8）I
（10）（x） M（x） EG（9）
2、
证明：①假设存在，使得，则
且，那么且，由此得，即f是入射。（3分）②任取，均有，使得
，从而是满射。（3分）
综合①②知是双射。 （2分）

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

1、设，集合上的等价关系所确定的的划分的是{{a},{ b, c }} ，则=( )
A． {< a, a>,,,,}
B．{< a ,b>,,,}
C．{< a ,b>,,}
D．{< a, a>,< a ,b>,,,,}
2、设是一个复合映射。下列哪个命题是假命题（　　）．
A．若是满射，则是满射 B．若是入射，则是入射
C．若是双射，则和都是双射 D．若和都是双射，则是双射
3、下面给出的四个图中，哪个不是汉密尔顿图（ ）．

4、下列蕴含式不成立的是（ ）.
A． B．
C． D．.
5、下面哪个图是强连通的（ 　）．

6、具有个结点的完全图是欧拉图，则为( )。
A．偶数； B．奇数； C．9； D．10．
7、下列各图是欧拉图的是（ ）．

8、，其中，为集合的对称差运算，则方程的解为（ ）。
A．； B．； C．； D．
9、前提条件：P®（Q ®S），Q, PÚØR, 则它的有效推论为（ ）
A．S B． R ® S C．P D．R ® Q
10、设有向图，其中，，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
11、下列哪个命题是假命题（　　　　）．
A．如果2+2=4，则太阳从东方升起；
B．如果2+2=4，则太阳从西方升起；
C．如果2+24，则太阳从东方升起；
D．如果2+24，则太阳从西方升起．
12、设={1，2，3}，上的二元关系=，则的对称闭包是（　 ）．
A． B． 　 C． D．
13、设是图的邻接矩阵，，则为（　）．
A．结点的度数； B．结点的度数；
C．结点的入度； D．图中由到长度为的路径的条数．
14、命题公式 中极小项的个数为（ ）
A．0 B．1 C．2 D．3
15、集合上的关系为一个偏序关系，当且仅当具有（ ）。
A．自反性、对称性和传递性　 B．自反性、反对称性和传递性
C．反自反性、对称性和传递性 D．反自反性、反对称性和传递
16、设N为自然数集，：N N，则是( )．
A．是入射不是满射 B．既非入射也非满射
C．是满射不是入射 D．是双射
17、命题“所有的马都比某些牛跑得快”的符号化公式为（ ）
假设：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)))
18、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（　　）．
A．ｎ－ｍ－１；　B．ｎ－ｍ＋１；　　C．ｍ－ｎ＋１；　D．ｍ－ｎ－１．
19、谓词演算中，是的有效结论，其理论依据是（　　　）．
A．全称指定规则（US） 　 C．全称推广规则（UG）
B．存在指定规则（ES）　 D．存在推广规则（EG）．
20、n阶完全图结点v的度数为（ ）。
A．n； B．n-1； C．n+1； D．2(n-1)
二、填空题（20小题，每空1分，共20分）
得分

1、设是到的函数，若 ，则称为双射。
2、谓词公式Ø（F（x,y）ÚR（x,y））Ù R（x,y）是 （重言式，矛盾式，可满足式）
3、设, 则= ．其中 表示集合的幂集．
4、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
5、写出下表中各列所定义的命题联结词

0 0
0 1
1 0
1 1
0
0
0
1

6、在下图所给的偏序集中，集合的下确界是 。

7、设是A到B的函数，若使是B到A的函数，必须满足
8、设P，Q 的真值为0，R，S的真值为1，则
的真值= 。
9、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是
10、以为子集的最少元素的集合为 ．
11、设R是集合A上的二元关系，则r(R) =
12、设R是实数集合， ，，且，则
13、给定命题公式：P Ú（ØP®（QÚ(Ø Q®R)）则它的成假值为 。
14、集合上的关系，则= 。
15、由前提（"x）（F（x）® H（x））, （"x）ØH（x）可得出的有效结论是

16、设，上的二元关系=，则具有 性。
17、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树根。
18、无向图中有10条边，且每个结点的度数均为4，则结点数是 ．
19、完全图K5 的边数是 。
20、在任何图中，其奇数度结点的个数必为 。
三、简答题（4小题，每小题6分，共24分）
得分

1、对有向图求解下列问题：
1）写出邻接矩阵；
2）中由到长度为2和4的路有几条？
3）求出的可达性矩阵。

2、以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。

3、设={1,23,5,6,10,15,30} ， “／” 为集合上的整除关系。〈，／〉是否为偏序集? 若是，画出其哈斯图。

4、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。

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

1、设函数，，证明是双射的。

2、符号化下列命题并推证其结论．
任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x喜欢音乐，S(x)：x喜欢体育，Ａ(x)：ｘ喜欢美术．个体域是人类集合）

一、单选题（20小题，每小题2分，共40分）
1
2
3
4
5
6
7
8
9
10
A
C
D
A
A
B
B
A
B
C
11
12
13
14
15
16
17
18
19
20
B
C
D
D
B
B
C
C
A
B

二、填空题（20小题，每空1分，共20分）
1、既是单射又是满射
2、矛盾式
3、8
4、8
5、∧
6、
7、f是双射
8、1
9、2,3
10、
11、
12、
13、000
14、
15、（"x）ØF（x）
16、对称
17、入度为0的结点
18、5
19、10
20、偶数
三、简答题（4小题，每小题6分，共24分）
1、解：
3） 邻接矩阵为：
（2分）
4） （2分）
由到长度为2的路有1条，由到长度为4的路有2条。(1分）
3）的可达性矩阵为 （1分）

2、
（根据树的完整程度酌情减分）
3、答：（1）〈，／〉是偏序集。（2分）
（2）其哈斯图为：（4分）

4、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边：
（4分）
C ( A , B ) , C ( B , C ) , C ( D , E ) , C ( B , E )
C ( T ) = 3+6+2+4 = 15 ( 千万RMB ) （2分）

四、证明题（2小题，每小题8分，共16分）
1、证明：①假设存在，使得，则
且，那么且，由此得，即f是入射。（3分）②任取，均有，使得
，从而是满射。（3分）
综合①②知是双射。 （2分）
2、

（1）该命题符号化为：（（ｘ）（M（x）→S（x））∧（ｘ）（S（x）∨A（x））∧（x） A（x）→（（x） M（x））（2分）
（2）（6分）证：（1）（x） A（x） P
（2） A（a） ES（1）
（3）（ｘ）（S（x）∨A（x）） P
（4）S（a）∨A（a） US（3）
（5）S（a） T（2）（4）I
（6）（ｘ）（M（x）→S（x）） P
（7）M（a）→S（a） US（6）
（8）S（a）→ M（a） T（7）E
（9） M（a） T（5）（8）I
（10）（x） M（x） EG（9）

1 A 第 21 页 共 21 页