函授专升本-课程复习资料-计算机科学与技术离散数学-试题3套含答案

P279（2）写出下图相对于完全图的补图。

P287（5）a-c1．分析图1，求： （1）从A到F的所有通路。 （2）从A到F的所有迹。 （3）A和F之间的距离。

D 图1

P300(3)在下图中给出了一个有向图，试求该图的邻接 矩阵，并求出可达性矩阵和距离矩阵。

v1v2

vs

v3 v4A

B

C

E F

P311(3)确定n取怎样的值，完全图Kn有一条欧拉回路。

P311(7)判断下图所示的图中是否有汉密尔顿回路。

P317(2)证明：小于30条边的平面简单图有一个结点度数小于等于４。

P327(3) (3)一棵树有n2个结点度数为2，n3个结点度数为3，…，nk个结点度数为k, 问它有几个度数为1的结点?

P327(6a) 对于下图，利用Kruskal算法求一棵最小生成树。

9 2 8 7 5 6 3 4 10 1 P337(3)证明在完全二叉树中，边的总数等于2(n - 1)，式中n是树叶数。

P337（5a）给定权1，4，9，16，25，36，49，64，81，100，构造一棵最优二叉树。

P279（1）证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。

证明：设有向完全图具有n个结点，对任一结点vi均有

degvidegvin1

nn1又因边数nn1degvidegvi，故而

2i1i1nndegvin1degvi

i1i122 n12n1degvdegviii1i1i1nn2i1i1n2nn2

 nn12n1degvidegvi

n21degv nn12n1nn1i 2i1n degvii12

P279（2）写出下图相对于完全图的补图。

P287（5）a-c1．分析图1，求： （1）从A到F的所有通路。 （2）从A到F的所有迹。 （3）A和F之间的距离。

D 图1

E F A B

C

解(1)从A到F的通路有七条：

ABCF,ABCEF,ABEF,ABECF ADEF,ADECF,ADEBCF

(2)从A到F的迹有八条：

Ae1Be2Ce3F,Ae1Be2Ce6Ee8F,Ae1Be5Ee6Ce3F Ae1Be5E8F,Ae4De7EesF,Ae4De7Ee6Ce3F Ae4De7Ee5Be2Ce3F,Ae4De7Ee5Be2Ce6Ee8F

（3）dA,F3

P300(3)在下图中给出了一个有向图，试求该图的邻接

矩阵，并求出可达性矩阵和距离矩阵。

v1v2

vs

v3 v4解：邻接矩阵A（G），可达性矩阵P（G）和距离矩阵D（G）分别如下：

01AG10001DG12

00000011010000，PG101001000000110

100000001100000

01000000P311(3)确定n取怎样的值，完全图Kn有一条欧拉回路。

解：Kn有n个结点，每个结点的度数为n-1，故当n为奇数时，图Kn有一条欧位回路。

P311(7)判断下图所示的图中是否有汉密尔顿回路。

v1 B标记结点，使相邻结点的标记不同，此时需要在边B 解：如果用A和B v1,v2及ve,v7上

A v6 分别加结点v12和v13，该图经标记后如右图。那么左图有汉密尔顿回路当且仅当右图有汉密顿回路，在右图中有七个标记有A的结点，六个标记为B的结点，所以不可能存在一条汉密尔顿回路。 v2 P317(2)证明：小于30条边的平面简单图有一个结点度数小于等于４。 证明：用反证法。假设每个结点的度数4，即degvi5。因为2e即vv8 v3 v7 v11 v9 v4 B v10 v5 A B A A A A A A A degv5v，

ii1r26 e，由于e3v6，代入后得到ee6，即有e30，与边数小于30相矛盾。

55P327(3) (3)一棵树有n2个结点度数为2，n3个结点度数为3，…，nk个结点度数为k, 问它有几个度数为1的结点?

解：设有n1个度数为的结点。结点数vn1n2n3nk，边数

ev1(n1n22(n1n2n3n1n32n4nn)1，而2edeg(v1)，故

nkk

nk)2n11n22n33(k2)nk2

P327(6a) 对于下图，利用Kruskal算法求一棵最小生成树。

1 2 9 8 7 5 6 解：略

P337(3)证明在完全二叉树中，边的总数等于2(n - 1)，式中n是树叶数。

证明：由定理可知，分枝点数in11，结点数vint2nt1，而由定理可知，ve1，所以边数ev12(n11)。

P337（5a）给定权1，4，9，16，25，36，49，64，81，100，构造一棵最优二叉树。 解：a）最优二叉树如图所示。

385 219 166 119 100 85 81 64 55 36 30 49 25 14 16 5 9 1 4 P8-1指出上列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值.

a)离散数学是计算机科学系的一门必修课. b)计算机有空吗? c)明天我去看电影. d)请勿随地吐痰! e)不存在最大质数.

f)如果我掌握了英语、法语，那么学习其他欧洲语言就容易得多. g)9+5≤12

P8-3设P表示命题“天下雪”，Q表示命题“我将去镇上”，R表示命题“我有时间”.以符号形式写出下列命题.

a)如果天不下雪和我有时间，那么我将去镇上. b)我将去镇上，仅当我有时间时. c)天不下雪.

d)天下雪，那么我不去镇上.

a)王强身体很好，成绩也很好 b)小李一边看书，一边听音乐. c)气候很好或很热.

d)如果a和b是偶，则a+b是偶数.

e)四边形ABCD是平行四边形，当且仅当它的对边平行.

a)QRS

RS c)PQQP)

b)Pd)RST e)

PQRPQPQ

试把原子命题表示为P、Q、R等，然后用符号译出下列各句子.

a)或者你没有给我写信，或者它在途中丢失了. b)如果张三和李四都不去，他就去. c)我们不能既划船又跑步.

d)如果你来了，那末他唱不唱歌将看你是否伴奏而定.

P17-1求下列复合命题的真值表.

PQRPQPR

设SPQRP Q R T T T T T F T F T T F F F T T F T F F F T F F F PQPR，见下表

PR T F T F T T T T QR T F T T T F T T PPR PQ T F T T T T T T T T F F T T T T PQPR T F T T T T T T S T T T T T T T T P19-8化简以下各式(a)AB(┑B→┑A)C

(b)A(┑A(B┑B)) (c)(ABC)(┑ABC)

P23-1试证下列各式为重言式.

a)PQQRPR P23-2（a）不构造真值表证明下列蕴含式.

a)PQPPQP29(1)下列各式用只含V和┑的等价式表，并要尽可能的

简单.

a)PQ┑P

P39(1)求公式P(PQ)的析取范式和合取范式。

P39(4)求下列各式的主析取范式及主合取范式，并指出下列各式哪些是重言式。

(PQ)(PQ)

P39(5)用将合式公式化为范式的方法证明下列各题中两式是等价的。 a)(AB)(AC), A(BC)

P8-1指出上列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值.

a)离散数学是计算机科学系的一门必修课. b)计算机有空吗? c)明天我去看电影. d)请勿随地吐痰! e)不存在最大质数.

f)如果我掌握了英语、法语，那么学习其他欧洲语言就容易得多. g)9+5≤12

答案：a)是命题，真值为T。

b)不是命题。

c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。

P8-3设P表示命题“天下雪”，Q表示命题“我将去镇上”，R表示命题“我有时间”.以符号形式写出下列命题.

a)如果天不下雪和我有时间，那么我将去镇上. b)我将去镇上，仅当我有时间时. c)天不下雪.

d)天下雪，那么我不去镇上. 答案：a)PRQ

b)QR c)P d)PQ

a)王强身体很好，成绩也很好 b)小李一边看书，一边听音乐. c)气候很好或很热.

d)如果a和b是偶，则a+b是偶数.

e)四边形ABCD是平行四边形，当且仅当它的对边平行. 答案：a)P：王强身体很好 Q：成绩很好 PQ

b)P：小李一边看书 Q：一边听音乐. PQ c)P：气候很好 Q：天气很热. PQ d)P：a和b是偶数 Q：a+b是偶数. PQ

e)P：四边形ABCD是平行四边形 Q：它的对边平行. PQ a)QRS

RS c)PQQP)

b)Pd)RST e)

PQRPQPQ

答案：a)不是合式公式。（若规定运算符次序后亦可作为合式公式））

b)是合式公式。 c)不是合式公式。（括弧不配对） d)不是合式公式。（RS之间缺联结词） e)是合式公式。 试把原子命题表示为P、Q、R等，然后用符号译出下列各句子.

a)或者你没有给我写信，或者它在途中丢失了. b)如果张三和李四都不去，他就去. c)我们不能既划船又跑步.

d)如果你来了，那末他唱不唱歌将看你是否伴奏而定.

答案：解：a)P：你没有给我写信。R：信在途中丢失了。PQ。

b)P：张三不去。Q：李四不去。R：他就去。PQR c)P：我们能划船。Q：我们能跑步。PQ d)P：你来了。Q：他唱歌。R：你伴奏。P（QR） P17-1求下列复合命题的真值表.

PQRPQPR

设SPQRP Q R T T T PQPR，见下表

PR T QR T PPR PQ T T PQPR T S T T T F T F T T F F F T T F T F F F T F F F F T T T F T T F T T T T T T T F F T T T T F T F T T T T F T T T T T T T T T T T T T P19-8化简以下各式(a)AB(┑B→┑A)C

(b)A(┑A(B┑B)) (c)(ABC)(┑ABC)

答案：a）（（AB）（┑B┑A））C((AB)) （AB））CTCC b)A（┑A（B┑B））A（┑AF）A┑AT

c)（ABC）（┑ABC）（A┑A）（BC）T（BC）BC P23-1试证下列各式为重言式.

a)PQQRPR 略

P23-2（a）不构造真值表证明下列蕴含式.

a)PQPPQP29(1)下列各式用只含V和┑的等价式表，并要尽可能的简单.

a)PQ┑P 略

P39(1)求公式P(PQ)的析取范式和合取范式。

解：P(PQ)P（┑PQ）（P┑P）（PQ）PQ

P(PQ)P（┑PQ）（P（Q┑P））（┑PQ）（PQ）（P┑Q）（┑PQ）

P39(4)求下列各式的主析取范式及主合取范式，并指出下列各式哪些是重言式。

(PQ)(PQ)

解：（┑P┑Q）（P┑Q）┑（┑P┑Q）（P┑Q）（PQ）（P┑Q）

（┑PQ）1,2,3PQ=0。

P39(5)用将合式公式化为范式的方法证明下列各题中两式是等价的。 a)(AB)(AC), A(BC)

证明：（AB）（AC）（┑AB）（┑AC） A（BC）┑A（BC） （┑AB）（┑AC）

P86（4）对任意集合A、B、C，确定下列各命题是否为真，并证明之。

如果AB及BC，则AC P86（6）确定下列集合的幂集

 a)a,a1,2,3 b),a,b c)

P86（9）设某集合有101个元素。试问

a)可构成多少个子集？

b)其中有多少个子集的元素为奇数？ c)是否会有102个元素的子集？

1,2，确定下面集合。 P104-105（1）a，c设A0,1,B1B a)AP109（2）在一个有n个元素的集合上，可以有多少种不同的关系。

P110（6）对{0，1，2，3，4，5，6}上的二元关系，{x,yxyx是质数}，写出关系矩阵。

P110（7）设P1,2,2,4,3,3和Q1,3,2,4,4,2找出

PQ,PQ，domP，domQ，ranP，ranQ，domPQ，ranPQ。

P113（1）1．分析集合A{1,2,3}上的下述五个关系。

R{1,1,1,2,1,3,3,3}

S{1,1,1,2,2,1,2,2,3,3} T{1,1,1,2,2,2,2,3} 空关系

AA全域关系

判断A中的上述关系是不是（a）自反的，（b）对称的， （c）可传递的，（d）反对称的。

P119（5）R和A上的一个二元关系，如果R是自反的，则R1一定是自反的吗？ 如果R是对称的，则R1一定是对称的吗？如果R是传递的，则R1一定是传递的吗？

P127（3）归纳出用矩阵和作图方法求出自反（对称，传递）闭包的一般方法。

P130（1）4个元素的集合共有多少个不同的划分？

P134(2)试问由4个元素组成的有限集上所有的等价关系 的个数为多少？

P178 (1)设集合A={1，2，…，10}，问下面定义的二元运算*关于集合A是否封闭？

a)xy=max(x，y) b)xy=min(x，y) c)xy=GCD(x，y) d)xy=LCM(x，y)

e)xy=质数p的个数，使得x<=p<=y

P184 (1)对于实数集合R，下表所列的二元运算是否具有左边一列中的那些性质，请在相应的位置上填写“是”或“否”。 可结合性 可交换性 存在幺元 存在零元 + 是 是 是 否 – 否 否 否 否  是 是 是 是 max 是 是 否 否 miu 是 是 否 否 |xy| 否 是 是 否 P190(2) 设是一个半群，S，在S上定义一个二元运算口，使得对于S中的任意元素x和y，都有x□ y =x** y，证明二元运算口是可结合的.

P190(3) 设是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素a,b, 都有a*babab，证明0是幺元且是独异点.

P86（4）对任意集合A、B、C，确定下列各命题是否为真，并证明之。

如果AB及BC，则AC 答：真。因为BC，故ABAC。 P86（6）确定下列集合的幂集

 a)a,a1,2,3 b),a,b c)解：a)设Aa,a，则A£¬a,b)设Ba,aa.



1,2,3，则B,1,2,3 c)设E,a,b,,,a,,b,a,a,,a,bP86（9）设某集合有101个元素。试问

a)可构成多少个子集？

b)其中有多少个子集的元素为奇数？ c)是否会有102个元素的子集？ 解：a)可构成2101个子集； b)有2101/2个子集元素为奇数； c)不能有102个元素的子集。

1,2，确定下面集合。 P104-105（1）a，c设A0,1,B1B a)A解：A1B0,1,1,0,1,2,1,1,1,1,1,2 P109（2）在一个有n个元素的集合上，可以有多少种不同的关系。

解：因为在X中的任何二元关系都是XX的子集，而XX=X2中共有n2个元素，共可组成2n个子集，即|(XX)|2。

故在n个元素集合上，共有2n个不同的关系。

P110（6）对{0，1，2，3，4，5，6}上的二元关系，{x,yxyx是质数}，写出关系矩阵。

n解：R{0,1,0,2,0,3,0,4,0,5, 0,6,1,2,1,3,1,4,1,5, 1,6,2,3,2,4,2,5,2,6, 3,4,3,5,3,6,4,5,4,6, 5,6,2,0,2,1,2,2,3,0, 3,1,3,2,3,3,5,0,5,1, 5,2,5,3,5,4,5,5} 其关系矩阵为

011111100111111111111Mp1111111

000001111111110000000P110（7）设P1,2,2,4,3,3和Q1,3,2,4,4,2找出

PQ,PQ，domP，domQ，ranP，ranQ，domPQ，ranPQ。

解：PQ1,2,1,3,2,4,3,3,4,2

PQ2,4

domP={1，2，3}，domQ={1，2，4} ranP={2，3，4}，ranQ={2，3，4} domPQ={2}，ranPQ={4}

P113（1）1．分析集合A{1,2,3}上的下述五个关系。

R{1,1,1,2,1,3,3,3}

S{1,1,1,2,2,1,2,2,3,3} T{1,1,1,2,2,2,2,3} 空关系

AA全域关系

判断A中的上述关系是不是（a）自反的，（b）对称的， （c）可传递的，（d）反对称的。

解：（1）R是可传递的。（2）S是自反，对称和可传递的。（3）T关于a)b)c)d)都不成立。（4）空关系可定义为自反，对称，和可传递的。（5）全域关系是自反、对称和可传递的。 P119（5）R和A上的一个二元关系，如果R是自反的，则R1一定是自反的吗？ 如果R是对称的，则R1一定是对称的吗？如果R是传递的，则R1一定是传递的吗？ 证明：a)若R是自反的，则对所有xA，有x,xR，故x,xRc,即Rc是自反的。 b)若R是对称的，则RR，所以R也是对称的。

c)若R是传递的，则对所有x,y,zA，若x,yRy,zR，必有

cccc

y,xRz,yRz,yRx,zRc故Rc是传递的。

P127（3）归纳出用矩阵和作图方法求出自反（对称，传递）闭包的一般方法。 解：设有Xx1,x2,,xm上关系R，其关系矩阵为MR，关系图为GR。如果求R的自

反闭包r(R)，在MR中，只需将其对角线上的元系都改为1，即在MR中使an1,1in，在关系图GR上只需对每个结点画上自回路。

对于求R的对称闭包s(R)，在关系矩阵MR中，若有aij1，则可添加aji1，在关系图GR上，只要对任意两个结点间有连线，可使该两结点添加为双向线。

对于求R的传递闭包，矩阵MR可利用Warshall算法，求得传递闭包的矩阵，其算法为

（1）置新矩阵A:M; （2）置i:=1;

(3)对所有j，如果A{j,i}=1，则对k=1,2,（4）i加1

（5）如果ir0则转到步聚（3），否则停止。

对于关系图GR，可自某一结点开始，逐点检查，若有三个结点x1,xj,xk满足

,n，有Aj,k:Aj,kAi,k

xi,xjR，xj,xkR则可连结xi与xj。这样对所有邻接力都逐对检查，直至结束。

P130（1）4个元素的集合共有多少个不同的划分？ 解：整数4可划分为4，1+3，1+1+2，2+2，1+1+1+1。

12121C4C4C4115（种）

2P134(2)试问由4个元素组成的有限集上所有的等价关系 的个数为多少？

解：因为集合X上的等价关系与X的划分是一一对应的，所以4个元素的有限集上等价关系的数目，与4个元系集合进行划分的数目是相同的，由习题3-104可知共有15个不同的等价关系。

P178 (1)设集合A={1，2，…，10}，问下面定义的二元运算*关于集合A是否封闭？

a)xy=max(x，y) b)xy=min(x，y) c)xy=GCD(x，y) d)xy=LCM(x，y)

e)xy=质数p的个数，使得x<=p<=y 解：a)封闭 b)封闭 c)封闭

d)不封闭，例LOM（3,7）=21 e)不封闭，例660。

P184 (1)对于实数集合R，下表所列的二元运算是否具有左边一列中的那些性质，请在相应的位置上填写“是”或“否”。 可结合性 可交换性 存在幺元 存在零元 + 是 是 是 否 – 否 否 否 否  是 是 是 是 max 是 是 否 否 miu 是 是 否 否 |xy| 否 是 是 否 P190(2) 设是一个半群，S，在S上定义一个二元运算口，使得对于S中的任意元素x和y，都有x□ y =x** y，证明二元运算口是可结合的.

证明：因为

xyzxayzxayazaayaz

xyzxyazxayazxayaz

所以xyzxyz

P190(3) 设是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素a,b, 都有a*babab，证明0是幺元且是独异点.

证明：对于任意的aR,0a0a0a0,a0a0a0a，所以

0aa0a，故0是幺元。

对于任意的a,bR，则于+和·在R上封闭，所以，abababR，即*在R上封闭。

对于任意的a,b,cR，有

abcabacc

ababcababc =abcabacbcabc

a(bc)a(bcbc)

a(bcbc)a(bcbc)

=abcabacbcabc

所以，abcabc，故是可结合的。 因此，是独异点。