• / 8
  • 下载费用:20 金币  

离散试卷有答案.doc

关 键 词:
离散 试卷 答案
资源描述:
一、单项选择题 1.设A = {a, {a }},P(A)表示集合A的幂集,下列哪一个是错的?( ) A. B. C. D.2.设A={1 , 2 , 3 }上的二元关系R = {<1 , 1>, <1 , 2> , <1 , 3> , <3 , 3> } , 则R具备性质( )A.反对称的,传递的 B.反对称的 C.反对称的, 自反的 D.传递的3.集合A = {x, y, z }, B = {1, 2, 3},下列A到B的二元关系中,哪一个能构成函数?( )A.{, , , } B.{, } C.{, , } D.{, , }4.下列命题中( )是正确的。A.欧拉图的子图一定是欧拉图。 B.哈密顿图的子图一定是哈密顿图 。 C.平面图的子图一定是平面图 。 D.树的子图一定是树。5.设有向图D的邻接矩阵为,则D中长度为3的通路总数有( ) 条。 A.9 B.10 C.11 D.12二、填空题 1.公式的主析取范式为 。2.某班共有学生60人,其中有25人订杂志甲,26人订杂志乙,26人订杂志丙,11人订杂志甲和乙,9人订杂志甲和丙,8人订杂志乙和丙,还有8人未订任何杂志,则三种杂志都订的学生有 人。3.设A = {2,4,5,10,12,20},R为A上的整除关系,则A的子集B = {4,10,12}的极大元为 ,极小元为 ,上界为 ,下界为 。4.设 ,则函数f是 (单射,满射还是双射)。5.设集合A={ a , b , c , d , e}上的的划分S ={{a,d},{{b},{c,e}},则由划分S所确定的A上的等价关系R = 。6.用kruskal算法求得下图G的一棵最小生成树为 。v8图Gv1v2v3v4v512961248105711v6v737.设连通平面图G有4个面,9条边,则G有 个结点。三、解答题 ( 48 = 32分 )1.将下列语句翻译成命题逻辑公式或谓词逻辑公式。(1)(4分)只有天下大雨,小明才乘公共汽车上学。(2)(4分)不是所有整数都是奇数。2.设A = {1, 2, 3 }上的二元关系R = {<1, 1>, <1, 3>, <2, 1>},求R的关系矩阵,关系图。3.设是A到 A 的满射,且,证明 。这里 表示A 上的恒等映射。4.画图:(1)一个既没有欧拉回路,又没有哈密尔顿回路的图; (2)一个具有欧拉回路和哈密尔顿回路的图,并具体指出这两个回路。 5.用哈夫曼算法求带权为2,3,6,8,10,11的最优二元树并计算此最优树的权。6. 设一棵树T有7片树叶,3个度数为3的结点,其余结点的度数均为4,求T的结点总数。7.用二元有序完全树表示算术表达式并分别用波兰符号法和逆波兰符号法表示上述算术表达式。四、证明题 1.用演绎法证明下述论断的正确性。 2. 设R是集合A上的一个具有传递和自反性质的关系,T是A上的关系,使得 ,证明 T是A上的等价关系。3.试证明:树是一个偶图。4.用演绎法证明。5. P335 27,28 这类题一. 1 2 3 4 5 B A C C B二、1.2. 3 3. 10,12; 4,10; 没有; 24. 单射 5.6.7. 7三、1.解:(1)设P:天下大雨 Q:小明乘公共汽车上学,则有 (2)设Z(x):x 是整数,E(x):X是奇数 2.解: 3.略 4.略 5.解: 权 ( 定义10.3.7 ) 注:哈夫曼算法见书本(P292)算法10.3.6以及例10.3.9 6.解:设T有x个4度结点,则T的结点总数 ,边数 由握手定理 得 解得 所以结点总数 7. (1)-++d-hgji+feabc(2)算式的波兰符号表示式为 (书上P295:先根次序遍历算法… 省去括号 )(3)算式的逆波兰符号表示式为 (同上,用后根遍历,省去括号,规定… 即为… )四、1.证明: 2.证明:(1)对任意的,由R是自反的,得,所以,即T是自反的。 (2)对任意的,若,则 ,即有 从而,即T是对称的。 (3)对任意的,若,则 且即 且 又因为R是传递的 , 所以 从而 ,所以T是传递的。 由(1)、(2)、(3)知T是等价关系。 3.试证明:树是一个偶图。(P334:18)证:设 G= 是一棵树。任选 , 定义 V 的两个子集如下:, . 现证明V1 中任二结点之间无边存在。若存在一条边 (u,v), u,v, 由于树中任意两个结点之间仅存在唯一一条基本通路,故这条基本通路就是他们之间的短程线,设v0到u 的短程线为 ,则其长度为k+1,是偶数,因为(u,v),所以 ,v 是 到 v 的一条通路,且该通路的长度k+2 为奇数,从而它不是基本通路, 故v必与某个相同,从而 是G中的一条基本通路,这与G 是树矛盾。4.用演绎法证明。证明: (1) P (2) ES,(1) (3) P (4) US,(3) (5) T,(4) (6) T,(5)(2) (7) P (8) US,(7) (6分)(9) T,(8)(6) (7分)(10) EG,(9)5.在简单平面图G中,至少有一个度数小于等于5的结点。(P335:27)或5‘ 证明小于30条边的简单平面图G中至少有一个度数小于等于4的结点。(P335: 28 )
展开阅读全文
  亿读文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:离散试卷有答案.doc
链接地址:http://www.yddocs.com/p-2721241.html
侵权投诉举报 - 关于我们 - 联系我们 - 用户协议 - 网站免责声明 - 网站地图 - 帮助中心 - 人才招聘

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站文档被用户下载所得收益归上传人(含作者)所有。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1444168621 欢迎举报。

copyright@ 2019-2029 亿读文库-在线文档分享下载平台 网站版权所有

ICP许可证编号:黔ICP备19010449号      贵公网安备 52052702000145号





收起
展开