《离散数学》考试试卷(试卷库20卷)及答案

2024年3月21日发(作者：江山市小升初数学试卷)

《离散数学》考试试卷（试卷库20卷）及答案

第 1 页/共 4 页

《离散数学》考试试卷（试卷库20卷）

试题总分： 100 分 考试时限：120 分钟

、选择题（每题2分，共20分）

则“人总是要死的”谓词公式表示为( )

（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧

（C ） ))()((x Mortal x M x →?

（D ） ))()((x Mortal x M x ∧?

2. 判断下列命题哪个正确？( )

（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}

（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集） （D ）若A 为

非空集，则A ≠A∪A 成立

3. 集合},2{N n x x A n

∈==对( )运算封闭

（A ） 乘法

（B ）减法

（C ） 加法

（D ）y x -

1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，

4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数

间“小于等于”关系，则 N b a ∈?,有=∨b a ( )

（A ）a

（B ）b

（C ）min(a ，b)

（D ） max(a ，b)

5. 有向图D=

，则41v v 到长度为2的通路有( )条

（A ）0 （B ）1 （C ）2 （D ）3

6. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )

个顶点

（A ）10 （B ）4 （C ）8 （D ）12

7. 下面哪一种图不一定是树？（ ）

（A ）无回路的连通图 （B ）有n 个结点n-1条边的连通图 （C ）

每对结点间都有通路的图 （D ）连通但删去一条边则不连通的图 8. 设

P ：我将去镇上,Q ：我有时间。命题“我将去镇上,仅当我有时间”符

号化为（ ）

（A ） P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代

数系统中,其中*是加法运算,（ ）不是群。

（A ）G 为整数集合 （B ）G 为偶数集合 （C ）G 为有理数集合

（D ）G 为自然数集合 10. 设G=,|V|=n,|E|=m 为连通平面图且有r 个

面,则r=（ ）

（A ）m-n+2

（B ）n-m-2 （C ）n+m-2

（D ）m+n+2

二、填空题（每题2分，共20分）

1. 若P ，Q 为二命题，P Q 真值为T ，当且仅当 。

2. 设S={a 1，a 2，…，a 8}，B i 是S 的子集且B 1={a 8}，由B

17表达的子集为 ， 子集{a 2，a 6，a 7}规定为 。

3. 设S 为非空有限集，代数系统中幺元为 ，零元为 。

4. 哈斯图(Hasse diagram)的具体画法是： 。

5. 当且仅当 时，我们称“P 蕴含Q ”，记为 。

6. 图G 的最大度用 表示，最小度用 表示。

7. 设r 是集合A 上的相容关系， 称作r 的最大相容类。 8. 在 情

况下要对约束变元进行换名，也可以对自由变元进行代入。 9. 设A

≠ ?，R ? A ? A ，若R 是 ，则称R 是A 上的偏序关系。

10. 如果格〈L ，≤〉中既有 ，又有 , 则称格〈L ，≤〉为有界格。

三、判断题（每题1分，共10分）

1. “今天不是我值日”这句话是命题。（ ）

2. 设集合S={1,2,3,4},S 上的关系R={<1,1>,<2,2>,<1,3>},则R

具有传递性。（ ）

3. 有割点的连通图可能是哈密尔顿图。（ ）

4. 每一个链都是分配格。（ ）

5. 若两图结点数相同，边数相等，度数相同的结点数目相等，则

两图是同构的。（ ）

6. {,}{,,,{,,}}a b a b c a b c ?（ ）

7. A ?(B ?C) = (A ?B)?(A ?C) （ ）

8. 群中的运算不满足消去律。（ ）

9. 设〈L,≤〉是一个格，那么对L 中任何元素a,b,c,d,若a ≤b ，c

≤d ，则a ∨c ≤b ∨d ，a ∧c ≤b ∧d 。（ ） 10. 如果有界格中某个元

素有补元，则补元唯一。（ ）

四、解答题（5小题，共25分）

1. （5分）什么是前缀码？什么是最优前缀码？如何求得最优前缀

码？

2. （8分）求公式(P ∨Q)∧(Q →R)的主析取范式和主合取范式。

3. （4分）设A={1,2}，P(A)为A 的幂集，求集合P(A)?A 。

4. （3分）设Ａ＝｛0,1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B 的关系

Ｒ＝｛〈x,y 〉|x<=\"\" p=\"\" r=\"\" ｝，求(1)r=\"\">

。

5. （5分）一棵树T 中，有3个2度结点，一个3度结点，其余

结点都是树叶。

（1）T 中有几个结点；

（2）画出具有上述度数的所有非同构的无向图。

五、证明（3小题，共25分）

1. （10分）用推理P,T 规则证明：P →?Q ，Q ∨

R ，R ∧?S ? ?P 。

2. （10分）设R 是A 上一个二元关系，令S={|a,b ∈A ∧?c ∈A