离散数学单项选择题习题(有答案)集(DOC) 下载本文

78.设s?{1,111,2,,3,,4},*为普通乘法,则是( ) 234A.代数系统 B.半群 C.群 D.都不是 79.在自然数集N上,下列哪种运算是可结合的?( )

A.a*b=a-b B.a*b=max{a,b} C.a*b=a+2b D.a*b=|a-b| 80.设?A,??是一个有界格,如果它也是有补格,只要满足( )

A. 每个元素都至少有一个补元 B. 每个元素都有多个补元 C.每个元素都无补元 D. 每个元素都有一个补元

81.具有如下定义的代数系统?G,??,( )不构成群

A.G?{1,10},*是模11乘 B.G?{1,3,4,5,9},*是模11乘 C.G?Q(有理数集),*是普通加法 D.G?Q(有理数集),*是普通乘法 82.在( )中,补元是唯一的

A.有界格 B.有补格 C.分配格 D.有补分配格 83.在布尔代数?A ,? ,?,??中,b?c?0当且仅当( ) A.b?c B.c?b C.b?c D.c?b

84.设是偏序集,“?”定义为:?a,b?A,a?b?a|b,则当A=( )时,是格 A.{1,2,3,4,6,12} B.{1,2,3,4,6,8,12,14} C.{1,2,3,…,12} D.{1,2,3,4}

85.设?A ,? ,?,??是布尔代数,f是从A到A的函数,则( )

A.f是布尔代数 B.f能表示成析取范式,也能表示成合取范式 C.若A={0,1},则f一定能表示成析取范式,也能表示成合取范式 D.若f是布尔函数,它一定能表示成析(合)取范式 图论

86.连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )

A.只有一个奇度结点 B.只有两个奇度结点 C.只有三个奇度结点 D.没有奇度结点 87.设G??V,E?为无向图,V?7,E?23,则G一定是( ) A.完全图 B.树 C.简单图 D.多重图

88.若一棵完全二元(叉)树有2n-1个顶点,则它( )片树叶 A.n B.2n C.n-1 D.2

n

9

89.图 给出一个格L,则L是( )

A.分配格 B.有补格 C.布尔格 D.A,B,C都不对

90.在Peterson图 中,至少填加( )条边才能构成Euler图

A.1 B.2 C.4 D.5 91.在有n个顶点的连通图中,其边数( )

A.最多有n-1条 B.至少有n-1 条 C.最多有n条 D.至少有n 条 92.图 中 从v1到v3长度为2的通路有( )条

A. 0 B. 3 C. 2 D. 1 93.下面那一个图可一笔画出( A )

94.一个割边集与任何生成树之间( )

A.没有关系 B.割边集诱导子图是生成树 C.有一条公共边 D.至少有一条公共边 95.在任何图中必定有偶数个( )

A.度数为偶数的结点 B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点 96.一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为( ) A.5 B.7 C.8 D.9

97.下列偏序集( C )能构成格

10

98.连通图G是一棵树当且仅当G中( )

A.有些边是割边 B.每条边都是割边 C.所有边都不是割边 D.图中存在一条欧拉路径

99.有n个结点(n?3),m条边的连通简单图是平面图的必要条件( ) A.n?3m?6 B.n?3m?6 C.m?3n?6 D.m?3n?6

100. 设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点 A.10 B.4 C.8 D.12 101. 在有n个顶点的连通图中,其边数( )

A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条 102. 给定无向图G??V,E?,如下图所示,下面哪个边集不是其边割集( ) A.{?v1,v4?,?v3,v4?} B.{?v4,v5?,?v4,v6?} C.{?v4,v7?,?v4,v8?} D.{?v1,v2?,?v2,v3?}

103. 如右图 相对于完全图K5的补图为( A )

104. 下列哪一种图不一定是树( )

A.无回路的简单连通图 B.每对顶点间都有通路的图

C.有n个顶点n-1条边的连通图 D.连通但删去任何一条边便不连通的图 105. 下面偏序集( B )能构成格

11

106. 6阶有限群的任何子群一定不是( ) A.2阶 B.3 阶 C.4 阶 D.6 阶

107. 在如下的有向图中,从V1到V4长度为3 的道路有( )条

A.1 B.2 C.3 D.4 108. n个结点的无向完全图Kn的边数为( ) A.n(n?1) B.

n(n?1) 2C.n(n?1) D.n(n?1) 2109. 设G是一个哈密尔顿图,则G一定是( ) A.欧拉图 B.树 C.平面图 D.连通图 110. 在如下各图中( B)是欧拉图

111. 下列图中( )是根树

A.G1??{a,b,c,d},{?a,a?,?a,b?,?c,d?}? B.G2??{a,b,c,d},{?a,b?,?b,d?,?c,d?}? C.G3??{a,b,c,d},{?a,b?,?a,d?,?c,a?}? D.G4??{a,b,c,d},{?a,b?,?a,c?,?d,d?}? 112. 下面给出的集合中,哪一个是前缀码?( )

A.{0,10,110,101111} B.{1,11,101,001,0011} C.{b,c,aa,ab,aba} D.{01,001,000,1}

113. 左图[0]相对于完全图的补图为( A )

114. 下列图中是欧拉图的有( A )

12

115. 设n阶图G有m条边,每个结点度数不是k就是k+1,若G中有Nk个k度结点,则Nk=( ) A.n×k B.n×(k+1) C.n×(k+1)-m D.n×(k+1)-2m 116. 设G是简单有向图,可达矩阵P(G)刻画下列 ( C )关系 A.点与边 B.边与点 C.点与点 D.边与边 117. 设G是一棵树,n,m分别表示顶点数和边数,则( ) A.n=m

B. n=m+1 C. m=n+1 D.不能确定 . 13