i) 自反的：?a?A a-a=0k ∴a?a(mod k) ii) 对称的：若a?b(mod k) 则a-b=mk, ∴b-a=(-m)k ∴b?a(mod k)
iii) 传递的：若a?b(mod k) b?c(mod k) 则a-b=m1k b-c=m2k a-c=(a-b)+(b-c)= m1k + m2k =(m1＋m2)k ∴a? c(mod k)
十五、 求带权为1, 1, 2, 3, 4, 5的最优树。 参考答案
W(T) = 2 + 4 + 7 + 16 + 9 = 38
十六、 用狄克斯特洛算法求下图中a到z的最短通路。
十七、 已知权值 W={ 7，8，9，12，16 } (1) 画出一棵最优树，并求出该最优树的权值。
(2) 请依据最优树，为每个节点设计一种最优前缀码的编码方案。 参考答案
（1）
最优树的权值为： W=(7+8)×3＋(9+12+16)×2=45+74=119 （2）9：00 ，12：01，7：100，8：101，16：11
十八、 设A={2,3,4,6,12}，若关系R为定义在A上的整除关系，请回答下列问
题。
(1)请画出A的哈斯图
(2)请根据关系R给出A的极大、极小、最大和最小元。 (3)请给出集合{4,6,12}的极小元及下确界。 参考答案
12463（1）A的哈斯图：
2
（2）A的极大元为12，极小元为2,3，最大元为12，最小元不存在 （3）{4,6,12}的极小元为4,6，下确界为2。
十九、 设集合A?{a1,a2,a3,a4,a5}。用Washall算法求A上关系R的传递闭包：
R?{(a1,a2),(a2,a3),(a3,a4),(a5,a1),(a5,a5)}。
参考答案
利用Washall算法求得传递闭包t(R)的关系矩阵为：
?0?0?t(R)??0??0??1
1110?0110??0010??
0000?1111??
相关推荐：
loading