离散考试复习题 180题

26、已知a,b,c,d,e,f,g七人中,会讲的语言分别为:

a:英语、德语,b:英语、汉语,c:英语、意大利语、俄语,d:汉语、日语,e:意大利语、德语,f:俄语、日语、法语,g:德语、法语

问能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈? 27、求A到其余顶点的最短路径。

B8A1C24226D5F1E

28用Dijdstra算法求右图中u到v的最短路。

29一公司在六个城市C1,C2,----,C6中每一个都有分公司,从CI到CJ的班机旅费由下列矩阵中第I行第J列的元素给出(∞表示没有直接班机)。 0 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0

17

公司所关心的是计算两城市间的费用最低的路线,对上述六城市中任意一对城市,计算两城市间费用 最低的路线。 30、 (1)求下图的最小生成树; (2)求该图的点连通度和边连通度; (3)求A到B的最短路径的长度。 A

31 关于无向树的描述,不正确的是( ). 无向树是连通图、没有回路,每个边都是桥;

无向树是连通图、边数比顶点数少1,任意两个顶点的路径是惟一的; 无向树是连通图、没有回路,每个顶点都是割点; 无向树是连通图、没有回路,每条边都是割边。 32 下面与“T是树”不等价的是( )

A.T是无圈图,且e=n-1 B.T是连通图,且e=n-1 C.T删去任一边后不连通 D.T任意添加一条边后有且仅有一个圈 33、证明若T是n阶非平凡的无向树,则T 中至少有两片树叶.

34、已知无向树T中有1个3度顶点,2个2度顶点,其余顶点全是树叶,试求树叶数,并画出满足要求的非同构的无向树.

35、画出所有有3片树叶、1个3度顶点、其余顶点不等于1和3的7阶非同构的无向树。 36、一棵无向树T有5片树叶,3个2度分支点,其余的分支点都是3度顶点,问T有几个顶点?

37、求下图的一棵最小生成树.

38 对于下图,利用避圈法求一棵最小生成树。

18

39 关于含有n片树叶的最优二叉树描述,不正确的是( ). A. 含有n片树叶的最优二叉树每个分支点都有两个孩子; B. 含有n片树叶的最优二叉树分支点的个数是n-1;

C. W(T)等于个分支点的权重(构造最优二叉树时产生)之和; D. 在权重一定的前提下,含有n片树叶的最优二叉树是惟一的。 40、求带权为1, 1, 2, 3, 4, 5的最优树. 41、在通信中,八进制数字出现的频率如下: 0:25% 1:20% 2:15% 3:10% 4:10% 5:10% 6:5% 7:5%

求传输它们的最佳前缀码,并求传输10n(n?2)个按上述比例出现的八进制数字需要多少个二进制数字?若用等长的(长为3)的码字传输需要多少个二进制数字? 42 最优二叉树有n片树叶,则它有 分支点。 43 求带权2、3、5、7、11、13的最优二叉树。

44 画一棵带权为1,1,1,3,3,5,8的最优二叉树T,并计算它的权W(T)。 45 下图所示的二叉树中序遍历的结果是 ,前序遍历的结果是 ,后序遍历的结果是 ,

abdce

46 下列编码是前缀码的是( ).

A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000}

19

47、下列编码不是前缀码的是( )

A.{0,10,110,1111} B.{1,01,001,000} C. {1,11,101,001,0011} D.{0,10,111}

48.求下面2叉树所产生的二元前缀码

49. 设G是有n个结点的有向完全图,则G的边数为 。 50. 设有n个结点的无向图G有m条边,则G的补图G有 条边。

51. 一棵无向树T有7片树叶,3个3度结点,其余结点均为4度。则T有( )个4度结点。

A、1; B、2; C、3; D、4。 52. 如下图所示的赋权图表示某七个城市

v1,v2,?,v7及预先算出的它们之间的一些直接通

信线路造价(单位:百万元),试给出一个设计方案,使得各城市之间能够通信而且总造价最小,并计算最小总造价。

53. 下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7; B、 1,2,2,3,4; C、 2,1,1,1,2; D、 3,3,5,6,0。

54. 下图中既不是Euler图,也不是Hamilton图的图是( )。

20

55. 一棵无向树T有7片树叶,3个3度结点,其余结点均为4度。则T有( )个4度结点。

A、1 B、2 C、3 D、4

56. 对下图所示无向带权图G求一棵最小生成树T,并计算出T的权W(T)。

12341234533212833447456

21

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