《离散2002-2003试卷A》由会员分享，可在线阅读，更多相关《离散2002-2003试卷A（4页珍藏版）》请在金锄头文库上搜索。
1、广东外语外贸大学计算机科学与技术系离散数学课程2002-2003学年第二学期期末考试试卷 （A）考卷适应班级 时间：120分钟学号 班级 姓名 成绩题次一二三四五六七八九十总分评卷人分数202010810101012100评分一、 选择题：（从四个答案中选取唯一的正确答案填到右边空格内，每题2分，共20分）：1下列语句中是真命题的为（ ）A我正在说谎； B.不准喧哗；C如果1+2=3，那么雪是黑的。 D. 如果1+2=4,那么雪是白的。2设A（x）：x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号为（ ）A（x(A(x)B(x)）;B. x(A(x) B(x);C. （x(A(x) B
2、(x)）;D. （x(A(x) B(x)）.3设A=1，2，3，4，5，6，7，8，下列选项正确的为（ ）A1A；B. A， C。4，5A； D。1，2，3A.4集合A上的关系r是相容关系的充要条件是:r是（ ）A自反，反对称的； B。自反，对称的；C反自反，对称的； D。传递、自反的.5设A=a,b,c, B=1,2 令f：AB，则不同的函数的个数为（ ）A2+3个； B。2 个 C。23个， D。3 个.6I是整数集合，函数f定义为II，f（x）=|x|-2x，则f是（ ）A 单射；B。满射； C。双射； D。非单射也非满射。7在自然数集N上，下列哪个运算是可结合的（ ）Aa*b=a-b；
3、 B.a*b=max（a,b）； C.a*b=a+2b；D.a*b=|a-b|8.下列运算中，哪个运算关于整数集不能构成半群Aa b=max（a,b）； B. a b=b C. a b=2ab D. a b= a-b 9.在有n个结点的连通图中，其边数（ ）A最多有n-1条； B。至少有n-1条； C。最多有n条； D。至少有n条。10设有33盏灯，拟公用一个电源，则至少需要具有五插头的接线板数为（ ）A 7； B。8； C。9； D。14二、填空题 （每空1分，共20分）1 前提：（PQ）R, RS, S的有效结论是。2.（PQ）的主析取范式为，主合取范式的编码表示为。3实数集R 上的小于等
4、于关系“”是、和的关系。4.举出三个不同的可数集合；。5.设Q是有理数集合，对任意的a, bQ, 定义二元运算为 ab=a+b-ab, 则的幺元是，零元是，2的逆元是。6.设G=, |V|=n, |E|=m, v是G中度数为k的结点， e是中一条边，则Gv（删去结点v）中有 个结点，条边；Ge(删去边e)中有 个结点，条边。7.设G是具有n个结点的简单图，如果 G 中每一对结点度数，则在G 中存在一条汉密尔顿回路。8.连通图是一棵树，当且仅当每条边.9.无向图G 由 k(k2) 棵树组成的森林，至少要添加条边，才能使G成为一棵树。10.完全7叉树,其树叶数为55，则其分支点数为。三、判断题（在
5、括号内填上“”或“”，每题1分，共10分）1（ ）A：小张和小李是广外大学生，则 A：小张和小李都不是广外大学生。2（ ）二元关系不是自反的，则必为反自反的。3（ ）每一个良序集合，一定是全序集合。4（ ）实数集R上的小于等于关系“”是偏序关系。5（ ）设 是一个代数系统，aA ，如果 a 有左逆元则必有右逆元。6（ ）欧拉图中每个结点的度数必为偶数。7（ ）两个非空集合A和B，如果B是A的真子集，必有B的基数小于A的基数。8（ ）连通图必有一棵生成树。9（ ）一个汉密尔顿图中必有一条欧拉回路。10（ ）任意一棵二叉树的树叶可对应一个前缀码。四、画出4个结点、三条边的所有非同构的无向简单图.（10分）五、设集合A=2，3，4，5，是A上的二元运算，定义运算ab=maxa,b, 请写出的运算表，判断是否为独异点，是否有零元，并指出有逆元的元素.（10分）六、证明一棵完全二叉树必有奇数个结点.（10分）七、设G是边数小于30的简单平面图，试证明G中存在结点v, deg(v)4. (10分)八、给定权3，4，5，6，7，8，9，试用算法构造一棵最优二叉树，画出这棵树并计算出它的权。（12分）
