河南财经政法大学成教【离散数学】高起专教学计划
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,001B.010，011C.100101D.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∧QB.（P∧Q）∨（P∨Q）C.P∨QD.﹁（﹁P∧﹁Q）答案：C
10、下列公式成立的为( )A.﹁P∧﹁Q⇔P∨QBB.P→﹁Q⇔﹁P→QC.Q→P⇒PD.﹁P∧(P∨Q)⇒Q答案：D
二、 多选 11、 若某意命题公式含有2个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成假赋值有（ ）A.00B.01C.10D.11答案：CD
12、 若某意命题公式含有2个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成真赋值有（ ）A.00B.01C.10D.11答案：AB
13、 若某意命题公式含有3个命题变元，该公式的主析取范式所含有的极小项是m0、m1，则该命题公式的成假赋值有（ ）A.000,001B.010，011C.100101D.110111答案：BCD
14、 若某意命题公式含有2个命题变元，该公式的成假赋值有00,01，则该公式主析取范式所含有的极小项是（ ）A.m0B.m1C.m2D.m3答案：AB
15、设A有3个命题变项, 且已知A的主析取范式= m1∨m3∨m7，则下列描述正确的是（ ）A.A的成真赋值有001,011,111B.A的成假赋值有001,011,111C.A的成假赋值有000,010,100,101,110D.A是一个非重言式的可满足式答案：ACD
16、设A有3个命题变项, 且已知A的主合取范式= M0∧M2∧M4∧M5∧M6，则下列描述正确的是（ ）A.A的成真赋值有001,011,111B.A的主析取范式是 m1∨m3∨m7C.A的成假赋值有000,010,100,101,110D.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,0B.0,1C.1,0D.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.1B.0C.无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∈BB. A∈B，但A⊄BC. A⊂B，但A∉BD. A⊄B，且A∉B答案：A
2、若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）．A. B⊂A，且B∈AB. B∈A, 但B⊄AC. B⊂A, 但B∉AD. B⊄A, 且B∉A答案：B
3、若集合A的元素个数为10，则其幂集的元素个数为（ ）A.1024B.100C.10D.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}∈AB.{a}⊆AC. ∅⊆{{a}}⊆B⊆ED. {{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.1B.2C.3D.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.0B.1C.2D.3答案：C
14、 设集合A=｛a,b,c｝，B=｛1,2,3,4｝，作f：A→B，则不同的函数个数为（ ）个A.12B.81C.64D.以上均不对答案：C
15、 设集合A={1,2,3,4}，则A中的划分有（ ）个A.4B.9C.15D.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、2B.无、2、无、2C.6、2、6、2D.8、1、6、1答案：B
18、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的极小元为 ( )A.2B.4C.6D.无答案：A
19、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最小上界为 ( )A.2B.4C.6D.无答案：D
20、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大下界为 ( )A.2B.4C.6D.无答案：A
21、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最大元、最小元、上界、下界依次为 ( )A.8、1、8、1B.无、1、无、1C.7、1、7、1D.8、1、7、1答案：B
22、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的极小元为 ( )A.1B.8C.7D.无答案：A
23、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最小上界为 ( )A.1B.8C.7D.无答案：D
24、 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，则集合A的最大下界为 ( )A.1B.8C.7D.无答案：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.R1B.R2C.R3D.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.R1B.R2C.R3D.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.0B.1C.2D.3答案：C
29、 设A={1，2,3}，R是A上的等价关系，R=IA，则A关于R的等价类有（ ）个。A.0B.1C.2D.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>}∪IAB.{<1,3>,<3,1>}∪IAC.{<1,2>,<2,1>}∪IAD.以上均不正确答案：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.1B.2C.3D.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.2B.4C.6D.无答案：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.R1B.R2C.R3D.R4答案：ABC
42、若A={0,1}, B={2,3}, 那么R1={<0,2>},R2=A×B,R3=∅,R4={<0,1>}中，（ ）是从A到B上的二元关系A.R1B.R2C.R3D.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.R1B.R2C.R3D.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.R1B.R2C.R3D.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中结点度数和是10D.G中结点度数和是8答案：D
2、一个无向图G=<V,E>,其中V={v1,v2,v3,v4}，图G的度数列为（1,3,2,0），则对图G中的悬挂结点是（ ）A.v1B.v2C.v3D.v4答案：A
3、一个无向图G=<V,E>,其中V={v1,v2,v3,v4}，图G的度数列为（1,3,2,0），则对图G中的孤立结点是（ ）A.v1B.v2C.v3D.v4答案：D
4、设无向图连通图G＝<V,E>,若{v2,v4},{v3},{v5}是图G的点割集，则G的点连通度是（ ）A.0B.1C.2D.4答案：B
5、设无向图连通图G＝<V,E>,若{e6},{e5},{e2,e3}是图G的边割集，则G的边连通度是（ ）A.0B.1C.2D.4答案：B
6、 关于图的边连通度，下列说法错误的是（ ）A.非连通图的边连通度是0B.平凡图的边连通度是0C.n阶无向完全图的边连通度是n-1D.若图G是一个r边连通图，则在删去r-1条边后，图G变得不连通答案：D
7、 设无向图G有16条边且每个顶点的度数都是2，则图G有（ ）个顶点A.10B.4C.8D.16答案：D
8、 设无向图G有18条边且每个顶点的度数都是3，则图G有（ ）个顶点A.10B.4C.8D.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-1B.m=2nC.m=n(n-1)D.m=n(n-1)/2答案：D
15、 一个n阶有向完全图G中含有m条边，以下数量关系正确的是（ ）A.m=n-1B.m=2nC.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.1B.2C.3D.4答案：B
18、 一个4阶有向图的度数列为(1,4,3,5)，则该图的最大度为（ ）A.1B.4C.3D.5答案：D
19、 设图G为5阶图，该图中有4条边，则该图中所有结点度数和为（ ）A.1B.8C.9D.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.2B.nC.n-1D.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.矩阵当中的每一列的和均是2B.矩阵中每一行的元素和为对应结点的度数C.若矩阵中含有相同列，则表示图中含有平行边D.矩阵中所有元素的和为0答案：ABC
25、关于无向图的关联矩阵，描述正确的是（ ）A.矩阵中每一列的元素和是0B.矩阵中每一行的元素和是0C.若矩阵中含有相同列，则表示图中含有平行边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.1B.3C.4D.7答案：B
2、设T是无向连通图G的一棵生成树，生成树T的树枝有4条，弦有3条，则图G的割集秩是（ ）A.1B.3C.4D.7答案：C
3、设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树.A.m-n+1B.m-nC.m+n+1D.n-m+1答案：A
4、无向简单图G是棵树，当且仅当( )A.G连通且边数比结点数少1B.G连通且结点数比边数少1C.G的边数比结点数少1D.G中没有回路答案：A
5、设连通图G=<V,E>，则G的生成树有（ ）棵A.0B.1C.2D.不能确定答案：D
6、若一棵完全二叉树有2n-1个顶点，则它有（ ）片树叶。A.nB.2nC.n-1D.2答案：A
7、下列哪一种图不一定是树（ ）A.无简单回路的连通图B.有n个顶点n-1条边的连通图C.每对顶点间都有通路的图D.连通但删去一条边便不连通的图答案：C
8、已知无向树T中，2度有2个，3度顶点有2个，1个4度顶点，其余顶点均为树叶，求T的边数m为( )A.10B.6C.11D.7答案：A
9、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度结点。A.1B.2C.3D.4答案：A
10、前缀表达式+ - *33*425的值（ ）A.0B.1C.6D.7答案：C
11、连通图G是一棵树当且仅当G中( )。A.有些边是割边B.每条边都是割边C.所有边都不是割边D.图中存在一条欧拉路径答案：B
12、一颗树有两个2度结点,1个3度结点和3个4度结点,则1度结点数为( )。A.5B.7C.9D.8答案：C
13、设G是一棵树,则G 的生成树有( )棵。A.0B.1C.2D.不能确定答案：B
14、设G=<V,E>是n阶m条边的无向图，并且G是一棵树，则下列描述正确的是（ ）A.m=n+1B.m=n-1C.n=2mD.m=2n答案：B
15、若图G的最小生成树T中，各边的权值是1,2,3,3,4,7，那么该最小生成树的权为（ ）A.20B.17C.1D.以上均不正确答案：A
16、带权为1, 1, 2, 3的最有二叉树的权为（ ）A.7B.13C.20D.以上均不正确答案：B
页:
[1]