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

一、单选题（20小题，每小题2分，共40分）得分1、若集合的基数为4，则集合上的共有（ ）个不同的等价关系。A15 B16 C14 D122、集合上的关系为一个偏序关系，当且仅当具有（ ）。A自反性、对称性和传递性 B自反性、反对称性和传递性C反自反性、对称性和传递性 D反自反性、反对称性和传递3、设是集合上的二元运算，称元素为关于运算“”的幺元，如果（ ）。A，且对任意元素，使 B，且对任意元素，使 C，且存在元素，使 D，且存在元素，使 4、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）。A B C D 5、设，为集合上的等价关系，的对应于的划分是，则=( )。A B C D6、设是一个格，对，下列命题中不一定为真的是（ ）。A B C D7、n阶完全图的边数为（ ）。An(n-1)/2 Bn-1 Cn+1 D2n(n-1)8、下面推理中，正确的是（ ）。A（1）(x) (F(x) G(x) P（2）F(a) G(b) USB（1）F(a) G(b) P（2）($x) (F(x) G(x) EGC（1）F (x ) G(b) P（2）($x) (F(x) G(x) EGD（1）(x) (F(x) G(x) P（2）F(y)G(y) US9、下面四组数能构成无向图的度数列的有（ ）。A2,3,4,5,6,7 B1,2,2,3,4 C2,1,1,1,2 D3,3,5,6,010、设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（ ）个三角形。A100 B200 C300 D60011、下面所示的偏序集中，哪一个是格？（ ）。A B C D12、下列各图是欧拉图的是（ ）。A B C D13、下面哪个偏序集构成有界格（ ）。A； B，其中为整除关系；C； D；其中，为的幂集14、下面哈斯图所示的有界格中，哪个不是有补格（）。15、无向图是欧拉图，当且仅当（ ）。A连通且所有结点的度数为偶数；B的所有结点的度数为偶数；C连通且所有结点的度数为奇数； D的所有结点的度数为奇数16、在下述公式中是重言式为（ ）A B C DP（QR）17、设，以下哪一个关系是从到的满射 ( )。ABC 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，bN，ab=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、A2、B3、A4、C5、C6、D7、A8、D9、B10、B11、B12、B13、D14、A15、A16、B17、B18、C19、C20、C二、填空题（20小题，每空1分，共20分）1、最大下界和最小上界2、123、14、5、6、集合A中的每一个元素都存在补元7、矛盾式8、满射9、910、出度为0的结点11、或（PQ）（P Q）（PQ）12、1613、2E14、15、,16、 17、18、S19、 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 BC D2、下列各式哪个是错的（ ）？ A B C D , 3、设是集合上的二元运算，称元素为关于运算“”的幺元，如果（ ）。A，且对任意元素，使 B，且对任意元素，使 C，且存在元素，使 D，且存在元素，使 4、设G=V，E为（，）连通图，则要确定的一棵生成树，必删去的边数是（）。A B C D 5、在下述公式中是重言式为（ ）。A B C DP（QR）6、无向图是欧拉图，当且仅当（ ）。A连通且所有结点的度数为偶数B的所有结点的度数为偶数C连通且所有结点的度数为奇数 D的所有结点的度数为奇数7、下面推理中，正确的是（ ）。A（1）(x) (F(x) G(x) P（2）F(a) G(b) USB（1）F(a) G(b) P（2）($x) (F(x) G(x) EGC（1）F (x ) G(b) P（2）($x) (F(x) G(x) EGD（1）(x) (F(x) G(x) P（2）F(y)G(y) US8、下面所示的偏序集中，哪一个是格？（ ）。A B C D9、下面哈斯图所示的有界格中，哪个不是有补格（）。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上有（ ）个三角形。A100 B200 C300 D60013、下列符号串是合式公式的是（ ）A、 B、 C、 D、 14、集合上的关系为一个偏序关系，当且仅当具有（ ）。A自反性、对称性和传递性 B自反性、反对称性和传递性C反自反性、对称性和传递性 D反自反性、反对称性和传递15、设，为集合上的等价关系，的对应于的划分是，则=( )。A B C D16、n阶完全图的边数为（ ）。An(n-1)/2 Bn-1 Cn+1 D2n(n-1)17、下列各图是欧拉图的是（ ）。A B C D18、若集合的基数为4，则集合上的共有（ ）个不同的等价关系。A15 B16 C14 D1219、设，以下哪一个关系是从到的满射 ( )。ABC D 20、下面四组数能构成无向图的度数列的有（ ）。A2,3,4,5,6,7 B1,2,2,3,4 C2,1,1,1,2 D3,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，bN，ab=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、D2、C3、A4、C5、B6、A7、D8、B9、A10、D11、C12、B13、C14、B15、C16、A17、B18、A19、B20、B二、填空题（20小题，每空1分，共20分）1、S2、集合A中的每一个元素都存在补元3、4、最大下界和最小上界5、166、或（PQ）（P Q）（PQ）7、8、19、 10、 N，中不存在幺元11、12、,13、满射14、1215、16、2E17、918、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 页