《离散数学》期末考试复习题及答案
第一部分、考试形式和时间
答题时限： 120 分钟 考试形式：闭卷笔试 第二部分、考试题型和得分构成
大题号 总分 100
一 20 二 三 四 10 10 60 一、选择题：对每一道小题，从其4个备选答案中选择最适合的一项，每小题2分，共10道小题，20分。
二、填空题：每空1分，共5道小题，10个空白处待填，10分。
三、判断题：每一道小题均以陈述语句描述，对的打√，错的打х。每小题1分，共10道小题，10分。
四、综合题：每小题10分，共6道小题，60分。
第三部分、考试复习范围
一、选择题
1．含n个元素的集合A的幂集的元素个数为多少？ 答案：2n个。
2．数理逻辑的创始人是谁？ 答案：莱布里茨。
3．设(R,+,?)是环，它有哪些特性？
答案：1.(R,+)是阿贝尔群。2.(R,?)是半群。3.?对+可分配。 4．排中律满足哪些性质？
答案：A∧ A不成立。（不应同时否认一个命题（A）及其否定（非A））
x（F（x）∨F（x））对任何个体x而言，x有性质F或没有性质F。
5．什么是真命题？命题“如果雪是黑的，则1+1=0”是真命题吗？
答案：真值为真的命题为真命题。命题“如果雪是黑的，则1+1=0”是真命题！
解析：p:雪是黑的；q:1+1=0;如果雪是黑的，则1+1=0:p→q。由于p为假，所以无论的真值如何，“p→q”的真值都为真。 6. 下列哪个等价公式有错？
A．P?Q?Q?P；B．P?Q??P?Q；C．P?Q??Q?P； 答案：A
7. 设G为4阶有向图，度数列为（3,4,2,3），若它的入度列为（1,2,2,1），
则出度列为哪项？
A．（1,2,1,2）； B．（2,2,0,2）； C．（2,1,1,2）． 答案：B
解析：有向图中：度数=出度数+入度数。 8. 设S???a?,3,4,??,则表示空元素属于S怎样写？ 答案:?∈S
9. 什么是前束范式？下面哪个是前束范式？
A．Q(x,z)?(?x)(?y)R(x,y,z) ； B．(?x)(?y)Q(x,y)．
答案：前束范式：如果量词均在全式的开头，它们的作用域延伸到整个公式的末端，则该公式叫做前束范式。B。
解析：如果量词均在全式的开头，它们的作用域延伸到整个公式的末端，则该公式叫做前束范式，显然B选项满足定义。
9. 无向图G中有16条边，且每个结点的度数均为2，则结点数是多少？ 答案：16
解析：由于每个结点的度数为2，所以可以排除G中存在孤立点（度数为0）和悬挂点（度数为1）。由此可知，G中的任何一个结点皆是使用一度与上一个结点相连再使用另一度与下一个结点相连，从而每条边与两个结点关联（上一个结点与下一个结点），但是每个结点又与两条边相连，故结点数为：16×2÷2=16个。 10. 含n个命题变元的命题公式的不同的真值指派有几种？ 答案：2n种
11. 集合论的创始人是？ 答案：G.Cantor(康托尔) 13．以下推理错误的是？
A．P,?P?Q?Q； B．P,P?Q??Q； 错误！未找到引用源。
C．?Q,P?Q??P 答案：B
14．设G为4阶有向图，度数列为（4,4,2,2），若它的入度列为（2,2,1,1）， 则出度列为哪项？C
A．（2,1,1,2）； B．（1,2,1,2）； C．（2,2,1,1） 15．图论中的握手定理的内容是什么？
答案：握手定理：在任何（n,m）图G=（V，M）中，其所有结点度数之和等于边数m 的两倍，即：∑deg(v)=2m。
16．下面哪一种图不一定是树？