发布时间 : 星期三 文章离散考试复习题 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 关于无向树的描述,不正确的是( ). 无向树是连通图、没有回路,每个边都是桥；
无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的； 无向树是连通图、没有回路,每个顶点都是割点； 无向树是连通图、没有回路，每条边都是割边。 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