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

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

1、，其中，为集合的对称差运算，则方程的解为（ ）。
A．； B．； C．； D．
2、给定命题公式：（ØPÚ Q）Ù（P® R），与之等价的是（ ）
A．P®（Ø QÙR） B．P®（QÚR）
C．P®（QÙR） D．ØP®（QÙR）
3、设为实数集，函数：，，则是（　 　　）．
A．是入射不是满射 B．是满射不是入射
C．既非入射也非满射　 D．是双射
4、设N为自然数集，：N N，则是( )．
A．是入射不是满射 B．既非入射也非满射
C．是满射不是入射 D．是双射
5、下图中既不是欧拉图，也不是汉密尔顿图的图是（ ）。

A B C D
6、一个无向树中有7条边，则它结点数为( )。
A. 5； B.6； C.7； D. 8．
7、设是集合上的任意函数，下列哪个命题是真命题（　　）．
A． B．
C． 　 D．
8、下列各图是欧拉图的是（ ）．

9、设，以下哪一个关系是从到的满射（　 　）．
A．　　　　　 　
B．
C．
D．
10、设和是集合上的任意两个关系，则下列命题为真的是（　　）．
A．若和是自反的，则也是自反的
B．若和是非自反的，则也是非自反的
C．若和是对称的，则也是对称的
D．若和是传递的，则也是传递的
11、给定命题公式如下：（ØP ®Q）®（Ø P ÙQ）该命题公式的成真赋值个数（ ）
A．0 B．1 C．2 D．3
12、设，则有（ ）个元素。
A．3； B．6； C．7； D．8
13、谓词公式中量词（）辖域是（ ）。
A． B．
C． D．
14、下面哪个图是强连通的（ 　）．

15、下列等价公式正确的是（ ）。
A．； B．；
C．； D．．
16、下面四组数能构成无向简单图的度数列的有（ ）。
A．2,2,2,2,2,2； B．1,2,3,4,5,5； C．1,2,3,4,5,6； D．2,2,3,4,5,6
17、无向图中有16条边，且每个结点的度数均为2，则结点数是（　 　　）．
A．8 B．16 C．4 D．32
18、设A={1，2，3}，关系R是A上的二元关系，且R={<1，2 >}，则关系R所具有的性质是（ ）
A．自反性，反对称性，可传递性 B．反自反性，反对称性，可传递性
C．自反性，对称性，可传递性 D．反自反性，反对称性
19、谓词演算中，是的有效结论，其理论依据是（　　　）．
A．全称指定规则（US） 　 C．全称推广规则（UG）
B．存在指定规则（ES）　 D．存在推广规则（EG）．
20、由前提：("x) (P（x）®（Q（x）®ØR（x）），("x) (P（x）®（R（x）Ú S（x）））,
( $ x) (P（x）ÙØS（x））, 则它的有效推论为（ ）
A．("x) (P（x）®ØQ（x）） B．("x) (P（x）ÙØQ（x））
C．($x) (P（x）ÙØQ（x）） D．($x) (P（x）ÙQ（x））
二、填空题（20小题，每空1分，共20分）
得分

1、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为 ．
2、设表示“我将去书店”， 表示“我有时间”，则命题“我将去书店，仅当我有时间”符号化为 。
3、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是
4、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G) = ，则的入度为 　 。
5、设,则的双射共有 ．
6、设，则= 。其中表示集合Ａ的幂集。
7、设R是实数集合， ，，且，则
8、命题公式¬（PQ）的主合取范式为
9、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
10、设，上的二元关系=，则具有
___________________性。
11、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，则Ｒ具有____________________________
12、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。
13、设A为任一集合，则 ．
14、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
15、对谓词公式（（"x）P（x）Ú（$y）Q（y））®（"x）R（x）中约束变元应用变换规则所得到的前束范式是
16、命题公式¬（PQ）的主析取范式为
17、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=
18、设是到的函数，当为双射时，是到的函数，=
19、无向图中有10条边，且每个结点的度数均为4，则结点数是 ．
20、无向图G具有生成树，当且仅当___________________。
三、简答题（4小题，每小题6分，共24分）
得分

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

2、下图给出的赋权图表示七个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。

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

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

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

1、证明函数，是双射。

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

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

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

1、或
2、
3、无
4、3
5、6
6、
7、
8、(P∨Q)∧(┐P∨┐Q)
9、
10、对称
11、传递性、反对称性
12、
13、
14、8
15、（$x）（" y）（"z）（P（x）ÚQ（y））®R（z））
16、
17、
18、
19、5
20、图G连通

三、简答题（4小题，每小题6分，共24分）
1、答：（1）〈，／〉是偏序集。（2分）
（2）其哈斯图为：（4分）

2、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：
（4分）
因此如图架线使得各城市间能够通讯且总造价最小，最小造价费用为：
　1＋3＋4＋8＋9＋23＝48． （2分）
3、解：邻接矩阵为：
（2分）
1） （2分）
由到长度为2的路有1条，由到长度为4的路有2条。(1分）
3）的可达性矩阵为 （1分）
4、（根据树的完整程度酌情减分）
四、证明题（2小题，每小题8分，共16分）
1、证明：①任取， 且， 则

所以，即f是入射。 （3分）
②对任意的，都存在，使得，从而是满射。 （3分）
综合①②知是双射。 （2分）
2、该命题符号化为： （2分）
证明:
(1) P
(2) ES (1) （1分）
(3) P
(4) US (3) （1分）
(5) T(2)(4) I （1分）
(6) P
(7) US (6) （1分）
(8) T(5),(7) I （1分）
(9) EG(8) （1分）
一、单选题（20小题，每小题2分，共40分）
得分

1、给定命题公式如下：（ØP ®Q）®（Ø P ÙQ）该命题公式的成真赋值个数（ ）
A．0 B．1 C．2 D．3
2、下面哪个图是强连通的（ 　）．

3、无向图中有16条边，且每个结点的度数均为2，则结点数是（　 　　）．
A．8 B．16 C．4 D．32
4、设，以下哪一个关系是从到的满射（　 　）．
A．　　　　　 　
B．
C．
D．
5、给定命题公式：（ØPÚ Q）Ù（P® R），与之等价的是（ ）
A．P®（Ø QÙR） B．P®（QÚR）
C．P®（QÙR） D．ØP®（QÙR）
6、设，则有（ ）个元素。
A．3； B．6； C．7； D．8
7、下列各图是欧拉图的是（ ）．

8、，其中，为集合的对称差运算，则方程的解为（ ）。
A．； B．； C．； D．
9、下面四组数能构成无向简单图的度数列的有（ ）。
A．2,2,2,2,2,2； B．1,2,3,4,5,5； C．1,2,3,4,5,6； D．2,2,3,4,5,6
10、设和是集合上的任意两个关系，则下列命题为真的是（　　）．
A．若和是自反的，则也是自反的
B．若和是非自反的，则也是非自反的
C．若和是对称的，则也是对称的
D．若和是传递的，则也是传递的
11、设N为自然数集，：N N，则是( )．
A．是入射不是满射 B．既非入射也非满射
C．是满射不是入射 D．是双射
12、设为实数集，函数：，，则是（　 　　）．
A．是入射不是满射 B．是满射不是入射
C．既非入射也非满射　 D．是双射
13、设A={1，2，3}，关系R是A上的二元关系，且R={<1，2 >}，则关系R所具有的性质是（ ）
A．自反性，反对称性，可传递性 B．反自反性，反对称性，可传递性
C．自反性，对称性，可传递性 D．反自反性，反对称性
14、谓词演算中，是的有效结论，其理论依据是（　　　）．
A．全称指定规则（US） 　 C．全称推广规则（UG）
B．存在指定规则（ES）　 D．存在推广规则（EG）．
15、谓词公式中量词（）辖域是（ ）。
A． B．
C． D．
16、由前提：("x) (P（x）®（Q（x）®ØR（x）），("x) (P（x）®（R（x）Ú S（x）））,
( $ x) (P（x）ÙØS（x））, 则它的有效推论为（ ）
A．("x) (P（x）®ØQ（x）） B．("x) (P（x）ÙØQ（x））
C．($x) (P（x）ÙØQ（x）） D．($x) (P（x）ÙQ（x））
17、下图中既不是欧拉图，也不是汉密尔顿图的图是（ ）。

A B C D
18、下列等价公式正确的是（ ）。
A．； B．；
C．； D．．
19、设是集合上的任意函数，下列哪个命题是真命题（　　）．
A． B．
C． 　 D．
20、一个无向树中有7条边，则它结点数为( )。
A. 5； B.6； C.7； D. 8．
二、填空题（20小题，每空1分，共20分）
得分

1、命题公式¬（PQ）的主析取范式为
2、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是
3、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
4、命题公式¬（PQ）的主合取范式为
5、设，上的二元关系=，则具有
___________________性。
6、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G) = ，则的入度为 　 。
7、无向图G具有生成树，当且仅当___________________。
8、设，则= 。其中表示集合Ａ的幂集。
9、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
10、无向图中有10条边，且每个结点的度数均为4，则结点数是 ．
11、设R是实数集合， ，，且，则
12、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=
13、对谓词公式（（"x）P（x）Ú（$y）Q（y））®（"x）R（x）中约束变元应用变换规则所得到的前束范式是
14、设表示“我将去书店”， 表示“我有时间”，则命题“我将去书店，仅当我有时间”符号化为 。
15、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，则Ｒ具有______________________________
16、设A为任一集合，则 ．
17、设是到的函数，当为双射时，是到的函数，=
18、设,则的双射共有 ．
19、设表示“我将取得好成绩”， 表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为 。
20、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为 ．
三、简答题（4小题，每小题6分，共24分）
得分

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

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

3、下图给出的赋权图表示七个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。

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

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

1、证明函数，是双射。

2、任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。
（设：喜欢步行，：喜欢乘汽车，：骑自行车．个体域为所有人的集合）

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

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

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

1、（P∧┐Q）∨（┐P∧Q）
2、无
3、8
4、(P∨Q)∧(┐P∨┐Q)
5、对称
6、3
7、图G连通
8、
9、
10、5
11、
12、
13、（$x）（" y）（"z）（P（x）ÚQ（y））®R（z））
14、
15、传递性、反对称性
16、
17、
18、6
19、
20、或

三、简答题（4小题，每小题6分，共24分）
1、（根据树的完整程度酌情减分）
2、解：邻接矩阵为：
（2分）
2） （2分）
由到长度为2的路有1条，由到长度为4的路有2条。(1分）
3）的可达性矩阵为 （1分）
3、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：
（4分）
因此如图架线使得各城市间能够通讯且总造价最小，最小造价费用为：
　1＋3＋4＋8＋9＋23＝48． （2分）
4、答：（1）〈，／〉是偏序集。（2分）
（2）其哈斯图为：（4分）

四、证明题（2小题，每小题8分，共16分）
1、证明：①任取， 且， 则

所以，即f是入射。 （3分）
②对任意的，都存在，使得，从而是满射。 （3分）
综合①②知是双射。 （2分）
2、该命题符号化为： （2分）
证明:
(1) P
(2) ES (1) （1分）
(3) P
(4) US (3) （1分）
(5) T(2)(4) I （1分）
(6) P
(7) US (6) （1分）
(8) T(5),(7) I （1分）
(9) EG(8) （1分）

2、任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。
（设：喜欢步行，：喜欢乘汽车，：骑自行车．个体域为所有人的集合）