离散期末练习试卷

时间：2026-01-22

上海应用技术学院2008—2009学年第一学期

《离散数学》期末试卷（A）

课程代码: B204216 学分: 4 考试时间: 100 分钟

课程序号: 3404 班级：学号：姓名:

我已阅读了有关的考试规定和纪律要求，愿意在考试中遵守《考场规则》，如有违反将愿接受相应的处理。

试卷共 6 页，请先查看试卷有无缺页，然后答题。

一．选择题(10 x 2 =20)

1. 下列命题中命题（）为假。

A. “如果2是偶数，则一个公式的主析取范式唯一。” B. “如果2是偶数，则一个公式的析取范式唯一。”

C. “如果2是奇数，则一个公式的析取范式唯一。” D. “如果2是奇数，则一个公式的主析取范式唯一。” 2. 命题公式(p1 p2) p3的成真赋值为（）。 A. 001 B. 110 C. 100 D. 010

3. 集合A={x| x是单词“command”中的字母}，B={x,a,b,c,d},则|A∩B|=（）。 A. 7 B. 8 C. 4 D. 3

4. .若个体域为{0，1，2，3}，下列公式中值为真的是（）。 A. x y(x+y=0) B. y x(x+y=0) C. x y(x+y=0)

D. x y(x+y=0)

5. 设集合 S={{0,1},{1,2,3},{2,3,4,5}},集合( )是S中所有元素的交集。 A. {0,1,2,3,4,5} B. {1} C. Ф D. {0,1}

6. 若A B且B C则（）。 A. A∩C =B B. A∪B= A C. A∩C =A D. A∪C =B

7. 在自然数集合N上，下列运算中（）满足结合律。 A. a * b = | a-b | B. a * b = a+2b C. a * b = max( a,b ) D. a * b = a 8. 以下关系中（）不具有传递性。 A.S= { <1, 2>, <2, 1>, <1, 1>,<8, 5> } B. S={ <1, 1>,<2,2>,<1, 2>, <2, 1> } C. S={<2, 2>,<8, 5>}

D. S={<1, 1>, <2, 1>}

9. 以下命题中（）是假命题。 A.“群满足结合律” B.“群中只有一个幺元” C.“群中无零元” D.“群满足交换律”

10设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）。 A．3 C．5

二．填空题(2 x 10 = 20)

1. 设A={1,2,3,4}，R A×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包

r(R)=_____ _____，对称闭包t(R)=___ _______。 2. A={-1,0，1}，则<A, × >独异点，它的幺元为-1的逆元为。 3. 设F(x)表示“x是奇数”，H(x)表示“x是偶数”，G(x) 表示“x是整数”，用谓词公式表示命题“所有整数要么是奇数要么是偶数。” 。

B．4 D．6

4. 有向图中任意两点间均相互可达，此图为连通图。若任二顶点间至少从一个顶点到另一个顶点是可达的，则称此图为连通图

5．设A={a,b},B={0,1},则A与B的笛卡尔积A╳。 6．设命题P：天下雨，Q：我进城，R：我有空。用自然语言写出下列命题。（┐P→Q）∧（R→Q）：。 7．具有n个元素的集合A的子集个数是。

三．设A={1,2,3,4}，它的一个划分π={{1，3}，{2}，{4}}。 1．写出对应的等价关系R；（3） 2．画出R的关系图；（3）

3．写出A中元素关于R的等价类。（4）

10）（

四．写出命题公式( p →( p ∧ q )) ∨ r的真值表，并按真值表写出主析取范式和主合取范式。（10）

五．有带权图G如下(12) 1．写出图G的邻接矩阵（3）

2．求最小生成树和树权T（w）。（写出每一步生成过程）（7） 3．找出图中的“割点”（2）

六．给定权 1，4， 6 ， 7， 8，11，22，36，构造一棵最优二元树，并计算该二元树的权（写出构造的过程）。（10）

七．设有集合Z4 ={0，1，2，3}，+4 为定义在Z4 上的模4加法（两数相加后除以4的余数）（10）

1．构造< Z4 ，+4 >的运算表；（4） 2．证明< Z4 ，+4 >是一个群；（6）