数学参考答案破解版.pdf

数理逻辑练习 一、证明下面推理 1） 前提：p (q (s r),sp 结论： q 2） 前提： x(F(x)G(x)， x(G(x)R(x) ， xR(x) 结论： x(F(x) 3) 前提： x(F(x)(G(a) H(x)， x F(x) 结论： x (F(x)H(x) 证明:用归谬法, (1) q 附加前提 (2) sp P (3) p T(2),I (4) p(q (s r) P (5) q(s r) T(3)(4),I (6) s r T(1)(5),I (7) s T(2),I (8) s T(6),I (9) ss T(7)(8),I 由于最后步ss 0，所以推理正确，结论q 为有效结论。 2) 证明： x(G(x)R(x) P x(G(x)R(x) T(1),E G(c) R(c) T(2),I xR(x) P R(c) T(4),I G(c) T(3)(5),I x(F(x)G(x) P F(c)G(c) T(7),I F(c) T(6)(8),I x(F(x) T(9),I 3) 证明： 注意，在证明序列中先引进带存在量词的前提。 x F(x) P F(c) T(1),I x(F(x)(G(a) H(x) P F(c) (G(a) H(c) T(3),I G(a) H(c) T(4),I H(c) T(5),I F(c) H(c) T(2)(6),I x (F(x)H(x) T(7),I 二、在谓词逻辑中，构造下面推理的证明: 1、每个有理数都是实数，有的有理数是整数，因此有的实数是整数。 解: 设F(x):x 是有理数，G(x)：x 是实数，H(x ):x是整数。 则上述推理可以符号化为： x(F(x)( G(x)， x(F(x)H (x) |- x(G(x)H (x) 证明： x(F(x)H (x) P F(c)H (c) T(1),I x(F(x)( G(x) P F(c)G(c ) T(3),I F (c) T(2),I G(c ) T(4)(5),I H(c) T(2),I G(c )H (c) T(6)(7),I x(G(x)H (x) T(8),I 2、任何人，如果他喜欢步行，他就不喜欢乘汽车。每一个人或者喜欢乘汽车，或者喜欢骑 自行车。并非每个人都喜欢骑自行车。因此，有的人不爱步行。（个体域为人类集合） 解: 设F(x):x 喜欢步行，G(x)：x 喜欢乘汽车，H(x):x 喜欢骑自行车 则上述推理可以符号化为： x(F(x)( G(x), x(G(x)H (x), xH(x) |-xF(x) 证明： (1) xH(x) P (2) xH(x) T(1),E (3) H(c) T(2),I (4) x(G(x)H (x) P (5) G(c) H(c) T(4),I (6) G(c) T(3)(5),I (7) x(F(x)(G(x) P (8) F(c)(G(c) T(7),I (9) F(c) T(6)(8),I (10) xF(x) T(9),I 3) 如果2 是偶数，则 3是奇数。或者 2 是偶数或者 2 整除3，结果 2 整除 3，所以 3不是奇 数。 解 设 A：2是偶数；B：3 是奇数，C ：2 整除3；则推理化形式为： AB，AC ，C B 该推理形式不正确。例如，设有一赋值：AF， BT，C T，则 AB、AC 、C 都 为真，但 B 为假。 4) 如果 A 努力工作，那么 B 或 C 感到愉快；如果 B 愉快，那么 A 不努力工作；如果 D 愉 快那么 C 不愉快。所以，如果 A 努力工作，则 D 不愉快。 解： 设 A： A 努力工作；B、C 、D 分别表示 B、C 、D 愉快；则推理化形式为： ABC ，B A，D C AD 该推理形式正确。下面给出证明： (1)A 附加前提 (2)ABC P (3)BC T(1)(2)，I (4)BA P (5)AB T(4)，E (6)B T(1)(5)，I (7)C T(3)(6)，I (8)DC P (9)D T(7)(8)，I (10)AD CP 三、求下列命题公式的主析取范式和主合取范式，并求其成真赋值。 1） P(QR) 2） rq p )( 3） ) ()( qpqp 4） (P Q)(PQ) 1）公式法：因为 P(QR)P QR 6 M 0 m 1 m 2 m 3 m 4 m 5 m 7 m 所以，公式 P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、100、 101、111：成假赋值为：110。 真值表法： P Q R QR P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 由真值表可知，公式 P(QR)为可满足式， 其相应的成真赋值为 000、 001、 010、 011、 100、101、111：成假赋值为：110。 2） （p q）r ( p q )r (pq ) r (p r) ( q r) (p (q q )r) (p p )q r) (pq r) (pq r) ( p qr) ( p q r) 24 6 M MM 0135 mmmmm 7 其成真赋值为 000，001，011，101，111 3） （pq） (p q) (pq)（pq） pq 3 M 0 m 1 m 2 m 其成真赋值为 00，01，10 4) 公式法：因为( P Q)(PQ)(P Q)( P Q)( PQ ) (PQ )( P Q)( PQ ) 1 m 2 m 3 m 0 M 所以，公式( P Q)(PQ)为可满足式，其相应的成真赋值为 01、10、11：成 假赋值为：00。 真值表法： P Q PQ PQ (PQ )(PQ) 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 由真值表可知，公式( P Q)(PQ)为可满足式，其相应的成真赋值为 01、10、 11：成假赋值为：00。 四、求下列各公式的前束范式 1） ),( )( yxyQxPx 2） )()(),( zzRyyQyxxP 1） x(P(x) yQ(x,y) x ( P(x) yQ(x,y) x (P(x) yQ(x,y) x (P(x) yQ(x,y) x y (P(x)Q(x,y) 2）( x(P(x,y) yQ(y) zR(z) x(P(x,y) yQ(y) zR(z) x(P(x,t) yQ(y) zR(z) xy (P(x,t) Q(y) zR(z) x(y (P(x,t) Q(y) zR(z) x y (P(x,t) Q(y) zR(z) x yz (P(x,t) Q(y)R(z) 五、构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ 1） P( QR)。 2） (PQ )(P Q)。 解 (1) P Q R QR P(Q R ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 由真值表可知，公式 P( QR)的成真赋值为：101、110、111，成假赋值为 000、 001、010、011、100。 2) 解： P Q ( PQ ) PQ (PQ )(PQ ) 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 由真值表可知，公式 (P Q)(P Q)的成真赋值为：00、01、10、11，没有 成假赋值。 六、分别用真值表法和公式法判断下列命题公式的类型： (1)(PQ )(PQ )。 (3)(PQ ) (Q R) (R P Q)。 (5)(QP)( PQ )。 解 (1)真值表法： P Q PQ PQ (PQ )(PQ ) 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 1 由真值表可知，公式( PQ )(P Q)为可满足式。 公式法：因为( PQ )(PQ )(PQ )( P Q)(P Q)( PQ )，所以， 公式( PQ )(PQ )为可满足式。 (3)真值表法： P Q R PQ QR RP Q (PQ )(Q R )(R P Q ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 由真值表可知，公式( PQ ) (Q R) (R P Q)为矛盾式。 公式法：因为( PQ ) (Q R) (R P Q)(PQ ) QR( RP Q )F，所以，公式( PQ ) (Q R) (R P Q)为矛盾式。 (5)真值表法： P Q QP PQ (QP)(P Q ) 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 由真值表可知，公式( QP)( PQ )为矛盾式。 公式法：因为( QP)( PQ )(QP)( PQ )(Q P)( PQ )F， 所以，公式为矛盾式。 集合论练习 1.给定自然数集 N的子集： A1，3，7，8， B i|i 2 30 ， C i|i可以被 3 整除且 0 i20。求下列集合： (1)AB (2)BC。 (3)B( A C)。 (4)BC 解 由题意得 A1，3，7，8， B0，1，2，3，4，5， C0，3，6，9，12，15， 18所以 (1)AB0，1，2，3，4，5，7，8 (2) BC 0,3 (3)B( A C)B-0,1,3,6,7,8,9,12,15,18=2,4,5 (4) BC=BC-BC=0,1,2,3,4,5,6,9,12,15,18-0,3=1,4,5,6,9,12,15,18 2、已知ABAC，ABAC，请用集合恒等式证明BC。 证明 BB( AB) B( A C) ( BA) ( BC ) ( AC )( BC ) ( AB) C ( AC )C C 3.求由数字 1、2、3、4、5、6 组成的四位数(每个数字都不允许重复出现)中，数字 2 在 5 前面的四位数共有多少个？ 解 当2 在第1 位时， 21 43 12 3 36AC= 当 2 在第2位时， 21 42 12 2 24AC= 当 2 在第3位时， 2 4 12A = 任取 4 个不同的数字，且数字 2 在5 前面的4 位数个数为 36+24+12=72 4. 求 1 到 2500 之间能被 2， 3， 5 和 7 中任何一个数整除的整数个数。 解：设 A1表示 1 到 2500 之间能被 2 整除的整数集合， A2表示能被 3 整除的整数集合， A3表 示能被 5 整除的整数集合， A4表示能被 7 整除的整数集合。| x| 表示小于或等于 x的最大整 数。 1 2500 | | | | 1250 2 A = 2 2500 | |83 3 A = 3 2500 | | | | 500 5 A = 4 2500 | | | | 357 7 A = 12 2500 |41 23 AA= 6 13 2500 | | | 250 25 AA=| 14 2500 | 27 AA=178 23 2500 |16 35 AA= 24 2500 | | | 119 37 AA=| 34 2500 | 57 AA 71= = 12 3 2500 | 235 AA A=83 12 4 2500 |59 237 AA A|= = 23 4 2500 | 357 AAA= |23 123 4 2500 | 2357 AAA A 13 4 2500 | 257 AA A= |35 1= = 根据容斥原理 123 4 | | 1250 833 500 357 416 250 178 166 119 71 83 59 35 23 11 1929 AAA A=+ += 5、今有 111人购买 A,B,C 三种股票，已知只买了一种股票的共 75 人，买了 A 股和B股的共 有 20 人，买了 B 股和 C 股的共有 9 人，买了 A 股和 C 股的共 17 人，只买 A 股的共 31 人， 只买 B 股的共 23 人。试求： （10 分） 1） 三种股票都买的有几人？ 2） 买 A 股、B 股和 C 股的各几人？ 解：设集合 A，B，C 分别表示购买 A,B,C 三种股票的人的集合。根据题意画出文氏图如下图 所示。 设三种股票都买的有 x人，由已知条件填写图中相应区域。 C-(AB)= 75-31-23=21 由已知条件，可得以下方程： (20-x)+x+(9-x)+(17-x)+31+23+21 = 111 解得：x=5 故A=31+(20-5)+5+(17-5)=63 B=23+(20-5)+5+(9-5)=47 C=21+(9-5)+5+(17-5)=42 因而可得，三种股票都买的有 5 人。 买 A 股的有63 人，买B 股的有 47 人，买 C 股的有42 人。 31 23 21 A B C x 17-x 20-x 9-x 关系练习 1.设 A 1，2 ，构造集合 P(A) A。 解 P(A) A ， 1， 2 ， 1，2 1，2 ， ，。 2.设 R，求 D R 、 RR R R、 R 1、 R1、 R 、 R 、 R和 R。 解 D R 0，1，2 R R R 0，1，2 R R 1， R11，2 R R R R 3.证明 RA B RA RB。 (1)因为 y R AB x(xABxR y) x(xA x B) xR y) x(xA xR y )( xBxR y ) x(xA xR y) x(xBxR y ) R A R B y y R A RB y 所以 RAB RA RB。 4.设 X1，2，3，4， R 是 X 上的二元关系， R， ， (1)画出 R 的关系图。 (2)写出 R 的关系矩阵。 (3)说明 R 是否是自反、反自反、对称、传递的。 解 (1) R 的关系图如图所示： 1 2 3 4 (2) R 的关系矩阵为： 0100 1100 () 1010 1010 MR = (3)对于 R 的关系矩阵，由于对角线上不全为 1， R 不是自反的；由于对角线上存在非 0 元，R 不是反自反的；由于矩阵不对称，R 不是对称的； 经过计算可得 2 0100 0100 1100 1100 1100 1100 () 1010 1010 1110 1010 1010 1110 MR = ，所以 R 不是传递的。 5.令A=1,2,3;B=a,b,求 R1=,的关系矩阵。 1 11 01 10 R M = 6.令A=1,2,3;求 R2= ,的关系图。 1 2 3 7.令F=,，G=,求 F*G, G*F, F* F F*G=, G*F=, F*F=, 8.设集合 A=a, b, c ,d上的二元关系 R=, , , , 1） 试分析指出 R 所具有的性质（即是否具有自反性，反自反性，对称性，反对称性， 传递性这五种性质） 2） 求R 0 ，R 2 ，r(R) ，s(R) ，t(R) 的集合表达式。 解 1） R 既不具有自反性也不具有反自反性；R 既不具有对称性也不具备反对称性； R 也不具备传递性。 2) , 0 = bdaddcbcacbbabbaaaRt 9.设 A=1,2,3,4,5，A 上的等价关系 R 定义为： R=,I A 画出关系图，找出所有等价类。 解：R 的关系图如图 4.34 所示。 1 R =2R R R=1,2，3 R =4R R R=3,4，5 R =5R 关系图每一个连通分支的结点构成的集合是一个等价类。或者说， 每一个等价类导出了关系图的一个连通分支。 10.求出下列各偏序集的盖住关系COV A，画出哈斯图，找出A 的子集 B 1 、B 2 和 B 3 的极大元、极小元、最大元、最小元。 A=a,b,c,d,e， =,I A B 1 =b,c,d ，B 2 =a,b,c,d ，B 3 =b,c,d,e A=P(a,b,c)， = xP(A) yP(A)x y B 1 =,a,b，B 2 =a,c，B 3 =a, c,a,b,c 解：COV A=, 哈斯图如图所示。 A 的子集B 1 、 B 2 和B 3 的极大元、极小元、最大元、最小元、上界、 下界、上确界和下确界如表 4.3 所示。 表4.3 极大元 极小元 最大元 最小元 上界 下界 上确界 下确界 B 1 b,c,d b,c,d 无 无 e a e a B 2 b,c,d a 无 a e a e a B 3 e b,c,d e 无 e a e a A= P(a,b,c)=,a,b,c,a, b,a, c,b, c,a,b,c =, , , I A COV A=, , 哈斯图如图 4.45 所示。 A 的子集B 1 、 B 2 和 B 3 的极大元、极小元、最大元、最小元、上界、下界、上确界和下 确界如表 4.5 所示。 表4.5 极大元 极小元 最大元 最小元 B 1 a,b 无 B 2 a,c a,c 无 无 B 3 a,b,c a,c a,b,c a,c 线性代数练习 1. 若 0 221 50 131 = x ，求 x。 参考答案： 05 11 5 )1(1 110 50 131 221 50 131 11 =+= = = + x x xx 解得x=5 2设齐次线性方程组 只有零解， 则 123 123 12 3 0 0 0 xxx xxx xx x += += + = 满足条件？ 参考答案： 由题意，系数行列式不等于 0，即 2-01 01-(2( 00 01-0 111 2( 11 11 111 )2( 11 11 222 11 11 11 A +=+= += + = 并且 ） 3.计算行列式 x ab c d axbc d abxcd abcx + + + d+ 参考答案： 3 )( 000 000 000 1 )( 1 1 1 1 )( xdcbax x x x dcb dcbax dxcb dcxb dcbx dcb dcbax dxcbdcbax dcxbdcbax dcbxdcbax dcbdcbax dxcba dcxba dcbxa dcbax +=+= + + + += + + + + = + + + + 4. 计算行列式 2141 3121 1232 5062 解： 2605 2321 1213 1412 2605 0321 2213 0412 24 = cc nullnull 3 分 0412 0321 2213 0412 24 = rr nullnull 3 分 0 0000 0321 2213 0412 14 = = rr . 5. 设A = ，B = .求（1 ）AB 120 340 121 2 2 3 4 1 0 T ；（ 2）|4 A|. 解（1 ）AB T = = .（2 ）|4 A|=4 120 340 121 22 34 10 86 18 10 310 3 |A|=64|A|，而| A|= 120 340 121 2 = . 所以 |4 A|=64（ -2）= -128 . 343 122 321 的逆矩阵求 =A 6. 参考答案： () = + 111100 012520 011201 103620 012520 001321 100343 010122 001321 23 21 13 12 3 2 rr rr rr rr EAnull () 111100 2 5 3 2 3 010 231001 111100 563020 231001 1 2 1 5 2 3 2 32 31 r r rr rr = 111 2 5 3 2 3 231 1 A 7. 求下列非齐次方程组的通解 134 12 34 12 3 4 12 4 2 21 22 33 xxx xx xx xx x x xx x += + += += 3 5 ) = 参考答案： 对增广矩阵 做行变换 (bAnull 21 31 41 32 2 42 3 2 3 10 112 10 112 11211 01301 21123 01301 31035 01301 10 112 10 112 01301 01301 00 000 00000 00 000 00000 rr rr rr rr r rr r () ( ) 2RA RA b= ，所以原方程组有解，其同解方程组为： 134 23 2 31 xxx xx += = x3,x4 为自由变量，令x 3=c,x4=c2 得： 11 21 31 42 2 13 2 x cc x c xc xc = + =+ = = 所以方程的同解为： 1 2 12 3 4 11 30 10 01 x x cc x x =+ + 2 1 0 0 8.设 A= ,且矩阵 A,X 满足 AX=A+X,求矩阵 X 110 212 101 解：AX=A+X 所以有：(A-E)X=A 110010 212202 101100 101100 110010 212202 23 21 rr rr 101100 110010 05.00001 2 1 31 1 rr r 所以X= 101 110 05.00 9. 参考答案： （一）推出通项 （二）利用数学归纳法证明 当 n=1 时，A= 成立 100 110 011 假设 n=k 时成立，即 = 100 k10 )1( 2 1 k1 k kk A + + = = + 100 1k10 )1( 2 1 1k1 100 110 011 100 k10 )1( 2 1 k1 k1k kkkk AAA ，也成立 故 = 100 n10 )1( 2 1 n1 n nn A 成立 10. 设 111 121 -111,B 13-1 1-11 214 A = ，求(A-B)(A+B) 参考答案： 111 121 0 10 -111 13-1 2 2 2 1-11 214 1 2 3 AB = = 求 ，用数学归纳法证明。 n 110 011, 001 AA = 设 = = 100 210 121 100 110 011 100 110 011 2 A = = 100 310 331 100 110 011 100 210 121 23 AAA = 100 n10 )1( 2 1 n1 n nn A推断 = = 100 410 641 100 110 011 100 310 331 34 AAA 111 121 232 -1 1 1 1 3 -1 0 4 0 1-11 214 305 AB += = 010 232 0 40 222 040 2 146 1 2 3 3 0 5 11 11 17 = = (A-B)(A+B) 11.编写矩阵乘法函数 void multi_matrix(int aMS,int bSN,int cMN); 17 1 20 1 014 3 42 3 , 13 2 171310 20 1 AB = 并用主函数调用，验证 #include #define M 2 #define N 3 #define S 3 void multi_matrix(int aMS,int bSN,int cMN) int i,j,k; for(i=0;iM;i+) for(j=0;jN;j+) cij=0; for(k=0;kS;k+) cij+=aik*bkj; int main() int aMS=2,0,-1, 1,3,2; int bSN=1,7,-1, 4,2,3, 2,0,1; int cMN; int i,j; multi_matrix(a,b,c); for(i=0;iM;i+) for(j=0;jN;j+) printf(%5d,cij); printf(n); return 0; 12.求矩阵的秩 = = 10030 11603 02422 01211 ).2; 23111 612222 13288 ).1 BA 参考答案： 1） 13 21 1 2 31 2 8 1 4 6 11132 1113 2 222126 0041810 8 8 2 3 1 0 0 6 27 15 11132 95 00 1 2 22 00 0 0 0 rr rr r r rr A R + + = = 2 ） 13.求逆矩阵 4321 42 31 32 2 3 11210 11210 11210 000 40 000 40 030 41 3 030 41 030 41 000 41 03001 00040 00000 rrrr rr rr rr B R + ., 47 12 ).2, 300 020 001 ).1 11 = = AAAA 求求 参考答案： 1） 1 100 1 00 2 1 00 3 A = 2） 1* 41 1 72 AA A = （1 ） 当 满足什么条件 时， 下面的向量组线性相关： 1 11 (, , ) 22 =， 2 11 (,) ， 22 = 3 11 (,) 22 . = 1 或 1/2 11 2 2 33 111 123 11 11 0 1 1- - 2 240 2 11 -2+ 22 10+0 1 - - 2 2 kk k kkk kkk kk kk += 0+ += +=+= + = 解：由定义， （2 ） 已知向量 1 3 1 = ， 2 4 0 = ， 3 1 0 = ，则当 满足什么条件 时， 1 ， 2 ， 3 线性相关。 0 或 2 （3 ） 已知向量组 1 (1,2,3,4) = ， 2 (2,3,4,5) = ， 3 (3, 4,5,6) = ， 4 (4,5,6,7) = ， 则该向量组的秩是？ 2 （4 ） 向量组 1 (0,4,2 ) =， 2 (2,3 ,1) = ， 3 (1 , 2, 3) = 线性相关， 则实数 应满足什么条件？ 6 （5 ） 设向量 1 1 0 1 = ， 2 ， 3 0 1 0 = 0 0 1 = ，则向量 1 1 0 = 可表示为 1 ， 2 ， 3 的线性组合是？ 12 3 - + 1.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (1)(1，1，1，2，3)。 (2)(2，2，2，2，2)。 (3)(3，3，3，3)。 (4)(1，2，3，4，5)。 (5)(1，3，3，3)。 解 由于非负整数列 d( d 1 ，d 2 ， ，d n )是可图化的当且仅当 0(mod 2) ， 所以(1)、(2)、(3)、(5)能构成无向图的度数列。 = n i i d 1 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图 G 以为 1，3，3，3 度数列，不妨设 G 中 结点为 、 、 、 ，且 d( )1，d( )d( )d( )3。而 只能与 、 、 之一相邻，设 与 相邻，于是 d( )d( )3 不成立，矛盾。 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 2.有向图 D 如图 10-51所示： (1)求 D 的邻接矩阵 A。 (2)D中v 1到v 4长度为 4 的路有多少？ (3)D中v 1到自身长度为 3 的回路有多少？ (4)D 中长度为 4 的路数为多少？其中有几条回路？ (5)D 中长度小于等于 4的路有多少？其中有多少条回路？ (6)D 是哪类连通图？ 解 (1) 求 D 的邻接矩阵为： = 0100 1000 0100 0121 A 且有 = 01000 0100 1000 1321 2 A = 0100 1000 0100 3421 3 A = 1000 0100 1000 4621 4 A (2)由 4 A 中 可知， D中v4 )4( 14 =a 1到v 4长度为 4 的路有 4 条，分别为： 、 、 、 。 1 e 1 e 4 e 6 e 4 e 6 e 7 e 6 e 1 e 2 e 5 e 6 e 1 e 3 e 5 e 6 e (3)由 3 A 中 可知，D 中v1 )3( 11 =a 1到自身长度为 3 的回路只有 1 条，为 1 e 1 e 1 e 。 (4)D 中长度为 4 的路总数为 ，其中对角元素之和为 3，说明长度为 4 的回 路为 3 条。 16 4 1 4 1 )4( = =ij ij a (5)D 中长度小于等于 4 的路总数为 A、 2 A 、 3 A 、 4 A 中全体元素之和：7101316 46，其中回路数为：13138。 (6)由 可知，D 是单向连通图。 =+= 2200 2200 2200 81484 432 4 AAAAB 3. 如下图所示的赋权图表示某七个城市 721 , vvv null 及预先算出它们之间的一些直接通信 线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 参考答案： 用库斯克（Kruskal）算法求产生的最优树。算法为： 6161 5454 4343 37337 27227 71171 23),( 17),( 3),( 9),( 4),( 1),( vvevvw vvevvw vvevvw vvevvw vvevvw vvevvw = = = = = = 选 选 选 选 选 选 结果如图： 树权 C(T)=23+1+4+9+3+17=57（万元）即为总造价 4. 如下图所示的赋权图表示某六个城市 a,b,c,d,e,f 及预先算出它们之间的一些直接通信线 路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 (1) 6 6 4 3 2 1 55 5 5 f a b c d e 1 ()15 ()WT WT= 5. 在二叉树中 1） 求带权为 2， 3，5 ， 7，8 的最优二叉树 T。 2） 求 T 对应的二元前缀码。 参考答案： 由 Huffman 方法, 得最佳二叉树为： （ 4 分） （2 ）最佳前缀码为：000 ，001，01 ， 10， 11 （2 分） 6. 用 Huffman 算法求带权为 1，2 ， 3， 5，7 ， 9 最优二叉树，并计算其权值。 解：1）画出最优二叉树，如下图所示： （6 分） 1 2 3 3 6 11 5 27 16 9 7 2)计算其权值 （3 分） 63292725334241)( =+=TW 7. 一棵无向树 T 有8 个顶点，4 度、3 度、2 度的分枝点各 1 个，其余顶点均为树叶，则 T 中有几片树叶？ 答案是： m=n-1=7 x+(2+3+4)*1=7*2 x=5 8. 一棵树的 3 个 4 度点， 4 个 2 度点，其它的都是 1 度，那么这棵树的边数是多少？ 14 3*4+4*2+x*1=(3+4+x-1)*2 12+8+x=12+2x x=8 m=7+8-1=14