离散数学第二版6-7章自测题 6,7章自测题(只有小题) (第六七章图论部分) 1、设G是一个哈密尔顿图,则G一定是( )。 (1) 欧拉图 (2) 树(3) 平面图(4) 连通图 2、下面给出的集合中,哪一个是前缀码?( ) (1) {0,10,110,101111} (2) {01,001,000,1} (3) {b,c,aa,ab,aba} (4) {1,11,101,001,0011} 3、一个图的哈密尔顿路是一条通过图中(所有结点一次且恰好经过一次 )的路。 4、在有向图中,结点v的出度deg+(v)表示( 以v为起始点的所有边 ),入度deg-(v)表示( 以v为终点的所有边 )。 5、一棵无向树的顶点数n与边数m关系是(n=m+1)。 6、一个图的欧拉回路是一条通过图中(所有的边一次且恰好一次 )的回路。 7、有n个结点的树,其结点度数之和是( 2(n-1) )。 8、下面给出的集合中,哪一个不是前缀码( )。 (1) {a,ab,110,a1b11} (2) {01,001,000,1} (3) {1,2,00,01,0210} (4) {12,11,101,002,0011} 9、n个结点的有向完全图边数是(n(n-1) ),每个结点的度数是(2(n-1) )。 10、一个无向图有生成树的充分必要条件是( 图是连通的 )。 11、设G是一棵树,n,m分别表示顶点数和边数,则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 12、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( 2 )片树叶。 13、任何连通无向图G至少有( 1 )棵生成树,当且仅当G 是( 树 ),G 的生成树只有一棵。 14、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:m-n+2 (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 15、设T是一棵树,则T是一个连通且(没有回路的无向图 )图。 16、设无向图G有16条边且每个顶点的度数都是2,则图G有(16 )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 17、任一有向图中,度数为奇数的结点有(偶数个)个。 18、在有n个顶点的连通图中,其边数()。 (1) 最多有n-1条(2) 至少有n-1 条 (3) 最多有n条(4) 至少有n 条 19、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为( 9 )。 (1) 5 (2) 7 (3) 8 (4) 9 本文来源:https://www.wddqw.com/doc/859a99fb75eeaeaad1f34693daef5ef7ba0d12de.html