离散数学及应用 习题及答案 鄢小虎

1．设p:小张在自习室，q:小李在自习室。命题“小张在自习室，但小李不在自习室”符号化为（）。A.p∨q B.p∨qC.p∧q D.p∧q2．命题公式(pq)q为（）。A．重言式B．可满足式C．矛盾式D．等值式3.设集合A={1，b}，则P(A)=（）。A．{{1}，{b}}B．{，{1}，{b}}C．{，{1}，{b}，{1，b}}D．{{1}，{b}，{1，b}}4．A={1,2,3,4}，B={2,4,5,7}，AB=（）A.{1,2,3,4,5,7}B.{2,4}C.{1,2,3,4,2,4,5,7}D.{2,4,5,7}5．集合A={1,2,…,14}上的关系R={<x,y>|x+y=14,x,yA}，则R的性质为（）。A.自反的B.对称的C.传递的，对称的D.传递的6．设某个有向图的度数列为2,3,5，入度列为1,1,3，则出度列为（）。A.1,2,1 B.1,2,2 C.2,2,3 D.1,1,27.设集合A={1,2,3,4,5}，B为A的子集。若要求B必须包含元素{1,2}，且不能包含元素{3}，那么满足条件的集合B的个数是（）A．4 B.8C.16D.328.设图G是无向简单图，有5个顶点，7条边，已知G中所有顶点度数为奇数，则关于G说法正确的是（）。A.G不可能是连通图B.G的度数之和不可能是14C.这样的图不存在 D.G一定是树9.用Huffman算法对权值集合{2,3,5,7,11,13}构造最优二叉树，其带权路径长度为（）。A.80 B.86 C.94 D.9710.

设

G

为

n

阶连通简单平面图，且

G

中每个面至少由5条边围成，则

G

的边数

m

满足（）。A.m≤5(n−2)3 B.m≤3n−6 C.m≤5n11.f:R→R，f(x)=−xA.单射但非满射 B.满射但非单射 C.双射 D.既非单射也非满射12.命题公式(pA.永真式 B.矛盾式 C.可满足式 D.不确定13.“所有老鼠都怕猫”应该符号化为（），设C(x):x是老鼠，D(x):x是猫，F(x,y):x怕y。A.∀x(C(x)→∀y(D(y)→F(x,y)))B.∀x∃y(C(x)∧D(y)→F(x,y))C.∃x∀y(C(x)∧D(y)→F(x,y))D.∀x(C(x)→∃y(D(y)∧F(x,y)))14.下列语句中，不是命题的是（）。A．所有的质数都是奇数。B．这种花真香啊！C．若2+2=5，那么雪是黑色的。D．哪怕是计算机系的学生，也不一定都会修电脑。15.对一棵树进行前序遍历得到序列ABDECF，进行中序遍历得到序列DBEAFC，则该树的根节点的右子树包含节点（）。A．B、D、EB．C、FC．E、FD．只有C16.集合A={1,2,3}，关系R={<1,2>，<2,1>，<2,3>}。若要使R成为传递关系（即要求传递闭包t(R)），需要在R中额外添加序偶（）。A．仅<1,3>B．<1,1>和<2,2>C．<1,1>，<1,3>，<2,2>D．<1,3>，<3,1>，<3,3>17.设无向图G有5个顶点。若G为非连通图，则G的边数最多为（）。A．3 B.6 C.8 D.1018.若(p∧q)→r为假，则p，q，r的真值可能是（）。A.

p=1,q=1,r=0

B.

p=0,q=1,r=1

C.

p=1,q=0,r=1

D.

p=0,q=0,r=119.集合A={∅，∅}，则A.4 B.16 C.32 D.25620.设A={1,2,3}，A上的关系R的关系图中存在一条从1指向1的自回路，从2指向2的自回路，一条从2指向3的边，一条从3指向2的边，则R具有（）的性质。A．对称性 B.反对称性 C.传递性 D.既对称又反对称21.下列关系中，关系（）是偏序关系。A.实数集上的“不等于”关系B.整数集上的“整除”关系C.人的集合上的“父子”关系D.集合族上的“真包含”关系22.一棵树中含有2个度为4的节点，1个度为3的节点，3个度为2的节点，其余节点均为叶子节点（度为1）。则这棵树叶子节点的个数是（）。A.6 B.7 C.8 D.1023.算术表达式(a+b∗c)的二叉树表示（假设A．ab+c∗B．abc∗+C．ab∗c+D．abc+∗24.如果一个无向图是欧拉图，则它必须满足（）。A．所有的顶点度数是奇数B．恰有两个奇度顶点C．所有顶点度数为偶数D．有且只有一个奇度顶点ABCED10ABCED10234202A→C→B→D→EA→C→D→B→EA→C→B→E→DA→B→C→D→E26.设集合

A={1,2,3,4}，定义

A

上的关系

R

为：R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)}，则下列选项（）的集合是

R

的一个等价类。A.

{1,3}

B.

{2,4}

C.

{1,2,3}

D.

{3,4}二、填空题1．设A={1,2,3,4}，A上的关系R={<1,2>,<2,1>,<2,3>,<3,4>}，则RR=，R-1=2．令A={1,2,3},计算下列关系，小于等于关系LA=，整除关系DA=3．设集合A={a,b,c,d}，A上的二元关系R={<a,b>,<b,d>,<c,c>,<c,d>}，那么域fld(R)=，像R[{a,c}]=。4．A=(pq)r的析取范式，合取范式5．集合A={{a},{a,x}}，A上的包含关系R=6.命题“如果今天不下雨，我就去打球”可以符号化为

p→q，其中

p

表示“今天不下雨”，q

表示“我去打球”。那么“我今天没去打球，所以今天下雨了”可以符号化为

。7.设A={1,2,3,4,5}，B={2,3,4,6}，则A⨁B=。8.设集合A={∅，a，a}，则P（A）=9.某科技节活动，共有90名学生参加编程比赛。其中，有43名学生擅长Python编程，32名学生擅长Java编程，18名学生同时擅长这两种编程语言。则这两种编程语言都不擅长的学生有名。10.设A={x,y}，B={1,2}，则A×B=。11.设R={(1,2),(2,3),(3,4),(3,5),(4,2)}，则在R的关系矩阵中第3行第3列的元素是。12.设

R={(1,2),(2,3),(3,4)}

，在

A={1,2,3,4}

上，

t(R)=。13.设R是集合A={1,2,3,4}上的模2等价关系，则等价类[1]=。14.某无向图有4个顶点，度数列为(3,2,2,1)，则该图的边数为。15.一个连通的平面图有8个顶点和12条边，则该平面图将平面分割成的区域（面）数为。16.完全二部图K3,4的边数为，且该图17.一棵树有2个3度顶点，1个2度顶点，其余均为叶子结点（1度），则叶子结点的个数为。18.设A={1,2,3,4}，关系R是A上的小于关系，则R的补关系R中包含的有序对个数为。19.有向图G有4个顶点，每个顶点入度=出度=1，则G（填“一定”或“不一定”）有欧拉回路。20.设前缀表达式为+*52/63则其对应的中缀表达式的结果的值是。21.若用Huffman算法对权值集合{4,6,9,12,15}构造最优二叉树，则其带权路径长度WPL为。22.设函数f:ℝ→ℝ，定义为fx=2x+323.设全集合是整数集I，试用列举法表示集合A={x|x2-10x+21<0且0≤x≤15}，则结果为【答案】：选择题：题号789101112答案ACDADA13141516171819ABBCBAB20212223242526ABBBCAD填空题：6.¬q→¬p7.{1,5,6}8.P(A)={∅,{∅},{{a}},{a},{∅,{