大学离散数学复习试题_大学离散数学总复习题

大学离散数学复习试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“大学离散数学总复习题”。

离散数学练习题目

一、选择题

1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。

A、A； B、{6，7，8}A； C、{{4，5}}A； D、{1，2，3}A。

2.已知集合A={a,b,c},B={b,c,e},则 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列语句中，不是命题的是____A_________ A.我说的这句话是真话； B.理发师说“我说的这句话是真话”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以这些煤不会燃烧；

4.下面___D______命题公式是重言式。

A.PQR ； B.(PR)(PQ)；C.(PQ)(QR)；

D、(P(QR))((PQ)(PR))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为___D______。

A、x(L(x)A(x,y))； B、x(L(x)y(J(y)A(x,y)))； C、xy(L(x)J(y)A(x,y))； D、xy(L(x)J(y)A(x,y))。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元 8． 设SAB，下列各式中____B___________是正确的。

A、domSB ； B、domSA； C、ranSA； D、domS  ranS = S。9．设集合X，则空关系X不具备的性质是____A________。

A、自反性； B、反自反性； C、对称性； D、传递性。

10.集合A，R是A上的关系，如果R是等价关系，则R必须满足的条件是__D___ A.R是自反的、对称的 B.R是反自反的、对称的、传递的 C.R是自反的、对称的、不传递的 D.R是自反的，对称的、传递的 11.集合A={a,b,c,d},B={1,2,3},则下列关系中__ACD______是函数

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} 已知集合 RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},则顶点2的入度和出度分别是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n≥2)，m条边，当下面条件__C____满足时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 14.下面叙述正确的是____B______ A.二部图K3,3是欧拉图 B.二部图是平面图

K3,3是哈密尔顿图

C.二部图 K3,32

D.二部图K3,3是既不是欧拉图也不哈密尔顿图

15.已知某平面图的顶点数是12，边数是14，则该平面图有__D___个面 A.3 B.2 C.5 D.4 16．设G是n个结点、m条边和r个面的连通平面图，则m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面几种代数结构中，不是群的是___D____ A.B.C.D.(这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)

二、问答题

1.在程序设计过程中，有如下形式的判断语句： if(a>=0)if(b>1)if(c

请将这段程序化简，并说明化简的理由。解：简化的程序：

if(a>=0 && b>1 && c

设置命题变量： p: a>=0；q:b>1;r:c

A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①证明R是偏序关系。

②写出偏序集（A，R）的极小元、极大元；最小元、最大元 ③写出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根据整除性质可知，R满足自反性，反对称性，传递性。所以R是A上的偏序关系。

②偏序集（A，R）的极小元：1，极大元：5, 6，7，8，9 最小元：1； 最大元：无

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m个男孩子，n个女孩排成一排，任何两个女孩不相邻，有多少种排法？

(n

(2)如果排成一个园环，又有多少种排法？

解：(1)考虑5个男孩，5个女孩的情况

男孩的安排方法： _B_B_B_B_B_ 排列总数P(5,5)女孩的安排方法：6个位置安排5个女孩，排列中数 P(6,5)所以：总的排列方法数是 m!*p(m+1,n)

(2)考虑男孩的圆排列情况，结果是(m-1)!*p(m,n)

4.某商家有三种品牌的足球，每种品牌的足球库存数量不少于10只，如果我想买5只足球，有多少种买法？如果每种品牌的足球最少买一只，有多少种买法？

解：①这是一个多重集的组合问题

类别数是k=3，选取的元素个数是 r=5 多重集组合数的计算公式是 N所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由选取的球只有2个 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(rk1)!C(kr1,r)

r!(k1)!

5．某软件公司将职工分为三种岗位。该公司65人，有些职工（例如项目管理人员、设计人员）可能从事不止一个岗位的工作。每个职工至少被分在一个岗位。现在软件设计岗位（岗位A）（包括需求分析、概要设计和详细设计等工作）的人数是15人，代码编写岗位（岗位B）的人数是32人，软件测试岗位（岗位C）的人数是28人，同时参加岗位A和岗位B的有12人, 同时参加岗位B和岗位C的有8人, 同时参加岗位A和岗位C组的有3人，问，三个岗位参加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 设S表示全班同学总人数，则 |S|=65 求：|A∩B∩C|=？

根据容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因为每个同学至少参加一个小组，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三个小组都参加的人数是13人

6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

说明：也可以直接利用组合演算公式进行演算 7.求1228的个位数是多少? 解：1228的个位数就是1228 mod 10的余数1228mod10(12mod10)28mod1024*7mod10(27mod10)4mod108mod1064

8.已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于2, 问G至少有多少个顶点?

解：由握手定理∑d(v)=2m=20，度数为3的顶点有3个占去12度，还有8度由其余顶点占有，而由题意，其余顶点的度数可为0，1，当均为1时所用顶点数最少，所以应有8个顶点占有此8度，即G中至少有8+4=12个顶点。

9刑侦人员审一件盗窃案时，已经掌握的线索如下：（1）甲或乙盗窃了电脑。

（2）若甲盗窃了电脑，则作案时间不能发生在午夜前。（3）若乙证词正确，则在午夜时屋里灯光未灭。（4）若乙证词不正确，则作案时间发生在午夜前。（5）午夜时屋里灯光灭了。

请通过命题逻辑推理，推论出谁是真正的盗窃犯？（写出详细的推理步骤）解 设p： 甲盗窃了电脑，q： 乙盗窃了电脑，r： 作案时间发生在午夜前，s： 乙证词正确，t：午夜时屋里灯光灭了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的时间T与数据规模n的递推关系如下，求出T与n的显示关系表达式

T(n)T(n1)n1 T(1)0

解：

T(n)T(n1)n1 T(n2)n2n1T(n3)n3n2n1 T(nk)nkn2n1T(nk)kn-(12k)k(k1)T(nk)kn2令n-k=1，那么 k=n-1，所以：

n(n1)n(n1)n(n1) T(n)T(1)0222答：T与n的显示关系是：T(n)

11.解下列一阶同余方程组

n(n1)2x1(mod 3)x2(mod 4)x3(mod 5)解：已知a11,a22,a33;m13,m24,m35 方程组的齐次通解是：xkLcm(1,2,3)6k 60k 根据中国剩余定理，特解是：

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)M1m2m320,M2m1m315,M3m1m212 111M1mod m1是下列同余方程的解

3)，解得：x=2，即M12 M1x1(mod m1)即20x1(mod11同理可解得：M23，M33 11 7

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)mod m（120221533123）mod 60111所以：(4090108)mod 60238mod 6058

同余方程组的解是 xxx06k58 60k

12.假设需要加密的明文数据是a=8,选取两个素数p=7,q=19,使用RSA算法： ① 计算出密钥参数

② 利用加密算法计算出密文c ③ 利用解密算法根据密文c反求出明文a 解：① 取 p=7,q=19;计算 n=p*q=7*19=133 计算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 选取较小的数w,使w与108互质, 5是最小的,于是w=5 计算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余数为1, 于是算出d=65 至此加密、解密参数计算完成：

公钥w=5,n=133.私钥d=65,n=133.② 加密

cmwmodn85mod133((82mod133)*(83mod133))mod133

(64*113)mod13350③ 解密

acdmodn5065mod133

aA0A6 其中，A050, Ai(Ai1)2

根据上述递推公式可以计算出：A1502mod133106,A21062mod13364

A3642mod133106，„„, A61062mod13364 aA0A6(50*64)mod1338

解密后的明文与原来的明文是相等的，所以算法正确。

13.设A={1，2，3，4，6，9，12，24},R定义为R{(a,b)|ab(mod 3)}，（1）证明R是一个等价关系；（2）写出A的商集；

14.基于字典序的组合生成算法

问题说明：假设我们需要从5个元素中选取3个的所有组合，已知组合个数为 C（５，３）＝１０，按字典序，其具体组合为： 123,124,125,134,135,145,234,235,245,345 所谓按字典序生成组合，就是已知当前的组合（例如135），求下一个组合（例如，145）。下面给出算法的函数头：

//数组s[]:函数运行前，保存当前的组合，函数结束后，是新生成的下一个组合 //n,r:表示从n个元素中选取r个元素的组合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某单位要从A,B,C三人选派若干人出国考察, 需满足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 9