《离散数学》题库及答案

答:

n(n?1), n-1 260、一棵无向树的顶点数n与边数m关系是( )。

答:m=n-1

61、一个图的欧拉回路是一条通过图中( )的回路。

答:所有边一次且恰好一次

62、有n个结点的树,其结点度数之和是( )。

答:2n-2(结点度数的定义)

63、下面给出的集合中,哪一个不是前缀码( )。 (1) {a,ab,110,a1b11} (2) {01,001,000,1} (3) {1,2,00,01,0210} (4) {12,11,101,002,0011}

答:(1)

64、n个结点的有向完全图边数是( ),每个结点的度数是( )。

答:n(n-1),2n-2

65、一个无向图有生成树的充分必要条件是( )。

答:它是连通图

66、设G是一棵树,n,m分别表示顶点数和边数,则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答:(3)

67、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。

答:2

68、任何连通无向图G至少有( )棵生成树,当且仅当G 是( ),G的生成树只有一棵。

答:1, 树

69、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:

(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

答:(1)

9

70、设T是一棵树,则T是一个连通且( )图。

答:无简单回路

71、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16

答:(4)

72、设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 12

答:(4)

73、设图G=,V={a,b,c,d,e},E={,,,,},则G是有向图还是无向图?

答:有向图

74、任一有向图中,度数为奇数的结点有( )个。

答:偶数

75、具有6 个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成?

(1) 2 (2) 4 (3) 3 (4) 5

答:(3)

76、在有n个顶点的连通图中,其边数( )。

(1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条

答:(2)

77、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为( )。

(1) 5 (2) 7 (3) 8 (4) 9

答:(4)

78、若一棵完全二元(叉)树有2n-1个顶点,则它( )片树叶。

(1) n (2) 2n (3) n-1 (4) 2

10

答:(1)

79、下列哪一种图不一定是树( )。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图

答:(3)

80、连通图G是一棵树当且仅当G中( )。 (1) 有些边是割边 (2) 每条边都是割边

(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

答:(2)

(数理逻辑部分)

二、求下列各公式的主析取范式和主合取范式: 1、(P→Q)?R

解:(P→Q)?R?(?P?Q )?R

?(?P?R)?(Q?R) (析取范式) ?(?P?(Q??Q)?R)?((?P?P)?Q?R)

?(?P?Q?R)?(?P??Q?R)?(?P?Q?R)?(P?Q?R) ?(?P?Q?R)?(?P??Q?R)?(P?Q?R)(主析取范式)

?((P→Q)?R)?(?P??Q??R)?(?P?Q??R)?(P??Q?R)

?(P?Q??R)?( P??Q??R)(原公式否定的主析取范式)

(P→Q)?R?(P?Q?R)?(P??Q?R)?(?P?Q??R)

?(?P??Q?R)?(?P?Q?R)(主合取范式)

2、(P?R)?(Q?R)??P

解: (P?R)?(Q?R)??P(析取范式)

?(P?(Q??Q)?R)?((P??P)?Q?R)?(?P?(Q??Q)?(R??R)) ?(P?Q?R)?(P??Q?R)?(P?Q?R)?(?P?Q?R)

?( ?P?Q?R)?( ?P?Q??R)?(?P??Q?R)?(?P??Q??R)

?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P?Q??R) (?P??Q?R)?(?P??Q??R) (主析取范式)

11

? ?((P?R)?(Q?R)??P)

(原公式否定的主析取范式) ?(P??Q??R)?(P?Q??R)

(P?R)?(Q?R)??P ?(?P?Q?R)?(?P??Q?R)(主合取范式)

3、(?P→Q)?(R?P)

解:(?P→Q)?(R?P)

?(P?Q)?(R?P)(合取范式)

?(P?Q?(R??R))?(P?(Q??Q))?R)

?(P?Q?R)?(P?Q??R)?(P?Q?R)?(P??Q?R) ?(P?Q?R)?(P?Q??R)?(P??Q?R)(主合取范式) ?((?P→Q)?(R?P))

?(P??Q??R)?(?P?Q?R)?(?P??Q?R)?(?P?Q??R)

?(?P??Q??R)(原公式否定的主合取范式)

(?P→Q)?(R?P)

?(?P?Q?R)?(P??Q??R)?(P?Q??R)?(P??Q?R)?(P?Q?R) (主析取范式)

4、Q→(P??R)

解:Q→(P??R)

??Q?P??R(主合取范式) ?(Q→(P??R))

?(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)

?(P??Q?R)?(P?Q??R)?(P?Q?R)(原公式否定的主合取范式)

Q→(P??R)

?(P?Q?R)?(P?Q??R)?(P??Q?R)?(P??Q??R)?(?P?Q??R)

?(?P??Q?R)?(?P??Q??R)(主析取范式)

5、P→(P?(Q→P))

解:P→(P?(Q→P))

??P?(P?(?Q?P)) ??P?P

? T (主合取范式)

12

联系客服:779662525#qq.com(#替换为@)