河南财经政法大学成教【离散数学】高起专教学计划 图1
1、下列语句是命题的有（ ）
A.请勿吸烟！
B.我正在说假话。
C.您吃饭了吗？
D.火星上有生命。
答案：D
2、设命题公式G：¬p→(q∧r)，则使公式G取真值为1的P，Q，R赋值分别是 ( )
A.0,0,0
B.0,0,1
C.0,1,0
D.1,0,0
答案：D
3、下列公式成立的为( )
A.￢P∧￢Q⇔P∨QB
B.P→￢Q⇔￢P→Q
C.(P→(￢Q→P))↔(￢P→P(P→Q))
D.(￢P∨(P∧Q))↔Q
答案：D
4、若某意命题公式含有3个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则不是该命题公式的成假赋值有（ ）
A.000,001
B.010，011
C.100101
D.110111
答案：A
5、下列公式 ( )为重言式
A.￢P∧￢Q↔P∨Q
B.(Q→(P∨Q))↔(￢Q(P∨Q))
C.(P→(￢Q→P))↔(￢P→(P→Q))
D.(￢P∨(P∧Q))↔Q
答案：C
6、F(x): x是人, G(x): x呼吸，自然语言“没有不呼吸的人”可符号化表示为（ ）
A.￢∃x(F(x)∧￢G(x))
B.￢∀x(F(x)→G(x))
C.￢∃x(F(x)→￢G(x))
D.￢∀x(F(x)∧G(x))
答案：A
7、设个体域{1,2},对公式∀xF(x)→彐yG(y)消去量词后为（ ）
A.(F(1)∧F(2))→(G(1)∧G(2))
B.(F(1)∧F(2))→(G(1)∨G(2))
C.(F(1)∨F(2))∨(G(1)∧G(2))
D.(F(1)∨F(2))→(G(1)∨G(2))
答案：B
8、在谓词公式（∀x）(A(x)→B(x)∨C(x,y))中，（ ）
A.x，y都是约束变元
B.x，y都是自由变元
C.x是约束变元，y都是自由变元
D.x是自由变元，y都是约束变元
答案：C
9、公式∀xF(x)→∃y(G(y)∧H(x,y))的前束范式为（ ）
A.∀t∀y(F(t)→(G(y)∧H(x,y)))
B.∀x∃y(F(x)→(G(y)∧H(x,y)))
C.∃t∃y(F(t)→(G(y)∧H(x,y)))
D.∃t∃y(F(t)→(G(y)∧H(t,y)))
答案：C
10、在一阶逻辑中给出下面两个推理，______是正确的。 （1） 前提：∀x(F(x)→G(x)) ，∃yF(y) 结论：∃yG(y)；（2） 前提：∃x(F(x)∧G(x)) 结论：∀yF(y)
A.（1）
B.（2）
C.（1）（2）
D.都不正确
答案：A
11、设集合A = {1, a }，则P(A) = ( )．
A.{{1}, {a}}
B.{∅,{1}, {a}}
C.{∅,{1}, {a}, {1, a }}
D.{{1}, {a}, {1, a }}
答案：C
12、若A= {1,2}，则A的子集有（ ）
A.空集
B.{1}
C.{2}、{1,2}
D.以上都对
答案：D
13、设A={1,2,3,4,5},下面()集合等于A 。
A.{1,2,3,4,5,6}
B.{x|x是整数且x≤5}
C.{x|x是自然数且x≤5}
D.{x|x是正整数且x≤5}
答案：D
14、设A={1,2}，B={a,b},则（ ）是A×B中的有序对
A.<1,a>
B.<2,a>
C.<1,b>、<2,b>
D.以上都对
答案：D
15、若A={0,1}, B={2,3}, 那么R1={<0,2>},R2=A×B,R3=∅,R4={<0,1>}中，（ ）不是A上的二元关系
A.R1
B.R2
C.R3
D.R4
答案：D
16、设R={<0,1>,<0,2><1,2>,<1,3>,<2,3>},则domR=（ ）
A.{0,1,2}
B.{1,2,3}
C.{0,1,2,3}
D.∅
答案：A
17、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y∈A},则R 的性质为( )。
A.自反的
B.对称的
C.自反的，对称的
D.传递的
答案：B
18、设A={1,2,3}，R={<1,2>,<2,2>}，R'={<1,2>,<2,2>,<1,1>,<3,3>,<4,4>}，R和R'都是A上的关系，则R'是R的（ ）
A.自反闭包
B.对称闭包
C.传递闭包
D.以上均不正确
答案：A
19、设集合A={1,2,3,4},A上的等价关系R={<1,1>,<3,2>,<2,3>,<4,4>}∪IA，则对应于R的划分是（）。
A.{{1},{2,3},{4}}
B.{{1,3},{2,4}}
C.{{1,3},{2},{4}}
D.{{1},{2},{3},{4}}
答案：A
20、设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )
A.8、2、8、2
B.无、2、无、2
C.6、2、6、2
D.8、1、6、1
答案：B
21、若图G中含有平行边，则G是（ ）
A.多重图
B.平凡图
C.线图
D.简单图
答案：A
22、设P(x): x是简单回路，H(x): x是初级回路，则 “简单回路未必都是初级回路”在一阶逻辑中的符合化形式为（ ）
A.∀x(P(x)→H(x))
B.∃x(P(x)∧¬H(x))
C.∀x(P(x)→¬H(x))
D.∃x(P(x)∧H(x))
答案：B
23、设无向图连通图G＝<V,E>,若{v2,v4},{v3},{v5}是图G的点割集，则G的点连通度是（ ）
A.0
B.1
C.2
D.4
答案：B
24、关于有向图的邻接矩阵，描述正确的是（ ）
A.矩阵中每一列的元素和表示对应结点的出度
B.矩阵中每一行的元素和表示对应结点的入度
C.矩阵中每一列的元素和表示对应结点
D.矩阵中每一行的元素和表示对应结点的出度
答案：D
25、无向简单图G是棵树，当且仅当( )
A.G连通且边数比结点数少1
B.G连通且结点数比边数少1
C.G的边数比结点数少1
D.G中没有回路
答案：A
26、若图G的最小生成树T中，各边的权值是1,2,3,3,4,7，那么该最小生成树的权为（ ）
A.20
B.17
C.1
D.以上均不正确
答案：A
27、带权为1, 1, 2, 3的最有二叉树的权为（ ）
A.7
B.13
C.20
D.以上均不正确
答案：B
专题一
1、设命题公式G=(p∧q)→p，则G是（ ）
A.永假式
B.永真式
C.可满足式
D.析取范式
答案：B
2、已知命题G=¬(p→(q∧r))，则所有使G取真值1的解释是（ ）
A.（0，0，0），（0，0，1），（1，0，0）
B.（1，0，0），（1，0，1），（1，1，0）
C.（0，1，0），（1，0，1），（0，0，1）
D.（0，0，1），（1，0，1），（1，1，1）
答案：B
3、下列命题公式为重言式的是（ ）
A.p→（p∨q）
B.（p∨¬p）→q
C.q∧¬q
D.p→¬q
答案：A
4、用p表示：天下大雨；q表示：他乘公共汽车上班。将“如果天下大雨，他就乘公共汽车上班。”符号化正确的是（ ）
A.p→q
B.p∧q
C.p∨q
D.q→p
答案：A
5、设p：天气晴朗，q：小李出去郊游，命题“除非天气晴朗，否则小李不出去郊游”的符号化形式为（ ）。
A.q→p
B.p→q
C.¬p→q
D.p→¬q
答案：A
6、 在下述公式中不是重言式(永真式)的为（ ）
A.((p∨q)∧¬p)→q
B.((p→q)∧p)→q
C.((p∨q)∧r)→q
D.p→(p∨q)
答案：C
7、设p：今天汽车限号，q：小李开车上班，命题“如果今天汽车不限号，小李就开车上班”的符号化形式为（ ）。
A.q→p
B.┐p→q
C.p→ ┐q
D.p→q
答案：B
8、设p：天下大雨，q：小李乘公共汽车上班，命题“只有天下大雨，小李才乘公共汽车上班”的符号化形式为（ ）。
A.q→p
B.┐p→q
C.p→ ┐q
D.p→q
答案：A
9、在下述式子为重言式的是（ ）。
A.P→(P∨Q)
B.(┑P∨Q)∧(P∨┑Q)
C.┑(P↔Q)
D.(P∨Q)↔(P→Q)
答案：A
10、下列语句是命题的有（ ）
A.请勿吸烟！
B.我正在说假话。
C.您吃饭了吗？
D.火星上有生命。
答案：D
11、下列语句不是命题的有（ ）
A.我正在说假话。
B.3<5
C.我学英语或法语。
D.1+101=110
答案：A
12、下列语句是真命题的有（ ）
A.1+101=110
B.火星上有生命。
C.2+5=7
D.π是有理数。
答案：C
13、下列语句是假命题的有（ ）
A.1+101=110
B.火星上有生命。
C.2+5=7
D.π是有理数。
答案：D
14、下列语句中是原子命题的有（ ）
A.豆包是由红豆和面粉做出来的。
B.2是偶素数
C.3是偶素数
D.2或4是素数
答案：A
15、下列公式中不是合取范式的是( )。
A.p∧q
B.﹁p
C.p∨(﹁p∧r)
D.p∨q∨r
答案：C
16、命题公式﹁(﹁P∨q)∧q的类型是（ ）
A.永真式
B.永假式
C.非重言式的可满足式
D.以上均不对
答案：B
17、设命题公式G：¬p→(q∧r)，则使公式G取真值为1的P，Q，R赋值分别是 ( )
A.0,0,0
B.0,0,1
C.0,1,0
D.1,0,0
答案：D
18、下列公式 ( )为重言式
A. ¬P∧¬Q↔P∨Q
B.(Q→(P∨Q))↔(¬Q∧(P∨Q))
C.(P→(¬Q→P))↔(¬P→(P→Q))
D.(¬P∨(P∧Q))↔Q
答案：C
二、多选
19、下列语句中是复合命题的有（ ）
A.豆包是由红豆和面粉做出来的。
B.2是偶素数
C.3是偶素数
D.2或4是素数
答案：BCD
20、下列语句中哪些复合命题的真值为真（ ）
A.豆包是由红豆和面粉做出来的。
B.2是偶素数
C.3是偶素数
D.2或4是素数
答案：BD
21、下列语句中哪些复合命题的真值为假（ ）
A.π是无理数是不对的。
B.2是偶素数
C.3是偶素数
D.2或4是素数
答案：AC
22、命题公式¬(¬p∨q)∧q的成假赋值有（ ）
A.00
B.01
C.10
D.11
答案：ABCD
23、令命题p:太阳从东边升起；q:2+2=4；r:乌鸦是白色的，则下列公式（ ）的真值为真
A.((p∨q)∧r)→q
B.¬p→(p∨q)∧r
C.((p∨q)∧(r→q)
D.¬p→(p∨q∧r)
答案：BCD
24、公式¬p→q的成真赋值为（ ）
A.00
B.01
C.10
D.11
答案：BC
25、公式¬p→q的成假赋值为（ ）
A.00
B.01
C.10
D.11
答案：AD
三、判断
26、 语句“火星上有生命”是一个命题。 A.正确 B.错误 答案：A
27、若一个命题公式A是一个重言式，那么它一定是个可满足式。 A.正确 B.错误 答案：A
一、 单选 1、一个公式在等值的意义下，下面哪个写法是唯一的 A.析取范式 B.合取范式 C.主析取范式 D.以上都不对 答案：C
2、若某意命题公式含有3个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成真赋值有（ ） A.000,001 B.010，011 C.100101 D.110111 答案：A
3、若公式A的主析取范式含全部2n个极小项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：A
4、若公式A的主合取范式不含任何极大项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：A
5、若公式A的主合析取范式含全部2n个极大项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：B
6、若公式A的主析取范式不含任何极小项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：B
7、若公式A的主析取范式中至少含一个、但不是全部极小项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：C
8、若公式A的主合取范式中至少含一个、但不是全部极大项，则A的公式类型为（ ） A.永真式 B.永假式 C.非重言式的可满足式 D.以上均不对 答案：C
9、命题公式P∨Q的合取范式是 ( ) A.P∧Q B.（P∧Q）∨（P∨Q） C.P∨Q D.﹁（﹁P∧﹁Q） 答案：C
10、下列公式成立的为( ) A.﹁P∧﹁Q⇔P∨QB B.P→﹁Q⇔﹁P→Q C.Q→P⇒P D.﹁P∧(P∨Q)⇒Q 答案：D
二、 多选 11、 若某意命题公式含有2个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成假赋值有（ ） A.00 B.01 C.10 D.11 答案：CD
12、 若某意命题公式含有2个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成真赋值有（ ） A.00 B.01 C.10 D.11 答案：AB
13、 若某意命题公式含有3个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成假赋值有（ ） A.000,001 B.010，011 C.100101 D.110111 答案：BCD
14、 若某意命题公式含有2个命题变元，该公式的成假赋值有00,01，则该公式主析取范式所含有的极小项是（ ） A.m0 B.m1 C.m2 D.m3 答案：AB
15、设A有3个命题变项, 且已知A的主析取范式= m1∨m3∨m7，则下列描述正确的是（ ） A.A的成真赋值有001,011,111 B.A的成假赋值有001,011,111 C.A的成假赋值有000,010,100,101,110 D.A是一个非重言式的可满足式 答案：ACD
16、设A有3个命题变项, 且已知A的主合取范式= M0∧M2∧M4∧M5∧M6，则下列描述正确的是（ ） A.A的成真赋值有001,011,111 B.A的主析取范式是 m1∨m3∨m7 C.A的成假赋值有000,010,100,101,110 D.A是一个非重言式的可满足式 答案：ABCD
17、自然推理系统中构造证明的方法主要有（ ） A.直接证明法 B.附加前提证明法 C.归谬法 D.以上均不对 答案：ABC
一、 单选 1、设 P(x)：x是人， F(y):y是机器智能，H(x,y):x比y聪明，则自然语言“说人比所有机器智能都聪明是不对的”的符号化形式为（ ） A.﹁∀x∀y(p(x)→(F(y)→H(x,y))) B.∃x∃y(p(x)∧F(y)∧H(x,y)) C.﹁∀x(p(x)→∀y(F(y)→H(x,y))) D.∃x(p(x)∨∀y(F(y)→H(x,y))) 答案：C
2、设个体域{1,2},对公式∀xF(x)→彐yG(y)消去量词后为（ ） A.(F(1)∧F(2))→(G(1)∧G(2)) B.(F(1)∧F(2))→(G(1)∨G(2)) C.(F(1)∨F(2))∨(G(1)∧G(2)) D.(F(1)∨F(2))→(G(1)∨G(2)) 答案：B
3、谓词公式∀y∀x(P(x)→R(x,y))∧∃xQ(x,y)中变元y（ ） A.是自由变元但不是约束变元 B.是约束变元但不是自由变元 C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元 答案：C
4、设P(x): x是简单回路，H(x): x是初级回路，则 “简单回路未必都是初级回路”在一阶逻辑中的符合化形式为（ ） A.∀x(P(x)→H(x)) B.∃x(P(x)∧¬H(x)) C.∀x(P(x)→¬H(x)) D.∃x(P(x)∧H(x)) 答案：B
5、给定解释I如下：个体域D={3,4}；F(x,y):F(3,3)=F(4,4)=0, F(3,4)=F(4,3)=1.则在I下公式∀x∃yF(x,y)和∃x∀yF(x,y)的真值分别为（ ） A.0,0 B.0,1 C.1,0 D.1,1 答案：C
6、 F(x): x是人, G(x): x呼吸，自然语言“没有不呼吸的人”可符号化表示为（ ） A.﹁∃x(F(x)∧﹁G(x)) B.﹁∀x(F(x)→G(x)) C. ﹁∃x(F(x)→﹁G(x)) D.﹁∀x(F(x)∧G(x)) 答案：A
7、设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ ） A. ∀(x)(A(x)∧B(x)) B.﹁∃(x)(A(x)∧B(x)) C.﹁∀(x)(A(x)→B(x)) D.﹁∃(x)(A(x)﹁B(x)) 答案：C
8、给定解释 I 如下: (a)个体域D={2,3};(b)D中特定元素a=2;(c)D上的特定谓词F(x):F(2)=0, F(3)=1;G(x,y):G(2,2)=G(2,3)=G(3,2)=1,G(3,3)=0,在I下公式∀x(F(x)∧G(x,a))的真值是（ ） A.1 B.0 C.无 D.以上均不对 答案：B
二、判断
1、个体域不同，谓词公式的真值可能不同。 A.正确 B.错误 答案：A
1、在一阶逻辑中给出下面两个推理，______是正确的。 （1） 前提：∀x(F(x)→G(x)) ，∃yF(y) 结论：∃yG(y)；（2） 前提：∃x(F(x)∧G(x)) 结论：∀yF(y) A.（1） B.（2） C.（1）（2） D.都不正确 答案：A
2、公式∀xF(x)→彐y(G(y)∧H(x,y)) 的前束范式为（ ） A.∀t∀y(F(t)→(G(y)∧H(x,y))) B.∀x∃y(F(x)→(G(y)∧H(x,y))) C.∃t∃y(F(t)→(G(y)∧H(x,y))) D.∃t∃y(F(t)→(G(y)∧H(t,y))) 答案；C
3、在谓词公式(∀x)(A(x)→B(x)∨C(x.y))中，（ ） A.x，y都是约束变元 B.x，y都是自由变元 C.x是约束变元，y都是自由变元 D.x是自由变元，y都是约束变元 答案：C
4、谓词公式∃x(F(x,y,z)→∀y(G(x,y)∧H(x,y,z)))中，∃x的辖域是（ ） A.F(x,y,z) B.G(x,y)∧H(x,y,z) C.G(x,y) D.F(x,y,z)→（G(x,y)∧H(x,y,z)） 答案：B
二、 多选
5、下列谓词公式（ ）是前束范式 A.∀x(F(x)→∃y(G(y)∧H(x,y))) B.﹁∃x(F(x)∧G(x)) C.∀x﹁(F(x)∧G(x)) D.∀x∃y(F(x)→(G(y)∧H(x,y))) 答案：CD
6、下列（ ）是谓词公式﹁∃x(M(x)∧F(x))的前束范式 A.∀x(﹁M(x)∨﹁F(x)) B.∀x(M(x)→﹁F(x)) C.∃x﹁(M(x)∧F(x)) D.∀x﹁(M(x)∧F(x)) 答案：ABD
三、判断
7、在推导过程中，如既要使用US又要使用ES消去量词，而且选用个体是同一个符号，则必须先试用ES，再使用US。 A.正确 B.错误 答案：A
8、在一阶逻辑中，∀与∃是可以交换位置的，不会影响原命题的真值情况。 A.正确 B.错误 答案：B
一、 单选 1、若集合A={a，b}，B={ a，b，{ a，b }}，则（ ）． A. A⊂B，且A∈B B. A∈B，但A⊄B C. A⊂B，但A∉B D. A⊄B，且A∉B 答案：A
2、若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）． A. B⊂A，且B∈A B. B∈A, 但B⊄A C. B⊂A, 但B∉A D. B⊄A, 且B∉A 答案：B
3、若集合A的元素个数为10，则其幂集的元素个数为（ ） A.1024 B.100 C.10 D.1 答案：A
4、设集合A = {1, a }，则P(A) = ( )． A.{{1}, {a}} B.{∅,{1}, {a}} C.{∅,{1}, {a}, {1, a }} D.{{1}, {a}, {1, a }} 答案：C
5、设集合A = {∅, {∅}}，则P(A) = ( )． A.{∅, {∅}} B.{∅, {∅, {∅}} ,{∅}} C.{ {∅, {∅}}, {{∅}},{∅},∅} D.{{∅, {∅}}, {{{∅}}},{{∅}},∅} 答案：C
6、设A={1,2,3,4,5},下面()集合等于A 。 A.{1,2,3,4,5,6} B.{x|x是整数且x≤5} C.{x|x是自然数且x≤5} D.{x|x是正整数且x≤5} 答案：D
7、设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( ) A.{2}∈A B.{a}⊆A C. ∅⊆{{a}}⊆B⊆E D. {{a},1,3,4}⊂B 答案：C
8、设A={1,3,5}，B={1,2,3}，则A∩B=（ ） A.{1,3} B.{1,2,3,5} C.{5} D.{2,5} 答案：A
9、设A={1,3,5}，B={1,2,3}，则A∪B=（ ） A.{1,3} B.{1,2,3,5} C.{5} D.{2,5} 答案：B
10、设A={1,3,5}，B={1,2,3}，则A-B=（ ） A.{1,3} B.{1,2,3,5} C.{5} D.{2,5} 答案：C
11、设A={1,3,5}，B={1,2,3}，则A⊕B=（ ） A.{1,3} B.{1,2,3,5} C.{5} D.{2,5} 答案：D
二、 多选 12、若A= {1,2}，则A的子集有（ ） A.空集 B.{1} C.{2} D.{1,2} 答案：ABCD
三、判断
13、若Aimage.pngB ,Bimage.pngC ,则A⊆ C。 A.正确 B.错误 答案：A
14、空集是任何集合的子集。 A.正确 B.错误 答案：A
15、若A-B = A，那么B=∅。 A.正确 B.错误 答案：B
16、若A = {x}∪x，则 x∈A且⊆ A。 A.正确 B.错误 答案：A
17、若A∪B=A ，那么B=∅。 A.正确 B.错误 答案：B
一、 单选 1、设X={a,b,c}，Y={1,2,3}，定义f={<a,1>,<b,2>,<c,3>}，则下列命题中正确的是（ ） A.f是从X到Y的二元关系，但不是从X到Y的函数 B.f是从X到Y的函数，但不是满射函数，也不是单射函数 C.f是从X到Y的满射函数，但不是单射函数 D.f是从X到Y的双射函数 答案：D
2、设 A={1,2,3,4,5,6,7}, 定义A上的关系R：R={<x,y>| x,y∈A∧x ≡ y(mod 3)}, 其中x ≡ y(mod 3)叫做 x与 y 模3相等，则由R产生的等价类有（ ）个。 A.1 B.2 C.3 D.4 答案：C
3、设集合A={1 , 2 , 3 , 4}上的二元关系,R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>,},则S是R的（ ）闭包。 A.自反 B.对称 C.传递 D.以上都不对 答案：C
4、 设S={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉}，则R▫R=（ ）。 A.{〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉} B.{〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉} C.{〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉} D.{〈1,2〉,〈2,3〉,〈3,4〉,〈2,4〉} 答案：A
5、设集合A={1,2,3,4},A上的等价关系R={<1,1>,<3,2>,<2,3>,<4,4>}∪IA，则对应于R的划分是（）。 A.{{1},{2,3},{4}} B.{{1,3},{2,4}} C.{{1,3},{2},{4}} D.{{1},{2},{3},{4}} 答案：A
6、 设A={1,2,3,…,50}，R是A上相等关系“=”，由R产生等价类有（ ）。 A.10个 B.25个 C.50个 D.1个 答案：C
7、设R={<0,1>,<0,2><1,2>,<1,3>,<2,3>},则domR=（ ） A.{0,1,2} B.{1,2,3} C.{0,1,2,3} D.∅ 答案：A
8、设R={<0,1>,<0,2><1,2>,<1,3>,<2,3>},则ranR=（ ） A.{0,1,2} B.{1,2,3} C.{0,1,2,3} D.∅ 答案：B
9、设R={<0,1>,<0,2><1,2>,<1,3>,<2,3>},则fldR=（ ） A.{0,1,2} B.{1,2,3} C.{0,1,2,3} D.∅ 答案：C
10、 设A={1，2，3}，则A上的二元关系有（ ）个 A.2³ B.3² C.2³*³ D.3²*² 答案：C
11、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y∈A},则R 的性质为( )。 A.自反的 B.对称的 C.自反的，对称的 D.传递的 答案：B
12、 等价关系一定不是（ ） A.对称的 B.自反的 C.反自反的 D.可传递的 答案：C
13、如果R1和R2是集合A上的自反关系，则R1∪R2, R1∩R2, R1―R2中自反关系有（ ）个 A.0 B.1 C.2 D.3 答案：C
14、 设集合A=｛a,b,c｝，B=｛1,2,3,4｝，作f：A→B，则不同的函数个数为（ ）个 A.12 B.81 C.64 D.以上均不对 答案：C
15、 设集合A={1,2,3,4}，则A中的划分有（ ）个 A.4 B.9 C.15 D.16 答案：C
16、设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a,b>êa , b∈A , 且a +b = 8}，则R具有的性质为（ ） A.自反的 B.对称的 C.对称的且传递的 D.反自反的且传递的 答案：B
17、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( ) A.8、2、8、2 B.无、2、无、2 C.6、2、6、2 D.8、1、6、1 答案：B
18、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的极小元为 ( ) A.2 B.4 C.6 D.无 答案：A
19、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最小上界为 ( ) A.2 B.4 C.6 D.无 答案：D
20、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大下界为 ( ) A.2 B.4 C.6 D.无 答案：A
21、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最大元、最小元、上界、下界依次为 ( ) A.8、1、8、1 B.无、1、无、1 C.7、1、7、1 D.8、1、7、1 答案：B
22、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的极小元为 ( ) A.1 B.8 C.7 D.无 答案：A
23、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最小上界为 ( ) A.1 B.8 C.7 D.无 答案：D
24、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最大下界为 ( ) A.1 B.8 C.7 D.无 答案：A
25、A={1,2,3}, R1, R2, R3，R4是A上的关系, 其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<2,2>,<3,3>,<1,2>}，R3＝{<1,3>}，R4＝∅，关系（ ）具有自反性。 A.R1 B.R2 C.R3 D.R4 答案：B
26、设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系, 其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}，R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}，关系（ ）具有反对称性。 A.R1 B.R2 C.R3 D.R4 答案：C
27、设A={1,2,3}，R={<1,2>,<2,2>}，R'={<1,2>,<2,2>,<1,1>,<3,3>,<4,4>}，R和R'都是A上的关系，则R'是R的（ ） A.自反闭包 B.对称闭包 C.传递闭包 D.以上均不正确 答案：A
28、设A={1，2,3}，R是A上的等价关系，R={<1,2>,<2,1>}∪IA，则A关于R的等价类有（ ）个。 A.0 B.1 C.2 D.3 答案：C
29、 设A={1，2,3}，R是A上的等价关系，R=IA，则A关于R的等价类有（ ）个。 A.0 B.1 C.2 D.3 答案：D
30、 设 A＝{ a, b, c, d }, 以下（ ）是A的划分 A.π1={{ a, b, c },{ d }} B.π2{{ a }, { a, b, c, d }} C.π3={{ a, b}, { c }} D.π4={Æ,{ a, b }, { c, d }} 答案：A
31、 π={{1,2}，{3}}是A={1,2,3}的一个划分，则该划分对应的等价关系R是（ ） A.{<2,3>,<3,2>}∪IA B.{<1,3>,<3,1>}∪IA C.{<1,2>,<2,1>}∪IA D.以上均不正确 答案：C
32、 设I={2,3,6,8}，关系R为I上的整除关系，则R是一个（ ） A.等价关系 B.偏序关系 C.全序关系 D.相容关系 答案：B
33、 设集合A上的一个关系R，其关系图中每个结点都含有环，则关系R一定具有（ ）性质 A.自反 B.对称 C.传递 D.反对称 答案：A
34、 等价关系的关系图是由若干个独立子图构成的，且每一个独立子图是一个（ ） A.空关系 B.恒等关系 C.全域关系 D.以上均不正确 答案：C
35、 若集合A上的等价关系R的关系图中含有3个独立子图，则集合A关于R的不同的等价类数量是（ ） A.1 B.2 C.3 D.6 答案：C
二、 多选 36、给定集合A={1,2,3,4,5}，A上的关系S={<1,1>,<2,3>,<3,3>}，则关系S的性质有（ ）。 A.自反性 B.对称性 C.反对称性 D.传递性 答案：CD
37、 等价关系具有（ ） A.自反性 B.对称性 C.反对称性 D.传递性 答案：ABD
38、 偏序关系具有（ ） A.自反性 B.反对称性 C.对称性 D.传递性 答案：ABD
39、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的极大元为 ( ) A.2 B.4 C.6 D.无 答案：BC
40、 设A={1,2}，B={a,b},则（ ）是A×B中的有序对 A.<1,a> B.<2,a> C.<1,b> D.<2,b> 答案：ABCD
41、若A={0,1}, B={2,3}, 那么R1={<0,2>},R2=A×B,R3=∅,R4={<0,1>}中，（ ）是A上的二元关系 A.R1 B.R2 C.R3 D.R4 答案：ABC
42、若A={0,1}, B={2,3}, 那么R1={<0,2>},R2=A×B,R3=∅,R4={<0,1>}中，（ ）是从A到B上的二元关系 A.R1 B.R2 C.R3 D.R4 答案：CD
43、A={1,2,3}, R1, R2, R3，R4是A上的关系, 其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<2,2>,<3,3>,<1,2>}，R3＝{<1,3>}，R4＝∅，关系（ ）具有反自反性。 A.R1 B.R2 C.R3 D.R4 答案：CD
44、设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系, 其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}，R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}，关系（ ）具有对称性。 A.R1 B.R2 C.R3 D.R4 答案：AB
45、 设A={1，2,3}，R是A上的等价关系，R=IA，则A关于R的等价类有（ ）。 A.{1} B.{2} C.{3} D.以上均不正确 答案：ABC
46、 设I={2,3,6,8}，关系R为I上的整除关系，则R具有（ ）性质 A.自反 B.对称 C.反对称 D.传递 答案：ACD
47、若偏序集<A,R>的哈斯图中有一个孤立节点a,则a一定是集合A的（ ） A.最大元 B.最小元 C.极大元 D.极小元 答案：CD
48、 关于关系的性质，描述错误的有（ ） A.有些关系可能既不是自反的也不是反自反的 B.可能既不具有对称性，也不具有反对称性 C.若一个关系不是自反的，则它一定是反自反的 D.若一个关系不具有对称性，则一定具有反对称性 答案：CD
49、 下列描述正确的有（ ） A.恒等关系具有自反性 B.恒等关系具有反对称性 C.恒等关系具有对称性 D.恒等关系具有传递性 答案：ABCD
50、 下列描述正确的有（ ） A.空关系具有自反性 B.空关系具有对称性 C.空关系具有反自反性 D.空关系具有反对称性 答案：BCD
三、判断
51、若A×C = B×D，那么A=B,C=D。 A.正确 B.错误 答案：B
52、若A⊆ C∧B⊆D，则A×B⊆C×D。 A.正确 B.错误 答案：A
53、若若一个关系R不是自反的，那么它一定是反自反的。 A.正确 B.错误 答案：B
54、有些关系可能既是自反的，也是反自反的。 A.正确 B.错误 答案：B
55、有些关系可能既是对称的，也是反对称的。 A.正确 B.错误 答案：A
56、有些关系可能既不是对称的，也不是反对称的。 A.正确 B.错误 答案：A
57、有些关系可能既是自反的，也是反自反的。 A.正确 B.错误 答案：B
58、有些关系可能什么性质都没有。 A.正确 B.错误 答案：A
59、在一个偏序关系中，最小元一定是极小元；最大元一定是极大元。 A.正确 B.错误 答案：A
一、 单选 1、一个无向图G=<V,E>,其中|V|=4，|E|=5，则对图G的描述错误的是（ ） A.G是一个4阶图 B.G中含有5条边 C.G中结点度数和是10 D.G中结点度数和是8 答案：D
2、一个无向图G=<V,E>,其中V={v1,v2,v3,v4}，图G的度数列为（1,3,2,0），则对图G中的悬挂结点是（ ） A.v1 B.v2 C.v3 D.v4 答案：A
3、一个无向图G=<V,E>,其中V={v1,v2,v3,v4}，图G的度数列为（1,3,2,0），则对图G中的孤立结点是（ ） A.v1 B.v2 C.v3 D.v4 答案：D
4、设无向图连通图G＝<V,E>,若{v2,v4},{v3},{v5}是图G的点割集，则G的点连通度是（ ） A.0 B.1 C.2 D.4 答案：B
5、设无向图连通图G＝<V,E>,若{e6},{e5},{e2,e3}是图G的边割集，则G的边连通度是（ ） A.0 B.1 C.2 D.4 答案：B
6、 关于图的边连通度，下列说法错误的是（ ） A.非连通图的边连通度是0 B.平凡图的边连通度是0 C.n阶无向完全图的边连通度是n-1 D.若图G是一个r边连通图，则在删去r-1条边后，图G变得不连通 答案：D
7、 设无向图G有16条边且每个顶点的度数都是2，则图G有（ ）个顶点 A.10 B.4 C.8 D.16 答案：D
8、 设无向图G有18条边且每个顶点的度数都是3，则图G有（ ）个顶点 A.10 B.4 C.8 D.12 答案：D
9、 无向完全图K4是（ ） A.欧拉图 B.哈密顿图 C.树 D.以上均不正确 答案：B
10、 下面四组数能构成无向简单图的度数列的有（ ）。 A.（2，2，2，2，2） B.（1，1，2，2，3） C.（1，2，2，2，2） D.（0，1，3，3，3） 答案：A
11、 设G是简单有向图,可达矩阵P(G)刻划下列 ( )关系。 A.点与边 B.边与点 C.点与点 D.边与边 答案：C
12、 在有n个顶点的连通图中,其边数( ) A.最多有n-1条 B.至少有n-1 条 C.最多有n条 D.至少有n 条 答案：B
13、 若图G中含有平行边，则G是（ ） A.多重图 B.平凡图 C.线图 D.简单图 答案：A
14、 一个n阶无向完全图G中含有m条边，以下数量关系正确的是（ ） A.m=n-1 B.m=2n C.m=n(n-1) D.m=n(n-1)/2 答案：D
15、 一个n阶有向完全图G中含有m条边，以下数量关系正确的是（ ） A.m=n-1 B.m=2n C.m=n(n-1) D.m=n(n-1)/2 答案：C
16、 一个4阶有向图的度数列为(1,4,3,4)，出度列为(0,3,1,2),则其入度列为（ ） A.(1,7,4,6) B.(1,1,2,2) C.(1,1,4,2) D.(1,7,2,6) 答案：B
17、 设图G为5阶图，该图中有4条边，已知其中四点的度数为1,3,0,2，则第五点的度数为（ ） A.1 B.2 C.3 D.4 答案：B
18、 一个4阶有向图的度数列为(1,4,3,5)，则该图的最大度为（ ） A.1 B.4 C.3 D.5 答案：D
19、 设图G为5阶图，该图中有4条边，则该图中所有结点度数和为（ ） A.1 B.8 C.9 D.10 答案：B
20、 下面四组（ ）可以成为图的度数列 A.（2，2，2，2，2） B.（1，1，2，2，3） C.（1，2，2，2，2） D.（0，2，3，3，3） 答案：A
21、 在所有的n阶无向图中，n阶零图的连通分支数是（ ） A.2 B.n C.n-1 D.1 答案：B
二、 多选 22、一个无向图G=<V,E>,其中E={e1, e2, e3}，e1=(v1,v2), e2=(v1,v2), e3=<v3,v2>, 则对图G的描述错误的是（ ） A.G是一个有向图 B.G是一个无向图 C.e1与e2是平行边 D.G是一个简单图 答案：ABD
23、一个无向图G=<V,E>,其中V={v1,v2,v3,v4}，图G的度数列为（1,3,2,0），则对图G描述正确的是（ ） A.图G中含有3条边 B.图G中含有环 C.图G中含有平行边 D.图G是一个非连通图 答案：ACD
24、关于有向图的关联矩阵，描述正确的是（ ） A.矩阵当中的每一列的和均是2 B.矩阵中每一行的元素和为对应结点的度数 C.若矩阵中含有相同列，则表示图中含有平行边 D.矩阵中所有元素的和为0 答案：ABC
25、关于无向图的关联矩阵，描述正确的是（ ） A.矩阵中每一列的元素和是0 B.矩阵中每一行的元素和是0 C.若矩阵中含有相同列，则表示图中含有平行边 D.矩阵中所有元素的和为0 答案：ABCD
26、关于有向图的邻接矩阵，描述正确的是（ ） A.矩阵中每一列的元素和表示对应结点的出度 B.矩阵中每一行的元素和表示对应结点的入度 C.矩阵中每一列的元素和表示对应结点的入度 D.矩阵中每一行的元素和表示对应结点的出度 答案：CD
27、设无向图连通图G＝<V,E>,若{v2,v4},{v3},{v5}是图G的点割集，则下列描述正确的是（ ） A.点v2不是割点 B.点v3是割点 C.点v5是割点 D.{v2,v5}是图G的点割集 答案：ABC
28、设无向图连通图G＝<V,E>,若{e6},{e5},{e2,e3}是图G的边割集，则下列描述正确的是（ ） A.e6是割边 B.e5是桥 C.e2、e3是割边 D.{e2,e5}是图G的边割集 答案：AB
三、判断
29、平凡图只有一个顶点，没有边。 A.正确 B.错误 答案：A
30、任何图 (无向或有向) 中，奇度顶点的个数是偶数。 A.正确 B.错误 答案：A
31、在一个无向简单图中，圈的长度是≥3的。 A.正确 B.错误 答案：A
32、平凡图不具有连通性。 A.正确 B.错误 答案：B
33、任意一个图中，所有节点度数的和是一个偶数。 A.正确 B.错误 答案：A
34、若图G'是图G的生成子图，则G'一定是G的真子图。 A.正确 B.错误 答案：B
35、图G是自身的子图。 A.正确 B.错误 答案：A
36、若在图G中两个结点是相邻的，那么它们在G的补图中一定不相邻 A.正确 B.错误 答案：A
37、若图G是一个r边连通图，则在删去r-1条边后，图G变得不连通 A.正确 B.错误 答案：B
38、在有向图D中，结点V总是可达自身的。 A.正确 B.错误 答案：A
39、若有向图D是一个强连通图，那么图中任意两个结点是相互可达的。 A.正确 B.错误 答案：A
40、若有向图D是一个单向连通图，那么图中任意两个结点是相互可达的。 A.正确 B.错误 答案：B
41、若有向图D是一个强连通图，那么它的可达矩阵是一个全1矩阵。 A.正确 B.错误 答案：A
42、组{1，2, 3, 4, 4}是一个能构成无向简单图的度数序列。 A.正确 B.错误 答案：B
43、若一个命题公式A是一个重言式，那么它一定是个可满足式。 A.正确 B.错误 答案：A
一、 单选 1、设T是无向连通图G的一棵生成树，生成树T的树枝有4条，弦有3条，则图G的圈秩是（ ） A.1 B.3 C.4 D.7 答案：B
2、设T是无向连通图G的一棵生成树，生成树T的树枝有4条，弦有3条，则图G的割集秩是（ ） A.1 B.3 C.4 D.7 答案：C
3、设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树. A.m-n+1 B.m-n C.m+n+1 D.n-m+1 答案：A
4、无向简单图G是棵树，当且仅当( ) A.G连通且边数比结点数少1 B.G连通且结点数比边数少1 C.G的边数比结点数少1 D.G中没有回路 答案：A
5、设连通图G=<V,E>，则G的生成树有（ ）棵 A.0 B.1 C.2 D.不能确定 答案：D
6、若一棵完全二叉树有2n-1个顶点，则它有（ ）片树叶。 A.n B.2n C.n-1 D.2 答案：A
7、下列哪一种图不一定是树（ ） A.无简单回路的连通图 B.有n个顶点n-1条边的连通图 C.每对顶点间都有通路的图 D.连通但删去一条边便不连通的图 答案：C
8、已知无向树T中，2度有2个，3度顶点有2个，1个4度顶点，其余顶点均为树叶，求T的边数m为( ) A.10 B.6 C.11 D.7 答案：A
9、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度结点。 A.1 B.2 C.3 D.4 答案：A
10、前缀表达式+ - *33*425的值（ ） A.0 B.1 C.6 D.7 答案：C
11、连通图G是一棵树当且仅当G中( )。 A.有些边是割边 B.每条边都是割边 C.所有边都不是割边 D.图中存在一条欧拉路径 答案：B
12、一颗树有两个2度结点,1个3度结点和3个4度结点,则1度结点数为( )。 A.5 B.7 C.9 D.8 答案：C
13、设G是一棵树,则G 的生成树有( )棵。 A.0 B.1 C.2 D.不能确定 答案：B
14、设G=<V,E>是n阶m条边的无向图，并且G是一棵树，则下列描述正确的是（ ） A.m=n+1 B.m=n-1 C.n=2m D.m=2n 答案：B
15、若图G的最小生成树T中，各边的权值是1,2,3,3,4,7，那么该最小生成树的权为（ ） A.20 B.17 C.1 D.以上均不正确 答案：A
16、带权为1, 1, 2, 3的最有二叉树的权为（ ） A.7 B.13 C.20 D.以上均不正确 答案：B |
