离散数学试题B(计科)

——

E. 满射非单射 F.单射非满射 G,<5,6> H,{<5,6>} J,以上答案都不对.

—

11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 —得 分 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 —— 一、选择题（每个选择1分，共25分）

140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 — 把你所选答案前的字母填入括号内.

1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. ——1.无向图G注：请将所在的院（系）中有16条边，且每个结点的度数均为、专业、班级、姓名和学号写在密封线内，不要写在其它地方2，则结点数是( )

A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10

—A.8 B.16 C.4 D.32

12. 为每个逻辑断言选择正确的解释。T(x)：x今天来上课，S(x)：x学计算机专业的学生，

线—2.设A={a,b,c}，则下列是集合A的划分的是( )

P(x)：x编程序，G(x)：x玩游戏。个体域是殷都大学。 —A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},c} D.{{a},{b,c}} x T(x)表示（ ），x T(x)表示（ ），x T(x)表示（ ），x(S(x)→P(x))——3.设集合X={0,1,2,3}R是X上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，

表示（ ），x(S(x)∧G(x))表示（ ），x(S(x)∧P(x))表示（ ），x(S(x)→G(x))—则R的关系矩阵MR是( )

表示（ ）。

——110A 学计算机专业的学生会编程序，B 殷都大学的学生都是计算机专业且会编程序。—10101010C 有些计算机专业的学生玩游戏，D 所有同学今天都来上课了，E 今天有同学没—01111—A．1100来上课。F 计算机专业的学生玩游戏，G 今天没有同学来上课。

— B.001100001 D. 0001 —00011100 C. 10110得 分 二、计算与应用题（共40分）

—001100010111001010—4.下列描述中，不正确的是( )

1. S={ 1，2，„，10 }，定义S上的关系R={ | x,y∈S ∧ x+y=10 }， —封 A.P({a,{b,c}})={φ,{a},{{b,c}},{a,{b,c}}} B.P({φ})={φ,{φ}} 试列举出R中的所有有序对，并分析说明R具有哪些性质。(10分)

— 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.再过5000年，地球上就没水了。 ——D.我正在说谎

—9.给定算式: {[(a＋b)＊c]＊(d＋e)}＋[f－(g＊h)] —— 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ).

—A、＋＊＊a＋bc＋def－g＊h B、＋＊＊＋abc＋de－f＊gh —C、＊－＊＋abc＋de－fgh＋ D、ab＋c＊de＋＊fgh＊－＋

—10．设R,Z,N分别为实数,整数和自然数集，函数f：R→R，f(x)＝x，f是（ ）;

2．在偏序集中，其中Z={1,2,3,4,6,8,12,24}，≤是Z中的整除关系，求集合

第 1 页 共 3 页

______专业_____________ 班 ______学号______________ D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。(12分)

______________ 系

4. 若图G的邻接矩阵是A，试通过矩阵讨论图的连通性。（10分）

0 1 0 0 Ａ＝ 0 0 1 0 1 0 1 1 0 1 0 1

_ ____________________ __ __ _ _名 _ _姓 _ 线要 题 封不 答 密内——— ——线 —封——密—————————————————————————————————————————————

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

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

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

第 2 页 共 3 页

系系 班 班___ _______ __得 分

____________________ ____________________业_号 专业___专学_____________________________________________________________________________ ____ __ __ __ __ __ __ __ __ 名_ __ 名______ __ __ _ 姓 姓_____线 要 线 要 题 题 封 不 封 不 答 答 密 密内 内———————线———封——线 密——封—————密——————————————————————————————————————————————————————————————————————————————————————— 三,证明题（共35分）

1.有N个人，已知他们中的任何二人合起来认识其余的N-2个人。证明：当N≥3时，

这N个人 能排成一列，使得任何两个相邻的人都相互认识。而当N≥4时，这N个人 能

排成一个圆圈，使得每个人都认识两旁的人。(12分)

3．

2．设f是A到B的映射，g是B到A的映射。证明：f是单射的充分必要条件是fg=IA；

f是满射的充分必要条件是gf=IB。（13分）

第 3 页 共 3 页

设G为n（n≥5）阶简单图，证明G或G中必含圈。（10分）