模拟试题(一)一、 单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．给定命题公式如下：)()(p q q p ∨⌝→→⌝ 成真赋值的个数为（ ）。

A ．1 Ｂ．2 Ｃ．3 Ｄ．42. 设个体域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 ．<N,≤> Ｂ．<Z,≥> Ｃ．<{2,3,4,6,12},|> Ｄ．<p(A),⊆>6．全体自然数所组成的集合的最小元为（ ）。

A ．负数 Ｂ．最小的正数 Ｃ．0 Ｄ．17．对任何a ∈A ，形成的A 上的等价关系R 的等价类[a]R 为（ ）。

A ．空集 Ｂ．非空集 Ｃ．空集也可以为非空集 Ｄ．{x}x ∈A}8．设S=Q ⨯Q ，其中Q 为有理数集合，定义S 上的二元运算“*”，∀<a,b>,<x,y>∈S ，有>+>=<<><b by ax y x b a ,,*,，则<S,*>是（ ）。

A ．可交换的 Ｂ．可结合的Ｃ．既是可交换的，又是可结合的 Ｄ．不是可交换的，也不是可结合的9. 设有向图D=<V,E>的邻接矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0100100001000121)(D A ，则D 中v 1到v 3长度为4的通路有（ ）条。

A ．4 Ｂ．6 Ｃ．8 Ｄ．910.下面那种描述的图不一定是树（ ）。

A ．无回路的连通图 Ｂ．有n 个顶点的n-1条边Ｃ．每对顶点都有通路的图 Ｄ．连通但删去一条边则不连通的图11. 一颗二叉树后序遍历的结果是bdeca ，中序遍历的结果是badce ，则根结点的右子树有（ ）结点。

A ．1B ．2C ．3D ．412.设函数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 D15. 设集合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,*>为代数系统，其中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,|,{=+∧∈><y x N y x y x ，则=↑}6,4,3,2{R ，{3}在R 下的象是 。

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. 设，为上关系，关系矩阵为，a b c d e fg(1) 画出关系图。

(2) 求，。

(3) 求，，。

(4) 指出具有的性质。

(5) 是偏序关系吗？能否画出哈斯图？27．求下图的最小生成树，写出过程，并计算权。

四、证明题28．在命题逻辑中构造下面推理的证明。

前提：p→s，q→r，⌝r，p∨q结论：s29．设无向图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．有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中表示地道）。

问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。

（要求有一定的分析过程）模拟试题(二)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．下列是两个命题变元p，q的小项是（）A．p∧⌝p∧q B．⌝p∨q C．⌝p∧q D．⌝p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）A．p→⌝q B．p∨⌝q C．p∧q D．p∧⌝q3．下列语句中是命题的只有（）A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（）A．⌝(∃x)A(x)⇔(∀x)⌝A(x) B．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．( ∀x)( ∃y)(A(x)→B(y))⇔( ∃x)A(x)→(∃y)B(y)5．谓词公式∀xP(x,y)∧∃t(Q(t,z)→∀x∃yR(x,y,t))中量词∃t的辖域是（）A．∃t(Q(t,z)→∀x∃yR(x,y,t)) B．Q(t,z)→∀x∃yR(x,y,t)C．∀x∃yR(x,y,t) D．Q(t,z)6．设R为实数集，函数f：R→R，f(x)=2x，则f是（）A．满射函数 B．入射函数C．双射函数 D．非入射非满射7．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}8．设A={?}，B=P(P(A))，以下正确的式子是（）A．{?,{?}}∈B B．{{?,?}}∈B C．{{?},{{?}}}∈B D．{?,{{?}}}∈B9．设X，Y，Z是集合，“-”是集合相对补运算，下列等式不正确的是（）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z) D．(X-Y)-Z=X-(Y∪Z)10．设*是集合A上的二元运算，称z是A上关于运算*的零元，若（）A． z∉A，且有x*z=z*x=z B．z∈A，且有x*z=z*x=xC．z∈A，且有x*z=z*x=z D．z∉A，且有x*z=z*x=x11．在正整数Z+上，下列定义的运算中不可结合的只有（）A．a*b=min(a,b) B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数) D．a*b=a(mod b)12．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，<R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）A．{R+中的有理数} B．{R+中的无理数}C．{R+中的自然数} D．{1，2，3}13．设<A,*, >是环，则下列正确的是（）A．<A, >是交换群B．<A,*>是加法群C．对*是可分配的D．*对是可分配的14．图1所示的6个图中，强连通图为（）。

图1A. (1) (2) (3)B. (4) (5) (6)C. (1) (3) (4) (6)D. (1) (5) (6)15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）A．2个面 B．3个面C．4个面 D．5个面二、填空题16．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Q i(1≤ i ≤n)为，A为的谓词公式。

17．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是。

18．设Z 是整数集，在Z 上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<Z,*>的幺元是 ，零元是 。

19．图2所示平面图有3个面R 0,R 1和R 2，其中deg(R 0)= 。

20．图3中，结点v 2的度数是 。

图2 图321.设R 为A 上的关系，则R 的自反闭包为 ，对称闭包为 。

22. 公式)()(q p q p ⌝→→→⌝的主析取范式为 。

三、计算题23．求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。

24．判断下面集合对于给定运算能否构成群，并简要说明理由。

（1）实数集合R 关于☆运算，其中a ☆b =2(a +b )（2）非零实数集合R*关于⊙运算，其中a ⊙b =2ab25．画出5个具有5个结点5条边的非同构的无向连通简单图。