11． 有向图G仅有一个结点的入度为0，其余结点的入度均为1，则G必为根树。( × )？ 12． 若无向图G=(n,m)连通，则必有m?n。( × ) 13． 若无向图G=(n,m)连通，则必有m?n?1。 ( √ )

14． 在完全二元树中，若有t片树叶，则其边的总数为E?2t?1。( × ) 15． 在完全二元树中，若有t片树叶，则其分支结点数为i?t?1。( √ ) 16． 若无向图G中的每条边都是割边，则G必为树。( × ) 17． 带权为?1,?2,?,?t的最优二叉树是唯一的。( × )

18．若无向图G中任意两点间恰好有一条路径，则G必是树。( √ ) 19．若森林F??n,m?是由k棵树组成，则m?n?k。( √ )

20．设图G是个连通无向图，则G的生成子图，一定是G的生成树。( × )

三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内(多选不给分)。

1．给定一个无向图G，如果( D )，则G必是个欧拉图。 A．G中每个结点的度均为偶数 B．G是连通图

C．G是个简单完全图 D．G连通且每个结点的度均为偶数

2．设G是个(n,m)简单连通平面图，若G的每个区至少由3条边围成，则有( A ) A．m?3n?6 B．m?2n?4 C．m?5n?10 D．m?6n?12

3．设G=(n,m)是连通赋权图，如果用破圈法求G的一个生成树，则必须从G中去掉( D )条边。

A．n?1 B．m?n?1 C．m?1 D．m?n?1

4．设G=(n,m)是连通赋权图，如果用避回路求G的一个生成树，则必须从G中选取( A )条边。

A．n?1 B．m?n?1 C．m?1 D．m?n?1

5．具有n个结点的无向图G，如果( D )，则G一定是树。 A．G中恰有n?1条边 B．G中每对结点间都相互可达 C．G中的每条边都是割边 D．G连通但去掉一条边就不连通 6．T为完全二元树，有t片树叶，m条边，则有( C )。

A．m?2?t?1? B．m?2?t?1? C．m?2?t?1? D．m?2?t?1? 7．5个结点构成的根树中，其元数m最多为( C ) A．2 B．3 C．4 D．5

9

8．一棵树中有2个4度结点，3个3度结点，其余的都是树叶，则该树的树叶总数为( C )

A．7 B．8 C．9 D．10

9．一棵完全k元树中有t片树叶，i个分支结点，则有关系式( B ) A．i?t?1 B．?k?1?i?1?t C．?k?1?i?t D．?k?1?t?t?i 10．一棵完全k元树中有t片树叶，m条边，则有关系式( C ) A．m?k?t?1?k B．m?k?t?1??1 C．m?k?t?1?k?1 D．m?k?t?1?

11、下面哪一种图不一定是树( C )

A．无回路的连通图 B．有个n结点n?1条边的连通图 C．每对结点之间都有通路的图 D．连通但删去一条边则不连通的图 12、连通图G是一棵树当且仅当G中( B )

A．有些边不是割边 B．每条边都是割边 C．无割边集 D．每条边都不是割边 13、具有4个结点的非同构的无向树的数目为( A ) A．2 B．3 C．4 D．5

14、具有6个结点的非同构的无向树的数目为( B ) A．5 B．6 C．7 D．8 （1+1+1+2+1=6）

15、一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为(D)

A．5 B．7 C．8 D．9

16、完全m元树T中有t片树叶，i个分支点，则有关系式( B )

A．i?t?1 B．?m?1?i?1?t C．?m?1?i?t D．?m?1?t?i?1 17、T为完全二元树，有t片树叶，e条边，则有( C )

A．e?2?t?1? B．e?2?t?1? C．e?2?t?1? D．e?2?t?1? 18、在一棵完全t元树中，有k个分支点，若内部路径长度为I，外部路径长度为E，则满足关系式( D )

A．E?I?tk B．E?tk??t?1?I C．E??t?1?I?k D．E??t?1?I?tk

19、、具有4个结点的非同构的根树的棵数为( B ) A．32 B．4 C．5 D．6

20、5个结点可构成的根树中，其元数m最多为 (D) A．2 B．3 C．5 D．4

21、设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数为 (B) A．7 B．8 C．9 D．14

10

22、下面给出的符号串集合中，(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? 23、下面给出的符号串集合中，(D)不是前缀码 A．?0,10,110,1111? B．?01,001,000,1? C．?b,c,aa,ac,aba,abc? D．?0011,001,101,11,1?

24、按右上图所示的二元树做后序遍历得到的符号序列为 (D) A．DBKHEIFLMJGCA B．BDEHKCFIJLMGA C．GCFIJLDKHEMBA D．DKHEBILMJFGCA

25、带权为10，15，20，25，30的最优二元树的权为 (B) A．100 B．225 C．400 D．625

26、带权为4，6，8，10，12的最优二元树的权是 (B) A．80 B．90 C．100 D．110

ABCEFGJMDHKIL11