浙江科技学院考试试卷
8. (8 points) Answer the following questions for the partial order
得分 represented by the following Hasse diagram.
l k a) b) c) d) e) f)
Find the maximal elements. Find the minimal element Is there a greatest element? Is there a least element?
Find all upper bounds of {a, b, c}.
Find the least upper bound of {a, b, c}, if it exists.
g) Find all lower bounds of {f, g, h}.
h) Find the greatest lower bound of {f, g,
g}, if it exists.
j m\\ i h g d a ef bc
得分 9. (6 points) Let R be the relation on the set A={a,b,c,d} such that the matrix of R is
1 1 0 0
MR=
0 1 0 1 0 0 1 0 1 1 0 1
Find：
第 5 页 共 8 页
浙江科技学院考试试卷
(1) reflexive closure of R. (2) symmetric closure of R. (3) transitive closure of R.
得分
10. (8 points)
(1)Show that there is exactly one greatest element of a poset, if such an element exists.
(2) Show that the least upper bound of a set in poset is unique if it exists.
11．(6 Points) Find the main DNF (Disjunctive Normal Form) of the
得分 formula ～（P∧～Q）∧（～Q∨R ）∧～R
第 6 页 共 8 页
浙江科技学院考试试卷
12. (7 Points) Draw a Huffman tree and find the Huffman code of
得分 “A: 2/12”, “C: 1/12”, “D: 2/12”, “G: 1/12”, “N: 1/12”, “O: 1/12”, “S: 2/12”, “T: 2/12” according to the frequencies occur in the sequences of “CATSTANDDOGS”. And draw a new binary tree
whose preorder search produces the string CATSTANDDOGS, and draw again inorder search produces the string CATSTANDDOGS and postorder search produces the string CATSTANDDOGS.
第 7 页 共 8 页
浙江科技学院考试试卷
13. (8 Points) Complete the following table so that it defines a
得分 monoid and show the binary operation’ properties of this monoid.
* e a b c d f e e a b c d f
a e b b d e f a c c c f a d b e d f f c d a b e
第 8 页 共 8 页
