编 号
题目
答案
题 分 型 值 填 2 空 题
大纲
难
度
1
谓词公式 x(P(x) yR(y))
3.1
3
Q(x) 中量词 x 的辖域是（ ）。 答： P(x)yR(y)
2
令 R(x):x 是实数， Q(x):x 是有理数。则命题“并非每个实数都是有理数”的 符号化表示为（
）。
n 与边数 m 关系是 (
答：x(R(x)Q(x))
填 2 空 题
3.1
3
3 一棵无向树的顶点数 )。 答： m=n-1
填 2 空
7.1
3
4
题
一个图的欧拉回路是一条通过图中
(
)的回路。
答：所有边一次且恰好一次
填 2 空
6.4
3
5
题
有 n 个结点的树，其结点度数之和是
(
)。
答： 2n-2
填 2 空
6.4
3
6
题
设 T 是一棵树，则 T 是一个连通且 (
)图。
答：简单无回路
填 2 空
6.2
3
7
题
任一有向图中，度数为奇数的结点有
(
) 个。
答：偶数
填 2 空 题
6.1
3
8
答： {0 ，1， 2， 3，4， 6}
设 A { x | ( x 正偶数） 则
N )且 ( x 5)}, B { x | x E 且 x
7} （ N ：自然数集， E
+
填 2 空 题
1
2
A B
（ ） 。
答： 1
9
设 P， Q 的真值为 0， R， S 的真值为 1，则
填 2 空
2.1
3
( P (Q ( R
10
公式 (P
P))) R)
(R S) 的真值 = （
）。 ） 。
题
R) (S
P 的主合取范式为（
答： ( P S R) ( PS R)
填 2 空 题 填 2 空 题
2.3
4
11 设 A={1 ， 2 ， 3 ， 4} ， A 上关系为
｛ <1,2>,<2,1>,<2,3>,<3,4> ｝则 R2 = 答： {<1,1>, <1,3>, <2,2>, <2,4> }
4.1；4.2 3
( )。
12
设 A={a ， b， c，d} ，其上偏序关系
R 的哈斯图为
答： { IA 填 2 4.4 空 题 4 则 R= （ ）。 13 树是不包含树是不包含（ ）的（ ）图的。 答：环 ;无向 填 2 空 题 填 2 空 题 填 2 空 题 8.1 3 14 设 A={1 ，2，3} ，则 A 上既不是对称的又不是反对称的关系 R= ( ) 。 答： R={<1,2>,<1,3>,<2,1>} 4.3 3 15 答： 2(x+1) 设 f ，g 是自然数集 N 上的函数 x N , f (x) x 1 , g (x) 2x ，则 5.2 3 f g( x) （ ）。 16 设 A={a ， b， c} ， A 上二元关系 R={< a, a > , < a, b >,< a, c >, < c, c>} , 答 { a , a , a ,b , a , c , c , c , b , a , c, a } ： 填 2 空 题 4.4 5 则 s（R）= （ ）。 17 P，Q 真值为 0 ；R，S 真值为 1。则 wff ( P (R S)) (( P Q) (R S)) 答： 1 填 2 空 2.2 3 的真值为（ 18 wff ）。 题 (( P Q) R) R 的主合取范式为（ ）。 答： ( P Q R) ( P Q R) ( P Q R) 填 2 2.3 空 4 题 R) 19 设 P（ x）： x 是素数， E(x) ： x 是偶数， O(x) ： x 是奇数 N (x,y) ：x 可以整 答：( P Q R) ( P Q R) ( P Q 填 2 3.1 3 空 题 数 y 。 则 谓 词 wff （ ）。 x( P(x) y(O ( y) N ( y, x))) 的 自 然 语 言 是 20 答 谓 词 wff x y( z(P(x, z) P( y, z))uQ( x, y,u)) 的 前 束 范 式 为 ： 填 2 3.2 空 题 4 x y z u( P(x, z) （ ）。 P( y, z) Q (x, y,u)) 21 若 P， Q，为二命题， P Q 真值为 0 当且仅当（ ） 。 答： P 真值为 1， Q 的真值为 0 填 2 空 题 2.1 3 22 将量词辖域中出现的（ ） 和指导变元交换为另一变元符号，公式其余 答：约束变元 填 2 空 题 3.1 3 的部分不变，这种方法称为换名规则。 23 设 G 为 9 阶无向图，每个结点度数不是 个 5 度结点。 5 就是 6，则 G 中至少有 （ ） 答： 6 填 26.1 3 空 题 24 答： 2 填 2 6.3 3 空 题 有向图 （ 25 设 [ L, , （ 中从 v1 到 v2 长度为 2 ） 条。 的通路有 ] 是 代 数 系 统 ， 则 [ L, , ] 满 足 幂 等 律 ， 即 对 a L 有 ） 。 答： a a a 且 a a a 填 2 8.2 4 空 题 26 任何 (n,m) 图 G = (V,E) , 边与顶点数的关系是（ ）。 答： d(v) 2m v V 填 2 空 题 6.4 3 27 当 n 为（ ） 时, 非平凡无向完全图 Kn 是欧拉图。 答：奇数 填 2 空 题 6.2 3 28 已知一棵无向树有（ 填 2 7.1 3 T 有三个 3 顶点 , 一个 2 度顶点 , 其余的都是 1 度顶点 , 则 T 中 ）个 1 度顶点。 答： 5 空 题 29 集合 A={ ,{ }} 的幂集 P(A) =（ ） 。 答： { ,{ }, {{ }}, { ,{ }}} 填 2 空 题 1 3 30 设|A|=3 ，则 A 上有（ ）个二元关系。 答： 29 填 2 空 题 4.1 3 31 Q：我将去上海， R：我有时间，公式 (Q R) ( R Q ) 的自然语言为 答：我将去上海当且仅当我有空 填 2 2.1 空 题 （ 32 公式 (QP) ( ）。 3 P Q ) 的主合取范式是（ ） 。 答 ： ( P Q ) (P Q ) ( P Q) ( P Q ) 填 2 空 题 填 2 2.3 3 33 若 S { S1 , S2 , , Sm } 是集合 A 的一个分划，则它应满足（ ）。 m 答： (1)Si Sj (i j ) (2) Si i 1 A 空 题 填 2 空 题 填 2 空 题 4.4 3 34 代数系统 分别为 答： e 8.1 3 关系为（ ） 。 n 35 设 A { x | x 2 , n N } ，定义 A 上的二元运算为普通乘法、 除法和加法， 答：乘法 则代数系统 ）运算具有封闭性。 8.1 3 36 设 )。 答： G { a, a2 , a n 1， a n e} 填 2 8.3 空 题 填 2 空 题 填 2 空 题 填 2 空 题 4 37 一个图是平面图的充要条件是 ( ) 。 答：它不包含与 K 3, 3 或 K 5 在 2 度结点内同构的子图 6.4 3 38 某 人 有 三 个 儿 子 ， 组 成 集 合 A={S 1 ,S2,S3} ， 在 A 上 的 兄 弟 关 系 具 有 答：反自反性、对称性、传递性 4.1 （ ）性质。 3 39 若 f : A B 是函数，则当 f 是 A B 的（ ）， f c : BA 是 f 答：双射 5.2 3 的逆函数。 40 设 P：它占据空间， Q：它有质量， R：它不断运动， S：它叫做物质。 命题“占 答： S P Q R 填 2 2.1 3 空 题 据空间的，有质量的而且不断运动的叫做物质”的符号化为（ 41 设 A ， B 是两命题公式， A ）。 ）。 B 当且仅当（ 答： A B T 填 2 空 题 zQ(u, z)xR(x, w) 2.1；2.2 3 42 对 谓 词 公 式 ( )。 yP (x, y) zQ(x, z) xR(x, y) 的 自 由 变 元 代 入 得 答： yP (u, y) 填 空 题 2 3.1；3.2 3 43 对集合 X 和 Y ，设 |X|=m ， |Y|=n ，则从 X 到 Y 的函数有 ( ) 个。 答： n m 填 2 空 题 填 2 空 题 填 2 空 题 上封闭，② * 在 A 上可结合，③ * 填 2 空 题 ： 填 2 5.1 3 44 若关系 R 是等价关系 ,则 R 满足 ( )性质。 答：自反性、对称性、传递性 4.4 3 45 关系 R 的传递闭包 t (R) = ( ) 。 答： i R R 1 i 4.3 4 46 代数系统 A , 是群，则它满足 ( )。 答：①运算 * 在 A 8.2；8.3 3 在 A 上存在幺元，④ A 中每个元素都有逆元； 47 设 A, ,? 和 B , , 是两代数系统， f 是 A , ,? 到 B , , 答 a,b 8.2；8.3 3 A , f (a b) f (a) f (b) , f (a b) f (a) f (b) 空 的同态映射，则 48 若连通平面图 G f 具有 ( )性质。 题 答： v e r 2 填 2 6.4 空 题 3 V , E 共有 r 个面，其中 V v , E e，则它满足的 Euler 公式为 ( )。 49 树 T 的边数 e 与点数 v 有关系 ( )。 答： e v 1 填 2 空 题 填 2 空 题 填 2 空 题 7.1；7.2 3 50 n 个命题变元有 ( )个互不等价的极小项。 答： 2 n 2.2；2.3 3 n n 51 按 De-Morgan 定理， A1A2 An i Ai =( 1 答： )。 ( Ai ) i 1 2.2；2.3 3 52 公式 P ( Q R) 的主析取范式为 ( ) 。 答 ( P (P ： 填 2 2.3 4 Q Q R) ( P R) ( P Q R) ( P QR) ( P Q R) Q R ) (P Q R) 空 题 0,1, 2, 3, 4,5, 7 53 设 P(x)：x 是大象， Q(x) ：x 是老鼠， R(x,y) ：x 比 y 重，则命题“大象比老鼠 重”的符号化为 ( )。 答： x y( P( x) Q( y) R(x, y)) 填 2 空 题 3.1 3 54 1 0 1 1 1 1 ( )。 1 1 1 1 设 X { a, b, c} ， X 上的关系 R 的关系矩阵是 M R 1 1 0 ，则 答： 1 1 1 1 填 2 空 题 6.3 4 1 M R R 55 在 具 有 n 个 结 点 的 有 向 图 中 ， 任 何 基 本 通 路 的 长 度 都 不 超 过 ( ) 。 答： n-1 填 2 6.1 3 空 题 56 任 何图 的 点 连 通 度 (G ) ， 边 连 通度 (G ) ， 最 小 点 度 (G ) 的 关 系 为 答： (G )(G)(G ) ( )。 填 2 6.1；6.2 3 空 题 57 结点数 n（ n 3 ）的简单连通平面图的边数为 )。 m，则 m 与 n 的关系为 答： m 3n 6 填 2 6.4 4 空 ( 题 58 群 G 的非空子集 H 是 G 的子群当且仅当若 x , y H 则 ( )。 答： x y 1 H 填 2 8.3 4 空 题 填 2 8.2；8.3 5 59 代数系统 A, ,? 是环，若对运算“· ”还满足 ( )则 答：含幺元，可交换，无零因子 空 题 A, ,? 是整环。 60 给定命题公式 A 、B ，若（ ），则称 A 和 B 是逻辑相等的。 答：对于 A ，B 中原子变元 P1 , P2 , 真值指派， A 和 B 的真值相同。 , Pn 任意一组 填 2 空 题 填 2 2.1 3 61 设 A { a, b, c} 考 虑 下 列 子 集 S1 {{ a, b}, { b, c}} {{ a, b, c}} ， 答： S1 , S2 , S3 , S4 , S5 ； S3 ， S4 ， S5 4.4 4 空 题 S2 {{ a}, { a, b}, { a,c}} ， S3 {{ a}, {b, c}} ， S4 S5 {{ a}, {b}, { c}} ， S6 {{ a}, { a, c}} 则 A 的覆盖有（ 62 若 G ）， A 的划分有（ ）。 V, E 为哈密顿图，则对于结点集 ） S 成立， V 的每个非空子集 S，均有 答：≤ 填 2 空 题 6.4 4 P(G-S)（ 63 某班有学生 50 人 , 有 26 人在第一次考试中得优 , 有 21人在第二次考试中得优 , （）。 答： 14 有 17 人 两 次 考 试 都 没 有 得 优 , 那 么 两 次 考 试 都 得 优 的 学 生 人 数 是 填 2 空 题 1 3 64 给命题变元 p、 s 和 r 指派真值 1,q 指派真值 0, 公式 p→ ( ┐ (s ∧ r) →┐ q) ∧ s) 答： 1 的真值为（ ）。 65 设 p：我生病， q：我去上课，命题“我虽然生病但我还是去上课”符号化为： （ ）。 答： p q 填 2 2.1；2.2 3 空 题 填 2 2.1；2.2 3 空 题 66 公式 xA(x) → xB(x) 的前束范式为（ ）。 答： x( A( x) B( x))或 x( A( x) B( x)) 填 2 3.2 4 空 题 填 2 4.1；4.2 4 空 题 67 若{1,2,3,4} （ 上的二元关系 R={<1,1>,<1,2>,<2,4>}, ）。 则 R 的自反闭包 r(R )= 答： r(R)= ｛ <1,1>,<1,2>,<2,4>,<2,2><3,3>,<4,4> ｝ 68 有向图 D 如下，则 D 的邻接矩阵 A(D) = （ ）。 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 填 2 6.3 3 空 题 答： 69 5 阶的群有（ ）个不同的子群。 答： 2 填 2 8.3 4 空 题 填 2 7.1；7.2 3 空 题 70 一棵高度为 5 的二元树结点数最多为（ ）。 答： 63 71 一个连通平面图 G 有 10 条边， G 中度为 1 的顶点有 2 个，其余是度为 6 的顶 答： 5， 7 填 2 空 题 填 2 空 题 6.1；6.2 3 点，则 G 中共有（ ）个顶点，（ ， ）个面。 72 集 合 X={0,1,2,3} R 是X 上 的 二 元 关 系 ， R={<0,1>,<0,2>,<1,1>,<1,3>,<2,0>,<2,3>,<3,1,>} （ ，则 R 的关系矩阵 M R 是 答： 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 6.2；6.3 3 ）。 73 无向图 G 中有 n 个结点 m 条边，且 G 中每个结点的度数不是 k 就是 k+1,则 G 答： (k+1)n-2m 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 6.1；6.2 3 中度数为 k 的结点的个数是（ ）。 + 74 设 Z ={x │ x∈ Z∧ x>0} ，* 表示求两个数的最小公倍数的运算，则 * 运算的幺 答： 1 8.1；8.2 3 元是（ ）。 75 群 ）个不同的子群。 答： 2 8.1；8.2 4 76 在个体域 D={a,b} 中，与公式 xA(x) 等价又不含量词的公式是（ ）。 答： A(a) ∧ A(b) 3.1；3.2 3 77 具有 4 个结点的有向完全图的边数为（ ）条。 答： 24 6.1 3 78 若 p：他聪明； q：他用功； 则 “他虽聪明， 但不用功 ”，可符号化为 （ ）。 答： p∧┐ q 2.1 3 79 若集合 A={1, 2, 3} 上的二元关系 R1 和 R2 的关系图如下所示， 答： r(R)= ｛ <1,1>,<1,2>,<2,4>,<2,2><3,3>,<4,4> ｝ 4.1；4.2 3 则 R1oR2 =（ ）。 80 树是平面图，它有（ ）个面。 答： 1 填 2 空 题 填 2 空 题 6.1；7.1 3 81 哈密尔顿回路要求经过图中（ ）一次且仅一次。 答：每个顶点 6.4 3 82 有向图 D 如下：D 的邻接矩阵 A=(aij)3 × 3,则 a11=（ ）,a32=（ ）。 答： 1， 0 填 2 空 题 6.3 3 83 在一棵根树中，仅有一个结点的入度为（ 入度均为（ ）。 ），称为树根，其余结点的 答： 0， 1 填 2 空 题 7.2 3 84 合式公式 Q→(P ∨ (P∧ Q)) 与 Q→P 的关系是 _______的。（等价或蕴含选一） 答：等价 填 2 空 题 填 2 空 题 2.2；2.3 3 85 设 R 为非空集合 A 上的二元关系，如果 R 满足（ ），则称 R 为 A 答：自反、反对称、传递 4.3 3 上的一个偏序关系。 86 设 R 为 A 上的关系，则 R 的自反闭包 r(R)= （ ），对称闭包 s(R)= 答： R Ix , R Rc 填 2 空 题 4.3 4 （ ）。 87 一棵高度为 3 的二叉树结点数最多为（ ） 。 答： 7 填 2 空 题 7.1；7.2 3 88 设 Z 是整数集，在 Z 上定义二元运算 * 为 a*b=a+b+a ?b，其中 +和 ?是数的加法 答： a , 0 填 2 8.1；8.2 3 和乘法， 则代数系统 ），零元是（ ）。 空 题 89 设 T 是有 n 个结点的完全二叉树，则 T 叶子数为（ ）。 答： (n+1)/2 填 2 7.1；7.2 3 空 90 题 设 A={a,b,c}, 则 A × A 中的元素有 ( )。 答： 9 填 2 1； 4.1 3 空 题 填 2 91 图 G 与其对偶图 G* 的结点数目（ ）相等。 答：不一定 6.4 4 空 题 92 设 S { 1, 2, 3 } ，定义 S S上的等价关系 | a,b S S, c, dS 答： 4 填 2 4.3；4.4 3 空 题 R 由 { a,b , c, d S, a d b c} 则 R 产 生的 S S 上一个划分共有（ ）个分块。 1 93 设〈 G， 〉是一个群，则对任意的 a, b ∈ G 均有 (a b) = （ ）。 答： b * a 11 填 2 空 题 8.3 5 94 0 A= 1 1 1 0 1 0 1 1 0 0 答： 2， 2 设图 D= 23 4 ，v ，v ，v } ，若 D 的邻接矩阵 1 ，则 填 2 空 题 6.3 4 1 0 0 1 deg-（ v1） =（ ），从 v2 到 v4 长度为 2 的路有（ ）条。 95 设 A={1 ， 2} ， B={2 ， 3} ，则 A-A= （ ）， A-B= （ ）。 答： ，{1} 填 2 1 3 空 题 96 两个重言式的析取是（ ）式，一个重言式与一个矛盾式的析取是 答：重言式，重言式 填 2 2.1；2.2 3 空 （ ）式。 题 答： 5 填 2 97 一个无向树中有 6 条边，则它有（ ）个结点。 7.1 3 空 题 98 谓词公式 ( x)( 自由变元是（ y)（ P(x,y) ∨R(y)) → Q(y) ，则其约束变元是（ ）。 ）， 答：（ P(x,y) ∨ R(y)) 中的 x,y; Q(y) 中的 y 填 2 2.1；2.2 3 空 题 99 一个结点为（ 填 2 6.1；7.1 3 n 的无向完全图，其边的数目为（ ）度正则图。 ） , 并且它是 答： n(n-1)/2,n 空 题 填 2 100 答：［x］=［y］, 设 R 为非空集合 A 上的等价关系， 其等价类记为 〔 x〕R。 x,y∈ A ，若〈 x,y 〉 R R ∈R，则〔 x〕 R 与〔 y〕R 的关系是（ ∩〔 y〕 =（ R R 4.4 4 空 题 ），而若〈 x,y 〉 R，则〔 x〕 ）。 因篇幅问题不能全部显示，请点此查看更多更全内容