1、单项选择题第一章 命题逻辑1下列语句，哪一个是真命题：（ B ）A我正在说谎 B如果 1+1=0，那么雪是黑的C9+518 D存在最大的质数2下面哪一个命题是假命题（ A ）A如果 2 是偶数，那么一个公式的析取范式唯一B如果 2 是偶数，那么一个公式的析取范式不唯一C如果 2 是奇数，那么一个公式的析取范式唯一D如果 2 是奇数，那么一个公式的析取范式不唯一3下面哪个联结词运算不可交换（ B ）A ； B C D4设 P：天下大雨，Q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上班”符号化为（ B ）APQ BQ P CPQ D PQ5设 P：天下钉子，Q：我去 B 城 。命题“除
2、非天下钉子，否则我去 B 城”符号化为：（ C ）AP Q BQ P C P Q DQ P6设 P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（ B ）AP Q 2）（PQ） CPQ DPQV7令 P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）APQ BPQ CPQ DPQ 8设 P：我将去镇上，Q：我有时间，命题“我将去镇上，仅当我有时间” ，符号化为（ A ） 。AP Q B、Q P C、PQ D、PQ9下面哪一个命题公式是重言式（ D ）A （PR）（P Q） BP （QR ）C （PQ）（QR） D （P（Q R） ）（P Q） （
3、PR）10下面哪一组命题公式不是等价的（ C ）A （PQ） （Q P） ，P Q B （PQ） ， （PQ）（PQ）CP（QR ） ，P（ QR） D P （ QR） ， （PQ） R11下面哪个命题公式是重言式（ B ）A （P Q） （Q P） B （P Q）PC （PQ）（PQ） D （PQ） P12下列公式哪一个是两个命题变元 P，Q 的小项（ C ）APPQ BPQ CPQ DPPQ13一个公式在等价意义下，下面哪个写法是唯一的。 （ C ）A析取范式 B合取范式 C主析取范式 D以上答案都不对14命题公式(PQ)的主析取范式编码为 ( D )A B C D01m0m101m10m
4、15.命题公式(PQ)的主合取范为 ( a )A B. C. D.01M01M0110M16.命题公式的任意两个不同极小项的合取式一定为( b )A.永真式 B.永假式 C.可满足式 D.不可确定17下面联结词集中，哪一个不是联结词的极小全功能集（ d ）A， B C D，第二章 一阶逻辑1设 S(x): x 是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ） DAS（a） ， S（b） BS（a） S（b）CS（a）S（b） DS（a） S（b）2.令 F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号
5、化为 （ ） BA.x(F(x)G(x)x(G(x) F(x)B.x(F(x)G(x)x(G(x)F(x)C.x(F(x)G(x)x(G(x) F(x)D.x(F(x)G(x)x(G(x)F(x)3设 F(x)：x 是火车，G(x)：x 是汽车，H(x,y)：x 比 y 快。 “每列火车都比某些汽车快”符号化为（ ） CA ； B ；()()(,)yFGyH()()(,)xFGyHxC ； D)xxy ,4设 ： 是国家选手， ： 是健壮的。命题“没有一个国家选手不是健壮的”可)(符号化为（ ） CA ； B ；)()(xx )()(xCxC ； D ；G G5设个体域 A=a、b，公式 在
6、A 上消去量词应为（ ） D()()PxSAP(x)S(x) BP(a)P(b)S(a)S(b)CP(a)S(b) DP(a)P(b)(S(a)S(b)6一阶公式 x(P(x) yR(y)Q(x)中量词 x 的辖域是 ( ) AA. (P(x) yR(y) B. P(x)C. x(P(x) yR(y) D. (P(x) yR(y)Q(x)7、设论域为整数集，下列公式中哪个值为真（ ） AA B. C. D)0(yx)0(yx)0(yx)0(yx8下面给出的一阶逻辑等价式中，哪一个是错的。 （ ） BAAxB（ x）x（AB（x） ）Bx（A（x）B（x） ）xA（x）xB（x）Cx（A（x）B
7、（x） ）xA（x） xB（x）DxA（x） x（A（x） ）9在谓词演算中，下列各式中，哪式是正确的（ ） 。BA B),(),(yy),(),(yxAyxC DxxA10设论域为整数集，下列公式中哪个值为假 （ ） DA B)0(y)2(yxC Dzx111设 I 是如下一个解释：Da,b, 0 0 b)P(,a,bP(,a则在解释 I 下取真值为 1 的公式是( ).DA xyP(x,y) B xyP(x,y) C xP(x,x) D xyP(x,y).12谓词公式(x)P(x,y)( x)(Q(x,z)(x)(y)R(x,y,z)中量词x 的辖域是（ ）AA （Q(x,z)(x)(y)
8、R(x,y,z)） BQ(x,z)，R(x,y,z)CQ(x,z)(y)R(x,y,z) DQ(x,z)13.谓词公式 中变元 是 ( ) D)()xQyRxpA自由变元 B既不是自由变元也不是约束变元C约束变元 D既是自由变元又是约束变元14.一阶逻辑公式x(F(x,y)G(y,z) zF(z,y)是 （ ） CA.前束范式 B.封闭公式 C.永真式 D.永假式15一阶逻辑公式xP(x) xP(x)是( ) AA.永真的 B.永假的 C.可满足的 D.前束范式.16.一阶逻辑公式xP(x) yQ(y)的前束范式是（ d ）A.xy(P(x)Q(y) B.xP(x)yQ(y)C.xyP(x)Q
9、(y) D.xy(P(x) Q(y)第三章 集合的基本概念和运算1下列式子中正确的是（ ） DA0； B； C ； D2下列各式中哪个是错的（ B ） A、 ； B、； C、 ； D、 。3下列命题正确的是（ ） 。 AA= B = Ca a，b，c D a，b，c4下列各命题哪一个是假命题（ ） BAa,ba,b,c,a,b,c Ba,b a,b,c,a,b,cCa,ba,b,a,b Da,b a,b5设 A=1,2,3, 4,5, 6,7,8，下列哪个式子为真（ ） CA1A B1,2,3A C4,5A DA6设 A，B=P（P（ A） ） ，下式中错的是（ ） DA B； B B； CB
10、； D， P（A） 。7设 A=， B=, ，则 BA 是（ ） CA； B ； C, ； D8集合0的所有子集是（ ） BA； B , 0； C； D, 09设 Aa,b，则 A 的幂集 P（A）为（ ） DAa,b B,a,b C ,a, D,a,b,a,b10设 X，Y，Z 是集合， “一”是集合相对补运算，下列等式不正确的是（ ）A(X Y)ZX(YZ)B(XY) Z(XZ) YC(XY) Z(XZ) (YZ)D(X Y)ZX(YZ)11.设集合 A=2,a,3,4，B=1,a,3,4，E 为全集，则下列命题正确的是( ) CA 2A B a A C a B D a,1,3,4 B.1
11、2.设 A,B 为集合,AB=AB 成立的充分必要条件是( D )A. A=B= B. A= C. B= D. A=B第四章 二元关系与函数1设 A1，2，Ba,b,c，Cc,d，则 A（BC）为（ B ）A B C D,2,c1,2,c,1,2c2设集合 A=1，2，3，A 上的关系 R=，则R 不具备( ) BA传递性 B对称性 C自反性 D反对称性3设 R 是集合 A=a,b,c,d上的二元关系，R=,，则 R 具有关系的哪些性质（ ） DA.自反性、反对称性 B.反自反性、传递性C.自反性、对称性 D.反对称性、传递性 4设集合 A1,2,3,4，A 上的关系 R,，则 R 具有关系的
12、哪些性质（ ） AA传递性；B自反性；C对称性；D以上答案都不对5设 A=0, b，B=1, b, 3，则 AB 的恒等关系为（ ）AA, , ,； B, , ；C, , ； D, , , 6设 A1，2，4，6，8,集合 A 上的二元关系 ，则 和 分别2,baRdomRran为（ ）BA 和 B 和 C 和 D 和,1,4,12,4,1,1,4,227若集合 A 上的关系 R 为等价关系，则 R 的必要条件是（ ）DA对称的和传递的 B反自反的 C反对称的 D自反的，对称的和传递的8设集合 A=a,b,c，A 上所有互不相同的等价关系的数目为( ) CA. 3 B. 4 C. 5 D. 6
13、9设 A=a,b,c,d，A 上的等价关系 R=,I A，则对应于 R 的 A的划分是（ ）DAa,b,c,d Ba,b,c,dCa,b,c,d Da,b,c,d10P=a、b、c、d的最大划分是（ ） （即集中元素数目最多的划分） CAa，b，cd； Ba，b，c；Ca、b，c，d Da，b，c，d11集合 A 上的关系 R 是偏序关系的必要条件是（ ） AA自反的，反对称的和传递的； B自反的和对称的；C传递和和对称的； D传递的和反对称的。12集合 A1,2,3，4，5，6，7，8，9，10，A 上的整除关系是一个偏序关系，则元素10 是集合 的（ ） CA最大元； B最小元； C极大元
14、； D极小元13.下列关系中哪一个是集合 A=a,b,c,d,e,f上偏序关系？ （ ） BA.,I A B.,I AC.,I A D.,I A14.集合 A= ，A 上的一个划分 ，则对应的等价关系 （ ,abcd1,abcd 1RA ） 。A B,AI,cdC D,abcdab15.设 A=a,b,c,d，A 上的等价关系 R=,I A，则对应于 R 的 A 的划分是（ D）Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d16设 R 为实数集，映射 f：RR，f（x）-x 2+2x-1，则 f 是（ ） 。DA单射而非满射 B满射而非单射 C双射 D既不是单射，也不是
15、满射17设 f 和 g 都是 A 到 A 的双射函数，则（fog） -1为（ D ）Af -1og-1 B.f-og-1 C.（gof） -1 D.g-1 o f-118.设集合 A=a,b,c,B=,则从 A 到 B 最多可以定义多少个双射函数( )DA.27 B. 9 C.8 D.6 第七章 图的基本概念1仅由一个孤立点组成的图称为（ ） BA零图 B平凡图 C多重图 D子图2给下列序列，哪一个可构成无向简单图的顶点度数序列（ B ）（1） （1，1，2，2，3） （2） （1，1，2，2，2） （3） （1，2，3，4，5） （4） （1，3，4，4，5） 3下面所给的数值序列，能成为简
16、单图的度数序列的是（ ） CA(1,2,2,3,4,5) B(1,2,3,4,5,5) C(1,1,1,2,3) D(2,3,3,4,5,6)4在任何图 G=V，E中，顶点总度数和边数的关系为（ ）CA B C Dv2)deg(vE)deg(VvE2)deg(VvE)deg(5设 G 为有 n 个结点的无向完全图，则 G 的边数为（ ） AA B Cn (n1) Dn (n+1)1(2)1(6有向图 G=，其中 V=a,b,c,d,e,f，E=,是( ) AA弱连通图 B单向连通图 C强连通图 D不连通图7图 G=如下图所示，从 a 到 d 有多少条简单通路（ ）CA5 B6 C7 D8ba
17、ec d8邻接矩阵具有对称性的图一定是（ ） BA有向图 B无向图 C混合图 D简单图9G=是简单有向图，可达矩阵 P（G）刻划下列哪种关系（ ）AA点与点 B点与边 C边与点 D边与边10设图 G 的邻接矩阵为 ，则 G 的顶点数与边数分别为( ) D01A4, 5 B5, 6 C4, 10 D5, 811在完全图 的所有非同构的生成子图中，有几个是 3 条边的？( ) B4KA. 1 B. 2 C. 3 D. 412图 G 和 G的结点和边分别存在 对应关系是 （同构）的（ ）GA充分条件 B充分必要条件 C必要条件 D既不充分也不必要条件13.设图 G=为无向图，|V|=6，|E|=22
18、，则 G 一定是 DA.完全图 B.正则图 C.简单图 D.多重图14设 A（G）是有向图 G=（V，E）的邻接矩接，其中第 i 行中值为 1 的元素数目为（ ） BA结点 Vi 的入度 B.结点 Vi 的出度 C结点 Vi 的度数 D.结点 Vj 的度数15.有 3 条边的互不同构的 4 阶无向简单图的个数为 （ ）AA.2 B.3 C.4 D.516.有向图 G 是强连通图，当且仅当 DA.图 G 中至少有一条通路 B.图 G 中有通过每个顶点至少一次的通路C.图 G 中至少有一条回路 D.图 G 中有通过每个顶点至少一次的回路17.有向图 G 是单向连通图，当且仅当( ) BA.图 G
19、中至少有一条通路 B.图 G 中有通过每个顶点至少一次的通路C.图 G 的连通分枝数为一. D.图 G 中有通过每个顶点至少一次的回路.第八章 一些特殊的图1一个连通的无向图 G，如果它的所有结点的度数都是偶数，那么它具有一条( ) BA哈密尔顿回路 B欧拉回路 C哈密尔顿通路 D初级回路2无向图 G 是欧拉图，当且仅当（ ） DAG 的所有结点的度数全为偶数。 BG 中所有结点的度数全为奇数。CG 连通且所有结点度数全为奇数。 DG 连通且所有结点度数全为偶数。3设 G 是连通平面图，有 5 个顶点，6 个面，则 G 的边数是( ) AA9 条 B5 条 C6 条 D11 条4设 G 是连通
20、平面图，G 中有 6 个顶点 8 条边，则 G 的面的数目是（ ） CA2 个面 B3 个面 C4 个面 D5 个面5二部图 是( ) B3,KA.欧拉图 B. 哈密顿图 C. 平面图 D.完全图6.下列图形哪一个可以一笔画出？ （ ） DA. B. C. D.7在下面的无向图中，哪一个是哈密顿图？。 （ ） BD.C.B.A.8下图属于什么图？（ ） DA二部图 B欧拉图 C哈密尔顿图 D是二部图也是哈密尔顿图 9.下图的最大匹配是( )ae3e4e6 e7e9e8e2e1e5e10 e11A. B. C. D.2571,24691,15791,e12471,e10.、给定平面 G 如下所示
21、，则 G 中所有面的总次数为（ B）（1）28 （2）22 （3）26 （4）24第九章 树1下面哪一种图不一定是树。 （ D ）A有 n 个顶点 n1 条边的连通图 B无回路的连通图C连通但删去一条边则不连通的图 D每对结点间都有路的图2设 G 是有 5 个顶点的完全图，则从 G 中删去多少条边可以得到树？( A )A6 B5 C10 D4.3在具有 n 个顶点的完全图 Kn 中删去多少条边才能得到树？（ A ）A ； B ； C ； D 。(1)2(1)nm1n1nm4设 G=为（n, m）连通图，则要确定 G 的一棵生成树必删去 G 中边数为（ ） CAnm+1 Bnm1 Cmn+1 D
22、mn15.设图 G 是有 6 个顶点的连通图，总度数为 20，则从 G 中删去多少条边使之变成树？（ ） BA10 B5 C3 D2 6下面给出的符号串集合中，哪一个是前缀码？（ ） AA1, 01, 001, 000 B1, 11, 101, 001, 0011Cb, c, aa, bc, aba Db, c, a, aa, ac, abb7下面给出的符号串集合中，哪一个不是前缀码？（ ） BA ； B ；1,0, 10,1,0C ； D 。abcacb8设 T 是有 n 个结点的二元正则树，则树 T 的叶子数为（ ） 。CAn1 B2n1 C(n+1)/2 D(n+2)/39.T 为二元正则树，有 t 片叶子，e 条边，则有（ c ）Ae 2(t1) B. e 2(t1) C. e 2(t1) D. e2(t+1)
