2010秋夜大离散数学模拟题答(2010.12李)

《2010秋夜大离散数学模拟题答(2010.12李)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010级计算机科学与技术专业夜大离散数学模拟题答案姓名标准答案学号序号成绩100注意事项：1、本试卷满分100分，考试时间120分钟；2、请将答案一律写在试卷空白处。统分栏：题号一二三四五六总分得分151510202020100一、单项选择题（每题3分，共15分）1、令p：经一堑；q：长一智。将命题’’经一堑，长一智’’符号化为　　　[Ｂ]A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p2、10阶无向简单图G中有4个奇数度顶点，其补图中必有r个奇数度顶点[C]A．r=4；B．r=5；C．r=6；D．r=73、命题公式A=p∧﹁p→q的主析取范

2、式为[C]A．A=∑（0,1,2）。B．A=∑（0,2,3）。C．A=∑（0,1,2,3）。D．A=∑（1,2,3）。4、19个顶点的2-元正则树有多少片树叶？[C]A．38；B．19；C．10；D．9。5、10阶无向连通图G的边数为m，则其生成树的树枝数为[A]A．9；B．10；C．11；D．m。二、判断下列各题的是非（题中,m,n分别为边,顶点数.每题3分，共15分）。1、任何无向图都有一棵生成树。[非]2、令F（x）：x是兔子；G（y）：y是乌龟；H（x，y）：x比y跑得快。将命题“所有兔子比某些乌龟跑得快”符号化为：x（F（x）→彐y（G

3、（y）∧H（x，y）））。　[是]3、无向连通图G（m,n）的每一条边都可以成为他的某一生成树的树枝。[非]4、个体域是有理数集合，则xy彐z（x-y=z）为假命题[非]5、无向连通图G（m,n）的某一生成树T中必有关系m=n-1。[非]三、计算题(10分)1、无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有几个顶点.[8]22、无向图Ｇ中2个3度顶点，3个4度顶点，4个5度顶点，则Ｇ中有几条边．[18]四、填空题（每题4分，共20分）1、一阶逻辑公式彐xF（x）→彐yG（y）的类型是可满足式2、5阶非平凡无向树至少有2片树叶..3、

4、无向图G有生成树的充分必要条件是连通。4、无向图G（n，m）中，若边m大于等于顶点n，则图中必有圈。5、任何连通图G中,边数m不一定大于顶点数n.五、奥运会到了,给外国友人发电子邮件”福娃”--Friendlies的最佳前缀码共用二进制码多少位?(20分)1、最优二元树T；2.30位；3、每个字母的码字；4.等长码?F--000,r--001,i--01,n--1000,d--1001,e--101,l--110,s--111.六、证明题（20分）用附加前提法证明下面的推理：说明如下:前提：P，q∨﹁r，q→（p→s）。结论中的前提r移过来,与前

5、提2，构成结论：r→s.公式3,从而得到q,q与前提3构成公式3,从而得到（p→s）再与前提1构成公3得S.证毕.　　　扣题:推理正确.2