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

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

1、设A={1，2，3}上的关系如下，有传递性的有（ ）。
A．{<1，2 >，<2，1 >，<1，3>，<3，1>}
B．{<1 ,3>，<3 ,1>}
C．{<1，2 >，<2, 3 >，<1，1>}
D．{<1 ,2 >，<3，2 >}
2、下列语句是命题的是（ ）
A． 明年中秋节的晚上是晴天 B．
C． 请保持安静 D．我正在说谎
3、下列哪个命题是假命题（　　　　）．
A．如果2+2=4，则太阳从东方升起；
B．如果2+2=4，则太阳从西方升起；
C．如果2+24，则太阳从东方升起；
D．如果2+24，则太阳从西方升起．
4、设是正实数集，Ｒ是实数集，ｆ：ｆ，则ｆ是（　 　）．
A．是入射不是满射　　　　　 　 B．是满射不是入射
C．既非入射也非满射　　　　　　 D．是双射
5、下列等价式不成立的是（　）．
A． B．
C． D．．
6、n阶完全图的边数为（ ）。
A．n(n-1)/2； B．n-1； C．n+1； D．2n(n-1)
7、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（　　）．
A．ｎ－ｍ－１；　B．ｎ－ｍ＋１；　　C．ｍ－ｎ＋１；　D．ｍ－ｎ－１．
8、设为整数集，：，，则是（　　）．
A．是入射不是满射
B．是满射不是入射
C．既非入射也非满射　
D．是双射．
9、设是一个复合映射。下列哪个命题是假命题（　　）．
A．若是满射，则是满射 B．若是入射，则是入射
C．若是双射，则和都是双射 D．若和都是双射，则是双射
10、设，则有（ ）。
A．{{1,2}} ； B．{1,2 } ； C．{1} ； D．{2}
11、下列各图是欧拉图的是（　 　　）．

A B C D
12、在下述公式中是重言式为（ ）
A．¬ B．
C． D．ØP®（QÙR）
13、设，下列二元关系为到的函数的是( )
A． B．
C． D．
14、设为无向图，=7，=23，则G一定是（ ）。
A．完全图； B．树； C．简单图； D．多重图
15、下列各式哪个是错的（ ）？
A.Æ Í Æ ; B.Æ Î {Æ} ; C.Æ Ì Æ ; D.Æ Î {Æ , {Æ}
16、令:是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为（　）．
A． B．
C． D．
17、下面四组数能构成无向图的度数列的有（ ）。
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
18、无向图是欧拉图，当且仅当（　 　　）．
A．连通且所有结点的度数为偶数；　　B．的所有结点的度数为偶数；
C．连通且所有结点的度数为奇数；　 D．的所有结点的度数为奇数．
19、下列关系中能构成函数的是（ ）。
A．； B．；
C．； D．
20、下列哪个谓词公式与 等价？（ ）。
A． B． C． D．
二、填空题（20小题，每空1分，共20分）
得分

1、在偏序集中，，≤是上的整除关系，则的极大元是
2、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=
3、命题公式的逆反式是 。
4、设，则A的幂集是 ．
5、设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。
6、写出下表中所定义的命题联结词

0 0
0 1
1 0
1 1
0
0
0
1
7、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为 ．
8、在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是
9、在下图所给的偏序集中，集合的上确界是 。

10、设A为任一集合，则 ．
11、在下图所给的偏序集中，集合的下确界是 。

12、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有 个度为1的结点．
13、命题公式¬（PQ）的主析取范式为
14、完全图K5 的边数是 。
15、设是到的函数，若 ，则称为双射。
16、设上的关系的关系图如下，从关系图可知具有的性质是 ．

17、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。
18、设是图的邻接矩阵，，则图中由到长度为的路径的条数为 ．
19、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。
20、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
三、简答题（4小题，每小题6分，共24分）
得分

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

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

3、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。

子 集
上确界
下确界

4、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示．要求设计一个最经济的煤气管道路线，并求所需的总费用．
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
3.5
5
4
5
2
6
3
4
5
3
1

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

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

2、符号化下列命题并推证其结论．
所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数．）．

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

第 8 页 共 20 页
1、D
2、A
3、B
4、D
5、B
6、A
7、C
8、C
9、C
10、A

11、B
12、B
13、A
14、D
15、C
16、C
17、B
18、A
19、B
20、D

二、填空题（20小题，每空1分，共20分）

1、4，5，6
2、
3、
4、
5、 或
6、∧
7、或
8、6
9、
10、
11、
12、14
13、（P∧┐Q）∨（┐P∧Q）
14、10
15、既是单射又是满射
16、反自反性、反对称性和传递性
17、
18、
19、出度为0的结点
20、

三、简答题（4小题，每小题6分，共24分）
1、解：
1） 邻接矩阵为：
（2分）
2） （2分）
由到长度为2的路有1条，由到长度为4的路有3条。(1分）
3）的可达性矩阵为 （1分）
2、
（根据树的完整程度酌情减分）
3、答：
子 集
上 确 界
下 确 界

无

无
4、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：
（4分）
因此如图铺设煤气管道所需费用最小，最小费用为：
　2＋2＋2＋2＋2＋2＋2+3＋3+4+1＝25（万元）． （2分）
四、证明题（2小题，每小题8分，共16分）
1、证明：①假设存在，使得，则
且，那么且，由此得，即f是入射。 （3分）
②任取，均有，使得，从而是满射。（3分）
综合①②知是双射。 （2分）
2、该命题符号化为：（2分）
证: (1) P (6) T(2) I （1分）
(2) ES (1) （1分） (7) T(4),(5) I （1分）
(3) P (8) T(6),(7) I （1分）
(4) US (3) （1分）(9) EG(8) （1分）
(5) T(2) I

一、单选题（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．的所有结点的度数为奇数．
6、设，则有（ ）。
A．{{1,2}} ； B．{1,2 } ； C．{1} ； D．{2}
7、下列关系中能构成函数的是（ ）。
A．； B．；
C．； D．
8、下面四组数能构成无向图的度数列的有（ ）。
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
9、设是正实数集，Ｒ是实数集，ｆ：ｆ，则ｆ是（　 　）．
A．是入射不是满射　　　　　 　 B．是满射不是入射
C．既非入射也非满射　　　　　　 D．是双射
10、下列哪个谓词公式与 等价？（ ）。
A． B． C． D．
11、设为整数集，：，，则是（　　）．
A．是入射不是满射
B．是满射不是入射
C．既非入射也非满射　
D．是双射．
12、下列语句是命题的是（ ）
A． 明年中秋节的晚上是晴天 B．
C． 请保持安静 D．我正在说谎
13、设A={1，2，3}上的关系如下，有传递性的有（ ）。
A．{<1，2 >，<2，1 >，<1，3>，<3，1>}
B．{<1 ,3>，<3 ,1>}
C．{<1，2 >，<2, 3 >，<1，1>}
D．{<1 ,2 >，<3，2 >}
14、下列各图是欧拉图的是（　 　　）．

A B C D
15、下列哪个命题是假命题（　　　　）．
A．如果2+2=4，则太阳从东方升起；
B．如果2+2=4，则太阳从西方升起；
C．如果2+24，则太阳从东方升起；
D．如果2+24，则太阳从西方升起．
16、n阶完全图的边数为（ ）。
A．n(n-1)/2； B．n-1； C．n+1； D．2n(n-1)
17、在下述公式中是重言式为（ ）
A．¬ B．
C． D．ØP®（QÙR）
18、设是一个复合映射。下列哪个命题是假命题（　　）．
A．若是满射，则是满射 B．若是入射，则是入射
C．若是双射，则和都是双射 D．若和都是双射，则是双射
19、下列各式哪个是错的（ ）？
A.Æ Í Æ ; B.Æ Î {Æ} ; C.Æ Ì Æ ; D.Æ Î {Æ , {Æ}
20、设为无向图，=7，=23，则G一定是（ ）。
A．完全图； B．树； C．简单图； D．多重图
二、填空题（20小题，每空1分，共20分）
得分

1、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。
2、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为 ．
3、在下图所给的偏序集中，集合的上确界是 。

4、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=
5、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
6、设是图的邻接矩阵，，则图中由到长度为的路径的条数为 ．
7、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有 个度为1的结点．
8、写出下表中所定义的命题联结词

0 0
0 1
1 0
1 1
0
0
0
1
9、完全图K5 的边数是 。
10、命题公式¬（PQ）的主析取范式为
11、设A为任一集合，则 ．
12、在偏序集中，，≤是上的整除关系，则的极大元是
13、设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。
14、在下图所给的偏序集中，集合的下确界是 。

15、命题公式的逆反式是 。
16、设，则A的幂集是 ．
17、设上的关系的关系图如下，从关系图可知具有的性质是 ．

18、设是到的函数，若 ，则称为双射。
19、在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是
20、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中 称为树叶。
三、简答题（4小题，每小题6分，共24分）
得分

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

2、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示．要求设计一个最经济的煤气管道路线，并求所需的总费用．
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
3.5
5
4
5
2
6
3
4
5
3
1

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

4、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。

子 集
上确界
下确界

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

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

2、符号化下列命题并推证其结论．
所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数．）．

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

第 20 页 共 20 页
1、B
2、C
3、A
4、C
5、A
6、A
7、B
8、B
9、D
10、D
11、C
12、A
13、D
14、B
15、B
16、A
17、B
18、C
19、C
20、D

二、填空题（20小题，每空1分，共20分）

1、
2、或
3、
4、
5、
6、
7、14
8、∧
9、10
10、（P∧┐Q）∨（┐P∧Q）
11、
12、4，5，6
13、 或
14、
15、
16、
17、反自反性、反对称性和传递性
18、既是单射又是满射
19、6
20、出度为0的结点

三、简答题（4小题，每小题6分，共24分）
1、解：邻接矩阵为：
（2分）
3） （2分）
由到长度为2的路有1条，由到长度为4的路有3条。(1分）
3）的可达性矩阵为 （1分）
2、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：
（4分）
因此如图铺设煤气管道所需费用最小，最小费用为：
　2＋2＋2＋2＋2＋2＋2+3＋3+4+1＝25（万元）． （2分）
3、（根据树的完整程度酌情减分）
4、答：
子 集
上 确 界
下 确 界

无

无

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