本科《离散数学》（计算机数学软件）复习题

离散数学(计算机数学软件)复习题

一、单项选择题

1．无向图G是欧拉图，当且仅当（ D ）.

A．G的所有结点的度数全为偶数 B．G中所有结点的度数全为奇数 C．G连通且所有结点度数全为奇数 D．G连通且所有结点度数全为偶数 2．设A＝{a,b}，则A的幂集P（A）为（ D ）.

A．{a,b} B．{?,{a},{b}} C．{?,{a,}} D．{?,{a},{b},{a,b}} 3．设F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。“每列火车都比某些汽车快”符号化为（ C ）. A．(?x)(?y)(F(x)?G(y)?H(x,y)) B．(?x)(?y)(F(x)?G(y)?H(x,y)) C．(?x)(F(x)?(?y)(G(y)?H(x,y))) D．(?x)F(x)?H(x,y) 4．谓词公式?x(p(x)??yR(y)?Q(x)中变元χ是( D ).

A．自由变元 B．既不是自由变元也不是约束变元 C．约束变元 D．既是自由变元又是约束变元 5．设A＝{a,b}，则A的幂集P（A）为（ D ）.

A．{a,b} B．{?,{a},{b}} C．{?,{a,}} D．{?,{a},{b},{a,b}}

-1

6．设f和g都是A到A的双射函数，则（fog）为（ D ）.

-1-1--1-1-1-1

A．fog B.fog C.（gof） D.g o f

A．传递性 B．对称性 C．自反性 D．反对称性 7．下面联结词集中，哪一个不是联结词的极小全功能集（ ）. A．{?，?} B．{↓} C．{?} D．{?，?，?} 8．仅由一个孤立点组成的图称为（ B ）.

A．零图 B．平凡图 C．多重图 D．子图

9．给下列序列，哪一个可构成无向简单图的顶点度数序列（ B ）. A.（1，1，2，2，3） B.（1，1，2，2，2） C.（1，2，3，4，5） D.（1，3，4，4，5）

10．在任何图G=＜V，E＞中，顶点总度数和边数的关系为（ ）.

deg(v)?2Edeg(v)?EA．v?V B．v?V

deg(v)?2E?deg(v)?EC．v?V D．v?V

11．一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( B ). A．哈密尔顿回路 B．欧拉回路 C．哈密尔顿通路 D．初级回路 12．给定平面图G如下所示，则G中所有面的总次数为（ B ）. A. 28 B. 22 C. 26 D. 24

? 1

13．设图G是有6个顶点的连通图，总度数为20，则从G中删去多少条边使之变成树？（ B ）. A．10 B．5 C．3 D．2

14．下面给出的符号串集合中，哪一个不是前缀码？（ B ）.

A．?0,10,110,1111?； B．?1101,1001,101,110,?；

C．

?01,001,000,10?； D．?b,c,aa,ac,aba,abc?

15．下面给出的符号串集合中，哪一个是前缀码？（ A ）.

A．{1, 01, 001, 000} B．{1, 11, 101, 001, 0011} C．{b, c, aa, bc, aba} D．{b, c, a, aa, ac, abb} 16．下列语句，哪一个是真命题：（ B ）.

A．我正在说谎 B．如果1+1=0，那么雪是黑的 C．9+5＞18 D．存在最大的质数

17．P={a、b、c、d}的最大划分（即集中元素数目最多的划分）是（ C ）. A．{{a}，{b，c}{d}}； B．{a，{b，c}}； C．{{a}、{b}，{c}，{d}} D．{{a，b，c，d}}

18．一阶公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是( ). A. (P(x)∨?yR(y)) B. P(x)

C. ?x(P(x)∨?yR(y)) D. (P(x)∨?yR(y))→Q(x) 19．一阶逻辑公式?xP(x)??yQ(y)的前束范式是（ ）. A.?x?y(P(x)?Q(y)) B.??xP(x)∨?yQ(y) C.?x?y?P(x)∨Q(y) D.?x?y(P(x)?Q(y)) 20．命题公式?(P?Q)的主析取范式为 ( ). A．m00?m01?m11 B．m00∨m11 C．m01 D．m10

21．设集合A={a,b,c}，A上所有互不相同的等价关系的数目为( C ). A. 3 B. 4 C. 5 D. 6

22．设集合A={1，2，3}，A上的关系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，则R不具备( B ).23．下面所给的数值序列，能成为简单图的度数序列的是（ B ）. A．(1,2,2,3,4,5) B．(1,2,3,4,5,5) C．(1,1,1,2,3) D．(2,3,3,4,5,6)

24．设A（G）是有向图G=（V，E）的邻接矩接，其中第i行中值为1的元素数目为（ B ）. A．结点Vi的入度 B.结点Vi的出度 C．结点Vi的度数 D.结点Vj的度数

25．G=是简单有向图，可达矩阵P（G）刻划下列哪种关系（ A ）. A．点与点 B．点与边 C．边与点 D．边与边

2

26．设G是连通平面图，有5个顶点，6个面，则G的边数是( A ). A．9条 B．5条 C．6条 D．11条 27．设P：天下大雨，Q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上班”符号化为（ B ）. A．P?Q B．Q?P C．Q? ┐P D．?P? Q

28．设G是有5个顶点的完全图，则从G中删去多少条边可以得到树？( A ). A．6 B．5 C．10 D．4. 29．下面哪一种图不一定是树。（ D ）.

A．有n个顶点n—1条边的连通图 B．无回路的连通图

C．连通但删去一条边则不连通的图 D．每对结点间都有路的图

30．设G=为（n, m）连通图，则要确定G的一棵生成树必删去G中边数为（ C ）. A．n－m+1 B．n－m－1 C．m－n+1 D．m－n－1 二、判断题

1、设A≠?，A上的恒等关系I，既是A上的等价关系也是A上的偏序关系。（ √ ） 2、度数为奇数的结点个数为0个或2个的连通的无向图G可一笔画出。（ √ ） 3、永真式一定是可满足式。 （ √ ） 4、设A、B、C是集合，若A∩C= B∩C,则A=B。 （ Χ ） 5、P∧┐(Q→P)是永假式 （ √ ） 6、?x(A(x)?B(x))??xA(x)??xB(x)。 （ √ ） 7、在命题逻辑中，“我在说谎”是命题。 （ Χ ） 8、某个图中结点的度数序列为：1，2，3，4，5，6。 （ Χ ） 9、有隔点的图不可能是欧拉图。 （ Χ ） 10、(?x)(A(x)?B)?(?X)A(x)?B （ Χ ）

三、简答题 1．设A={a,b,c,d,e}，A上的偏序关系R＝{，，，，，，，}?IA ，求：

(1)画出偏序关系R的哈斯图；

(2)求子集B={c,d,e}的极大元，极小元，最大元，最小元。 解：R的哈斯图为：

acebd

B的极大元：c,d

B的极小元：e B中无最大元

B中的最小元：e

3

2．A ={1，2，3，4，6，9，24，54}，R是A上的整除关系，画出偏序集的哈斯图，并求A的极大元、极小元，最大元、最小元。 解：R的哈斯图为：

2454469231

A的极大元是24、54 A没有最大元 A的极小元、最小元都是1

3．设有向图G=(V，E)如下图所示，

(1) 试用邻接矩阵方法求长度为3的路的总数和回路总数； (2)求图G的可达矩阵.

V1V4V2V3

解：（1）图G的邻接矩阵为：

1100A?1010 10110010依次计算A2,A3,A4得： 211042218A2?2111 4231 2121A3?52A424?911101121215由矩阵A3

得，长度为3的路的总数为38；回路总数为11。 1111（2）矩阵A3

或A4得，可达矩阵P为：

P?1111 11111111

4

452463 5842424．有向图G如下所示。求：

（1）图G的邻接矩阵A（G）；

（2）从V1到V4长度为2和4的通路各有几条？ （3）图G的可达矩阵P（G）

V1V4V2V3

解：（1）图G的邻接矩阵为：

010A?10001110010 10（2）依次计算A2,A3,A4得：

10A2?011110110111 2A3?101002201211122 1A4?20021321233113221

由矩阵A的第一行第四列得，从V1到V4长度为2的通路有1条，又由矩阵A的第一行第四列得，从V1到

24V4长度为4的通路有3条。

43127524762375，而由矩阵B得，G的可达矩阵P为：

P?33111111111111（3）B?A?A?A?A?23411 11

5．求下图G的一棵最小生成树，并求它的权W（T）

4715832647

6．利用KrusKal算法求出下面加权图的最小生成树及其边权之和W(T)。

5

本文来源：https://www.bwwdw.com/article/sn7t.html