《离散数学》题库及答案

答：k

49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b|

答：(2)

50、任意一个具有2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群

答：(1)

51、6阶有限群的任何子群一定不是（ ）。 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶

答：(3)

（格与布尔代数部分）

52、下列哪个偏序集构成有界格（ ） (1) （N,?） (2) （Z,?）

(3) （{2,3,4,6,12},|（整除关系）） (4) (P(A),?)

答：(4)

53、有限布尔代数的元素的个数一定等于（ ）。

(1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂

答：(4)

9

（图论部分）

54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

答：(4)

55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1} (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

答：（2）

56、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( 答：以v为起点的边的条数， 以v为终点的边的条数

58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定

答：1

59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。答：

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

答：m=n-1

10

)。

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，树

11

)，

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

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

答：（1）

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条边的连通简单平面图中，每个面都是由( )条边围成？

12