离散数学 练习题三

9. 给定算式 : ＋ (b ＊ c)) ＊ d － e) ÷ (f ＋ g)) － ((h ＊ i) ＊ j) (((a 离散数学 练习题三 ___________________ __题_ 号 学 _ _ _ __答_ _ _ _ _ _ _ _ __要名 姓 班 _不_ _ _ _ _ _ _ _ __内_ _ 业 专 _ _ __线_ _ _ _ _ _ _ _ __封_ _ _ _ _ _ 系 密 ____________________—— 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ).

——题 号 一 二 三 四 五 六 七 八 九 十 总分 A、－＊＊a＋bc＋def－g＊hij＊＊ B、abc＊＋d＊e－fg＋÷hi＊j＊－

—C、－÷－＊＋a＊bcde＋fg＊＊hij D、ab＋c＊de＋＊fgh＊－＋ij＊－

—得 分 10．设R,Z,N分别为实数,整数和自然数集，函数f：R→R，f(x)＝x，f是（ ）; ——阅卷人 g: Z→N, g(x)＝|x|, g是( ); h: N→N×N. h(n)＝﹤n,n＋1﹥,h({5})＝( ) — A．满射函数 B．单射函数 C．双射函数 D．非单射非满射 —— 注：请将所在的院（系）、专业、班级、姓名和学号写在密封线内，不要写在其它地方 E. 满射非单射 F.单射非满射 G,{<5,6>} H,<5,6> J,以上答案都不对. —线得 分 —一、选择题（每个选择2分，共40分） 11. 对60个人的调查表明有25人阅读News,26人阅读Times,26人阅读Happy,9人

— 阅读News和Happy,11人阅读News和Times,8人阅读Times和Happy,还有8 — 把你所选答案前的字母填入括号内. 人什么杂志也不阅读.问阅读全部3种杂志的有( )人,只阅读News的有( )人, —1.无向树T中有3个3度,2个2度顶点,其余顶点都是树叶，T有几片树叶 ( ) 只阅读Times的有( )人,只阅读Happy的有( )人,只阅读一本杂志的有( )人. ——A.8 B.6 C.4 D.5 A.5 B.8 C.3 D.15 E.30 F.13 G.65 H.12 J.60 K.10 —2.设A={a,b,c}，则下列是集合A的划分的是( ) 12. S＝Z×Z,有S上的二元运算＊:,其中 对任意﹤a ，b﹥，﹤x ，y﹥∈S都有 ——A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},{c}} D.{a,{b,c}} ﹤a ，b﹥＊﹤x ，y﹥＝﹤ax ，ay＋b﹥ —3.设集合X={0,1,2,3}R是X上的二元关系，R={<0,0>,<0,2>,<1,0>,<1,1>,<2,3>,<3,2>,<3,3,>}， ﹤5 ，8﹥＊﹤3 ，6﹥＝( ) ——则R的关系矩阵MR是( ) A. <16,9> B, <17,12> C,<16,36> D.<15,38> ——?—?1010??1010??0001??1110?13. G＝{0,1,2,3},若＊为模4乘法,则﹤G ，＊﹥构成( )

1100???? A, 半群,不是群 B ,群 C. 以上答案都不对. 封?1010???A．?—?—?0001?? B.?0011?1100?? C. ??0011得 分 二、应用题（共32分）

—?0011????0001???0101?? D. ??0001?? ?1110???1010?? 1. 1. 有1克砝码3个,2克法码4个, 4克法码2个, 问能称出哪些质量?

——4.下列描述中，不正确的是( ) 每种质量的称重方案有多少种? (10分) —A.P({a,{b,c}})={φ,{a},{{b,c}},{a,{b,c}}} B.P({φ})={φ,{φ}}

— C.P(φ)={φ} D.P({a,{b,c}})={{φ},{a},{{b,c}},{a,{b,c}}} ——5.设个体域是正整数集，则下列公式中真值为真的公式是( ) ——A.(?x)(?y)(x·y=0) B.(?x)(?y)(x·y=1) —C.(?x)(?y)(x·y=2) D.(?x)(?y)(?z)(x÷y=2)

——6.令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解 —在某种液体中”可符号化为( ) 密A.(?x)(F(x)∧(—?y)(G(y)∧H(x,y))) B.(?x)(?(x)F(x)→(G(y)→H(x,y))) —C.(?x)(F(x)→(?y)(G(y)∧H(x,y))) D.(?x)(F(x)→(?y)(G(y)→H(x,y)) —7.在个体域D={a,b}中，与公式(—?x)A(x)等价又不含量词的公式是( ) —A.A(a)∧A(b) B.A(a)→A(b) C.A(a)∨A(b) D.A(b)→A(a) —8.下列句子是命题的是( ) ——A.水开了吗? B.x>1.5 —C.再过9000年，地球上就没水了。 ——D.我没讲真话。

第 1 页 共 3 页

班 _ __________ 系______ _________________业号_专学 _______________________________________ __ __ _ _名 _ _姓 _ 线要 题 封不 答 密内——— ——线 —封——密—————————————————————————————————————————————

2．求294与65的Gcd,并将它表示成294和65的线性组合,即求x,和y使得

Gcd(294,65)=294 x+65y. (6分)

3．设7个字母在通信中出现的频率如下:

a: 30%, b: 20%, c: 15%, d: 10%, e: 5%, f: 5%, g: 5%.

编一个最佳2元前缀码.在这个前缀码中,a,b,c,d,e,f,g的码长分别是多少? 传输10000个按上述比例出现的字母需要多少个二进制数字.(8分).

考生注意:从下面4,5,6三题中选做一题.

4.设V＝﹤A ，＊﹥是代数系统,其中A＝{0,1,2,3,4}.对任意a,b∈A, a＊b＝(ab) mod 5.

(1) 列出＊的运算表.

(2) ＊是否有零元和单位元? 若有单位元,请求出所有可逆元素的逆元.(8分)

5.设V1=<{0,1,2},⊙>,V2=<{0,1},＊>,其中⊙表示模3加法,＊表示模2乘法. 试构造积代数V1×V2的运算表.若有单位元指出其单位元.(8分)

6.1231000的十进制表示的个位数是多少? (8分)

第 2 页 共 3 页

系 系班_ __ 班___ __________________________ ____________________业_号 专业___专学_____________________________________________________________________________ ____ __ __ __ __ __ __ __ __ 名_ __ 名______ __ __ _ 姓 姓_____线 要 线 要 题 题 封 不 封 不 答 答 密 密内 内———————线———封——线 密——封—————密———————————————————————————————————————————————————————————————————————————————————————

得 分 三,证明题（共28分）

1.设V=是半群,对任意a,b,c∈S,如果a,b都与c可交换,

证明:a*b也与c是可交换的.(8分)

3．设G＝Z，对G规定“＊”如下：a＊b＝a＋b－3 证明：﹤G ，＊﹥是一个群。（8分）

2．设f是双射，且fg有意义。证明：g是单射的充分必要条件是fg是单射；g是满射的 充分必要条件是fg是满射。（12分）

第 3 页 共 3 页