模拟试题(一)
一、 单项选择题
在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。
1．给定命题公式如下：)()(p q q p ∨⌝→→⌝ 成真赋值的个数为（ ）。
A ．1 Ｂ．2 Ｃ．3 Ｄ．4
2. 设个体域D={a,b}，公式()()x xS x xP ∃∧∀在A 中消去量词后应为（ ）
A ．()()x S x P ∧
B ．()()())()(b S a S b P a P ∨∧∧
C ．()()b S a P ∧
D ．()())()(b S a S b P a P ∨∧∧
3．若R 和S 是集合A 上的两个关系，则下述结论正确的是（ ）。
A ．若R 和S 是自反的，则R ⋂S 也是自反的
B ．若R 和S 是对称的，则R ︒S 也是对称的
C ．若R 和S 是反对称的，则R ︒S 也是反对成的
D ．若R 和S 是传递的，则R ⋃S 也是传递的
4．设全集U={1,2,3,...,20},A,B,C 是其子集，其}4|{<=x x A ，
}100|{},076|{22<==--=x x C x x x B 则=⋂⋂C B A ~~~（ ）
。 A ．{16,17,18,19,20} B ．{1,2,3,4,5}
C ．{10,11,12,13,14,15}
D ．{1,2,3,4,5,6,7}
5．下面偏序集构成有界格的是（ ）。
A ． Ｂ． Ｃ．<{2,3,4,6,12},|> Ｄ．
6．全体自然数所组成的集合的最小元为（ ）。
A ．负数 Ｂ．最小的正数 Ｃ．0 Ｄ．1
7．对任何a ∈A ，形成的A 上的等价关系R 的等价类[a]R 为（ ）。
A ．空集 Ｂ．非空集 Ｃ．空集也可以为非空集 Ｄ．{x}x ∈A}
8．设S=Q ⨯Q ，其中Q 为有理数集合，定义S 上的二元运算“*”，∀,∈S ，有>+>=<<>是（ ）。
A ．可交换的 Ｂ．可结合的
Ｃ．既是可交换的，又是可结合的 Ｄ．不是可交换的，也不是可结合的
9. 设有向图D=的邻接矩阵为⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎣⎡=0100100001000121)(D A ，则D 中v 1到v 3长度为4的通路有（ ）条。
A ．4 Ｂ．6 Ｃ．8 Ｄ．9
10.下面那种描述的图不一定是树（ ）。
A ．无回路的连通图 Ｂ．有n 个顶点的n-1条边
Ｃ．每对顶点都有通路的图 Ｄ．连通但删去一条边则不连通的图
11. 一颗二叉树后序遍历的结果是bdeca ，中序遍历的结果是badce ，则
根结点的右子树有（ ）结点。
A ．1
B ．2
C ．3
D ．4
12.设函数f ：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )
A. f 是单射
B. f 是满射
C. f 是双射的
D.f 非单射非满射
13.设S={0,1},则S 满足（ ）。
A. 在普通乘法下封闭，在普通加法下不封闭
B. 在普通加法和乘法下都封闭
C ．在普通加法下封闭，在普通乘法下不封闭
D ．在普通加法和乘法下都不封闭
14. 下图中（ ）是欧拉图。
A B C D
15. 设集合A={a ，b ，c ，d ，e}，
偏序关系R 的哈斯图如左图所示，
则元素的关系不正确的是（ ）。
A ．d c ≤
B ．e a ≤
C ．b a <
D ．e d ≤
二、 填空题 16.设无向图G 有12条边，有6个3度顶点，其余顶点度数均小于3，则G 种至少有 顶点。
17. 在彼得森图中至少添加 条边才能构成欧拉图。
18.由Huffman 算法，带权1,3,4,5,6的最优二叉树的权W(T)= 。
19.设V=为代数系统，其中A={0,1,2,3,4}。∀a,b ∈A,a*b=(ab)mod5。关于运算“*”的幺元是 。
20．设Z 为整数集，∀a,b ∈Z ，有a ︒b=a+b-1，则a 的逆元= 。
21．集合{a,b,c,d}上关系R 的关系图如左所示，则R 的传递
闭包（用集合表示）为 。
22.设R 是由方程x+3y=12定义的正整数集N 上的关系，即}123,|,{=+∧∈>23.若集合A 的基数|A|=10，则其幂集|P(A)|= 。
三、计算题
24．判断正整数集合Z+和下面的二元运算是否构成代数系统。如果是，则说明这个运算是否满足交换律、结合律和幂等律，并求出单位元和零元。
(1)a*b=min(a,b) (2)a ◊b=(a/b)+(b/a)
25.用主析取范式判断()r q p →→与()r p q →→是否等值。
26. 设，为上关系，关系矩阵为
， (1) 画出关系图。 (2) 求，。 (3) 求，，。 (4) 指出具有的性质。(5) 是偏序关系吗？能否画出哈斯图？
c f
g
27．求下图的最小生成树，写出过程，并计算权。
四、证明题
28．在命题逻辑中构造下面推理的证明。
前提：p→s，q→r，⌝r，p∨q结论：s
29．设无向图G是由k（k≥2）棵树组成的森林，已知G中有n个结点，m条边，证明m=n-k。
30．证明对于任意集合A,B,C，有(A-B)-C=(A-C)-(B-C)
五、应用题
31．75名儿童到公园游乐场，他们在那儿可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘过其中的两种。若每样乘坐一次的而费用是0.50元，公园游乐场总共收入70元，试确定有多少儿童没有乘过其中任何一种。
32．有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。（要求有一定的分析过程）
