离散数学复习题及答案

《离散数学复习题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总复习题（一）一．单选题1(C)。一连通的平面图，5个顶点3个面，则边数为（）。、4、5、6、72、(A)。如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。、1、2、3、43、(D)。为无环有向图，为的关联矩阵，则（）。、是的终点、与不关联、与关联、是的始点4、(B)。一连通的平面图，8个顶点4个面，则边数为。、9、10、11、125、(D)。如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。、1、2、3、46、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、107、(D)。有向图的通路包括。、简单通路、

2、初级通路、复杂通路、简单通路、初级通路和复杂通路8、(D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、129、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。、13、12、11、1010、(D)。有向图的通路包括。、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路11、(D)。一连通的平面图，9个顶点5个面，则边数为。、9、10、11、1212、(B)。为有向图，为的邻接矩阵，则。、邻接到的边的条数是５、接到的长度为４的通路数是５、长度为４的通路总数是５、长度为４的回路总数是５13、(C)。在无向完全图中有个结点，则该图的边数为（）

3、。A、B、C、D、14、(C)。任意平面图最多是（）色的。A、3B、4C、5D、615、(A)。对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。A、10B、9C、11D、1216、(C)。对于任意的连通的平面图，且每个面的次数至少为有，其中，分别为的阶数、边数。、、、、二．判断题1、(A)。有向图的关联矩阵要求图是无环图。（　　）2、(A)。是某图的度数序列。（　　）3、(A)。无向连通图的点的连通关系是等价关系（　　）4、(B)。是某图的度数序列。（　　）5、(A)。V和E分别为无向连通图G1的点割集和边割集.G1-E的连通分支个数为2。()6、(A)。彼

4、得森图不是哈密尔顿图。（　　）7、(B)。是平面图。（　　）8、(B)。设是平面图，若，则它们的对偶图。（　　）9、(A)。是平面图。（　　）10、(A)。一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。（）11、(B)。平面图中，任何两条边除端点外可以有其他交点。（）12、(B)。余树一定是树。（　　）13、(A)。为无向连通图，是的生成子图，并且是树，则是的生成树。（　　）14、(A)。是非平凡的无向树，则至少有两片树叶（　　）15、(B)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有4片树叶。()16、(A)。无向树有3个3度、2个2度顶点，其余

5、顶点都是树叶，共有5片树叶。()17、(B)。已知n(n>=2)阶无向简单树具有n-1条边，他一定是树。()18、(A)。一个连通无向图中，存在两个结点和，如果结点和的每一条路都通过结点，则结点比为割点。（）19、(A)。一个有向图，如果中有一个回路，至少包含每个结点一次，则是强连通。20、(A)。给定图，则关于树的定义是每一对结点之间有且仅有一条路。（）21、(A)。完全叉树是每一个结点的出度等于或0的根树。（）22、(A)。在正则叉树中，所有的树叶层次相同。（）23、(B)。树中分支点的通路长度为外部通路长度。（）24、(B)。树中树叶的通路长度为内部通路长度。（）

6、25、(A)。任何一棵二叉树的树叶可对应一个前缀码。（）26、(A)。任何一个前缀码都对应一棵二叉树。（）三．综合题1.证明:若图是自对偶的，则.2.T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数n=2+1+3+xT的边数m=n-1=5+x又由得2·（5+x）=2·2+3·1+4·3+x 所以x=9，即树T有9片树叶。3.图所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。解：最小生成树为因此如图TG架线使

7、各城市间能够通讯，且总造价最小，最小造价为：　Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝484.求出下所示图的邻接矩阵和可达性矩阵，并找出。解：邻接矩阵答案错误5.求下图的一棵最小生成树.解：因为图中n＝8，所以按算法要执行n－1＝7次，其过程见下图中(1)~(7)。6.v1到v4,v4到v1长为3的通路各有多少条?求出下所示图的邻接矩阵和可达性矩阵v1到v4长为3的通路0条，v4到v1长为3的通路3条。总复习题二1、(B)。设是半群，其中为非空集合，如果是上满足交换律的二元运算，则称为。、半群、可交换半群、可交换群、域2、(D)。设是代数系统