离散数学复习题.doc

离散数学复习题 1下面给出的四个图中，哪个不是汉密尔顿图（ ）． (A) (B) (C) (D) 2 Ａ是集合， =10，则=（ ）。 (A) 100 （B） 2048 （C） 1024 （D）512 3设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为（ ）． (A)７；　　　　 (B)８；　　　　 (C)９；　　　　 (D)１４． 4 S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除关系。S的子集Ｂ＝{2,4,6｝，则在(S，≤)中，Ｂ的上确界是（ ） （A）不存在 （B）6 （C）4 （D）12 5 设集合A中有4个元素，则A上的不同的等价关系的个数为 ( ) (A)11 (B)14 (C)15 (D)17 6下列图中，（）是平面图。 （A） （B） （C） （D） 7若G,*是一个群，则运算“*”一定满足（）。 （A）交换律 （B）消去律 （C）幂等律 （D）分配律 8设偏序集(A，≤)上关系只的哈斯图如下图所示，若A的子集B＝{2，3，4，5}，则元素6为B的( )． （A）下界 （B）上界 （C）最小上界 （D）最大下界 9设图G是有6个顶点的连通图，总度数为20，则从G中删去( )边后使之变成树． （A）10 （B） 2 （C）3 （D）5 10设G＝V, E是有6个结点，8条边的连通图，则从G中删去 条边，可以确定图G的一棵生成树． 11设G=V，E，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试 （1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形. （1）G的图形表示为： （3分） （2）邻接矩阵： （6分） （3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （9分） （4）补图如下： 12构造关于权｛２，３，４，４，５，５，７｝的最优二叉树。 2 2 3 4 4 5 5 7 （1）｛２，３，４，４，５，５，７｝ （2）｛４，４，５，５，５，７｝ （3）｛５，５，５，７，８｝ （4）｛５，７，８，１０｝ （5）｛８，１０，１２｝ （6）｛１２，１８｝ 13用推理法求命题公式 (P→Q)R 的主析取范式（答案见教材） 14用迪克斯特拉算法求下面权图中点到之间的最短路径。(注：图形不一定遵循三角形2边之和大于第3边，直线只代表路径) v v1 v7 2 5 5 2 3 3 5 7 5 7 1 1 解：用双标号法，各点标号如下： （1分） （2分） 或 （3分，标出一个即可） （4分） （5分） （6分） 最短路为 或（7分，最短路求出一条即可，在其它地方未做对，只是指出两条最短路及最短距的情况下，可考虑加1分） 最短距为2+2+3+1+5=13（8分） 参考答案：1 D 2 C 3 B 4 D 5 C 6 C 7 B 8 B 9 D 10 3