离散数学复习题及答案

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、3 B、4 C、5 D、615、 (A)。对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。A、10 B、9 C、11 D、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)。树中树叶的通路长度为内部通路长度。（）25、 (A)。任何一棵二

6、叉树的树叶可对应一个前缀码。（）26、(A)。任何一个前缀码都对应一棵二叉树。（）三综合题1.证明:若图是自对偶的，则.2.T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数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及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。解：最小生成树为因此如图T

7、G架线使各城市间能够通讯，且总造价最小，最小造价为：()23484.求出下所示图的邻接矩阵和可达性矩阵，并找出。解：邻接矩阵答案错误5.求下图的一棵最小生成树.解：因为图中n8，所以按算法要执行n17次，其过程见下图中(1)(7)。6.v1到v4,v4到v1长为3的通路各有多少条?求出下所示图的邻接矩阵和可达性矩阵v1到v4长为3的通路0条，v4到v1长为3的通路3条。总复习题二1、 (B)。设是半群，其中为非空集合，如果是上满足交换律的二元运算，则称为。、半群、可交换半群、可交换群、域2、 (D)。设是代数系统，其中为非空集合，如果,+是上的二元运算，则称环、为半群、为阿贝尔群、乘法对加法适

8、合分配律、满足A、B、C三条3、 (D)。设是环，如果乘法适合交换律，则称环。、整环、除环、域、交换环4、 (B)。设代数系统是个独异点，对任意，且均有逆元，则为（）。A、 B、 C、 D、5、 (D)。设代数系统是个独异点，则还需满足（）条件，代数系统为群。A、运算封闭 B、运算可结合 C、运算可交换 D、每个元素有逆元6、 (B)。代数系统中，如果存在为等幂元，则（）。A、 B、 C、 D、7、 (B)。设是个群，是的平凡子群，则=（）。A、 B、 C、 D、8、 (D)。在群中，对于，必存在，使得，则为（）。A、 B、 C、 D、9、 (C)。设代数系统是群，则运算满足（）条件，是阿贝尔

9、群。A、运算封闭 B、运算可结合 C、运算可交换 D、每个元素有逆元判断题1、(A)。为独异点，且中任意元素都存在逆元，则为一个群。（）2、(A)。为代数系统，为二元运算，如果是可结合的，且中任意元素都存在逆元，则为一个群。（）3、(B)。为独异点，且中任意元素都存在逆元，则为一个半群。（）三综合题1.设 运算为Q上的二元运算，(1) 指出运算的性质.(2) 求 运算的单位元、零元和所有可逆元.解：(1) 运算可交换，可结合. 任取 x, yÎQ,xy = x+y+2xy = y+x+2yx = y x,任取 x, y, zÎQ, (xy)z = (x+y+2xy)+z+2

10、(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x(yz) = x+(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz(2) 设运算的单位元和零元分别为 e 和 q，则对于任意 x 有 xe = x 成立，即 x+e+2xe = x Þe = 0 由于运算可交换，所以 0 是幺元.对于任意 x 有xq= q成立，即x+q+2xq =qÞx+2xq= 0 Þq = -1/2 给定 x，设 x 的逆元为 y, 则有 xy = 0 成立，即 x+y+2xy = 0 Þ (x -1/2 )因此当x&

11、#185;-1/2时， 是x的逆元. 2.S = P(1, 2), Å为对称差运算，写出 <s,Å>的运算表，并判断此代数系统是一个群。解：ÅÆ1 2 1,2Æ121,2Æ 1 2 1,21 Æ 1.2 22 1,2 Æ 11,2 2 1 Æ3.证明关于gcd, lcm运算构成的布尔代数. 解(1) 不难验证S110关于gcd和lcm 运算构成格. (略)(2) 验证分配律"x, y, zS110有gcd(x, lcm(y, z) = lcm(gcd(x, y), gcd(x, z)

12、 (3) 验证它是有补格, 1作为S110中的全下界, 110为全上界, 1和110互为补元, 2和55互为补元, 5和22互为补元, 10和 11互为补元, 从而证明了<S110, gcd, lcm>为布尔代数.总复习题三一证明下列公式等值二（1）求(p®Øq)ÚØr公式的析取范式与合取范式以及成真赋值成假赋值。解 (p®Øq)®rÛ (pÙq)Úr（析取范式） (pÙq) Û (pÙq)Ù(ØrÚr)Û (p&

13、#217;qÙØr)Ú(pÙqÙr)Ûm6Úm7 rÛ (ØpÚp)Ù(ØqÚq)ÙrÛ (ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr)Ûm1Úm3Úm5Úm7 , 代入并排序，得 (p®Øq)®r

14、9;m1Úm3Úm5Úm6Úm7（主析取范式）(p®Øq)®rÛ (pÚr)Ù(qÚr) （合取范式） pÚrÛpÚ(qÙØq)ÚrÛ (pÚqÚr)Ù(pÚØqÚr) ÛM0ÙM2 qÚrÛ (pÙØp)ÚqÚrÛ (pÚqÚr)Ù(&#

15、216;pÚqÚr) ÛM0ÙM4, 代入 并排序，得 (p®Øq)®rÛM0ÙM2ÙM4（主合取范式）成真赋值为 001, 011, 101, 110, 111，成假赋值为 000, 010, 100. （2）已知命题公式A中含3个命题变项p, q, r，并知道它的成真赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对应的真值函数.解：A的主析取范式为m1 Úm2Úm7A的主合取范式为M0ÙM3ÙM4 ÙM5ÙM

16、6 pq r F pq r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 1三构造下面推理的证明：（1）若明天是星期一或星期三，我明天就有课. 若我明天有课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解(1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课(2) 写出证明的形式结构 前提：(pÚq)®r, r®s, Øs结论：ØpÙØq(3) 证明 r®s前提引入 Ø

17、s前提引入 Ør 拒取式 (pÚq)®r前提引入 Ø(pÚq) 拒取式 ØpÙØq 置换（2）2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数，r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pÚq, p®r, r®Øs结论：s®q(3) 证明 s附加前提引入 p®r前提引入 r®Øs前提引入 p

18、®Øs 假言三段论 Øp 拒取式 pÚq前提引入 q 析取三段论（3）前提：Ø(pÙq)Úr, r®s, Øs, p 结论：Øq证明 用归缪法 q结论否定引入 r®s前提引入 Øs前提引入 Ør 拒取式 Ø(pÙq)Úr前提引入 Ø(pÙq) 析取三段论 ØpÚØq 置换 Øp 析取三段论 p前提引入ØpÙp 合取（4） (P®（QR)(S

19、4;Q)(PS)ÞR.证：（1） PS P（2） P T（1） I1（3） S T（1） I1（4） P®（QR) P（5） QR T (2)，(4) I11（6） S®Q P（7） Q T(3)，(6) I11（8） R T(5)，(7) I11四求下列公式的前束范式。解：五将下列命题符号化。(1) 所有的人都长着黑头发；(2)有的人登上过月球；(3) 没有人登上过木星； (4)在美国留学的学生未必都是亚洲人。解：令M(x)：x 为人。(1)  令F(x)：x长着黑头发。则"x (M(x) F(x)。 (2) 令G(x)：

20、x登上过月球。则$x (M(x)G(x)。(3) 令H(x)：x登上过木星。则 $x (M(x)H(x)。(4) 令F(x)：x是在美国留学的学生; G(x)：x是亚洲人。则"x (F(x) G(x)。六给定解释I 如下：（a） 个体域D= 2,3; （b） D中特定元素，a=2;（c） D上特定函数f (x) 为：f (2)=3, f (3)=2。（d） D上特定谓词： G(x,y): G(2,2)=G(2,3)=G(3,2)=1, G(3,3)=0; L(x,y): L(2,2)= L(3,3)=1, L(2,3)= L

21、(3,2) =0; F(x)：F(2)=0, F(3)=1在I下求下列各式的真值。 (1) "x(F(x)G(x,a);(2) $x(F(f(x)G(x,f(x);(3) "x$y L(x,y); (4) $y"x L(x,y)A Û(F(2)G(2,2)(F(3)G(3,2)解：设公式（1）为A, 则 Û(01)(11) Û0(2) B Û(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)Û(F(3)G(2,3)(F(2)G(3,2)Û (11)(01) Û 1(3) C Û

22、; (L(2, 2) L(2,3)(L(3,2)L(3,3)Û (10)(01) Û 1(4) D Û (L(2,2) L(2,3)(L(3,2)L(3,3)Û (10)(01) Û 0七求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？S = x | xÎZ1£x£1000 A = x | xÎSx可被5整除B = x | xÎSx可被6整除C = x | xÎSx可被8整除解：|A| = int(1000/5) = 200|B| = int(1000/6) = 166|C| = int(1000/8) = 125|AB| = int(1000/lcm(5,6) = 33|AC| = int(1000/lcm(5,8) = 25|BC| = int(1000/lcm(6,8) = 41|ABC| = int(1000/lcm(5,6,8) = 81000-(200+100+33+67)=600八A=1,2,3,4,