《离散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分)