一、单项选择题（本大题共40分，共 20 小题，每小题 2 分）
1. 设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是 （ ） A. 自反、对称、传递的 B. 自反、对称、反对称的 C. 对称、反对称、传递的 D. 只有对称性
2. 在下列命题中，为真的命题是（ ）
A. 汉密顿图一定是欧拉图
B. 无向完全图都是欧拉图
C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出
D. 有割点的连通图是汉密顿图
3. 设P：我去踢球，Q：明天下雨，命题“如果我踢球，当且仅当明天不下雨”的符号化表示为（ ）。
A. P→Q
B. Q→P
C.
D. PQ
4. 设A为一集合，（P(A),）为有补格，P(A)中每个元素的补元（ ）。
A. 存在且唯一
B. 不存在
C. 存在且不唯一
D. 可能存在
5. 下图哪个能一笔画？（ ）
A.
B.
C.
D.
6. 若X是Y的子集，则一定有 （ ）。 A. X不属于Y B. X∈Y C. X真包含于Y D. X∩Y=X
7. 若集合A的基数|A|=10，则其幂集的基数为（ ）
A. 1024
B. 100
C. 20
D. 12
8. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（ ）
A. 2是偶数或-3不是负数
B. 2是奇数或-3不是负数
C. 2不是偶数且-3不是负数
D. 2是奇数且-3不是负数
9. 对于下面某个偏序集的哈斯图，其中集合 {a,b,c,e} 的最大元是（ ）
A. c
B.
d
C.
e
D.
无
10. 设G是n个顶点的无向简单图，则下列说法不正确的是（）。 A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇数度顶点 D. 若G中任意一对顶点的度数之和大于等于n-1,则G中有汉密顿路
11. 在谓词演算中，P(a)是∀xP(x)的有效结论，其理论根据是（ ）。
A. 全称指定规则（US）
B. 全称推广规则（UG）
C. 存在指定规则（ES）
D. 存在推广规则（EG）
12. 设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数（ ）
A. 7
B. 8
C. 9
D. 14
13. 函数的复合满足（ ）
A. 交换律
B. 结合律
C. 幂等律
D. 分配律
14. 以下叙述正确的是（ ）
A. 代数系统能构成半群，其中运算o定义为：aob=|a-b|。
B. 对于自然数集合，运算a*b=min{a,b}是可结合的。
C. 代数系统是半群，其中运算“-“表示普通的减法运算。
D. 以上的叙述均不对。
15. 以下叙述正确的是（ ）
A. {b, c, a, aa, ac, abb}是前缀码。
B. 在有界格中，若有一个元素有补元，则补元必唯一。
C. 在有向图中，结点间的可达关系是等价关系。
D. 连通图的最小生成树不一定是唯一的。
16. 以下叙述正确的是：（ ）。
A. 的幂集没有任何元素。
B. 整数集上关于加法运算的幺元是0。
C. 整数集上的任何元素x关于乘法运算均有逆元1/x。
D. 整数集上的关于乘法运算的幺元是0。
17. 命题公式 P Q R 的对偶式为？（ ）
A. P （ Q R ）
B. P （ Q R ）
C. P （ Q R ）
D. P （ Q R ）
18. Q (P Q) 主合取范式为（ ）
A. P Q
B. P Q
C. (P Q) (P Q) ( P Q)
D. (P Q) (P Q) ( P Q)
19. 设Z+为正整数集合，S为正偶数集合，则 A. 自同构 B. 同构 C. 自同态 D. 非同构 20. 设G=为无环的无向图，|V|=6,|E|=16,则G是（ ） A. 完全图 B. 零图 C. 简单图 D. 多重图 二、多项选择题（本大题共30分，共 10 小题，每小题 3 分） 1. 相容关系需要满足的特性为：（ ） A. 对称性 B. 传递性 C. 自反性 D. 反对称性 2. 以下关系中哪些是 A B 的函数，其中 A={a,b,c} B={1,2,3}( ) A. { B. { C. { D. { 3. 在下列命题中，为真的命题是（ ） A. 具有6个结点的无向完全图共有15条边。 B. 无向完全图都是欧拉图。 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出。 D. 有割点的连通图是汉密顿图。 4. 以下叙述正确的是（）。 A. 若A＝{φ,1,2}，则A的幂集有8个元素 B. 朋友关系是等价关系 C. 具有5个顶点的完全图，需要删去6条边才能得到树 D. 集合B = {{a},3,4,1}，E为全集，则φ{{a}}BE 5. 设Z是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？（ ） A. f(x)=2x B. f(x)=1000x C. f(x)=|x| D. f(x)=0 6. 以下表达方式正确的是：（ ） A. 小明打开箱子并拿出一件衣服。 设P：小明打开箱子； Q：小明拿出一件衣服。原命题表示为：PQ B. 如果骑自行车，我就没法按时到校。 设P：我骑自行车； Q：我按时到校；原命题可表示为：P→Q C. 我打开门，走了进来。 设M：我打开门； N：我走进来。 原命题为：M→N D. 小红和小华是好朋友。 设H：小红是好朋友； J：小华是好朋友；原命题为：HJ 7. 设偏序集<,≤> 的哈斯图如下所示，若A的子集B = {2,3,4},则元素为B的极大元为( )。 A. 5 B. 6 C. 3 D. 4 8. 对于下列各式，是永真式的有（ ）。 A. (P∧(P→Q))→Q B. P→(P∨Q) C. Q→(P∧Q) D. ((P∧(P(Q))→Q E. (P→Q)→Q 9. 设集合A={1,2,3,…10}，下面定义的哪种运算关于集合A是封闭的（ ） A. x*y=max{x,y} B. x*y=min{x,y} C. x*y=GCD(x,y) 即x,y的最大公约数 D. x*y=LCM(x,y) 即x,y的最小公倍数 10. 设T是一棵具有n个结点m条边（n2）的树，则T（ ）。 A. 连通 B. 包含有环 C. m=n-1 D. 至少有两个度为1的结点 三、判断题（本大题共30分，共 10 小题，每小题 3 分） 1. {1，01，001，000}是前缀码。（ ） 2. 若f：NN, f(x)=x2+2，则f是满射函数。（ ） 3. 能一笔画出的图一定是欧拉图。（ ） 4. 为矛盾式。（ ） 5. 交换群必是循环群。（ ） 6. 任何图中必有偶数个度数为奇数的结点。（ ） 7. 设S={0,1},S是关于普通的加法和乘法运算，则S上的加法与乘法运算满足封闭性、结合性。（ ） 8. 为重言式。（ ） 9. 设是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元，则e。（ ） 10. 设e为无向连通图G中的一条边，e在G的任何生成树中，则e是桥。（ ） 答案： 一、单项选择题（40分，共 20 题，每小题 2 分） 1. C 2. C 3. C 4. A 5. D 6. D 7. A 8. C 9. D 10. B 11. A 12. B 13. B 14. B 15. D 16. B 17. D 18. C 19. B 20. D 二、多项选择题（30分，共 10 题，每小题 3 分） 1. AC 2. BC 3. AC 4. ACD 5. ABD 6. BC 7. CD 8. ABD 9. ABC 10. ACD 三、判断题（30分，共 10 题，每小题 3 分） 1. √ 2. × 3. × 4. √ 5. × 6. √ 7. × 8. √ 9. √ 10. √ 下载本文
