交大 离散 期末考卷lisan20070711ab答案.doc

上海交通大学试卷( AB 卷答案)

A一选择题(50’,每题2’, 在错误答案上划\,在题号上写得分。)
D B B A D C D C D B C D B A A B D A B A D B A D A
B五选择题(50’,每题2’)
B D D C B A B A B B A B B C A B D C D C B D D B D
A二 B六填空题(30’,每题2’, 在错误答案上划\,在题号上写得分。)
1-100的这100个整数中,能被2,3,5之一整除的数有_______74__________个。
设,则
含个结点的简单图共有个。
设A = {1, 2, 3, …., 13, 14, 15}, 定义R={<x,y>|xºy(mod 4),x,yÎA},
则[2]=_ __ {2,6,10,14}______________
5. 设A和B都是有穷非空集合,A和B的基数为n, 则A到B有_____ __n!________种不同的双射。
,
,,
则_____x+6 __________
下图的一条欧拉回路是_(e1,e2,e3,e4,e7,e5,e6,e8)_或点的序列或点边序列。
设图G=(V,E)有7个结点,其中6个结点的度都为3,一个结点的度为6,
则该图有 12 条边。
有向图G的关联矩阵为,
则其邻接矩阵为:
f(v1)=b,f(v2)=a,f(v3)=c,f(v4)=e,f(v5)=d,f(v6)=f 。
,个结点的度为2,…,个结点的度为k-1,结点最大的度为k。问度为k的结点有个。
某简单平面图有8个结点,18条边,则每个域的边数是 3 。
在K3,K4,K5,K6,K型图)中,非平面图为 K5,K6,K型图。
对于权序列,构造Huffman树,则带权路径总长为 34 。
A三B三.(5') 对任意的集合A,证明

证明: 空集是任意集合的子集。
(3’)
(1’)
由上面两式知:。(1’)
A四B二.(5') 设是非空集合A上的二元关系,是自反的、传递的,试证:
证明:若,所以存在,使得
,
又因为是传递的,所以可以得到。(2’)
若,因为是自反的,所以有,于是得到
由此即知。(3’)
所以由, 可知。
A五B一.(5')下图中直线的交点都为图的结点,共有18个结点。
判断图中是否存在欧拉回路,若有,